I am aware of Lagrange's Four-Square Theorem, which states that every positive integer can be written as the sum of at most four squares. Clearly some integers require fewer squares. Does there exist a polynomial-time algorithm to compute the minimum number of squares needed to sum to a given integer $n$?

It is easy to come up with a dynamic program for this problem; denote the number of squares needed to represent $i$ by $T[i]$, then

\begin{align*} T[i] = \min_{1 \le s \le \sqrt{i}} T[i - s^2] + 1 \end{align*}

Thus, we can solve this problem in $\Theta(n\sqrt{n})$, but this is not polynomial in $\log(n)$.

  • 1
    $\begingroup$ Are you aware of the three-square and two-square theorems? $\endgroup$ – Yuval Filmus Jan 25 '12 at 14:27
  • $\begingroup$ I know that a prime $p$ is a sum of squares iff $p \equiv 1 \pmod{4}$, but I don't immediately see how it helps to determine if a composite integer is a sum of squares. Moreover, I do not know of any results that state whether or not something is a sum of three squares. These reasons together are why I'm asking the question. $\endgroup$ – Zach Langley Jan 25 '12 at 14:41
  • 2
    $\begingroup$ Zach, a non-negative integer $m$ is the sum of 3 squares iff it is not of the form $4^a(8k+7)$. This was proved by Legendre. $\endgroup$ – emiliocba Jan 25 '12 at 14:59
  • 2
    $\begingroup$ a non-negative integer $m$ is the sum of $2$ squares iff the exponent of a prime divisor $p$ of $m$ with $p\equiv3\pmod4$ is even. $\endgroup$ – emiliocba Jan 25 '12 at 15:02
  • 3
    $\begingroup$ The integer $n$ is a sum of two squares iff, for every prime $q$ which is $3 \mod 4$, the number of times that $q$ divides $n$ is even. It seems to be hard to turn this into a computationally effective criterion. We kicked this around at MO and couldn't find anything better than factoring $n$; see mathoverflow.net/questions/57981/… and mathoverflow.net/questions/3820/… $\endgroup$ – David E Speyer Jan 25 '12 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.