6 Collatz tiles

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+1$ problem, the $3x+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,\dots\}$ be the set of natural numbers and $\N^+ = \{1,2,\dots\}$. Define the Collatz map $T: \N \to \N$ by $T(x) = \frac{x}{2}$ if $x$ is even and $T(x) = \frac{3x+1}{2}$ if $x$ is odd. The Collatz sequence of $x\in\N$ is produced by iterating $T$ starting from $x$, i.e. it is the sequence $u$ defined by $u_0 = x$ and $u_{n+1} = T(u_n)$ for $n \in \N$.

Collatz conjecture. For all $x \in \N^+$, the Collatz sequence of $x$ eventually reaches $1$.

Example. For instance, iterating $T$ from $x=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 $T$ in $\N^+$ is $\{1,2\}$.

• No divergent orbits. There are no $x\in\N$ such that $\text{lim}_{n \to \infty} T^n(x) = + \infty$.

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:

For instance, considering tile 4, we have:

We also have:

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

Chinese Remainder Theorem (special case). Let $0 \leq s < 2$ and $0 \leq e < 3$, there is unique $0 \leq x < 6$ such that $x = s \text{ mod } 2$ and $y = e \text{ mod } 3$.

For instance, in the case of tile 4, $s = 0 = 4 \text{ mod } 2$ and $e = 1 = 4 \text{ mod } 3$, which means that $\text{CRT}_{2,3}(0,1) = 4$.

Remark. Using the Chinese Remainder Theorem, similar tile sets can be created for any pairs of coprimes. The tiles can also be generalised beyond pairs by going to arbitrary dimension instead of 2D and they can also be generalised beyond coprimes [3].

Rectangular tilings

Tiling. A tiling allocates one of our 6 tiles (assuming we have infinite supply of them) or none of them to each position of the plane such that adjacent tiles have the same color on their shared edge.

Before going to Collatz, in order to get more familiar with the tiles, we’ll feature our first result which is that the arithmetical properties that are true at the scale of one tile propagate to rectangular tilings in an elegant way, involving base 2, 3 and 6. Consider a rectangular tiling:

We read the north and south sides of the rectangle in binary (using the binary-labelled north/south edges of the tiles) and the east and west (using the ternary-labelled east/west edges of the tiles) in ternary. Here for instance we have $\text{north} = 11000_2 = 24$ and $\text{west} = 202_3 = 20$.

Then, in general we get Corollary 1.16, p.24 in the thesis:

With $h$ and $w$ the height and width of the rectangle.

Here this gives:

Similarly to before, the rectangle also solves the Chinese Remainder Theorem but now in the case $2^h \times 3^w$. Here for instance, $662$ is the only number less than $2^5 3^3 = 864$ such that $662 \text{ mod } 2^5 = \text{south} = 22$ and $662 \text{ mod } 3^3 = \text{east} = 14$.

There are two interesting special cases to note:

• Squares: when $h=w$
• Base conversion rectangles: when $\text{north} = \text{west} = 0$

Squares. In the special case of a $c \times c$ square, the south-east going diagonal (in brown below) reads in base 6:

Here, the south-east going diagonal (in brown) is $122_6 = 50$.

In general, we get:

Base conversion rectangles. If $\text{north} = \text{west} = 0$, by the above we have $\text{east} = \text{south}$ but $\text{east}$ is in base 3 and $\text{south}$ in base 2. Hence the rectangle performs base conversion from base 3 to 2. For instance:

Here we get $23 = 212_3 = 10111_2$. If we extend this rectangle to a $5\times5$ square, putting two leading $0$s on the east, we can apply our result for squares and we read $23 = 212_3 = 10111_2 = 35_6$ on the south-east diagonal. We got base conversion between bases 3, 2 and 6.

Rectangles are base-$2^w 3^h$ digits. We’ve seen how individual tiles act like base-6 digits when read on south-east going diagonals. In a similar way, a $w \times h$ rectangle acts like a base-$2^w 3^h$ digit: in a tiling, changing scale changes the base in which we can read numbers.

