13
$\begingroup$

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 fields rings 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:

Github repo

$\endgroup$

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for this very nice proof! After making this, do you think that this property is generic? i.e. that the details of using cosets of <2> and the map x -> 3x+1 aren't so important and that the proof strategy would work for many other cosets / maps, or maybe the result is mostly due to the finite size of the rings? Or do you think that the result is somewhat less generic, and wouldn't be true for other choices of <q>, x -> ax+b? $\endgroup$
    – jwimberley
    Jun 28, 2016 at 15:36
  • 2
    $\begingroup$ The proof immediately extends to $\langle q\rangle$ and $x\mapsto ax+b$ so long as $(abq(q-1),m)=1$. Different ideas might be needed when $(abq(q-1),m)=1$. $\endgroup$ Jun 28, 2016 at 15:51
  • $\begingroup$ At least those with $(q,m)=1$ are trivial, since then $g \mapsto qg$ is not a bijection, so $g \langle q \rangle$ and $h \langle q \rangle$ may share elements and there are no longer well defined cosets. There are at least some interesting cases where $(ab(q-1),m)\neq 1$. For example, for q=3,a=5,b=1, I found no exceptions up to m=10,000, $3 \nmid m$. m=40 is an interesting case - see an image of the graph here. An edge A -> B means there is some g in B such that 3g+1 in A. The graph is not strongly connected. $\endgroup$
    – jwimberley
    Jun 28, 2016 at 18:21
  • $\begingroup$ The one part of your proof that I don't understand is the $3 \mid m$ case. If my code isn't mistaken, or if we don't have somewhat different conventions, these actually fail to be strongly connected. Here is an example for m=15 (q=2,a=3,b=1). This appears to be the case for all the odd multiples of 3. The coset "1", $\{3,6,9,12\}$, is not strongly connected to any other: $\nexists g \ni 3g+1 \cong h \in \{3,6,9,12\}$. $\endgroup$
    – jwimberley
    Jun 28, 2016 at 19:53
  • 1
    $\begingroup$ In case $3\mid m$, I showed that there is a directed path going from any coset of $\langle 2\rangle$ in $(\mathbf{Z}/m\mathbf{Z})^\times$ to any other coset. As noted in your original question, this path might pass through fake cosets, meaning $a\langle 2\rangle$ where $a$ is in $\mathbf{Z}/m\mathbf{Z}$ but not in $(\mathbf{Z}/m\mathbf{Z})^\times$. In the example you mentioned, $\{3,6,9,12\}$ is a fake coset. Anyway, if you specify what step of my proof you don't follow (in case $3\mid m$), I can explain further. $\endgroup$ Jun 28, 2016 at 20:13
5
$\begingroup$

Shifting by $1/2$, one sees that the map $x\mapsto 3x+1$ is conjugate to multiplication by 3. It is periodic with period the multiplicative order of 3. Therefore, strong conjecture cannot hold if this order is strictly less than the number of cosets of $\langle 2\rangle$ --- there are just too many cosets to visit. This presumably explains your counterexamples with "unusually high" number of cosets.

$\endgroup$
1
$\begingroup$

I'm caching in the work I did with the Boost Graph Library to post a few examples as a supplement to the accepted answer. The code is available at this GitHub page. The theorem in the accepted answer shows that for any odd $m$ that is not a multiple of 3, the graph formed of the cosets of $\langle 2 \rangle$ in $\mathbb{Z}/m\mathbb{Z}$ (including ones consisting of by zero-divisors) is strongly connected. One example for $m=8233$ is shown here:

m8233q2a3b1

The node colored red is a "fake" cosets consisting of zero-divisors. In this case each node is connected to every other node, except for the {0} node. This is not always the case. For $m=31$, for example, some nodes are separated by two other nodes:

m31q2a3b1

For $m=127$, two pairs of nodes are separated by three intermediate nodes, though its hard to see:

m127q2b3a1

The theorem in the accepted answer gives an upper bound on these distances related to the order of 3 in $(\mathbb{Z}/m\mathbb{Z})^\times$ and the number of binary digits required to represent every number in the ring.

The following is a good example of a case where $3 \nmid m$. There are two fake cosets $3 \langle 2 \rangle$ and $5 \langle 2 \rangle$, since $(3,15) > 1$ and $(5,15)>1$. In this case the graph isn't strongly connected, but every non-fake node is connected to every other non-fake node, possibly through fake nodes (though I didn't find a small example that required this):

m15q2a3p1

The author of the proof also indicates that the proof extends naturally when replacing $\langle 2 \rangle$ with $\langle q \rangle$ and $3x+1$ with $ax+b$, so long as $(abq(q-1),m)\neq1$, and if I had to guess it still works for $a \mid m$ (following the $3 \mid m$ case above) and its ill-defined when $(q,m) \neq 1$, so the unproven case is $(b(q-1),m) \neq 1$. Numerically, it still seems to hold in such cases. For example, for q=3, a=5, b=1, and m=40, the graph is

m40q3a5b1

Here the fake nodes are very important intermediate nodes.

A much more interesting property would be a well-defined rule to pick a single element of each coset such that the corresponding graph is strongly connected. This would greatly prune the number of edges (allowing only one path out of each coset), and be closer to the spirit of the Collatz conjecture where $3x+1$ is only applied to numbers that aren't divisible by 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.