Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$?

share|improve this question
2  
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
add comment

4 Answers 4

up vote 11 down vote accepted

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

share|improve this answer
2  
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
5  
@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
add comment

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).

share|improve this answer
add comment

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)$.

share|improve this answer
1  
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
add comment

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...

share|improve this answer
    
+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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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