Semidefinite programming bounds for spherical three-distance sets

問題與23維的答案

球面三距離集合是R^n中的有限單位向量集，不同點的內積恰有三種值d₁<d₂<d₃；因||x−y||²=2−2〈x,y〉，也等價於三種歐氏距離。本文結合調和維度界、Nozaki整數性、半正定規劃與平方和，證明23維最大大小為2300。已知4600點的反足tight7-design每對取一點可得2300點三距離集合，內積為−1/3、0、1/3，提供下界；全域上界則必須涵蓋所有可能的三內積，不能只檢查這個特殊構造。

調和界與特殊內積算例

一般Delsarte–Goethals–Seidel上界為n(n+1)(n+5)/6，在23維是2576。若固定三個內積，取f(x)=Π(x−d_i)，使f(1)>0，展開成正規化Gegenbauer基底；正係數所對應的調和空間維度之和給上界。對−1/3、0、1/3，f=x³−x/9=(2/225)G₁+(22/25)G₃，故|X|≤h₁+h₃=23+2277=2300。原文乘積符號與例子係數不一致，導讀採上述一致規約。此算例只是固定內積的上界，尚未處理其他候選。

從兩點LP到三點SDP

球面調和加法公式給Σ_(x,y)G_k(〈x,y〉)≥0，導出平均鄰居數的LP限制。SDP再看三點內積(u,v,t)，將兩向量投影到第一向量的正交補空間，得到(t−uv)/sqrt((1−u²)(1−v²))的投影內積，再構成Bachoc–Vallentin矩陣核並對六種置換對稱化。本文使用13個三元組計數變數：3種重複點型態與10種不同點型態；搭配非負計數、2×2矩條件、LP次數18及SDP核次數6。其目標為1+(x₁+x₂+x₃)/3，變數正規化與LP不同。

整數條件把搜尋降為一維

Nozaki定理指出，N=h₀+h₁+h₂=n(n+3)/2且|X|≥2N時，K_i=Π_(j≠i)(d_j−1)/(d_j−d_i)為有界整數；較小集合直接由2N−1控制。Lagrange插值給ΣK_i=Σd_iK_i=Σd_i²K_i=1。固定有限種整數三元組，令a=d₃，便能將d₁、d₂寫成a的仿射函數，再保留合法順序的區間。23維N=299，小集合上界597，原文列66種整數三元組；特殊構造對應(3,−8,6)。整數參數可行不代表實際點集必然存在。

兩種上界互補

對每個候選參數，取harmonic bound與SDP bound的較小者，再對所有候選取最大，並納入小集合門檻。靠近某些端點時LP／SDP可能變大，但harmonic bound仍能控制；另一部分區域則靠SDP改善。23維中(1,−3,3)與(2,−6,5)分支的取樣LP最大值約2385.60、2319.82，而SDP約1072.29、1693.01。這些最大值未必發生在相同參數，更不能把有限取樣結果直接當成整段區間的嚴格上界。

為何取樣圖還不是證明

即使網格很密、圖形看起來平滑，兩個取樣點之間仍可能出現更大的值。本文因此把對偶限制改寫成單變數a的多項式非負條件，尋找在整個[L,U]上可行的同一組對偶變數，使對偶目標成為統一上界。這同時涉及連續參數覆蓋與數值可行性；只檢查求解器沒有警告，或只保存幾個網格點的答案，都不能取代所需的區間證書。

平方和如何變成半正定規劃

令a=(L+Uz²)/(1+z²)，對m次多項式f乘上(1+z²)^m，得到F(z)。有限z涵蓋[L,U)，端點U以極限與連續性補入，因此區間非負性可轉為整條實線上的一元多項式非負性。一元非負多項式可寫成平方和，亦即F=vᵀQv、Q⪰0，v=(1,z,…,z^m)。係數比對是線性條件，故可用SDP尋找Q。這個等價是單變數的重要特性，不能擴張成所有多變數非負多項式都必為平方和。

整數門檻的重要細節

Table5在23維、K=(3,−8,6)、a∈[0.332,0.335]報告SOS上界2300.85。它其實大於2300，與原文「所有SOS值都小於harmonic bound」的文字不完全一致；但2300.85<2301，加上|X|是整數，仍可推出≤2300。導讀採這個正確解釋。其他關鍵分支有1234.62與1703.71等值。表格只列關鍵區間，完整論證仍需所有分支與區間覆蓋，以及矩陣與係數的可驗證性；本導讀未獨立重跑完整證書。

六個維度的成果與未解問題

相對原文引用的舊上界，n=7由91降84，n=20由1541降1540，n=21由1772降1771，n=23由2301降2300，n=24由2601降2600，n=25由2926降2925。23維因已知構造而得到精確答案；其他改善不能都寫成等號。7維原文已知下界64，半個E₇只有63點。PSL(2,7)群軌道與能量最小化搜尋未找到84點，並不證明84點不存在，也不能把作者的期待寫成已完成構造。

方法意義與來源

本文的價值在於把有限整數分類、局部凸最佳化與連續區間的平方和控制接起來，展示由計算探索走向全域上界的路徑。它沒有給所有維度的閉式最大值，也沒有證明每個tight7-design的半集必定全域最大。來源：Feng-Yuan Liu、Wei-Hsuan Yu，Semidefinite programming bounds for spherical three-distance sets，arXiv:2005.01324v1（2020）。導讀中的數值比較是此版本報告的歷史成果，不宣稱是2026年的最新紀錄。