8
$\begingroup$

Given a finite field $F$ of odd characteristic, does there always exist an element $x$ of $F$ such that $1 + x^2$ is not a square in $F$? If so, can one even find a natural description of such an element, e.g. as a function of $\lvert F \rvert$ and a generator of $F^\times$?

$\endgroup$

3 Answers 3

17
$\begingroup$

Short answer I found to the existence part of my question.

Let $\lvert F \rvert = p^n$ for some odd prime $p$ and a natural number $n$. The number of squares in $F$ is given by $\frac{p^n + 1}{2}$, a number not divisible by $p$. If we would have that $1 + x^2$ is always a square, then any orbit of the action of $+1$ would either contain no squares or consist entirely of squares. That is, for any square $x^2$, also $x^2 + 1, x^2 + 2, \ldots, x^2 + (p - 1)$ would be squares.

In particular, the number of squares would be a multiple of $p$, as every orbit of this action contains $p$ elements. Contradiction.

$\endgroup$
3
  • $\begingroup$ Very elegant and nice! +1 $\endgroup$
    – pisco
    Dec 7, 2017 at 13:34
  • $\begingroup$ I don't understand the orbit part. What is the action of $+1$? $\endgroup$ Dec 7, 2017 at 13:46
  • 1
    $\begingroup$ I will formulate it differently $\endgroup$
    – Bib-lost
    Dec 7, 2017 at 13:50
5
$\begingroup$

It is easy to show that such element always exists.


Let $F$ be a finite field of odd characteristic, we copy the definition of Legendre symbol:

$$\bigg( \frac{a}{F}\bigg) = \begin{cases}1 \quad \text{ if } a\neq 0 \text{ is a square in } F \\-1 \quad \text{ if } a\neq0 \text{ not a square in } F \\0 \quad \text{ if } a=0 \end{cases}$$

Then you can show the following (the analogs for Legendre symbol is well-known):

$$\bigg( \frac{ab}{F}\bigg) = \bigg( \frac{a}{F}\bigg) \bigg(\frac{b}{F}\bigg)$$

Also, (again, the analogs for Legendre symbol is well-known)

$$\sum_{x\in F} \bigg(\frac{x}{F} \bigg) = 0$$ $$\tag{1}\begin{equation}\sum_{x\in F} \bigg(\frac{x^2+ax+b}{F} \bigg) = -1 \quad \quad \text{if }a^2-4b\neq 0 \end{equation}$$

In particular, we have $$\sum_{x\in F} \bigg(\frac{x^2+1}{F} \bigg) = -1$$ so some terms must be $-1$, this implies there is always an $x\in F$ such that $1+x^2$ is not a square in $F$.


I will outline the proof of $(1)$: completing the square, we only need to prove when $a\neq 0$, $$S_a = \sum_{x\in F} \bigg(\frac{x^2-a}{F} \bigg) = -1$$ Note that when $a,b$ are both residues or both non-residues, $S_a = S_b$. Let $u$ denote a non-residue. $$\sum_{a\in F} S_a = \sum_{x\in F}\sum_{a\in F} \bigg(\frac{x^2-a}{F} \bigg) = 0$$ because the inner sum is identically zero. Hence $$\tag{2}S_0 + \frac{|F|-1}{2} S_1 + \frac{|F|-1}{2} S_u = 0 \implies S_1 + S_u = -2 $$ where we used the fact that $S_0 = |F|-1$. Moreover, $$\sum_{a\in F} S_{a^2} = \sum_{a,x\in F} \bigg(\frac{x-a}{F} \bigg)\bigg(\frac{x+a}{F} \bigg) = \sum_{x\in F} \sum_{a\in F} \bigg(\frac{x+2a}{F} \bigg)\bigg(\frac{x}{F} \bigg) = 0$$ this implies $$S_0 + (|F|-1)S_1 = 0 \implies S_1 = -1$$ Combining with $(2)$ shows $S_a = -1$ whenever $a\neq 0$.

$\endgroup$
6
  • $\begingroup$ Could you please elaborate what $f(x)=x^2+ax+b$ is separable means? I'm just asking for increasing my knowledge. Thanks. $\endgroup$ Dec 7, 2017 at 13:29
  • 1
    $\begingroup$ But that's not true, I think. I mean $x^2+1$ is indeed factorized into linear factors when $p=4k+1$. For example, because $x=2$ modulo $5$ is equal to $-1$, $x^2+1$ can indeed be factorized into linear terms in $\mathbb{Z}_5$. Right? $\endgroup$ Dec 7, 2017 at 13:38
  • $\begingroup$ @pisco125 Could you elaborate on why the last statement (when $x^2 + ax + b$ is not a square) holds? It seems to contain the crucial point of the argument but I do not see why it should hold. $\endgroup$
    – Bib-lost
    Dec 7, 2017 at 13:38
  • $\begingroup$ @pisco125: So, in other words you meant that if $ax^2+bx+c$ can be written as $a(x-r)^2$ then it is separable? $\endgroup$ Dec 7, 2017 at 13:43
  • $\begingroup$ @stressed-out : "Separable" here would mean "having distinct roots". In general, separability means one can place disjoint open sets (in some topology) around each root. This is impossible if any root is repeated, which is captured by pisco125's "cannot be written as the square of a linear polynomial" -- i.e., this quadratic does not have repeated roots. I'm having a hard time understanding your interpretation of those words in exactly the opposite sense. $\endgroup$ Dec 7, 2017 at 14:47
1
$\begingroup$

For $F=\mathbb{F}_p$ we can use the usual Legendre symbol to find such an $x$. For example, we can choose $x=-1$, and then $1+x^2=2$ is not a square in $F$ if and only if $$ \left( \frac{2}{p}\right)=-1, $$ i.e., if and only if $p\equiv 3,5\bmod 8$. For the cases $p\equiv 1,7\bmod 8$ we may chose a different $x$. In general, for $F=\mathbb{F}_{p^n}$ this is more complicated, but we may use the Legendre symbol $(a/F)$ as in the answer above.

$\endgroup$
3
  • 1
    $\begingroup$ I think question is about general finite field, not just $\mathbb{Z}/p\mathbb{Z}$. $\endgroup$
    – pisco
    Dec 7, 2017 at 13:30
  • $\begingroup$ Right, I do not see how this would work for general finite fields. Taking $p \equiv 3, 5 \bmod 8$ we can definitely find finite fields characteristic $p$ in which $2$ is a square, for example. $\endgroup$
    – Bib-lost
    Dec 7, 2017 at 13:33
  • $\begingroup$ Yes, sure. This was only meant as a "starting hint". We can do a similar (but more involved) argument with the Legendre symbol for $F$. $\endgroup$ Dec 7, 2017 at 14:18

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.