Defining irreducible polynomials recursively: how far can we go?

Question

Fix $n\in\mathbb N$ and a starting polynomial $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_n\ne0$.

Define $p_{n+1},p_{n+2},\dots$ recursively by $p_r = p_{r-1}+a_rx^r$ such that $a_r\in \mathbb N$ is the smallest such that $p_r$ is irreducible over $\mathbb Q$. It should not be too hard to prove (but how?) that there will always be an $r_0$ such that $a_r=1\ \forall r>r_0$. Let $r_0$ be smallest possible. E.g. for $n=0$ and $p_0\equiv 1$, we have to go as far as $r_0=11$, getting before that $(a_0,\dots,a_{11})=(1,1,1,2,2,3,1,2,1,3,1,2)$.

Questions (apart from proving the existence of $r_0$):

• Is it possible to construct, for a certain $n$, a polynomial $p_n$ such that $a_{n+1}$ is bigger than $3$ or even arbitrarily large?

(From the above example, for $n=4$ and $p_n=1+x+x^2+2x^3+2x^4$, we get $a_5=3$, likewise for $n=8$ and $p_n=1+x+x^2+2x^3+2x^4+3x^5+x^6+2x^7+x^8$, we get $a_9=3$.)

• Is it possible to construct, for a certain $n$, a polynomial $p_n$ such that $r_0-n$ is bigger than $11$? If so, how big can $r_0-n$ be?

Answer 1

Very nice questions! The sequence $1,1,1,2,2,3,1, \ldots$ is in Sloanes. I used Sage to generate this sequence. It doesn't seem to become all ones after any point - I've checked it up to a few hundred places. We do eventually get a $4$: $p_{276}(x) = 4x^{276} + x^{275} + x^{274} + \ldots$. We could still ask if the coefficients can become arbitrarily large. The link above doesn't give any references, so I would imagine this problem is open, and presumably very difficult.

Answer 2

The answer to your first question is YES (and a similar method can probably answer positively your second question as well). One can use the following lemma :

Lemma Let $n,g$ be positive integers. Then there is a polynomial $Q_{n,g}\in {\mathbb Z}[X]$ of degree $\leq n$ such that $Q_{n,g}(i)=i^g$ for any integer $i$ between $1$ and $n+1$.

Answer to question 1 using the lemma. Take $p_n=-Q_{n,n+2}$, so that $p_n(x)=-x^{n+2}$ for $1\leq x \leq n+1$. Then for $a\leq n+1$, the polynomial $ax^{n+1}+p_n(x)$ is zero when $x=a$, so it is not irreducible. We deduce $a_{n+1} \geq n+2$ for this $p_n$.

Proof of lemma By Lagrange interpolation, we know that there is a unique polynomial $Q_{n,g}\in {\mathbb Q}[X]$ satisfying the conditions. What we need to show is that the coefficients of $Q_{n,g}$ are integers. If $g\leq n$, then $Q_{n,g}(x)=x^g$ and we are done. For $g>n$, the identity

$$ \frac{x^g-1}{x-1}=\sum_{k=0}^{g-1} \binom{g}{k+1} (x-1)^k $$

shows that when $2 \leq x \leq n+1$, we have $$ x^g=1+(x-1)\bigg( \sum_{k=0}^{g-1} \binom{g}{k+1} Q_{n-1,k}(x-1)\bigg) $$

and so we may take $$ Q_{n,g}(x)=1+(x-1)\bigg(\sum_{k=0}^{g-1} \binom{g}{k+1} Q_{n-1,k}(x-1)\bigg) $$

and we are done by induction.