2
$\begingroup$

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
    Are you aware of the three-square and two-square theorems?2012-01-25
  • 0
    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.2012-01-25
  • 2
    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.2012-01-25
  • 2
    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.2012-01-25
  • 3
    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 http://mathoverflow.net/questions/57981/testing-whether-an-integer-is-the-sum-of-two-squares and http://mathoverflow.net/questions/3820/how-hard-is-it-to-compute-the-number-of-prime-factors-of-a-given-integer/10062#100622012-01-25
  • 0
    This [question](http://mathoverflow.net/questions/63032/is-there-another-simple-formula-for-the-sum-of-squares-function) is related.2012-01-25
  • 0
    So the difficult part is differentiating between numbers that require two squares and numbers that require three. Thanks for the feedback!2012-01-27

0 Answers 0