Pólya–Vinogradovの不等式

同義語:Pólya–Vinogradov inequalityPólya–Vinogradovの定理Polya–Vinogradovの不等式

概要

Pólya–Vinogradovの不等式(Pólya–Vinogradov inequality)とは、法 $q$ の自明でない Dirichlet 指標 $\chi$ の連続する整数にわたる和 $\sum_{M< n\le M+N}\chi(n)$ が、区間によらず $2\sqrt q\log q$ 未満であり、$\chi$ が原始指標なら $\sqrt q\log q$ 以下であるという評価である。原始指標は絶対値 $\sqrt q$ の Gauss 和を係数とする有限 Fourier 展開をもち、それが証明の鍵である。原始指標では区間和の最大値が $\sqrt q/(2\pi)$ より大きいので、$\sqrt q$ の冪は改良できない。系として、最小の平方非剰余は $\sqrt p\log p+1$ 以下である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Dirichlet指標, Gauss和, Legendre記号

Pólya–Vinogradovの不等式(Pólya–Vinogradov inequality)は、法 $q$ の自明でない Dirichlet指標 $\chi$ の値を連続する整数にわたって足した和が、区間の長さによらず $2\sqrt q\log q$ 未満に収まる、という評価である。$\chi$ が原始指標なら上界は $\sqrt q\log q$ にできる。
$\chi$ の値は $1$ の冪根で、1 周期の和は $0$ である。そのため区間和は、どんなに長い区間でも、たかだか法の半分程度の大きさにしかならない(rem-pv-trivial)。Pólya–Vinogradov の不等式は、これを $\sqrt q$ に対数をかけた大きさまで改良する。$\sqrt q$ は、値 $\pm1$ をでたらめに $q$ 個並べたときの和の典型的な大きさであり、指標の値が「偏りなく散らばっている」ことの定量的な表現になっている。証明の鍵は、指標を加法的な指標 $n\mapsto e^{2\pi ian/q}$ の重ね合わせとして書く有限 Fourier 展開で、その係数は Gauss和 であり、絶対値が $\sqrt q$ である。
応用として、奇素数 $p$ の最小の 平方非剰余 が $\sqrt p\log p+1$ 以下であること(cor-pv-nonresidue)、$L(1,\chi)$ が $\log q$ 程度に抑えられること(cor-pv-l1)を示す。

主張

以下 $e(x):=e^{2\pi ix}$ とおき、$\log$ は自然対数とする。

指標の区間和

$\chi$ を法 $q$ の Dirichlet 指標とする。整数 $M$ と $N\ge0$ について
$$ S_\chi(M,N):=\sum_{M< n\le M+N}\chi(n) $$
とおく。

自明な評価

$\chi$ が自明でない指標なら、1 周期の和 $\sum_{n=1}^{q}\chi(n)$ は $0$ である(Dirichlet指標)。よって区間の長さ $N$ を $q$ で割った余りに置き換えてよく、$N< q$ としてよい。その区間で $\chi(n)\ne0$ となる $n$ の個数を $k$ とすると、$\lvert S_\chi(M,N)\rvert\le k$ であり、1 周期の残りの部分の和は $-S_\chi(M,N)$ なので $\lvert S_\chi(M,N)\rvert\le\varphi(q)-k$ でもある。したがって
$$ \lvert S_\chi(M,N)\rvert\le\frac{\varphi(q)}2 $$
である($\varphi$ は Euler の関数)。

Pólya–Vinogradovの不等式

$\chi$ を法 $q$ の自明でない Dirichlet 指標とする。すべての整数 $M$ と $N\ge0$ について次が成り立つ。

  1. $\chi$ が原始指標なら $\lvert S_\chi(M,N)\rvert\le\sqrt q\log q$ である。
  2. 一般に $\lvert S_\chi(M,N)\rvert\le2\sqrt{\tfrac23}\,\sqrt q\log q< 2\sqrt q\log q$ である。
証明の所在と文献

