peterkagey

I made a video that illustrates a particularly interesting “discrete state random dynamical system,” which was inspired by a Tweet (and a mistake) that I saw.

First, be hypnotized by this video, which I recommend you watch in 4K, and then scroll down to read about the inspiration and the cool math going on under the hood.

Matt Henderson’s tweet

This whole exploration came from a “happy accident” that Matt Henderson made (and corrected) in the Tweets below. Watch the video in the first tweet, which shows an concrete example of the “discrete state random dynamical system” that I mentioned earlier.

Matt’s mistake got me interested! If the centroid and the incenter create such interesting and intricate designs, what about other triangle centers like the circumcenter or the orthocenter? In particular, I was interested in finding examples of interesting triangle centers from Clark Kimberling’s Encyclopedia of Triangle Centers (ETC), which is a database with over 53,000 named triangle centers, including all of those that you have heard about.

Patterns from other triangle centers

Instead of illustrating the results of this process on hexagons as Matt did in his tweet, I’ve done the iterative process on squares. Here are six examples illustrating the patterns for various triangle centers from ETC.

Some basics of triangle centers

In the video at the top, I interpolate between 20 chosen triangle centers in a continuous way so that we can see how the image transforms as we transform the choice of triangle center.

In order to understand what’s going on, you have to understand something about coordinates. We can define a triangle center with a map \(f\colon \mathbb{R}^3 \to \mathbb{R}\) such that \(f(a,b,c)\) is symmetric in \(b\) and \(c\). What we do is take the triangle with vertices \(\vec{v}_1\), \(\vec{v}_2\), and \(\vec{v}_3\), define \(a = |\vec{v}_2 – \vec{v}_3|\), \(b = |\vec{v}_1 – \vec{v}_3|\), and \(c = |\vec{v}_1 – \vec{v}_2|\), and define the midpoint as the weighted average \[\frac{f(a,b,c) \vec{v}_1 + f(b,c,a)\vec{v}_2, + f(c,a,b)\vec{v}_3}{f(a,b,c) + f(b,c,a) + f(c,a,b)}.\] Whenever \(f(a,b,c)\), \(f(b,c,a)\), and \(f(c,a,b)\) are simultaneously positive, this will describe a point inside the triangle. This way of describing points in space is called a “barycentric coordinate system“.

In the table below, I give examples of five triangle centers and their description in barycentric coordinates. In the case of \(X(2)\), the barycentric coodinates say that the centroid is just an honest average of the vertices. In all other cases, the other triangle centers are weighted averages of the vertices.

A curve of triangle centers

The triangle centers in the video are all described by functions of the form \[f(a,b,c) = a^{x_1}(b + c – a)^{x_2} (bc)^{x_3} (b^{x_4} + c^{x_4})^{x_5},\] where \((x_1, x_2, x_3, x_4, x_5) \in \mathbb{R}^5\) and each frame follows a path in \(\mathbb{R}^5\), which intersects a triangle center from ETC for a single frame every ten seconds. In order to get this path in five-dimensional space, the code stitches together twenty piecewise-defined Bézier curves into a differentiable curve that goes through those twenty “anchor points”, as suggested by the following illustration. (Thankfully I could reuse some of the code I wrote for my Twitter bot @BotzierCurves!)

In addition to choosing a slightly different triangle center in each frame, the colors of the points change throughout time as well. For example, in the picture below, the pixel is colored white if the same side is chosen twice in a row, red if the opposite side is chosen, and blue or green if the side to the left or right of the previous side is chosen. In the video, these colors change too, by following a Bézier curve through the three-dimensional RGB colorspace.

You can download the code for yourself by visiting my MathArt repository on Github. If you have thoughts on this, if you want to play around with these ideas together, or if you just want to chat, please don’t hesitate to reach out!

The first animated GIF that I ever made was made with the LaTeX package TikZ and the command line utility ImageMagick. In this post, I’ll give a quick example of how to make a simple GIF that works by layering images with transparent backgrounds on top of each other repeatedly.

TikZ code

In our first step toward making the above GIF, we’ll make a PDF where each frame contains one of the above circles on a transparent background. In this case, each circle is placed uniformly at random with its center in a \(10 \times 10\) box, with a radius in \([0,1]\), and whose color gets progressively more red and less green with a random amount of blue at each step.

\documentclass[tikz]{standalone}
\usepackage{tikz}

\begin{document}
\foreach \red[evaluate=\red as \green using {255 - \red}] in {0,1,...,255} {
  \begin{tikzpicture}
    \useasboundingbox (0,0) rectangle (10,10);
    \pgfmathrandominteger{\blue}{0}{255}
    \definecolor{myColor}{RGB}{\red,\green,\blue}
    \fill[myColor] ({10*random()},{10*random()}) circle ({1+random()});
  \end{tikzpicture}
}
\end{document}

