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

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