In electronic music, sequences of "gates" express rhythms. A gate is either "open" or "closed." An "open" gate says "play this instrument at this step" and a "closed" gate says "play nothing at this step." A gate sequence is a bunch of gates in a row, like "open closed open open", which would mean the associated sound is played, skipped, played, played (repeating forever).

If we use 1 for "open" and 0 for "closed," we can write sequences compactly. For example, we can write a kick (bass drum) pattern of 1000, a snare pattern of 0010, and a hihat pattern of 0101. Read these one digit at a time, left to right: 1000 is "one zero zero zero", not "one thousand". Drawn out, those would be:

Here's what that pattern sounds like:

These 0101.. bitstrings look an awful lot like binary numbers!

I'll attempt to explain Galois Fields well enough here to follow the rest of the post, but I recommend reading Learn you Galois Fields for Great Good if you'd actually like to learn how they work.

When people talk about math, they are typically discussing numbers and operations. The most familiar operations are addition, subtraction, multiplication, and division. These operations take (usually) two numbers and give you back a new one.

We've come up with a bunch of rules that these operations follow. One such rule is the "distributive property," which says: x × (y + z) = x × y + x × z.

Sometimes we change the way the operations work. When doing "clock math" (math with time), numbers past 12 "wrap around", so 6+7 = 1. Wrapping is the same as keeping the remainder: 13 ÷ 12 leaves a remainder of 1. The number we wrap around, 12 in this case, is called the modulus, and this style of math is called modular arithmetic. Math (for some definition of math) still works on a clock face.

If we can change what operations do, can we also change what numbers are? Maybe; we could, for example, replace numbers with drum patterns, then define specific operations over these patterns that allow us to "add patterns together." Imagine "adding" two patterns together with a simple rule:

In each output position, the gate is open (1) only when the gate in the same position was open in exactly one of the two input patterns.

Working that out for a single position, we get this table:

input 1	input 2	output
0	0	0
0	1	1
1	0	1
1	1	0

Then, for a full sequence, we'd say: 0110 + 1101 = 1011 (check this yourself).

We've changed our numbers and changed our operations. Are we still doing math? We have a new "add" operation, does it follow any familiar rules? One familiar way to understand multiplication by a nonnegative whole number N is repeated addition: combine N copies of a value. But our new things are gate sequences, not whole numbers, so that recipe no longer tells us what multiplication should do. Can we define multiplication at all?

It turns out that the answer to these questions is sometimes. For some combinations of "things" and "operations," the familiar rules of math keep working (the distributive property, for example). When a combination allows the rules to work, we call it a field. A field built from only a finite collection of things is called a Finite Field, or Galois Field (named after Évariste Galois).

Next we'll convert the orbit into drum sequences using each element to sequence a single drum. We play a sequence for a while, then switch to the next sequence in the orbit.

For example, running the kick through one trip around the orbit, playing each sequence one time:

This sounds like:

On its own, it's fun. Each element is 3 steps long, so the full loop has 21 steps and does not naturally line up with the four-step groupings common in 4/4. I enjoy polyrhythmic/odd-metered music, so this is a good start.

Let's add more drums to the beat. We'll give each instrument its own starting element, then play the sequences all together. This looks something like:

And sounds like:

I do not like listening to this beat.

It's too dense, there's nothing obviously repeating to gravitate to; the structure is all buried. Every instrument also eventually plays 111, which adds more busyness to the beat.

Changing start, or choosing another gen that produced a full orbit, did not resolve the problem. The orbit visits every possible nonzero three-bit pattern, so this ends up just being dense and chaotic.

Let's try something different.

Let's "transpose" the sequences. For three-bit elements, we'll sequence 3 different instruments. Then, as we move through the orbit, use each bit of each element as the gates for the 3 instruments.

The pattern an instrument plays is defined by the whole orbit, rather than a single element.

Here's a diagram to help this make sense:

This sounds like:

This new beat sounds way better to me. What's going on?

We want to prove that, in any full orbit, every row is a shift of row 0.

Define \(L=2^n-1\); the number of nonzero elements in the field.

An orbit is: \[ e(t)=s g^t, \] where \(s\) is start and \(g\) is gen, both nonzero. Because the orbit is full, \(g^0,g^1,\ldots,g^{L-1}\) are distinct and \(g^L=1\).

Multiplying by a fixed nonzero value rearranges the field: every element comes out exactly once, or division would break.

Let \(b_i\) be the function that returns bit \(i\) of an element, counting from the left. For example, \(b_0(110)=1\) and \(b_2(110)=0\).

For each possible shift \(k\), and any element \(z\), define a "shift" function \(S_k\): \[ S_k(z)=b_0(g^kz), \qquad 0\leq k\lt L. \]

Observe: \[ g^k e(t) = g^k s g^t = s g^{k+t} = e(t+k) \]