Starting with \documentclass[tikz]{standalone} says to make each tikzpicture its own page in the resulting PDF.

Next we loop through values of \red from 0 to 255, each time setting \green to be equal to 255 - \red so that with each step the amount of red goes up and the amount of green goes down.

The command \useasboundingbox (0,0) rectangle (10,10); gives each frame a \(10 \times 10\) bounding box so that all of the frames are the same size and positioned the same way.

The command \pgfmathrandominteger{\blue}{0}{255} chooses a random blue values between 0 and 255.

The command \fill[myColor] ({10*random()},{10*random()}) circle ({1+random()}); places a circle with its center randomly chosen in the \(10 \times 10\) box and with a radius between \(1\) and \(2\).

ImageMagick

When we compile this code, we get a PDF with one circle on each page. In order do turn this PDF into an animated GIF, we convert the PDF using ImageMagick, a powerful command-line utility for handling images. If we named our PDF bubbles.pdf then running the following code will give us an animated GIF called bubbles.gif.

convert -density 300 -delay 8 -loop 0 -background white bubbles.pdf bubbles.gif

I hope that you use this blog post as a jumping off point for making animated GIFs of your own! If you do, please reach out to share them with me!

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)

I’ve gotten a lot of mathematical inspiration from Project Euler questions, but perhaps the question that has gotten me thinking the most is Project Euler Problem 208: Robot Walks. In this problem, a robot takes steps either to the right or the left, and at each step, it turns \(\frac 15\) of the way of a circle.

Demo

I started thinking about this problem more seriously after I met Chase Meadors at the 2018 Graduate Student Combinatorics Conference and learned about his Javascript applet which allows a user to control a (virtual) robot 🤖 by using the left and right arrow keys. By repeating the same sequence of moves (e.g. \(4\) steps to the right followed by \(2\) steps to the left) I found that the robot traced out surprising symmetric patterns.

I cloned Chase’s Github Repo so that I could customize the robot further. If you go to the URL https://peterkagey.github.io/project-euler-208/?n=8&w=3,2,5,1 you’ll see an example of a robot walk, where n=8 means that each step will be \(\displaystyle \frac 18\) of a circle, and w=3,2,5,1 means that the robot will follow the pattern of \(3\) steps to the right followed by \(2\) steps to the left, followed by \(5\) steps to the right, followed by \(1\) step to the left, and repeating this pattern until it returns to where it began.

Stack Exchange Questions

I’ve asked a number of questions on Math Stack Exchange (MSE) and Code Golf Stack Exchange (CGSE) about these problems.

• Non-self-intersecting “Robot Walks” (MSE, May 2018)
• Area enclosed by robot walk (MSE, May 2018)
• Points in \(\mathbb{R}^2\) that can be reached via steps which are \(1/5\) of a unit circle. (MSE, August 2019)
• Circular Robot Instructions (CGSE, November 2019)

Openish Problem Collection

I’ve also asked about this setup in my Openish Problem Collection in Problem 41 and in Problem 69.

@RobotWalks

Twice each day, my Twitter Bot @RobotWalks tweets a randomly generated Robot Walk cycle. Check out the Github code if you want to see how it works, and read my series on making a Twitter Bot if you want to make something like it for yourself.

Jessica’s Robot Walk Prints

I ordered some canvas prints of some numerologically significant walks for my friend Jessica, which she hung behind her TV. There’s no doubt that this caused her to form a deep mental association between me and The Good Place.

What’s next?

Some day, I want to laser cut or 3D print some coasters based on these designs. Reach out to me if that’s something that you’re interested in, and we can do it together!

In March 2021, I got an out-of-the-blue email from OEIS editor Michel Marcus which totally delighted me. He wrote:

This afternoon I went to the library.
And I was browsing “Pour La Science” the French version of the Scientific American.
And here is what I saw.

I like the mysterious tone.

He included this photo of an excerpt of an article, which on the first line mentioned an OEIS sequence of mine (with my name slightly misspelled):

The article, translated

Michel had sent me a snippet of the article “Addition et multiplication, des tables qui intriguent” by French Computer Science professor Jean-Paul Delahaye. I read French quite clumsily, so I sent it to my friend Alec, and he volunteered a translation.

Sloane [verb not pictured] of my sequence A337655, Peter Kagey, who must have been informed of changes to the encyclopedia, proposed this second way of accounting for addition and multiplication. This has yielded a new entry in the encyclopedia, the following A337946:

1, 3, 7, 12, 22, 30, 47, 61, 85, 113, 126, 177, 193, 246, 279, 321, 341, 428, 499, 571, 616, 686, 754, 854, 975, 1052, 1150, 1317, 1376, 1457, …