1 は prf-pv-main、2 は prop-pv-imprimitive で証明する。Was82 Lemma 11.8(p. 214)は、始点を $0$ に固定した和 $\sum_{0\le n< u}\chi(n)$ について、原始指標で 1 と同じ形の評価(真の不等号)を述べ、原始的でない指標で定数 $2$ の形を別の文献を引いて注記している。区間の長さ $N$ が $\sqrt q\log q$ 以下なら自明な $\lvert S_\chi\rvert\le N$ の方が強いので、この不等式が意味をもつのは長い区間である。

Legendre 記号の区間和

奇素数 $p$ について $\chi=\left(\frac{\cdot}{p}\right)$(Legendre記号)は法 $p$ の原始指標である(Dirichlet指標 の例「小さな法の指標」)。区間和の絶対値の最大値 $\max_{M,N}\lvert S_\chi(M,N)\rvert$ は次のとおりで、下の prop-pv-lower の下界と定理の上界の間にある。

$p$区間和の最大値下界 $\sqrt p/(2\pi)$上界 $\sqrt p\log p$自明な上界 $(p-1)/2$
$7$$2$$0.42$$5.1$$3$
$101$$14$$1.60$$46.4$$50$
$1009$$36$$5.06$$219.7$$504$
$10007$$130$$15.92$$921.4$$5003$

$p=7$ では値は $n=1,\dots,6$ で $1,1,-1,1,-1,-1$ であり、部分和は $1,2,1,2,1,0$ なので最大値は $2$ である。$p$ が小さいうちは自明な上界の方が強く、$p$ が大きくなると定理の上界が自明な上界を大きく下回る。

証明

証明は 3 つの補題に分かれる。有限 Fourier 展開で指標を加法的な指標の和に書き(lem-pv-fourier)、加法的な指標の区間和を等比級数として評価し(lem-pv-geometric)、出てくる調和級数を対数で抑える(lem-pv-harmonic)。

原始指標の有限 Fourier 展開

$\chi$ を法 $q$ の原始指標とする。$\tau(\bar\chi):=\sum_{a=1}^{q}\bar\chi(a)e(a/q)$ とおくと $\lvert\tau(\bar\chi)\rvert=\sqrt q$ であり、すべての整数 $n$ について
$$ \chi(n)=\frac1{\tau(\bar\chi)}\sum_{a=1}^{q}\bar\chi(a)\,e\Bigl(\frac{an}q\Bigr) $$
である。

$\chi$ が原始指標なら共役 $\bar\chi$ も原始指標である($\bar\chi(a)=1$ と $\chi(a)=1$ は同値なので、Dirichlet指標 の定義「導手と原始指標」の「法 $d$ で定まる」は $\chi$ と $\bar\chi$ で同じである)。Gauss和 の定理「原始指標のGauss和」を $\bar\chi$ に適用すると、2 から $\lvert\tau(\bar\chi)\rvert^2=q$ で、1 から、すべての整数 $n$ について
$$ \sum_{a=1}^{q}\bar\chi(a)e\Bigl(\frac{an}q\Bigr)=\tau_n(\bar\chi)=\overline{\bar\chi(n)}\,\tau(\bar\chi)=\chi(n)\tau(\bar\chi) $$
である。$\tau(\bar\chi)\ne0$ で割ればよい。$\square$

加法的な指標の区間和

$q\ge2$、$a$ を $q$ の倍数でない整数とすると、すべての整数 $M$ と $N\ge0$ について
$$ \Bigl\lvert\sum_{M< n\le M+N}e\Bigl(\frac{an}q\Bigr)\Bigr\rvert\le\frac1{\lvert\sin(\pi a/q)\rvert} $$
である。

$w:=e(a/q)\ne1$ とおくと、和は等比級数で $w^{M+1}\frac{w^N-1}{w-1}$ に等しい。$\lvert w^N-1\rvert\le2$、$\lvert w-1\rvert=\lvert e^{\pi ia/q}\rvert\cdot\lvert e^{\pi ia/q}-e^{-\pi ia/q}\rvert=2\lvert\sin(\pi a/q)\rvert$ から従う。$\square$

調和数の評価

$H_m:=\sum_{a=1}^{m}\frac1a$ とすると、$m\ge0$ について $H_m\le\log(2m+1)$ である。

