New code upper bounds for the folded n-cube

Folded cube 中的碼是什麼

二元 Hamming cube 的頂點是長度 n 的 0–1 字串，距離為不同座標數。Folded cube 把 x 與逐位互補的 x̄ 視為同一點 [x]，因此共有 2ⁿ⁻¹ 點，距離變成 δ([x],[y])=min{h(x,y),n−h(x,y)}，直徑 D=floor(n/2)。本篇要求不同碼字的 folded 距離至少 d，並研究最大可能大小 A(□ₙ,d)。一般 Hamming 碼不能直接沿用最小距離，因為折疊也會把接近互補的點拉近。

從兩點分布到三點資訊

Delsarte 線性規劃以兩點距離分布及 Bose–Mesner 代數的正半定性限制碼大小。作者推廣 Schrijver 的方法，固定一個基點，加入相對基點的距離層投影 Eᵢ*，與鄰接矩陣 A₁ 共同生成 Terwilliger 代數 T。這個通常不交換的代數保留三點相容資訊，有機會排除只用兩點分布時容許的形式解。它仍是上界放鬆，並不保證每個可行分布都能實現為碼。

三點軌道與偶數邊界

把三點的第一點送到零後，以 i、j 表示另外兩點到零的距離，t 表示支撐交集大小，第三距離為 min{i+j−2t,n−(i+j−2t)}。奇數長度每個互補對有唯一較小支撐代表；偶數長度的最外層則沒有，因此 t 要按原文規則對互補代表取最大交集。最外層點數也由 binom(n,D) 除以二。這些邊界因子會影響軌道矩陣、區塊係數與目標函數。

代數基底與多項式規模

用 Mᵢⱼᵗ 表示指定三點型態的零一指示矩陣。作者證明，固定基點的自同構群不變矩陣所形成的代數，恰好就是 T。其維數在 n=2D+1 時為 (D+1)(D+2)(2D+3)/6，在 n=2D 時為 (D+1)(D²+2D+3)/3，因此只有 O(n³) 個參數。證明藉由距離層間升降算子的乘積與二項式反演，把每個軌道矩陣寫入 T。

區塊對角化才真正縮小 PSD 檢查

標準空間可分解成 thin 不可約 T 模組，每個距離層在模組中至多一維，且 endpoint r 決定模組類型。奇數長度的區塊階數為 D+1−r；偶數長度則在 r 偶數時為 D+1−r、r 奇數時為 D−r，D 奇數時沒有 r=D 模組。刪除重複副本後，n=8 的 128 階矩陣只需檢查 5、3、3、1、1 階區塊；n=9 則從 256 階降成 5、4、3、2、1 階。

三點變數與目標函數

令 λᵢⱼᵗ 計數碼 C 的有序三元組中指定型態的數量，γᵢⱼᵗ 是固定基點後軌道矩陣的非零項數，定義 xᵢⱼᵗ=λᵢⱼᵗ/(|C|γᵢⱼᵗ)。若第 i 距離層大小為 kᵢ，則 |C|=Σkᵢxᵢ₀⁰。目標函數因此是三點變數的線性式；偶數最外層的 kᴅ 必須除以二。正規化還給 x₀₀⁰=1、非負性、上限、軌道重標號對稱，以及禁距離的零條件。

兩個平均矩陣帶來雙重 PSD 限制

碼的指示向量外積 χ_C χ_C^T 本來就是正半定。對含基點零的自同構像取平均，得到 M′=ΣxᵢⱼᵗMᵢⱼᵗ；對不含零的自同構像取平均，移除正比例因子後得到 Σ(xν₀⁰−xᵢⱼᵗ)Mᵢⱼᵗ，其中 ν 是第三 folded 距離。第二個矩陣不是補集碼的指示矩陣。把兩者搬到不可約小區塊，就得到原文的 SDP；其係數是明確的二項式和。

為何是上界，且至少不弱於 LP

每個真實碼都產生 SDP 可行分布，而且目標值等於碼大小，所以放鬆後的最大值給 A(□ₙ,d) 上界。兩個平均矩陣組合後回到全群不變的距離矩陣，故 SDP 的可行分布也滿足 Delsarte LP 條件；新上界只會更小或相等。原文以 O(n³) 變數與 O(n) 個線性階數區塊控制計算規模。數值上，primal 可行解本身不是上界證書，仍需 dual 可行性或適當誤差控制。

數值成果與一項可直接核對的版本疑點

2018 年 v1 報告 (n,d)=(10,3) 的界由 32 改善為 24，(12,4) 由 85 為 54，(11,4) 由 27 為 20；此導讀未重跑這些 SDP。但同表 n=8、d=2 所列 28 與定義衝突：偶同位元的互補對明確給 64 個碼字，逐對驗證最小 folded 距離為 2；翻轉固定座標給完美匹配，反向得到上界 64，故 A(□₈,2)=64。本教材不採用 28，也不推斷尚未取得的期刊全文是否已修正。

閱讀重點與來源

本篇核心是 folded cube 的三點軌道、Terwilliger 代數基底與可實作區塊分解，讓更強的凸最佳化上界成為可能。使用時須注意偶數邊界、兩個 PSD 條件、正規化，以及數值證書的方向。來源：Lihang Hou、Bo Hou、Suogang Gao、Wei-Hsuan Yu，New code upper bounds for the folded n-cube，arXiv:1801.06971v1（2018）；Journal of Combinatorial Theory, Series A 172（2020），105182，DOI:10.1016/j.jcta.2019.105182。