インテジャーズ

インテジャーズ

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

ディクソンの恒等式

Dixonの恒等式 (1891/1903) 非負整数a, b, cに対し、
\displaystyle \sum_{k=-a}^a(-1)^k\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k} = \frac{(a+b+c)!}{a!b!c!}
が成り立つ。

a=b=c=nとおくと、

mathtrain.jp

で紹介されている

\displaystyle \sum_{k=-n}^n(-1)^k\binom{2n}{n+k}^3 = \frac{(3n)!}{(n!)^3}

となります。

正整数jに対して、多項式 \binom{x}{j}

\displaystyle \binom{x}{j} := \frac{x(x-1)\cdots (x-j+1)}{j!}

で定義します。\binom{x}{j}x=0, 1, \dots, j-1を根に持つj次の多項式です。

証明*1. m, rを非負整数とする。多項式P(x)

\displaystyle P(x) := (-1)^r\binom{x}{r}\binom{x+m+r}{m+r}

と定義する。このとき、P(x)m+2r個の整数 x=-m-r, -m-r-1, \dots, r-1を根に持つm+2r次の多項式である。

理由: \binom{x}{r}x=0, 1, \dots, r-1を根に持つr次の多項式であり、\binom{x+m+r}{m+r}x=-m-r, -m-r+1, \dots, -1を根に持つm+r次の多項式であることからわかる

次に、多項式 Q(x)

\displaystyle Q(x) := \sum_{k=0}^{2r}(-1)^k\binom{m+2r}{m+k}\binom{x}{k}\binom{x+m}{m+2r-k}

と定義する。このとき、Q(x)m+2r個の整数 x=-m-r, -m-r-1, \dots, r-1を根に持つm+2r次の多項式である。

理由:k毎に \binom{x}{k}k次、\binom{x+m}{m+2r-k}m+2r-k次、よって \binom{x}{k}\binom{x+m}{m+2r-k}m+2r次である。よって、Q(x)m+2r次。根については3通りに場合分けして確認しよう。

x=0, 1, \dots, r-1の場合: このような非負整数xを固定して、各kに対してkに関する項

\displaystyle (-1)^k\binom{m+2r}{m+k}\binom{x}{k}\binom{x+m}{m+2r-k}

が消えていることを確認する。

x < kの場合:
\ \binom{x}{k}=0である。

x\geq kの場合:
x+k \leq 2x < 2rなのでx < 2r-kであり、x+m < m+2r-kである。これは、\binom{x+m}{m+2r-k}=0を意味している。

x=-m, -m+1, \dots, -1の場合:
同様にx, kを固定するとき、0 \leq x+m < m \leq m+2r-kなので \binom{x+m}{m+2r-k}=0であり、Q(x)=0

x=-m-r, -m-r+1, \dots, -m-1の場合:
x=-y-1とおくと、y=m, m+1, \dots, m+r-1である。

\begin{align} \binom{x}{k} &= \binom{-y-1}{k} \\
&= \frac{(-y-1)(-y-2)\cdots (-y-k)}{k!}\\ &= (-1)^k\frac{(y+k)(y+k-1)\cdots (y+1)}{k!} \\
&=(-1)^k\binom{y+k}{k}\end{align}

および

\begin{align} \binom{x+m}{m+2r-k} &= \binom{-y+m-1}{m+2r-k} \\
&= \frac{(-y+m-1)(-y+m-2) \cdots (-y-2r+k)}{(m+2r-k)!} \\
&= (-1)^{m+2r-k}\frac{(y+2r-k)(y+2r-k-1)\cdots (y-m+1)}{(m+2r-k)!} \\
&= (-1)^{m-k}\binom{y+2r-k}{m+2r-k}\end{align}

より

\displaystyle Q(x) = \sum_{k=0}^{2r}(-1)^{m-k}\binom{m+2r}{m+k}\binom{y+k}{k}\binom{y+2r-k}{m+2r-k}

と書き換えられる。以下、整数m \leq y < m+rを固定する。整数k-m \leq k < 0を満たしているとすると、0 \leq y+k \leq y-1であることから

\displaystyle \binom{y+k}{k} = \binom{y+k}{y} = \frac{(y+k)(y+k-1)\cdots (k+1)}{y!} = 0

となる。これより、

\begin{align} Q(x) &= \sum_{k=-m}^{2r}(-1)^{k-m}\binom{m+2r}{m+k}\binom{y+k}{y}\binom{y+2r-k}{y-m}\\
&= \sum_{l=0}^{m+2r}(-1)^l\binom{m+2r}{l}\binom{y-m+l}{y}\binom{y+m+2r-l}{y-m}\end{align}

と変形できる。ここで、\binom{y-m+l}{y}\binom{y+m+2r-l}{y-m}lに関する多項式だと思えば、それはy+(y-m)=2y-m次である。2y-m < m+2rなので

\displaystyle \binom{y-m+l}{y}\binom{y+m+2r-l}{y-m} = \sum_{i=0}^{m+2r-1}a_il^i

と書ける*2。よって、

\displaystyle Q(x) = \sum_{i=0}^{m+2r-1}a_i\left\{\sum_{l=0}^{m+2r}(-1)^l\binom{m+2r}{l}l^i\right\}

を得る。

\displaystyle \sum_{l=0}^{m+2r}(-1)^l\binom{m+2r}{l}l^i=0

なので*3、結局 Q(x)=0 が示された

また、x=rのときを考えると、k > r ならば \binom{r}{k}=0であるし、0 \leq k < r ならば r+m < m+2r-k なので \binom{r+m}{m+2r-k}=0 である。すなわち、

\displaystyle Q(r) = (-1)^r\binom{m+2r}{m+r} = P(r)

が成り立つ。以上によって、P(x)Q(x)は次数より一つ多いm+2r+1個の相異なる数で値を共有していることが判明し、P(x) \equiv Q(x)であることが示された:

\displaystyle \sum_{k=0}^{2r}(-1)^k\binom{m+2r}{m+k}\binom{x}{k}\binom{x+m}{m+2r-k} = (-1)^r\binom{x}{r}\binom{x+m+r}{m+r} −(⭐︎)

a, b, c が与えられたときに

  • x=c+a
  • x+m=b+c
  • m+2r=a+b

となるように x, m, r を選ぶ(m=b-a \equiv a+b \pmod{2}であることに注意)。このとき、(⭐︎)の左辺は

\begin{align} &\sum_{k=0}^{2a}(-1)^k\binom{a+b}{b-a+k}\binom{c+a}{k}\binom{b+c}{a+b-k} \\
&= \sum_{k=-a}^a(-1)^{a+k}\binom{a+b}{b+k}\binom{c+a}{a+k}\binom{b+c}{b-k} \\
&= (-1)^a\sum_{k=-a}^a(-1)^k\binom{a+b}{a-k}\binom{b+c}{b-k}\binom{c+a}{c-k} \\
&=(-1)^a\sum_{k=-a}^a(-1)^k\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k}\end{align}

となり、(⭐︎)の右辺は

\displaystyle (-1)^a\binom{c+a}{a}\binom{a+b+c}{b} = (-1)^a\frac{(c+a)!}{a!c!}\frac{(a+b+c)!}{b!(a+c)!} = (-1)^a\frac{(a+b+c)!}{a!b!c!}

となる。 Q.E.D.

*1:Victor J. W. Guoによる。

*2:定数a_iy, m, rに依って定まるが、記号が煩雑になるので明示しない。重要なのはlに依らないこと。

*3:0 \leq j < nであれば、

\displaystyle \sum_{k=0}^n(-1)^k\binom{n}{k}k^j=0
である。これは、
\displaystyle \left( x\frac{d}{dx} \right)^j(1+x)^n=\sum_{k=0}^nk^j\binom{n}{k}x^k
であり、
\displaystyle \left. \left( x\frac{d}{dx} \right)^j(1+x)^n \right|_{x=-1} = 0
0 \leq j < n で成り立つことからわかる。

Weyl Differencing

Weyl DifferencingによってWeylの一様分布定理を二次式の場合に拡張しましょう。

記号: 実数\alphaに対して、\alphaに一番近い整数との距離を\left\|\alpha\right\|と表し*1e(\alpha) := e^{2\pi \sqrt{-1}\alpha}とします(\left|e(\alpha)\right|=1)。

補題1 \alphaを任意の実数とし、Nを正の整数とする。このとき、
\displaystyle \left| \sum_{n=1}^Ne(\alpha n) \right| \leq \min \left\{ N, \frac{1}{2\left\|\alpha\right\|}\right\}
が成り立つ。

