Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Are you aware of the three-square and two-square theorems? –  Yuval Filmus Jan 25 '12 at 14:27
    
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. –  Zach Langley Jan 25 '12 at 14:41
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. –  emiliocba Jan 25 '12 at 14:59
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. –  emiliocba Jan 25 '12 at 15:02
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 mathoverflow.net/questions/57981/… and mathoverflow.net/questions/3820/… –  David Speyer Jan 25 '12 at 15:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.