On the size of maximal binary codes with 2, 3, and 4 distances

研究問題：限制距離的種類

本文研究二元碼中不同碼字之間只出現少數距離時，最多可以放多少碼字。Hamming距離d_H計算不同座標數；s-distance code指所有不同碼字對的距離恰有s種，並不是最小距離等於s，也不要求碼為線性。主要完整結果是對每個n≥6，A(H₂ⁿ,2)=1+binom(n,2)。下界很直接：取零向量及所有重量2的向量，任兩個不同碼字距離只會是2或4。n=6時此構造有16字。困難在於上界必須涵蓋任何可能的兩個距離，而不只構造使用的2與4。

把Hamming問題轉成等角線問題

將二元字x映成v(x)=((-1)^x₁,…,(-1)^xₙ)/sqrt(n)，便有〈v(x),v(y)〉=1−2d_H(x,y)/n。設距離a>b對應內積α<β。若a+b≤n，可直接套用二距離調和上界得到目標；若a+b>n，則α+β<0。新增正交單位向量e，令y_i=t v_i+sqrt(1−t²)e、t²=2/(2−α−β)，新內積變成±1/γ，其中γ=(a+b)/(a−b)。因此原碼嵌入R^(n+1)的等角線集合，可使用既有等角線上界。

如何處理少數例外

等角線估計一般已給|C|≤binom(n,2)，只留下γ為奇整數且n=γ²−2或γ²−3的例外。令γ=2m+1，再利用距離的整數性、a+b>n與b≤n/2，可把例外縮成a=(m+1)(2m+1)、b=m(2m+1)。若兩內積都負，Rankin界早已足夠。剩下的參數再用球面二距離上界(n+2)/(1−(n−1)/(n(1−α)(1−β)))處理，分母在所用條件下為正。n=6、a=6、b=3可直接算得96/7；其餘例外也低於目標整數門檻，於是上下界吻合。

固定重量：距離等價於交集

Johnson空間J^(n,w)由所有重量w的字組成，可視為n元素集合的w子集，通常假設2w≤n。Johnson距離d_J(A,B)=w−|A∩B|=d_H(A,B)/2；必須注意它只有Hamming距離的一半。標準s距離構造固定w−s個共同元素，再從其餘n−w+s個元素中選s個，得到binom(n−w+s,s)個碼字與距離1到s。例如n=12、w=4、s=2，固定{1,2}並從{3,…,12}再選兩元素，得到45字。這先給下界，最大性仍須排除所有其他距離組合。

禁止交集與EKR的角色

若禁止兩個w子集的交集恰為l，對每個固定l子集考慮包含它的成員，再刪除該l子集，剩餘族必兩兩相交。n≥2w−l時可用Erdős–Ko–Rado定理，再對所有l子集雙重計數，得到m(n,w,forbid l)≤(w−l)/(n−l)·binom(n,w)。l=0用通常EKR。由此對n≥2w得到A(J^(n,w),w−1)=binom(n−1,w−1)，由固定一個共同元素的星形族達成。這是一整族精確答案，也提醒讀者保留2w≤n的基本範圍。

Hahn多項式與可手算的對偶證書

在Johnson空間，正規化Hahn多項式滿足ψ_k(0)=1。若f_j表示距離d_j的平均鄰居數，則f_j≥0、|C|=1+Σf_j，而且Σf_jψ_k(d_j)≥−1。選非負權重y_k，使每個允許距離都滿足Σy_kψ_k(d_j)=−1，加總便得|C|≤1+Σy_k。對n=12、w=4、距離{1,2}，精確計算得ψ₄(1)=−1/8、ψ₄(2)=1/28、ψ₃(1)=1/16、ψ₃(2)=−1/14。取y₄=20、y₃=24，兩個距離的加權係數都為−1，故上界45，與共同核心構造吻合。

整數條件與精確範圍

Nozaki定理指出N=binom(n,s−1)且|C|≥2N時，K_i=Π_(j≠i)d_j/(d_j−d_i)為有界整數，因此只需細查少量距離組合；不符合者上界為2N−1。結合解析LP證書與小參數計算，兩距離Johnson碼在w=4、n≥9，w=5、n≥12，w=6、n≥35時分別達binom(n−w+2,2)。w=6另外15≤n≤24也由計算涵蓋，不能把25至34的缺口補成已證。三距離時w=5、6、7分別在n≥12、16、20達共同核心大小；四距離例如w=6、n≥15也得到精確答案。

小參數計算與三點資訊

解析行列式的符號往往只在充分大n成立，有限小n需要枚舉距離集合並求LP或Schrijver三點SDP。若2N−1仍高於目標，連未滿足整數條件的距離組合也不能略過。本文新增Johnson參數包括三距離(n,w)=(12,5)，以及四距離(15,6)、(16,6)。Hamming三距離則在8≤n≤22、24≤n≤37與n=44有A=n+binom(n,3)，新補入34與35。n=23的Golay相關2048字構造超過標準1794字，說明三距離情形不能直接推成所有n的統一等式。

一般猜想與方法限制

對固定w>s，本文討論充分大n時A(J^(n,w),s)=binom(n−w+s,s)的一般猜想，但沒有證明所有w,s。選定Hahn證書可給c(w,d₁,d₂)n²階上界；距離{1,2}得到正確首項1/2，但w=7、距離{2,4}只有35/64>1/2，不足以達到猜想所需的主項。這是方法限制，不是35n²/64構造的存在證明。即使最大大小已確定，也不等於所有最優碼已分類或唯一。原文部分表格與定理範圍、四距離二項式下標有差異，本導讀以定理及數值命題交叉核對。

來源與閱讀方式

來源為Alexander Barg、Alexey Glazyrin、Wei-Jiun Kao、Ching-Yi Lai、Pin-Chieh Tseng、Wei-Hsuan Yu，On the size of maximal binary codes with 2, 3, and 4 distances，arXiv:2210.07496v1（2022）。本文使用Mathematica、CVX與MOSEK，公開程式位於github.com/PinChiehTseng/s-distance-set。本導讀獨立以有理數重算45字證書，但未重跑全部LP與SDP，也不宣稱表格代表2026最新紀錄。建議先掌握Hamming球面嵌入，再跟算Johnson的45字例子，最後閱讀整數條件與漸近限制。