9

Wikipedia states that there randomized polynomial-time algorithms for writing $n$ as a sum of four squares

$n=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}$

in expected running time $\mathrm {O} (\log^{2} n).$

My question is can someone give the efficient algorithm( $\mathrm {O} (\log^{2} n)$ ) to represent $n$ as sum of four squares.

nequit
  • 99
  • 6
    Not only does Wikipedia state this, but it gives a precise reference for where you can read about it. – Kevin Buzzard Jan 09 '17 at 10:50
  • 1
    ...although my reading of the paper is that the $O(log^2n)$ method they give assumes ERH, and the other method (which doesn't) runs in time $O(log^2n.loglog(n))$ (so it seems to me that the statement in Wikipedia is slightly inaccurate, unless one argues that the truth of ERH is "expected" :-) ) – Kevin Buzzard Jan 09 '17 at 10:59
  • @KevinBuzzard not available for budget users. –  Jan 09 '17 at 11:22
  • @Kevin Buzzard can you provide the research paper? – nequit Jan 09 '17 at 16:50
  • Probably not legally. It will be copyright the journal. Course I could try and read the paper and summarise, but unfortunately I have other things to do :-( – Kevin Buzzard Jan 09 '17 at 16:53
  • 2
    If you have access to a library, you can see whether they can get it for you by interlibrary loan. – Gerry Myerson Jan 10 '17 at 00:45
  • 2
    Negative attention to this question and its answers may be explained by the fact that potentially this is related to the current CodeChef challenge. Your browser settings permitting you can follow the links here and judge yourself. – Jyrki Lahtonen Jan 10 '17 at 22:10
  • @Jyrki Lahtonen What will you say about this question ? http://mathoverflow.net/questions/17711/lagrange-four-squares-theorem-efficient-algorithm-with-units-modulo-a-prime?rq=1 – nequit Jan 11 '17 at 05:53
  • 1
    Nothing, nequit. I came here because some helpful users at another related Math.SE question (trackable to that on-going competition) referred the asker here. Not accusing you of anything. It is just that the timing was a bit unfortunate. I apologize for implying anything else. – Jyrki Lahtonen Jan 11 '17 at 07:45
  • 1
    See also http://cs.stackexchange.com/q/68501/755, http://stackoverflow.com/q/41524508/781723, http://mathoverflow.net/q/259152/37212, http://math.stackexchange.com/q/366673/14578, http://math.stackexchange.com/q/483101/14578, http://mathoverflow.net/q/110239/37212. – D.W. Jan 20 '17 at 05:44

3 Answers3

3

One of their methods for $n=4k+2$ is as follows:

Randomly select an even number $a$ and an odd number $b$ such that $a^2+b^2 < n$. Then, we hope $p=n-a^2-b^2$ is a prime (you can show there's about a $1/(A \log n \log \log n)$ chance of $p$ being prime ); $p$ is of the form $4r+1$, so if $p$ is prime there's a solution to $c^2+d^2=p$.

To find that, we try to solve $m^2+1 \equiv 0 \pmod{p}$; I'm actually going to describe a slightly different method. Select $x$ at random from $1$ to $p-1$; then, $x^{2r}=\pm 1$ depending on whether $x$ is a quadratic residue so calculate $x^r$ by repeated squaring, and with a $1/2$ chance if $p$ is prime (a smaller one if $p$ is composite) you'll find a valid $m$.

Given such an $m$, $m+i$ is a Gaussian integer with norm divisible by $p$ but smaller than $p^2$; use the Euclidean algorithm on the Gaussian integers with $p$ and get $c+di$ with norm $p$, and $a^2+b^2+c^2+d^2=n$.

For an odd number $n$, solve for $a^2+b^2+c^2+d^2=2n$; note that by mod $4$ considerations exactly two of $a,b,c,d$ must be odd, and without loss of generality assume $a,b$ are odd and $c,d$ are even. Then,$(\frac{1}{2}(a+b))^2+(\frac{1}{2}(a-b))^2+(\frac{1}{2}(c+d))^2+(\frac{1}{2}(c-d))^2=n.$

For $n$ a multiple of $4$, solve for $n/4$ recursively, and multiply all values by $4$.

W. Cadegan-Schlieper
  • 397
0

This seems to be addressed in this paper by Bumby.

Igor Rivin
  • 95,560
0

I am going to provide you with 4 links and I hope it will help you.

this one is an online calculator based on an algorithm from math overflow.

http://www.mathcelebrity.com/foursquare.php?num=+178&pl=Show+Lagrange+Four-Square+Notation

the math overflow algorithm can be found here.

https://stackoverflow.com/questions/11732555/how-to-find-all-possible-values-of-four-variables-when-squared-sum-to-n

and then there is also this algorithm from cs stackexchange

https://cs.stackexchange.com/questions/2988/how-fast-can-we-find-all-four-square-combinations-that-sum-to-n

and if you want to do a bit of work, then there is this algorithm that can find the sum of 2 squares for a given integer. So you would have to divide your number in two ( not necessarily equal part ) and then add up the results to get a 4 square representation.

https://math.stackexchange.com/questions/1972771/is-this-the-general-solution-of-finding-the-two-original-squares-that-add-up-to/1977767?noredirect=1#comment4062390_1977767

Community
  • 1
user25406
  • 113
  • 2
    Why all the negative votes I wonder, for what look like more than adequate posts? Also, in view of Euler's quaternion norm product identity, doesn't finding multiple essentially distinct four square representations of an integer allow non-trivial factorizations of it? If so then finding four square forms can't be that easy or else factoring would be also! (Or maybe this readily works only for two square forms?) – John R Ramsden Jan 10 '17 at 10:42
  • This answer also appears at http://cs.stackexchange.com/a/68536/755. – D.W. Jan 20 '17 at 05:41
  • @JohnRRamsden I don't see how this answer addresses the issues of runtime which were explicitly mentioned in the original questoin – Yemon Choi Jan 23 '17 at 03:17
  • 2
    @YemonChoi, good point. you could maybe tackle the question yourself and derive an algorithm that is efficient to answer the original question or review the different algorithms known to produce a 4-square representation of an integer and show us which one is the most efficient. we will all be grateful to you. – user25406 Jan 23 '17 at 15:04