# Defining irreducible polynomials recursively: how far can we go?

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?
• Note: The author has posted an elaboration of this question to MathOverflow here. I think these are very intriguing questions! – Jair Taylor Nov 23 '13 at 21:31

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.

• Would you believe it?... After encountering six or seven ones in a row, it seemed so obvious, and so it didn't occur to me at all to look up what I thought to be a "finite sequence" in the oeis. So much for "Don't trust numerical evidence too quickly" :) – Wolfgang Nov 13 '13 at 8:34
• Starting with other polynomials does seem to result in a sequence that's eventually just ones. For example if we start with $1 + 3x + 2x^2$ we get the coefficient sequence $1,3,2,3,3,1,1,1, \ldots$ and then only ones for at least a few hundred terms. I would guess that there is a simple proof that there are starting polynomials so that the next coefficient is arbitrarily high - you'd have to cleverly choose your starting polynomial $p(x)$ so that $p(x) + kx^n$ has an obvious factorization for $k < N$. I think this question deserves more attention. – Jair Taylor Nov 13 '13 at 18:52
• I agree with you last sentence. :) It seems to me that for many polynomials, the sequence becomes quickly periodic: $x^2+1$ yields 1,0,1,1,[1,1,2]. Others, including the "trivial" one $1$, seem sort of quasi periodic, with several (almost symmetric!) repeated patterns in a row. I haven't yet encountered a coefficient bigger than 4. – Wolfgang Nov 14 '13 at 19:58
• The periodicity is pretty surprising to me. I've put a bounty on this question. If it doesn't get much attention you might consider posting it to MathOverflow. – Jair Taylor Nov 17 '13 at 23:48

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.

• Nice. I had thought of Lagrange interpolation but I didn't know how to get integer coefficients. But I can't seem to get your recursive formula to work, am I missing something? – Jair Taylor Nov 18 '13 at 18:58
• Do you have an idea about how to get positive coefficients? – Jair Taylor Nov 18 '13 at 19:20
• @JairTaylor I added one more step to the recursive formula proof, hope you’re convinced now. It is certainly feasable to get positive coefficients (if we relax the lower bound on $a_{n+1}$, for example $a_{n+1}\geq \frac{n}{2}$), though the details may be messy. I’ll update this answer if I find anything useful in that direction. – Ewan Delanoy Nov 18 '13 at 21:32
• Ah, I see now. The edited formula works nicely. Thanks! I think I'll leave the bounty up for now to see if it attracts more interest in the periodicity question. It appears that starting with your $p_n(x)$, you get coefficients $a_{n+1} = n+2$ and $a_{n+k} = 1$ for $k>1$, that is, $p_n(x) + (n+2)x^{n+1} + x^{n+2} + \ldots + x^{n+ k}$ is always irreducible. – Jair Taylor Nov 18 '13 at 22:11
• In between, I have found a much easier one: $p_n(x)=(1+x)(1+2x)\cdots(1+nx)+x^{n}$. Then $p_n(x)+ax^{n+1}$ has a factor $(1+ax)$. – Wolfgang Nov 19 '13 at 8:38