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