18
$\begingroup$

Lagrange's four-squares theorem states that every natural number can be represented as the sum of four integer squares. Rabin and Shallit gave a randomised algorithm that finds one of these solutions in quadratic time. My question is if anything is known about the deterministic time complexity of finding one of the solutions? Any pointers would be appreciated.

(It seems that enumerating all the solutions is hard as factoring in certain cases (via Jacobi's four-square theorem), but correct me if I am wrong.)

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Your parenthetical remark is essentially correct. For instance, this is at least as difficult as factoring semiprimes, because it lets us compute $1+p+q+pq$ given a semiprime $pq$, and from $p+q,pq$ it's easy to compute $p,q$. $\endgroup$
    – Wojowu
    Commented Apr 19, 2019 at 13:51

1 Answer 1

Reset to default
19
$\begingroup$

As far as I know, this is still an open problem. This is discussed in Section $5$ of the paper Finding the four squares in Lagrange's theorem by Pollack and Treviño. They mention that there is a deterministic polynomial-time algorithm when $n$ is a prime via quaterion multiplication, due to Bumby. Assuming a conjecture of Heath-Brown, there is a deterministic polynomial-time algorithm that works for all $n$. Finally, they mention that a positive proportion of all numbers can be written as the sum of four squares in deterministic polynomial time. Under the Extended Riemann Hypothesis, almost all numbers can be written as the sum of four squares in deterministic polynomial time.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .