「オンライン整数列大辞典の未解決問題が解けた話」
というプレゼンをさせていただきました。今回の話はこのイベントで紹介した未解決問題の解説および証明になります(おせーよ)。
素数ものさしってご存知でしょうか?その名の通り、目盛りが素数しかないものさしで、現在でも京大生協でのみ販売されています*1。
なんとも不便なものさしですが、 なので「3歩進んで2歩下がる」を繰り返せば、一応すべての自然数を測ることは可能です。しかし、これでは芸がないですね。せっかくならたくさんの素数を使いこなしたいところ。
そこで、すべての自然数を、2から順番に目盛りを1回だけ使って測ってみるのはいかがでしょう?例えば3なら
\[
3 = 2 + 3 + 5 - 7
\]なので、「2歩進んで、3歩進んで、5歩進んで、7歩下がる」ことで3を測れます。素数に囚われた水前寺清子みたいで楽しい。
さて、この方法ですべての自然数を測ることはできるのでしょうか?
あ、素数は無限にあるので素数ものさしは無限に長いこととします。
問題設定と考察
本日は次の問題を考えます。
例えばからまでを考えるとこんな感じになります。
\begin{alignat*}{2}
1 &= &- 2& + 3\\
2 &= &2&\\
3 &= &2& + 3 + 5 - 7\\
4 &= &2& - 3 + 5\\
5 &= &2& + 3\\
6 &= &- 2& + 3 + 5\\
7 &= &2& + 3 - 5 + 7\\
8 &= &2& - 3 + 5 - 7 + 11\\
9 &= &2& + 3 - 5 + 7 - 11 + 13\\
10 &= &2& + 3 + 5\\
11 &= &2& - 3 + 5 + 7\\
12 &= &2& - 3 - 5 + 7 + 11\\
13 &= &- 2& + 3 + 5 + 7\\
14 &= &2& + 3 + 5 - 7 + 11\\
15 &= &2& + 3 + 5 + 7 + 11 - 13\\
16 &= &2& - 3 + 5 - 7 - 11 + 13 + 17\\
17 &= &2& + 3 + 5 + 7\\
18 &= &2& + 3 - 5 + 7 + 11\\
19 &= &2& + 3 + 5 + 7 - 11 + 13\\
20 &= &2& - 3 - 5 + 7 - 11 + 13 + 17
\end{alignat*}ただし、\begin{alignat*}{2}
1 &= &- 2& + 3\\
&= &2& - 3 - 5 + 7,\\
7 &= &2& + 3 - 5 + 7\\
&= &-2& - 3 + 5 + 7
\end{alignat*}のように、表示は一通りであるとは限りません。また、2から連続する有限個の素数の足し引きで表せない自然数がある可能性があります。ですが、もし表せたとすると「最低限必要な素数の数」が求まります。ということで、次の問題を考えます。
\[
n=\pm2\pm3\pm5\cdots\pm p_k
\]と表せるような最小のをとおく(もし表せなければとする).このとき,数列はどのように表せるか?
\[
20 > 17 \ge \pm 2 \pm 3 \pm 5 \pm 7
\]なので7よりも少なく表示できないことは分かりますが、 や,の形で表せる可能性があるからです。このくらいであれば総探索で求められますが、後で効率的な方法を紹介します。
なんやかんやで、くらいまでの数列をグラフにするとこのようになります:
んー。てけてけ動いてて、よく分からない。でもこの調子だと とはならなそう…ですかね?
ちなみに、この数列に関する記事はすでにオンライン整数列大辞典(OEIS)にありますが、2021年9月23日時点ではを表す公式はありませんでした*2。
oeis.org
ちょっと大げさに言えば、(オンライン整数列大辞典上の)未解決問題ということになります。本日はこの問題を解決します!!
主定理の紹介
さっそくですが、主定理の紹介です。
- のとき,.すなわち,.
- かつ が奇数のとき,.
- のとき,.
- が ,, 以外の偶数のとき,.
我ながら、場合分け、えっぐ。いきなりこんなの見せられてもいまいちピンと来ないと思いますので、定理1の使用例をいくつか見てみましょう。
のとき、 なのでです。また、(奇数)なので、定理1 (2)によるととなります。つまり、は,,の足し引きで表すことができ、これ以上素数の数は減らせないことが分かります。実際、 と表せます。
では、 のときはどうでしょうか。
\begin{alignat*}{2}
&2+3+5+7+11+13+17+19 &=& 77,\\
&2+3+5+7+11+13+17+19+23 &=& 100
\end{alignat*}なので です。また、(, , 以外の偶数)なので、定理1 (4)によれば が分かります。実際、
\begin{equation*}
96 = -2+3+5+7+11+13+17+19+23
\end{equation*}
また、 のときは かつ なので となります。調べてみると、
\begin{equation*}
98 = 2+3+5-7-11-13+17+19+23+29+31
\end{equation*}
いかがでしょうか?手順としては、まず最初は のように素数を足していき、初めてに到達するときの素数の個数 を見つけます。
次に、 の偶奇を調べれば、(以外の) は多くても 番目の素数までの足し引きで表せることが分かる、ということになります。まあまあ便利でしょ?
ただし、具体的にどこをマイナスにすればよいかまでは教えてくれないことに注意です。
それでは、証明に取り掛かりましょう。
3つの補題
主定理を証明する上で重要となる補題を3つ紹介します。最初の補題はの形で表せることの同値な言い換えについてです。
うまく符号を選んでの形で表せたとする.マイナスの符号をつけた素数を()とすれば
\[
n=\sum_{i=1}^{a}p_i -2(p_{a_1}+\cdots+p_{a_j})
\]と表せる.逆に相異なる素数()を用いてと表せたとすると
\begin{align*}
n&=\sum_{i=1}^{a}p_i -2(p_{a_1}+\cdots+p_{a_j})\\
&=p_1 + \cdots - p_{a_1} + \cdots - p_{a_j} + \cdots + p_a
\end{align*}となる.■
証明は大したことないですが、補題1によって今考えている問題は相異なる素数の和が本質的に絡んでいることが分かりました。
再び例として、の場合を考えます。20は
\begin{align*}
20 &= 2 + 3 + 5 + 7 + 11 \color{red}{- 8}\\
&= 2 + 3 + 5 + 7 + 11 + 13 \color{red}{- 21}\\
&= 2 + 3 + 5 + 7 + 11 + 13 + 17 \color{red}{- 38}
\end{align*}と表せますが、であり、は明らかに相異なる素数の和で表せません。また、は奇数なので論外です(との偶奇が異なると考えてもOK)。そしてなので
\[
20 = 2 \color{red}{-}3 \color{red}{-}5 + 7 \color{red}{-}11 + 13 + 17
\]という表示が得られます。なるほど、相異なる素数の組とマイナスをつける素数の組が対応しているわけですねー。
ところで、さらっとと分解しましたが、どんなに大きい自然数でも相異なる素数の和で表せるんでしょうか?そういえば、「4以上の偶数は2つの素数の和で表せる」というゴールドバッハ予想がありますが、これと同じノリで未解決問題だったりして…?
そんな不安を払拭してくれるのが次の補題です。
素数は無限に存在するので、補題2により7以上の自然数は相異なる素数の和で表せることが分かります(H. E. Richert, 1949)。Richert先生、Danke schön!
なお、1,4,6は相異なる素数の和で表せません。何となくですけど、それぞれ2倍すれば2,8,12になります。おやぁ?どこかで見たような気がしますねぇ…?それはさておき、補題2は割と単純な(?)数学的帰納法で証明できます。詳細は以下の記事に任せることにします。
integers.hatenablog.com
ただし、補題2はとある定理を使って証明されております。
その定理とは…Bertrandの仮説です*3。
\[
p_{k+1}\le 2p_{k}\quad(k\ge 1)
\]が従います。この形で定理1の証明に利用しますので、お見逃しなく。
主定理の証明
それでは定理1の証明を行います。補題を適用させるために、小さいについてはしらみつぶしに証明することになりますが、それ以外は気持ちよく証明できたと思います。ぜひ、絶妙な不等式評価に注目してご覧ください。
- のとき,.すなわち,.
- かつ が奇数のとき,.
- のとき,.
- が ,, 以外の偶数のとき,.
(1)の証明
のとき,なのでであり,
\[
9 = 2 + 3 - 5 + 7 - 11 + 13
\]なので.また,
\begin{align*}
9 &= 2+3+5\color{red}{-1}\\
&= 2+3+5+7\color{red}{-8}\\
&= 2+3+5+7+11\color{red}{-19}
\end{align*}と表せるが,1,19は奇数なので補題1により.また,であるが4は相異なる素数の和で表せないので.したがって.
のときはなのでである.のときと同様の議論をすることでが分かる.
(2)の証明
,とおく().このうち,をみたすのはである.このときそれぞれであり,
\begin{alignat*}{2}
1 &= &- 2& + 3\\
4 &= &2& - 3 + 5\\
7 &= &2& + 3 - 5 + 7\\
12 &= &2& - 3 - 5 + 7 + 11\\
14 &= &2& + 3 + 5 - 7 + 11
\end{alignat*}と表せるが,確かにをみたしている(とはならない証明はと同様の議論をすればよい).
のときはである.は奇数であるからはの形で表せない.また
\begin{equation}
n=\sum_{i=1}^{k+1} p_i - (2l+p_{k+1}-1) \tag{eq1}\label{eq1}
\end{equation}であるが,は偶数であるからとおくと
\[
m\ge 1+\frac{1}{2}(p_{6}-1)=7.
\]また,
\begin{align*}
m&< \frac{1}{2}(p_{k}+1)+\frac{1}{2}(p_{k+1}-1)\\
&\le p_{k+1}
\end{align*}であるから.ここで補題2よりある自然数が存在して,かつ区間 内の自然数はの相異なる素数の和で表せる.したがってはの相異なる素数の和で表せることができ,補題1と\eqref{eq1}によりの形で表せる.よって.
(3)の証明
とおく(かつ).このうち,をみたすのはである.このときそれぞれであるが
\begin{alignat*}{2}
3 &= &2& + 3 + 5 - 7\\
8 &= &2& - 3 + 5 - 7 + 11\\
15 &= &2& + 3 + 5 + 7 + 11 - 13
\end{alignat*}と表せるので,が確認できる.以後(よって)とする.
は相異なる素数の和で表せないので.また,
\begin{align}
n &= \sum_{i=1}^{k+1} p_i - (2l+p_{k+1})\notag\\
&= \sum_{i=1}^{k+2} p_i - (2l+p_{k+1}+p_{k+2}) \tag{eq2}\label{eq2}
\end{align}という表示ができるが,は奇数なので.一方は偶数なのでとおくとBertrandの仮説より
\begin{align*}
m - p_{k+1} &= l+\frac{1}{2}(p_{k+2} - p_{k+1})\\
& \le 6+\frac{1}{2}(2p_{k+1} - p_{k+1})\\
& = 6+\frac{p_{k+1}}{2}\\
& \le p_{k+1}.\\
\end{align*}のとき,補題2よりはの相異なる素数の和で表せる.よってはの相異なる素数の和で表せるので\eqref{eq2}と合わせてが得られる.
のとき,すなわち
\begin{align*}
(l, p_{k+2}-p_{k+1}) =& (1, 2),\,(1, 4),\,(1, 6),\,(1, 8),\,(1, 10),\\
&(4, 2),\,(4, 4)
\end{align*}
\begin{align*}
m &= l+\frac{1}{2}(p_{k+1}+p_{k+2})\\
&= 1+\frac{1}{2}(p_{k+2}-2t+p_{k+2})\\
&= p_{k+2}-t+1\\
&\le p_{k+2}.
\end{align*}また,なので,補題2よりはの相異なる素数の和で表せる.したがって\eqref{eq2}と合わせて.
()のときは
\begin{align*}
m &= 4+\frac{1}{2}(p_{k+2}-2t+p_{k+2})\\
&= p_{k+2}-t+4.
\end{align*}よってまたはとなるが,いずれも相異なる素数の和になっているので
\[
n = 2 - 3 + \cdots + p_{k+1} - p_{k+2}
\]または
\[
n = - 2 + 3 + \cdots + p_{k+1} - p_{k+2}
\]と表せる.ゆえに.
あとがき
これにてOEIS上の未解決問題は無事解決しました(万一証明に不備があればご連絡ください。質問でもOKです)。達成感がはんぱない。
証明に手こずったのは、やはり(3)ですね( のとき)。2021年9月23日の時点では完全に証明したつもりになっていましたが、ブログに公開するにあたって証明をもう一度読み直したら、不備がありました。添え字を見誤ったり、になる可能性を考えてなかったり…。(3)だけ色々ありました。
でも証明を頑張った分、以下のグラフの例外的にピョコっと出てくる3人組に共感できるようになりました(はガチの例外だから知らん)。
僕にはわかるよ。君たちが周りよりちょっと素数が必要なのは、が相異なる素数の和で表せないからだもんね。いいこいいこ。今から素数ものさしで測ってあげるね~。
さて、今回の問題は、2020年5月末に「1から連続する有限個の自然数を足し引きして、すべての整数をつくることができるか?」という問題をTwitterで見かけたのが発端でした。この問題を深掘りして数学デーで議論していたところ、なんとオンライン整数列大辞典(OEIS)上の未解決問題に辿り着きました。
また、n=1~nまでを順に足したり引いたりしたとき、任意の整数を表せる数列bnの必要十分条件を探しました。OEISに関連する数列があり、どうやら三角数が関係しそうであることまではわかりました。未解決のopen questionが関わってくるようです。(キグロ)#数学デー #オンライン数学デー pic.twitter.com/VSdB3T81eU
— 「数学デー」公式 (@sugaku_day) 2020年5月29日
oeis.org
その後、独自に証明を考えてみたところ、証明ができてしまった、という経緯がありました。
corollary2525.hatenablog.com
一応、高校数学で分かるので、よろしければこちらもご覧ください。
身近な問題を深堀りして出くわした未解決問題のことを個人的に“野生の未解決問題”と呼んでいます。特にOEISは野生の未解決問題の宝庫なので、OEISを漁るのも面白いかもしれません。
演習問題(奇数バージョン)
最後に、OEIS上に類似の未解決問題があるので、演習問題として掲載したいと思います(暗黒微笑)。
\[
n=\pm1\pm3\pm5\cdots\pm (2k-1)
\]と表せるような最小のをとおく(もし表せなければとする).このとき,数列はどのように表せるか?
oeis.org
ヒントを書いておくと、奇数(なんなら任意の数列)の場合も全体の証明の流れは一緒です。
つまり、補題1および補題2の奇数バージョンに相当する命題を考えるのです。要するに
- と表せることは、相異なる以下の奇数を使ってと表せることと同値(ただしを用いた)
- 相異なる奇数の和で表せない例外的な自然数はあるか?
を考えればOKです。あとは「例外を除く任意の自然数を相異なる奇数の和で表す方法(めちゃ単純)」や、「小さい数で具体的に計算して得られる法則」を見つければ、ほとんど証明できたようなものです。相変わらず場合分けが面倒ですが、素数に比べれば簡単簡単。
ぜひ、未解決問題にレッツチャレンジ!
thank Q for rEaDing.φ(・▽・ )