🔢 mathematics

Optimal Non-Binary Single-Track Gray Code

This paper proves the existence of optimal non-binary single-track Gray codes of length $p^t$ with $p^{p^t}$ codewords over the finite field $\mathbb{F}_p$ for the primes $p=3$ and $p=5$ , while also providing conditions for their existence for larger primes and non-prime alphabet sizes.

Original authors: Tuvi Etzion

Published 2026-07-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tuvi Etzion

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to keep track of a spinning wheel, like the one on a bicycle or a giant industrial fan. You want to know exactly where the wheel is at any split second. To do this, engineers paint stripes on the wheel and use sensors to read them. If you use a standard numbering system, the sensors might get confused when the wheel is right between two numbers, because multiple stripes might change at once, leading to a "glitch" where the computer thinks the wheel is in the wrong spot.

To fix this, mathematicians invented a special kind of code called a Gray code. Think of it as a secret language where, to move from one number to the next, you are only allowed to change one single thing at a time. It's like climbing a ladder where you can only move one rung up or down; you never jump two rungs at once. This ensures that if your sensors get a little shaky, they will only see a tiny, harmless mistake, not a massive confusion.

Now, imagine you want to build a super-precise wheel, but you don't have enough space to paint a separate track for every single sensor. You need a way to squeeze all that information into a smaller package. This is where Single-Track Gray Codes come in. Instead of having many different tracks, you have just one track that is copied and shifted around. It's like having a single, long ribbon of code that is wrapped around the wheel, but the sensors read it at different starting points. The magic is that this single ribbon, when read from different angles, still follows the "change only one thing" rule.

For a long time, scientists knew how to make these codes for simple "yes/no" (binary) systems, but they hit a wall: they couldn't make them work for every possible size of wheel, especially when the wheel needed to show every single position without missing any. They also struggled to make them work with more complex systems that use numbers like 0, 1, 2, 3, and 4 (non-binary systems).

This paper is about breaking that wall down. The authors, led by T. Etzion, have figured out how to build these special "single-track" codes for systems that use prime numbers like 3 and 5 as their alphabet size. They didn't just guess; they built a mathematical machine—a recursive recipe—that proves these codes definitely exist for wheels of specific sizes (lengths of $p^t$ where $p$ is 3 or 5 and $t$ is any number 2 or larger).

Here is the story of how they did it, using a few playful metaphors:

The Building Blocks: The "Self-Dual" Ribbons

To build their code, the authors needed a special kind of ingredient. Imagine you have a long strip of paper with a pattern of numbers on it. Now, imagine a "magic mirror" that adds 1 to every number on the strip (so 0 becomes 1, 1 becomes 2, and 2 wraps around to 0).

Usually, if you look at the original strip and the mirrored strip, they look totally different. But the authors needed a special kind of strip where, if you shift the mirror image just the right amount, it looks exactly like the original. They call these Self-Dual Sequences (SDS). Think of them as ribbons that are perfectly symmetrical under a specific kind of magic transformation.

The paper proves that you can create an infinite supply of these ribbons for systems using 3 or 5 symbols. They did this by showing a step-by-step recipe: take a small ribbon, add some extra "flavor" (mathematical words called $Z$ and $Y$ ), and boom—you have a bigger, perfect ribbon. It's like a fractal: you take a small pattern, apply a rule, and it grows into a larger pattern that still keeps its special symmetry.

The Assembly Line: Stitching the Ribbons Together

Having the ribbons is only half the battle. You need to line them up in a specific order to create the final code. If you just throw them in a pile, the sensors will get confused.

The authors had to arrange these ribbons so that when you move from one ribbon to the next, you only change one single position in the code. This is the hardest part. It's like trying to arrange a deck of cards where every time you swap one card for the next, you can only change the value of that one card, and you must eventually loop back to the start without ever getting stuck.

For the number 3 (ternary systems) and the number 5 (quinary systems), the authors found a way to do this. They used a clever "merging" technique. Imagine you have several groups of ribbons. Some groups are very similar, differing only in one tiny spot. The authors showed how to take two groups, find the exact spot where they differ, and weave them together into a bigger group, while still keeping the "change only one thing" rule intact.

They proved that for sizes based on powers of 3 and 5 (like $3^2, 3^3, 5^2$ , etc.), you can always find a way to stitch these ribbons together to form a full-period code. This means the code can represent every single possible position ( $m^{m^t}$ codewords) without missing any.

What They Didn't Do (And What They Ruled Out)

It is important to know what this paper is not saying.

It's not a magic wand for all numbers: The authors explicitly state that for binary systems (using only 0 and 1), you cannot make a full-period single-track code for any size except $n=2$ . They proved this is impossible for larger binary wheels.
It's not for every prime yet: While they proved it works for 3 and 5, they admit that for larger prime numbers (like 7, 11, 13), they haven't found the "seed" ribbons yet. They suspect the recipe works, but they need to find the starting pattern first.
It's not for non-prime numbers (mostly): They showed a specific example for size 4, but their main, rigorous proof is for prime numbers.

The Verdict

The paper doesn't just suggest these codes might exist; it proves they do for an infinite family of sizes based on the numbers 3 and 5. They provided the mathematical "blueprints" (the recursive construction) and the "starter kits" (the seeds for $p=3$ and $p=5$ ) to build them.

