I was wondering what an equivalent of the Collatz conjecture might be for finite fields. In a Collatz sequence a number is moved down within a set $\{2^k n : k \in \mathbb{Z}^* \}$ for some odd $n$ or jumped to another such set via $n \mapsto 3n+1$. The analogy of the sets $\{2^k n \}$ in $F_p$ are the cosets of the cyclic subgroup $\langle 2 \rangle$ of $F_p^\times$ generated by $2$. The analogy of the operation $n \mapsto 3n+1$ would be some operation that maps one such coset to another.
I came up with the following two conjectures, the first and stronger of which I've disproved by a couple of counterexamples and the second and weaker of which I've verified for all primes $p$ and prime powers $p^k$ less than $500,000$. Before going into the details, my question is – are these conjectures:
- a) trivially true or false
- b) proven to be true or false, and if I had used better search keywords I would have found this
- c) interesting and yet to be proven either way
- d) yet to be proven either way, because it is completely uninteresting
Strong conjecture For every prime $p > 2$, the cosets of $\langle 2 \rangle$ in the finite field $F_p^\times$ are traversed (in some order, with repetitions allowed) by a progression $g_{n+1} = 3 g_{n} + 1$.
One subtlety is that the progression can go through the fake ''coset'' $\{0\}$, and then end up in $\langle 2 \rangle$ in the next step. I'm allowing this for now.
Very frequently (a little less than half the time for primes under 40k) the conjecture is trivial because 2 is a generator of $F_p^\times$. A nontrivial example is $p = 8233$, for which one such progression is
$$29, 88, 265, 796, 2389, 7168,…$$
which traverses the four cosets of $F_{8233}^\times / \langle 2 \rangle$ (88 and 265 belong to the same coset, as do 2389 and 7168 which both belong to $\langle 2 \rangle$ itself).
The conjecture is false. Directly testing all primes $p \leq 48871$, I found a handful of exceptions, for $p = 683$, $6553$, $8191$, and $34511$. These appear to be cases where the rank of $F_p^\times/\langle 2 \rangle$ is unusually high: 31, 56, 630, and 58, respectively. Relaxing the conjecture to allow multiple progressions that terminate in $\langle 2 \rangle$ and together cover all the cosets, 8191 appears to remain an exception (barring coding mistakes on my part). I found no connections to $\langle 2 \rangle$ by a progression for two cosets: $1171 \langle 2 \rangle$ and $2775 \langle 2 \rangle$.
In the weaker conjecture the sequence is not required to be a direct progression. Instead there must be a way to traverse the cosets by repeatedly going from some element $g$ in a coset $n \langle 2 \rangle$ to another $3g+1$ in the next coset $n' \langle 2 \rangle$:
Weak conjecture For every prime $p > 2$, consider a directed graph where each node represents the cosets of $g \langle 2 \rangle$ of $\langle 2 \rangle$ in $F_p^\times$ and each pair of nodes corresponding to cosets $A$ and $B$ is connected exactly when there exists some $g \in A$ such that $3g+1 \in B$. The conjecture is that the graph is strongly connected, or that there is a directed path from each coset to $\langle 2 \rangle$.
I've used the graph language mostly because it was convenient and because I think a good implementation in C++ of a check of this conjecture needs to use a graph structure to be efficient.
UPDATES
-
I wrote a method using the Boost Graph Library to test the weak conjecture. The four primes that failed the property in the strong conjecture all pass the property in the weak conjecture. This doesn't appear to be entirely trivial; while the graphs for small primes are often strongly connected, for $p = 8191$ the longest path from a coset to $\langle 2 \rangle$ via the $3n+1$ operation has a path length of 4 (computed using Dijkstra's algorithm).
-
I've tested the weaker conjecture for all primes $p < 100,000$. All have passed, including one monster case for the Mersenne prime $p = 2^{16}+1 = 65537$, for which $F_{65537}^\times/\langle 2 \rangle$ has rank 2048. Like for 8191, many of the shortest paths from the various cosets to $\langle 2 \rangle$ have length 4.
-
The conjecture naturally extends to the finite
fieldsrings corresponding to prime powers $p^k$. So, I've also tested all prime powers $p^k < 100,000$, where $p \neq 2$, and the conjecture holds for their corresponding finite fields as well. -
Amateur mistake: I confused the rings $\mathbb{Z}/p^k \mathbb{Z}$ with the finite fields $F_{p^k}$ – of course $p$ is a zero divisor for each of the former for $k>1$. For the odd primes this doesn't seem to seriously impact meaning of the conjecture, because $2^n g \ncong 0 \mod p^k$ for any n, and I did still verify these cases for $p^k < 100,000$. For that matter I could have checked any odd $n$, and I verified the property for all odd $n < 10,000$.
-
Overnight I updated the upper bounds to $500,000$ for primes powers and $50,000$ for generic odd numbers. A very nice proof has been provided that the conjecture holds for all odd numbers.
CODE
You can find the C++ code I've written to test this here:
Best Answer
Here is a proof of the generalization of your Weak conjecture to the ring $\mathbf{Z}/m\mathbf{Z}$ where $m$ is any odd positive integer. First let me clarify what is being proved. Let $S$ be the subgroup of $(\mathbf{Z}/m\mathbf{Z})^\times$ which is generated by $2$, and consider a directed graph whose vertices are the sets $gS$ with $g\in\mathbf{Z}/m\mathbf{Z}$ (I emphasize that $g$ need not be in $(\mathbf{Z}/m\mathbf{Z})^\times$), and which has a directed edge from $gS$ to $(3g+1)S$ for every $g\in\mathbf{Z}/m\mathbf{Z}$. I will show:
1) If $3\nmid m$ then this directed graph is strongly connected (in the sense that there is a directed path from any vertex to any other vertex).
2) If $3\mid m$ then for any $g,h\in(\mathbf{Z}/m\mathbf{Z})^\times$ there is a directed path from the vertex $gS$ to the vertex $hS$ (although this path might go through vertices of the form $iS$ with $i\notin (\mathbf{Z}/m\mathbf{Z})^\times$).
Both of these are special cases of the Theorem proved below.
Lemma. Let $n$ be a positive integer, and let $M$ be a subset of $\mathbf{Z}/n\mathbf{Z}$ which contains elements $u,v$ for which $u-v\in(\mathbf{Z}/n\mathbf{Z})^\times$. Then, for every sufficiently large positive integer $s$, every element of $\mathbf{Z}/n\mathbf{Z}$ is the sum of exactly $s$ elements of $M$.
Proof. Let $M_r$ be the set of all sums of exactly $r$ elements of $M$, so that $M_1=M$. Pick $u,v\in M_r$ for which $u-v\in(\mathbf{Z}/n\mathbf{Z})^\times$. Plainly $M_{r+1}$ contains $M_r+u$ and $M_r+v$, so that $\#M_{r+1}\ge\#M_r$. If $\#M_{r+1}=\#M_r$ then we must have $M_r+u=M_r+v$, or equivalently $M_r+(u-v)=M_r$. But then $M_r+\ell(u-v)=M_r$ for any positive integer $\ell$, whence $M_r+w=M_r$ for any $w\in\mathbf{Z}/n\mathbf{Z}$, so we must have $M_r=\mathbf{Z}/n\mathbf{Z}$. Thus, for every $r>0$, either $\#M_{r+1}>\#M_r$ or $M_r=\mathbf{Z}/n\mathbf{Z}$. Since $\#M_r\le m$ for every $r$, it follows that there is some $r$ for which $M_r=\mathbf{Z}/n\mathbf{Z}$, whence $M_s=\mathbf{Z}/n\mathbf{Z}$ for every $s\ge r$. This finishes the proof of the Lemma.
Theorem. Write $m=3^kn$ where $k\ge 0$ and $3\nmid n$. Pick any $g,h\in\mathbf{Z}/m\mathbf{Z}$, and suppose that either $k=0$ or $3\nmid h$. Then there is a directed path from $g\langle 2\rangle$ to $h\langle 2\rangle$.
Proof. Apply the Lemma with $M$ being the subgroup of $(\mathbf{Z}/n\mathbf{Z})^\times$ generated by $2$ (and with $u=2$ and $v=1$) to obtain a corresponding $s$. Let $r$ be the order of $3$ in $(\mathbf{Z}/n\mathbf{Z})^\times$. Let $\ell$ be the smallest integer such that $\ell>k/r$. Recall that every element of $U:=(\mathbf{Z}/3^k\mathbf{Z})^\times$ is a power of $2$. Since an element $i\in \mathbf{Z}/3^k\mathbf{Z}$ lies in $U$ if and only if $i+3/2$ lies in $U$, it follows that every element of $U$ can be written as $-3/2+2^t$ for some positive integer $t$. The hypothesis that either $k=0$ or $3\nmid h$ implies that the image of $h$ in $\mathbf{Z}/3^k\mathbf{Z}$ is actually in $U$, so there is some $t>0$ for which $h\equiv -3/2+2^t\pmod{3^k}$. Let $b_0,\dots,b_{s-1}$ be nonnegative integers for which $h-3g+s-2^t\equiv\sum_{i=0}^{s-1} 2^{b_i}\pmod{n}$. Define $$a_0:=t,$$ $$a_i:=0 \,\,\text{if either $0<i<r\ell$ or $r\nmid i$},$$ $$a_{r(\ell+j)}:=b_j \,\,\text{for $0\le j\le s-1$}.$$ Then $$x:=3^{r(\ell+s-1)+1}2^0g+\sum_{i=0}^{r(\ell+s-1)} 3^i 2^{a_i}$$ equals $$3^{r(\ell+s-1)+1}g + \sum_{i=0}^{r(\ell+s-1)} 3^i + \sum_{j=0}^{s-1} 3^{r(\ell+j)} (2^{b_j}-1) + (2^t-1)$$ $$=3^{r(\ell+s-1)+1}g + \frac{3^{r(\ell+s-1)+1}-1}{3-1} + \sum_{j=0}^{s-1} 3^{r(\ell+j)} (2^{b_j}-1) + (2^t-1).$$ Here $x$ is congruent mod $3^k$ to $$-\frac12+(2^t-1)=2^t-\frac32=h.$$ Next, $x$ is congruent mod $n$ to $$3g+\frac{3-1}{3-1}+\sum_{j=0}^{s-1} (2^{b_j}-1) + (2^t-1)= 3g+1+(h-3g+s-2^t)-s+(2^t-1)=h.$$ Therefore $x=h$. An easy induction shows that the union of the sets $v\langle 2\rangle$ for which the vertex $v\langle 2\rangle$ can be reached from $g\langle 2\rangle$ via a directed path of length $z$ is $\{3^z2^{d_z}g +\sum_{i=0}^{z-1} 3^i 2^{d_i}\colon d_i\in\mathbf{Z}\}$. Thus there is a directed path of length $r(\ell+s-1)+1$ from $g\langle 2\rangle$ to $h\langle 2\rangle$. This finishes the proof of the Theorem.