Cardinality control for prefix-free codes preserving weighted occurrence sums: Kraizberg's weak commutative-equivalence approximation

For every finite binary code $C$, Kraizberg (arXiv:2603.27656, 2026) proved that there exists a prefix-free code $C'$ such that for every word length $k$ the sums $\sum 2^{[w]_a}$ over codewords of length $k$ coincide between $C$ and $C'$, where $[w]_a$ counts occurrences of the letter $a$. This is a weak structural form of commutative equivalence, motivated by the Schützenberger commutative equivalence conjecture for maximal codes and constrained by Shor's counterexample to the unrestricted conjecture. The paper's tree-based construction gives no control on $|C'|$, and Remark 1.10 shows exact cardinality equality is impossible in general. The paper explicitly asks whether $C'$ can always be chosen with $||C|-|C'|| = O(|C|)$, or even $O(1)$. No subsequent work addressing this question is known; it remains open.

Background

A code over the binary alphabet $\{a,b\}$ is a set of finite words in which every concatenation of codewords decodes uniquely (a uniquely decodable set); a prefix-free code is a code in which no codeword is a prefix of another, the standard structure making decoding instantaneous. Two finite codes $C_1, C_2$ are commutatively equivalent if there is a bijection $f:C_1\to C_2$ preserving the number of occurrences of each letter in every word (i.e., preserving Parikh vectors, the vectors of per-letter occurrence counts). Perrin and Schützenberger asked whether every finite code is commutatively equivalent to a prefix-free code; Schützenberger later restricted the conjecture to maximal codes — codes to which no word can be added without destroying unique decodability — yielding the Commutative Equivalence Conjecture (the history and partial results are covered in Berstel, Perrin, and Reutenauer's monograph Codes and Automata). Shor (1985), disproving the related triangle conjecture, exhibited a finite code $C_{Shor}=b\{1,a,a^7,a^{13},a^{14}\}\cup\{a^3,a^8\}b\{1,a^2,a^4,a^6\}\cup a^{11}b\{1,a,a^2\}$ that is not commutatively equivalent to any prefix-free code, so the unrestricted conjecture is false; Mauceri and Restivo (1981) exhibited families of codes that are commutatively equivalent to prefix codes. In this context, Dean Kraizberg (arXiv:2603.27656, March 2026) established a weak structural surrogate: writing $[w]_a$ for the number of occurrences of $a$ in $w$, his Theorem 1.9 states that for every code $C$ there exists a prefix-free code $C'$ such that for every $k$, $\sum_{w\in C,|w|=k}2^{[w]_a}=\sum_{w'\in C',|w'|=k}2^{[w']_a}$. The proof goes through a bijection between prefix-free codes and a class of rooted trees called symmetric trees (every branching vertex has two identical child subtrees), under which the number of leaves at depth $k$ equals the length-$k$ weighted sum above; each codeword $w'$ of the associated prefix-free code corresponds to exactly $2^{[w']_a}$ leaves of the tree, so the constructed tree has $\sum_{w\in C}2^{[w]_a}$ leaves in total and the construction controls the cardinality of $C'$ only through the coarse bound $|C'|\le\sum_{w\in C}2^{[w]_a}$, which can exceed $|C|$ by as much as $\sum_w(2^{[w]_a}-1)$, a potentially enormous gap. Kraizberg's Remark 1.10 shows the gap cannot always be zero: a prefix-free $C'$ satisfying the Theorem 1.9 conclusion for $C_{Shor}$ with $|C'|=|C_{Shor}|$ would be commutatively equivalent to $C_{Shor}$, contradicting Shor's result. The paper's Section 3 (Further Discussion) then asks how small the gap can be, which is the present problem. Kraizberg also states, with proof omitted, an extension to alphabets of size $A$: for each letter $a$ there is a prefix-free $C'$ over the same alphabet with $\sum_{w\in C,|w|=k}A^{k-[w]_a}$ matched for all $k\ge A$; the paper poses the cardinality question explicitly only for the binary theorem, to which this extension is a natural analogue.

Problem Statement

For every finite binary code $C$, Kraizberg's Theorem 1.9 guarantees 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}$ for every $k$, where $[w]_a$ is the number of occurrences of the letter $a$ in $w$. The open question, posed in Section 3 of arXiv:2603.27656: can $C'$ always be chosen so that $||C|-|C'||=O(|C|)$? Can it even be chosen so that $||C|-|C'||=O(1)$? That is, determine (with proof) the optimal uniform control on the cardinality gap between a code and a prefix-free code satisfying the per-length weighted-sum identity. The two tiers are nested — a gap of $O(1)$ implies a gap of $O(|C|)$. The paper poses this cardinality question explicitly for the binary theorem (Theorem 1.9).

References

1. Dean Kraizberg, "A Weak Structural Form of Commutative Equivalence in Finite Codes", arXiv:2603.27656 (2026), https://arxiv.org/abs/2603.27656
2. P. W. Shor, "A counterexample to the triangle conjecture", Journal of Combinatorial Theory, Series A 38(1):110–112 (1985), DOI 10.1016/0097-3165(85)90032-9, https://doi.org/10.1016/0097-3165(85)90032-9
3. S. Mauceri and A. Restivo, "A family of codes commutatively equivalent to prefix codes", Information Processing Letters 12(1):1–4 (1981), DOI 10.1016/0020-0190(81)90064-8, https://doi.org/10.1016/0020-0190(81)90064-8
4. J. Berstel, D. Perrin, and C. Reutenauer, "Codes and Automata", Encyclopedia of Mathematics and its Applications 129, Cambridge University Press (2009), DOI 10.1017/CBO9781139195768, ISBN 9780521888318, https://doi.org/10.1017/CBO9781139195768
5. Dean Kraizberg, "Winning Criteria for Open Games: A Game-Theoretic Approach to Prefix Codes", arXiv:2601.17521 (2026), https://arxiv.org/abs/2601.17521