🔢 mathematics

Degree-Four Vector-Coordinate SoS Cannot Detect the MUB Upper Bound

本論文は、次数4の二乗和緩和において、ベクトル座標形式を用いた手法は（ $m > d+1$ の場合であっても）既知の互いに直交する基底（MUB）の個数の上限を検出できないのに対し、射影体座標形式を用いた手法は同次数でこの上限を正常に復元できることを確立するものである。

原著者： Shreyhaan Sarkar

公開日 2026-06-15

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Shreyhaan Sarkar

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

全体像：「完璧に偏りのない」友人たちのゲーム

あなたが、 $d$ 次元の部屋（高次元空間）でパーティーを計画していると想像してください。あなたは、特定のパターンで立つように、いくつかのグループ（基底）を招待したいと考えています。

「相互に偏りのない基底（MUB）」のルールは、完璧なバランスを求めるゲームのようなものです：

グループ内では： 全員が互いに完璧に直角（直交）に立っていなければなりません。
グループ間では： もしグループAから一人、グループBから一人を選んだ場合、その二人の間の「角度」は、あらゆる組み合わせにおいて全く同じでなければなりません。彼らは互いに「偏りがない（unbiased）」状態です。

数学者は、このゲームには厳しい限界があることを知っています。そのようなグループは、最大でも $d + 1$ 個までしか作れません。例えば、6 次元の部屋（ $d=6$ ）では、最大で 7 つのグループを持つことができます。6 次元の部屋において、実際にその限界である 7 に到達できるのか、それともその前にルールが崩壊してしまうのかというのは、有名な未解決の謎です。

問題：コンピュータは「限界」を見抜けるか？

この論文は、Sum-of-Squares (SoS) と呼ばれる一種のコンピュータ・アルゴリズムに関する具体的な問いを投げかけています。SoS を、非常に賢いが、少し近視眼的な「探偵」だと考えてください。探偵は、人々の位置を記述する数学方程式を調べることで、ある配置が不可能であることを証明しようとします。

この探偵には「次数（degree）」の制限があります。次数 4 の探偵は、一度に最大 4 つの変数（例えば、4 人のポジションがどのように相互作用するか）の関係性しか見ることができません。

具体的な問い（「Open Problem 23」より）はこうでした：「次数 4 の探偵は、6 次元の部屋に 7 つのグループが存在することは不可能であると証明できるか？」

発見：探偵は間違った地図を使っている

著者である Shreyhaan Sarkar は、答えは「その人々をどのように探偵に記述するか」に完全に依存するということを発見しました。

1. 「ベクトル」による記述（失敗）

最初の手法では、探偵には、あらゆる人の頭、手、足の生の座標（ベクトルの実部と虚部）が与えられます。

トリック： 著者は、ランダムで独立した人々のグループを用いて、「偽の現実」を構築しました。この偽の世界では、グループは厳密な意味での「相互に偏りのない」状態ではありませんが、もし「次数 4 のレンズ」を通して見るならば、それらは完璧に偏りがないように見えます。
比喩： 群衆のぼやけた写真を見ているところを想像してください。遠くから（次数 4 で）見ると、その群衆は完璧にバランスが取れていてランダムに見えます。探偵は数学的計算を行い、すべてがゼロに収束しているのを見て、「ほら、この配置は可能だ！」と言ってしまいます。
結果： この「偽の現実（疑似期待値と呼ばれるもの）」によって探偵が欺かれるため、探偵は「7 つのグループは不可能である」と証明することができません。それは限界（ $d+1$ ）を見落としてしまいます。たとえ 6 次元室に 7 つのグループが存在するのは間違いだと分かっていても、100 個のグループが可能であるかもしれないと判断してしまうのです。

2. 「射影（プロジェクター）」による記述（成功）

次に、著者は人々の記述方法を変えて試みました。人々の手足の座標を教える代わりに、各人が落とす影や射影（数学的には $P = vv^*$ ）の記述を教えたのです。

