# Legendre's three-square theorem and squared norm of integer matrices

Let $$\mathbb{N}$$ be the set of non-negative integers. Let $$E_n$$ be the set of integers which are the sum of $$n$$ squares. Let $$F_n$$ be the set of integers of the form $$\Vert A \Vert^2$$ with $$A \in M_n(\mathbb{N})$$ and $$\Vert A \Vert$$ the operator norm. Recall that $$\Vert A \Vert^2$$ is the largest eigenvalue of $$A^*A$$.

If $$A = uv^*$$ with $$u,v \in \mathbb{N}^n$$ then $$A^*A = v u^*uv^*$$, so that $$\Vert A \Vert^2 = \Vert u \Vert^2\Vert v \Vert^2$$ and $$E_nE_n \subseteq F_n$$.

This answer and Lagrange's four square theorem imply that $$E_n = F_n$$ $$\forall n \neq 3$$, whereas $$E_3 \subsetneq F_3$$ because, by Legendre's three-square theorem, $$E_3 = \mathbb{N} \setminus \{ 4^a(8b+7) \ | \ a,b \in \mathbb{N} \} \subsetneq E_3E_3$$.

The investigation below shows that $$F_3$$ contains every non-negative integer less than $$3 \cdot 10^6$$.

Question: Does the form $$\Vert A \Vert^2$$ cover every non-negative integer for $$A \in M_3(\mathbb{N})$$?

Remark: It is proved here for $$A \in M_3(\mathbb{Z})$$.

Investigation

Observe that $$L:= \mathbb{N} \setminus E_3E_3$$ is the set of positive integers $$8a-1$$ whose prime factors are of the form $$8b \pm 1$$. The first elements of $$L$$ are $$7, 23, 31, 47, 71, 79, 103, 119, 127, 151, 167, \dots$$

Take $$A=(u_1,u_2,u_3)$$ with $$u_i \in \mathbb{N}^3$$. Then the characteristic polynomial of $$A^*A$$ is $$P(x) = x^3-\left(\sum_{i=1}^3 \Vert u_i \Vert^2 \right)x^2 + \left( \sum_{i with $$u \times v$$ the cross product and $$u \cdot v$$ the dot product.

Assume that the vectors $$u_1, u_2, u_3$$ are linearly dependent. Then

$$\Vert A \Vert^2 = \frac{1}{2} \left( \sum_{i=1}^3 \Vert u_i \Vert^2 + \sqrt{\left( \sum_{i=1}^3 \Vert u_i \Vert^2 \right)^2 -4 \sum_{i

Assume moreover that $$u_3=0$$, and then observe that $$\Vert A \Vert^2 = \frac{1}{2} \left( \Vert u_1 \Vert^2 + \Vert u_2 \Vert^2 + \sqrt{\left( \Vert u_1 \Vert^2 - \Vert u_2 \Vert^2 \right)^2 + 4 (u_1 \cdot u_2)^2} \right).$$ If moreover $$\Vert u_1 \Vert = \Vert u_2 \Vert$$ then $$\Vert A \Vert^2 = \Vert u_1 \Vert^2 + (u_1 \cdot u_2) = \frac{1}{2} \Vert u_1+u_2 \Vert^2$$, and we know by this post that this form covers every odd less than $$90000$$, except those in $$\{ 5, 23, 29, 65, 167 \}$$, but its intersection with $$L$$ is just $$\{23,167\}$$ whereas
$$23 = \left\| \pmatrix{0&2&0\\ 1&4&0 \\ 2&1&0} \right\|^2 \ \text{ and } \ 167 = \left\| \pmatrix{0&7&0\\ 2&5&0 \\ 8&7&0} \right\|^2.$$ It follows that every non-negative integer less than $$90000$$ is covered.

If $$u_1=(a,b,c)$$, $$u_2 = (b,c,a)$$ and $$u_3=0$$, then $$2\Vert A \Vert^2 = (a+b)^2+(b+c)^2+(c+a)^2$$.
Observe (after this comment) that we are reduced to show that $$\forall n > 90000$$, if $$n \in L$$ then $$2n$$ is of the form $$x^2+y^2+z^2$$ (which is true by Legendre's three-square theorem) with the stronger assumption that $$x,y,z$$ are the integer sides of a triangle (i.e. $$x \le y \le z \le x+y$$). It is checked below for $$2543. Then every non-negative integer less than $$3 \cdot 10^6$$ is covered.

Remark: This stronger version of Legendre's three-square theorem is suspected to be true for every $$2n$$ with $$n$$ odd greater than $$5969$$ (see this post), and in general every large element of $$E_3$$.

Computation

sage: ModelOutEE(1,3000000)
[23, 167, 239, 479, 623, 1031, 1439, 1751, 2543]


Code

cpdef StrongLegendre(int i):
cdef int n,a,b,c,j
n=isqrt(i)
for a in range(n+1):
for b in range(a+1):
j=i-a**2-b**2
if j>=0:
c=isqrt(j)
if c**2==j:
if c<=a and a<=b+c:
return True
if c>a and c<=a+b:
return True
return False

cpdef is_EE(int i):
cdef int a,l
cdef list f
cdef tuple j
if not Integer(i).mod(8)==7:
return True
b=0
f=list(factor(i))
for j in f:
a=j[0]
if not Integer(a).mod(8) in [1,7]:
return True
return False

cpdef ModelOutEE(int r1, int r2):
cdef int i
cdef list L
L=[]
for i in range(r1,r2):
if not is_EE(i):
if not StrongLegendre(2*i):
L.append(i)
return L

• Note that the notation $\mathbb{N}$ is a bit ambiguous. To some it includes $0$, and to others (especially number theorists) it doesn't. It's clear once you get to examples that you intend $0 \in \mathbb{N}$, but it's not so clear earlier. – Jeremy Rouse Nov 1 '18 at 0:45
• @JeremyRouse: yes I assumed $0 \in \mathbb{N}$. Thanks for your comment! I just added this clarification. – Sebastien Palcoux Nov 1 '18 at 8:09
• I guess, judging by his name, that Sébastien is French. What we call "les entiers naturels" is the set of non negative integers. – Sylvain JULIEN Nov 1 '18 at 21:14
• @SylvainJULIEN Are there any other countries where $0$ is a natural number? – Alexey Ustinov Nov 2 '18 at 5:15
• I don't know. Maybe in India, since Indians invented the "sunya" concept ? – Sylvain JULIEN Nov 2 '18 at 7:09