2018-03-23

HAPPY BIRTHDAY

整数整数-25 整数-121 整数-5041 整数-1729

三つの平方数の平均値

Brocard-Ramanujan方程式

$n!+1=m^2$

の解は三つと強く予想されており、その三つの平方数は $25, 121, 5041$ でした。

integers.hatenablog.com

実はこの三つの平方数の平均がRamanujanのタクシー数 $1729$ になることは記憶に値します。

ピアノの話

実家のアップライトピアノは甥っ子に譲るとのことですが、ここ数年は一切弾いておりませんでした。数日前、懐かしくなって何曲か弾いてみたのですが、その中から好きな曲を二曲紹介します。どちらも『ピアノ名曲110選 GRADE A 』(ドレミ楽譜出版社)収録曲です。

ヘンデルのラルゴ
www.youtube.com

野ばらに寄せて Edward Alexander MacDowell作曲
www.youtube.com

少年のときは例えばGRADE Cに収録されているような難しめのが好きだったのですが、難易度と曲の素晴らしさには別に関係がなく、今思うとGRADE Aに収録されている曲達もかなりの名曲揃いです。

実家最後の日

今日で28年間過ごした大阪府池田市を出て初めての一人暮らしを始めます。甥っ子と池田市のチキンラーメン記念館に行ってきました*1。

新天地でも一生懸命数学をします。

f:id:integers:20180323225257j:plain

*1:何度か行ったことがあります。 integers.hatenablog.com

2018-03-12

鳩ノ巣原理

その他

鳩ノ巣原理(pigeonhole principle)、鳩の巣原理、Dirichletの(箱入れ)原理(box principle)、Dirichletの抽斗論法、部屋割り論法などと呼ばれる次の原理*1は有名です。

鳩ノ巣原理 $n$ を正整数とする。 $n+1$ 羽以上の鳩を $n$ 個の鳩ノ巣に入れるとき、少なくとも一つの鳩ノ巣に二羽の鳩が入る。

当ブログで鳩ノ巣原理を利用している記事に

ディリクレの近似定理 - INTEGERS
ファン・デル・ヴェルデンの定理 - INTEGERS
ベイカーの定理の証明 - INTEGERS

などがあります。次のように拡張したものはしばしば一般化鳩ノ巣原理と呼ばれます。

一般化鳩ノ巣原理 $n, k$ を正整数とする。 $kn+1$ 羽以上の鳩を $n$ 個の鳩ノ巣に入れるとき、少なくとも一つの鳩ノ巣に $k+1$ 羽の鳩が入る。

$k=1$ のときを考えると鳩ノ巣原理となるため、一般化鳩ノ巣原理は確かに鳩ノ巣原理の一般化です。これは次のように表現することもできます。

一般化鳩ノ巣原理(言い換え) $n, k$ を正整数とする。このとき、非負整数 $a_1, \dots, a_n$ に対して

$\displaystyle \sum_{i=1}^na_i \geq kn+1$

ならば、或る $j$ が存在して $a_j \geq k+1$ が成り立つ。

これは $1, \dots, n$ が鳩ノ巣の番号で、 $i$ 番の鳩ノ巣に入っている鳩の羽数を $a_j$ として記述したものです。

さて、この記事の本論は簡単に証明できる次の命題についてです。

命題 $n$ を正整数、 $t$ を正の数とする。このとき、実数 $a_1, \dots, a_n$ に対して

$\displaystyle \sum_{i=1}^na_i \geq nt$

ならば、或る $j$ が存在して $a_j \geq t$ が成り立つ。

証明. もし、全ての $i$ に対して $a_i < t$ ならば

$\displaystyle \sum_{i=1}^na_i < nt$

となって矛盾する。 Q.E.D.

この命題(やその変種*2 )を利用するときに「鳩ノ巣原理より」という枕詞が使われることがよくあります*3。

当ブログでは

IMO2006 Problem 6 - INTEGERS
グリーン・タオ論文の§9を読む（その一） - INTEGERS
セメレディの定理の組合せ論的証明ー６ - INTEGERS
セメレディの定理の組合せ論的証明ー７ - INTEGERS
105に関するErdősの予想や剱岳など - INTEGERS

