Consider the cubic polynomial $$ f = x^3+px+q, $$ where $p,q$ are elements of a fixed algebraic closure $\overline{\mathbb{F}}_2$ of $\mathbb{F}_2$.

Is there an elegant criterion for deciding whether $f$ has $0$, $1$ or $3$ roots in the field $\mathbb{F}_2(p,q)$?

For example, I would consider as "elegant" any criterion stipulating that certain polynomial expressions in $p,q$ be "of a certain form," e.g., are themselves values of certain polynomials (with coefficients in $\mathbb{F}_2$).

  • 1
    $\begingroup$ Do you reckon this is easier, or harder, than the same question over the rationals? $\endgroup$ Aug 3 '16 at 3:44

There are $1$ or $3$ roots if and only if $q$ is in the value set of $x^3+px$ on $K=\mathbb F_2(p,q)$. It remains to decide between these two cases, which can be done using the Berlekamp discriminant: The case $q=0$ is trivial, so assume that $q\ne0$, hence $f$ is separable. Let $\alpha,\beta,\gamma$ be the roots of $f$. The Berlekamp discriminant is \begin{equation*} B=\frac{\alpha\beta}{\alpha^2+\beta^2}+\frac{\beta\gamma}{\beta^2+\gamma^2}+\frac{\gamma\alpha}{\gamma^2+\alpha^2}. \end{equation*} If I computed correctly, then \begin{equation*} B=\frac{p^3+q^2}{q^2}. \end{equation*} Now the Galois group of $f$ over $K$ contains a transposition if and only if $B$ is not in the value set of $x^2+x$ on $K$. As we have at least one root of $f$ in $K$, this is equivalent to having exactly one root of $f$ in $K$.

  • $\begingroup$ Thank you very much. Unfortunately for me, the polynomial $x^3+px$ has coefficients in $\mathbb{F}_2(p)$ rather than in $\mathbb{F}_2$, so your solution is not completely satisfactory to me. The stuff about the Berlekamp discriminant is very helpful though! $\endgroup$
    – Milton
    Aug 5 '16 at 17:10
  • $\begingroup$ @Milton: I see. Anyway, maybe Elkies' answer to mathoverflow.net/questions/163155/… is also of interest to you. $\endgroup$ Aug 7 '16 at 12:15
  • $\begingroup$ @Milton Would having a polynomial expression in $p,q,x$, where $x$ is the root of $x^2+x=B$, having a certain form, be sufficient? $\endgroup$
    – Will Sawin
    Jul 1 '18 at 17:05
  • $\begingroup$ @WillSawin Milton was `last seen' at this site more than a year ago ... $\endgroup$ Jul 2 '18 at 8:50

Let $K$, the field generated by the coefficients of $f$, have $t=2^n$ elements. If $p=q=0$, $f$ has a triple root. If $q$ is not $0$, then $f$ is separable. Assume $q$ not $0$. If $p=0$ and n odd, then $f$ has exactly one root in $K$. If $p=0$ and $n$ even then $f$ has $0$ or $3$ roots in $K$. Assume now that $f$ has at least 1 root in $K$. Let $tr$ be the trace of $K$ over the prime field. Put $B=1+\frac{p^3}{q^2}$. Then $f$ has $3$ roots iff $tr(B)=0$.

The question if $f$ has no roots (i.e. $f$ irreducible) can be done by Berlekamp's algorithm.


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.