The binary Collatz dynamics of the trinomials $x^n+x+1$: proof of two conjectures of Gallardo and Rahavandrainy

David Niedbala Giraudin

The binary Collatz dynamics of the trinomials $x^n+x+1$ : proof of two conjectures of Gallardo and Rahavandrainy

Primarily AI-generated textHuman understanding: no partsmath.NT — Number Theory

Contributed by David Niedbala Giraudin ↗

Version 1 / Nov 03, 2026 / CC BY 4.0

Abstract

Gallardo and Rahavandrainy studied an analogue of the Collatz map on

\mathbb{F}_2[x]

, in which

x(x+1)

plays the role of

2

and

x^2+x+1

that of

3

: an odd polynomial

A

is sent to the odd part of

1+(x^2+x+1)A

. They proved that every orbit reaches

1

, and conjectured that the orbit of the trinomial

x^n+x+1

has length

2^s+1

, where

s

is the largest integer with

2^{s+1}<n

, and that for

1\le t\le s-1

it contains

2^t

terms of the same degree. We prove both statements for every

n\ge3

. The proof rests on the identity

(x^2+x+1)+x(x+1)=1

: it reduces the dynamics to a map from one plateau to the next, characterises the last plateau of any orbit, and shows that along the orbit of

x^n+x+1

the plateaus start at the

2^j

-th powers of the odd parts of the polynomials

x^m(x^2+x+1)+1

, the index

m

following an explicit binary recursion. We also note that a later restatement of the conjecture, with a non-strict inequality, fails exactly when

n

is a power of

2

. A script checks all the statements numerically.

Provenance statement

The research and the writing were carried out by the author with Claude (Anthropic). The proofs were checked by independent AI reviews and by exact computation. No professional mathematician has reviewed the note yet.

Tools used

Anthropic: Claude Opus

References

L. H. Gallardo and O. Rahavandrainy, On Mersenne polynomials over $\F_2$ , Finite Fields Appl. 59 (2019), 284--296.
L. H. Gallardo and O. Rahavandrainy, On Collatz conjecture for binary polynomials , arXiv:2308.01181, 2023.arXiv
L. H. Gallardo and O. Rahavandrainy, A variant of Collatz's conjecture over binary polynomials , arXiv:2510.07530, 2025; Rev. Un. Mat. Argentina 69 (2026), no. 1, 295--302, doi:10.33044/revuma.5555.arXiv DOI
K. Hicks, G. L. Mullen, J. L. Yucas and R. Zavislak, A polynomial analogue of the $3N+1$ problem , Amer. Math. Monthly 115 (2008), no. 7, 615--622.
D. Nichols, Analogues of the $3x+1$ problem in polynomial rings of characteristic $2$ , Experiment. Math., doi:10.1080/10586458.2016.1227734; arXiv:1610.02545.arXiv DOI

Version history

v1Submitted by David Niedbala GiraudinInitial depositCurrentNov 02, 2026