違い： この「射影」の言語では、「偏りのなさ」に関するルールがずっと単純になります（4 次ではなく 2 次になります）。
結果： この地図を使って探偵が動くと、「偽の現実」のトリックはもはや通用しません。次数 4 の探偵は、明確に数学的な矛盾を見つけ出すことができます。それは、グループを $d+1$ 個より多く作ることは不可能であると、見事に証明します。

主な要点

この論文は、問題が解けない理由は数学が難しいからではなく、記述が弱すぎるからであると結論付けています。

ベクトル座標： パズルのピースを一つずつバラバラに見ながら、パズルを解こうとしているようなものです。次数 4 の探偵は混乱し、本来は解けないはずのパズルが解けると思い込んでしまいます。
射影座標： パズルの箱に描かれた絵を見ているようなものです。次数 4 の探偵はすぐにパターンを見抜き、そのパズルが不可能であることを理解できます。

なぜこれが特定の問いにとって重要なのか

この論文は、2 つの「ベクトル」手法について問うた「Randomstrasse101 Open Problem 23」に直接答えています。

答え： いいえ。 それらの特定のベクトル記述を用いた次数 4 の Sum-of-Squares 証明では、6 次元において 7 つの MUB が存在しないことを証明することはできません。
注意点： これは、いかなる証明も存在しないという意味ではありません。単に、この特定の、直接的な問題の書き方は、次数 4 のアルゴリズムにとっては弱すぎるという意味です。もし「射影」の書き方に切り替えれば、アルゴリズムは限界を見つけ出すのに十分な強さを持つようになります。

要約すると： この論文は、問題を生の座標を使って記述すると、限られた「視力」を持つコンピュータ（次数 4）は、不可能なことが可能であるという錯覚に陥ることを示しています。しかし、問題を「影（射影）」を使って記述すれば、同じコンピュータでも真実を見抜くことができるのです。

技術要約：次数4のベクトル座標型SoSはMUBの上界を検出できない

問題提起
本論文は、 $\mathbb{C}^6$ において7つの互いに直交する基底（MUB）が存在しないことを証明するために、次数4の和の平方（Sum-of-Squares; SoS）証明が存在するかどうかを問う Randomstrasse101 Open Problem 23 を扱っている。この問題は、以下の2つの特定のベクトル座標エンコーディングを用いて定式化されている：

4次等式定式化（Quartic Equality Formulation）: 制約は、ベクトル成分の実部および虚部に関する4次の関係式、具体的には $|\langle v, w \rangle|^2 = 1/d$ としてエンコードされる。
$2 \times 2$ ヘルミシャン半定値定式化（ $2 \times 2$ Hermitian Semidefinite Formulation）: 基底間の条件は、2次の内積 $\langle v, w \rangle$ を含む $2 \times 2$ ヘルミシャン行列に関する半定値制約としてエンコードされる。

より広い背景として、次元 $d$ における MUB の数 $m \le d + 1$ という既知の上界がある。素数冪の次元では等号が成立するが、 $d=6$ のケースは未解決であり、 $m=7$ は不可能であるという予想がある。

手法
著者らは、次数4の擬似期待値（pseudoexpectations）を構成することにより、次数4のSoS緩和の能力を分析している。次数4の擬似期待値とは、高々次数4の多項式に対する線形汎関数 $\tilde{\mathbb{E}}$ であり、正値性（ $\tilde{\mathbb{E}}[f^2] \ge 0$ ）および制約との整合性を満たすものである。このような擬似期待値が存在する場合、そのシステムに対して次数4のSoS反駁（不可能性の証明）は存在しない。

核心となる手法は以下の通りである：

