Start with a row of marks
A coin has two different faces. Recognizing that difference makes a distinction. Counting requires something more: a rule we can apply again and again.
Begin with an empty record. Add one mark, then another, then another. Call the empty record 0 and the act of adding a mark δ, pronounced "delta." If the current record is r, write Sr for the record with one extra mark. The letter S stands for "successor," or the next record.
These records give the natural numbers: 0, 1, 2, 3, and so on. Joining a two-mark record to a three-mark record gives five marks, which defines addition. Joining three copies of a two-mark record gives six, which defines multiplication. The notation ℕδ means the natural numbers constructed this way; ℕ is the usual symbol for natural numbers.
There is also a way to prove something about every record without checking them one by one. Check the empty record, then show that adding a mark preserves the property. Every record is reached by these steps. This method is called induction.
A switch remembers odd or even
Imagine flipping a light switch once for each mark. Start with the light off. One mark leaves it on, two leave it off, and three leave it on again. The switch remembers whether the number of marks is odd or even. It cannot distinguish two marks from four.
Once the starting state and the next-step rule are fixed, each row of marks has exactly one corresponding state of the switch. This remains true for any system with a specified start and next step. The counting records provide a common way to describe all such systems, including ones that forget how many steps have occurred.
When does another system preserve all the counting records?
The formal name for a system with a start and next step is a δ-algebra. The statement that the counting records map into each such system in exactly one start-and-step-preserving way is called initiality. A map here is simply a rule assigning a target state to each record.
For that map to keep different records different, two conditions suffice: the next-step rule must never merge two states, and it must never return to the starting state. The switch fails the second condition. If, in addition, induction holds for every property of the target states, then there are no extra states beyond the ones reached by counting. The two systems correspond exactly. This stronger result is called rigidity.
The construction uses a mathematical setting in which records can be generated step by step, compared for equality, and used to define operations recursively. "Recursively" means that the rule for the next record uses the result for the previous one. The result establishes the counting structure within that setting.
Source: The δ-calculus, section 1.
When a summary starts to repeat
The light switch gives a useful summary of a count: odd or even. It also lets us combine summaries. An odd count plus another odd count is even, regardless of the counts themselves. For instance, 3 + 5 and 7 + 9 are both even.
Call a summary a recognizer when it preserves this ability to combine. We must be able to obtain the summary of a combined record from the summaries of its parts alone. The original counts may be lost.
A recognizer need not repeat immediately. The counter below remembers its first two states, then cycles through three more. Follow the arrows or press "Add one step." The labels are states of the counter, not the total number of steps taken.
Explore 01 · A counting summary
Count to two, then repeat a three-state cycle
Two numbers specify this pattern: how long it takes to reach the cycle and how many states the cycle contains. Mathematicians write it as M(i, p), where i is the number of states before the cycle and p is the number in the cycle. Here i = 2 and p = 3, giving five states in all. A twelve-hour clock has no initial stretch and twelve repeating states: M(0, 12).
The five-state counter also preserves combination. Two counts each summarized by state 2 combine to state 4: 2 + 2, 2 + 5 and 5 + 5 give 4, 7 and 10, all remembered as state 4. More generally, once each input has reached the cycle, changing it by a multiple of three cannot change the summary of the sum.
Under the usual classical rules of logic, every recognizer of counting has one of two forms. It either keeps every count distinct, or it eventually repeats in exactly this way. Once two different counts have merged, applying the same next step to both cannot pull them apart again. That is what makes the repetition persist.
The names behind the classification
A monoid is a collection with a combining rule and an empty item that changes nothing. Brackets must not affect the result: (a + b) + c equals a + (b + c). Counting under addition is one example. Strings of letters joined end to end are another.
A recognizer is formally a monoid homomorphism: a map that preserves combination and the empty item. Counts with the same summary form a group of indistinguishable inputs. The collection of these groups is the recognition quotient. For the light switch, its two groups are the even and odd counts.
A congruence is a rule for treating inputs as equivalent that remains valid when inputs are combined. For M(i, p), two counts are equivalent if they are equal, or if both have reached i and their difference is a multiple of p. In M(2, 3), counts 2 and 5 are equivalent, while 1 and 4 are not.
The classification says that, using classical logic, every such congruence is exact equality or the rule for one unique pair i, p, with i ≥ 0 and p ≥ 1. A recognizer may have infinitely many possible outputs; finiteness is a conclusion in the repeating case, not a premise.
What information lets us find a repetition?
The diagram shows where its counter starts repeating. A summary supplied only as a rule is harder to inspect. Whether we can locate a repetition depends on what else we know about that rule.
First suppose we can decide, for any two counts, whether their summaries match. "Decide" means that a procedure always finishes with yes or no. If we are also given a matching pair, say counts 2 and 5, we have a finite region to search. We can check earlier counts for the first repetition, then find the shortest repeating cycle.
Now suppose we have the same yes-or-no procedure but no matching pair. We are given only a proof that it is impossible for all counts to stay distinct. In constructive mathematics, which requires an existence proof to supply an example or a way to find one, this is weaker information. An additional logical principle is needed to turn that impossibility proof into a matching pair. It is called Markov's principle.
We can write a search without that principle: test (0, 1), then (0, 2) and (1, 2), then every pair ending in 3, and continue. Every individual comparison finishes. The remaining question is whether the search as a whole will return a match. Markov's principle permits the inference from "there cannot be no match" to the existence of a matching pair. It justifies success from that negative premise; it supplies no new search technique or advance bound on how far to search.
The broadest classification makes no assumption that matching can be decided by a procedure. It uses excluded middle: for any statement P, either P is true or its negation is true. Classical mathematics accepts this principle even when neither alternative comes with a method for finding out which holds.
For this classification, these are exact requirements. Over the constructive starting assumptions used in the paper, the second version implies Markov's principle, and the broadest version implies excluded middle. The principles are therefore needed for those versions of the theorem; they are not just conveniences of the proofs presented.
How the calculus records logical assumptions
The paper distinguishes a proof inside its formal calculus, a system of specified deduction rules, from a proof about that calculus in the surrounding mathematics. The classification requirements above concern the surrounding mathematics.
Inside the calculus, a derivation is a sequence of permitted deductions. Each derivation carries a list of the extra logical rules it uses. EM abbreviates excluded middle and MP abbreviates Markov's principle. MP concerns a test that can be decided for each natural number: if it is impossible that no number passes, MP permits the conclusion that some number passes. This is the removal of a double negation, "not no example," for that kind of test.
LPO, the limited principle of omniscience, says that a yes-or-no sequence either contains a yes somewhere or contains only no. Excluded middle implies LPO, and LPO implies MP in the constructive setting used here. LPO has no separate role in the final classification requirements.
A fourth label, QInd, records induction on formulas that contain "for every" or "there exists." The paper calls a derivation forced when its list contains none of EM, LPO or MP; QInd does not change that designation.
The soundness result concerns this last definition. Any complete statement obtained by a forced derivation, starting without assumptions, is true when interpreted using the ordinary natural numbers and their usual arithmetic. A complete statement has no unspecified free variables. Soundness relates the deduction rules to that interpretation.
Source: The δ-calculus, sections 3 and 7.
What if we need to subtract more than we have?
So far, we have made records smaller by merging counts. We can also extend what a record can represent. A row of marks can record five, but it cannot record minus three. To include negative numbers, use a pair of rows: one for an amount received, one for an amount owed. The pair (2, 5) records two received and five owed. The pair (4, 7) has the same balance.
We can recognize equal balances without having defined negative numbers yet. Move the debts to the other side and compare two ordinary sums:
Treat all pairs with the same balance as one number. This constructs the integers, including negative numbers and zero. Their symbol is ℤ; ℤδ names the integers obtained from our counting records.
Fractions use the same idea. A numerator and a nonzero denominator form a pair, and cross-multiplication tells us when two pairs represent the same fraction. For example, 1/2 and 2/4 agree because 1 × 4 = 2 × 2. The resulting numbers are the rational numbers, written ℚδ.
Extending the counting records
Each extension keeps the numbers we already have. Five can be represented as the balance (5, 0), then as the fraction 5/1. No arbitrary representative has to be chosen for each balance or fraction: the construction works with all equivalent pairs together.
Negative numbers will let us count a crossing as +1 in one direction and −1 in the other. But adding negatives or fractions still gives the same result when the terms are rearranged. To record order itself, we will need something beyond an ordinary sum.
Encoding the numbers, and the question of real numbers
An encoding assigns a different natural-number label to each object. For integers, a simple list begins 0, 1, −1, 2, −2, and so on; the position labels the integer. The paper provides encodings for natural numbers, integers and rational numbers. The labels identify the objects, but adding two labels need not correspond to adding the objects they label.
Real numbers include quantities such as √2 that are not fractions. One construction uses a Cauchy sequence: an ordered list of rationals in which, for any positive rational tolerance, however small, any two sufficiently late terms differ by less than that tolerance. Another describes a number by the set of rationals smaller than it, called a Dedekind cut. For the number 1, the cut contains the rationals less than 1. Its complement, meaning all the remaining rationals, contains 1 and every rational greater than 1. Under classical assumptions these constructions give equivalent number systems. Under weaker constructive assumptions, their equivalence requires further care. The paper's number construction stops at the rationals.
The same roads can be taken in a different order
With a row of identical marks, three marks followed by two gives the same result as two followed by three. There is only one kind of step to record. A journey gives us several kinds: at a junction, we can take different roads.
Use the corners and edges of a cube as a small road network. A network of points and connections is called a graph; the points are its vertices. Our graph has eight vertices and twelve edges. Its faces are not part of the network, so every journey must follow edges.
Label the vertices with three digits, each 0 or 1. Think of these as the settings of three switches. Moving along an edge changes one setting. Number the positions 0, 1 and 2 from right to left: move 0 changes 000 to 001; move 1 changes 000 to 010; move 2 changes 000 to 100.
Start at 000 and return there. This is a closed walk, and 000 is its basepoint. Name two walks A and B. Walk A uses moves 0101 and goes around one square face. Walk B uses 1212 and goes around another. AB means take A and then B; BA means take them in the other order.
Keep a letter when a route crosses a marked edge
Choose seven edges that connect every vertex without forming a circuit. These edges are called a spanning tree, drawn as solid lines below. They provide routes between vertices, but no choice of ways around a circuit. The five remaining edges are dashed and carry labels x₁ to x₅.
Each time the walk crosses a dashed edge, write its label. For the opposite direction, use an inverse label, such as x₁⁻¹, read "x one inverse." Here the −1 marks the reverse crossing; it is not an ordinary numerical fraction. Solid edges write nothing. On walk A, the first three edges are solid. Only the final crossing, from 010 back to 000, writes a letter: x₁⁻¹. If an x₁ is immediately followed by x₁⁻¹, cancel the pair. The same rule applies in reverse and to each of the five labels. Continue until no adjacent opposite pair remains.
The letters left over form the reduced word of the walk. For example, x₁x₂x₂⁻¹ becomes x₁. The notation ρ(w), read "rho of w," means the reduced word of walk w. A separate signed count for each label adds 1 for xi and subtracts 1 for xi−1, forgetting where those letters occurred. The display shows both records.
Explore 02 · Walk the graph
Watch a route become a shorter record
Letters remaining · read left to right
Start at 000. No crossings yet.
Signed counts: (0, 0, 0, 0, 0)
AB and BA cross each directed edge the same number of times. "Directed" means that a road taken outward and the same road taken back get separate counts. Yet the two reduced words differ:
Same edge counts · different order
AB
Face A first, then face B.
BA
Face B first, then face A.
No choice of fixed edge scores can distinguish these trips. AB and BA use each directed crossing equally often, so adding its scores always gives the same total. Recovering the order requires a record that retains it.
Reduced words forget something too. Going out along an edge and straight back leaves the same empty word as staying home, although the edge counts differ. Thus an edge tally and a reduced word preserve different information; neither one determines the other.
Why five letters? What is a free group?
A connected graph with eight vertices needs seven edges to connect them without a circuit. Each of the remaining 12 − 7 = 5 edges creates another way around. These five ways give the five letters.
Reduced words can be combined by joining them and canceling opposite pairs. They can be undone by reversing the letters and changing every letter to its inverse. The system is called the free group on five generators, written F₅. "Generators" are the five letters, and "free" means that the only simplifications imposed are inverse cancellation. For example, x₁x₂ cannot be changed to x₂x₁.
A square has only one independent way around. Its reduced words amount to a signed number of circuits, so their order makes no difference. Among cube graphs, the ordinary three-dimensional cube is the first with enough independent circuits for order to matter this way. Other kinds of smaller graphs can also have that property.
A cube graph Qn has a vertex for each string of n zeros and ones, with an edge whenever two strings differ in one position. This defines higher-dimensional cubes without needing to draw them.
Other ways of dividing and summarizing a walk
Cut a closed walk each time it returns home. This gives a unique list of trips with no intermediate return, called first-return loops. For example, the move sequence 00101101 splits as (00)(101101). Joining closed walks is associative: the placement of brackets does not change their sequence. With staying home as the empty item, this makes a monoid, denoted W. It is the free monoid on first-return loops: every walk is one unique list of those loops.
The signed letter counts are written a(w). Keeping these counts and forgetting letter order is called abelianization. The word x₁x₂x₁⁻¹x₂⁻¹ has zero count for every letter, although nothing cancels. Its order survives in the reduced word.
The full directed-edge tally is written τ(w), read "tau of w." Any rule that adds fixed edge scores can be calculated from this tally, including vector scores, provided their addition is independent of order. A collection with reversible, order-independent addition is called an abelian group.
One special scoring rule assigns a height to each vertex and records the change in height at each step. Along a route the changes cancel except for final height minus initial height. Every closed walk therefore scores zero under this rule, even when its reduced word is nonempty.
Exact histories keep more information than reduced words, which in turn keep more than signed letter counts. In the notation of the paper, ∼r means "has the same result under reading r" and ΔW means exact equality of walks. The relation ΔW ⊊ ∼ρ ⊊ ∼a says that each step to the right merges more histories. The symbol ⊊ means "is contained in, but is not equal to."
A fixed amount of memory eventually loses some order
The last example defeats a tally, but a small memory can distinguish AB from BA. Give it a single setting, 0 or 1. A crossing used only by A sets it to 0; a crossing used only by B sets it to 1. The final setting reports which face was visited last. One binary setting, or bit, is enough for this pair.
Now consider any reader with a fixed number of internal states. After each edge crossing, it updates its state using only its present state and that edge. At the end it gives an answer. A two-state reader is like the single bit; a reader with a million states has many more possibilities, but still a fixed limit.
For every such limit, the paper gives two closed walks with different reduced words that all readers within the limit confuse.
The pair depends on the memory limit. A larger reader can distinguish a particular pair that defeated a smaller one. The result is that no fixed number of states can recover the reduced word for every possible walk, however long.
The paper’s finite-memory result
Feed one block of moves to a limited-memory reader repeatedly. Eventually an internal state must repeat. Once that happens, feeding another complete cycle of blocks returns it to the same state.
For readers with at most k states, choose N = k!, meaning 1 × 2 × … × k. For three states, N = 3! = 6. This number is long enough to pass any initial stretch, and every possible cycle length divides it. The reader therefore treats N copies and 2N copies of a block alike, from any starting state.
The paper applies this to the square walk B = 1212. Every reader with at most k states finishes in the same state on BN and B2N. Their reduced words are different: one contains N copies of x₁x₅⁻¹x₂⁻¹, the other contains 2N, and no letters cancel between copies.
Their signed counts are also different. An unbounded counter can distinguish this pair. The result isolates a limit of fixed finite memory; it does not say that these particular walks hide their difference from a tally.
An extension: even exact tallies can agree
The repetition argument also gives a stronger result: two walks can have equal lengths, equal directed-edge tallies, and equal final reader states. Even supplying the exact tally at the end leaves the reader unable to distinguish them.
Use the square walk A = 0101 and another closed walk C = 01020102. C leaves the single reduced letter x₂⁻¹. Now arrange repeated copies in two ways; AN means N copies of A:
Both trips use 3N copies of A and N copies of C, so every directed-edge count agrees. The reader's states also agree after each block: it cannot distinguish N copies of A from 2N. But their reduced words change from x₁⁻¹ to x₂⁻¹ at different positions, after N letters in the first trip and after 2N in the second. Neither the final state nor the crossing counts say which order occurred.
Allow the record to grow
Instead of fixing the number of states, keep a list of letters that can grow as needed. When a new letter arrives, compare it with the last letter on the list. If they are opposites, erase the last letter and discard the new one. Otherwise add the new letter at the end.
This arrangement is called a stack: only the most recently added item is added to or removed from. The conventional names are "push" for adding and "pop" for removing. In the figure, the rightmost letter is the top of the stack.
One reduction, step by step
The list always holds the reduced word of the letters seen so far. Each finite walk needs only finite storage. What changes is that the available storage has no fixed upper bound.
The precise restriction on the reader
The argument uses a deterministic reader: the same current state and edge always produce the same next state. Its updates may consult only those two items. It may receive exact counts at the end, but cannot consult unlimited counters while the walk is in progress. Such counters would themselves supply memory beyond the fixed bound.
With A four moves long and C eight moves long, each displayed trip has length 20N. The construction works for k ≥ 1 and for every possible initial state of the reader.
A sequential reader need not be a recognizer in the combining sense of section 2. Its final answer need not tell us how answers combine. The reduced-word map does preserve combination: join the words and cancel adjacent inverse pairs.
Does changing the starting point remove the difference?
The words for the two trips above are different when read from their specified beginning, but describe the same circular sequence if the beginning is moved. Mathematically they are conjugate: if g is one word, the other can be written t g t⁻¹ for some word t. The inverse word t⁻¹ lists the letters of t in reverse order, with each letter replaced by its inverse. The prefix t moves the starting point and the suffix t⁻¹ moves it back.
A stronger pair remains different even after that freedom is allowed:
Both contain 4N copies of A and two copies of C, have length 16N + 16, and defeat every reader with at most k states by the same repetition argument. Their reduced words contain only inverse letters, so no cancellation occurs even when each word is read as a circle. Two such words are conjugate exactly when one is a circular rotation of the other. The spacings between the two x₂⁻¹ letters are N and 3N copies of x₁⁻¹ in P, compared with 2N and 2N in Q. No rotation makes those spacings agree, so the words are not conjugate. This is a further extension of the paper’s repetition argument.
Source: The loop-order paper, theorems 5.1–5.3. The equal-tally and nonconjugate examples are extensions derived above.
Fourteen steps leave order after the signed counts cancel
Return to the signed letter counts: x₁ adds one to the first count and x₁⁻¹ subtracts one. We want a closed walk whose counts all return to zero, while its reduced word stays nonempty. On the cube, the shortest such walk has fourteen edge crossings.
There is one positive and one negative occurrence of each of x₁, x₂ and x₃, so all the signed counts cancel. None of the opposite letters are adjacent. The word therefore cannot be reduced any further. Choose "the fourteen-step loop" in the cube example to follow it.
The ordinary crossing counts have not vanished. The walk has taken fourteen steps, and a tally still records them. What disappears is the net count, positive crossings minus negative crossings. That difference is essential to the result.
Why fewer than fourteen steps cannot work
Look only at the vertices and edges visited by the walk. They form a connected graph, because the walk travels through all of them. Choose a spanning tree within it. Each extra edge beyond the tree supplies one independent circuit. With only one such circuit, a reduced word is determined by the net number of times around it. A nonempty reduced word with all signed counts zero therefore needs at least two independent circuits.
A spanning tree on v vertices has v − 1 edges. Two extra edges require at least v + 1 edges altogether. If a walk could use six or fewer edges, it would therefore visit at most five vertices.
Divide cube vertices into those with an even number of ones in their labels and those with an odd number. Every edge crosses between these sets. This makes the graph bipartite. It is also simple: it has no self-connections or duplicate edges.
Fewer than four vertices cannot make a circuit in a simple bipartite graph. Four vertices allow at most a square, which has only one independent circuit. Five vertices are the only remaining possibility. A one-versus-four division permits at most four edges. A two-versus-three division permits six, but reaching six requires every possible connection between the sets. This six-edge graph is called K₂,₃: two vertices each joined to the same three neighbors.
A cube cannot contain that graph. For two distinct cube vertices to share a neighbor, their labels must differ in exactly two positions. There are only two possible intermediate labels, one for each position changed first. They can therefore share at most two neighbors, never three. At least seven distinct edges are needed.
It remains to count how often those edges are crossed. A closed walk has as many arrivals as departures at each vertex. Once the dashed edges have zero net flow, consider an endpoint of the remaining tree. Its one solid edge must also have zero net flow. Remove that edge and repeat at a new endpoint. This exhausts the tree, so every used edge is crossed equally often in both directions, at least twice. Seven edges require at least fourteen crossings.
The displayed walk reaches that bound. The same lower bound and example work on every cube graph Qn with n ≥ 3. The formal name for this minimum is abelian girth: the shortest closed walk with zero net edge flow whose reduced word is nonempty.
A number that detects some of the remaining order
Signed counts lose all letter order. A further quantity can retain some of it. Watch two counts, a₁ and a₂, as the word is read. Whenever a new x₂ or x₂⁻¹ arrives, add the current a₁ times that letter's sign. Whenever x₁ or x₁⁻¹ arrives, subtract the current a₂ times its sign. Call the final result μ₁₂, read "mu one two."
For x₁x₂x₁⁻¹x₂⁻¹, the contributions are 0, 1, 1, 0, giving μ₁₂ = 2. For the fourteen-step example they give −2. Both words have zero signed counts, but this extra quantity detects order that the counts lost. Canceling an adjacent opposite pair does not change μ₁₂.
The same construction works for any two labels i and j. In symbols, if si(k) is +1, −1 or 0 according to what step k contributes to count i, then
Σ means add the contribution from every step; the superscript k−1 selects the count just before the step. These quantities fit into a classification of order using commutators. For two words g and h, their commutator is ghg⁻¹h⁻¹. The inverse of a word reverses its letter order and replaces each letter by its inverse.
Start with all reduced words, called level γ₁, read "gamma one." Level γ₂ consists of words made by joining finitely many commutators or their inverses and canceling adjacent opposite letters. This is what "generated by commutators" means. They have zero signed counts, even though their words can be nonempty.
To form the next level, take a word r from γ₂ and any word t, and form rtr⁻¹t⁻¹. Joining finitely many of these new commutators or their inverses makes level γ₃. For a concrete example, take r = x₁x₂x₁⁻¹x₂⁻¹ and t = x₁. The resulting word rx₁r⁻¹x₁⁻¹ belongs to γ₃. This process continues and is called the lower central series.
Ignoring third-level differences means treating two words u and v as equivalent when uv⁻¹ belongs to γ₃. Within γ₂, the numbers μij/2 describe the distinctions left by that rule: two such words are equivalent exactly when all these numbers agree. Every word in γ₃ has all its μ values zero. The fourteen-step word has μ₁₂ = −2, so it is in γ₂ but outside γ₃.
Choosing a different spanning tree changes the letters and individual coordinates. It preserves whether a word is empty, its level in the series, and the minimum of fourteen steps.
Two order-sensitive records can disagree
The reduced word remembers some order and cancels backtracking. We can design a different record that notices backtracking too. For this example, assign each of the three move directions a multiplier, and multiply them as the walk proceeds.
Ordinary numbers would lose the order: 2 × 3 equals 3 × 2. Instead use quaternions, numbers with four parts, written a + bi + cj + dk. Their rules are i² = j² = k² = −1, with ij = k, jk = i and ki = j. Reversing any of those last three products changes its sign: ji = −k, kj = −i and ik = −j. Multiplication distributes over addition as it does in ordinary algebra, but the order of the factors matters.
Give move 0 the multiplier 1 + i, move 1 the multiplier 1 + j, and move 2 the multiplier 1 + k. A walk's product is formed from left to right. These multipliers are a choice in this example, added to the cube and its routes. Keep the directed-edge tally alongside the product; the paper calls this combined record a clock. Here "clock" means a record updated at each step, not a measurement of elapsed physical time.
Both directions along an edge use the same multiplier. An out-and-back trip in direction 0 therefore gives (1 + i)² = 2i. The reduced word erases that backtrack, but the quaternion product retains its effect.
The product can distinguish erased trips
The walks 001122 and 002211 each go out and back in three directions. Both reduced words are empty, and their directed-edge tallies agree. Their products are (2i)(2j)(2k) = −8 and (2i)(2k)(2j) = 8.
The word can distinguish equal products
For the square walks, (1 + i)(1 + j) = (1 + j)(1 + k) = 1 + i + j + k. A and B each square that quantity, giving 2(−1 + i + j + k). AB and BA therefore multiply the same quantity by itself. Their products and directed-edge tallies agree, while their reduced words differ.
Knowing the combined clock record does not determine the reduced word, and knowing the reduced word does not determine the clock record.
Why the normalized product has finitely many values
Each multiplier has size √2. Dividing a walk's product by (√2)n, where n is the number of moves, removes its growth in size. This is called normalization. The size of a + bi + cj + dk is √(a² + b² + c² + d²).
On closed cube walks, the normalized product has exactly 24 possible values. When unfinished walks are included, there are 48 possible normalized products. A record with 48 states can therefore keep track of the product step by step. The 24 closed-walk values form a multiplication system called the binary tetrahedral group, denoted 2T. Its name identifies this finite group; the result here is the exact count of normalized products.
The full clock also keeps the directed-edge tally, whose counts have no fixed bound. It therefore does not have only 24 possible outputs. Write h(w) for the product and τ(w) for the directed-edge tally. The full record is c(w) = (τ(w), h(w)). Thus the full history distinguishes more walks than c, and c distinguishes more than the tally alone.
A correct list must belong to the right trip
Suppose we write a number beside every cube vertex to record how often a walk visited it. To avoid counting a closed walk's return twice, count the vertex being departed from on each step. The out-and-back walk 00 counts one departure from 000 and one from 001. Every other vertex gets zero.
This list of eight counts is called the walk's occupation vector, written occ(w). A vector here means an ordered list of numbers, one for each vertex. Staying home without taking a step gives an all-zero list. Now imagine receiving both a walk and a proposed list, α, read "alpha." A matching test accepts the pair exactly when α = occ(w).
Could that test be replaced by two independent checks, one for the list and one for the walk? Take staying home as trip 1 and the out-and-back walk 00 as trip 2. Their respective visit lists both pass with their own trips. If the lists and trips were checked independently, list 1 would also pass with trip 2. But when the trips have different visit counts, the swapped list is wrong.
Independent tests or a matching rule?
Two independent tests
A matching test
The matching rule connects a record to a particular history. In the paper this is called occupation binding. A rule that does allow every accepted list to pair with every accepted trip is called rectangular, because its allowed pairs fill a rectangle in a grid such as the one above.
An occupation-based rule may compare α with occ(w), but uses no other information about the walk. There is an exact condition under which every such rule can be split into independent checks: all walks under consideration must have the same occupation vector. Then the history contributes the same list every time, so it supplies no varying information to the rule. If two walks have different vectors, the matching test already prevents that split.
What counts as an occupation-based rule?
The proposed state α may assign any integer to each vertex, even though a genuine visit count is nonnegative. Write A = ℤV for all these assignments, where V is the collection of vertices and ℤ is the integers. A rule is occupation-based if it looks at the history only through occ(w). It may compare that vector with α in any way; it cannot inspect the rest of the walk.
For a specified collection S of closed walks, the theorem says that every such rule is rectangular on A × S if and only if occupation is constant on S. The product notation A × S means all pairs of an assignment from A and a walk from S. A rectangular rule accepts exactly the pairs in PA × PS, for some independently accepted assignments PA and walks PS.
The right record depends on the question. Parity is enough to determine whether a sum is odd or even. Crossing counts are enough to total fixed edge scores. A reduced route requires a record of order; a valid visit list requires a connection to the trip it describes.
Names and symbols used in the guide
- δ; 0; Sr
- Adding one mark; the empty record; record r with one extra mark.
- ℕ; ℤ; ℚ
- Natural numbers; integers; rational numbers. A subscript δ names their construction from the repeated step.
- M(i, p)
- A counting summary with i states before repetition and p states in its cycle.
- Recognizer
- A summary that preserves combination: summaries of the parts determine the summary of the whole.
- EM; MP; LPO
- Excluded middle, Markov's principle and the limited principle of omniscience, explained in section 3.
- Qn; W
- The graph of n-digit binary labels connected by one-digit changes; the collection of closed walks from a fixed home.
- ρ(w); F₅
- The reduced word of walk w; the system of words on five letters and their inverses, with adjacent opposite pairs canceled.
- a(w); τ(w)
- Signed letter counts; the tally of each directed edge crossing. These are different summaries.
- μij; γn
- An extra count sensitive to order between letters i and j; levels in the commutator classification explained in section 7.
- h(w); c(w)
- The chosen quaternion product; the combined record of that product and the directed-edge tally.
- α; occ(w)
- A proposed list of integers at the vertices; a walk's actual departure counts at those vertices.
Sources and further reading
- The δ-calculus: from distinction to arithmetic, Jonathan Washburn and Milan Lj. Zlatanović. The construction of the numbers, the classification of counting summaries, and the logical assumptions required by that classification. Published in Advances in Pure Mathematics 16 (2026), 705–739.
- From One Generator to Loop Order on the Three-Dimensional Cube, Jonathan Washburn and Milan Zlatanović. arXiv:2609.19218v1, 16 September 2026. The research paper behind the cube-walk sections: directed transition counts, reduced loop words, finite memory, the shortest fourteen-step example, quaternion records and occupation constraints. Read the paper (PDF).
- From Distinction to Loop Order: A Concept Guide. An explanatory companion to the arithmetic and cube-walk papers.
- δ mathematics in Lean. Lean is software for checking formal mathematical proofs. This repository includes a map connecting the arithmetic results to their proofs.
- Recognition Science's public physics proofs, and the Recognition Encyclopedia for the wider theory.
The arithmetic results are developed in the δ-calculus paper and its accompanying code. The main cube-walk proofs are in the loop-order paper; section 6 of this guide also derives two stronger memory examples and labels them as extensions. The interactive walks let you inspect particular examples.