What are the number of ordered m-tuples of integers,such that sum of square of elements is a given integer?

Question

Given a non-zero integer $n$,the problem is to find a m-tuple of integers,$(x_1,x_2,x_3,...,x_m)$such that the following equation is satisfied---$$\sum_{i=1}^mx_i^2=n$$ I have no idea how to approach the problem,neither can I find exactly a solution to this,but I hope maybe counting and a bit of number theory can help.Is there any analytic solution at all?

Answer 1

Claim: We can always find such an ($m$-tuple) for $m\geq4$

Proof: We will prove that ANY number can be written as the sum of 4 squares. Suppose M is the set of numbers which can be written in this form. We will prove that if $a\in M$ and $b\in M$ then $ab \in M$.

It is easy to see that $(x^2+y^2+z^2+t^2)(a^2+b^2+c^2+d^2)=(ax+by+cz-dt)^2+(ct+dz+ay-bx)^2+(cx+dy+az-bt)^2+(at+bz+dx-cy)^2$, so done.

Using the above observation, if we prove any prime can be written as a sum of 4 squares, we are done.

$-1$ is a quadratic residue $\pmod{p}$ if $p$ is $\equiv 1\pmod{4}$ so choose an $a$ such that $a^2\equiv-1\pmod{p}$. From Thue's lemma, we know there exist $x,y$ such that $x\equiv ay\pmod{p}$ so $x^2\equiv (ay)^2\equiv -y^2\pmod{p}$ so $x^2+y^2$ is divisible by $p$ (and $<2p$) ao it is $p$.

Thus, any prime $\equiv 1\pmod{4}$ is written as a sum of 2 squares (so 4 too, the 2 others being 0) so any number of the form $4k+1$ can be written as a sum of 2 squares (i won't prove this as it is obvious from the previous observation) so also prime of the form $4k+3$ can be written too as a sum of 4 squares ($4k+1+1^2+1^2=x^2+y^2+1^2+1^2$).

So any number can be written as a sum of 4 squares. Thus for $m\geq4$ just take 4 squares accordingly and then the others 0. So we win!

(Important! For $m\leq3$ We will not always be able to do so. Take $n=7$ and try to write it as a sum of 3 squares or less.)

Answer 2

Given $$\sum_{i=1}^m x_i^2=n$$

We can use Euclid's formula for generating Pythagorean triples $$A=x^2-y^2\qquad B=2xy\qquad C=x^2+y^2$$

We can find a case for $m=2$ easily if we solve the $C$-function for $(y)$ and test a defined range of $m$-values to see which yield integers. For example

$$C=x^2+y^2\implies y=\sqrt{C-x^2}\qquad\text{where}\qquad \bigg\lfloor\frac{ 1+\sqrt{2C-1}}{2}\bigg\rfloor \le x \le \lfloor\sqrt{C-1}\rfloor$$ The lower limit ensures $x>y$ and the upper limit ensures $y\in\mathbb{N}$.

$$C=85\Rightarrow \bigg\lfloor\frac{ 1+\sqrt{170-1}}{2}\bigg\rfloor=6 \le x \le \lfloor\sqrt{85-1}\rfloor=9\quad\land \quad x\in\{7,9\}\Rightarrow y\in\{6,2\}$$

$$f(7,6)=(13,84,85)\quad f(9,2)=(77,36,85)$$

Side $C$ always takes the form $(C=4n+1)$ and we see that side $A$ of $F(7,6)=13=4(3)+1$ so we can try the process again. (Note: not all values of $4n+1$ are valid.) $$C=13\implies \bigg\lfloor\frac{ 1+\sqrt{26-1}}{2}\bigg\rfloor=3 \le x \le \lfloor\sqrt{13-1}\rfloor=3\quad\text{ and we find} \quad x\in\{3\}\Rightarrow y\in\{2\}$$ $$f(3,2)=(5,12,13)\quad \text{and repeating the process for } A=5\quad f(2,1)=(3,4,5)$$ So we get a $4$-dimensional m-tupple where $3^2+4^2+12^2+84^2=85^2=7225$

There are an infinite number of these where $2\le m \le\infty$. It is easier to build them by finding a side $A$ to match a given side $C$ and, we can always find such since all odd numbers greater than $1$ are valid $A$-values.

$$A=x^2-y^2\implies y=\sqrt{x^2-A}\qquad\text{where}\qquad \sqrt{A+1} \le x \le \frac{A+1}{2}$$ The lower limit ensures $y\in\mathbb{N}$ and the upper limit ensures $x> y$. $$A=15\implies \sqrt{15+1}=4\le x \le \frac{15+1}{2} =8\quad\text{ and we find} \quad x\in\{4,8\}\implies y \in\{1,7\} $$ $$fF4,1)=(15,8,17)\qquad \qquad f(8,7)=(15,112,113)$$

The example repeated yields $f(9,8)=(17,144,145)$ or $f(57,56)=(113,6384,6385)$ and this process will always work and for an unlimited number of iterations.