証明. 三角不等式より

\displaystyle \left| \sum_{n=1}^Ne(\alpha n) \right| \leq N

が成り立つ。\alpha \not \in \mathbb{Z}であれば、等比数列の和の公式と三角不等式により

\displaystyle \left| \sum_{n=1}^Ne(\alpha n) \right|  = \frac{\left|e(\alpha)-e(\alpha(N+1))\right|}{\left|1-e(\alpha)\right|} \leq \frac{2}{\left|1-e(\alpha)\right|} = \frac{2}{\left|e(\alpha/2)-e(-\alpha/2)\right|} = \frac{1}{\left|\sin(\pi \alpha)\right|}

を得る。任意の実数xに対して\left|\sin(\pi x)\right| \geq 2\left\|x\right\|が成り立つ*2ので証明が完了する。 Q.E.D.

Weyl Differencing N \geq 2を整数とし、P(X)を実数係数多項式とする。
\displaystyle S:=\sum_{n=1}^Ne(P(n))
に対して
\displaystyle |S|^2 \leq N+2\sum_{h=1}^{N-1}\left| \sum_{n=1}^{N-h}e\left( P(n+h)-P(n) \right) \right|
が成り立つ。

P(n+h)-P(n)の次数はP(n)の次数より1落ちていることに注意しましょう。多項式に関する指数和を評価する際に次数を1下げることができるというテクニックが"Weyl Differencing"です。

証明. 実数xに対して \overline{e(x)}=e(-x)であることに注意すると

\displaystyle |S|^2 = \sum_{n=1}^N\sum_{m=1}^Ne(P(m)-P(n))

と変形できる。h=m-nとすると1-N \leq h \leq N-1であり、

\max\{1, 1-h\} \leq n=m-h \leq \min\{N, N-h\}

なので、

\begin{align} |S|^2 &= \sum_{1-N \leq h \leq N-1}\sum_{n=\max\{1, 1-h\}}^{\min\{N, N-h\}}e(P(n+h)-P(n)) \\ 
&= \left( \sum_{h=0}^{N-1}\sum_{n=1}^{N-h}+\sum_{h=1-N}^{-1}\sum_{n=1-h}^N \right) e(P(n+h)-P(n)) \\ 
&= N + \sum_{h=1}^{N-1}\sum_{n=1}^{N-h}e(P(n+h)-P(n)) + \sum_{k=1}^{N-1}\sum_{j=1}^{N-k}e(P(j)-P(j+k)) \\
&= N + 2\mathrm{Re}\left( \sum_{h=1}^{N-1}\sum_{n=1}^{N-h}e(P(n+h)-P(n))\right) \\ 
&\leq N+2\sum_{h=1}^{N-1}\left| \sum_{n=1}^{N-h}e(P(n+h)-P(n))\right|
\end{align}

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

命題1 N, a, qは整数でN, q \geq 2, aqは互いに素とする。また、実数\alpha
\displaystyle \left| \alpha-\frac{a}{q} \right| \leq \frac{1}{q^2}
を満たすものとする。\beta, \gammaは実数。このとき、指数和評価
\displaystyle \left| \sum_{n=1}^Ne(\alpha n^2+\beta n+\gamma) \right| \leq 8N\left( \frac{1}{\sqrt{q}}+\sqrt{\frac{1}{N}+\frac{q+4N}{N^2}\log q} \right)
が成り立つ。

これがメインの計算ですが、もう少し準備が必要です。

補題2 L, M, NL \leq Mを満たす2以上の整数。\alpha_1, \dots, \alpha_Lは実数で、i \neq jに対して \left\|\alpha_i-\alpha_j\right\| \geq 1/M が成り立つものとする。このとき、
\displaystyle \sum_{l=1}^{L}\min\left\{ N, \frac{1}{\left\|\alpha_l\right\|}\right\} \leq 2N+8M\log M
が成り立つ。

証明. \left\| \ \ \right\|の値は\bmod{1}で決まるので\alpha_1, \dots, \alpha_L \in [-1/2, 1/2)と仮定しても一般性を失わない。また、必要ならば\alpha_l \mapsto -\alpha_lとすることによって

