ある種の4次元図形は、どんなアルゴリズムにも見分けられない

レシピの存在しない問いがある。まだ誰も見つけていないからではない。どんなアルゴリズムも、つまりどれほど長くても、どんなコンピューターで実行しても、一歩一歩進む手順では、それにいつも正しく答えることはできないと証明されているからだ。テキサス大学オースティン校のCameron McA. Gordonは、4次元の図形について、そうした問いを2つ付け加えた。

同じ図形だろうか

数学者はこうした図形を4次元多様体と呼ぶ。近くで見ると、どこでも普通の4次元空間のように見える空間だ。コンピューターに渡せるように、論文ではこれらが平らな部品を貼り合わせてつくられている（「区分線形」、PL）と仮定する。そうすれば、それぞれを有限個のデータのリストで記述できる。基本的な問いはこうなる。そのような図形が2つ与えられたとき、連続的な変形を除いて、両者は同じだろうか。

1958年、A. A. マルコフは、この問いにはアルゴリズムが存在しないことを示した。マルコフの証明は、図形の問題を群の問題に変える。有限個の規則で定義される群のなかには、その元の与えられた組み合わせが単位元に等しいかどうかを、どんなアルゴリズムも判定できないものがある。これが「語の問題」だ。そのような群から、その不可能な問題を解かない限りアルゴリズムでは区別できない図形をつくることができる。

7個へのカウントダウン

マルコフの議論は、難しさを特定の図形にまで絞り込みさえする。普通のボールの表面であるS²をとり、直積S² × S²をつくる。これは4次元の図形だ。そのk個を貼り合わせる（「連結和」と呼ばれ、#kと書く）。あるkについては、与えられた図形が#k(S² × S²)であるかどうかを判定できるアルゴリズムは存在しない。そのkはいくつか。

論文はこのカウントダウンをたどる。1969年にBorisovが見つけた、語の問題が解けない、規則が12個の群からは、14個が得られた。Gordonは2022年にそれを12個にした。M. Tancerは、フリードマンによる4次元図形の分類を通る新しい道筋を見つけ、図形が平らな部品からつくられていなくてもよい「位相的」な場合で9個に到達した。この研究の以前の版は8個に達していた。その後、Kegel、Li、Renが、生成元3個と規則9個という、はるかに小さな解けない群をつくり、位相的な場合で7個、平らな部品の場合で9個に到達した。

Gordonは、Tancerの道筋を平らな部品からつくられた図形にも使えるようにし、次のことを証明した。

与えられた4次元多様体が、S² × S²を7個連結和したものと、部品ごとに見て同じかどうかを判定するアルゴリズムは存在しない。

証明の核心は辞書だ。Kegel、Li、Renの群の各語wに対して、Gordonは4次元の図形を1つつくる。wが単位元に等しければ、規則に対する許された一連の変形、つまり図形を変えずに記述を書き換えるAndrews-Curtis変形によって、その図形がちょうどS² × S²の7個分であることが示される。等しくなければ、その図形は1点に縮められないループを含む。S² × S²の7個分ではそういうことは決して起こらないので、その図形はその7個分ではありえない。したがって、#7(S² × S²)を見分けるアルゴリズムがあれば語の問題が解けてしまうが、それは不可能である。

結ばれた球面

2つ目の問いは結び目に関するものだ。普通の結び目は3次元空間の中で結ばれた円で、結び目がほどけるかどうかは判定できる。ハーケンによるアルゴリズムがあるのだ。次元を1つ上げると、2次元の球面が4次元空間の中で結ばれることがある。より高い次元では、対応する問題にアルゴリズムが存在しないことが知られている。4次元球面S⁴の中の2次元球面については、誰にもわからない。

Gordonは、連結和#7(S² × S²)の中で、2次元球面が、あるいは向き付け可能かどうかによらずどんな曲面でも、結ばれていないかどうかを判定するアルゴリズムは存在しないことを証明した。その過程で論文は、この図形の中に、周りの空間の群が解けない語の問題をもつような球面をつくり、さらにS² × S²の12個分の中に、その群がコンピューターで記述できるすべての群のコピーを含むような球面をつくっている。

目標：0個

論文は目標をはっきり述べている。コピーの数を0まで下げることだ。0個とは、4次元球面S⁴そのものを意味する。5次元以上では球面を見分けるアルゴリズムは存在せず、2次元と3次元では存在する。4次元はまだ未解決であり、S⁴の中の結ばれた球面を検出できるかという問いも同様だ。1個減らすごとに、両方の問いに近づいていく。