Collatz tilings

Back to Collatz: we are going to show how to assemble Collatz sequences with our tiles. But first we need to talk about Collatz parity vectors, a concept which has been central to the study of the Collatz problem [8–10].

Collatz parity vectors. The parity vector of a Collatz sequence gives the parity of each successive iterate. For instance, the parity vector of the Collatz sequence 45, 68, 34, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 2, 1, 2, 1, … is 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, …

We are going to encode a parity vector as a valued path in 2D. A valued path is a sequence of vectors in $\Z^2$ where each vector is associated to an integer. Here’s how we do it:

• A 0 in the parity vector is encoded by
• A 1 in the parity vector is encoded by

This encoding may feel a bit had hoc / arbitrary at first, please refer to Section 1.3.1 in the thesis for more context.

Then, for instance, the parity vector 1, 0, 0, 1, 0, 1 is encoded by the valued path:

Then, place tile 4 on and horizontal edge 0 on , we get:

Now, because each of our 6 tiles is uniquely defined by its (south,east) corner, there is a unique reconstruction north-west to this path:

We show in the thesis, Corollary 1.36 p.32, that this reconstruction gives $\alpha$ on the north in binary and $\beta$ on the west in ternary such that $\beta = T^n(\alpha)$ with $n$ the size of the parity vector. Here, our parity vector is of size 6 and we get:

Indeed, iterating Collatz from 45 gives: 45, 68, 34, 17, 26, 13, 20. We have $20 = T^6(45)$. Note that the parity vector of this sequence (excluding the last term) is indeed 1, 0, 0, 1, 0, 1 which we started with. Also note that there is one row in the triangular assembly per 1 entry (i.e. odd iterate) in the parity vector.

With a bit of practice, in the above triangular assembly, one can read each of the 7 iterates: they are given in a mixed base system mixing base 2 and 3. For instance, iterate 13 is given by starting from the top left corner, taking ternary digits 2 and 0 down and then binary digit 1 horizontally. Indeed, $13 = (2\times 3 + 0)\times 2 + 1$.

The tiles give a geometric and visual proof of the known fact that there is a 1-1 correspondence between parity vectors of size $n$ and binary Collatz inputs of size $n$ (i.e. Collatz inputs smaller than $2^n$) [8, 9] – the above, with the uniqueness of reconstruction of the triangular assembly, gives the surjectivity of the mapping from inputs of size $n$ to parity vectors of size $n$ (every parity vector is feasible), injectivity comes by cardinality.

Hence, through its parity vector, any Collatz sequence can be assembled using the 6 Collatz tiles. Here’s a bigger example featuring $1622 = T^{18}(64749)$:

Figure 2. Collatz tiling representing $1622 = T^{18}(64749)$ with parity vector 1,0,0,1,0,1,1,0,0,0,0,1,0,1,0,1,0,1 given in blue. $64749 = 1111110011101101_2$ is given in binary on the north side of the assembly and $1622 = 2020002_3$ is given in ternary on the west side of the assembly.

Remark. In the thesis (Figure 1.17 p.36), we show how to assemble Collatz sequences directly from their input (e.g. 64749 in Figure 2) rather than from their parity vector, with the use of two additional tiles.

Collatz cycles

Let’s use the Collatz tiles to think about Collatz cycles.

As seen in the introduction of this article, the weak Collatz conjecture states that 1,2,1,2,… is the only Collatz cycle in $\N^+$. Let’s visualise these cycles with Collatz tilings, using their parity vectors which are 1,0,1,0,… and 0,1,0,1,… respectively:

The geometric question then becomes: why only those very specific shapes of parity vectors (alternating and ) give us the same number on the north and west of the assembly?

If we take an arbitrary parity vector, such as 1,0,0,1,0,1 which is geometrically encoded by , we can force a Collatz cycle to appear by repeating it infinitely often to the right and to the left (or equivalently by working on a slanted torus):