\displaystyle \sum_{\substack{1 \leq l \leq L \\ \alpha_l \geq 0}}\min\left\{N, \frac{1}{\left\|\alpha_l\right\|}\right\} \geq \frac{1}{2}\sum_{l=1}^L\min\left\{N, \frac{1}{\left\|\alpha_l\right\|}\right\}

が成り立つと仮定しても一般性を失わない。番号を入れ替えることによって非負値を取るものが

0 \leq \alpha_1 < \alpha_2 < \cdots < \alpha_r < \frac{1}{2}

だとする。このとき、1 \leq j < i \leq rに対して\left\| \alpha_i \right\| = \alpha_iかつ\left\|\alpha_i - \alpha_j\right\|=\alpha_i-\alpha_jなので、仮定より

\displaystyle \alpha_i \geq \frac{i-1}{M}

である。従って、

\begin{align}\sum_{\substack{1 \leq l \leq L \\ \alpha_l \geq 0}}\min\left\{N, \frac{1}{\left\|\alpha_l\right\|}\right\} &\leq \sum_{i=0}^{r-1}\min\left\{ N, \frac{M}{i}\right\} = \sum_{i=0}^{[M/N]}N+\sum_{M/N < i < r}\frac{M}{i} \\
&\leq \left( \left[ \frac{M}{N} \right] + 1 \right) N + \sum_{i=1}^M\frac{M}{i} \leq N+2M+M\log M
\\ &\leq N+4M\log M\end{align}

を得る。 よって、

\displaystyle \sum_{l=1}^L\min\left\{N, \frac{1}{\left\|\alpha_l\right\|}\right\} \leq 2N+8M\log M

が示された。Q.E.D.

次の補題は繊細な議論が必要であり、Keyとも言えます。

補題3 a, q, \alphaは命題1と同じ設定。正整数k_1, k_20 < \left| k_2-k_1\right| \leq q/2 を満たすならば
\displaystyle \left\|\alpha k_2 - \alpha k_1 \right\| \geq \frac{1}{2q}
が成り立つ。

証明. \beta := \alpha - a/qとすると\left|\beta\right| \leq 1/q^2であり、

\displaystyle \left\|\alpha k_2-\alpha k_1 \right\| = \left\| (k_2-k_1)\frac{a}{q} + (k_2-k_1)\beta \right\|

である。(a, q)=10 < \left|k_2-k_1\right| \leq q/2 より (k_2-k_1)a/q は整数ではない。

\displaystyle (k_2-k_1)\frac{a}{q} \in \frac{1}{q}\mathbb{Z}

であり

\displaystyle \left|(k_2-k_1)\beta \right| \leq \frac{1}{2q}

なので、

\displaystyle \left\|\alpha k_2-\alpha k_1 \right\| \geq \left\| (k_2-k_1)\frac{a}{q} \right\| - \frac{1}{2q} \geq \frac{1}{q} - \frac{1}{2q} = \frac{1}{2q}

を得る。 Q.E.D.

命題2 N, a, q, \alphaは命題1と同じ設定でHを正の整数とする。このとき、
\displaystyle \sum_{k=1}^H \min\left\{N, \frac{1}{\left\|\alpha k\right\|} \right\} \leq 2\left(N+\frac{4HN}{q}+16(q+4H)\log q\right)
が成り立つ。

証明. 和の範囲を[q/2]個ずつに分けるというアイデアによって

\displaystyle \sum_{k=1}^H \min\left\{N, \frac{1}{\left\|\alpha k\right\|} \right\} \leq \sum_{j=0}^{[4H/q]}\sum_{k=j[q/2]+1}^{(j+1)[q/2]}\min\left\{N, \frac{1}{\left\|\alpha k\right\|} \right\}

とする。この内側の和は補題3によってL=[q/2], M=2qに対して補題2が適用できる形になっており、

\begin{align} \sum_{k=1}^H \min\left\{N, \frac{1}{\left\|\alpha k\right\|} \right\} &\leq 2\left( 1+\frac{4H}{q} \right) (N+8q\log (2q)) \\ 
&\leq 2\left( 1+\frac{4H}{q} \right)(N+16q\log q) \\
&= 2\left(N+\frac{4HN}{q}+16(q+4H)\log q\right) \end{align}

が示された。 Q.E.D.

命題1の証明. P(X) = \alpha X^2+\beta X+\gammaとすると

P(X+h)-P(X) = 2\alpha h X + \alpha h^2 + \beta h

