🔢 mathematics

A Weak Structural Form of Commutative Equivalence in Finite Codes

This paper establishes a canonical correspondence between binary prefix-free codes and symmetric unlabeled rooted trees to demonstrate that every code is commutatively equivalent to a prefix-free code sharing specific structural properties regarding the sums of powers of two determined by a distinguished symbol.

Original authors: Dean Kraizberg

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dean Kraizberg

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 a master architect designing a library. In this library, every book has a unique barcode (a code) made of two types of bricks: Red bricks (let's call them 'a') and Blue bricks (let's call them 'b').

The Problem: The "Unbreakable" Library

In a perfect library, you want a Prefix-Free Code. This is a rule where no book's barcode is the beginning of another book's barcode.

Example: If you have a book with the barcode Red-Blue, you cannot have another book with Red-Blue-Red. If you did, a scanner reading Red-Blue-Red wouldn't know if it was reading the first book or the second one.

For a long time, mathematicians had a big question: If you have a messy collection of barcodes (a "code") that isn't prefix-free, can you always rearrange them into a perfect, prefix-free library that looks exactly the same in terms of the count of Red and Blue bricks?

They thought the answer was "Yes." But then, a mathematician named Peter Shor found a tricky, messy collection of barcodes that could not be rearranged into a perfect prefix-free library without changing the number of Red or Blue bricks. The "Perfect Rearrangement" conjecture was broken.

The New Discovery: A "Weak" but Useful Equivalence

The author of this paper, Dean Kraizberg, says, "Okay, we can't match the exact count of Red and Blue bricks for every single book. But what if we look at the library as a whole, grouped by the length of the barcodes?"

He introduces a new concept called Symmetric Trees.

The Analogy: The Family Tree

Imagine a family tree where every person (node) has children.

Symmetric Tree: This is a special family tree where, if a parent has at least two children, at least two of those children must have identical families growing out of them. It's like having twin branches on a tree that look exactly the same.

The paper proves a magical connection:

Every Prefix-Free Code (the perfect library) can be turned into a Symmetric Tree.
Every Symmetric Tree can be turned back into a Prefix-Free Code.

But here is the twist: The tree doesn't just count the total number of books. It counts them in a very specific way based on how many Red bricks ('a') are in the barcode.

The Main Result: The "Red Brick" Balance

The paper's big achievement (Theorem 1.9) is this:

