MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f(x), g(x), h(x)$ be randomly chosen irreducible polynomials over the finite field $GF(2^n)$.

What would the probability be for $\sum_{(i,j,k:i,j,k\in\mathbb{N},i+j+k=C)} f^i(x)g^j(x)h^k(x)=0$, where $C$ is much smaller than $n$?

I want to prove that this probability tends to zero as $n$ increases.

share|cite|improve this question
up vote 0 down vote accepted

Taking a view from old-fashioned algebra: your sum can be interpreted from a generating function of a product of three geometric series. That generating function has a partial fraction decomposition, with numerators say P, Q, and R. If these were rational functions in x alone the issue would be like

$Pf^m(x) + Qg^m(x) +Rh^m(x) = 0$

for certain values of m. There is no reason to expect this can happen more than three times, I think.

Is there a proof in there? This is too long for a comment, really.

share|cite|improve this answer

Your Answer


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.