Problem 1577

21. (a) Representing $n^{2}$ as a sum of $n^{2}-13$ squares is equivalent to representing 13 as a sum of numbers of the form $x^{2}-1, x \in \mathbb{N}$, such as $0,3,8,15, \ldots$ But it is easy to check that this is impossible, and hence $s(n) \leq n^{2}-14$. (b) Let us prove that $s(13)=13^{2}-14=155$. Observe that $$\begin{aligned} 13^{2} & =8^{2}+8^{2}+4^{2}+4^{2}+3^{2} \\ & =8^{2}+8^{2}+4^{2}+4^{2}+2^{2}+2^{2}+1^{2} \\ & =8^{2}+8^{2}+4^{2}+3^{2}+3^{2}+2^{2}+1^{2}+1^{2}+1^{2} \end{aligned}$$ Given any representation of $n^{2}$ as a sum of $m$ squares one of which is even, we can construct a representation as a sum of $m+3$ squares by dividing the odd square into four equal squares. Thus the first equality enables us to construct representations with $5,8,11, \ldots, 155$ squares, the second to construct ones with $7,10,13, \ldots, 154$ squares, and the third with $9,12, \ldots, 153$ squares. It remains only to represent $13^{2}$ as a sum of $k=2,3,4,6$ squares. This can be done as follows: $$\begin{aligned} 13^{2} & =12^{2}+5^{2}=12^{2}+4^{2}+3^{2} \\ & =11^{2}+4^{2}+4^{2}+4^{2}=12^{2}+3^{2}+2^{2}+2^{2}+2^{2}+2^{2} \end{aligned}$$ (c) We shall prove that whenever $s(n)=n^{2}-14$ for some $n \geq 13$, it also holds that $s(2 n)=(2 n)^{2}-14$. This will imply that $s(n)=n^{2}-14$ for any $n=2^{t} \cdot 13$. If $n^{2}=x_{1}^{2}+\cdots+x_{r}^{2}$, then we have $(2 n)^{2}=\left(2 x_{1}\right)^{2}+\cdots+\left(2 x_{r}\right)^{2}$. Replacing $\left(2 x_{i}\right)^{2}$ with $x_{i}^{2}+x_{i}^{2}+x_{i}^{2}+x_{i}^{2}$ as long as it is possible we can obtain representations of $(2 n)^{2}$ consisting of $r, r+3, \ldots, 4 r$ squares. This gives representations of $(2 n)^{2}$ into $k$ squares for any $k \leq 4 n^{2}-62$. Further, we observe that each number $m \geq 14$ can be written as a sum of $k \geq m$ numbers of the form $x^{2}-1, x \in \mathbb{N}$, which is easy to verify. Therefore if $k \leq 4 n^{2}-14$, it follows that $4 n^{2}-k$ is a sum of $k$ numbers of the form $x^{2}-1$ (since $k \geq 4 n^{2}-k \geq 14$ ), and consequently $4 n^{2}$ is a sum of $k$ squares. Remark. One can find exactly the value of $f(n)$ for each $n$ : $$f(n)= \begin{cases}1, & \text { if } n \text { has a prime divisor congruent to } 3 \bmod 4 \\ 2, & \text { if } n \text { is of the form } 5 \cdot 2^{k}, k \text { a positive integer; } \\ n^{2}-14, & \text { otherwise. }\end{cases}$$