5
$\begingroup$

Consider a polynomial $p(x)$ with of degree $d$ with coefficients in $GF(2)$. How many roots can it have in $GF(2^m)$? The intent here is that $d \ll 2^m$.

The trivial bound is of course $\leq d$. When $d$ is large, then this bound can be tight: take $p(x) = x^{2^m} + x$.

But when $d \ll 2^m$ I suspect something different happens. A random polynomial $p(x)$ should act kind of like a random function on $GF(2^m)$, and have about $1$ root. I expect that the subset of polynomials I am interested in (low degree, $GF(2)$-coefficients) is basically like a random subset of such polynomials so nothing special algebraic happens.

Hence the actual number of roots should be roughly Poisson, so one would expect that taking the maximum (over all $2^d$ possible polynomials $p$), the maximum number of roots would be something like $d/\log d$.

How far can I push this random-function intuition? For example, can I say that most polynomials have approximately $O(1)$ roots, etc.?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Write $p=\prod_{i<k}p_i$ where the $p_i$ are irreducible, of degrees $d_i=\deg(p_i)$. If $d_i\mid m$, then $p_i$ has $d_i$ roots in $\mathbb F_{2^m}$, otherwise it has no roots. $\endgroup$
    – Emil Jeřábek
    Commented Mar 17, 2014 at 22:34
  • 3
    $\begingroup$ That is to say, the magnitude of $m$ by itself does not say much. If $m$ is divisible by $d!$, every such $p$ will split in $\mathbb F_{2^m}$, whereas if $m$ is a large prime, $p$ will have no more roots than it already had in $\mathbb F_2$. $\endgroup$
    – Emil Jeřábek
    Commented Mar 17, 2014 at 22:43
  • 2
    $\begingroup$ Also, these polynomials do not at all behave like random functions on $\mathbb F_{2^m}$: they are uniquely determined by their values on any $(d+1)$-element subset of $\mathbb F_{2^m}$, and they commute with the Frobenius automorphism $x\mapsto x^2$. $\endgroup$
    – Emil Jeřábek
    Commented Mar 17, 2014 at 22:54
  • 2
    $\begingroup$ Note also that a random polynomial with coefficients in $GF(2)$ might act very differently, with respect to its number of roots in $GF(2^m)$, from a random polynomial with coefficients in $GF(2^m)$ itself. For example, Emil pointed out that every degree-$d$ polynomial with coefficients in $GF(2)$ has $d$ roots in $GF(2^{d!})$. But the average number of roots in $GF(2^{d!})$ of a degree-$d$ polynomial with coefficients in $GF(2^{d!})$ itself is exactly $1$, as you can see by varying only the constant coefficient for each input. $\endgroup$
    – Greg Martin
    Commented Mar 17, 2014 at 23:37

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .