Corollaryは必然に。

このブログは「コロちゃんぬ」の提供でお送りします

すべての自然数を「2±3±5±…±(k番目の素数)」の形で表す

2021年9月23日に行われたロマンティック数学ナイト@オンライン #16
「オンライン整数列大辞典の未解決問題が解けた話」
というプレゼンをさせていただきました。今回の話はこのイベントで紹介した未解決問題の解説および証明になります(おせーよ)。


素数ものさしってご存知でしょうか?その名の通り、目盛りが素数しかないものさしで、現在でも京大生協でのみ販売されています*1

素数ものさしのイメージ

なんとも不便なものさしですが、3-2=1 なので「3歩進んで2歩下がる」を繰り返せば、一応すべての自然数を測ることは可能です。しかし、これでは芸がないですね。せっかくならたくさんの素数を使いこなしたいところ。

そこで、すべての自然数を、2から順番に目盛りを1回だけ使って測ってみるのはいかがでしょう?例えば3なら
\[
3 = 2 + 3 + 5 - 7
\]なので、「2歩進んで、3歩進んで、5歩進んで、7歩下がる」ことで3を測れます。素数に囚われた水前寺清子みたいで楽しい。

さて、この方法ですべての自然数を測ることはできるのでしょうか?

あ、素数は無限にあるので素数ものさしは無限に長いこととします。


問題設定と考察

本日は次の問題を考えます。

問題1
任意の自然数2から連続する有限個の素数の足し引きで表すことができるか?

例えば1から20までを考えるとこんな感じになります。
\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から連続する有限個の素数の足し引きで表せない自然数がある可能性があります。ですが、もし表せたとすると「最低限必要な素数の数」が求まります。ということで、次の問題を考えます。

問題2
p_kは小さい方から数えてk番目の素数を表すことにする.自然数nに対して,2から連続するk個の素数に符号を与えて
\[
n=\pm2\pm3\pm5\cdots\pm p_k
\]と表せるような最小のka_nとおく(もし表せなければa_n=\inftyとする).このとき,数列(a_n)_nはどのように表せるか?
例としてn=20を考えましょう。先ほど 20 = 2 - 3 - 5 + 7 - 11 + 13 + 17 と表せることを紹介しましたが、これだけではa_{20}=7とは言い切れません(a_{20}\le7 ならOK)。というのも、
\[
20 > 17 \ge \pm 2 \pm 3 \pm 5 \pm 7
\]なので7よりも少なく表示できないことは分かりますが、20=\pm 2 \pm 3 \pm 5 \pm 7 \pm 11 \pm 13 や,20=\pm 2 \pm 3 \pm 5 \pm 7 \pm 11の形で表せる可能性があるからです。このくらいであれば総探索で求められますが、後で効率的な方法を紹介します。


なんやかんやで、n=80くらいまでの数列(a_n)_nをグラフにするとこのようになります:

んー。てけてけ動いてて、よく分からない。でもこの調子だとa_n=\infty とはならなそう…ですかね?

ちなみに、この数列に関する記事はすでにオンライン整数列大辞典(OEIS)にありますが、2021年9月23日時点では(a_n)_nを表す公式はありませんでした*2
oeis.org

ちょっと大げさに言えば、(オンライン整数列大辞典上の)未解決問題ということになります。本日はこの問題を解決します!!


主定理の紹介

さっそくですが、主定理の紹介です。

定理1
自然数nに対して,kn\le \displaystyle\sum_{i=1}^k p_i をみたす最小の自然数とする(p_iは小さい方から数えてi番目の素数を表す).このとき,以下が成り立つ:
  1. n=9, 16のとき,a_n=k+3.すなわちa_9=6a_{16}=7
  2. n\neq9, 16 かつ \displaystyle\sum_{i=1}^k p_i - n奇数のとき,a_n=k+1
  3. \displaystyle\sum_{i=1}^k p_i - n = 2, 8, 12 のとき,a_n=k+2
  4. \displaystyle\sum_{i=1}^k p_i - n2812 以外の偶数のとき,a_n=k

我ながら、場合分け、えっぐ。いきなりこんなの見せられてもいまいちピンと来ないと思いますので、定理1の使用例をいくつか見てみましょう。


n=4 のとき、2 < 4 < 5 = 2+3 なのでk = 2です。また、5-4=1奇数なので、定理1 (2)によるとa_4=k+1=3となります。つまり、4235の足し引きで表すことができ、これ以上素数の数は減らせないことが分かります。実際、4 = 2-3+5 と表せます。


では、 n=96 のときはどうでしょうか。
\begin{alignat*}{2}
&2+3+5+7+11+13+17+19 &=& 77,\\
&2+3+5+7+11+13+17+19+23 &=& 100
\end{alignat*}なので k = 9 です。また、100-96=42, 8, 12 以外の偶数)なので、定理1 (4)によれば a_{96}=k=9 が分かります。実際、