The tiling to the north-west of the parity vector is unique:

By construction, the binary row at each repetition of the parity vector is the same (highlighted in yellow above), and must be eventually repeating (as any row in the tiling) – see Theorem 1.58 p.44 in the thesis. However, by the weak Collatz conjecture, if our parity vector is not trivial (i.e. not 0,1,0… or 1,0,1…) then that row cannot encode a positive integer, i.e. the yellow row cannot start by infinitely many binary 0s.

Binary numbers with infinitely many bits on the most significant sides are known as 2-adic integers in mathematics and their set is denoted $\Z_2$. See Appendix A of the thesis which gives a survival guides to 2-adic integers. And it happens that, eventually repeating 2-adic integers exactly correspond to rational numbers with odd denominator. Furthermore, running Collatz on a 2-adic rational is simple: parity is defined as parity of the numerator and then we apply $T$ using standard arithmetic on rationals.

Lagarias’ periodicity conjecture [7]. Note that $\Z_2$ contains $\N$ (strings starting by $0^\infty$) and $\Z \setminus \N$ (strings starting by $1^\infty$). Hence, $\Z_2$ provides a unified framework for thinking about Collatz beyond the natural numbers. For instance, it allows to think about the 3 known negative Collatz cycles: the cycles of $-1$, $-5$ and $-17$. Generalising the nondivergence conjecture to $\Z_2$ is known as Lagarias’ periodicity conjecture [7] and says that: “The Collatz sequence of an eventually periodic 2-adic integer (i.e. a rational with odd denominator) is eventually periodic.”.

Coming back to the above tiling construction, we now know that the yellow line highlights a 2-adic rational number! In our particular case illustrated above, this 2-adic rational is:

${\small(011001111100100010100110000011011101)^* 101} = \frac{65}{37}$

${\scriptsize(011001111100100010100110000011011101)^* 101}\\ = \frac{65}{37}$

The period 011001111100100010100110000011011101 is so long that we do not see it completely yet, let alone repeating, at the scale of the above tiling.

Illustrating Lagarias’ periodicity conjecture, we get the Collatz cycle of $\frac{65}{37}$ which is: $\frac{65}{37}, \frac{116}{37}, \frac{58}{37}, \frac{29}{37}, \frac{62}{37}, \frac{31}{37}, \frac{65}{37}$. As mentioned above, $T$ was applied at each step taking the parity of the numerator for knowing which of $\frac{x}{2}$ or $\frac{3x+1}{2}$ to apply. As we expect, each row of the above tiling gives the 2-adic expansion of these rationals. Note that they follow the parities (given by the numerators) 1,0,0,1,0,1 as prescribed by the parity vector.

Hence, a parity vector naturally yields the 2-adic rational that cycles under Collatz following the parities that it prescribed. Similarly, we could have read expansions vertically instead of vertically and would have got the 3-adic expansion of that rational, or its 6-adic expansion on south-east going diagonals. This property of parity vectors was known [11] but the tiles give a natural visualisation of this phenomenon.

Geometrically, it is quite mesmerizing that it is so hard to prove, in general, that as soon as we deviate from the simple staircase geometry of the trivial cycle’s parity vector we never get integers in the reconstructed infinite tiling. The mystery remains!

Conclusion

We gave an overview of the arithmetical tiling framework that we introduced in our PhD thesis for assembling Collatz sequences.

We believe that this framework provides a base camp for reasoning about the Collatz process symbolically in base 2, 3, 6 and beyond.

For going further, in Chapter 1 of the thesis, you will find:

• The formal presentation of the theory outlined in this article
• Application of this framework to the complexity of Collatz prediction (Section 1.4), Collatz cycles (Section 1.5) and, Collatz ancestors (Section 1.6)
• Applications of the 6 tiles to two other known number-theoretical open problems: Erdős’ conjecture on powers of two (Figure 2.1) and Mahler’s 3/2 problem (Appendix B)

References