離散數學/解析數論

介紹

解析數論是將分析應用於數論問題的學科。以下是對解析數論中某些部分的簡要概述。

Zeta 函式

Zeta 函式，定義為

$\zeta (s)=\sum _{n=1}^{\infty }n^{-s}$

對於 s > 1 的實數值，在該理論中起著核心作用。當 s > 1 時，它絕對收斂。它滿足尤拉積公式，

$\zeta (s)=\prod _{p}{\frac {1}{1-p^{-s}}}$

其中積是對所有素數進行的。要看到這一點，請注意，將級數定義乘以 1-2^-s 並重新排列項（由於級數絕對收斂，因此這是合理的）會消除偶數項，即 ${\displaystyle (1-2^{-s})(1+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+{\frac {1}{4^{s}}}+{\frac {1}{5^{s}}}+\ldots )=(1+{\frac {1}{2^{s}}}+{\frac {1}{3^{s}}}+{\frac {1}{4^{s}}}+{\frac {1}{5^{s}}}+\ldots )-({\frac {1}{2^{s}}}+{\frac {1}{4^{s}}}+{\frac {1}{6^{s}}}+{\frac {1}{8^{s}}}+{\frac {1}{10^{s}}}+\ldots )=(1+{\frac {1}{3^{s}}}+{\frac {1}{5^{s}}}+{\frac {1}{7^{s}}}+\ldots )}">$

同樣，在乘以 1-3^-s 後，所有剩餘的 n 被 3 整除的項都被消除了。在對所有素數重複此過程後，可以得出

$\zeta (s)\prod _{p}\left(1-p^{-s}\right)=1$

因為 1 是唯一一個不被素數整除的數，因此只有 n=1 項保留下來。解出 ζ(s) 立即給出尤拉積公式。

狄利克雷級數

Zeta 函式的級數是狄利克雷級數的一個特例。狄利克雷級數是以下形式之一：

$\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}$ 其中 $a$ 是一個複數序列。

許多重要的算術函式，$a$，都具有以下性質：$a(1)=1$ 以及 $a(m)a(n)=a(mn)$ 當 $m$ 和 $n$ 互質時。這種函式被稱為 **積性** 函式。

對於一個積性函式 $a$，其對應的狄利克雷級數可以用尤拉積表示為

$\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}=\prod _{p}\sum _{k=0}^{\infty }{\frac {a(p^{k})}{p^{ks}}}$.

這可以透過類似於 ζ 函式證明的方式來證明。

一個 **完全積性** 函式指的是即使 $m$ 和 $n$ 不互質，也滿足 $a(m)a(n)=a(mn)$ 的函式。

對於一個完全積性函式，尤拉積簡化為

$\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}}=\prod _{p}{\frac {a(p)}{1-p^{-s}}}$.

兩個狄利克雷級數的積由以下公式給出

$\left(\sum _{k=1}^{\infty }{\frac {a(k)}{k^{s}}}\right)\left(\sum _{m=1}^{\infty }{\frac {b(m)}{m^{s}}}\right)=\sum _{n=1}^{\infty }{\frac {(a*b)(n)}{n^{s}}}$

其中 $a*b$ 表示 $a$ 和 $b$ 的狄利克雷卷積，定義為

$(a*b)(n)=\sum _{d|n}a(d)b\left({\frac {n}{d}}\right)$

一些重要的狄利克雷級數包括

${\frac {\zeta ^{\prime }(s)}{\zeta (s)}}=\sum _{n=1}^{\infty }{\frac {\Lambda (n)}{n^{s}}}$

${\frac {1}{\zeta (s)}}=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}$

$\zeta (s-k)=\sum _{n=1}^{\infty }{\frac {n^{k}}{n^{s}}}$

以及

$\zeta (s)\zeta (s-k)=\sum _{n=1}^{\infty }{\frac {\sigma _{k}(n)}{n^{s}}}$

大O符號

許多問題涉及難以精確處理的函式，但函式的增長速度而不是其確切值才是主要關注點。 因此發明了一種記號（通常稱為“大O符號”）。

符號

$f(x)=O(g(x))$

用於表示，對於足夠大的數 $x_{0}$，存在一個數 $C$ 使得

$\left|f(x)\right|\leq Cg(x)$ 對所有 $x>x_{0}$ 成立。

表示式 $f(x)=g(x)+O(h(x))$ 表示 $f(x)-g(x)=O(h(x))$.

狄利克雷定理

解析數論證明的第一個結果之一是狄利克雷定理，該定理指出，對於任何兩個互質整數 a 和 b，存在無窮多個 k 值，使得 ak+b 是素數。證明涉及定義在整數集上的復值函式，稱為狄利克雷特徵，其性質為 χ(n) 僅取決於它模 a 的剩餘類，χ(n) 是完全可乘的，並且 χ(n) = 0 當且僅當 a 和 n 不互質。主特徵 χ₀ 定義為當 a 和 n 互質時為 1，否則為 0。很容易證明 χ₀ 是一個特徵。可以證明特徵的數量等於 φ(a)。還可以證明，當 $n\equiv 1{\pmod {a}}$ 時，所有特徵 χ 上 χ(n) 值的總和等於 φ(a)，否則為 0。與特徵對應的狄利克雷級數稱為狄利克雷 L 級數，傳統上用 L(s,χ) 表示。很容易證明 L(1,χ₀) 發散。透過一個複雜的論證，可以證明當 χ 非主時，L(1,χ) 收斂且不為零。函式

