On short cycles of Newton's method for root finding in characteristic $2$

Question

While experimenting with Newton's method for root finding $x \mapsto x-\frac{f(x)}{f'(x)}$ in positive characteristic, we observed that in the oddest characteristic $2$ there are always short cycles.

Let $K=\mathbb{F}_{2^k}$ and $f \in K[x]$.

Define the iterates of Newton's maps $g_0=x_0 \in K$ and $g_{n+1}=g_n-\frac{f(g_n)}{f'(g_n)}$ assuming that there is no zero division in $f'$.

Let $N(k,f,x_0)$ be the smallest integer such that $g_N=g_{2N}$.

We didn't find roots of $f$, but got very short cycles with small $N$.

Q1 Is $N(k,f,x_0)$ always $O(k \deg(f))$?

Q2 Are there short cycles $o(\sqrt{q})$ in other characterstics?

---

Comment asked do we really mean cycles of $O(\log 2^k)$.

Yes, we really mean cycles of $O(\log 2^k)$ or more precisely $O(k \deg(f))$.

We tested tens of $k \in [100,1000]$ and the cycles are short.

Here is sage code which you can run in a browser

""" Period of the map x -> x-f(x)/f'(x) over GF(2^k) Author Georgi Guninski 2025-06-15 """ k=541;K.<w>=GF(2^k) #w is generator name Kx.<x>=K[] #f=x*(x+w)*(x+w^2) f=Kx.random_element(degree=3) fd=f.derivative() def F(x): return x-f(x)/fd(x) def period1(x0): a,b=x0,x0 n=0 while True: n=n+1 a=F(a) b=F(F(b)) if a==b: return n x0=K.random_element() N=period1(x0) print("N=",N) 

Answer 1

The answer to Q1 is yes assuming $f$ has degree at most $3$, as we will show using the following proposition.

Proposition: Fix a prime power $q$ and a natural number $k$, let $a,b,c,d\in\mathbb{F}_{q^k}$ with $ad-bc\neq 0$, and set $$\phi(x):=\frac{ax^q+b}{cx^q+d}.$$ (Say $\phi(x)=\infty$ if $cx^q+d=0$, and $\phi(\infty)=\frac{a}{c}$.) Then there exists $1\leq r\leq q+1$ such that $\phi^{rk}(x)=x$ for all $x\in\mathbb{F}_{q^k}$.

To apply this, suppose $q=2$ and $f(x)=ax^3+bx^2+cx+d$ for some $a,b,c,d\in\mathbb{F}_{2^k}$. then $f'(x)=ax^2+c$, and $$x-\frac{f(x)}{f'(x)}=\frac{(ax^3+cx)-(ax^3+bx^2+cx+d)}{ax^2+c}=\frac{bx^2+d}{ax^2+c}.$$ If $bc-ad=0$ then every $x$ maps to the same constant value in one step, so we only need to consider the case $bc-ad\neq 0$; then the proposition implies that regardless of starting point, the cycle length is at most $3k$.

On the other hand, if we take $q>2$, or if we keep $q=2$ but take $f$ with degree greater than $3$, the Newton method map no longer has this structure, and so the cycles should typically be significantly longer; in other words, I would suspect that the answer to Q1 is no if we take degree greater than 3, and the answer to Q2 is also likely no (or rather, short cycles may exist, but not from most starting points). The only reason we see short cycles in the case $q=2$ and degree at most $3$ is because the Newton method map happens to take a very special form.

---

Now let's prove the proposition. To do this, we note that the general linear group $\text{GL}_2(\mathbb{F}_{q^k})$ acts on the projective line $\mathbb{P}^1(\mathbb{F}_{q^k})$ by Mobius transformations: if we take $T=\begin{pmatrix}a&b\\c&d\end{pmatrix}$, then $T\cdot x=\frac{ax+b}{cx+d}$. So we can rewrite $\phi(x)=T\cdot \sigma(x)$, where $\sigma:\mathbb{F}_{q^k}\to\mathbb{F}_{q^k}$ is the Frobenius automorphism $x\mapsto x^q$. Note that $\sigma$ also acts on $\text{GL}_2(\mathbb{F}_{q^k})$ by raising each entry to the power of $q$, and by properties of field automorphisms we have \begin{align*} \phi^{rk}(x)&=(T\circ \sigma\circ T\circ \sigma\circ\cdots\circ T\circ\sigma)(x)\\ &=T\sigma(T)\sigma^2(T)\cdots\sigma^{rk-1}(T)\cdot\sigma^{rk}(x). \end{align*} Since $\sigma^k$ is the identity, we can rewrite this as $$\phi^{rk}(x)=\big(T\sigma(T)\cdots \sigma^{k-1}(T)\big)^r\cdot x.$$ Let $A:=T\sigma(T)\cdots \sigma^{k-1}(T)$. Note that $A$ satisfies the identity $T\sigma(A)T^{-1}=A$, so the characteristic polynomial of $A$ is fixed by $\sigma$ and is therefore defined over $\mathbb{F}_q$. This implies that $A$ is conjugate to an element in $\text{GL}(\mathbb{F}_q)$, namely, its rational canonical form $C$. It isn't hard to show that every element of the projective general linear group $\text{PGL}_2(\mathbb{F}_q)$ has order at most $q+1$ (for instance by considering all possible Jordan normal forms), so there exists $1\leq r\leq q+1$ such that $C^r=cI$ for some $c\in\mathbb{F}_q^\times$. Since $cI$ is fixed by conjugation, this implies $A^r=cI$ as well, and hence $\phi^{rk}(x)=(cI)\cdot x$. But scalar matrices act trivially, and so $\phi^{rk}(x)=x$ as desired.