5
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – N. S. Mar 9 '16 at 18:55
  • $\begingroup$ @Dietrich Does $T=T_{b}$ in your comment? and is $b$ an arbitrary element of the field? $\endgroup$ – Ishika Mar 9 '16 at 19:01
  • $\begingroup$ @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. $\endgroup$ – Ishika Mar 9 '16 at 19:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Will Jagy Mar 9 '16 at 19:15
  • 1
    $\begingroup$ @WillJagy Right, I see the problem. One could ask to leave out $0$. $\endgroup$ – Dietrich Burde Mar 9 '16 at 19:18
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen Mar 9 '16 at 19:20
  • 1
    $\begingroup$ 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... $\endgroup$ – Will Jagy Mar 9 '16 at 19:30
  • 1
    $\begingroup$ 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 $\endgroup$ – Will Jagy Mar 9 '16 at 19:55
  • 1
    $\begingroup$ Thanks, @Will. I was trying to recall that result. It settles the question. Editing. $\endgroup$ – Jyrki Lahtonen Mar 9 '16 at 19:57
  • 2
    $\begingroup$ @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? $\endgroup$ – Will Jagy Mar 9 '16 at 21:03
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Mar 9 '16 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.