2017-04-12

ディクソンの恒等式

高校数学

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$ 次。根については三通りに場合分けして確認しよう。

・ $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_i$ は $y, 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$ で成り立つことからわかる。

2017-04-08

Weyl Differencing

定理解説

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

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

命題１ $N, a, q$ は整数で $N, q \geq 2$ , $a$ と $q$ は互いに素とする。また、実数 $\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)$

が成り立つ。

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

補題２ $L, M, N$ は $L \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とも言えます。

補題３ $a, q, \alpha$ は命題１と同じ設定。正整数 $k_1, k_2$ が $0 < \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)=1$ と $0 < \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.

命題２ $N, a, q, \alpha$ は命題１と同じ設定で $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\}$

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

$\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.

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

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

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

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

と評価できる。よって、命題２で $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$ なる整数 $a$ と $q\geq 2$ に対して

$\displaystyle \left| \alpha-\frac{a}{q} \right| \leq \frac{1}{q^2}$ −①

であれば、命題１より

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