Kraizberg (arXiv:2603.27656, 2026) proved that every finite binary code CC admits a prefix-free code C′C' matching its per-length power sums: for every word length kk, the sum of 2[w]a2^{[w]_a} over codewords of length kk, where [w]a[w]_a counts occurrences of a distinguished letter aa, is the same for CC and C′C'. This is a weak structural surrogate for commutative equivalence of codes, a notion going back to Perrin and Schützenberger whose general conjecture was disproved by Shor (1985) and whose maximal-code restriction remains open. Shor's counterexample also shows ∣C′∣=∣C∣|C'|=|C| cannot always be achieved, and the paper asks how close in cardinality C′C' can be chosen: is a discrepancy ∣∣C∣−∣C′∣∣=O(∣C∣)||C|-|C'||=O(|C|) always achievable, or even O(1)O(1)? This problem record asks, as the paper does, for a determination of the asymptotic behaviour of the minimal achievable cardinality discrepancy under the weighted per-length equality, for the binary case. No bounds on this quantity exist anywhere in the literature; the question has been untouched since its posing.

Background

A (finite) code is a finite set CC of words over the binary alphabet {a,b}\{a,b\} in which every concatenation of codewords factors uniquely into codewords (unique decodability). A prefix-free code is one where no codeword is a prefix of another; such codes are exactly the instantaneously decodable ones. The Kraft–McMillan theorem states that the codeword lengths of any code over an alphabet of size kk satisfy ∑w∈Ck−∣w∣≤1\sum_{w\in C}k^{-|w|}\le 1, and conversely every multiset of lengths satisfying this inequality is realized by a prefix-free code; in particular every code is length-equivalent to a prefix-free code. Perrin and Schützenberger (1977) introduced a stronger comparison: two codes are commutatively equivalent if there is a bijection between them that maps each word to an anagram of itself, i.e. preserves the number of occurrences of each letter ([w]a[w]_a and [w]b[w]_b for the letters a,ba,b). They conjectured that every finite code is commutatively equivalent to a prefix-free code; Shor (1985) disproved this by exhibiting an explicit finite code not commutatively equivalent to any prefix-free code. The conjecture survives in restricted form for maximal codes — codes to which no word can be added without destroying unique decodability — where it remains a well-known open problem (partial results include the family of Mauceri and Restivo, 1981). Against this background, Kraizberg (2026) introduced symmetric trees — finite rooted subtrees of the full 3-ary tree in which every vertex with at least two children has two children whose entire rooted subtrees are identical — and established a bijective correspondence between prefix-free binary codes and symmetric trees under which the number of leaves at depth kk equals the power sum ∑w∈C,∣w∣=k2[w]a\sum_{w\in C,|w|=k}2^{[w]_a} (lifting a Cayley-graph construction from his earlier work on prefix codes and open games). From this he deduced Theorem 1.9: for every binary code CC there exists a prefix-free code C′C' with, for every kk, ∑w∈C,∣w∣=k2[w]a=∑w′∈C′,∣w′∣=k2[w′]a\sum_{w\in C,|w|=k}2^{[w]_a}=\sum_{w'\in C',|w'|=k}2^{[w']_a} — a weak structural form of commutative equivalence that keeps a per-length weighted trace of the letter statistics while dropping the bijection. Genuine commutative equivalence would give the same per-length equalities together with ∣C′∣=∣C∣|C'|=|C|; conversely, Remark 1.10 of the paper shows that requiring ∣C′∣=∣C∣|C'|=|C| in Theorem 1.9 would force commutative equivalence on Shor's example, so equal cardinality is not always possible. The paper's Section 3 extends the statement to an alphabet of size AA with weights Ak−[w]aA^{k-[w]_a} (for each distinguished letter and each k≥Ak\ge A), omitting the detailed proof, and poses the quantitative question that is the subject of this record.

Problem Statement

Let CC be a finite code (uniquely decodable set of words) over the binary alphabet {a,b}\{a,b\}, and for a word ww write [w]a[w]_a for the number of occurrences of the letter aa in ww. Call a prefix-free code C′C' weight-equivalent to CC if for every kk, ∑w∈C, ∣w∣=k2[w]a  =  ∑w′∈C′, ∣w′∣=k2[w′]a.\sum_{w\in C,\ |w|=k} 2^{[w]_a} \;=\; \sum_{w'\in C',\ |w'|=k} 2^{[w']_a}. Theorem 1.9 of Kraizberg (2026) guarantees that every CC has a weight-equivalent prefix-free C′C', while Remark 1.10 (via Shor's counterexample) shows one cannot always demand ∣C′∣=∣C∣|C'|=|C|. Define the minimal achievable discrepancy d(C)  =  min⁡ { ∣∣C∣−∣C′∣∣  :  C′ prefix-free and weight-equivalent to C },d(C)\;=\;\min\,\{\,||C|-|C'||\;:\; C' \text{ prefix-free and weight-equivalent to } C\,\}, where the minimum exists because the set is nonempty by Theorem 1.9 and takes values in the nonnegative integers. Determine d(C)d(C) up to order: (i) is d(C)=O(1)d(C)=O(1) over all finite binary codes CC? (ii) if not, is d(C)=O(∣C∣)d(C)=O(|C|)? The objective is to quantify the cardinality price of the weak commutative-equivalence surrogate: how far from genuine commutative equivalence (which would give discrepancy 00) does the weighted per-length matching force one to stray.

References

  1. Dean Kraizberg, A Weak Structural Form of Commutative Equivalence in Finite Codes, arXiv:2603.27656 (2026), DOI 10.48550/arxiv.2603.27656, 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. D. Perrin and M. P. Schützenberger, Un problème élémentaire de la théorie de l'information, in Théorie de l'Information, Colloques Internationaux CNRS vol. 276, Cachan (1977), pp. 249–260 (proceedings volume dated 1978 in zbMATH), zbMATH record 3760085, https://zbmath.org/3760085
  4. M. P. Schützenberger, Codes à longueur variable, manuscript in D. Perrin (ed.), Actes de la 7ème École de Printemps d'Informatique Théorique, LITP and ENSTA (1980), pp. 247–271.
  5. 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
  6. Jean Berstel, Dominique Perrin, and Christophe Reutenauer, Codes and Automata, Encyclopedia of Mathematics and its Applications vol. 129, Cambridge University Press (2009), ISBN 978-0-521-88831-8, DOI 10.1017/CBO9781139195768, https://doi.org/10.1017/CBO9781139195768
  7. Dean Kraizberg, Winning Criteria for Open Games: A Game-Theoretic Approach to Prefix Codes, arXiv:2601.17521 (2026), https://arxiv.org/abs/2601.17521
  8. Clelia De Felice, Finite maximal codes and factorizations of cyclic groups, arXiv:2202.09675 (2022), https://arxiv.org/abs/2202.09675
  9. Christophe Cordero, Factorizations of Cyclic Groups and Bayonet Codes, arXiv:2301.13566 (2023), https://arxiv.org/abs/2301.13566
  10. Christophe Cordero, A note with computer exploration on the triangle conjecture, in Language and Automata Theory and Applications (LATA 2019), Lecture Notes in Computer Science vol. 11417, Springer (2019), pp. 409–420, DOI 10.1007/978-3-030-13435-8_30, https://doi.org/10.1007/978-3-030-13435-8_30