9
$\begingroup$

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.

$\endgroup$
10
  • 6
    $\begingroup$ Not only does Wikipedia state this, but it gives a precise reference for where you can read about it. $\endgroup$ Jan 9, 2017 at 10:50
  • 1
    $\begingroup$ ...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" :-) ) $\endgroup$ Jan 9, 2017 at 10:59
  • 2
    $\begingroup$ If you have access to a library, you can see whether they can get it for you by interlibrary loan. $\endgroup$ Jan 10, 2017 at 0:45
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 10, 2017 at 22:10
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 11, 2017 at 7:45

3 Answers 3

3
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

This seems to be addressed in this paper by Bumby.

$\endgroup$
4
  • 1
    $\begingroup$ Is he related to Grothendieck's ex-wife? $\endgroup$ May 26, 2017 at 17:20
  • 1
    $\begingroup$ That seems to rely on factorization, which I would not call efficient. $\endgroup$ May 26, 2017 at 22:47
  • 1
    $\begingroup$ @SylvainJULIEN By marriage, yes. $\endgroup$
    – Igor Rivin
    May 26, 2017 at 23:29
  • $\begingroup$ Why the downvote? $\endgroup$
    – Igor Rivin
    May 26, 2017 at 23:29
0
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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?) $\endgroup$ Jan 10, 2017 at 10:42
  • $\begingroup$ This answer also appears at cs.stackexchange.com/a/68536/755. $\endgroup$
    – D.W.
    Jan 20, 2017 at 5:41
  • $\begingroup$ @JohnRRamsden I don't see how this answer addresses the issues of runtime which were explicitly mentioned in the original questoin $\endgroup$
    – Yemon Choi
    Jan 23, 2017 at 3:17
  • 2
    $\begingroup$ @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. $\endgroup$
    – user25406
    Jan 23, 2017 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.