黒峰問題が未解決問題に逆戻りした件について

「黒峰問題」と界隈で呼ばれている問題をご存知でしょうか。具体的には以下の問題です。

次を満たす整数 $(x, y, z)$ をすべて求めよ。

$\displaystyle 2^{x} + 3^{y} + 5 = z^{3}$

黒峰氏( @kuromineharuto ) が twitter で解答を求めたところいろんな人が群がり、ぷりんが勝手に「黒峰問題」と呼び出したのが最初だったと記憶しています。twitter で #黒峰問題で検索すると、いろいろな人が挑戦していたことが伺えると思います。

この問題について、実は1年ほど前に「解決宣言」をしています↓

#黒峰問題が解決しました！だまｼ氏( @dama_math )とふりっぐ氏( @41078129 )に大きく感謝します。6ページあるので続けてツイートします。 pic.twitter.com/J13n9DLh24
— すむーずぷりんちゃん🍮 (@mat_der_D) August 8, 2019

証明の大きな流れは以下のツイートの図にまとまっています。

一か所数字を間違えていたので直しました
(12029→12096) pic.twitter.com/Hj0ZOTqw3Q
— すむーずぷりんちゃん🍮 (@mat_der_D) August 8, 2019

最近 Julia を使ってこの証明を追試したところ、うっかり計算ミスを発見してしまいました。さらに悪いことに、この欠陥を未だ修正できていません。

この記事は、以上の経緯と具体的な内容について、以下の四段構成でお送りします。

黒峰問題の基本的性質と基本手筋
Julia のコードを使って黒峰問題を再検証した話
検証の結果計算ミスが見つかった話
ミスを修正しようと試みた話
まとめ

黒峰問題の基本的性質と基本手筋

改めて黒峰問題を眺めてみましょう。

次を満たす整数 $(x, y, z)$ をすべて求めよ。

$\displaystyle 2^{x} + 3^{y} + 5 = z^{3}$

ぐっと睨む*1と、次の解が見つかると思います。
$\displaystyle (x, y, z) = (1, 0, 2), (5, 3, 4)$
さらにいろいろ実験してみると「これ以外なさそうだな」という風に予想したくなります。この予想が正しいか？というのが黒峰問題の中心的関心です。
これに対して武器になるのはズバリ ${}\bmod{}$ です。数多の ${}\bmod{}$ をとることで、 $(x, y)$ が満たすべき条件を絞っていきます。
簡単な議論により, $x, y, z$ がいずれも非負の場合を考えれば十分であることが分かるので、以下ではこれを仮定します。
具体例をいくつか示します。まず $y = 0$ の場合を考えます:
$\displaystyle 2^{x} + 6 = z^{3}$ ここで ${}\bmod 4$ を考えると、それぞれ $x = 0, x = 1, x \geqq 2$ に対して
$\displaystyle \begin{aligned} -1 &\equiv z^{3} \pmod{4} \\ 0 &\equiv z^{3} \pmod{4} \\ 2 &\equiv z^{3} \pmod{4} \end{aligned}$ となります。一方で
$\displaystyle z^{3} \equiv 0^{3}, 1^{3}, 2^{3}, 3^{3} \equiv 0, \pm 1 \pmod{4}$ となるので、 $x \geqq 2$ はすべて不適になります。 $x = 0, 1$ の場合は、元の式にそれぞれ代入することで、方程式を満たすか簡単に調べることができます。
次に $y = 1$ の場合を考えましょう。方程式は
$\displaystyle 2^{x} + 8 = z^{3}$ となります。今度は ${}\bmod 7$ を考えます。このとき $2^{x} \equiv 1, 2, 4 \pmod{7}$ となることから、 $(左辺) \equiv 2, 3, 5 \pmod{7}$ となります。一方右辺は
$\displaystyle z^{3} \equiv 0^{3}, (\pm 1)^{3}, (\pm 2)^{3}, (\pm 3)^{3} \equiv 0, \pm 1 \pmod{7}$ となるので、等式が成立しえないことが分かります。
${}\bmod{}$ の威力は続きます。 $y \geqq 2$ の場合に ${}\bmod{9}$ を考えると、方程式は
$\displaystyle 2^{x} + 5 \equiv z^{3} \pmod{9}$ となります。先程と同様にして、 $2^{x} \equiv \pm 1, \pm 2, \pm 4 \pmod{9}$ より $2^{x}+5 \equiv 0, 1, 3, 4, 6, 7 \pmod{9}$ が従う一方で
$\displaystyle z^{3} \equiv 0^{3}, (\pm 1)^{3}, (\pm 2)^{3}, (\pm 3)^{3}, (\pm 4)^{3} \equiv 0, \pm 1 \pmod{9}$ となるので、 $2^{x} \equiv 4, 5 \pmod{9}$ が従います。このとき $x \equiv 2, 5 \pmod{6}$ すなわち $x \equiv 2 \pmod{3}$ が成り立ちます。
このような感じでどんどん条件を絞り込んで行きます。 $x \geqq 2$ が確定したので ${}\bmod{4}$ を考え、さらに ${}\bmod{7}$ を考えれば、
$\displaystyle (x \% 3, y \% 6) = (2, 3), (2, 5)$ が得られます。ここで $a \% b$ は「 $a$ を $b$ で割ったあまり」を表す記号で、多くのプログラミング言語(Julia を含む！)で採用されています。
前回の解決宣言の際には、これをさらに分解して
$\displaystyle (x \% 6, y \% 6) = (2, 3), (2, 5), (5, 3), (5, 5)$ の4通りに分けて議論しています。ここから先は計算が厳しいので、次の章で Julia を使って検証していきましょう。

