XOR Triangles

In this post, I’ll explore the math behind one of my Twitter bots, @xorTriangles. This bot was inspired by the MathOverflow question “Number triangle,” asked by user DSM posted in May 2020.

(I gave an overview of my Twitter bots @oeisTriangles in my post “Parity Bitmaps from the OEIS“. And if you want to build your own bot, I showed the steps for building @BotfonsNeedles in parts I, II, and III of my three-part series “A π-estimating Twitter bot”.)

In May 2020, MathOverflow user DSM posted a question “Number triangle” where they asked about the following construction:

Start with a list of \(n\) bits (\(0\)s and \(1\)s), and to get the next row, combine all adjacent pairs via the XOR operation, \(\oplus\). (A mathematician might call this “addition modulo \(2\).”) That is $$\begin{alignat*}{2} 0 \oplus 0 &= 1 \oplus 1 &&= 0 \quad\text{and} \\ 0 \oplus 1 &= 1 \oplus 0 &&= 1.\end{alignat*}$$

For example, starting with the row \(110101\), the resulting triangle is $$1~~~1~~~0~~~1~~~0~~~1\\ 0~~~1~~~1~~~1~~~1\\ 1~~~0~~~0~~~0\\ 1~~~0~~~0\\ 1~~~0\\ 1$$

We’re especially interested in understanding the triangles with rotationally symmetric boundaries (and consequently insides)! OEIS sequence A334556 enumerates all of the rotationally symmetric triangles with a \(1\) in the upper left corner.

@xorTriangles

My Twitter bot @xorTriangles posts these triangles four times a day, alternating between the triangles described above and a “mod \(3\)” analog. If you want to see how it works, you can check it out on Github.

Here is an illustration by Michael De Vlieger that shows many small XOR triangles and which is available on the OEIS.

Mathematica

One way to find a rotationally symmetric XOR triangle is by setting up a system of equations. Using the convention that the top row of the triangle is labeled \(x_0, x_1, \dots, x_n\), we can use the Pascal’s Triangle-like construction to set up a system of linear equations over \(\mathbb{Z}/2\mathbb{Z}\). The solutions of this system of equations are precisely those that correspond to the XOR triangle we care about! This allows us to write down a matrix whose null space is the set of such triangles:

$$\begin{align}x_n &= x_0\\x_{n-1} &= x_0 + x_1\\x_{n-2} &= x_0 + 2x_1 + x_2\\ &\vdots \\ x_k &= \sum_{i=0}^{n-k} \binom{n-k}{i}x_i \\ &\vdots \\ x_0 &= \binom{n}{1}x_0 + \binom{n}{1}x_1 + \dots + \binom{n}{n}x_n\end{align}$$

Using Mathematica to find the null space works like this:

value[i_, j_, n_] := Binomial[i, j] - If[j == n - i, 1, 0];
xorSeedsBasis[n_] := NullSpace[
  Table[value[i, j, n], {i, 0, n}, {j, 0, n}],
  Modulus -> 2
];

Because this is the null space of a \(n+1 \times n+1\) matrix over \(\mathbb{Z}/2\mathbb{Z}\), we know that there must be \(2^M\) rotationally symmetric XOR triangles, where \(M\) is an integer—which isn’t obvious from the original construction!

Related OEIS sequences

If you’re interested in learning more about this construction, reach out to me or take a look at some of these related OEIS sequences:

• A334596: Number rotationally symmetric triangles of size \(n\) with \(1\)s in the corners.
• A334591: Largest triangle of \(0\)s in the XOR triangle generated by the binary expansion of \(n\).
• A334592: Total number of \(0\)s in the XOR triangle generated by the binary expansion of (n).
• A334593: Total number of \(1\)s in the XOR triangle generated by the binary expansion of \(n\).
• A334594: Binary interpretation of the \(k\)-th row of the XOR triangle generated by the binary expansion of \(n\).
• A334930: Numbers that generate rotationally symmetrical XOR-triangles featuring singleton zero bits in a hexagonal arrangement. (from Michael De Vlieger, see his illustration)