Problem 1730

Solution:
We begin with the following claims:

Claim 1: There are finitely many $Q(x)$ that divide some $P(x)$ of the given form.

Proof: First of all the leading coefficient of $Q$ must be 1, because if $Q$ divides $P$ then $P / Q$ must have integer coefficients too. Note that if $S=\{s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}\}$ with elements in increasing order, then
$$|P(x)| \geq |x^{s_{6}}| - |x^{s_{5}}| - |x^{s_{4}}| - \cdots - |x^{s_{1}}| = |x|^{s_{6}} - |x|^{s_{5}} - |x|^{s_{4}} - \cdots - |x|^{s_{1}}.$$
So all the roots of $P$ must have magnitude less than 2, and so do all the roots of $Q$. Therefore, all the symmetric expressions involving the roots of $Q$ are also bounded, so by Vieta's Theorem all the coefficients of $Q$ of a given degree are bounded, and the number of such $Q$ is therefore finite.

Claim 2: If $Q$ has a nonzero root that does not have magnitude 1, then the probability that it divides a randomly chosen $P$ vanishes as $n$ goes to infinity.

Proof: WLOG suppose that $Q$ has a root $r$ with $|r| > 1$ (similar argument will apply for $|r| < 1$). Then from the bound given in the proof of Claim 1, it is not difficult to see that $s_{6} - s_{5}$ is bounded since
$$|P(r)| > |r|^{s_{6}} - 5|r|^{s_{5}} > |r|^{s_{6} - s_{5}} - 5$$
which approaches infinity as $s_{6} - s_{5}$ goes to infinity. By similar argument we can show that $s_{5} - s_{4}, s_{4} - s_{3}, \ldots$ are all bounded. Therefore, the probability of choosing the correct coefficients is bounded above by the product of five fixed numbers divided by $n^{5} / 5!$, which vanishes as $n$ goes to infinity.

From the claims above, we see that we only need to consider polynomials with roots of magnitude 1, since the sum of all other possibilities vanishes as $n$ goes to infinity. Moreover, this implies that we only need to consider roots of unity. Since $Q$ has degree at most 3, the only possible roots are $-1, \pm i, \frac{-1 \pm i \sqrt{3}}{2}, \frac{1 \pm i \sqrt{3}}{2}$, corresponding to $x+1, x^{2}+1, x^{2}+x+1, x^{2}-x+1$ (note that eighth root of unity is impossible because $x^{4}+1$ cannot be factored in the rationals).

Now we compute the probability of $P(r)=0$ for each possible root $r$. Since the value of $x^{s}$ cycles with $s$, and we only care about $n \rightarrow \infty$, we may even assume that the exponents are chosen independently at random, with repetition allowed.

Case 1: When $r=-1$, the number of odd exponents need to be equal to the number of even exponents, which happens with probability $\frac{\binom{6}{3}}{2^{6}} = \frac{5}{16}$.

Case 2: When $r= \pm i$, the number of exponents that are 0 modulo 4 need to be equal to those that are 2 modulo 4, and same for 1 modulo 4 and 3 modulo 4, which happens with probability $\frac{\binom{6}{0}}{2^{6}} \cdot \frac{\binom{0}{0}\binom{6}{3}}{2^{6}} + \frac{\binom{6}{2}}{2^{6}} \cdot \frac{\binom{2}{1}\binom{4}{2}}{2^{6}} + \frac{\binom{6}{4}}{2^{6}} \cdot \frac{\binom{4}{2}\binom{2}{1}}{2^{6}} + \frac{\binom{6}{6}}{2^{6}} \cdot \frac{\binom{6}{3}\binom{0}{0}}{2^{6}} = \frac{25}{256}$.
Note that Case 1 and Case 2 have no overlaps, since the former requires 3 even exponents, and the latter requires 0, 2, 4, or 6 even exponents.

Case 3: When $r=\frac{-1 \pm i \sqrt{3}}{2}$, the number of exponents that are $0,1,2$ modulo 3 need to be equal to each other, so the probability is $\frac{\binom{6}{2,2,2}}{3^{6}} = \frac{10}{81}$.

Case 4: When $r=\frac{1 \pm i \sqrt{3}}{2}$, then if $n_{i}$ is the number of exponents that are $i$ modulo $6$ ($i=0,1,2,3,4,5$), then $n_{0}-n_{3}=n_{2}-n_{5}=n_{4}-n_{1}=k$ for some $k$. Since $3k \equiv n_{0}+n_{1}+\cdots+n_{5}=6 \equiv 0 \pmod{2}$, $k$ must be one of $-2,0,2$. When $k=0$, we have $n_{0}+n_{2}+n_{4}=n_{1}+n_{3}+n_{5}$, which is the same as Case 1. When $k=2$, we have $n_{0}=n_{2}=n_{4}=2$, which is covered in Case 3, and similar for $k=-2$. Therefore we do not need to consider this case.

Now we deal with over-counting. Since Case 1 and 2 deal with the exponents modulo 4 and Case 3 deal with exponents modulo 3, the probabilities are independent from each other. So by complementary counting, we compute the final probability as
$$1 - \left(1 - \frac{5}{16} - \frac{25}{256}\right)\left(1 - \frac{10}{81}\right) = 1 - \frac{151}{256} \cdot \frac{71}{81} = \frac{10015}{20736}$$