$1/x$ は $x>0$ で下に凸なので、$a\ge1$ について $\int_{a-1/2}^{a+1/2}\frac{dx}x\ge\frac1a$ である(区間 $[a-\frac12,a+\frac12]$ で $\frac1x\ge\frac1a-\frac{x-a}{a^2}$ が成り立ち、右辺の 1 次の項の積分は $0$)。$a=1,\dots,m$ で足すと $H_m\le\int_{1/2}^{m+1/2}\frac{dx}x=\log(2m+1)$ である。$\square$

原始指標の場合

$\chi$ を法 $q$ の自明でない原始指標とする。法 $1$ の指標は自明な指標だけで、法 $2$ の指標も自明な指標だけなので $q\ge3$ である。lem-pv-fourier を $n=M+1,\dots,M+N$ について足すと
$$ S_\chi(M,N)=\frac1{\tau(\bar\chi)}\sum_{a=1}^{q-1}\bar\chi(a)\sum_{M< n\le M+N}e\Bigl(\frac{an}q\Bigr) $$
となる($a=q$ の項は $\bar\chi(q)=0$ なので落とした)。$q$ が偶数なら $a=q/2$ の項も $\bar\chi(q/2)=0$ なので落ちる($q\ge4$ で $\gcd(q/2,q)=q/2\ge2$)。$\lvert\tau(\bar\chi)\rvert=\sqrt q$ と lem-pv-geometric から
$$ \lvert S_\chi(M,N)\rvert\le\frac1{\sqrt q}\sum_{\substack{1\le a\le q-1\\ a\ne q/2}}\frac1{\sin(\pi a/q)}=\frac2{\sqrt q}\sum_{1\le a< q/2}\frac1{\sin(\pi a/q)} $$
である($\sin(\pi(q-a)/q)=\sin(\pi a/q)$ により $a$ と $q-a$ の項が等しい)。$0\le x\le\frac\pi2$ では $\sin x\ge\frac{2x}\pi$($\sin$ は $[0,\frac\pi2]$ で上に凸)なので、$1\le a< q/2$ について $\frac1{\sin(\pi a/q)}\le\frac q{2a}$ である。$a< q/2$ となる正の整数は $a\le m:=\lfloor(q-1)/2\rfloor$ であり、lem-pv-harmonic と $2m+1\le q$ から
$$ \lvert S_\chi(M,N)\rvert\le\frac2{\sqrt q}\cdot\frac q2\,H_m=\sqrt q\,H_m\le\sqrt q\log(2m+1)\le\sqrt q\log q $$
を得る。$\square$

原始的でない指標は、導手の法の原始指標から誘導されたものなので、Möbius関数 で「法 $q$ と互いに素」という条件をほどけば 1 に帰着する。

原始的でない指標

$\chi$ を法 $q$ の自明でない指標、$\chi^*$ をそれに付随する法 $q^*$ の原始指標とし、$r$ を $q$ を割り $q^*$ を割らない素数すべての積とする。$\omega(r)$ を $r$ の素因数の個数とすると
$$ \lvert S_\chi(M,N)\rvert\le2^{\omega(r)}\sqrt{q^*}\log q^*\le2\sqrt{\tfrac23}\,\sqrt q\log q $$
である。とくに定理の 2 が成り立つ。

