The Mersenne-type binary polynomial odd-sequence length conjecture

Exact stopping times and complete phase decomposition for the Mersenne-polynomial family

Work in $\mathbb F_2[x]$, and write

$$y=x(x+1),\qquad z=1+y=x^2+x+1. \tag{1}$$

For a nonzero $F(y)\in\mathbb F_2[y]$, substitution into $\mathbb F_2[x]$ gives

$$v_x(F(y))=v_{x+1}(F(y))=v_y(F), \qquad \operatorname{odd}_x(F(y)) =\frac{F(y)}{y^{v_y(F)}}. \tag{2}$$

Indeed, after extracting $y^{v_y(F)}$, the remaining factor has constant term $1$, and therefore evaluates to $1$ at both $x=0$ and $x=1$. In particular, the entire odd trajectory starting from any element of $\mathbb F_2[y]$ remains in this invariant subring, where its accelerated transition is

$$\mathcal T(Q)=\operatorname{odd}_y(zQ+1), \qquad Q(0)=1. \tag{3}$$

For every integer $n\geq1$, put

$$a=2^{v_2(n)},\qquad n=au\ \ (u\text{ odd}), \qquad G_n(y)=\frac{z^n+1}{y^a}. \tag{4}$$

Since $z^a=1+y^a$ in characteristic two, the numerator in (4) has exact $y$-adic valuation $a$. Thus $G_n(0)=1$, and $G_n$ is precisely the first odd polynomial associated with the starting polynomial $z^n+1$. If $u=1$, then $G_n=1$ immediately.

Suppose henceforth that $u>1$, and define

$$b=2^{v_2(u-1)},\qquad \delta=a(b-1),\qquad n'=n+\delta. \tag{5}$$

Here $b\geq2$. Writing $u=1+bc$, where $c$ is odd, and putting $w=y^a$, we obtain

$$G_n+1 =\frac{(1+w)^u+1+w}{w} =\frac{(1+w)\bigl((1+w^b)^c+1\bigr)}{w}. \tag{6}$$

The bracketed factor has exact $w$-adic valuation $b$, because $c$ is odd. Consequently,

$$v_y(G_n+1)=a(b-1)=\delta. \tag{7}$$

Introduce the unaccelerated affine operator

$$L(Q)=\frac{zQ+1}{y}. \tag{8}$$

A direct induction, using $z=1+y$, gives the exact iterate formula

$$L^t(Q)=1+\frac{z^t(Q+1)}{y^t} \qquad(0\leq t\leq v_y(Q+1)). \tag{9}$$

For $0\leq t<\delta$, equation (7) shows that $L^t(G_n)$ is a polynomial with constant term $1$. Therefore the first $\delta-1$ accelerated transitions remove exactly one power of $y$, and the $\delta$-th removes the entire remaining $y$-power. Hence

$$\mathcal T^t(G_n) =1+\frac{z^t(G_n+1)}{y^t} \quad(0\leq t<\delta), \qquad \mathcal T^{\delta}(G_n) =\operatorname{odd}_y\bigl(L^{\delta}(G_n)\bigr). \tag{10}$$

Now $a+\delta=ab$, and both $a$ and $ab$ are powers of two. Therefore $z^a=1+y^a$ and $z^{ab}=1+y^{ab}$. Substituting (4) into (9) yields

$$\begin{aligned} L^{\delta}(G_n) &=\frac{y^{ab}+z^{\delta}(z^n+1+y^a)}{y^{ab}}\\ &=\frac{y^{ab}+z^{n'}+z^{\delta+a}}{y^{ab}}\\ &=\frac{y^{ab}+z^{n'}+z^{ab}}{y^{ab}} =\frac{z^{n'}+1}{y^{ab}}. \end{aligned} \tag{11}$$

Moreover,

$$n'=a(u+b-1)=ab(c+1), \qquad a'=2^{v_2(n')}\geq 2ab. \tag{12}$$

Taking the odd part of (11) consequently proves the exact phase-transition theorem

$$\boxed{\ \mathcal T^{\delta}(G_n)=G_{n'}, \qquad \delta=n'-n.\ } \tag{13}$$

Let $N=2^{\lceil\log_2 n\rceil}$. If $n$ is not a power of two, write $N=aK$, where $K$ is a power of two and $u<K$. Since $u-1=bc$, with $c$ odd, and $b\mid K$, we have

$$c\leq\frac Kb-1, \qquad n'=ab(c+1)\leq aK=N. \tag{14}$$

Thus each phase strictly increases $n$, never passes $N$, and strictly increases its $2$-adic valuation by (12). Iterating (13) must therefore reach a power of two, necessarily $N$. If

$$n=n_0<n_1<\cdots<n_s=N, \qquad \delta_i=n_{i+1}-n_i, \tag{15}$$

then the number of accelerated odd transitions telescopes:

$$\sum_{i=0}^{s-1}\delta_i=N-n. \tag{16}$$

The initial odd polynomial is included in the odd sequence, and $G_N=1$ is its final term. Therefore the exact odd-sequence length is

$$\boxed{\ r_{z^n+1}=2^{\lceil\log_2 n\rceil}-n+1 \qquad(n\geq1).\ } \tag{17}$$

The argument also determines the entire degree profile. Within the $i$-th phase, all $\delta_i$ odd polynomials preceding the next phase have the same $x$-degree, namely

$$2\bigl(n_i-2^{v_2(n_i)}\bigr), \tag{18}$$

because (10) preserves $y$-degree. The sequence ends with the single degree $0$. Its successive $x$- and $(x+1)$-valuations coincide; within a phase they equal $1$ for the first $\delta_i-1$ transitions, and the final transition has common valuation

$$1+2^{v_2(n_{i+1})} -2^{v_2(n_i)}\,2^{v_2(n_i/2^{v_2(n_i)}-1)}. \tag{19}$$

Finally, under the precise hypotheses of Conjecture 3.1, take $n=2^r-j$, with $r\geq1$ and $0\leq j\leq2^{r-1}-1$. Then $2^{\lceil\log_2 n\rceil}=2^r$, so (17) gives

$$\boxed{\ r_{(x^2+x+1)^{2^r-j}+1}=j+1.\ } \tag{20}$$

This proves the published conjecture for every admissible pair $(r,j)$, and the explicit phase and degree descriptions give the full orbit rather than only its stopping time.

Source: Luis H. Gallardo and Olivier Rahavandrainy, A variant of Collatz's conjecture over binary polynomials, Revista de la Unión Matemática Argentina 69 (2026), 295–302, Conjecture 3.1.