This is a toy version of a problem I have posted recently.
Imagine playing the following game. You choose a polynomial $B$ over a finite field $\mathbb F_p$, of degree $\deg B\le p-1$ (where $p$ is a large prime). I can modify your polynomial any way I wish, except that I am not allowed to add or change monomials of degree exceeding $0.9p$. My goal is to make the resulting polynomial split completely into linear factors; if I fail to do so, you win.
- What polynomial $B$ will you start the game with to win?
- Is there a comprehensible classification of all winning (for the first player) polynomials?
As an illustration, if I can change only monomials of degree smaller than $(p-10)/4$, then you win by choosing $B(x):=x^{p-1}-nx^{p-3}$, where $n$ is a quadratic non-residue modulo $p$. To see this, suppose that $R$ is a polynomial of degree $d$ such that $Q(x):=x^{p-1}-nx^{p-3}+R(x)$ splits into linear factors, and show that $d\ge(p-10)/4$. Writing $D(x):=(Q(x),x^{p-1}-1)$, we have \begin{align*} D(x) &= (nx^{p-3}-R(x)+1,x^{p-1}-1) \\ &= (nx^{p-1}-x^2R(x)+x^2,x^{p-1}-1) \\ &= (x^2R(x)-x^2-n,x^{p-1}-1), \end{align*} so that $\deg D\le d+2$. On the other hand, since $Q(x)$ splits into linear factors, it is a divisor of the polynomial $$ (Q(x),x^p-x)^3(x^3Q(x))''' = (Q(x),x^p-x)^3(x^3R(x))'''. $$ Since the degree of $(Q(x),x^p-x)$ does not exceed $\deg D+1$, we conclude that either $$ p-1 = \deg Q \le 3(\deg D+1) + \deg R \le 4d+9, $$ or $(x^3R(x))'''=0$. In the former case we are done, in the latter case $R=0$ and $Q(x)=x^{p-1}-nx^{p-3}$, contrary to the choice of $n$ and the assumption that $Q$ splists into linear factors.
It should be possible to push this argument to replace $(p-10)/4$ with $p/2+O(1)$, but I cannot see how to get all the way up to $0.9p$.