である。よって、Weyl Differencingと補題1によって

\begin{align}\left| \sum_{n=1}^Ne(\alpha n^2+\beta n+\gamma) \right|^2 &\leq N+2\sum_{h=1}^{N-1}\left| \sum_{n=1}^{N-h}e(2\alpha hn + \alpha h^2 + \beta h) \right| \\ 
& = N+2\sum_{h=1}^{N-1}\left| \sum_{n=1}^{N-h}e(2\alpha hn) e(\alpha h^2 + \beta h) \right| \\
&= N+2\sum_{h=1}^{N-1}\left| \sum_{n=1}^{N-h}e(2\alpha hn) \right| \\
&\leq  N + 2\sum_{h=1}^{N-1}\min \left\{ N-h, \frac{1}{\left\| 2\alpha h \right\|} \right\} \\
&\leq N+2\sum_{k=1}^{2N}\min \left\{N, \frac{1}{\left\|\alpha k \right\|} \right\}
\end{align}

と評価できる。よって、命題2でH=2Nとすることにより

\begin{align} \left| \sum_{n=1}^Ne(\alpha n^2+\beta n+\gamma) \right|^2 &\leq N+4\left(N+\frac{8N^2}{q}+16(q+8N)\log q\right) \\
&\leq 64\left( \frac{N^2}{q} + N+(q+8N)\log q\right)\end{align}

であり、

\displaystyle \left| \sum_{n=1}^Ne(\alpha n^2+\beta n+\gamma) \right| \leq 8N\left( \frac{1}{\sqrt{q}}+\sqrt{\frac{1}{N}+\frac{q+4N}{N^2}\log q} \right)

を得る。 Q.E.D.

定理 \alphaを無理数, \beta, \gammaを実数とする。このとき、数列\{\alpha n^2+\beta n+\gamma\}_{n=1}^{\infty}\bmod{1}で一様分布する。

証明. (a, q)=1なる整数aq\geq 2に対して

\displaystyle \left| \alpha-\frac{a}{q} \right| \leq \frac{1}{q^2} −①
であれば、命題1より

\displaystyle \frac{1}{8N}\left| \sum_{n=1}^Ne(\alpha n^2+\beta n+\gamma) \right| \leq \frac{1}{\sqrt{q}}+\sqrt{\frac{1}{N}+\frac{q+4N}{N^2}\log q} \xrightarrow{N \to \infty} \frac{1}{\sqrt{q}}

を得る。 つまり、

\displaystyle \limsup_{N \to \infty} \frac{1}{N}\left| \sum_{n=1}^Ne(\alpha n^2+\beta n+\gamma) \right| \leq \frac{8}{\sqrt{q}}

であるが、Dirichletの近似定理

integers.hatenablog.com

によって①を満たすようなペア(a, q)は無数に存在するので、特にq \to \inftyとでき、

\displaystyle \lim_{N \to \infty}\frac{1}{N}\left| \sum_{n=1}^Ne(\alpha n^2+\beta n+\gamma) \right| = 0

が従う。従って、e(\ )の中身をk \neq 0倍しても同じなので、Weylの規準

integers.hatenablog.com

により証明が完了する。 Q.E.D.

*1:以前違う記号を用いたことがあります。 integers.hatenablog.com

*2:まずJordanの不等式

\displaystyle \frac{2}{\pi}x \leq \sin x \leq x, \quad \left( 0 \leq x \leq \frac{\pi}{2} \right)
を思い出します。 mathtrain.jp x=n\pm y, \ n \in \mathbb{Z}, \ y=\left\|x\right\|とすると 0 < y < 1/2なので、Jordanの不等式により
\displaystyle \left| \sin(\pi x) \right| = \left|\sin (\pi y)\right| \geq 2y = 2 \left\|x\right\|
が言えます。

フランスで出会った猫

先月フランスに滞在した際に出会った猫さんがとても素敵な方でした。


f:id:integers:20170407122351p:plain


さて、

integers.hatenablog.com

においてDiophantusの5つ組予想(=D(1)-5つ組の非存在)の解決宣言がなされたことを紹介しましたが*1、本日D(4)-5つ組の非存在の解決宣言がなされました。

[1704.01874] Nonexistence of $D(4)$-quintuples


今日も素敵な猫さんに出会えることを祈りましょう。

*1:まだプレプリントのようです