Dirichlet指標 の定理「導手の性質と付随する原始指標」により、$\gcd(n,q)=1$ なら $\chi(n)=\chi^*(n)$ である。$\chi$ は自明でないので $\chi^*$ も自明でなく、$q^*\ge3$ である。
$\chi$ を $\chi^*$ で書く。 $\gcd(n,q)=1$ は「$\gcd(n,q^*)=1$ かつ $\gcd(n,r)=1$」と同値である($q$ の素因数は $q^*$ か $r$ の素因数)。$\gcd(n,q^*)>1$ なら $\chi^*(n)=0$ なので、すべての $n$ で
$$ \chi(n)=\chi^*(n)\,[\gcd(n,r)=1]=\chi^*(n)\sum_{d\mid\gcd(n,r)}\mu(d) $$
である($[\cdot]$ は条件が成り立てば $1$、そうでなければ $0$。最後の等号は Möbius 関数の基本性質 $\sum_{d\mid k}\mu(d)=[k=1]$)。
和を入れ替える。 $n=dm$ と書くと $\chi^*(dm)=\chi^*(d)\chi^*(m)$ なので
$$ S_\chi(M,N)=\sum_{d\mid r}\mu(d)\chi^*(d)\sum_{M/d< m\le(M+N)/d}\chi^*(m) $$
である。内側の和は $\chi^*$ の区間和なので、prf-pv-main により絶対値は $\sqrt{q^*}\log q^*$ 以下である。$r$ は平方因子をもたないので約数は $2^{\omega(r)}$ 個で、最初の不等式を得る。
定数を整える。 $r$ と $q^*$ は互いに素でどちらも $q$ を割るので $rq^*\le q$ であり、$\sqrt{q^*}\le\sqrt{q/r}$ である。
$$ \frac{2^{\omega(r)}}{\sqrt r}=\prod_{p\mid r}\frac2{\sqrt p}\le\frac2{\sqrt2}\cdot\frac2{\sqrt3}=2\sqrt{\tfrac23} $$
である($p\ge5$ なら $2/\sqrt p< 1$)。$\log q^*\le\log q$ と合わせて 2 番目の不等式を得る。$2\sqrt{2/3}\approx1.633< 2$ である。$\square$

下からの評価

不等式の $\sqrt q$ は、対数の因子を除けば改良できない。区間和が全部小さいと、Gauss 和も小さくなってしまうからである。

区間和の最大値の下界

$\chi$ を法 $q$ の自明でない原始指標とすると
$$ \max_{1\le N< q}\lvert S_\chi(0,N)\rvert>\frac{\sqrt q}{2\pi} $$
である。

$A(n):=S_\chi(0,n)$ とおくと $A(0)=0$、$A(q)=0$(1 周期の和)、$\chi(n)=A(n)-A(n-1)$ である。$\tau(\chi):=\sum_{n=1}^{q}\chi(n)e(n/q)$ を部分和で書き直すと
$$ \tau(\chi)=\sum_{n=1}^{q}A(n)e\Bigl(\frac nq\Bigr)-\sum_{n=0}^{q-1}A(n)e\Bigl(\frac{n+1}q\Bigr)=\sum_{n=1}^{q-1}A(n)\Bigl(e\Bigl(\frac nq\Bigr)-e\Bigl(\frac{n+1}q\Bigr)\Bigr) $$
である。$\bigl\lvert e(\frac nq)-e(\frac{n+1}q)\bigr\rvert=2\sin\frac\pi q\le\frac{2\pi}q$ なので、$A^*:=\max_{1\le N< q}\lvert A(N)\rvert$ とおくと $\lvert\tau(\chi)\rvert\le(q-1)\frac{2\pi}qA^*$ である。Gauss和 の定理「原始指標のGauss和」の 2 より $\lvert\tau(\chi)\rvert=\sqrt q$ なので、$A^*\ge\frac q{q-1}\cdot\frac{\sqrt q}{2\pi}>\frac{\sqrt q}{2\pi}$ である。$\square$

ex-pv-legendre の表では、区間和の最大値は $\sqrt p$ の $0.75$ 倍から $1.4$ 倍程度で、上界 $\sqrt p\log p$ よりも下界 $\sqrt p/(2\pi)$ に近い。法 $400$ 以下のすべての奇素数で、Legendre 記号の区間和の最大値は $\sqrt p\log p$ の $0.556$ 倍以下である(ex-pv-legendre と同じ計算)。

応用

最小の平方非剰余

奇素数 $p$ について、法 $p$ の最小の正の 平方非剰余 を $n(p)$ とすると
$$ n(p)\le\lfloor\sqrt p\log p\rfloor+1 $$
である。

$N:=n(p)-1$ とおく。$1,\dots,N$ はすべて平方剰余なので $\left(\frac np\right)=1$($1\le n\le N$)であり、$\chi=\left(\frac{\cdot}{p}\right)$ について $S_\chi(0,N)=N$ である。$\chi$ は法 $p$ の原始指標なので thm-pv-main の 1 から $N\le\sqrt p\log p$、すなわち $n(p)\le\lfloor\sqrt p\log p\rfloor+1$ である。$\square$

