Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 4 min ago
PreprintarXiv licencearXiv

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

  • Weiguo Gao
  • Zhi Shan
Open at sourcePDFDOICite

Abstract

We prove the 3/4 conjecture for q-ary fix-free codes with at most three distinct codeword lengths, for every integer q≥2. 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.

Related

  1. On the lengths of MDS codes with a two-transitive permutation automorphism group
    Haihua Deng, Tao Feng, Andrey V. Vasil'ev
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. A proof of Ward's conjecture on Griesmer codes
    Haihua Deng, Weiye Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Counterexamples to Charpin's Conjecture on BCH codes
    Run Zheng, Yaoran Yang, Yutong Zhang +2
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  4. Auxiliary Codes and the Generalized Packing-Covering Conjecture
    Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  5. DS and AMDS Symbol-Pair Codes from Three Families of Simple Root Cyclic Codes
    Jiawei He, Zihan Zhang, Xiaoqiang Wang +1
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{gao2026conjecture,
  title = {{The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths}},
  author = {Weiguo Gao and Zhi Shan},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.18237},
  eprint = {2609.18237},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.18237},
}
RIS
TY  - UNPB
TI  - The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths
AU  - Weiguo Gao
AU  - Zhi Shan
PY  - 2026
DA  - 2026/09/20
PB  - arXiv
DO  - 10.48550/arxiv.2609.18237
UR  - https://arxiv.org/abs/2609.18237
AB  - We prove the 3/4 conjecture for q-ary fix-free codes with at most three distinct codeword lengths, for every integer q≥2. 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.
ER  -