Haarランダム構成: 著者らは、独立なHaarランダムユニタリ行列に基づく期待値に基づく擬似期待値を定義する。具体的には、 $m$ 個の基底に対し、ベクトルは独立なHaarランダムユニタリ行列の列として取られる。
制約の検証:
- 同一基底内の制約: ランダム構成において、直交性は点ごとに（正確に）成立する。
- 異なる基底間の制約: 独立なHaarランダム単位ベクトル $x, y$ に対して、 $\mathbb{E}[|\langle x, y \rangle|^2] = 1/d$ が成立する。
アフィン乗数解析（Affine Multiplier Analysis）: 半定値定式化において、著者らは、内積 $z = \langle x, y \rangle$ によるアフィン線形関数への乗算の演算子ノルムに関する特定の境界を証明する。彼らは、 $|\mathbb{E}[p z q]| \le \frac{1}{d} \sqrt{\mathbb{E}[|p|^2]\mathbb{E}[|q|^2]}$ が成り立つことを示す。
定式化の比較: 論文では、ベクトル座標定式化と、変数がランク1の射影演算子 $P = vv^*$ である**射影座標定式化（projector-coordinate formulation）**を対比させている。この設定では、基底間の直交条件は2次（ $\text{Tr}(P_i^{(k)} P_j^{(\ell)}) = 1/d$ ）となる。

主要な貢献および結果

ベクトル座標定式化に対する下界:
主要な結果（定理5.1および7.1）は、任意の次元 $d$ および任意の提案された基底数 $m$ に対して、標準的なベクトル座標MUBシステムが、独立なHaarランダム基底から導かれる次数4の擬似期待値を許容することを確立している。
- 4次等式: この擬似期待値は4次の制約を満たす。なぜなら、4次の項 $|\langle x, y \rangle|^2 - 1/d$ の期待値はゼロだからである。制約は次数4であるため、次数4の反駁はこれらに定数を掛けることしかできず、擬似期待値によってこれらは消滅する。
- 半定値定式化: アフィン乗数境界（定理6.1）を用いて、著者らは、この擬似期待値が $2 \times 2$ ヘルミシャン行列に対する次数4の局所化制約を満たすことを示す。
- 帰結: これらのベクトル座標定式化における次数4のSoSは、 $m > d + 1$ （MUBが存在しない、あるいは存在しないと予想される場合でも）において、 $m$ 個のMUBの存在を反駁できない。具体的には、 $d=6, m=7$ の場合、これらのエンコーディングにおいて、非存在を示す次数4のSoS証明は存在しない。
定式化による分離（射影器 vs ベクトル）:
論文は、この失敗がベクトル座標エンコーディングに特有であることを示している。変数が中心化された射影演算子 $Q = P - I/d$ である射影座標定式化（定理8.1）においては、基底間の直交条件は2次である。
- 著者らは、 $m > d + 1$ のとき、射影座標システムに対する次数4のSoS反駁を構成できる。
- この反駁は、射影演算子の平方和のトレースを含むグラム行列の恒等式を利用しており、これは $m > d + 1$ の場合に制約の下で負の定数を与える。
- 結果: 次数4のSoSは、射影器定式化において、基本的な上界 $m \le d + 1$ を確かに回収することができる。

意義および主張
本論文は、MUB問題における低次SoS階層の能力に関する定式化依存の分離を主張している：

Open Problem 23への否定的回答: 問題文に記載された2つの特定のベクトル座標エンコーディング（4次方程式および $2 \times 2$ LMI）に関して、答えは否定的である。次数4のSoSは、基本的な計数上の障害（ $m \le d + 1$ ）を検出するには本質的に弱すぎる。
定式化の感受性: 低次SoSの失敗は、手法自体の普遍的な限界ではなく、直接的なベクトル座標緩和の限界である。同じ次数レベルの緩和であっても、射影器座標に適用された場合は厳密に強力であり、既知の上界を正常に回収できる。
$d=6$ への含意: 射影器定式化は $d=6$ において $m \le 7$ を回収するが、論文では $d=6, m=7$ のケースがこの境界の「タイト」な境界であることを指摘している。したがって、この分離結果は、より強力な射影器変数を用いた次数4の証明が、正確に7つのMUBを排除できるかどうかを決定的に答えるものではない（少なくとも、8つ以上を排除できることは示している）。

本研究は、ベクトル座標SoSにおける特定の次数4の障害を特定しており、次元6のMUB問題に対する成功的な低次SoSアプローチは、直接的なベクトル座標ではなく、リフトされた定式化（射影器など）を利用する必要があることを示唆している。