Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Fix $n\in\mathbb N$ and a starting polynomial (or seed) $p_n=a_0+a_1x+\dots+a_nx^n$ with $a_k\in\mathbb Z\ \forall k$ and $a_0a_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$.

What can be said about the behaviour of the sequence $(a_{n+1},a_{n+2},...)$ ?

I have asked this question on Math SE for $p_n\equiv 1$, where it did receive some but not much attention, and it was suggested to ask it here.

For the vast majority of seeds, it looks like there is an $r_0$ such that $a_r=1$ for all $r\ge r_0$. Denote the set (=class) of these seeds by $C_0$.
For some, there is an $r_0$ such that $a_r=2$ for all $r\ge r_0$. (i.e. a priori such a polynomial with biggest coefficient $1$ instead of $2$ would have a factor $(1+x)$). Denote these by $C_1$.
For others, the sequence becomes periodic with repeating $[1,...,1,2]$ where there are $k-1$ ones. Denote these classes by $C_k$. The onset can be quite long, e.g. the seed $1-x+x^2-x^3+x^4\in C_3$ has its (supposedly) periodic part $[1,1,2]$ only from $a_{261}$ on, after $a_{260}=3$.
I suppose that it should be not too hard to show the periodicity for a given polynomial, if belonging to one of the above classes, on a case-by-case basis. But:

Are there whole families of polynomials that can be shown to belong to a class $C_k, k\ge 2$?

And then there are seeds yielding much more complicated patterns. Below are for example the coefficients for $p_n=-1+x-x^2+x^3-x^4$, from $a_5$ on, using a color code 1=grey, 2=red, 3=yellow and 4=blue ($a_{32}=4$ is the only one). The 3's provide 'landmarks', and it turns out that almost all of what comes between them is symmetric (the braces labeled $a,b,c,...$), only for $c$ one 1 at the margin is not included, and after $d$ the pattern 211 occurs three more times.

${\mathbf{\color{grey}{\color{red}||\color{red}||\color{red}||\color{red}||\color{red}|\color{red}|||||||||\color{red}|||||||||\color{darkblue}| \underbrace{||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||\color{red}||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||| }_{a}\color{yellow}| \underbrace{|||||\color{red}|\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|\color{red}||||||}_{b} \color{yellow}| |\underbrace{|\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||}_{c} \color{yellow}|\color{red}|\color{red}|\color{red}|\color{red}|\color{red}| \color{yellow}| \underbrace{|\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||}_{c}|\color{yellow}| \underbrace{|||||\color{red}|\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|\color{red}||||||}_{b} \color{yellow}| \underbrace{||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||\color{red}||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||| }_{a} \color{yellow}| \underbrace{|||||\color{red}|\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|\color{red}||||||}_{b} \color{yellow} | \underbrace{||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||\color{red}||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||| }_{a} \color{yellow}| \underbrace{|||||\color{red}|\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|\color{red}||||||}_{b} \color{yellow} | \underbrace{||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||| \color{red}||\color{red}||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||| }_{a} \color{yellow}| \underbrace{|||||\color{red}|\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|\color{red}||||||}_{b} \color{yellow} | \underbrace{||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||| \color{red}||\color{red}||\color{red}|||\color{red}|||\color{red}||| \color{red}||\color{red}||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||| }_{d} \color{red}|||\color{red}|||\color{red}|||\\ \color{yellow}| \underbrace{||||||||\color{red}|||||||||\color{red}|||||||||}_{e} \color{yellow}| \underbrace{||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||\color{red}||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}|||\color{red}||| }_{f} }}}$
followed by at least four more identical lines $3e3f$. Might that be the period? Or will the sequence be only "quasi-periodic" with a kind of self-similarity (a quite exciting possibility...)?

The pattern for the seed $1$ is even more complex, but has again the property that most chunks between two 3's are symmetric.

Some questions about these sequences:

  • Can there be an arbitrary number of consecutive 1's (other than the $C_p$ case)?

We can force an arbitrary number of 1's immediately or shortly after $a_n$, which is a trivial exercise of no interest. But later on in the sequence? The seed $(x^6-1)/(x-1)$ exhibits nine blocks of $14$ 1's, but after $a_{327}$, where supposedly the periodic part starts, there are only blocks of $2$ and of $5$ 1's. To wit, here are $a_6,...,a_{391}$ displayed in a way that shows the multiple symmetries in the pre-periodic part.

$$\color{grey}{1\color{red}2 \\ {\color{red}2\color{red}2\color{red}2\color{red}2\color{red}2\color{yellow}311111} \\ {\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}2} \\ {111\color{red}211111111111111\color{red}211111111111111\color{red}2111}\\ {\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}2}\\ {\color{red}211111111111111\color{red}211111111111111\color{red}211111111111111\color{red}211111111111111\color{red}211111111111111\color{red}2}\\ {\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}2}\\ {111\color{red}211111111111111\color{red}211111111111111\color{red}2111} \\ {\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}211111\color{red}2} \\ {11111\color{yellow}3\color{red}2\color{red}2\color{red}2\color{red}2\color{red}2} \\ \color{yellow}311111\color{red}2\color{red}211\color{red}211\color{red}211\color{red}211\color{red}211\color{red}211\color{red}2\color{red}211111\color{yellow}311\color{red}211\color{red}211\color{red}211\color{red}211\color{red}211\color{red}21\color{red}21\color{red}211\color{red}211\color{red}211\color{red}211\color{red}211\color{red}211}$$

The very last line is the periodic (?) part, which is of length 64.
Likewise, the seed $(x^{12}-1)/(x-1)$ produces several blocks of $26$ 1’s, and $1+x+x^{14}$ yields three blocks of $30$ 1's.

  • If the period is displayed as a cycle (i.e. a regular polygon), is there always an axis of symmetry?

This might follow from the fact that if $P(x)$ of degree $m$ is irreducible iff $x^mP(\frac1x)$ is irreducible. Looking at the symmetry in the lines of the above examples (and I've encountered similar patterns over and over again), there seems to be some deep principle at work here. It reminds me somewhat of continued fractions, even though I don't think there is a connection. As said above, the tendency is that almost all chunks of only 1's and 2's (i.e. between two entries >2) are symmetric.

  • Can there be arbitrary large numbers, except from near to the beginning?

Next to the beginning, we can force one arbitrary large value (see here). What about later? Occasionally, there can be 5’s occurring (e.g. $a_{51}$ for the seed $1-x^8+x^{12}+x^{24}$, shortly before it gets periodic [1,2]), but I have not yet encountered more than a 5, and in what seems to be a period never more than a 3.

EDIT: even 6’s can appear: the seed $1-x^4+x^8+x^{12}$ yields the pattern $1_{22},3,2_9,3,1_{10} ,(3,2_{10} ,3,1_{10} )_{11},6,1,2,[2,1,1]$.

Curious things can happen. The seed $1-x^6+x^{12}+x^{24}$ for instance yields the sequence $1_{34},3,2_{34},3,3,2,3,[1,2]$. (Here indices denote repeated entries.)

This really looks like it is worth more investigations.

share|improve this question
Wow, I sure hope you generated the $\TeX$ for for the first display by machine! :-) –  Suvrit Nov 21 '13 at 20:15
Most of it, but not all. Still easier than using another software for creating a graphic, I guess :-) –  Wolfgang Nov 22 '13 at 10:25
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.