Timeline for Enumerating ways to decompose an integer into the sum of two squares
Current License: CC BY-SA 2.5
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 12, 2015 at 15:24 | comment | added | KalEl | @user25246 ... it is 13 because you have 3 primes with powers of 2 each, and $\lfloor(2+1)(2+1)(2+1)/2\rfloor=13$. Likewise for $N=5*5*5*13*13$, the count is $\lfloor(3+1)(2+1)/2\rfloor=6$ and so on. Hope that helps. See my detailed answer below. | |
| Dec 8, 2014 at 0:07 | comment | added | Gerry Myerson | @pts, I think for $13^4$ you have to look at $(3+2i)^4$, $(3+2i)^3(3-2i)$, and $(3+2i)^2(3-2i)^2$, which give rise to $120^2+119^2$, $156^2+65^2$, $169^2+0^2$, respectively. But, honestly, why do you not work these out for yourself? | |
| Dec 7, 2014 at 16:54 | comment | added | pts | @GerryMyerson: What about $13^4$? Should it be $(3\pm 2i)(3\pm 2i)(3\pm 2i)(3+2i)$? | |
| Dec 7, 2014 at 5:43 | comment | added | Gerry Myerson | @pts, why not experiment a bit, and see for yourself? $5=2^1+1^1$, $13^2=12^2+5^2=13^2+0^2$, mix 'n' match, see what happens? Or, $(2\pm i)(3\pm2i)(3+2i)$. | |
| Dec 7, 2014 at 0:06 | comment | added | pts | @GerryMyerson: How should the duplicates be eliminated if the exponent of the prime is larger than 1, e.g. for $N = 5\cdot 13^2$? (Also if $N$ is even.) How can the trick of complex multiplication be applied? | |
| Jul 20, 2012 at 22:25 | comment | added | Douglas Zare | The reason the conjugate wasn't used on one term was because there is a symmetry on the whole set by conjugating everything. If it's confusing, write out the whole set without worrying about the conjugation symmetry first, then note that you have solutions which only differ by conjugation or equivalently, switching $a^2$ and $b^2$. There are many choices for how to eliminate the duplicates. For $5*5*x$, you have two choices of sign in $(2\pm i)(2 \pm i)$ and what matters is the count of plus signs. Afterwards, worry about the duplicates from the conjugation symmetry. | |
| Jul 20, 2012 at 21:37 | comment | added | user25246 | I wouldn't mind an elaboration on Gerry's hints. For example, N=5*5*13*13*17*17 is going to have 13 representations. What variants of x +/- yi are we multiplying together to come up with those? In Gerry's example, how come we don't look at (2-i) as a term and end up with 8 representations? | |
| Jul 19, 2010 at 6:25 | vote | accept | MathMonkey | ||
| Jun 28, 2010 at 1:21 | comment | added | Will Jagy | Hi, Gerry. I remembered the Stan Wagon piece with this material, jstor.org/pss/2323912 | |
| Jun 27, 2010 at 23:50 | history | edited | Gerry Myerson | CC BY-SA 2.5 |
expanded a point
|
| Jun 27, 2010 at 14:32 | comment | added | David E Speyer | Yes, all expressoins as a sum of squares occur in this way. This is an immediate consequence of unique factorization in $\mathbb{Z}[i]$. | |
| Jun 27, 2010 at 6:12 | comment | added | Gerry Myerson | I think it will be easier for you to learn by doing than by me explaining (since I'm not so hot at explaining). Take an example, say, $N=5\times13\times17$, and use the expressions $5=2^2+1^2$, $13=3^2+2^2$, $17=4^2+1^2$, and see what you have to do to get all 4 distinct representations. Qiaochu Yuan's remark may help guide you; in effect, we're finding all 4 values of $a+bi=(2+i)(3\pm2i)(4\pm i)$ where $i$ is the square root of minus one, and our representations are $N=a^2+b^2$. Yes, this is guaranteed to get everything, and without duplicates if you set it up right. Try it and see. | |
| Jun 27, 2010 at 2:53 | comment | added | MathMonkey | And finally, is it guaranteed that the above algorithm will actually find ALL of the top level N decompositions? The formula just tells us that given one factoring we get one sum of two squares decompositions, but does that mean that all factorings will give us all decompositions? | |
| Jun 27, 2010 at 2:50 | comment | added | MathMonkey | So what would the algorithm itself be? It sounds like I should enumerate all possible $xy=N$ factorings (both prime and composite). Then for each, decompose $x$ into each possible $a^2+b^2$ and each y into each possible $c^2+d^2$, and use the above formula to find one answer to the top level N decomposition. Finally after iterating over all such factors, and over the two inner loops of all decompositions of those factors, I should take all the answers and sort them and eliminate duplicates. Is this the right algorithm or is it doing unnecessary work? | |
| Jun 26, 2010 at 22:41 | history | answered | Gerry Myerson | CC BY-SA 2.5 |