Julia のコードを使って黒峰問題を再検証した話

Julia を使うと言っても、作戦がなければなにもできません。ここでは典型例の $(x\%6, y\%6) = (5, 5)$ に着目して作戦を整理します。
解決宣言でのフローでは、 $73 \to 13 \to 37 \to 109 \to 433$ の順番に ${}\bmod{}$ を取ればよい、と書いてあります。まず前情報がないと考えて ${}\bmod{73}$ を考えます。 ${}\bmod{73}$ での $2$ の位数*2は $9$ であり、 $3$ の位数は $12$ です。したがって $x$ は $9$ で割った余りを、 $y$ は $12$ で割った余りを考えればよいことになります。そこで以下のような表を準備します。

$x, y$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$
$0$
$1$
$2$
$3$
$4$
$5$
$6$
$7$
$8$

$(x, y)$ の組み合わせとしては表のマスの数、すなわち $108$ 通りあります。それぞれについて $2^{x} + 3^{y} + 5$ を計算し、これが ${}\bmod{73}$ で $z^{3}$ と合同になるような整数 $z$ があるかどうかを調べます。条件を満たすものについて、表に○を書き入れます。以上により $(x \% 9, y \% 12)$ として条件を満たすものが求まります。さて、ここまで忘却していましたが、前情報として $(x \% 6, y \% 6)=(5, 5)$ があったことを思い出します。この2つの情報を合わせるには $(x \% 18, y \% 12)$ の情報として合わせる必要があります。つまり ${}\bmod{}$ の周期性を利用して、表のサイズを合わせる、という寸法です(サイズだけに)。サイズを合わせたら、2つの表の両方で現れている○だけを残して、全て削除します。結果的には $(x \% 18, y \% 12) = (17, 5)$ のみが残ります。
この操作を実装したものが以下になります。
toy-box/kuromine_checker_neo.jl at master · mat-der-D/toy-box · GitHub
詳細は省きますが、sheet_gen(p) 関数で $\bmod{p}$ のときの表(にあたるもの)を作成し、 $\otimes$ という演算により「表を合わせる」操作を実行できます。例えば上の操作は次のように書かれます。

julia> include("kuromine_checker_neo.jl")
prod (generic function with 1 method)

julia> s = sheet_gen(5, 5, 6, 6);

julia> pr(s)
mod:(6, 6)
candidates:
   Set([(5, 5)])

julia> pr(s ⊗ sheet_gen(73))
mod:(18, 12)
candidates:
   Set([(17, 5)])

また立て続けに表を生成して合わせていく操作も手軽に行えるよう、prod という関数も作りました。 $73 \to 13 \to 37 \to 109 \to 433$ の操作は以下のようになります。

julia> s = sheet_gen(5, 5, 6, 6);

julia> pr(s)
mod:(6, 6)
candidates:
   Set([(5, 5)])

julia> pr(s ⊗ prod(73, 13, 37, 109, 433))
mod:(72, 108)
candidates:
   Set(Tuple{Int64,Int64}[])

最後の candidates: のところが空の Set になっているので、この場合はすべて不適であることが判定されたことになります。

問題なく検証できたあと2ケースについても取り組んでみます。

$(x \% 6, y \% 6) = (2, 5)$ のケース

$27 \to 73$ の順で考えます。事情により $2$ べきおよび $3$ べきの ${}\bmod{}$ は先程のツールで扱えないので、 $\bmod{27}$ は手計算で処理します*3。まず $y \geqq 5$ が確定しているので、 $3^{y}$ は必ず $27$ の倍数になります。よって