$\sum _{p\equiv b{\pmod {a}}}{\frac {1}{p}}=\sum _{\chi }{\frac {L(1,\chi )}{\chi (b)}}+O(1)$

必須發散，因為 L(1,χ₀)/χ(b) 發散，而其他項都收斂。由於左側和中所有項都是有限的，它的發散意味著該和有無窮多個項，因此有無窮多個形如 ak+b 的素數。

黎曼ζ函式和ξ函式

上面介紹的ζ函式（尤拉ζ函式）對於所有滿足 Re(s)>1 的 s 值收斂。黎曼ζ函式定義為尤拉ζ函式的解析延拓，並且對於所有複數 s 值定義，除了 s=1。在兩個函式都存在的地方，尤拉ζ函式和黎曼ζ函式在定義上是相等的。可以證明，如果ξ函式定義為

$\xi (s)={\frac {1}{2}}s(s-1)\Gamma ({\frac {s}{2}})\pi ^{-{\frac {s}{2}}}\zeta (s)$

那麼 ξ(s)=ξ(1-s)。這是黎曼ζ函式著名函式方程的對稱形式，為當 Re(s)<1 時計算黎曼ζ函式提供了一種方便的方法。

尤拉ζ函式的級數定義表明 ζ(s) 在 Re(s)>1 時沒有零點。還可以證明ζ函式在 Re(s)=1 時沒有零點。函式方程表明，對於整數 n 值，ζ(-2n)=0，任何其他零點都位於所謂的臨界帶中，0<Re(s)<1。眾所周知的黎曼猜想指出，所有非平凡零點（即不是 s=-2n 形式的零點），都有 Re(s)=1/2。很容易證明 ξ 函式的零點恰好是 ζ 函式的非平凡零點。

哈達瑪積公式

哈達瑪積公式指出，具有某些性質的函式（特別是 ξ 函式）足夠接近多項式，因此可以使用零點上的乘積表示它們。對於 ξ 函式，哈達瑪積公式指出

$\xi (s)=e^{A+Bs}\prod _{\rho }(1-{\frac {s}{\rho }})$

對於 A 和 B 的某些值，其中乘積在 ξ(s) 的零點上進行。這個公式是 ξ 函式零點（因此是 ζ 函式零點）極其重要的主要原因之一。

無平方數的分佈

設 S(x) 表示小於或等於 x 的無平方數的數量。為了計算這個函式，我們首先計算所有小於或等於 x 的整數。然後我們減去那些可以被 4 整除的數，那些可以被 9 整除的數，那些可以被 25 整除的數，等等。然後我們移除了具有 2 個重複素因子的數字，這些數字是具有 3 個重複素因子的數字的兩倍，依此類推。為了彌補具有 2 個重複素因子的數字的重複，我們加上小於或等於 x 的可以被 36 整除的數字，那些可以被 100 整除的數字，那些可以被 225 整除的數字，等等。現在我們已經重新包含了那些具有 3 個重複素因子的數字，所以我們必須把它們去掉。繼續這個過程會得到

$S(x)=\sum _{n^{2}\leq x}\mu (n)\left\lfloor {\frac {x}{n^{2}}}\right\rfloor =\sum _{n^{2}\leq x}\mu (n){\frac {x}{n^{2}}}+O({\sqrt {x}})={\frac {x}{\zeta (2)}}+O({\sqrt {x}})={\frac {6}{\pi ^{2}}}x+O({\sqrt {x}})$

除了關於無平方數的常見程度的資訊外，這個估計還提供了關於它們分佈的資訊。例如，要證明存在無窮多個成對的連續無平方數（即差值為 1 的無平方數），假設只有有限多個這樣的對。那麼存在某個 x₀，使得所有這樣的對都位於 x₀ 以下。然後對於 n > x₀，n 和 n+1 不能都是無平方數，因此 x₀ 以上最多有一半的整數是無平方數，或者更準確地說，

$S(x)\leq {\frac {1}{2}}(x-x_{0})+x_{0}+1={\frac {x}{2}}+O(1)$

但由於 ${\frac {6}{\pi ^{2}}}>{\frac {1}{2}}$ 這與之前獲得的估計相矛盾，因此存在無窮多個成對的連續無平方數。

該估計還表明，對於足夠大的 x，在 x^3 和 (x+1)^3 之間至少存在一個無平方數。要看到這一點，請注意該範圍內無平方數的個數為

$S\left((x+1)^{3}\right)-S(x^{3})={\frac {6}{\pi ^{2}}}\left((x+1)^{3}-x^{3}\right)+O\left({\sqrt {(x+1)^{3}}}\right)+O\left({\sqrt {x^{3}}}\right)={\frac {18}{\pi ^{2}}}x^{2}+O\left(x^{3 \over 2}\right)$

對於足夠大的 x，這至少為 1。

待辦事項：新增關於素數定理和篩法以及狄利克雷反演的提及