Semidefinite programming bounds for binary codes from a split Terwilliger algebra

研究問題與主要成果

A(n,d)表示長度n、任意兩個不同碼字Hamming距離至少d的二元碼最大大小；碼不必線性。本文將座標分區，保留更細的三點距離資訊，再利用split Terwilliger algebra導出半正定限制。作者以此把A(18,4)的已知上界由6552改善為6551，並估計對偶誤差以支持整數上界。這不是6551碼字的建構，也不是證明A(18,4)=6551。ISIT2022的相關會議版本與此文可共用這組導讀資源。

從距離分布到三點限制

距離分布A_j是距離j的有序碼字對數除以|C|，因此A₀=1、ΣA_j=|C|，1≤j<d時A_j=0。Delsarte LP另要求Krawtchouk轉換非負。Schrijver SDP則看三元組(X,Y,Z)：把X以XOR平移到零，記兩個相對支持集大小i、j及交集t，第三邊距離便為i+j−2t。三點資訊比兩點分布更細，可排除某些雖滿足距離平均、卻不符合局部幾何的候選解。

半正定性與對稱化

碼的指示向量χ給出外積χχᵀ，因vᵀχχᵀv=(vᵀχ)²≥0而半正定。對等距變換取平均，並依零字是否在變換後的碼中分成R與R′，仍保留半正定性。固定零字後的座標置換軌道由(i,j,t)描述，形成Terwilliger代數；其維度為binom(n+3,3)，可分成大小n−2k+1的區塊。這裡須區分包含平移的全等距群與固定零字的穩定子，否則個別重量i、j並不被保留。

分割如何保留更多資訊

把座標分為T₁、T₂，大小n₁+n₂=n。同一總距離4可分為(0,4)、(1,3)、(2,2)，一般距離分布會把這些不同情況合併。分割三元組使用六個索引(i,j,t;i′,j′,t′)，並對兩區分別計算支持大小與交疊。最小距離限制必須用總三邊距離，不能要求每一區都至少d。三條邊的分區向量也必須同步置換，不能在兩區各自隨意交換。

張量積讓新限制可計算

分割軌道矩陣等於兩個局部矩陣的Kronecker乘積，因此A_(n₁,n₂)≅A_(n₁)⊗A_(n₂)。區塊(k,k′)大小為(n₁−2k+1)(n₂−2k′+1)。在18=2+16時，每個PSD家族有18個區塊，最大51階，相較原矩陣262144階小得多。這是代數同構下去除重複表示，不是任意裁切。R_s與R′_s兩種條件平均各提供一組新限制，不能只保留其中一種便宣稱得到相同結果。

變數、目標與線性一致性

三元組計數λ以|C|及軌道大小正規化成x；軌道大小須包括「只在第一支持、只在第二支持、兩者都有、兩者都無」四類座標的階乘，分割時取兩區乘積。目標Σbinom(n₁,i)binom(n₂,i′)x_pair仍是碼大小。變數滿足0≤x_triplet≤x_pair≤1、正規化、邊置換與禁距離條件。原始λ可由分割λ相加，正規化x卻必須帶軌道比例聚合，不能直接求和。原文多項係數的剩餘階乘漏項，導讀依正確軌道計數解釋。

為何還要加入已知限制

R_s與R′_s的非負線性組合落在分割Bose–Mesner代數，同時對角化可推出ΣA_(i,j)K_p^(n₁)(i)K_q^(n₂)(j)≥0，所以split SDP包含split Delsarte頻譜限制。實際模型還整合原始Schrijver PSD、Best與Mounits–Etzion–Litsyn不等式，以及常重量、雙常重量碼上界。例如A_i≤A(n,d,i)，因固定碼字平移後，其距離i鄰居形成常重量碼。加強LP有額外組合限制，故不能只以「SDP」名稱判定任何設定都優於它。

對偶誤差如何變成可靠上界

設原始SDP為max c·x，F₀+Σx_iF_i⪰0。若對偶Y⪰0且tr(F_iY)+c_i=0，弱對偶性給c·x≤tr(F₀Y)。浮點殘差ε_i=tr(F_iY)+c_i可用0≤x_i≤1補償，得到上界tr(F₀Y)+Σmax(0,ε_i)。此式仍要求Y半正定，不能只修正等式殘差而忽略負特徵值。原文稱變數negative是筆誤，應為nonnegative。本導讀轉述作者的驗證，沒有重新執行求解器或獨立審核完整數值證書。

6551已驗證，13087尚未驗證

Theorem19使用2+16分割，報告A(18,4)≤6551.93且誤差項小於10^(−16)，利用碼大小整數便得≤6551。另一組較少限制給6551.98，也跨過相同整數門檻。對A(19,4)，9+10分割的求解值約13087.5，但保守誤差估計高達215.7376，相加13303.2376，無法改善原文比較上界13104。因此不能把13087寫成本文已證定理；軟體正常結束或作者相信數值正確，都不能取代所需認證。

方法關係、延伸與來源

作者證明四點SDP可推出R_s的PSD限制，但是否也包含R′_s限制在原文未解決；不能由單一參數的改善推論普遍支配。m分區可用各局部代數張量積推廣，但平衡分區變數量約O((n/m)^(3m))，成本迅速增加。常重量、非二元碼與其他association schemes是後續方向。來源：Pin-Chieh Tseng、Ching-Yi Lai、Wei-Hsuan Yu，Semidefinite programming bounds for binary codes from a split Terwilliger algebra，arXiv:2203.06568v4（2023）；相關ISIT2022會議版本。