Impossible Little Tables

Let’s consider the fourth question. The response is negative this time: no, it’s not possible that the tables of addition and multiplication have simultaneously only a few distinct values. This is a result of Paul Erdős and Endre Szemerédi from 1983, which we state precisely here:

“There exist two constants \(C>0\) and \(e > 0\) such that, for the set \(E\) of real numbers of […]

Translation by Alec Jones

A Sum-Product Problem

The article—or at least the part that I could make sense of—is about the opposite of Erdos’s Sum-Product Problem. This article explores questions about the greatest number of different values in the corresponding addition and multiplication tables for different sequences of positive integers.

Jean-Paul’s sequence, A337655, is the lexicographically earliest (greedy) sequence such that for all \(n\) both the addition and multiplication tables of the first \(n\) terms have \(\binom{n+1}{2}\) distinct terms (the greatest number).

The addition and multiplication tables share some values. For example, they both have a \(2\), a \(4\), a \(7\), a \(10\), and so on. My sequence, A337946, is similar to Jean-Paul’s but with the additional restriction that the addition and multiplication tables cannot have any values in common.

Some related sequences

I’ve recently added some new sequences to the OEIS related to these sequences.

One way of thinking of A066720 is that it’s the lexicographically earliest infinite sequence \(S = \(a_i\)_{i=1}^{\infty}\) such that for all \(n\) the set \(S_n = \{a_i\}_{i=1}^{n}\) consisting of the first \(n\) terms of \(S\) has the property that \(S_n \times S_n = \{xy \mid x, y \in S_n\}\) has exactly \(\binom{n+1}{2}\) elements—the most possible.

A347498: minimize the largest term

If instead of minimizing the lexicographic order, we instead minimize the size of the largest element, we get OEIS sequence A347498: for each \(n\), find the least \(m\) such that there exists a subset \(T_n \subseteq \{1, 2, \dots, m\}\) with \(n\) elements such that \(|T_n \times T_n| = \binom{n+1}{2}\). \(A347498(n)\) records the value of the \(m\)s.

For example, \(A347498(8) = 11\) as illustrated by the table below.

A347499: Examples with minimized largest element

We wish to record examples of the sequences described in the above section. There are \(A348481(n)\) subsets of \(\{1,2,…,A347499(n)\}\) with the distinct product property, but we record the lexicographically earliest one in OEIS sequence A347499.

 n | Distinct product subset of {1,2,...,A347499(n)}
---+-------------------------------------------------------
 1 | {1}
 2 | {1, 2}
 3 | {1, 2, 3}
 4 | {1, 2, 3, 5}
 5 | {1, 3, 4, 5,  6}
 6 | {1, 3, 4, 5,  6,  7}
 7 | {1, 2, 5, 6,  7,  8,  9}
 8 | {1, 2, 5, 6,  7,  8,  9, 11}
 9 | {1, 2, 5, 6,  7,  8,  9, 11, 13}
10 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15}
11 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15, 17}
12 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15, 17, 19}
13 | {1, 5, 6, 7,  9, 11, 13, 14, 15, 16, 17, 19, 20}
14 | {1, 2, 5, 7, 11, 12, 13, 16, 17, 18, 19, 20, 21, 23} 

For all of the known values, the lexicographically earliest subset begins with \(1\). Is this true in general?

A347570: Sums with more terms

Perhaps instead of asking when all sums \(x + y\) are distinct for \(x \leq y\), we want to know when all sums \(x_1 + x_2 + \dots + x_n\) are distinct for \(x_1 \leq x_2\leq \dots \leq x_n\). This family of sequences are sometimes called \(B_n\) sequences and have been studied by the likes of Richard Guy.

I’ve recorded the lexicographically earliest \(B_n\) sequences in OEIS sequence A347570.

n\k | 1  2   3   4    5     6     7      8
----+------------------------------------------
  1 | 1, 2,  3,  4,   5,    6,    7,     8, ...
  2 | 1, 2,  4,  8,  13,   21,   31,    45, ...
  3 | 1, 2,  5, 14,  33,   72,  125,   219, ...
  4 | 1, 2,  6, 22,  56,  154,  369,   857, ...
  5 | 1, 2,  7, 32, 109,  367,  927,  2287, ...
  6 | 1, 2,  8, 44, 155,  669, 2215,  6877, ...
  7 | 1, 2,  9, 58, 257, 1154, 4182, 14181, ...
  8 | 1, 2, 10, 74, 334, 1823, 8044, 28297, ... 

I ask about this family of sequences in a recent question on Code Golf Stack Exchange.

Other ideas?

Did this post spark any related ideas? Let me know about them on Twitter @PeterKagey—I’d love to hear about them!