离散数学/解析数论

介绍

解析数论是将分析应用于数论问题的学科。以下是对解析数论中某些部分的简要概述。

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。

待办事项：添加关于素数定理和筛法以及狄利克雷反演的提及