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?
  • $\begingroup$ Note: The author has posted an elaboration of this question to MathOverflow here. I think these are very intriguing questions! $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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" :) $\endgroup$ – Wolfgang Nov 13 '13 at 8:34
  • $\begingroup$ 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. $\endgroup$ – Jair Taylor Nov 13 '13 at 18:52
  • $\begingroup$ 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. $\endgroup$ – Wolfgang Nov 14 '13 at 19:58
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Jair Taylor Nov 18 '13 at 18:58
  • $\begingroup$ Do you have an idea about how to get positive coefficients? $\endgroup$ – Jair Taylor Nov 18 '13 at 19:20
  • $\begingroup$ @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. $\endgroup$ – Ewan Delanoy Nov 18 '13 at 21:32
  • $\begingroup$ 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. $\endgroup$ – Jair Taylor Nov 18 '13 at 22:11
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Wolfgang Nov 19 '13 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.