\begin{equation*}
96 = -2+3+5+7+11+13+17+19+23
\end{equation*}

と表せます。


また、n=98 のときは k = 9 かつ 100-98=2 なので a_{98}=k+2=11 となります。調べてみると、

\begin{equation*}
98 = 2+3+5-7-11-13+17+19+23+29+31
\end{equation*}

と表すことができ、29以下の素数では表すことができません。


いかがでしょうか?手順としては、まず最初は 2+3+5+\cdots のように素数を足していき、初めてnに到達するときの素数の個数 k を見つけます。

次に、2+3+\cdots+p_k - n偶奇を調べれば、(n=9, 16以外の)n は多くてもk+2 番目の素数までの足し引きで表せることが分かる、ということになります。まあまあ便利でしょ?

ただし、具体的にどこをマイナスにすればよいかまでは教えてくれないことに注意です。



それでは、証明に取り掛かりましょう。


3つの補題

主定理を証明する上で重要となる補題3つ紹介します。最初の補題n=\pm2\pm3\pm\cdots\pm p_kの形で表せることの同値な言い換えについてです。

自然数nn=\displaystyle\sum_{i=1}^{a} p_i - ba, b自然数)という形で表したとする.このとき,n=\pm2\pm3\pm\cdots\pm p_{a}の形で表せることと,相異なる素数p_{a_1}, \ldots, p_{a_j}1 \le a_1< a_2 < \cdots < a_j \le a)を用いてb=2(p_{a_1}+\cdots+p_{a_j})と表せることは同値.特にb奇数のときはn=\pm2\pm3\pm\cdots\pm p_{a}の形で表せない.
証明
うまく符号を選んでn=\pm2\pm3\pm\cdots\pm p_{a}の形で表せたとする.マイナスの符号をつけた素数p_{a_1}, \ldots, p_{a_j}1 \le a_1< a_2 < \cdots < a_j \le a)とすれば
\[
n=\sum_{i=1}^{a}p_i -2(p_{a_1}+\cdots+p_{a_j})
\]と表せる.逆に相異なる素数p_{a_1}, \ldots, p_{a_j}1 \le a_1< a_2 < \cdots < a_j \le a)を用いてb=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によって今考えている問題は相異なる素数の和が本質的に絡んでいることが分かりました。

再び例として、n=20の場合を考えます。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*}と表せますが、8=2\times4であり、4は明らかに相異なる素数の和で表せません。また、21は奇数なので論外です20\pm2\pm3\pm\cdots\pm13の偶奇が異なると考えてもOK)。そして38=2\times19=2(3+5+11)なので
\[
20 = 2 \color{red}{-}3 \color{red}{-}5 + 7 \color{red}{-}11 + 13 + 17
\]という表示が得られます。なるほど、相異なる素数の組とマイナスをつける素数の組が対応しているわけですねー。


ところで、さらっと19=3+5+11と分解しましたが、どんなに大きい自然数でも相異なる素数の和で表せるんでしょうか?そういえば、「4以上の偶数は2つの素数の和で表せる」というゴールドバッハ予想がありますが、これと同じノリで未解決問題だったりして…?

そんな不安を払拭してくれるのが次の補題です。

任意の整数k\ge5に対して,次をみたす自然数s_kが存在する:

素数は無限に存在するので、補題2により7以上自然数相異なる素数の和で表せることが分かります(H. E. Richert, 1949)。Richert先生、Danke schön!

注意 素数自身は相異なる素数の和で表せると見なします。2つ以上の相異なる素数の和を考える場合、11が反例になります。
なお、1,4,6は相異なる素数の和で表せません。何となくですけど、それぞれ2倍すれば2,8,12になります。おやぁ?どこかで見たような気がしますねぇ…?



それはさておき、補題2は割と単純な(?)数学的帰納法で証明できます。詳細は以下の記事に任せることにします。
integers.hatenablog.com

ただし、補題2とある定理を使って証明されております。

その定理とは…Bertrandの仮説です*3

Bertrandの仮説
任意の自然数nに対して,n \le p \le 2n を満たす素数pが存在する.
Bertrandの仮説から、
\[
p_{k+1}\le 2p_{k}\quad(k\ge 1)
\]が従います。この形で定理1の証明に利用しますので、お見逃しなく。


主定理の証明

それでは定理1の証明を行います。補題を適用させるために、小さいnについてはしらみつぶしに証明することになりますが、それ以外は気持ちよく証明できたと思います。ぜひ、絶妙な不等式評価に注目してご覧ください。