などでこの用法を使っています*4。この用法はあまり見かけない、或いは不自然だと感じる人もいると思いますが、ここでは上記命題から鳩ノ巣原理が出る、すなわち鳩ノ巣原理と全くの無関係なものではない*5ということを指摘しておきます。

命題 $\Longrightarrow$ 一般化鳩ノ巣原理の証明. 命題において $a_1, \dots, a_n$ を非負整数と限定し、 $t=k+\frac{1}{n}$ とする。すると

$\displaystyle \sum_{i=1}^na_i \geq n(k+\frac{1}{n}) =kn+1$

であれば、或る $j$ が存在して $a_j \geq k+\frac{1}{n}$ が成り立つ。しかしながら、 $a_j$ は整数なので $a_j \geq k+1$ でなければならない。 Q.E.D.

もちろん、ただの背理法の応用の一つなので名前なんて付ける必要はないという指摘はもっともです。

*1:原理とは言っても、自然数論の立場でちゃんと証明できます。

*2:不等号が等号なしだったり逆だったり、積で考えたり。或いはもっと一般的に「全体で何かの性質を満たすとき、有限個の類に類別すると少なくとも一つの類でその性質が満たされる」とする論法(ファン・デル・ヴェルデンの定理 - INTEGERSの最後の方やセメレディの定理の組合せ論的証明ー４ - INTEGERS で利用している)。

*3:背理法ですぐ証明できるけれども、論法はいつも同じなのでこの枕詞でわかってもらうという慣習。

*4:偉い人が使っているから使い方が正しいということはないですが、Szemerédiの定理の記事はTaoの原稿をもとに書いたものであり、Taoはよくこの用法でpigeonhole principleという言葉を使っています。

*5:この命題の論法+整数性=鳩ノ巣原理。より大元となる命題のことも鳩ノ巣原理と呼んでしまおうという慣習もあるということ。

2018-03-09

105に関するエルデシュの予想や剱岳など

整数整数-105 整数-4 整数-7 整数-15 整数-21 整数-45 整数-75

$105$ という整数について、これまでに二つ記事を書いたことがあります。

integers.hatenablog.com

今日は更に二つほど紹介しようと思います。

Ramanujanの公式

Ramanujanの発見した次の公式に $105$ が登場します。

$\displaystyle \left(1+\frac{1}{2^4}\right)\times \left(1+\frac{1}{3^4}\right)\times \left(1+\frac{1}{5^4}\right)\times \left(1+\frac{1}{7^4}\right)\times \left(1+\frac{1}{11^4}\right)\times \cdots = \frac{105}{\pi^4}.$

証明. $p$ は素数をわたるものとして、Riemannゼータ関数のEuler積表示と特殊値を利用すれば

$\displaystyle \prod_p\left(1+\frac{1}{p^4}\right) =\frac{\prod_p\left(1-\frac{1}{p^8}\right)}{\prod_p\left(1-\frac{1}{p^4}\right)}=\frac{\zeta(4)}{\zeta(8)}=\frac{\pi^4/90}{\pi^8/9450}=\frac{105}{\pi^4}$

と計算できる. Q.E.D.

Erdősの予想

予想 (Erdős, 1950) $n-2^k > 0$ であるような全ての正整数 $k$ に対して $n-2^k$ が素数となるような正整数 $n$ は $n=4, 7, 15, 21, 45, 75, 105$ のみであろう。

$4-2=2$

$7-2=5, \ 7-4=3$

$15-2=13, \ 15-4=11, \ 15-8=7$

$21-2=19, \ 21-4=17, \ 21-8=13, \ 21-16=5$

$45-2=43, \ 45-4=41, \ 45-8=37, \ 45-16=29, \ 45-32=13$

$75-2=73, \ 75-4=71, \ 75-8=67, \ 75-16=59, \ 75-32=43, \ 75-64=11$

$105-2=103, \ 105-4=101, \ 105-8=97, \ 105-16=89, \ 105-32=73, \ 105-64=41$

は全て素数であり、このような性質を持つ最大の整数が $105$ であろうという予想です。

ちなみに、 $105-128=-23, \ 105-256=-151$ も絶対値が素数だったりします。

この予想は

P. Erdős, On integers of the form $2^k + p$ and some related questions, Summa Bras. Math., 2 (1950), 113-123.

