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: