# Can every element of a finite field be written as a sum of two non-squares?

We know that any element of a finite field $\mathbb{F_{q}}$ ($q$ odd prime power) can be written as a sum of two squares - is the same true for non-squares? Can any element of a (sufficiently large) finite field be written as a sum of two non-squares?

I know that the above is not true in general, e.g. in $\mathbb{F_{3}}$, the only non-square is $2$ and so $2$ itself cannot be written as a sum of two non-squares. However, if $q$ is large enough could the above be true?

If it is true, then could anyone provide any hints on I could prove it?

Many thanks!

• The problem is obviously true for every field where each element is the sum of two non-zero squares, but it is not clear to me if this is the case for large $q$. – N. S. Mar 9 '16 at 18:55
• @Dietrich Does $T=T_{b}$ in your comment? and is $b$ an arbitrary element of the field? – Ishika Mar 9 '16 at 19:01
• @Dietrich I can see that every non-zero square can be written an a product of two non-squares, but I can't see how to compute $|S\cap T_{b}|$, for $b$ a non-square. – Ishika Mar 9 '16 at 19:07
• @DietrichBurde, I just did a few by hand. The key point is that $0$ is regarded as a square and we cannot use it as a non-square. For prime $q \equiv 3 \pmod 4,$ it is impossible to represent $0,$ but up to $p \leq 11$ everything else works. For prime $p \equiv 1 \pmod 4,$ for $p=5$ we miss $2,3,$ for $p=13$ we miss $6,$ but for $p=17$ we get everything. – Will Jagy Mar 9 '16 at 19:15
• @WillJagy Right, I see the problem. One could ask to leave out $0$. – Dietrich Burde Mar 9 '16 at 19:18

## 2 Answers

Leading off with the following.

If $g$ is a primitive element of a finite field then multiplication by $g$ takes a non-zero square to a non-zero non-square and vice versa.

So if we can represent $0$ as a sum of two non-squares, then multiplication by $g$ shows that $0$ can also be written as a sum of two squares: $$0=a^2+b^2.$$ This implies that $-b^2=a^2$ and a fortiori that $-1=(a/b)^2$ is a square. This is known to be the case in $\Bbb{F}_q$ if and only if $q\equiv1\pmod4$.

Consequently:

There exists arbitrarily large finite fields such that the element $0$ cannot be written as a sum of two non-squares of that field. More precisely, this happens in the field $\Bbb{F}_q$ whenever $q\equiv-1\pmod4$.

A more interesting result is that any non-zero element $z$ of a finite field $\Bbb{F}_q$, $q$ and odd number $>5$, can be written as a sum of two non-squares. This can be seen as follows.

Assume first that $z$ is a square. Then $g^{-1}z$ is a non-square. By the well- known result we can write it as a sum of two squares $$g^{-1}z=x^2+y^2.$$ Because $g^{-1}z$ is a non-square, we can deduce that $x$ and $y$ must both be non-zero. This means that the elements $gx^2,gy^2$ are both non-squares, and $$z=gx^2+gy^2$$ is a presentation of the required type.

If $z=ga^2$ is a non-square then we need the result (see e.g. Ireland and Rosen) that the equation $$x^2+y^2=1\qquad(*)$$ has $q-\eta(-1)$ solutions (here $\eta$ is the unique multiplicative character of order two, so equal to the Legendre symbol in the case of a prime field). The equation $(*)$ is equivalent to $$a^2x^2+a^2y^2=a^2,$$ so the equation $x^2+y^2=a^2$, too, has $q-\eta(-1)\ge q-1$ solutions. At most $4$ of those solutions have either $x=0$ or $y=0$. So if $q>5$, then we are guaranteed the existence of elements $x\neq0\neq y$ such that $g^{-1}z=a^2=x^2+y^2$. Again, it follows that $$z=gx^2+gy^2$$ is a presentation of $z$ as a sum of two non-square.

The OP noted themself that in the fields of $3$ or $5$ elements there are too few non-squares. For example in $\Bbb{F}_5$ the only non-squares are $2$ and $3$, and we cannot write either of those as sums of two non-squares.

For the case of the prime fields the elegant solution by Mikhail Ivanov is surely better than this argument.

• @Will: I think that if we leave zero out of the reckoning we get a more interesting problem :-) Thinking... if we can write $g^{-1}x$ as a sum of two non-zero squares, then we can write $x$ as a sum of two non-squares following the same trick... So any square $x$ can be written as a sum of two non-squares because $g^{-1}x$ is a non-square. BUT. We need something that only works in large enough fields. – Jyrki Lahtonen Mar 9 '16 at 19:20
• Ordinarily I compute a bunch of examples, see what is going on most likely, but I am still computer crunching on math.stackexchange.com/questions/1685100/… looking for possible methods for a proof in the opposite direction... – Will Jagy Mar 9 '16 at 19:30
• I think I did copy some pages from a book that did such things, I willl look for it. Meanwhile Ireland and Rosen say the number of solutions to $x^2 + y^2 \equiv 1 \pmod p$ for odd prime $p$ is $p - (-1|p).$ Pages 92-93, on Jacobi sums – Will Jagy Mar 9 '16 at 19:55
• Thanks, @Will. I was trying to recall that result. It settles the question. Editing. – Jyrki Lahtonen Mar 9 '16 at 19:57
• @Ishika a square $a$ cannot be a primitive element, as then all powers $a^n$ would be squares. So such $a$ is a non-square. Why did you ask your original question? – Will Jagy Mar 9 '16 at 21:03

For prime fields its true for $p=4k+1>5$, and for all elements except 0 for $p=4k+3$.

1. If $p=4k+3$, then 0 cannot be written in this way.
2. Now for non-zero elements. Its equivalent to prove that each element is the sum of two non-zero squares.

2a. For squares use such formula $$a^2=(\frac35a)^2+(\frac45a)^2.$$

2b. Let $x$ be non-square without such decomposition. Then, of course, all non-square don't have such decomposition. Since $x-1$ is non-square (if not, then $x=1+a^2$), then $x-1$, $x-2$, $\dots$ $2$, $1$ are non-squares.Contradiction.

• Very nice! Your trick in 2b seems to work for prime fields only. May be it can be souped up to work for all finite fields? – Jyrki Lahtonen Mar 9 '16 at 19:40