$\displaystyle 2^{x} + 5 \equiv z^{3} \pmod{27}$
を考えることになります。 $\bmod{27}$ での $2$ の位数は $18$ です。これらに対応する $2^{x} + 5$ の剰余のうち、立方剰余*4となるものを列挙すると
$\displaystyle 2^{x} + 5 \equiv 0, 1, 10, 19 \pmod{27}$
となり、それぞれ
$\displaystyle x \% 18 = 5, 11, 14, 17 \pmod{18}$
になります。前情報とあわせれば
$\displaystyle (x \% 18, y \% 6) = (14, 5)$
のみが残ります。あとは先程のツールで $\bmod{73}$ を組み合わせると

julia> s = sheet_gen(14, 5, 18, 6);

julia> pr(s ⊗ sheet_gen(73))
mod:(18, 12)
candidates:
   Set(Tuple{Int64,Int64}[])

となり、すべて不適になりました。

$(x \% 6, y \% 6) = (2, 3)$ のケース

これは一瞬です。以下のとおり $\bmod{13}$ をとると不適になります。

julia> s = sheet_gen(2, 3, 6, 6);

julia> pr(s ⊗ sheet_gen(13))
mod:(12, 6)
candidates:
   Set(Tuple{Int64,Int64}[])

検証の結果計算ミスが見つかった話

さて最後の $(x \% 6, y \% 6) = (5, 3)$ のケースを検証してみましょう。このケースは既に見つかっている解のうち $(x, y, z) = (5, 3, 4)$ を含んでいることに注意してください。これが残っている限りは $\bmod$ をいくらとっても不適にならないため、うまく外す必要があります。そこで ${}\bmod{64}$ を取ります。こうすることで、 $x \leqq 5$ と [x \geqq 6] を分解できます。
計算は読者の演習問題とする*5ことにして、結果を述べると、以下の3つの場合に分けられます。

$x = 5$ かつ $y \% 6 = 3$
$x \geqq 6$ かつ $(x \% 6, y \% 48) = (5, 27)$
$x \geqq 6$ かつ $(x \% 6, y \% 12) = (5, 9)$

1つ目の場合は $y = 3 \eta$ とおくことで

$\begin{aligned} & 32 + 3^{3 \eta} + 5 = z^{3} \\ \Leftrightarrow \quad & 37 = z^{3} - (3^{\eta})^{3} \\ & \hphantom{37} {} = (z - 3^{\eta})(z^{2} + 3^{\eta} z + 3^{2\eta}) \end{aligned}$ が得られます。 $37$ が素数であり $0 < z - 3^{\eta} < z^{2} + 3^{\eta} z + 3^{2\eta}$ から
$\displaystyle z - 3^{\eta} = 1, \quad z^{2} + 3^{\eta} z + 3^{2 \eta} = 37$ となります。これを解けば $(\eta, z) = (1, 4)$ が得られます。
2つ目の場合はフローチャートのとおりです。人が計算できるように(?)分岐していますが、要は 73, 97, 109, 193, 337, 433, 577, 673, 769, 1009, 1153, 3457 で ${}\bmod{}$ を取ればよいはずです。Julia のツールを使えば以下のようになります。

julia> s = sheet_gen(5, 27, 6, 48);

julia> pr(s)
mod:(6, 48)
candidates:
   Set([(5, 27)])

julia> pr(s ⊗ prod(73, 97, 109, 193, 337, 433, 577, 673, 769, 1009, 1153, 3457))

mod:(8064, 12096)
candidates:
   Set(Tuple{Int64,Int64}[])

ちゃんと不適になりました。
3つ目の場合も調べましょう。フローチャートによれば 73, 97, 109, 193, 577, 769, 3457 で ${}\bmod{}$ を取れば不適になるはずです。

julia> s = sheet_gen(5, 9, 6, 12);

julia> pr(s)
mod:(6, 12)
candidates:
   Set([(5, 9)])

julia> pr(s ⊗ prod(73, 97, 109, 193, 337, 433, 577, 673, 769, 1009, 1153, 3457))

mod:(8064, 12096)
candidates:
   Set([(3425, 969), (1841, 4857), (3749, 12093), (7457, 2697), (1841, 11721), (6449, 11769), (2417, 11721), (5873, 11721), (5, 381), (1841, 6537), (5873, 6537), (6053, 1725), (6881, 7881), (6053, 12093), (5, 10749), (5765, 1725), (5, 12093), (5765, 10749), (6881, 969), (5765, 10365), (5873, 4857), (5, 1725), (3749, 2973), (2417, 11769), (6449, 10041), (6449, 1353), (1841, 10041), (1157, 381), (2849, 7881), (5765, 9021), (2417, 1353), (5765, 381), (1157, 1725), (6449, 11721), (3749, 6429), (7205, 6429), (5873, 10041), (2849, 969), (7457, 969), (6053, 6429), (6053, 4701), (3749, 4701), (7205, 1725), (3749, 1725), (3425, 2697), (3749, 10365), (2417, 10041), (5765, 12093)])