Even if you have that messy, impossible-to-fix collection of barcodes (Shor's counterexample), you can always find a new perfect prefix-free library that matches the original one in a specific way:

For every length of barcode (e.g., all 5-brick codes), the total "Red Power" is identical.

What is "Red Power"?

If a barcode has 2 Red bricks, its power is $2^2 = 4$ .
If it has 3 Red bricks, its power is $2^3 = 8$ .
The paper proves that if you add up these powers for all books of a certain length in the messy library, you can find a perfect library where the sum is exactly the same.

How They Did It (The Magic Trick)

The author uses a clever construction involving a "3-ary tree" (a tree where branches can split into three).

They take the messy code and imagine it as a tree.
They realize that because the tree is "symmetric" (it has twin branches), they can swap things around.
They use a mathematical "sieve" (Lemma 2.6) to show that if you have enough "Red Power" in the messy pile, you can always pick out a specific set of perfect barcodes that add up to the exact same number.

Think of it like this: You have a pile of coins of different values. You can't rearrange the coins to make the exact same list of coins as the original pile, but you can rearrange them to make a new pile where the total value of the coins in every "size bucket" is exactly the same.

Why Does This Matter?

This is a "Weak Structural Form" of equivalence.

Strong Equivalence (Failed): "I can make a new library where Book A has the same number of Red bricks as Book A in the old library." (Impossible for some cases).
Weak Equivalence (Success): "I can make a new library where the total number of Red bricks across all 5-letter books is the same as the old library." (Always possible).

The Takeaway

The paper tells us that while we can't always perfectly match every single book's composition when fixing a messy code, the overall structure of the "Red bricks" is preserved in a beautiful, symmetric way. It's like saying that even if you can't rearrange the furniture in a room to look exactly like the blueprint, you can always rearrange it so that the total amount of "wood" in the room remains exactly the same.

This gives mathematicians a new tool to understand the deep relationship between messy codes and perfect trees, opening the door to solving other puzzles in information theory.

1. Problem Statement and Context

Background:
The paper addresses the Commutative Equivalence Conjecture in coding theory. Two codes $C_1$ and $C_2$ are commutatively equivalent if there exists a bijection between them preserving the count of each symbol in every codeword (i.e., $[w]_a = [f(w)]_a$ and $[w]_b = [f(w)]_b$ ).

The Conjecture: Originally, it was conjectured that every code is commutatively equivalent to a prefix-free code.
The Counterexample: Peter Shor disproved this by constructing a specific code ( $C_{Shor}$ ) that is not commutatively equivalent to any prefix-free code.
The Open Question: While the general conjecture is false, it remains open whether it holds for maximal codes (Schützenberger's Conjecture). Furthermore, even if exact commutative equivalence fails, does a weaker structural equivalence exist?

The Core Problem:
The author investigates whether, for any given finite code $C$ , there exists a prefix-free code $C'$ such that they share specific structural invariants related to symbol occurrences, even if they are not strictly commutatively equivalent. Specifically, the paper seeks to preserve the weighted sum of codeword lengths based on the number of occurrences of a distinguished symbol (e.g., 'a').

2. Methodology

The paper employs a novel combinatorial framework linking coding theory with graph theory, specifically utilizing Symmetric Trees.

A. Symmetric Trees

The author introduces a specific class of rooted trees called symmetric trees.

Definition: A finite rooted tree where every vertex with at least two children has at least two distinct children whose rooted subtrees are identical.
Constraint: These trees are viewed as subtrees of a full 3-ary tree (alphabet $\{a, a^{-1}, b\}$ ).

B. Canonical Correspondence (The Bridge)

The central methodological contribution is establishing a bijective correspondence between prefix-free codes over the binary alphabet $\{a, b\}$ and symmetric trees.

The Mapping: The author constructs a mapping involving the Cayley graph of the free group $F(a, b)$ $F (a, b)$ .
- A prefix-free code $C$ is lifted into a labeled tree structure within the Cayley graph.
- By projecting this structure onto specific coordinates, a symmetric tree $T$ is derived.
The Invariant: Under this correspondence, the number of leaves at depth $k$ in the symmetric tree, denoted $|L_k(T)|$ , equals the sum of powers of two determined by the occurrences of 'a' in the codewords of length $k$ :
$|L_k(T)| = \sum_{w \in C, |w|=k} 2^{[w]_a}$

C. Inductive Construction

To prove the main theorem, the author uses an inductive argument on the size of the code $|C|$ :

Base Case: Trivial for single-word codes.
Inductive Step: Given a code $C$ and a maximal length word $c_M$ , the author constructs a symmetric tree for $C \setminus \{c_M\}$ .
Extension and Adjustment: The tree is extended to depth $M$ $M$ . The author analyzes the "gap" between the current leaf count and the required count for $c_M$ $c_{M}$ .
- Lemma 2.6 (Subset Sum): A number-theoretic lemma is used to show that if the sum of powers of two is sufficient, a subset can be found to match a specific target power ( $2^{[c_M]_a}$ ).
- Tree Modification: If a direct subset isn't available, the author performs "adjustments" on the tree structure (swapping nodes or shifting vacancies) to create space for the required word without altering the total leaf counts at other depths.

3. Key Contributions

Definition of Symmetric Trees: The introduction of symmetric trees as a structural proxy for prefix-free codes, preserving specific weighted length distributions.
Bijective Correspondence (Theorem 1.8): Proving a one-to-one mapping between prefix-free codes and symmetric trees that preserves the quantity $\sum 2^{[w]_a}$ for each length.
Weak Commutative Equivalence (Theorem 1.9): Establishing that for every finite code $C$ (not just maximal ones), there exists a prefix-free code $C'$ such that:
$\sum_{w \in C, |w|=k} 2^{[w]_a} = \sum_{w' \in C', |w'|=k} 2^{[w']_a}$
This holds for every length $k$ .
Generalization: The results extend to arbitrary finite alphabets, replacing the base 2 with the alphabet size $A$ and adjusting the weight function accordingly.

4. Main Results

Theorem 1.8: There is a bijection between prefix-free codes and symmetric trees. The number of leaves at depth $k$ in the tree corresponds exactly to the sum of $2^{[w]_a}$ for all codewords $w$ of length $k$ in the code.
Theorem 1.9 (Main Result): For any finite code $C$ , there exists a prefix-free code $C'$ that is "weakly commutatively equivalent" to $C$ . Specifically, they share the same distribution of the weighted sum $2^{[w]_a}$ across all word lengths.
Cardinality Note (Remark 1.10): The prefix-free code $C'$ constructed in Theorem 1.9 does not necessarily have the same cardinality as $C$ . If $|C| = |C'|$ , then $C$ and $C'$ would be strictly commutatively equivalent. Since Shor's counterexample proves that some codes are not commutatively equivalent to any prefix-free code of the same size, the construction in Theorem 1.9 generally requires $|C| \neq |C'|$ .

5. Significance and Implications

Refining the Equivalence Conjecture: The paper demonstrates that while the strong conjecture (exact commutative equivalence with equal cardinality) is false, a structural weak equivalence holds universally. This suggests that the "obstruction" to commutative equivalence lies in the specific arrangement of symbols within words of the same length, rather than the aggregate distribution of symbol counts.
New Structural Tool: The introduction of symmetric trees provides a powerful new tool for analyzing prefix-free codes. It translates complex coding problems into tree-structural problems, potentially allowing for new proofs in information theory and combinatorics on words.
Resolution of Shor's Counterexample Context: The results clarify why Shor's code fails the strong conjecture: while a prefix-free code exists that matches the "weighted sum" invariants, it cannot match the cardinality. This quantifies the "distance" between a general code and a prefix-free code.
Future Directions: The paper opens questions regarding the cardinality gap $||C| - |C'||$ . It asks whether this gap is bounded by $O(|C|)$ or even $O(1)$ , suggesting a path for further research into the efficiency of this weak equivalence.

In summary, Kraizberg provides a rigorous structural framework showing that every code can be transformed into a prefix-free code that preserves a specific, weighted measure of symbol distribution, thereby offering a nuanced, "weak" resolution to the long-standing commutative equivalence problem.