For the curious teenager or the engineer designing a high-speed sensor, this is a big deal. It means that for a whole new class of machines, we can now build encoders that are smaller, more precise, and less prone to errors. The authors have opened a door, showing that with the right mathematical tools, we can organize information in ways that were previously thought impossible. They didn't just find a needle in a haystack; they built a machine that can find needles in an infinite number of haystacks, as long as those haystacks are made of 3s and 5s.

Technical Summary: Optimal Non-Binary Single-Track Gray Code

Problem Statement
The paper addresses the construction of Single-Track Gray Codes (STGCs) over non-binary alphabets. An STGC of length $n$ and period $P$ is a cyclic list of $P$ distinct words such that consecutive words differ in exactly one position, and the $n$ tracks (columns) of the code array are cyclic shifts of a single track. While binary STGCs with full period ( $P=2^n$ ) are known to exist only for $n=2$ , and the maximum period for $n > 2$ is limited to $2^n - 2^n$ , the paper investigates the existence of such codes over larger alphabets. Specifically, it seeks to construct STGCs of length $n = p^t$ and period $P = p^{p^t}$ over the finite field $\mathbb{F}_p$ (where $p$ is a prime), which would represent full-period codes for these parameters.

Methodology
The authors employ a recursive construction strategy based on Non-Binary Self-Dual Sequences (SDSs). The methodology proceeds through the following steps:

Generalization of Binary Constructions: The paper adapts existing binary STGC construction theorems (specifically Theorem 2 from prior work involving self-dual sequences) to non-binary alphabets $\mathbb{Z}_m$ . This adaptation (Theorem 4) requires an ordering of $r$ pairwise inequivalent SDSs of period $m^n$ such that consecutive sequences differ in exactly $m$ coordinates, with specific conditions on the shift operator $E$ and the difference set.
Recursive Generation of SDSs: A core component of the work is a recursive method to generate SDSs over $\mathbb{Z}_p$ $Z_{p}$ (where $p$ $p$ is an odd prime).
- Base Case: For a given period $p^t$ , an SDS has the form $[X, X+1, \dots, X+(p-1)]$ .
- Recursive Step: To construct an SDS of period $p^{t+1}$ from one of period $p^t$ , the authors define a new word $V$ using a base word $Z$ (starting with zero) and auxiliary words $Y_1, \dots, Y_{p-2}$ . The new SDS is formed as $[V, V+1, \dots, V+(p-1)]$ .
- Combinatorial Counting: The paper proves that this construction yields the exact number of distinct SDSs required ( $p^{p^t - t - 1}$ ) by enumerating the choices for $Z$ and the $Y$ vectors.
Arrangement and Merging: The critical challenge is arranging these generated SDSs into a sequence that satisfies the STGC adjacency conditions (differing in exactly one coordinate in the final code).
- The authors define properties (P1) and (P2) regarding the positions where consecutive SDSs differ.
- A complex merging process is described (detailed for $p=3$ ) where components of SDSs are combined. This involves partitioning words by weight and merging lists $A(Z, Y)$ such that the resulting sequence of SDSs maintains the required difference properties.
- The merging logic ensures that the set of difference positions $D_{p^{t+1}}$ covers all necessary indices $\{0, 1, \dots, p^t - 1\}$ .

Key Contributions and Results

Existence Proof: The paper proves the existence of full-period non-binary STGCs of length $n = p^t$ and period $P = p^{p^t}$ over $\mathbb{F}_p$ for the specific primes $p=3$ and $p=5$ , for all $t \ge 2$ .
Recursive Framework: It provides a general recursive construction framework for any odd prime $p$ . The construction is conditional on the existence of an "appropriate seed"—a specific arrangement of all SDSs of period $p^2$ (or period 27 for $p=3$ ) that satisfies the initial arrangement properties.
Specific Seeds: The authors provide the necessary seeds for $p=3$ (729 SDSs of period 27) and $p=5$ (detailed in Appendices A and B), thereby completing the construction for these two cases.
Non-Prime Alphabets: The paper notes that while the primary focus is on prime fields, indications exist that such codes may also exist for non-prime alphabet sizes (demonstrated for $m=4$ in Example 3).

Significance and Claims
The paper claims to present the first and only known two infinite families of full-period Single-Track Gray Codes (for $p=3$ and $p=5$ ). The significance lies in overcoming the limitation found in binary codes where full-period STGCs do not exist for $n > 2$ . By utilizing non-binary alphabets, the authors achieve codes that contain all possible words of length $n$ ( $P = p^{p^t}$ ), which is optimal for quantization and coding applications requiring high resolution with a single physical track.

The authors modestly state that for primes $p > 5$ , the construction is theoretically valid but requires the discovery of appropriate seeds (arrangements of SDSs of period $p^2$ ). They identify the search for these seeds for larger primes, as well as the generalization of the "complemented cycling register" to non-binary alphabets, as primary directions for future research. The paper does not claim to have solved the problem for all primes or non-prime sizes, but rather establishes the existence for $p=3$ and $p=5$ and outlines the path for others.

The Building Blocks: The "Self-Dual" Ribbons

The Assembly Line: Stitching the Ribbons Together

What They Didn't Do (And What They Ruled Out)

The Verdict

More like this