🔢 mathematics

Determinants of modular Collatz graphs and variants

This paper determines the determinants of modular Collatz graphs and the modular Conway amusical permutation graph while describing associated number theoretic properties.

Original authors: Achilleas Karras, Benne de Weger

Published 2026-01-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Achilleas Karras, Benne de Weger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of Musical Chairs with Numbers

Imagine a giant game of musical chairs, but instead of people, we have numbers, and instead of music, we have a set of strict rules for moving them around.

The authors of this paper are studying two famous number games:

The Collatz Game: If a number is even, divide it by 2. If it's odd, multiply by 3 and add 1. (The famous "3n + 1" problem).
Conway's Amusical Game: A slightly different set of rules involving dividing by 2, 4, or 3 depending on the number's shape.

Usually, mathematicians ask: "If I keep playing this game, will the number eventually get stuck in a loop or fly off to infinity?" That is the famous Collatz Conjecture, which nobody has solved yet.

This paper does not try to solve that mystery. Instead, the authors ask a different question: "What happens if we play this game inside a small, closed room with a fixed number of seats (let's say $N$ seats)?"

The "Room" (Modular Arithmetic)

Imagine you have a clock with $N$ hours. When you add or multiply numbers, if you go past the last hour, you wrap around to the beginning. This is called "working modulo $N$ ."

The authors built a map (a graph) showing how every number in this room moves to another number based on the game's rules.

The Map: Every number is a dot. An arrow points from one dot to the next number it becomes.
The Matrix: They turned this map into a giant spreadsheet (a matrix) where they wrote down 1s, 2s, or 0s to show how the numbers connect.

The Mystery: The "Determinant"

In math, every spreadsheet has a single special number attached to it called a determinant. You can think of this determinant as a "fingerprint" or a "score" for the whole map.

The Problem: When the authors calculated this score for different room sizes ( $N$ ), the results looked chaotic. Sometimes the score was zero. Sometimes it was a tiny number. Sometimes, for very specific room sizes, the score was a massive number (like $2^{100,000}$ ).
The Analogy: Imagine rolling a die. Most of the time, you get a 1, 2, 3, 4, 5, or 6. But occasionally, you roll a die and it explodes into a mountain of gold coins. The authors wanted to know: Why does the mountain of gold appear only on certain days?

The Discovery: The "Cycle" Secret

The authors found that the "score" (the determinant) depends entirely on how the numbers move in loops (cycles).

The Loop Detective: They realized that the numbers in the room don't just wander randomly; they get trapped in loops. For example, 1 might go to 2, 2 to 4, and 4 back to 1. That's a loop of length 3.
The Odd vs. Even Rule: They discovered a simple rule:
- If the loops in the room have even lengths, the score is Zero. The map is "broken" or "flat."
- If the loops have odd lengths, the score is Non-Zero.
The Size of the Score: When the score is not zero, its size depends on how many loops there are and how long they are.
- The "score" is basically a power of 2 (like $2^1, 2^2, 2^{100}$ ).
- The exponent (the power) is calculated by adding up the lengths of all the loops in a very specific way.

The "Why" of the Chaos:
The reason the scores looked "erratic" before is that the length of these loops changes unpredictably as you change the room size ( $N$ ).

If the room size $N$ is a prime number where the number 3 (in the Collatz game) takes a long time to return to the start, the loops are long, and the score is small.
If the room size $N$ is a prime where 3 returns to the start very quickly, the loops are short, and the score explodes into a massive number.

The "Magic" Formula

The authors wrote down a formula that predicts the score perfectly.

Step 1: Check the room size $N$ .
Step 2: Look at the "loops" the numbers make.
Step 3: If any loop is "even" (in a specific mathematical sense), the score is 0.
Step 4: If all loops are "odd," the score is $2^{\text{something}}$ . The "something" is the total number of loops you can find.

They also applied this same logic to Conway's game, finding a similar pattern, though the math was slightly more complex because Conway's game uses three different rules instead of two.

