Metraipolis › archive › dc_d8658eeaae9e

The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths — arXiv:2609.18237

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.18237
License (as archived)
CC0-1.0
Archived
2026-10-15T16:14:04.271Z
SHA-256 of the archived text
6cae2f0570d66e26b2a17af36b5fff8bf3d8e0aff86b2c68aa3c92983ff3a622
Stable URL of this page
https://metraipolis.com/documento/dc_d8658eeaae9e

How to cite

The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths — arXiv:2609.18237 — arXiv (en), https://arxiv.org/abs/2609.18237 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d8658eeaae9e (Metraipolis archive dc_d8658eeaae9e, sha256 6cae2f0570d66e26b2a17af36b5fff8bf3d8e0aff86b2c68aa3c92983ff3a622)
BibTeX
@misc{dcd8658eeaae9e,
  title = {The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths — arXiv:2609.18237},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18237},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d8658eeaae9e; sha256 6cae2f0570d66e26b2a17af36b5fff8bf3d8e0aff86b2c68aa3c92983ff3a622},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.18237. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We prove the \(3/4\) conjecture for \(q\)-ary fix-free codes with at most three distinct codeword lengths, for every integer \(q\geq2\). Every prescribed length distribution with Kraft sum at most \(3/4\) is realized by a deterministic construction. We introduce a matrix approach based on an exact identity for the overlap between forbidden prefix extensions and suffix residuals. Natural numerical order fixes the shortest layer, and the remaining selection problem is expressed through row and column counts. A fixed-cardinality interpolation theorem supplies feasible sets of every intermediate cardinality between nested endpoints, provided their differences satisfy one-sided uniqueness and either acyclicity or integral slack. Reverse-order selection handles the uniform cases directly; in the remaining cases, layer completion and aligned groups provide endpoints for interpolation. Together, these methods extend the binary three-length result to arbitrary finite alphabets and give a deterministic procedure for constructing the code.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-17 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.18237 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T15:40:33.218Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).