ロバスト軌道問題（エラー補正） ↔︎ abc予想
“Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture” (arXiv:2405.15368)
https://arxiv.org/pdf/2405.15368
1. ロバスト軌道問題（Robust Orbit Problem）とは？
数学や物理、情報科学では、ある対象（ベクトルやデータなど）に対称性（群の作用）が働くとき、その作用によって移り変わる軌跡を 「軌道（Orbit）」 と呼びます。
- 従来の軌道問題： 「与えられた2つのデータが、全く同じ軌道上にあるか（対称性を介して完全に一致させられるか）」を判定する問題。
- ロバスト軌道問題（エラー補正）： 現実のデータにはノイズやエラーが含まれます。そのため、「2つのデータが（エラーを許容して）近似的に同じ軌道上にあるか、それとも完全に離れているか」を、一定の近似比（誤差の許容度 γ）の範囲内で判定する問題です。これはまさに、エラー補正（Error Correction）や最適化、量子情報科学などで重要となる設定です。
この論文では、特にトーラス作用（Torus Actions：可換な連続群の作用）という、比較的扱いやすいはずの対称性を持った空間（C^n）でのロバスト軌道問題を対象にしています。
2. abc予想（abc-conjecture）とは？
数論における最も重要で有名な未解決問題（あるいは議論が続いている問題）の一つです。
自然数 a + b = c （互いに素）という極めて単純な足し算において、それぞれの数に含まれる「異なる素因数の積（根基：radical）」が、元の数 cと比べてどれほど小さくなり得るかを制限する予想です。
簡単に言うと、「足し算（a+b=c）と掛け算（素因数分解）の構造は、互いに強い制約を与え合っている」という数論の根本的な性質を主張しています。
3. この論文が明かした「2つの繋がり」
この論文の最大の貢献は、「ロバスト軌道問題を効率的に解くアルゴリズムが、多項式時間（実用的なスピード）で動作するかどうかは、数論の『abc予想』が正しいかどうかに完全に依存している」 という事実を証明した点です。具体的には、著者たち（P. Bürgisser, M. L. Doğan, V. Makam, M. Walter, A. Wigderson）は以下の2つの側面を示しました。
① アルゴリズムの限界（NP困難性）
誤差の許容度 γ が非常に小さい（厳密に近い）場合、このロバスト軌道問題は格子暗号の基盤となる「最短ベクトル問題（CVP）」と同等以上に難しくなり、NP困難（一般に効率的には解けない） であることを示しました。
② abc予想が握る「効率的なアルゴリズム」の鍵
一方で、誤差の許容度 γ を指数関数的な大きさ（exp(poly(n))）まで広げると、不変式論（Invariant Theory）と格子理論の高度なツールを組み合わせた新しい近似アルゴリズムを構築することに成功しました。このアルゴリズムは、2つの軌道が「近い」という証拠（群の要素）を実際に計算して出力してくれます。
そして、この「提案したエラー補正アルゴリズムが、多項式時間（実用的な時間）で終了するかどうか」を数学的に評価したところ、それが「abc予想（の特定のバージョン）が真であること」と必要十分条件（同値）になることが判明しました。
- エラー補正問題の複雑さの境界：ノイズやエラーを含んだデータの対称性を判定・補正する「ロバスト軌道問題」において、どのレベルのノイズまでなら計算科学的に効率よく処理（エラー補正）できるかという限界を明確にしました。
- コンピューターサイエンスと数論の架け橋：一見すると、データの最適化やエラー補正という「実用的なアルゴリズムの計算量」の話をしているはずなのに、そのアルゴリズムが速いかどうかを証明するためには、純粋数学の最深部にある「整数と素数の絡み合い（abc予想）」を解き明かさなければならないという、数学的同型性を示しました。
abc予想
a + b = cが「abc予想」の文脈において、「abc予想通り（反例に近づくような、珍しい関係性）」になる組み合わせのことを、数論では「abc-triple（abcの三つ組）」、あるいはその極端な例を「クオリティが高い（Quality > 1）」組み合わせと呼びます。
abc予想は、簡単に言うと「a, b, c のそれぞれの素因数をすべて掛け合わせた数（根基 rad(abc)）は、基本的には c よりも大きくなる。c の方が大きくなるようなケースは非常に珍しい」という予想です。
この「珍しいケース（c > rad(abc) となる組み合わせ）」を、c が小さい順（1から順に探索した場合）に並べると、最初の5つは以下のようになります。
c > rad(abc) となる組み合わせ（c の小さい順トップ5）
【前提ルール】
- a, b, c は互いに素（共通の公約数を持たない）正の整数。
- a < b とします。
- rad(abc) ＝ a, b, c に含まれるすべての素因数を1回ずつ掛け合わせたもの。
- 通常はc<rad(abc)となる。1+2=3で3<6
① 1 + 8 = 9 （最も小さい組み合わせ）
- 式: 1 + 8 = 9 → 1 + 2^3 = 3^2
- 素因数の積 rad(abc): 1 * 2 * 3 = 6
- 比較: c = 9 なので、 9 > 6 となり条件を満たします。
② 1 + 80 = 81
- 式: 1 + 80 = 81
- 1 + (2^4* 5) = 3^4
- 素因数の積 rad}(abc): 1 * 2 * 5 * 3 = 30
- 比較: c = 81 なので、 81 > 30 となり条件を満たします。
③ 32 + 49 = 81
- 式: 32 + 49 = 81
- 2^5 + 7^2 = 3^4
- 素因数の積 rad(abc): 2 * 7 * 3 = 42
- 比較: c = 81 なので、 81 > 42 となり条件を満たします。
④ 1 + 242 = 243
- 式: 1 + 242 = 243
- 1 + (2 * 11^2) = 3^5
- 素因数の積 rad(abc): 1 *2 *11*3 = 66
- 比較: c = 243 なので、 243 > 66 となり条件を満たします。
⑤（正） 1 + 512 = 513
- 式: 1 + 512 = 513
- 1 + 2^9 = 3^3 * 19
- 素因数の積 rad(abc): 1 * 2 * 3 * 19 = 114
- 比較: c = 513 なので、 513 > 114となり条件を満たします。
なぜこれらが「abc予想通り」の珍しい数なのか？
数学的には、これらの数を「クオリティ（Quality）」という指標で評価します。クオリティの計算式は以下の通りです。
$$q(a,b,c) = \frac{\log c}{\log(\text{rad}(abc))}$$
この値が q > 1 になるもの
| 順位 (cの小さい順) | a | b | c | rad(abc) | クオリティ (q) |
| 1 | 1 | 8 (2^3) | 9 (3^2) | 6 | 1.2263 |
| 2 | 1 | 80 (2^4 *5) | 81 (3^4) | 30 | 1.2920 |
| 3 | 32 (2^5) | 49 (7^2) | 81 (3^4) | 42 | 1.1764 |
| 4 | 1 | 242 (2 * 11^2) | 243 (3^5) | 66 | 1.3105 |
| 5 | 1 | 512 (2^9) | 513 (3^3 * 19) | 114 | 1.3179 |
これらは「小さな素数がたくさん掛け合わされた数（累乗数）」が足し算で偶然結びついた時にしか現れません。
abc予想は、「クオリティ q が 1 を大きく超えるような（例えば 1 + ε を超えるような）組み合わせは、無限には存在せず、高々有限個しか存在しない」 ということを主張しています。