So then, if we plug in an orbit \(e(t)\) for \(z\), we get: \[ S_k(e(t))=b_0(g^ke(t))=b_0(e(t+k)), \]

In English, this means that \(S_k\) produces row 0 (on the orbit) shifted by \(k\) steps.

We will show that, in a full orbit, for every \(b_i\) there is some \(S_k\) that is the same function.

Call any function that takes an element and returns a bit a readout: \[ f:\{n\text{-bit field elements}\}\longrightarrow\{0,1\}. \]

Two readouts are the same when they return the same bit for every element.

A readout is additive if it respects addition: \[ f(u+v)=f(u)+f(v) \]

Both \(+\) signs are the same XOR. Field addition applies it one position at a time, across all \(n\) positions at once. A readout hands back a single bit, so on the right there is only one position left to apply it to.

Addition of any two field elements never mixes the bits across positions. So this means that every \(b_i\) is an additive readout: \[ b_i(u+v) = b_i(u) + b_i(v) \qquad \forall i \]

No \(b_i\) is 0 everywhere, either: \(b_i\) returns 1 on the element whose only 1 sits at position \(i\).

We can count the additive readouts by looking at what they do to elements containing a single 1.

In a three-bit field, suppose \(f\) is additive. Since \(101 = 100 + 001\), \[ f(101)=f(100)+f(001). \]

We can apply the rule repeatedly. Since \(111=110+001\) and \(110=100+010\),

\begin{align*} f(111) &= f(110)+f(001) \\ &= f(100)+f(010)+f(001). \end{align*}

A three-bit field has three single-1 elements: 100, 010, 001. Every element breaks down into some combination of them, so \(f\) is determined entirely by \(f(100)\), \(f(010)\), and \(f(001)\). Every other output \(f(u)\) is found by XORing some combination of these three bits. Each of the three answers can be either 0 or 1, giving at most \(2^3\) additive readouts.

With \(n\) bits, this means there are at most \(2^n\) additive readouts. One is 0 everywhere, leaving at most \(2^n-1=L\) nonzero additive readouts.

We just showed that there are at most \(L\) nonzero additive readouts. We also have \(L\) shift functions: \[ S_0,S_1,\ldots,S_{L-1}. \]

If these are all additive, nonzero, and different from one another, they must fill all \(L\) available spots. There are three things to check.

1. Each \(S_k\) is additive. Multiplication distributes, and \(b_0\) is additive:

   \begin{align*} S_k(u+v) &= b_0(g^k(u+v)) \\ &= b_0(g^ku+g^kv) \\ &= b_0(g^ku)+b_0(g^kv) \\ &= S_k(u)+S_k(v). \end{align*}
2. No \(S_k\) is 0 everywhere. Multiplication by \(g^k\) rearranges the field, so some element \(z\) must satisfy \(g^kz=100\ldots0\). For that element, \[ S_k(z)=b_0(g^kz)=b_0(100\ldots0)=1. \] So \(S_k\) is not 0 everywhere.

3. No two shift amounts give the same readout. Suppose two different shifts produce the same readout: \(S_j=S_k\), with \(j\neq k\). Then, for every \(z\), \[ b_0(g^jz)=b_0(g^kz). \]

   XORing these two equal bits gives 0. Since \(b_0\) is additive,

   \begin{align*} 0 &= b_0(g^jz)+b_0(g^kz) \\ &= b_0(g^jz+g^kz) \\ &= b_0((g^j+g^k)z). \end{align*}

   Because \(j\neq k\), the coefficient \(g^j+g^k\) is nonzero. Multiplication by this coefficient rearranges the field, so the equation would make \(b_0\) return 0 on every element. But \(b_0(100\ldots0)=1\), so that is impossible.

We have found \(L\) distinct nonzero additive readouts, the most there can be. Thus, for every \(i\), there is some \(k\) such that \[ b_i(e(t))=S_k(e(t))=b_0(e(t+k)). \] Every row is therefore a shift of row 0, so every pair of rows differs by a shift. \(\square\)

Suppose the orbit repeats after \(d\) steps, where \(d\lt L\). Then \(g^d=1\), so \[ S_{k+d}(z)=b_0(g^{k+d}z)=b_0(g^kz)=S_k(z). \] There are only \(d\) different shift functions. The count no longer matches: there are \(d\) shift functions, not \(L\), so nothing forces every \(b_i\) to be a shift function.

For example, in the field of four-bit elements (\(2^4=16\) elements), gen=1000 produces this short orbit:

orbit   0001 1000 1100 1010 1111
rows    01111
        00101
        00011
        10001

Row 0 contains four ones, while every other row contains two. A shift preserves that count, so row 0 cannot be a shift of any other row. The property can fail when the orbit is short.

I had tried short orbits earlier, but some of them were deceptive: the active rows were shifts of one another while another row was all zero. That looked like another version of the same pattern, and I missed that only full orbits guarantee it for every row. An all-zero row just means that the short orbit never visits an element with a 1 in that bit position.