From: CDP@cipcinsa.insa-lyon.fr (Comite de Parrainage) Newsgroups: sci.math Subject: What is the best method to decompose an integer into threee squares of integer ? Date: Mon, 6 Feb 1995 19:27:01 GMT I would like to know the best way to decompose an integer into three squares of integers . For example 11=3^2+1^2+1^2, but it is impossible for seven, fifteen.... Please answer quickly, i'll need this method very soon. Thank you. ============================================================================== From: robert@cs.caltech.edu (Robert J. Harley) Newsgroups: sci.math Subject: Re: What is the best method to decompose an integer into threee squares of integer ? Date: 8 Feb 1995 01:09:48 GMT CDP@cipcinsa.insa-lyon.fr (Comite de Parrainage) writes: >I would like to know the best way to decompose an integer into three >squares of integers. [...] I don't know about the best way, but here is a good way for large integers. Let n be a non-negative integer that we want to express as a sum of three squares. We can assume n != 0 (mod 4) since when: n = x^2 + y^2 + z^2, then: n*4^t = (x*2^t)^2 + (y*2^t)^2 + (z*2^t)^2 for all integers t >= 0. When n = 7 (mod 8) it cannot be represented as a sum of three squares. Otherwise it can be and it suffices to represent it by a positive definite ternary quadratic form of discriminant 1 since that is (properly) equivalent to a sum of three squares. Emil Grosswald describes how to find the matrix of such a form in Chapter 4 of "Representation of Integers as Sums of Squares". Here is a paraphrase: When n = 2 or 6 (mod 8), let a_22 be a prime in the arithmetic progression 4*n*m+n-1. When n = 1, 3 or 5 (mod 8), let c = 1 if n = 3 (mod 8) or c = 3 otherwise and let a_22 be twice a prime in the progression 4*n*m+(c*n-1)/2. Now let a_12 be a square root of -(1+a_22)/n modulo a_22 (this exists!) and let a_11 be (a_12^2+(1+a_22)/n)/a_22. The desired m'x is: [ a_11 a_12 1 ] [ a_12 a_22 0 ] [ 1 0 n ] By construction, it has determinant 1. Furthermore n is clearly represented when x_1 = x_2 = 0, x_3 = 1. If you need code to compute representations email me and I'll write some! Salut, Rob .-. robert@vlsi.cs.caltech.edu .-. / \ .-. .-. / \ / \ / \ .-. _ .-. / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / `-' `-' \ / \ / \ \ / `-' `-' \ / `-' Question all you are. `-' ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: sum of three squares. Date: 30 Oct 1995 21:38:27 GMT In article <4714ji$542@mirv.unsw.edu.au>, wrote: > A colleague is doing some programming to produce 'nice' matrices to >use as exam and test questions. He asked me the following question. > Can every square integer be expressed as the sum of at least 3 squares >in a non-trivial way. ie either as the sum of two non-zero squares or >as the sum of three non-zero squares. Yes, assuming you mean "at most 3", as in 7^2=6^2+3^2+2^2. Heh, heh. Watch this. We begin with a theorem of Gauss: a natural number n can be expressed as a sum of three integral squares iff n is not of the form 4^t(8s-1). One proof involves taking square roots of quaternions(!), so I'd like to show the connection with that other thread. We observe that such a decomposition exists iff the number field K=Q(sqrt(-n)) embeds into the division algebra A of rational quaternions, that is, iff we may calculate a rational quaternionic square root of -n . Indeed, if n=a^2+b^2+c^2, then n = x*xbar, where x=ai+bj+ck and "bar" is the usual quaternionic conjugate, so that xbar=-x and x^2=-n. So the rational span of 1 and x is the field in question. Conversely, if K embeds in A, then its ring of integers is contained in a maximal order in A. This is a little tricky, but you can show the Euclidean algorithm works, not for the order S=Z+Zi+Zj+Zk but rather for the larger order T=S+Zw where w=(1+i+j+k)/2 -- T is really the appropriate "ring of integers" for the rational quaternions. From the Euclidean algorithm one may show that all maximal orders are of the form aTa^(-1) where a is in A. So, conjugating by a^(-1), we see that if K embeds in A, then there is also an embedding which carries the ring of integers into T. In particular, there is an element x of T with x^2=-n. Well, this x's minimal polynomial is X^2+n=0, so its trace is zero, meaning x=ai+bj+ck for some rational a, b, c; they're even half-integers since x lies in T. But the intersection of T with the span of i, j, and k is just S, so really a, b, and c are integers. Then of course we compute a^n+b^2+c^2=n. The rest of the proof of Gauss's theorem uses the Hasse-Minkowski theorem to decide whether Q(sqrt(-n)) does indeed embed in A. The conclusion is that n _cannot_ be written as a sum of three squares iff n=n1^2*n2 with n2 squarefree and n2=7 mod 8. Splitting n1 into its even and odd factors gives Gauss's result. Still with me? OK, the point I need from this proof for our application is that different representations of n as a sum of three squares come from conjugate embeddings of Q(sqrt(-n)) in A. Of course, if you want integral representations, you need to choose conjugates which keep axa^(-1) = (a*x*abar)/(a*abar) within the maximal order. This is tricky to keep track of, in general, but the poster's question makes it easy. If n=m^2 for some integer m, then one representation of n as a sum of three squares is trivial: take x=mi+0j+0k. Then just choose any a which has a norm a*abar dividing m. We know for example that there are integral quaternions with a*abar=m by the four-square theorem: every integer m is the sum of four squares. In this case the conjugate is then just a*i*abar, which is integral. (Of course, if m is composite, there are other conjugates we may take as well). So for example we consider m=7, that is, we ask how to write 49 as a sum of squares in a different way. Noting that 7=2^2+1^2+1^2+1^2, we compute (2+i+j+k)*i*(2-i-j-k)=3i+6j-2k (I hope I did that right). Thus 3^2+2^2+6^2=49. There's enough information on sums of squares to fill a book; in fact, Emil Grosswald has written a book, "Representation of Integers as Sums of Squares", so I will forbear detailing the many questions one may naturally ask about this material, many of which have elegant answers. Oh, OK, just one nugget. In how many ways may one represent a given integer n as a sum of three squares? Eichler noted that for n squarefree, the number of ways is, as noted above, zero if n=7 mod 8. If n=3 mod 8, he showed the number of representations is 12h, where h is the class number of the field Q(sqrt(-n)). Otherwise, the number of representations is 24h. (The proof above indicates the connection.) dave ============================================================================== [The following alternate version was not posted. It is longer.] ============================================================================== Newsgroups: sci.math Subject: Re: sum of three squares. Summary: Expires: References: <4714ji$542@mirv.unsw.edu.au> Sender: Followup-To: Distribution: world Organization: Northern Illinois University, Math Keywords: Cc: In article <4714ji$542@mirv.unsw.edu.au>, wrote: > A colleague is doing some programming to produce 'nice' matrices to >use as exam and test questions. He asked me the following question. > Can every square integer be expressed as the sum of at least 3 squares >in a non-trivial way. ie either as the sum of two non-zero squares or >as the sum of three non-zero squares. Yes, assuming you mean "at most 3", as in 7^2=6^2+3^2+2^2. Heh, heh. Watch this. We begin with a theorem of Gauss: a natural number n can be expressed as a sum of three integral squares iff n is not of the form 4^t(8s-1). The proof involves taking square roots of quaternions(!); it's really only that rather less-technical aspect of the proof I need, but here's a sketch of the whole proof. Step one is to observe that such a decomposition exists iff the number field K=Q(sqrt(-n)) embeds into the division algebra A of rational quaternions. Indeed, if n=a^2+b^2+c^2, then n = x*xbar, where x=ai+bj+ck and "bar" is the usual quaternionic conjugate, so that xbar=-x and x^2=-n. So the rational span of 1 and x is the field in question. Conversely, if K embeds in A, then its ring of integers is contained in a maximal order in A. This is a little tricky, but you can show the Euclidean algorithm works, not for the order S=Z+Zi+Zj+Zk but rather for the larger order T=S+Zw where w=(1+i+j+k)/2 -- T is really the appropriate "ring of integers" for the rational quaternions. From the Euclidean algorithm one may show that all maximal orders are of the form aTa^(-1) where a is in A. So, conjugating by a^(-1), we see that if K embeds in A, then there is also an embedding which carries the ring of integers into T. In particular, there is an element x of T with x^2=-n. Well, this x's minimal polynomial is X^2+n=0, so its trace is zero, meaning x=ai+bj+ck for some rational a, b, c; they're even half-integers since x lies in T. But the intersection of T with the span of i, j, and k is just S, so really a, b, and c are integers. Then of course we compute a^n+b^2+c^2=n. OK, so step 2 is to decide for which natural numbers n we have a subfield K isomorphic to Q(sqrt(-n)) inside A. Here you need to know a little about division algebras over fields, so I'll have to gloss over details. Since [A:Q]=[K:Q]^2, K is a splitting field for A: A\tensor K will be the ring of 2x2 matrices over K. The Hasse-Minkowski principle applies here, meaning that this splitting occurs iff it occurs locally (at each prime p). At almost every prime the splitting is automatic; only p=2 can prohibit the splitting. But if n = n1^2*n2 with n2 squarefree, then Q(sqrt(-n))=Q(sqrt(-n2)). If n2=1 or 2 mod 4, then (2) ramifies and A splits. If n2=3 mod 4, then Q(sqrt(-n2))=Q((1+sqrt(-n2))/2); we find that (2) factors into two primes and so A splits, if n2=3 mod 8, but (2) remains prime and so A does not split, if n2=7 mod 8. Combining steps one and two, we see n cannot be written as a sum of three squares iff n=n1^2*n2 with n2 squarefree and n2=7 mod 8. Splitting n1 into its even and odd factors gives Gauss's result. Still with me? OK, the point I need from this proof for our application is that the representations of n as a sum of three squares are in one-to-one correspondence with the embeddings of Q(sqrt(-n)) in A, and that these are in turn all conjugate in A: given any two representations n=x*xbar=y*ybar I can find an a in A such that axa^(-1) = y (well, maybe you can only get -y instead of y). Conversely, such a conjugate automatically has (axa^(-1))^2=a(x^2)a^(-1) = -n, although it's not automatic that this conjugate will be integral. On the other hand, I note axa^(-1) = (a*x*abar)/(a*abar), so if we use only _integral_ quaternions a (which is in general sufficient) then the resulting conjugate is also integral if the natural number a*abar divides the coefficients of i,j, and k in a*x*abar. Of course, this is tricky to keep track of, in general, but the poster's question makes it easy. If n=m^2 for some integer m, then one representation of n as a sum of three squares is trivial: take x=mi+0j+0k. Then we can get other conjugates, but we need to arrange it so the denominators clear. Well, fine: just choose any a which has a norm a*abar dividing m. Then the conjugate is a*((m/(a*abar))i + 0 j + 0 k) * abar, which is integral. Oh, yes, one more thing: how do we know there _are_ integral quaternions with a*abar=m? Simple -- that's the four-square theorem: every integer m is the sum of four squares, i.e., m=a*abar for some m. So for example we consider m=7, that is, we ask how to write 49 as a sum of squares in a different way. Noting that 7=2^2+1^2+1^2+1^2, we conjugate the one solution x=7i+0j+0k by a=(2+i+j+k) to get (-3)i+2j+(-6)k. Thus 3^2+2^2+6^2=49. There's enough information on sums of squares to fill a book; in fact, Emil Grosswald has written a book, "Representation of Integers as Sums of Squares", so I will forbear detailing the many questions one may naturally ask about this material, many of which have elegant answers. Oh, OK, just one nugget. In how many ways may one represent a given integer n as a sum of three squares? Eichler noted that for n squarefree, the number of ways is, as noted above, zero is n=7 mod 8. If n=3 mod 8, he showed the number of representations is 12h, where h is the class number of the field Q(sqrt(-n)). Otherwise, the number of representations is 24h. dave There are several other natural questions to ask. The number of representations of an integer n as a sum of two squares was treated by Gauss in Disq. Arith. section 182. It must be true that n=2^r Prod p_i^(2e_i) Prod q_i^f_i where the p_i are distinct primes with p_i=1 mod 4 and the q_i are the distinct primes q_i=3 mod 4. Then n has ceiling((Prod(f_i + 1))/2) representations as a sum of two squares. The number of representations of a number m as a sum of three squares is treated above. The number of representations of a number m as a sum of four squares is 8 times the sum of the divisors of m which are themselves not multiples of 4, e.g., when m=12 there ought to be 8(1+2+3+6)=96 representations, and indeed there are, when you count the permutations and sign changes of the basic solutions (3, 1, 1, 1) and (4, 4, 4, 0). A reasonably accessible proof of this comes from studying products of four theta functions Sum(exp(pi*i*(a*n^2+b*n+c)), n=-oo,..., oo). The number of integers up to N which are squares is of course roughly sqrt(N). The number of integers up to N which are sums of two squares is roughly K* N/sqrt(log(N)), a result proved by Landau (1908) and noted by Ramanujan. The best estimate I know of for K is 0.76422365... (Shiu, 1986). The number of integers up to N which are sums of three squares is roughly 5N/6. Here it's the error term which is quite interesting (Osbaldestin and Shiu, 1989) All integers are sums of four squares. Algorithms for representating integers as sums of squares are much desired. Rabin and Shallit (1986) showed how to represent any positive integer n as a sum of four squares in random polynomial time. Bumby (1990?) gave a deterministic, polynomial-time algorithm in the case n is prime. Determining the number of such representations for composite n is random polynomial-time equivalent to factoring n. I also have some now-useless notes scribbled here which I will toss out for what they might be worth. Gauss considered the representations by three squares in Diss. Arith. V and found the number of representations in terms of two other functions of n which, stupidly, I did not record. Uspensky (1929) considered representations by more general ternary quadratic forms. Borevich and Shafarevich's book on number theory gives significant space to such representations.