# Irreducible polynomial not attaining squares over finite field

Is it possible to construct an irreducible polynomial $f$ over $\mathbb{F}_{q}$ such that $f(x)$ is a non-square for any $x \in \mathbb{F}_{q}$?

I can prove the existence of irreducible polynomials (Euclid's argument), and I can construct polynomials with no square values (for example by Lagrange interpolation through non-squares), but satisfying these 2 conditions feels difficult.

Motivation: I am trying to construct an hyper-elliptic curve $y^2 = f(x)$ with no rational points.

EDIT: Can you construct such an $f$ that will not be constant on the ground field $\mathbb{F}_{q}$?

-
The en.wikipedia.org/wiki/Hasse_bound gives you a lower bound on the genus of your curve. On average, about one in $d$ of the polynomials of degree $d$ are irreducible; one would imagine that your Lagrange interpolation method should work if you just make enough random trials. – Hurkyl Jul 7 '12 at 4:09

One way is with Artin-Schreier polynomials $f(x)=x^q-x+a$ with $a$ a non-square.

-
This answer and Henning's both leave open the interesting question of whether such a polynomial can take on more than one value... – Steven Stadnicki Jul 6 '12 at 22:50
@paul Nice answer! I actually thought about these polynomials lately (in another context), as they give explicit formulae for irreducible polynomials. – Ofir Jul 6 '12 at 23:02
@StevenStadnicki: An example of that would be $x^4+2$ modulo 5. Its values are $2$ and $3$, and a bit of calculation shows that it cannot be the product of two quadratics. – Henning Makholm Jul 6 '12 at 23:03

It is possible for at least some $q$s, such as $f(x) = x^3-x+2$ over $\mathbb F_3$.

Here the value of $f(x)$ is $2$ for all $x$, and $2$ is not square modulo 3.

$f$ is also irreducible, because it it were reducible it would have a linear factor (the product of two nonlinear polynomials would have degree 4 or more), but then it would have a root, which contradicts the value always being $2$.

Under the additional requirment that $f$ needs to be able to take on two different values, take for example $x^4+2$ in $\mathbb F_5$. Its values are 2 and 3, and a bit of calculation shows that it cannot be the product of two quadratics. (It cannot have any linear factors either, because as above then it would have a root and 0 is always square).

-

Let $h$ be any function $\mathbb{F}_q \to \mathbb{F}_q \setminus \{ 0 \}$. Then there is an irreducible polynomial $f$ such that $f(x) = h(x)$ for all $x \in \mathbb{F}_q$. In particular, if we choose the values of $h$ to be non-squares, then there is an irreducible polynomial achieving these values. For $p \geq 5$, this answers the question of whether we can make $f$ nonconstant.

Proof By Lagrange interpolation, there is some polynomial $b(x)$ which coincides with the function $h$ on $\mathbb{F}_q$. Consider polynomials of the form $f(x) = a(x) (x^q-x) + b(x)$. Any such $f$ is equal to $h$ on $\mathbb{F}_q$. We have $GCD(x^q-x, b(x))=1$, since $h$ is nonzero. Dirichlet's theorem on primes in arithmetic progressions holds for $\mathbb{F}_q[x]$ (see Chapter 4 in Rosen's Number theory in function fields), so there is an irreducible polynomial of the form $(x^q-x) a(x) + b(x)$.

-
Very cool, and thanks for the link. It's an interesting result - it shows that irreducibilty of a polynomial doesn't have much to do with its values on the ground field (assuming its image doesn't contain 0). – Ofir Jan 4 '13 at 18:54

Here is an example that takes 3 different values in $\mathbb F_{11}$: $x^{5} + 7$. More generally, if $p$ is a Sophie Germain prime and $q=2p+1$, then $x^p + a$ is irreducible over $\mathbb F_q$ for any $a \ne 0,\pm 1$. All sufficiently large primes admit three consecutive quadratic non-residues, so we can find an $a$ that does the job. I would love to be able to say there are infinitely many Sophie Germain primes, though...

-
+1: A very nice construction. Does this generalize to other cases, where $p$ is a large factor of $q-1$? – Jyrki Lahtonen Jul 10 '12 at 12:37