Tristan Stérin

Tristan Stérin

PhD in Computer Science

GitHub Mark Linkedin Logo
I am an entrepreneur, researcher and scientific writer passionate about software, theoretical computer science, and DNA-nanotechnologies.

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

Collatz conjecture. For all xN+x \in \N^+, the Collatz sequence of xx eventually reaches 11.

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

  • No divergent orbits. There are no xNx\in\N such that limnTn(x)=+\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

6 Collatz 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} \text{name of the tile} &= 3\times \text{north} + \text{east} \\&= 2\times \text{west} + \text{south} \end{aligned}

For instance, considering tile 4, we have:

4=3×1+1=2×2+04 = 3\times 1 + 1 = 2\times 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})

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

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

For instance, in the case of tile 4, s=0=4 mod 2s = 0 = 4 \text{ mod } 2 and e=1=4 mod 3e = 1 = 4 \text{ mod } 3, which means that CRT2,3(0,1)=4\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:

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 north=110002=24\text{north} = 11000_2 = 24 and west=2023=20\text{west} = 202_3 = 20.

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

3h×north+east=2w×west+south 3^h\times \text{north} + \text{east} = 2^w\times \text{west} + \text{south}

With hh and ww the height and width of the rectangle.

Here this gives:

33×24+14=25×20+22=662 3^3 \times 24 + 14 = 2^5 \times 20 + 22 = 662

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

There are two interesting special cases to note:

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

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

square tiling

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

In general, we get:

diagonal=3c×north+east=2c×west+south\begin{aligned} \text{diagonal} &= 3^c\times \text{north} + \text{east} \\&= 2^c\times \text{west} + \text{south} \end{aligned}
50=33×1+23=23×6+250 = 3^3 \times 1 + 23 = 2^3 \times 6 + 2

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

base conversion tiling

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

Rectangles are base-2w3h2^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×hw \times h rectangle acts like a base-2w3h2^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 [810].

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 Z2\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 encoding 0
  • A 1 in the parity vector is encoded by encoding 1

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:

encoding of parity vector 1,0,0,1,0,1

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

encoding of parity vector 1,0,0,1,0,1

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:

encoding of parity vector 1,0,0,1,0,1

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 β=Tn(α)\beta = T^n(\alpha) with nn the size of the parity vector. Here, our parity vector is of size 6 and we get:

encoding of parity vector 1,0,0,1,0,1

Indeed, iterating Collatz from 45 gives: 45, 68, 34, 17, 26, 13, 20. We have 20=T6(45)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×3+0)×2+113 = (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 nn and binary Collatz inputs of size nn (i.e. Collatz inputs smaller than 2n2^n) [8, 9] – the above, with the uniqueness of reconstruction of the triangular assembly, gives the surjectivity of the mapping from inputs of size nn to parity vectors of size nn (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=T18(64749)1622 = T^{18}(64749):

encoding of parity vector 1,0,0,1,0,1

Figure 2. Collatz tiling representing 1622=T18(64749)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=1111110011101101264749 = 1111110011101101_2 is given in binary on the north side of the assembly and 1622=202000231622 = 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+\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:

1,2,1,2,1 2,1,2,1,2

The geometric question then becomes: why only those very specific shapes of parity vectors (alternating encoding 1 and encoding 1) 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 path, 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):

repeating parity vector 1,0,0,1,0,1

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

repeating parity vector 1,0,0,1,0,1

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 Z2\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 TT using standard arithmetic on rationals.

Lagarias’ periodicity conjecture [7]. Note that Z2\Z_2 contains N\N (strings starting by 00^\infty) and ZN\Z \setminus \N (strings starting by 11^\infty). Hence, Z2\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-1, 5-5 and 17-17. Generalising the nondivergence conjecture to Z2\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:

(011001111100100010100110000011011101)101=6537{\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 6537\frac{65}{37} which is: 6537,11637,5837,2937,6237,3137,6537\frac{65}{37}, \frac{116}{37}, \frac{58}{37}, \frac{29}{37}, \frac{62}{37}, \frac{31}{37}, \frac{65}{37}. As mentioned above, TT was applied at each step taking the parity of the numerator for knowing which of x2\frac{x}{2} or 3x+12\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 path 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

[1]
Coxeter, H.S.M. 1971. Cyclic sequences and frieze patterns: The Fourth Felix Behrend Memorial Lecture, Vinculum 8.
[2]
Guy, R.K. 1983. Don’t Try to Solve These Problems! The American Mathematical Monthly. 90, 1 (1983), 35–41.
[3]
Kopra, J. 2022. Multiplication cubes and multiplication automata.
[4]
Lagarias, J.C. 2003. The 3x+1 problem: An annotated bibliography (1963–1999) (sorted by author).
[5]
Lagarias, J.C. 2006. The 3x+1 Problem: An Annotated Bibliography, II (2000-2009).
[6]
Lagarias, J.C. 2021. The 3x+1 Problem: An Overview. (2021).
[7]
Lagarias, J.C. 1985. The 3x + 1 Problem and Its Generalizations. The American Mathematical Monthly. 92, 1 (1985), 3–23.
[8]
Lagarias, J.C. 2010. The Ultimate Challenge: The 3x+1 Problem. American Mathematical Society.
[9]
Rozier, O. 2019. Parity Sequences of the 3x+1 Map on the 2-adic Integers and Euclidean Embedding. Integers. 19, (2019), A8.
[10]
Terras, R. 1976. A stopping time problem on the positive integers. Acta Arithmetica. 30, 3 (1976), 241–252.
[11]
Wirsching, G.J. 1998. The dynamical system generated by the 3n + 1 function. Springer.