の3ページ目に述べられています。この論文でErdősは例えば次の定理を証明しています。

定理 (Erdős) $n$ を正整数とし、 $f(n)$ を $\#\{(k, p) \mid n=2^k+p, k \in \mathbb{Z}_{>0}, p: \text{素数}\}$ とする。このとき、 $\displaystyle \limsup_{n \to \infty}f(n)=\infty$ が成り立つ。

証明. $N>0$ は十分大きい整数とする。 $w(N)$ を $\displaystyle \lim_{N \to \infty}w(N)=\infty$ であるような十分増加速度の遅い実数値単調増大関数とし、 $W=W(N)$ を

$\displaystyle W(N):=\prod_{3 \leq p \leq w(N)}p$

と定義する( $p$ は素数)。 $S(N)$ を

$\displaystyle 2^k+p\equiv 0 \pmod{W},\quad 2^k+p \leq N$

を満たすような $(k, p)$ の個数とする。このとき、

$\displaystyle S(N) = \sum_{j =1}^{[N/W]}f(jW)$ −①

が成り立つことがわかる。 $k \leq \log N$ を固定する。すると、 $p < N/2$ であれば $2^k+p < N$ が成り立つので、 $W$ を法として $-2^k$ と合同な $x$ 以下の素数の個数を $\pi_{W, -2^k}(x)$ で表すと

$\displaystyle S(N) \geq \sum_{k \leq \log N}\pi_{W, -2^k}\left(\frac{N}{2}\right)$ −②

が成り立つことがわかる*1。さて、 $W$ と $-2^k$ は互いに素なので、 $\varphi(n)$ をEulerのトーシェント関数として

$\displaystyle F(W, N):=\frac{\pi_{W, -2^k}\left(\frac{N}{2}\right)}{\frac{1}{\varphi(W)}\frac{\frac{N}{2}}{\log\frac{N}{2}}}-1$

と $F(W, N)$ を定義すると、W-トリックの補題および算術級数の素数定理より

$\displaystyle \lim_{N \to \infty}F(W, N)=0$

がわかる。よって、 $N \gg 0$ であれば、或る正の数 $c_0$ が存在して

$\displaystyle \pi_{W, -2^k}\left(\frac{N}{2}\right) > \frac{c_0}{\varphi(W)}\frac{N}{\log N}$

が成り立つ。トーシェント関数の公式とMertensの第三定理より

$\displaystyle \varphi(W) = W\prod_{p \mid W}\left(1-\frac{1}{p}\right) = O\left(\frac{W}{\log W}\right)$

であり、Chebyshevの定理より

$\log W = \vartheta(w(N) )-\log 2 \gg w(N)$

なので、或る正の数 $c_1$ が存在して

$\displaystyle \pi_{W, -2^k}\left(\frac{N}{2}\right) > c_1\cdot \frac{Nw(N)}{W\log N}$

がわかった。従って、①・②より或る正の数 $c_2$ が存在して

$\displaystyle \sum_{j =1}^{[N/W]}f(jW) > c_2\cdot \frac{Nw(N)}{W}$

が成り立つ。故に、鳩ノ巣原理によって $lW \leq N$ なる正整数 $l=l(N)$ が存在して

$\displaystyle f(lW) > c_2w(N) \geq c_2w(lW)$

でなければならない。つまり、 $f(n) > c_2w(n)$ を満たすような $n$ が無数に存在することが示された*2。 Q.E.D.

Erdősは実際には $w(N)=\log \log N$ と取れることまで示していますが、そのためには準備が必要になるのでここでは紹介しません。

余談

最近知ったとある伝説がかっこいいなあと感じたので書いておきます。飛騨山脈北部立山連峰にある剱岳(標高2999m)の記録に残る初登頂は1907年7月13日(測量隊の生田信ら)らしいのですが、その際、錆び付いた鉄剣と銅製の錫杖が発見され、当時の鑑定ではこれらは奈良時代後半から平安時代初期にかけて登頂した修験者のものだそうです(Wikipediaより引用)。この伝説の修験者、かっこよすぎる。

*1:この式では $k$ を固定するという約束をいったん解除。

*2:有限個の $n$ が得られている場合、それらの最大値より大きい $W$ を考えると新しいものが得られる。

INTEGERS

数、特に整数に関する記事。