定理1(再掲)
自然数nに対して,kn\le \displaystyle\sum_{i=1}^k p_i をみたす最小の自然数とする(p_iは小さい方から数えてi番目の素数を表す).このとき,以下が成り立つ:
  1. n=9, 16のとき,a_n=k+3.すなわちa_9=6a_{16}=7
  2. n\neq9, 16 かつ \displaystyle\sum_{i=1}^k p_i - n奇数のとき,a_n=k+1
  3. \displaystyle\sum_{i=1}^k p_i - n = 2, 8, 12 のとき,a_n=k+2
  4. \displaystyle\sum_{i=1}^k p_i - n2812 以外の偶数のとき,a_n=k

(1)の証明

n=9のとき,2+3 < 9 < 2+3+5なのでk=3であり,
\[
9 = 2 + 3 - 5 + 7 - 11 + 13
\]なのでa_9 \le 6.また,
\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によりa_9\neq 3, 5.また,8=2\times4であるが4は相異なる素数の和で表せないのでa_9\neq 4.したがってa_9 = 6 = k+3

n=16のときは2+3+5 < 16 < 2+3+5+7なのでk=4である.n=9のときと同様の議論をすることでa_{16} = 7 = k+3が分かる.

(2)の証明

n\neq9, 16\sum_{i=1}^k p_i - n = 2l-1とおく(1\le l < \frac{p_k + 1}{2}).このうち,n\le 17=2+3+5+7をみたすのはn=1, 4, 7, 12, 14である.このときそれぞれk=1, 2, 3, 4, 4であり,
\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*}と表せるが,確かにa_n=k+1をみたしている(a_n < k+1とはならない証明はn=9と同様の議論をすればよい).

n > 17のときはk\ge5である.2l-1は奇数であるからn=\sum_{i=1}^k p_i - (2l-1)\pm 2\pm 3\pm\cdots\pm p_{k}の形で表せない.また
\begin{equation}
n=\sum_{i=1}^{k+1} p_i - (2l+p_{k+1}-1) \tag{eq1}\label{eq1}
\end{equation}であるが,2l+p_{k+1}-1は偶数であるからm=l+\frac{1}{2}(p_{k+1}-1)とおくと
\[
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*}であるから7\le m \le p_{k+1}.ここで補題2よりある自然数s_{k}が存在して,s_{k}\ge p_{k+1}かつ区間 [7, 6+s_{k}] 内の自然数p_1, \ldots, p_kの相異なる素数の和で表せる.したがってmp_1, \ldots, p_kの相異なる素数の和で表せることができ,補題1と\eqref{eq1}によりn=\pm2\pm3\pm\cdots\pm p_{k+1}の形で表せる.よってa_n = k+1

(3)の証明

\sum_{i=1}^k p_i - n = 2lとおく(l=1, 4, 6かつl < \frac{p_k}{2}).このうち,n\le17をみたすのはn=3, 8, 15である.このときそれぞれk=2, 3, 4であるが
\begin{alignat*}{2}
3 &= &2& + 3 + 5 - 7\\
8 &= &2& - 3 + 5 - 7 + 11\\
15 &= &2& + 3 + 5 + 7 + 11 - 13
\end{alignat*}と表せるので,a_n=k+2が確認できる.以後n > 17(よってk\ge5)とする.

l=1, 4, 6は相異なる素数の和で表せないのでa_n\neq k.また,
\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}という表示ができるが,2l+p_{k+1}は奇数なのでa_n\neq k+1.一方2l+p_{k+1}+p_{k+2}は偶数なのでm=l+\frac{1}{2}(p_{k+1}+p_{k+2})とおくと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*}m - p_{k+1}\ge7のとき,補題2よりm - p_{k+1}p_1, \ldots, p_{k}の相異なる素数の和で表せる.よってmp_1, \ldots, p_{k+1}の相異なる素数の和で表せるので\eqref{eq2}と合わせてa_n=k+2が得られる.

m - p_{k+1} < 7のとき,すなわち

\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*}

の場合を考える.(l, p_{k+2}-p_{k+1}) = (1, 2t)1\le t\le5)のときは
\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*}また,m\ge 1+\frac{1}{2}(p_{6}+p_{7})=16 > 7なので,補題2よりmp_1, \ldots, p_{k+1}の相異なる素数の和で表せる.したがって\eqref{eq2}と合わせてa_n=k+2

(l, p_{k+2}-p_{k+1}) = (4, 2t)1\le t\le 2)のときは
\begin{align*}
m &= 4+\frac{1}{2}(p_{k+2}-2t+p_{k+2})\\
&= p_{k+2}-t+4.
\end{align*}よってm= p_{k+2}+3またはm=p_{k+2}+2となるが,いずれも相異なる素数の和になっているので
\[
n = 2 - 3 + \cdots + p_{k+1} - p_{k+2}
\]または
\[
n = - 2 + 3 + \cdots + p_{k+1} - p_{k+2}
\]と表せる.ゆえにa_n=k+2

