==== Given integer n>=1 let a(n) = number of non-congruent solutions of x^3 + y^3 == 1 mod n . Is there a simple formula for a(n) ? ==== > Given integer n>=1 let a(n) = number of non-congruent solutions of > x^3 + y^3 == 1 mod n . > > Is there a simple formula for a(n) ? Theorem 2 of Section 3 of Chapter 8 of Ireland and Rosen, A Classical Introduction to Modern Number Theory: Suppose p is a prime, congruent to 1 mod 3. Then there are integers A and B such that 4p = A^2 + 27 B^2. If we require A congruent 1 mod 3, A is uniquely determined, and the number of solutions of x^3 + y^3 = 1 mod p is p - 2 + A. -- Approved: Daniel Grayson, dan@math.uiuc.edu, moderator for sci.math.research ==== >Given integer n>=1 let a(n) = number of non-congruent solutions of >x^3 + y^3 == 1 mod n . >Is there a simple formula for a(n) ? This is sequence A087412 in the On-line Encyclopedia of Integer Sequences . No formula for it is given there. Note however that if phi(n) is not divisible by 3, the map x -> x^3 is 1-1 and onto on Z_n, so in that case a(n) = n. Also, a(n) is a multiplicative function, i.e. a(mn) = a(m) a(n) if m and n are relatively prime. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 Approved: Daniel Grayson, dan@math.uiuc.edu, moderator for sci.math.research ==== >Given integer n>=1 let a(n) = number of non-congruent solutions of >x^3 + y^3 == 1 mod n . >Is there a simple formula for a(n) ? > This is sequence A087412 in the On-line Encyclopedia of Integer Sequences > . No formula > for it is given there. Note however that if phi(n) is not divisible by 3, > the map x -> x^3 is 1-1 and onto on Z_n, so in that case a(n) = n. Oops: of course it's not true that x -> x^3 is 1-1 and onto on Z_n. It's 1-1 and onto on the group G(n) of members of Z_n relatively prime to n. Nevertheless, I believe it is still true that a(n) = n if phi(n) is not divisible by 3. Moreover (from numerical evidence) it looks like a(p^k) = p^(k-1) a(p) for any prime p <> 3 and positive integer k, while a(3^k) = 3^(k-2) a(9) for k >= 2. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ==== Your conjectural formula a(p^k) = p^(k-1) a(p) for any prime p <> 3 and positive integer k is correct. This follows from Hensel's lemma, since the equation x^3+y^3=1 is non-singular modulo p, except for p=3. Your formula when p=3 is also fine; Hensel's lemma says that even if the equation is singular, you simply need to start with some higher power congruence, depending on how bad the singularity is. In general, if a(f,n) denotes the number of solutions to f(x,y)=0, where f(x,y) is a polynomial with integer coefficients, then a(f,p^k) = p^{k-1}a(f,p) provided the curve is nonsingular, or what comes to the same thing, provided f, df/dx, and df/dy do not have a simultaneous root in the algebraic closure of Z/pZ. In the present instance, f = x^3+y^3-1, df/dx = 3x^2, df/dy = 3y^2, so it's clear there is no simultaneous solution unless p = 3. Suppose now that phi(n) is not divisible by 3. Since both phi(n) and a(n) are multiplicative (Chinese remainder theorem), it suffices to prove that a(n) = n when n is a power of a prime, say n = p^k. Further, from the formula above, unless p = 3, it's enough to check it for n = p. But phi(p) = p-1, so it suffices to check it when p-1 is not divisible by 3. In other words, it needs to be checked when p = 2 (mod 3), and you already noted that it is true in that case since every element of Z/pZ is a cube. That leaves the case p=3 to check. But if n = 3^k with k > 1, then phi(n) is divisible by 3. So we're left to check that a(3) = 3, and the solutions mod 3 are (1,0), (0,1), (2,2). That completes the proof that a(n) = n when phi(n) != 0 (mod 3). Finally, to get back to the question of the value of a(p), the hard case is p = 1 (mod 3). In that case, there are formulas for a(p) using cubic residue symbols (see, e.g., Ireland-Rosen's book on number theory). More importantly, if you build all of the a(p) values into an L-series, it turns out that the L-series factors as a product of two Hecke L-series. This is a particular case of the theory of complex multiplication of elliptic curves. JHS >Given integer n>=1 let a(n) = number of non-congruent solutions of >x^3 + y^3 == 1 mod n . > >Is there a simple formula for a(n) ? > > This is sequence A087412 in the On-line Encyclopedia of Integer Sequences > . No formula > for it is given there. Note however that if phi(n) is not divisible by 3, > the map x -> x^3 is 1-1 and onto on Z_n, so in that case a(n) = n. > > Oops: of course it's not true that x -> x^3 is 1-1 and onto on > Z_n. It's 1-1 and onto on the group G(n) of members of Z_n relatively prime > to n. Nevertheless, I believe it is still true that a(n) = n if phi(n) is > not divisible by 3. Moreover (from numerical evidence) it looks like > a(p^k) = p^(k-1) a(p) for any prime p <> 3 and positive integer k, while > a(3^k) = 3^(k-2) a(9) for k >= 2. > > Robert Israel israel@math.ubc.ca > Department of Mathematics http://www.math.ubc.ca/~israel > University of British Columbia > Vancouver, BC, Canada V6T 1Z2 Sender: Ilya Zakharevich Originator: ilya@powdermilk Approved: Daniel Grayson, dan@math.uiuc.edu, moderator for sci.math.research ==== [A complimentary Cc of this posting was sent to Laurent Demanet > Consider the eigenvalue problem A R = R Lambda, where A is a n-by-n > matrix of operators acting on functions. Forget about functions; simplify the stuff, and assume that entries in A are m x m matrices. > We seek eigenvectors R_i and eigenvalues lambda_i that are > themselves operators. Not clear what you mean. Should R be an n-vector with entries being operators? Then, essentially, you want to solve A R = R Lambda with A being a given nm x nm matrix, R being an unknown nm x m matrix, and lambda being an unknown m x m matrix? Then the problem reduces to finding m-dimensional invariant subspaces of A - which is easy if you know diagonalization (or the Jordan form) of A. [The answer is essentially the same in infinite-dimensional case - you should look for closed invariant subspaces of infinite dimension and codimension.] I know some other interpretations of your question - and they have different answers... Hope this helps, Ilya ==== > Not clear what you mean. Should R be an n-vector with entries being > operators? Then, essentially, you want to solve > > A R = R Lambda > > with A being a given nm x nm matrix, R being an unknown nm x m matrix, > and lambda being an unknown m x m matrix? Then the problem reduces to > finding m-dimensional invariant subspaces of A - which is easy if you > know diagonalization (or the Jordan form) of A. > > [The answer is essentially the same in infinite-dimensional case - you > should look for closed invariant subspaces of infinite dimension and > codimension.] the full diagonalization is a particular instance of an incomplete one. There are plenty of ways to identify any number of infinite-dimensional subspaces from the spectral representation of A. My question was poorly phrased. What I had in mind were examples like the following one : (A f)(x) = (0, d/dx (c(x)*f(x)) ; - c(x)*d/dx (f(x)) , 0), which can be diagonalized as A R_pm = R_pm Lambda_pm with Lambda_pm^2 f = -c d^2/dx^2 (c*f), take the 2 square roots (say |log c| is bounded and smooth), and R_pm f = ( d/dx (c*f) , Lambda_pm f ). I was wondering if this particular construction was part of a broader calculus. I think it's called a one-way wavefield decomposition. > > I know some other interpretations of your question - and they have > different answers... like the above one ? thanks again, - Laurent Approved: Daniel Grayson, dan@math.uiuc.edu, moderator for sci.math.research ==== The following paper has been published: Algebraic and Geometric Topology URL: http://www.maths.warwick.ac.uk/agt/AGTVol3/agt-3-38.abs.html Title: Addendum to Coarse homology theories Author(s): Paul D. Mitchener Abstract: theories [Algebr. Geom. Topol. 1(2001) 271-297]. AMS Classification Numbers. Primary: 55N35, 55N40 Secondary: 19K56, 46L85 Keywords: Coarse geometry, exotic homology, coarse Baum-Connes conjecture, Novikov conjecture Received: 12 September 2002 Author(s) address(es): Institut fuer Mathematik, Universitaet Goettingen D-37083 Goettingen, Germany URL: http://www.uni-math.gwdg.de/mitch/ Approved: Daniel Grayson, dan@math.uiuc.edu, moderator for sci.math.research ==== >Given is a cube in R^K > Q = { x is element of R^K | 0 <= x <= 1 } >and a linear map > A : R^K -> R^2. >The image of the cube A(Q) is a convex polyhedron which can be described by >a system of linear inequalities > A(Q) = { y is element of R^2 | B*y <= C } >with a (m,2)-matrix B and a (m,1)-vector C. >The problem is to find (m,B,C) as a function of the linear map A. Let A_n be the image of {y in Q: y_j = 0 for j > n}. So each A_n is a convex polygon, A_2 being a (possibly degenerate) parallelogram, and A_{n+1} is the convex hull of A_n and its translate by A(e_{n+1}) where e_n is the vector in R^K with 1 in position n and 0 elsewhere. Going from A_n to A_{n+1} is easy: for each segment s of the boundary of A_n where the dot product of A(e_{n+1}) and the outward-pointing normal to s is negative, you take s; for each segment s where the dot product is positive you take s + A(e_{n+1}); and for the two points p where the dot product changes sign you take segments p to p + A(e_{n+1}). (Modify this slightly to take care of the case where a dot product is 0) Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ==== Informal Inductive reasoning seems to imply the image in R^2 has 2k corners (or less). 1) Is this true? 2) Is there a similar formula for R^3? 3) For what more general class of figures than a k-cube does this hold? FIRST name on the list (No.1) along with a note in the NOTE