For large and even $n$ consider a random degree $n$ polynomial $v(t)$ with coefficients from $\{-1,0,1\}$. The coefficients are chosen uniformly and independently.

Is it possible to get an estimate for the probabiltiy that $v(t)$ is divisible either by $1-t$ or by $1+t^{2^{j-1}}$, for some $j$?

  • $\begingroup$ What sort of estimate are you looking for (that is: upper bound, lower bound, both?) $\endgroup$
    – Igor Rivin
    May 13, 2014 at 20:24
  • $\begingroup$ @IgorRivin Upper and lower bounds that apply for large $n$ would be great. If I had to choose, I would pick the upper band though. $\endgroup$
    – Simd
    May 13, 2014 at 20:28
  • 3
    $\begingroup$ This shouldn't be too hard: divisibility by $1-t$ is equivalent to the sum of the coefficients being 0, while divisibility by $1+t^k$ for some $k$ has the same probability of being divisible by $1-t^k$, and this is equivalent to the vanishing of the sum of $k$-spaced coefficients. One should get a good asymptotic control on these two conditions holding both separately and simultaneously. $\endgroup$ May 13, 2014 at 20:57
  • 1
    $\begingroup$ @MarcoGolla I think the divisibility by $1+t^k$ is actually equivalent to the sum of the $k$ sums of $k$-space coefficients being equal. I agree that this should not be hard. $\endgroup$
    – Igor Rivin
    May 13, 2014 at 21:45

1 Answer 1


I will compute the probabilities separately, and bound the probability you look for with the sum of the probabilities. This is probably not a great bound, but I guess you can squeeze out some more from this idea. Just to make things clear, I will assume that $v$ is of degree at most $n$ (that is, I allow the leading coefficients to vanish).

The probability $p_0$ that $v$ is divisibile by $1-t$ is the probability that the sum of all coefficients is 0, and this in turn is equivalent to having as many positive coefficients as negative ones. In particular, $$p = \frac1{3^{n+1}}\sum_{k=0}^{\lfloor \frac{n+1}2 \rfloor} \frac{(n+1)!}{k!^2(n-2k)!}$$.

The probability $p_j$ that $v$ is divisible by $1+t^{2^{j-1}}$ is 0 when $j>1+\log_2 n$. When $0\le j \le 1+\log_2 n$, the probability is equivalent to all the alternated sums of $2^{j-1}$-spaced coefficients being zero.

All of these sums are pairwise independent (they depend on disjoint sets of coefficients), so the probability that they all vanish simultaneously is their product. The same argument for the computation of $p$ shows that each of these probabilities is roughly (here I'm using the fact that $n$ is large) $$p_j \approx \left(\frac1{3^m} \sum_{k=0}^{\lfloor \frac{m}2 \rfloor} \frac{m!}{k!^2(2m-k)!}\right)^{2^{j-1}}$$ where $m = \lfloor \frac{n+1}{2^{j-1}} \rfloor$.

Therefore, the probability you're looking for is bounded by a quantity that resembles $\displaystyle\sum_{j\ge 0} p_j$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.