Tristan Stérin | 6 Collatz tiles

6 Collatz tiles

July 3rd 2023

Assembling Collatz sequences using Wang tiles.

This article gives an overview of the first chapter of my PhD thesis which shows how to interpret the Collatz problem in terms of Wang tilings. We only illustrate some results of the thesis in this article, please refer to the thesis for proofs and all the gory details.

Tiling images for this article were generated using the Python library coreli, see Appendix C in the thesis for a manual.

Acknowledgement. I thank Matthew Cook and Damien Woods for their participation to this work. Matthew introduced us to the 6 Collatz tiles and together, we figured out that paths in tilings made of these tiles have arithmetical interpretations. This work can be seen as a generalisation of our previous work with Damien. I also thank Jarkko Kari and Johan Kopra for insightful conversations on this matter.

Introduction

The Collatz problem is known under many names such as: the 3n+13n+13n+1 problem, the 3x+13x+13x+1 problem, Ulam’s conjecture, Thwaites’ conjecture, the Syracuse problem, etc. The essence of the problem seems to trace back to Lathar Collatz’s notebooks from the 1930s and is known to have circulated in mathematical circles in the 1950s [1]. The first printed occurrence of the problem seems to be a 1971 written version of a lecture by H. S. Coxeter [1, 2].

The Collatz problem has been open ever since and is notoriously extremely hard in spite of more than half a century of research [2, 3, 5]. Famously, mathematician Paul Erdős said that “Mathematics is not yet ready for such problems” and, reportedly, he would also have described the problem as “Hopeless. Absolutely hopeless.” [4]. As a warning, the Collatz problem is also given as Problem 2 in Richard Guy’s 1983 paper “Don’t try to solve these problems!” [2].

Here’s how the Collatz problem is defined:

Let N={0,1,2,… }\N = \{0,1,2,\dots\}N={0,1,2,…} be the set of natural numbers and N+={1,2,… }\N^+ = \{1,2,\dots\}N+={1,2,…}. Define the Collatz map T:N→NT: \N \to \NT:N→N by T(x)=x2T(x) = \frac{x}{2}T(x)=2x​ if xxx is even and T(x)=3x+12T(x) = \frac{3x+1}{2}T(x)=23x+1​ if xxx is odd. The Collatz sequence of x∈Nx\in\Nx∈N is produced by iterating TTT starting from xxx, i.e. it is the sequence uuu defined by u0=xu_0 = xu0​=x and un+1=T(un)u_{n+1} = T(u_n)un+1​=T(un​) for n∈Nn \in \Nn∈N.

Collatz conjecture. For all x∈N+x \in \N^+x∈N+, the Collatz sequence of xxx eventually reaches 111.

Example. For instance, iterating TTT from x=45x=45x=45 yields the Collatz sequence 45, 68, 34, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 2, 1, 2, 1, …

The Collatz conjecture can be decomposed into two, seemingly independent conjectures:

No nontrivial cycles. (or weak Collatz conjecture) The only cycle of TTT in N+\N^+N+ is {1,2}\{1,2\}{1,2}.

No divergent orbits. There are no x∈Nx\in\Nx∈N such that limn→∞Tn(x)=+∞\text{lim}_{n \to \infty} T^n(x) = + \inftylimn→∞​Tn(x)=+∞.

In this article we give an overview of how to represent Collatz sequences using a set of 6 Wang tiles . In these tilings, Collatz iterates can be read in infinitely many bases including base 2, 3, 6 and mixed bases. This framework also naturally features 2-adic, 3-adic and 6-adic integers.

We’ll apply this framework to the weak Collatz conjecture (no nontrivial cycles) and see how it transforms it into an elegant geometric tiling problem.

The tiles

Figure 1. The 6 Collatz tiles.

We are considering the set of 6 tiles given in Figure 1. These tiles are Wang tiles, i.e. non-rotable square tiles with colors on their sides. The colors are labelled by 0, 1, or 2: north and south sides of the tiles only use binary colors (0 and 1) while west and east sides use ternary colors (0, 1 and 2). The tiles themselves are labelled from 0 to 5 and we’ll see that they represent base-6 digits.

The tiles are uniquely identified by each one of three corners: (north,east), (south,east) or (south,west). Only the (north,west) corner does not uniquely identify the tiles: for instance, both tiles 4 and 5 have (north,west) = (1,2).

The tiles are governed by the following equations:

name of the tile=3×north+east=2×west+south\begin{aligned}<br>\text{name of the tile} &= 3\times \text{north} + \text{east} \\&= 2\times \text{west} + \text{south}<br>\end{aligned}name of the tile​=3×north+east=2×west+south​

For instance, considering tile 4, we have:

4=3×1+1=2×2+04 = 3\times 1 + 1 = 2\times 2 + 04=3×1+1=2×2+0

We also have:

name of the tile=CRT2,3(south,east)\text{name of the tile} = \text{CRT}_{2,3}(\text{south},\text{east})name of the tile=CRT2,3​(south,east)

Where CRT2,3\text{CRT}_{2,3}CRT2,3​ solves the Chinese Remainder Theorem in the special case of 2×3=62 \times 3 = 62×3=6. By this, we mean the following:

Chinese Remainder Theorem (special case). Let 0≤s20 \leq s 0≤s2 and 0≤e30 \leq e 0≤e3, there is unique 0≤x60 \leq x 0≤x6 such that x=s mod 2x = s \text{ mod } 2x=s mod 2 and y=e mod 3y = e \text{ mod } 3y=e mod 3.

For...