On the average stopping time of the Collatz map in ${\mathbb{F}}_2[x]$

Abstract

Define the map $T_1$ on ${\mathbb{F}}_2[x]$ by $T_1(f)=\frac{f}{x}$ if $f(0)=0$ and $T_1(f)=\frac{(x+1)f+1}{x}$ if $f(0)=1$. For a non-zero polynomial $f$ let ${\tau }_1(f)$ denote the least natural $k$ number for which $T_1^k(f)=1$. Define the average stopping time to be ${\rho }_1(n)=\frac{{\sum }_{f\in {\mathbb{F}}_2[x],\text{deg}(f)=n}{\tau }_1(f)}{2^n}$. We show that ${\lim }_{n\to \infty }\frac{{\rho }_1(n)}{n}=2$, confirming a conjecture of Alon, Behajaina, and Paran. Furthermore, we give a new proof that ${\tau }_1(f)\in O(\text{deg}(f{)}^{1.5})$ for all $f\in {\mathbb{F}}_2[x]\setminus \{0\}$.

Revised version. Three figures added