For a cubic polynomial $f(x)=x^3+x^2+\frac{1}{4}x+c$ over $\mathbb{F}_q$, where $q$ is a odd prime power, I find that for a lot of $q$, there does not exist $c\in\mathbb{F}_q$ such that $f$ has three distinct roots in $\mathbb{F}_q$, one of which is a quadratic residue and the other two are non-residues. I have not found any counter examples, so my question is, does it hold for any $q$? If so, what forms of cubic polynomials have such property?
Cubic Polynomials Over Finite Fields with Quadratic Residue Roots – Number Theory
field-extensionsfinite-fieldsgalois-theorynt.number-theory
Related Solutions
These are known as Fekete polynomials: http://en.wikipedia.org/wiki/Fekete_polynomial . I don't know of any results on their Galois groups.
These results have been known for many years. Here are some references and further developments; full bibliographic details are at the end of this answer.
Reducibility criteria for cubics over finite fields of characteristic at least $5$ were given already in 1906 by Dickson. In fact he gave conditions for a cubic to have each of the possible factorization types. Reducibility criteria for cubics in characteristic $2$ were given in 1966 by Berlekamp, Rumsey and Solomon (see also their 1967 paper). Those criteria are slightly different than your Theorem A. Your Theorems A and B appear to have been published for the first time in 1975 by Williams, who also gave criteria for each of the possible factorization types.
Reducibility criteria for quartics over prime fields of odd order were given by Skolem in 1952. In 1969, Leonard gave a different proof of Skolem's result, which extends at once to non-prime fields of odd order. Finally, reducibility criteria for quartics in characteristic $2$ were given by Leonard and Williams in 1972.
Your Theorems A and B can be generalized in various ways. Bluher's 2004 paper generalizes your Theorem A to polynomials of the form $x^{p^k+1}+ax+b$. In a series of papers culminating in 1980, Agou determined all instances when $f(L(x))$ is irreducible over $\mathbf{F}_{p^s}$, where $f,L\in\mathbf{F}_{p^s}[x]$ and all terms of $L(x)$ have degree $p^i$ with $i\ge 0$. The case $f=x+c_3$ and $L=x^3+c_2 x$ with $p=3$ yields your Theorem B. Subsequently, a simpler proof of Agou's results was given by Cohen in 1982; following two related papers by Moreno, Cohen gave an even simpler proof in 1989.
References:
- S. Agou, Irréducibilité des polynômes $f(\sum_{i=0}^m a_i X^{p^{ri}})$ sur un corps fini $\mathbf{F}_{p^s}$, Canadian Mathematical Bulletin 23 (1980), 207-212
- E. R. Berlekamp, H. Rumsey and G. Solomon, Solutions of algebraic equations in field of characteristic 2, Jet Propulsion Lab. Space Programs Summary No. 4 (1966), 37-39
- E. R. Berlekamp, H. Rumsey and G. Solomon, On the solution of algebraic equations over finite fields, Information and Control 10 (1967), 553-564.
- A. W. Bluher, On $x^{q+1}+ax+b$, Finite Fields and their Applications 10 (2004), 285-305
- S. D. Cohen, The irreducibility of compositions of linear polynomials over a finite field, Compositio Mathematica 47 (1982), 149-152
- S. D. Cohen, The reducibility theorem for linearised polynomials over finite fields, Bulletin of the Australian Mathematical Society 40 (1989), 407-412
- L. E. Dickson, Criteria for the irreducibility of functions in a finite field, Bulletin of the American Mathematical Society 13 (1906), 1-8
- P. A. Leonard, On factoring quartics (mod $p$), Journal of Number Theory 1 (1969), 113-115
- P. A. Leonard and K. S. Williams, Quartics over GF($2^n$), Proceedings of the American Mathematical Society 36 (1972), 347-350
- Th. Skolem, The general congruence of 4th degree modulo $p$, $p$ prime, Nordisk matematisk tidskrift 34 (1952), 73-80
- K. S. Williams, Note on cubics over GF($2^n$) and GF($3^n$), Journal of Number Theory 7 (1975), 361-365
Best Answer
EDIT: Following a clever observation of user44191 in the comments:
If $f(x)$ is a monic polynomial, and $c$ a number, then the polynomial $xf(x)^2+c$ has a similar property to your example (the case $f(x)=x+1/2$). Indeed, we have $x = \frac{-c}{f(x)^2}$ so
This produces polynomials of odd degree. For even degree examples, we can do $f(x)^2+cx$. This gives $x =\frac{ f(x)^2}{-c}$ so we have the same thing except if $-c$ is zero than all roots are double, and there is a special case if $f(0)=0$.
So we have many examples of polynomials of this type.
(See the edit history for an earlier argument, special to the case of degree 3 polynomials, if desired. This was inspired by darij grinberg's answer, and that earlier answer inspired user44191's comment, so both of them are partially responsible for this solution.)