HEXAGONbeta

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

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

Contributed by David Niedbala Giraudin

Version 2 / Nov 03, 2026 / CC BY 4.0

Abstract

Gallardo and Rahavandrainy studied an analogue of the Collatz map on 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 <= t <= s-1 it contains 2^t terms of the same degree. We prove both statements for every n >= 3. They were proved earlier, with a complete Lean 4 formalization, by W. Choi; the proof given here was obtained independently. 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

  1. W. Choi, Exact lengths and a quadratic bound for a Collatz variant over binary polynomials , preprint, Zenodo, 2026, doi:10.5281/zenodo.23356586; Lean 4 formalization: https://github.com/coo001/binpoly-collatz-lean.DOI
  2. L. H. Gallardo and O. Rahavandrainy, On Mersenne polynomials over $\F_2$ , Finite Fields Appl. 59 (2019), 284--296.
  3. L. H. Gallardo and O. Rahavandrainy, On Collatz conjecture for binary polynomials , arXiv:2308.01181, 2023.arXiv
  4. 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.arXivDOI
  5. K. Hicks, G. L. Mullen, J. L. Yucas and R. Zavislak, A polynomial analogue of the 3N+13N+1 problem , Amer. Math. Monthly 115 (2008), no. 7, 615--622.
  6. D. Nichols, Analogues of the 3x+13x+1 problem in polynomial rings of characteristic 22 , Experiment. Math., doi:10.1080/10586458.2016.1227734; arXiv:1610.02545.arXivDOI

Version history

  1. v1 · 6 pagesSubmitted by David Niedbala GiraudinInitial depositSupersededNov 02, 2026
  2. v2 · 6 pagesSubmitted by David Niedbala GiraudinSubmitted as a new versionCurrentNov 03, 2026