...
あれ？？？？？？？

実は分岐するところで間違えてます。

julia> s = sheet_gen(5, 9, 6, 12);

julia> pr(s)
mod:(6, 12)
candidates:
   Set([(5, 9)])

julia> s = s ⊗ sheet_gen(73);

julia> pr(s)
mod:(18, 12)
candidates:
   Set([(5, 9)])

julia> s = s ⊗ prod(97, 577, 193);

julia> pr(s)
mod:(288, 48)
candidates:
   Set([(113, 9), (95, 9), (5, 45), (257, 9)])

実は4分岐になっていて、 $(x \% 288, y \% 48) = (275, 45)$ はありません。
$(x \% 288, y \% 48) = (95, 9)$ についてはフローチャート通り不適にできます。

julia> s = sheet_gen(95, 9, 288, 48);

julia> pr(s)
mod:(288, 48)
candidates:
   Set([(95, 9)])

julia> pr(s ⊗ prod(109, 769, 3457))
mod:(1152, 1728)
candidates:
   Set(Tuple{Int64,Int64}[])

他は残念ながらうまく死にません。以下はそのときのSOSのツイートです。

ということで #黒峰問題は未解決になってしまいました。。。
だれか (x%288, y%48)=(113, 9), (257, 9), (5, 45) の息の根を止めてください。。。

探索に役に立つツールは以下で公開しているので、適宜使ってくださいhttps://t.co/9tSqGF58W0
— すむーずぷりんちゃん🍮 (@mat_der_D) September 16, 2020

ミスを修正しようと試みた話

とはいえここまで頑張ったなら気合でなんとかしたいのが人情。ということで前回一緒に議論してくれただま氏( @dama_math )と DM で議論しました。だま氏の提案で $x$ や $y$ の $\bmod$ があまり大きくならないような素数たちを気合で重ねてみました。(素数の選定はだま氏にやってもらいました！)

julia> s = Sheet((288, 48), Set([(113, 9), (5, 45), (257, 9)]));

julia> pr(s)
mod:(288, 48)
candidates:
   Set([(113, 9), (5, 45), (257, 9)])

julia> ps = (7, 13, 19, 31, 37, 43, 61, 67, 73, 97, 109, 127, 181, 193, 199, 211, 241, 271, 331, 337, 379, 397, 421, 433, 463, 541, 577, 631, 661, 673, 757, 991, 1009, 1321, 2017, 2113, 2161, 2311, 2377, 2521, 2971, 3169, 3361, 3697, 4159, 4621, 5281, 6337, 7393, 7561, 8317, 8641, 9241, 12097, 13441, 15121, 16633, 18481, 19009, 20161, 23761, 30241, 47521, 55441, 66529, 110881);

julia> pr(s ⊗ prod(ps...))
mod:(332640, 332640)
candidates:
   Set([(5, 332637), (5, 166317)])

なぜか $(x \% 332640, y \% 166320) = (5, 166317)$ のひとつだけしぶとく残っています。実は

$\displaystyle 2^{5} + 3^{-3} + 5 = \left( \dfrac{10}{3} \right)^{3}$ が成り立っていて、 $\bmod$ の世界ではこれに対応するものが解として出てきています。悪いことに、3の倍数でない任意の $n$ に対して $\bmod{n}$ で考えると解となってしまいます。また $3$ べきを取っても排除できません。残念ながら今のところ、この解を回避する方法を見つけられていません。

まとめ

約一年前に解決宣言した黒峰問題ですが、実は計算ミスがあり解決していませんでした。ツールを使ってたくさん計算して修正を試みましたが、ある解を回避できないために完全解決に至ることができませんでした。誰か解いてください。

*1:「直観や経験や知識や計算を適宜用いて一定時間費やすと」という意味の業界用語。

*2:「何乗するとはじめて1と合同になるか？」という数。 $\bmod{73}$ での $2$ の位数が $9$ であるとは、 $2, 2^2, 2^3, 2^4, 2^5, 2^6, 2^7, 2^8$ がいずれも ${}\bmod{73}$ で $1$ と合同でなく、 $2^{9} \equiv 1 \pmod{73}$ が成り立つという意味です。