実際の $n(p)$ はこれよりずっと小さい。$p\le20000$ の奇素数で $n(p)$ の最大値は $p=18191$ での $n(p)=29$ だが、この $p$ での上界は $\sqrt p\log p\approx1322.9$ である。

$L(1,\chi)$ の上界

$\chi$ を法 $q$ の自明でない指標とし、$B:=\sup_{N\ge0}\lvert S_\chi(0,N)\rvert$ とおく。Dirichlet L関数 の $s=1$ での値 $L(1,\chi)=\sum_{n\ge1}\chi(n)/n$ について
$$ \lvert L(1,\chi)\rvert< 1+\log(B+1) $$
である。とくに $\chi$ が原始指標なら $\lvert L(1,\chi)\rvert< 1+\log(\sqrt q\log q+1)$ である。

$A(n):=S_\chi(0,n)$ とおくと $\lvert A(n)\rvert\le\min(n,B)$ である。Abelの総和公式 と同じ和の組み替えで
$$ \sum_{n=1}^{N}\frac{\chi(n)}n=\frac{A(N)}N+\sum_{n=1}^{N-1}\frac{A(n)}{n(n+1)} $$
であり、$\lvert A(N)\rvert\le B$ なので $N\to\infty$ で $L(1,\chi)=\sum_{n\ge1}\frac{A(n)}{n(n+1)}$(右辺は絶対収束)を得る。$X:=\lfloor B\rfloor$ として $n\le X$ では $\lvert A(n)\rvert\le n$、$n>X$ では $\lvert A(n)\rvert\le B$ を使うと
$$ \lvert L(1,\chi)\rvert\le\sum_{n=1}^{X}\frac1{n+1}+B\sum_{n>X}\frac1{n(n+1)}=(H_{X+1}-1)+\frac B{X+1}< H_{X+1} $$
である($H_k=\sum_{a\le k}1/a$、$X+1>B$)。$k\ge1$ で $H_k\le1+\log k$($a\ge2$ で $\frac1a\le\int_{a-1}^{a}\frac{dx}x$)なので、$\lvert L(1,\chi)\rvert< 1+\log(X+1)\le1+\log(B+1)$ である。原始指標の場合は thm-pv-main の 1 で $B\le\sqrt q\log q$ である。$\square$

$\chi=\left(\frac{\cdot}{p}\right)$ では、$L(1,\chi)$ の値(20 万項の部分和)と上界 $1+\log(\sqrt p\log p+1)$ は、$p=5$ で $0.430$ と $2.53$、$p=101$ で $0.597$ と $4.86$、$p=1009$ で $3.078$ と $6.40$ である。上界は $\frac12\log q+\log\log q$ 程度の増え方である。

反例:条件を外すと成り立たないこと

外す条件反例成り立たなくなること
thm-pv-main で $\chi$ が自明でないこと法 $101$ の自明な指標 $\chi_0$$S_{\chi_0}(0,100)=100$ で、$\sqrt{101}\log101\approx46.38$ を超える。区間和は長さに比例して増える
thm-pv-main で $\chi$ が指標であること法 $101$ の周期関数 $f$:$1\le n\le50$ で $1$、$51\le n\le100$ で $-1$、$101\mid n$ で $0$値は $\pm1,0$ で 1 周期の和も $0$ だが、$\sum_{n\le50}f(n)=50>46.38$ である
lem-pv-fourier で $\chi$ が原始指標であること法 $6$ の指標 $\chi(1)=1$、$\chi(5)=-1$$\tau(\bar\chi)=\sqrt3\,i$ で、$n=2$ の右辺は $\tau_2(\bar\chi)/\tau(\bar\chi)=1$ だが $\chi(2)=0$ である(Gauss和 の例による)
prop-pv-lower で $\chi$ が原始指標であること法 $81$ の指標で $\left(\frac{\cdot}{3}\right)$ から誘導されたもの値は $1,-1,0$ の繰り返しなので区間和は $-1,0,1$ のどれかで、最大値は $1$ だが、$\sqrt{81}/(2\pi)\approx1.43$ である

3 行目と 4 行目の指標では、導手($3$)が法より小さいことが原因である。prop-pv-imprimitive の評価では、$\sqrt q$ の代わりに導手の平方根 $\sqrt{q^*}$ が現れる。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する