(4)の証明

\sum_{i=1}^k p_i - n = 2lとおく(l\neq1, 4, 6かつl < \frac{p_k}{2}).

このうち,n\le17をみたすのはn=2, 5, 6, 10, 11, 13, 17である.このときそれぞれk=1, 2, 3, 3, 4, 4, 4であるが
\begin{alignat*}{2}
2 &= &2&\\
5 &= &2& + 3\\
6 &= &- 2& + 3 + 5\\
10 &= &2& + 3 + 5\\
11 &= &2& - 3 + 5 + 7\\
13 &= &- 2& + 3 + 5 + 7\\
17 &= &2& + 3 + 5 + 7
\end{alignat*}と表せるので,a_n=kが確認できる.以後n > 17(よってk\ge5)とする.

l=2のときはn=-2+3+\cdots+ p_{k}と表せる(l=3, 5も同様).l\ge7のときは7\le l < p_{k+1} であり,補題2よりlp_1, \ldots, p_{k}の相異なる素数の和で表せる.■


あとがき

これにてOEIS上の未解決問題は無事解決しました(万一証明に不備があればご連絡ください。質問でもOKです)。達成感がはんぱない。

証明に手こずったのは、やはり(3)ですね(\sum_{i=1}^k p_i - n = 2, 8, 12 のとき)。2021年9月23日の時点では完全に証明したつもりになっていましたが、ブログに公開するにあたって証明をもう一度読み直したら、不備がありました。添え字を見誤ったり、m - p_{k+1} < 7になる可能性を考えてなかったり…。(3)だけ色々ありました。

でも証明を頑張った分、以下のグラフの例外的にピョコっと出てくる3人組に共感できるようになりました9, 16はガチの例外だから知らん)

僕にはわかるよ。君たちが周りよりちょっと素数が必要なのは、1, 4, 6が相異なる素数の和で表せないからだもんね。いいこいいこ。今から素数ものさしで測ってあげるね~。



さて、今回の問題は、2020年5月末に「1から連続する有限個の自然数を足し引きして、すべての整数をつくることができるか?」という問題をTwitterで見かけたのが発端でした。この問題を深掘りして数学デーで議論していたところ、なんとオンライン整数列大辞典(OEIS)上の未解決問題に辿り着きました。


oeis.org

その後、独自に証明を考えてみたところ、証明ができてしまった、という経緯がありました。
corollary2525.hatenablog.com
一応、高校数学で分かるので、よろしければこちらもご覧ください。



身近な問題を深堀りして出くわした未解決問題のことを個人的に“野生の未解決問題”と呼んでいます。特にOEISは野生の未解決問題の宝庫なので、OEISを漁るのも面白いかもしれません。


演習問題(奇数バージョン)

最後に、OEIS上に類似の未解決問題があるので、演習問題として掲載したいと思います(暗黒微笑)。

問題3
自然数nに対して,1から連続するk個の奇数に符号を与えて
\[
n=\pm1\pm3\pm5\cdots\pm (2k-1)
\]と表せるような最小のka_nとおく(もし表せなければa_n=\inftyとする).このとき,数列(a_n)_nはどのように表せるか?
OEISのリンクはこちら(Conjecture(予想)も載っています)。
oeis.org

ヒントを書いておくと、奇数(なんなら任意の数列)の場合も全体の証明の流れは一緒です。

つまり、補題1および補題2の奇数バージョンに相当する命題を考えるのです。要するに

  • n=\pm1\pm3\pm5\cdots\pm (2k-1)と表せることは、相異なる2k-1以下の奇数b_1,\ldots,b_jを使ってn=k^2 -2(b_1+\cdots+b_j)と表せることと同値(ただし\sum_{i=1}^{k}(2i-1)=k^2を用いた)
  • 相異なる奇数の和で表せない例外的な自然数はあるか?

を考えればOKです。あとは「例外を除く任意の自然数を相異なる奇数の和で表す方法(めちゃ単純)」や、「小さい数で具体的に計算して得られる法則」を見つければ、ほとんど証明できたようなものです。相変わらず場合分けが面倒ですが、素数に比べれば簡単簡単。

ぜひ、未解決問題にレッツチャレンジ!



thank Q for rEaDing.φ(・▽・ )

*1:一応Amazonでも売っていますが、ちょっと高めの価格。いつか直接買いに行きたい。

*2:今は私がConjectureとして主張だけ書いておきました。

*3:仮説と呼ばれていますが、ちゃんと正しい定理です。