What This Means (and What It Doesn't)

What it DOES:

It explains why the "scores" of these graphs look so random. They aren't random; they are strictly determined by the hidden loops inside the number system.
It provides a way to calculate these massive numbers instantly without doing billions of calculations.
It generalizes the rules to other types of number games (like $pn + q$).

What it DOES NOT:

The authors explicitly state that this does not solve the Collatz Conjecture. Knowing the score of the "room" doesn't tell us what happens when the room is infinitely large (which is the real Collatz problem).
It doesn't predict future events or have medical applications. It is purely a mathematical discovery about the structure of numbers.

Summary Analogy

Imagine you are a tour guide in a city with $N$ streets. You have a rule: "Turn left if the street number is even, turn right if it's odd."

Sometimes, if you follow the rules, you get stuck in a small circle.
Sometimes, you get stuck in a huge circle.
The authors found that if you count how many circles exist and how big they are, you can calculate a "City Score."
If the city has any "even-sized" circles, the score is zero (the city is boring).
If all circles are "odd-sized," the score is a huge number, and the size of that number tells you exactly how many circles there are.

They figured out the secret code to calculate this score for any city size, explaining the wild fluctuations they saw in their data.

Technical Summary: Determinants of Modular Collatz Graphs and Variants

Problem Statement
The paper investigates the structural properties of finite directed graphs representing the action of the Collatz $3n+1$ function and Conway's "amusical" permutation function on congruence classes of integers modulo $N$ . Specifically, the authors focus on the adjacency matrices of these modular graphs, denoted as $C_N$ for the Collatz case and $M_N$ for the Conway case. While the graphs exhibit a regular structure (e.g., specific outdegrees), their determinants display seemingly erratic behavior as the modulus $N$ varies. The primary objective is to derive explicit formulas for these determinants and explain the observed patterns using number-theoretic properties, specifically multiplicative orders modulo divisors of $N$ .

Methodology
The authors employ a combination of experimental computation, graph theory, and algebraic number theory.

Experimental Analysis: Initial computations of $\det(C_N)$ for primes $N \le 300,000$ revealed that non-zero determinants are powers of 2 (with a sign), often appearing large when $N$ is a divisor of $3^k - 1$ .
Graph Decomposition: The modular graphs are analyzed as unions of edges induced by specific permutations. For the Collatz function, the edges correspond to permutations $\pi_2(n) \equiv 2^{-1}n$ and $\pi_3(n) \equiv 2^{-1}(3n+1)$ .
Permutation Cycle Analysis: The core theoretical tool is the decomposition of the composite permutation $\rho_0 = \pi_3 \pi_2^{-1}$ into disjoint cycles. The authors utilize a general theorem regarding the determinant of the adjacency matrix of a graph formed by two permutations, relating the determinant to the cycle structure of their composition.
Spectral Analysis: An alternative proof approach involves transforming the adjacency matrix into the form $I + X$ , where $X$ is a permutation matrix. The spectrum of $X$ is determined by the cycle lengths of the underlying permutation, allowing the determinant to be calculated as a product of eigenvalues.
Generalization: The methods are extended to the generalized $pn+q$ function and Conway's three-rule permutation, utilizing Discrete Fourier transforms and properties of Jacobi symbols to determine signs and cycle structures.

Key Contributions and Results

Collatz Graphs ( $C_N$ ):
- Even Moduli: It is proven that for even $N$ , $\det(C_N) = 0$ . The rank of the matrix is $N/2$ , and the characteristic polynomial satisfies $P_N(x) = x^{N/2} P_{N/2}(x)$ .
- Odd Moduli: For odd $N$ , the determinant is non-zero if and only if the multiplicative order of 3 modulo every prime divisor of $N$ is odd.
- Explicit Formula: Let $N = 3^h N_0$ where $3 \nmid N_0$ . Define $K_N = \sum_{d|N_0} \frac{\phi(d)}{\text{ord}_d(3)}$ . Then:
  $\det(C_N) = \begin{cases} 0 & \text{if } \exists p|N_0 \text{ s.t. } \text{ord}_p(3) \text{ is even} \\ 2^{K_N} & \text{if } \forall p|N_0, \text{ord}_p(3) \text{ is odd and } N \equiv \pm 1 \pmod 8 \\ -2^{K_N} & \text{if } \forall p|N_0, \text{ord}_p(3) \text{ is odd and } N \equiv \pm 3 \pmod 8 \end{cases}$
- This formula explains the "erratic" behavior: large determinants occur when $N$ divides $3^k-1$ for small $k$ , making the multiplicative orders small and $K_N$ large.
- Strong Connectivity: The modular Collatz graphs are proven to be strongly connected for all $N$ .
Conway's Amusical Permutation ( $M_N$ ):
- The graph is defined by three rules based on $n \pmod 4$ .
- Even/Divisible by 3: $\det(M_N) = 0$ if $N$ is even or divisible by 3.
- Explicit Formula: For $N$ coprime to 6, let $k_d = \text{ord}_d(2)$ . Define $K_N = \sum_{d|N, d>1} \frac{\phi(d)}{k_d}$ . Then:
  $\det(M_N) = \begin{cases} 0 & \text{if } \exists p|N \text{ s.t. } \text{ord}_p(2) \text{ is even} \\ 3 \cdot 2^{K_N} & \text{if } \forall p|N, \text{ord}_p(2) \text{ is odd and } N \equiv \pm 1, \pm 5 \pmod{24} \\ -3 \cdot 2^{K_N} & \text{if } \forall p|N, \text{ord}_p(2) \text{ is odd and } N \equiv \pm 7, \pm 11 \pmod{24} \end{cases}$
- Strong Connectivity: Modular Conway graphs are also proven to be strongly connected.
Generalizations:
- The results are generalized to the $pn+q$ function (for odd $p, q$ coprime to $N$ ), showing that the determinant depends on the multiplicative order of $p$ modulo divisors of $N$ , and is independent of $q$ (provided $\gcd(N, q)=1$ ).

Significance and Limitations
The authors state that their results provide a complete explanation for the observed behavior of the determinants of modular Collatz and Conway graphs, linking the erratic numerical values directly to the multiplicative orders of the defining parameters (3 for Collatz, 2 for Conway) modulo the divisors of the modulus.

However, the paper explicitly notes a limitation regarding the broader context of the Collatz conjecture. The authors state: "We think that our results have some interest, however, we fail to see how they could help in proving the Collatz conjecture, or to prove similar statements about Conway's amusical permutation." The work is presented as a structural and number-theoretic characterization of the modular graphs rather than a step toward resolving the infinite dynamics of the original functions.