Mathematical proof note · Version 1.0 · October 16, 2026
Binary Cyclic Codes with Simultaneously Near-Linear Minimum and Dual Distances
National Mobile Communications Research Laboratory and the Frontiers Science Center for Mobile Information Communication and Security, Southeast University, Nanjing 211189, China
Abstract
For every odd integer m ≥ 3, put n = 2m − 1. We give a self-contained probabilistic proof that ordinary binary cyclic codes of dimension (n − 1)/2 can have both minimum distance and dual distance at least (1/2 − o(1))n/(m log2 m). A finite-length sufficient condition is H2(δ) + δ ≤ 1/(2m). The proof counts only low-weight words whose zeroth coordinate is one. Shift symmetry contributes a factor δ to the count, and a first-moment estimate for random reciprocal-factor choices completes the argument. A probability-tending-to-one version has the same leading distance constant.
Full text and source
Scope
This is a probabilistic existence theorem. The scalar condition is sufficient, not necessary. The guaranteed relative distance tends to zero; no fixed positive relative distance or efficient deterministic generator-selection algorithm is claimed.
Keywords
binary cyclic codes; minimum distance; dual distance; self-orthogonal codes; cyclic rank; entropy method; probabilistic existence.
中文关键词：二元循环码；最小距离；对偶距离；自正交码；循环秩；熵方法；概率存在性。
Suggested citation
S. Yang, "Binary Cyclic Codes with Simultaneously Near-Linear Minimum and Dual Distances," mathematical proof note, version 1.0, Oct. 16, 2026. [Online]. Available: https://github.com/stalin1943/Coding-Theory-Proof-Notes/blob/main/binary-cyclic-minimum-dual-distance/proof.pdf