用户: Cybcat/一些解析数论

这个笔记的内容来自很多乱七八糟的地方, 比如 GTM 74 《乘性数论》, 又比如一篇叫做 Hardy–Ramanujan’s Asymptotic Formula for Partitions and the Central Limit Theorem 的论文. 写到最后又觉得, 很多东西其实和解析数论半毛钱关系没有, 更像是某些披着不知道什么外衣的数论大杂烩.

1第一幕

观察

对于 $p$ 是一个奇素数, 我们很关心如下的一个求和:

$$s(p):=\sum _{m=1}^{(p-1)/2}\left(\frac{m}{p}\right).$$

其中 $\left(\frac{m}{p}\right)$ 是 Jacobi 符号. 首先我们仔细地计算一些小 $p$ 时候的情况:

例 1.1. 当 $p<200$ 时, 我们计算得到 $(p,s(p))$ 的值为$$\begin{array}{rl}& (3,1),(5,0),(7,1),(11,3),(13,0),(17,0),(19,3),(23,3),\\ & (29,0),(31,3),(37,0),(41,0),(43,3),(47,5),(53,0),(59,9),\\ & (61,0),(67,3),(71,7),(73,0),(79,5),(83,9),(89,0),(97,0),\\ & (101,0),(103,5),(107,9),(109,0),(113,0),(127,5),(131,15),\\ & (137,0),(139,9),(149,0),(151,7),(157,0),(163,3),(167,11),\\ & (173,0),(179,15),(181,0),(191,13),(193,0),(197,0),(199,9).\end{array}$$

实际上有这样一系列可以从上表中迅速看出却不平凡的事实. 读者不难证明 $p\equiv 1\mathrm{mod}4$ 时 $s(p)$ 总是 $0$, 当 $p\equiv 3(\mathrm{mod}4)$ 时因为求和有奇数项所以它总不是 $0$, 但奇怪的是它总是正的, 说明二次剩余都喜欢待在前半个区间里面. 还有更奇怪的事, $p\equiv 3(\mathrm{mod}8)$ 时除了 $3$ 以外它一定是 $3$ 的倍数.

证明

这两个结果有一个令人震惊的, 统一的, 却又无比简单的解释.

定理 1.2. $p\equiv 3(\mathrm{mod}4)$ 且 $p>3$ 时总成立着$$s(p)=\left(2-\left(\frac{2}{p}\right)\right)h(-p).$$其中 $h(-p)$ 为 $\mathbb{Q}(\sqrt{-p})$ 的类数.

证明. 首先我们取二次剩余 $\chi (m)=\left(\frac{m}{p}\right)$ 是模 $p$ 的实特征. 则$$L(s;\chi ):=\sum _{n=1}^{\infty }\left(\frac{n}{p}\right)n^{-s}={\left(1-\frac{1}{2^s}\left(\frac{2}{p}\right)\right)}^{-1}\sum _{n\in 2{\mathbb{Z}}_{\ge 0}+1}\left(\frac{n}{p}\right)n^{-s}.$$这是 Euler 乘积公式中将 $2$ 的部分单独分离出来立刻看出的.

紧接着我们很关心 $s=1$ 时候的值, 我们有两种方法计算它. 一种是直接计算求和, 另一种是使用类数公式. 为了证明的完整性, 我们都做的仔细一点.

首先是直接求和 $s=1$ 的时候, 我们需要做离散 Fourier 变换. 我们考虑 Gauss 和$$G(n):=\sum _{m=1}^p\left(\frac{m}{p}\right)e^{2\pi i\frac{mn}{p}}.$$我们熟知 $G(n)=\left(\frac{n}{p}\right)G(1)$, 因此直接把 $G(1)$ 除过去就得到$$\left(\frac{n}{p}\right)=\frac{1}{G(1)}\sum _{m=1}^p\left(\frac{m}{p}\right)e^{2\pi i\frac{mn}{p}}.$$将 $p\equiv 3(\mathrm{mod}4)$ 时 Gauss 和的非平凡结果 $G(1)=i\sqrt{p}$ 连同上式带回 $L(s,\chi )$ 表达式得$$L(1;\chi )={\left(1-\frac{1}{2}\left(\frac{2}{p}\right)\right)}^{-1}\sum _{n\in 2{\mathbb{Z}}_{\ge 0}+1}\frac{1}{i\sqrt{p}}\sum _{m=1}^p\left(\frac{m}{p}\right)e^{2\pi i\frac{mn}{p}}\cdot \frac{1}{n}.$$通过交换求和顺序我们只需计算$$\sum _{n\in 2{\mathbb{Z}}_{\ge 0}+1}{e}^{2\pi i\frac{mn}{p}}\cdot \frac{1}{n}=\frac{1}{2}\ln \left(\frac{1+e^{2\pi i\frac{m}{p}}}{1-e^{2\pi i\frac{m}{p}}}\right)=\{\begin{array}{ll}i\pi /4,& 0<m<p/2,\\ -i\pi /4,& p/2<m<p.\end{array}$$于是利用 ${\sum }_{m=1}^p\left(\frac{m}{p}\right)=0$ 可将原式化简为$$\begin{array}{rl}L(1;\chi )=& {\left(1-\frac{1}{2}\left(\frac{2}{p}\right)\right)}^{-1}\frac{1}{i\sqrt{p}}\frac{i\pi }{4}\left(\sum _{m=1}^{(p-1)/2}\left(\frac{m}{p}\right)-\sum _{m=(p+1)/2}^p\left(\frac{m}{p}\right)\right)\\ =& \frac{\pi \cdot s(p)}{\left(2-\left(\frac{2}{p}\right)\right)\sqrt{p}}.\end{array}$$值得说明的是到这里我们其实知道 $L(1;\chi )\in {\mathbb{R}}_{>0}$, 这件事只依赖于 Euler 乘积公式而与我们后面的讨论无关.

另一方面根据 Dirichlet 的虚二次域的类数公式, 对 $p>3$ 时 (域 $\mathbb{Q}(\sqrt{-p})$ 中只有平凡单位根, 由此修正的因子 $\omega =2$, 这也解释了为何 $p=3$ 时不是 $3$ 的倍数) 我们应该有$$L(1;\chi )=\frac{\pi h(-p)}{\sqrt{p}}.$$于是对照两条表达式立刻得出我们需要的结论.

$\square$

杂谈

这里暗示了一个问题, 如果我们指望证明 $s(p)\ge 0$, 就需要确定 Gauss 和的符号 $G(1)=i\sqrt{p}$. 但是好玩的事情在于我们成功把 Gauss 和的符号问题完全转化为了一个和 $\mathrm{Gal}(\mathbb{C}/\mathbb{R})$ 完全无关的问题. 凭这一点我很难相信 $s(p)\ge 0$ 有什么简单的初等证明, 当然如果真的有的话快快联系笔者.

另外和这个问题形式相似地, 我们还有著名的 Pólya–Vinogradov 不等式, 即对模 $p$ 非主特征, 总有$$\left|\sum _{k=1}^B\chi (k)\right|\le \sqrt{p}\ln p.$$对于这个问题来说这个界太差了, 对于类数来说我们也完完全全可以轻松给出 $\sqrt{p}$ 级别的界. 不过有意思的是这个界也带来很多其他不平凡的估计, 最容易用简单的语言讲清楚的或许是: 它告诉我们前 $\sqrt{p}\ln p$ 个数中总有 $d$(其中 $d|(p-1)$) 次非剩余, 每连续的 $2\sqrt{p}\ln p$ 个数中也是如此. 它的证明也并不复杂, 就是简单地将 $1_{[1,B]\cap \mathbb{Z}}$ 作离散 Fourier 变换.

2第二幕

要说我见过最奇妙, 最美丽的阶, 我必须要向你展示$$p(n)\sim \frac{e^{\pi \sqrt{2n/3}}}{4n\sqrt{3}}.$$其中 $p(n)$ 是所谓的无限制分拆数, 例如 $p(5)=7$, 因为$$\begin{array}{rl}5=& 5\\ =& 4+1\\ =& 3+2\\ =& 3+1+1\\ =& 2+2+1\\ =& 2+1+1+1\\ =& 1+1+1+1+1.\end{array}$$

Euler 发现了著名的乘积公式, 基本按照分拆数的定义就能算出$$f(z)=\sum _{n=0}^{\infty }p(n)z^n=\prod _{k=1}^{\infty }(1+z^k+z^{2k}+z^{3k}+\cdots )=\prod _{k=1}^{\infty }\frac{1}{1-z^k}.$$

这个阶之所以奇妙, 首先它看起来就不那么容易证明, 虽然形式并不那么完美, 但是 $e,\pi$ 和根号还有各种常数在其中排布得当. 它最经典的方法也是用解析数论中的圆法, 读者不仅需要了解模群和 Farey 分数, 具体计算的时候也需要取一个乱七八糟的围道. 然而神奇的是这阶的证明竟有一个 (披着) 概率论 (外衣的) 方法, 本质上说, 和 Hayman 对 Stirling 公式的推广想法是一样的. 我们马上就来介绍它.

想法

对幂级数 $f(z)={\sum }_{n=0}^{\infty }{a}_n{z}^n$, 满足 $a_n\ge 0$ 且收敛半径 $0<R<+\infty$. 那么对任意 $t\in (0,R)$ 我们都能考虑一个随机变量 $X_t$, 满足$$\mathbf{P}[X_t=n]=\frac{a_n{t}^n}{f(t)}.$$依定义它的特征函数为$$\mathbf{E}[e^{i\theta X_t}]=\frac{f(t{e}^{i\theta })}{t}.$$而期望和方差也能简单地算出来. $$m(t)=t\frac{d}{dt}\ln f(t),{\sigma }^2(t)=t\frac{d}{dt}m(t).$$随着 $t\to R^{-}$ 容易证明 $m(t)\to +\infty$, 不妨设我们的 $f$ 很好, 使得 $\sigma (t)\to +\infty$. 也许你会认为这并没有什么稀奇的, 但是如果我们考虑一族 $f$ 呢?

现在考虑 $f(z)={\prod }_{k=1}^{\infty }{f}_k(z)$, 其中 $f_k$ 是一系列收敛半径 $R$ 的非负系数的幂级数, 而乘积在半径内满足内闭绝对一致收敛. 现在考虑 $X_{t,k}$ 为按照上面的方法定义的 $f_k$ 关联的一族独立的随机变量. 我们就会自然地考虑 $\sum X_{t,k}$, 我们很自然地有比如 $L^2$ 的收敛性, 于是得到依概率收敛. 不难检查收敛到的 $X_t$ 确实也是 $f$ 定义出的随机变量. 但问题是, 收敛到的 $X(t)$ 是否是某种好的分布呢? 于是我们对其作标准化$$Z(t)=\frac{X_t-m(t)}{\sigma (t)}.$$那么 Fourier 变换得到$$\begin{array}{rl}{a}_n=& \frac{1}{2\pi t^n}{\int }_{-\pi }^{\pi }f(t{e}^{i\theta })e^{-in\theta }d\theta \\ =& \frac{f(t)}{2\pi \sigma (t)t^n}{\int }_{-\pi \sigma (t)}^{\pi \sigma (t)}\mathbf{E}[e^{i\theta Z(t)}]e^{-i\theta (n-m(t))}d\theta \\ =& \frac{f(t_n)}{2\pi \sigma (t_n)t_n^n}{\int }_{-\pi \sigma (t_n)}^{\pi \sigma (t_n)}\mathbf{E}[e^{i\theta Z(t_n)}]d\theta .\end{array}$$其中 $t=t_n$ 精心选择使 $m(t_n)=n$. 因为收敛半径为 $R$ 且 $m(t)$ 在 $[0,R)$ 从 $0$ 单增到无穷, 故总存在 $t_n\in [0,R)$ 符合条件. 那么我们的核心想法来叻:

如果 $Z(t_n)$ 足够接近标准正态分布, 那么 $\mathbf{E}[e^{i\theta Z(t_n)}]$ 就会足够接近 $e^{-{\theta }^2/2}$. 这样就得到$$a_n\sim \frac{f(t_n)}{\sqrt{2\pi }\sigma (t_n)t_n^n}.$$这意味着我们使用 $f$ 的值就估计出了其中的系数!

实践

为了让这个想法成功执行, 我们首先需要一个定义和一个引理.

定义 2.1. 前一小节记号中, 如果随 $t\to R^{-}$ 成立着$${\int }_{-\pi \sigma (t)}^{\pi \sigma (t)}\left|\mathbf{E}[e^{i\theta Z(t)}]-e^{-{\theta }^2/2}\right|d\theta \to 0,$$则称强 Gauss 条件得到满足.

引理 2.2. 如强 Gauss 条件满足, 假设随着 $t$ 单增到 $R$ 函数 $m_1(t)$ 连续严格单增到无穷, 函数 ${\sigma }_1(t)\sim \sigma (t)$, 且$$ϵ(t)=\frac{m_1(t)-m(t)}{\sigma (t)}\to 0.$$则我们能给出替代的估计$$a_n\sim \frac{f({\tau }_n)}{\sqrt{2\pi }{\sigma }_1({\tau }_n){\tau }_n^n},$$其中 $m_1({\tau }_n)=n$.

证明. 替代地令 $Z_1(t)=(X_t-m_1(t))/{\sigma }_1(t)$, 照葫芦画瓢也能算出$$\begin{array}{r}{a}_n=\frac{f({\tau }_n)}{2\pi {\sigma }_1({\tau }_n){\tau }_n^n}{\int }_{-\pi {\sigma }_1({\tau }_n)}^{\pi {\sigma }_1({\tau }_n)}\mathbf{E}[e^{i\theta Z_1({\tau }_n)}]d\theta .\end{array}$$然而另一边仔细比对得到$${\int }_{-\pi {\sigma }_1(t)}^{\pi {\sigma }_1(t)}\mathbf{E}[e^{i\theta Z_1(t)}]d\theta =\frac{{\sigma }_1(t)}{\sigma (t)}{\int }_{-\pi \sigma (t)}^{\pi \sigma (t)}\mathbf{E}[e^{i\theta Z(t)}]e^{iϵ(t)\theta }d\theta .$$于是强 Gauss 条件和控制收敛立刻推出随着 $t\to R^{-}$ 有$${\int }_{-\pi {\sigma }_1(t)}^{\pi {\sigma }_1(t)}\mathbf{E}[e^{i\theta Z_1(t)}]d\theta \to \sqrt{2\pi }.$$从而结论得证.

$\square$

那么回到原估阶问题. 自然地选取 $f_k=(1-z^k{)}^{-1}$, 对应 $X_{t,k}$. $R=1$, $m_{t,k}=\frac{k{t}^k}{1-t^k},{\sigma }_{t,k}^2=\frac{k^2{t}^k}{(1-t^k{)}^2}$. 记 $\rho :=-\log t$. 现在 Euler-Maclaurin 公式告诉我们$$\begin{array}{rl}m(t)=& \sum _{k=1}^{\infty }\frac{k{e}^{-\rho k}}{1-e^{-\rho k}}=\frac{{\pi }^2}{6{\rho }^2}+O(\frac{1}{\rho }),\\ {\sigma }^2(t)=& \sum _{k=1}^{\infty }\frac{k^2{e}^{-\rho k}}{(1-e^{-\rho k}{)}^2}\sim \frac{{\pi }^2}{3{\rho }^3}.\end{array}$$所以自然令 $m_1(t)=\frac{{\pi }^2}{6{\rho }^2},{\sigma }_1(t)=\frac{\pi }{\sqrt{3}{\rho }^{3/2}}$. 如此一来 ${\tau }_n=e^{-\pi /\sqrt{6n}}$, 而后注意到$$\ln f(e^{-\lambda })=-\sum _{m=1}^{\infty }\ln (1-e^{-m\lambda }),$$再使用一次 Euler-Maclaurin 公式计算得到对 $\lambda \to 0^{+}$, $$\ln f(e^{-\lambda })=\frac{{\pi }^2}{6\lambda }+\frac{1}{2}\log \lambda -1-{\int }_1^{\infty }q(x)\frac{\lambda }{e^{\lambda x}-1}dx+O(\lambda ),$$其中 $q(x)=x-\lfloor x\rfloor -1/2$, 而控制收敛得到$$\underset{\lambda \to 0^{+}}{\lim }{\int }_1^{\infty }q(x)\frac{\lambda }{e^{\lambda x}-1}dx={\int }_1^{\infty }q(x)\frac{dx}{x}=\frac{1}{2}\log (2\pi )-1,$$于是$$f(e^{-\lambda })\sim \frac{1}{\sqrt{2\pi }}{e}^{{\pi }^2/6\lambda }\sqrt{\lambda }.$$所以把这些乱七八糟的东西拼装到那个引理里, 立刻得到$$a_n\sim \frac{\frac{1}{\sqrt{2\pi }}{e}^{\pi \sqrt{n/6}}\sqrt{\pi /\sqrt{6n}}}{\sqrt{2\pi }\frac{\pi }{\sqrt{3}(\pi /\sqrt{6n}{)}^{3/2}}\cdot e^{-\pi \sqrt{n/6}}}=\frac{e^{\pi \sqrt{2n/3}}}{4n\sqrt{3}}.$$

收官

因此只需证明强高斯条件得到满足. 不难检查$$\mathbf{E}[Y_{t,k}^4]=\frac{k^4{t}^k(1+7t^k+t^{2k})}{(1-t^k{)}^4}\le 9\frac{k^4{t}^k}{(1-t^k{)}^4}.$$再次使用 Euler-Maclaurin, 表明$$\sum _{k=1}^{\infty }\mathbf{E}[|Y_{t,k}{|}^3]\le \sum _{k=1}^{\infty }\mathbf{E}[Y_{t,k}^4{]}^{3/4}\le \frac{c_1}{{\rho }^4}.$$那么具体地计算, 例如参考 Durrett 上 Lindeberg-Feller 定理证明中的估计, 立刻得到某个 $|\theta |\le \frac{c_2}{\sqrt{\rho }}$ 的范围内$$|\mathbf{E}[e^{i\theta Z(t)}]|\le \exp \left(-\frac{1}{2}{\theta }^2+\frac{2}{3}\frac{|\theta {|}^3}{{\sigma }^3(t)}\sum _{k=1}^{\infty }\mathbf{E}[|Y_{t,k}{|}^3]\right).$$这样我们只需对 $Z(t)$ 特征函数绝对值给出一个尾分布即可. $$\begin{array}{rl}\log |\mathbf{E}[e^{i\theta X_t}]|=& -\sum _{k=1}^{\infty }\sum _{v=1}^{\infty }\frac{t^{kv}}{v}(1-\cos (kv\theta ))\\ =& -\sum _{v=1}^{\infty }\frac{t^v(1+t^v)}{1-t^v}\frac{1}{4t^v+{\left(\frac{1-t^v}{\sin (v\theta /2)}\right)}^2}.\end{array}$$于是对 $\frac{1}{2}<t<1,c_3(1-t)<|\theta |\le \pi$ 时, $\log |\mathbf{E}[e^{i\theta X_t}]|\le -\frac{c_4}{1-t}$, 其中 $c_4=\frac{3}{4}(4+{\pi }^2{c}_3^{-2}{)}^{-1}$.

那么 $|\mathbf{E}[e^{i\theta Z(t)}]|$ 在 $|\theta |\le A,A\le |\theta |\le c_2{\rho }^{-1/2},c_2{\rho }^{-1/2}<|\theta |\le \pi \sigma (t)$ 一分段就得到了我们需要的结果. 其中 $|\theta |\le A$ 的部分贡献 $\exp (-{\theta }^2/2)$ 的主要部分. 本质上说, 如果估算地更细一点误差项也将能够控制.

后记

实际上有很多别的序列我们也非常关心, 比如$$\sum _{k=0}^{\infty }\tilde{p}(k)z^k:=\prod _{k=1}^{\infty }(1+z^k).$$它可以认为是某种 “有限制分拆数”, 而它的阶$${\tilde{p}}_n\sim \frac{e^{\pi \sqrt{(n-1/24)/3}}}{4\cdot 3^{1/4}\cdot (n-1/24{)}^{3/4}}.$$又比如著名的 j-不变量$$j(\bar{q}):=\frac{[1+240{\sum }_{n=1}^{\infty }{\sigma }_3(n){\bar{q}}^n{]}^3}{\bar{q}{\prod }_{n=1}^{\infty }(1-{\bar{q}}^n{)}^{24}}.$$它的系数以 $a_{-1}=1,a_0=744,a_1=196884$ 打头而著名, 它的阶$$a_n\sim \frac{e^{4\pi \sqrt{n}}}{2^{1/2}{n}^{3/4}}.$$而在阶的表达式中代入 $n=1$ 得到 $a_1\approx e^{4\pi }/\sqrt{2}\approx 202764$, 说明效果很好.

另外更一般的 ${\sum }_{n=0}^{\infty }{p}_s(n)z^n:={\prod }_{k=1}^{\infty }\frac{1}{(1-z^k{)}^s}$. 也能有类似的估计$$p_s(n)\sim c_n\frac{e^{\pi \sqrt{2sn/3}}}{n^{(3+s)/4}}.$$其中的 $c_n$ 是一个常数.

这些公式是否能通过我们介绍的方法得到就留给读者思考.

3第三幕

问题

相传有这样一道竞赛题:

定理 3.1. 设 $\{a_n{\}}_{n=1}^{\infty }$ 是正整数列, 假设存在常数 $c>0$ 使$$a_n<cn,$$证明存在正整数 $m\ne n$ 使 $a_m|a_n$.

后来我们得知著名的 Paul Erdos 写过一篇文章证明了这样一个定理:

定理 3.2. 设正整数列 $\{a_n{\}}_{n=1}^{\infty }$ 中没有两者具有倍数关系, 那么$$\sum _{n=1}^{\infty }\frac{1}{a_n\log a_n}<+\infty .$$

这显然能推出原问题, 因为 $\sum (cn\log (cn){)}^{-1}$ 发散. 实际上这些信息对满足题目条件的序列做出了一些控制. 说回来有一个著名的竞赛题说 $[1,2n]$ 之间任意 $n+1$ 个数必有两个数具有倍数关系, 选 $n$ 个数是不会出问题的, 因为可以选 $[n+1,2n]$ 间的所有数. 选不出 $n+1$ 个是因为将这些数写成 $2^s(2t+1)$ 的形状后, 由鸽笼原理必然有两个数具有相同的奇数部分. Chowla, Davenport 和 Erdos 曾猜测满足题目条件的数列 $a_n$ 的 (上) 密度为 $0$, 但这是不对的, 因为 Besicovitch 证明了具有 $[a,2a]$ 间因子的数的密度 $d_a$ 随着 $a\to +\infty$ 有 $\mathrm{liminf}{d}_a=0$. 这道竞赛题实则叙述的是 $a_n$ 的下密度为 $0$.

解答

记 $p_n$ 为 $a_n$ 的最大素因子, 我们将证明这样的不等式:

$$\sum _{n=1}^{\infty }\frac{1}{a_n}\prod _{\text{素数}p\le p_n}\left(1-\frac{1}{p}\right)\le 1.$$

倘若这已得证, 注意到这个乘积$$\prod _{\text{素数}p\le N}{\left(1-\frac{1}{p}\right)}^{-1}=O\left(\exp \left(\sum _{\text{素数}p\le N}\frac{1}{p}\right)\right)=O(\exp \log \log N)=O(\log N).$$

由此结合 $\log p_n\le \log a_n$ 即可得到 $(a_n\log a_n{)}^{-1}$ 的求和收敛. 为了检查我们所述命题的正确性, 用反证法, 设有 $N$ 使这不等式不真, 即$$\sum _{n=1}^N\frac{1}{a_n}\prod _{p\le p_n}\left(1-\frac{1}{p}\right)>1.$$

我们重排一下 $a$, 使它们的最大素因子不减, 这总能做到, 因为最大素因子小于常数者只能选出有限多没有倍数关系者. 待定一个大数 $n$, 用 (可能糟糕的记号) $n(a)$ 表示不超过 $n$ 的数中, 至少是某个 $a_k$ 倍数者; 用 $n(a_k)$ 表示不超过 $n$ 的数中, 是 $a_k$ 倍数但不是 $a_i(i<k)$ 倍数者. 这样依照定义有$$n(a)=\sum _{k=1}^{\infty }n(a_k)\ge \sum _{k=1}^{N}n(a_k).$$

接着估计 $n(a_k)$, 现在由于 $p_k$ 递增, $n(a_k)$ 统计了这样的数: $a_{k}x$, 其中 $x$ 是所有素因子都大于 $p_k$ 的正整数. 这样由 Eratosthenes 筛得到平凡下界$$n(a_k)\ge \frac{n}{a_k}\prod _{p\le p_k}\left(1-\frac{1}{p}\right)-2^k.$$

结尾要减去 $2^k$ 的原因是在边界有一些舍入, 乘积式最多涉及 $k$ 个素数, 容斥过程中全部按小的算就需要减掉 $2^k$ 个 $1$. 继续写不等式, 就有$$n\ge n(a)\ge \sum _{k=1}^N\frac{n}{a_k}\prod _{p\le p_k}\left(1-\frac{1}{p}\right)-\sum _{k=1}^N{2}^k.$$令 $n\to +\infty$ 然后约掉 $n$ 就得到欲证的结论.

4第四幕

差分

我们来讨论一个第一眼看起来和数论关系不大的组合数学对象, 差分集, 英文是 Difference Set. 它描述的是这么一个对象:

定义 4.1. 对于一个阶为 $v$ 的 Abel 群 $G$, 如果它的一个子集 $D$ 满足对 $0\ne g\in G$ 都有$$D_g:=(g+D)\cap D=\{d^{\prime }\in D:\exists d\in D,g+d=d^{\prime }\}$$的元素数量是一个与 $g$ 的选取无关的定值, 则称 $D$ 为一个差分集. 记 $k:=\#D,\lambda :=\#D_g$, 则具体地将 $D$ 称为 $(\mathbf{v},\mathbf{k},\mathbf{\lambda })$-差分集.

上面这些数也自然是刻画 $D$ 所需的最基本的数据. 此外我们再记 $n:=k(v-k)/(v-1)=k-\lambda$.

$\bullet$ 最浅显的观察是 $\lambda$ 其实能用 $v,k$ 计算出来. 具体来说, 我们有$$\lambda =\frac{k(k-1)}{v-1}.$$这非常容易, 因为简单的组合数学告诉我们, $\lambda$ 为任意 $0\ne g\in G$ 能被写成两个 $D$ 中元素之差的方法数, 这也解释了差分集的名字来源. 除了 $g=0$ 以外的 $v-1$ 个 $G$ 中元素, 每个都具有 $\lambda$ 种写法作为两个元素的差, 而有顺序地选取两个元素就有 $k(k-1)$ 种选法, 这就是上面的恒等式.

$\bullet$ 第二浅显的观察是, 我们很容易从一个差分集构造另一个差分集, Abel 群 $G$ 中差分集 $D$: 同时将其中的元素平移 $g$ 所得的 $g+D$(这称之为 $D$ 的平移, translate), 或者作用 $G$ 的自同构 $\sigma \in \mathrm{Aut}(G)$ 所得的 $\sigma D$, 都是 $(v,k,\lambda )$-差分集. 直观来说, $G$ 最常见的自同构无非是交换一些直和分量或者在 $\mathbb{Z}/n\mathbb{Z}$ 分量上左乘一个与 $n$ 互质的数. 另外取补集 $G\backslash D$ 将得到 $(v,v-k,v-2k+\lambda )$-差分集.

本文接下来的讨论中, 为了使问题简单化, 让我们暂且把 $G$ 限制为循环群 $\mathbb{Z}/v\mathbb{Z}$, 请相信我, 即便是循环群也已经够我们喝一壶的了.

到这里, 会觉得这些定义实在是太正常了. 说好的数论呢? 别急, 让我们来展示下面一系列经典的例子, 首先我们将不加证明地展示 $100$ 阶以内循环群具有的差分集:

展示

实际上, $100$ 阶以内的差分集分成很多个类型.

我们先直观感受两个最简单的例子, $v=7,11$ 时的$$\begin{array}{rlrlrlrlr}v=7,& & D=\{1,2,4\},& & k=3,& & \lambda =1,& & n=2;\\ v=11,& & D=\{1,3,4,5,9\},& & k=5,& & \lambda =2,& & n=3.\end{array}$$直观地检查一下它们是差分集, 用 $T$ 表示 $10$, 平移得到$$\begin{array}{rl}& 124,235,346,450,561,602,013;\\ & 13459,2456T,35670,46781,57892,\\ & 689T3,79T04,8T015,90126,T1237,02348.\end{array}$$

这两个例子体现了两个不同的类型. 第一种叫做 Singer 类, 第二种叫做 Paley 类, 这二者确实是 $v$ 较小时最常见的两种类型. 不过 $v=7$ 实在太小, 导致此时这两类刚好一致.

例 4.2. 差分集最经典的两类构造:

$\bullet$ Paley 类, 假设 $p=4s-1$ 是一个素数. 考虑 ${\mathbb{F}}_p$ 中全体 (非零的) 二次剩余, 一共有 $2s-1$ 个, 则它们构成的集合 $D$ 是一个差分集, 这里$$(v,k,\lambda )=(4s-1,2s-1,s-1).$$

$\bullet$ Singer 类, 假设 $q=p^r$ 是素数幂, $s$ 是一个正整数. 考虑 $G={\mathbb{F}}_{q^{s+2}}^{\times }/{\mathbb{F}}_q^{\times }$, 因为有限域的乘法群是循环群, 所以 $G$ 是循环群. 现在考虑集合$$D=\{x\in G:{\mathrm{Tr}}_{q^{s+2}/q}(x)=0\},{\mathrm{Tr}}_{q^{s+2}/q}(x):=x+x^q+\cdots +x^{q^{s+1}}.$$它良定义, 因为 ${\mathbb{F}}_q^{\times }$ 中的元素 $q$ 次方还是自身. $D$ 是一个差分集, 对应的$$(v,k,\lambda )=\left(\frac{q^{s+2}-1}{q-1},\frac{q^{s+1}-1}{q-1},\frac{q^s-1}{q-1}\right).$$

还有一个特立独行的类, 很有意思, 它由一对孪生素数给出, 以 $v=15,35$ 为例: $$\begin{array}{rlrlrlrlr}v=15,& & D=\{0,1,2,4,5,8,10\},& & k=7,& & \lambda =3,& & n=4;\\ v=35,& & D=\{0,1,3,4,7,9,11,12,13,& & & & & & \\ & & 14,16,17,21,27,28,29,33\},& & k=17,& & \lambda =8,& & n=9.\end{array}$$其中的 $v=15$ 好巧不巧, 正好撞上此时的 $(q=2,s=2)$Singer 类.

例 4.3. 神秘的:

$\bullet$ 孪生素数类, 假设 $p,p+2$ 是孪生素数, 则 $\mathbb{Z}/p(p+2)\mathbb{Z}$ 是循环群 $G$. 现在考虑 $D$ 是以下两类元素对 $(x,y),x\in \mathbb{Z}/p\mathbb{Z},y\in \mathbb{Z}/(p+2)\mathbb{Z}$ 的集合, 第一类是 $y=0$, 第二类是 $x,y$ 都不是 $0$ 而且 $x,y$ 要么都是二次剩余要么都不是. 此时$$(v,k,\lambda )=\left(p^2+2p,\frac{p^2+2p-1}{2},\frac{p^2+2p-3}{4}\right).$$

最后还有一些类也在 $v\le 100$ 的循环群中出现, 比如 Hall 类. 具体来说, $v=37$ 时的 (非零) 四次剩余构成 $(37,9,2)$ 的差分集, 而 $v=43$ 时取一个原根 $r$(比如 $3$) 然后考虑全体 $r^{6k},r^{6k+1},r^{6k+3}$ 构成的集合, 它们构成一个 $(43,21,10)$ 的差分集, 而且不等价于二次剩余者, 实际上这种构造对于 $v=4x^2+27$ 形的素数都有效.

例 4.4. Lehmer 和 Hall 的剩余系差分集:

$(1)$ 我们已经见到 Paley 类, 对素数 $p=4s-1$ 的非零二次剩余是差分集.

$(2)$ 对素数 $p=4x^2+1$, $x$ 是奇数. 非零四次剩余是 $(4x^2+1,x^2,(x^2-1)/4)$-差分集.

$(3)$ 对素数 $p=4x^2+9$, $x$ 是奇数. 含零四次剩余是 $(4x^2+9,x^2+3,(x^2+3)/4)$-差分集.

$(4)$ 对素数 $p=8a^2+1=64b^2+9$, $a,b$ 为奇数. 非零八次剩余是 $(p,a^2,b^2)$-差分集.

$(5)$ 对素数 $p=8a^2+49=64b^2+441$, $a$ 奇 $b$ 偶. 含零八次剩余是 $(p,a^2+6,b^2+7)$-差分集.

$(6)$ 对素数 $p=4x^2+27$, 前段构造的集合为 $(p,(p-1)/2,(p-3)/4)$-差分集.

此外还有 GMW 序列, $$\begin{array}{rlrlrlrlr}v=63,& & D=\{0,1,2,4,8,9,13,15,16,18,& & & & & & \\ & & 19,26,27,30,31,32,36,38,39,41,& & & & & & \\ & & 45,47,51,52,54,55,57,59,60,61,62\}& & k=31,& & \lambda =15,& & n=16.\end{array}$$它其实给出不同于 Singer 类的$$(v,k,\lambda )=\left(\frac{q^N-1}{q-1},\frac{q^{N-1}-1}{q-1},\frac{q^{N-2}-1}{q-1}\right).$$的差分集, 其中 $N=nm$, 如果 $n\ge 3$ 且 $m$ 是 $r$ 个素数的乘积, 那么至少能给出 $2^r$ 个互不等价的差分集. 这里 $q=2,n=3,m=2,r=1$ 恰好符合条件, 于是 $v=63$ 就得到了这个新的解.

最后还有一个散在序列, Legendre 序列, $$\begin{array}{rlrlrlrlr}v=31,& & D=\{3,6,11,12,13,15,17,21,& & & & & & \\ & & 22,23,24,26,27,29,30\},& & k=15,& & \lambda =7,& & n=8.\end{array}$$

姑且不给出上面构造的集合是差分集的证明, 我们看到这一下子给出了非常多可能的 $(v,k)$ 组, 上面这些构造实则给出了 $v\le 100$ 的差分集在等价 (平移和自同构) 下的完全分类. 实际上差分集有 Dan Gordon 做的数据库, https://www.dmgordon.org/diffset/ 本节中的具体构造都是从那里找来的.

论证

无论如何, 上面很多的构造都是令人感到惊异的, 我们来看最直接的论证.

定理 4.5. Paley 类确实构造了差分集.

证明. 设 $p=4s-1$ 是素数, 对 $g\not\equiv 0$, 我们熟知有计算$$\begin{array}{rl}& \sum _{x=1}^{p-1}\left(\frac{x}{p}\right)\left(\frac{x+g}{p}\right)=\sum _{x=1}^{p-1}\left(\frac{1+g/x}{p}\right)=-1\\ ⟹& \sum _{x\ne 0,-g}\left(1+\left(\frac{x}{p}\right)\right)\left(1+\left(\frac{x+g}{p}\right)\right)=p-2-\left(\frac{-g}{p}\right)-\left(\frac{g}{p}\right)-1=p-3.\end{array}$$这里我们用到了 $-1$ 的二次剩余是 $-1$. 于是通过这计算得知平移 $g$ 后和自己交的大小为 $(p-3)/4=s-1$, 是前文所述的定值.

$\square$

类似的孪生素数差分集也能被大差不差地证出来. 至于 Lehmer 的那些具体构造, 倘若先承认他们, 其实会带来 Gauss 和的一些有趣的结果:

定理 4.6. 关于四次剩余的求和:

假设 $p=4b^2+1$ 其中 $b$ 是一个奇数, 则$$S_4:=\sum _r{e}^{2\pi ir/p}=\frac{\sqrt{p}-1}{4}\pm \frac{i}{2}\sqrt{\frac{p+\sqrt{p}}{2}}.$$其中求和 ${\sum }_r$ 表示 $r$ 取遍 $(p-1)/4$ 个四次剩余.

假设 $p=4b^2+9$ 其中 $b$ 是一个奇数, 则$$S_4=\frac{\sqrt{p}-1}{4}\pm \frac{i}{2}\sqrt{\frac{p-3\sqrt{p}}{2}}.$$

证明. 以 $p=4b^2+1$ 为例, 此时实则有 $p\equiv 5\mathrm{mod}8$ 所以 $-1$ 是二次剩余而非四次剩余, 这样立刻就得到 $S_4+\overline{S_4}$ 其实恰是全体二次剩余的和, 根据 Gauss 和的知识该值是 $(\sqrt{p}-1)/2$. 而对于 $S_4\cdot \overline{S_4}$ 的计算, 如果四次剩余是差分集那么$$S_4\cdot \overline{S_4}=\sum _r{e}^{2\pi ir/p}\sum _r{e}^{-2\pi ir/p}=\frac{p-1}{4}+\frac{p-5}{16}\sum _{s=1}^{p-1}{e}^{2\pi is/p}=\frac{3p+1}{16}.$$由此即可反解出 $S_4$ 的值. 对 $p=4b^2+9$ 做法也是类似的.

$\square$

不过某种意义上说, 这些结果的强度其实和说四次剩余构成差分集没有太大差别.

为了证明 Lehmer 的结论, 我们需要下面的记号以及 Gauss 本人就明白的引理:

引理 4.7. 假设素数 $p=4s+1$ 而 $r$ 是一个模 $p$ 原根, 用 $S(i,j)$ 表示下面方程的解数: $$g^{4x+i}+1=g^{4y+j},0\le x,y<n.$$假设 $p=a^2+4b^2$, 其中 $a\equiv 1\mathrm{mod}4$ 且 $b$ 是奇数, 那么$$S(0,0)=\frac{p+2a-7}{16},S(1,0)=\frac{p-2a-3}{16}.$$

利用这个引理, 如果 $p=4b^2+1$ 而且 $b$ 是奇数那么 $S(0,0)=S(1,0)=(p-5)/16$, 然后利用 $-1$ 是二次剩余但不是四次剩余, 可得 $S(2,0)=S(3,0)$ 也是该值. 此时容易证明 Lehmer 的结论, 细节留给读者作为练习. 经过一些讨论, 其实我们也看到了更强的结论, 对 $p=4s+1$, 四次剩余构成差分集当且仅当 $(p-1)/4$ 是奇平方数.

然后就是 Singer 类.

定理 4.8. Singer 类构造了差分集.

证明. 熟知 Trace 映射 $f(x):=x+x^q+\cdots +x^{q^{s+1}}$ 是 ${\mathbb{F}}_{q^{s+2}}\to {\mathbb{F}}_q$ 的 ${\mathbb{F}}_q$-线性映射, 因为多项式零点数量被次数控制, 所以非零进而是满射, 所以在 ${\mathbb{F}}_{q^{s+2}}$ 的零点数量为 $q^{s+1}$. 接下来对 $g\in {\mathbb{F}}_{q^{s+2}}^{\times }\backslash {\mathbb{F}}_q^{\times }$, 我们声称 $f(x)=f(xg)=0$ 在 ${\mathbb{F}}_{q^{s+2}}$ 只有 $q^s$ 个解, 这样 $x$ 除了 $0$ 外剩下的解在 ${\mathbb{F}}_q^{\times }$ 左乘下恰好是 $(q^s-1)/(q-1)$ 类. 为了证明这件事, 只需证明 $x\mapsto (f(x),f(xg))$ 秩 $2$, 由于这两个映射非零, 故只要证明不存在 $c\in {\mathbb{F}}_q^{\times }$ 使 $f(x)=cf(xg)$ 恒成立. 由于 $f(x)-cf(xg)$ 是不超过 $q^{s+1}$ 次多项式, 所以它恒成立就必须恒 $0$, 但比较一次项系数得到 $cg=1$, 这与 $c,g$ 的定义矛盾.

$\square$

我们看到了这么多的证明某些东西是差分集的定理, 那有没有证明对于某些 $v$ 来说不可能存在差分集的定理呢? 确实是有的, 最典型的例子就是如下的:

定理 4.9 (Bruck–Ryser–Chowla). 若存在 $(v,k,\lambda )$ 差分集, 那么:

$\bullet$ 若 $v$ 为偶数, 则 $n=k-\lambda$ 是平方数.

$\bullet$ 若 $v$ 为奇数, 则 $z^2=n{x}^2+(-1{)}^{(v-1)/2}\lambda y^2$ 有非零解.

证明. 如果存在差分集 $D$, 我们考虑 $M$ 是一个 $v\times v$ 矩阵, 第 $g$ 行第 $i$ 个元素为 $1_{i+g\in D}$, 这样依定义$$M{M}^{\text{T}}=nI+\lambda J.$$其中 $J$ 是全 $1$ 的矩阵, $I$ 是单位矩阵. 两边计算行列式得到$$(\det M{)}^2=n^{v-1}(n+v\lambda )=(n^{(v-1)/2}k{)}^2.$$由此如果 $v$ 为偶数, 等式左右为平方数的条件立刻推出 $n$ 是平方数.

接下来观察 $v$ 是奇数时的神奇解决办法. 先来看 $v\equiv 1\mathrm{mod}4$, 此时待定一个行向量 $x=(x_1,\cdots ,x_v)$, 设行和 $y=\sum x_i$, 代入得到$$(xM)(xM{)}^{\text{T}}=nx{x}^{\text{T}}+\lambda y^2.$$此时注意到任意正整数 $n$ 都是四平方和, 因此由 $v$ 的同余条件, 可以将 $n(x_1^2+\cdots +x_{v-1}^2)$ 重新配成 $x_i$ 线性组合的平方和 $y_1^2+\cdots +y_{v-1}^2$, 于是现在记 $xM=(z_1,\cdots ,z_v)$ 就有$$z_1^2+\cdots +z_v^2=y_1^2+\cdots +y_{v-1}^2+n{x}_v^2+\lambda y^2.$$然后合理地选择下标 $i_1,\cdots ,i_{v-1},j_1,\cdots ,j_{v-1}$, 使得求解 $z_{i_1}=y_{j_1},\cdots ,z_{i_{v-1}}=y_{j_{v-1}}$ 能给出 $x$ 的非零有理解, 因为在一般位置下, $x$ 具有 $v$ 个分量, 但是这里只求解 $v-1$ 个分量, 结合矩阵 $M$ 非退化可知 $z_1,\cdots ,z_v$ 线性无关, 所以最后能得到 $z$ 非平凡的解 $z^2=n{x}_v^2+\lambda y^2$.

再来看 $v\equiv -1\mathrm{mod}4$, 此时和前面的技巧类似, 我们在等式左右补充一项 $n{x}_{v+1}^2$, 就得到$$z_1^2+\cdots +z_v^2+n{x}_{v+1}^2=y_1^2+\cdots +y_{v+1}^2+\lambda y^2.$$仍是求解消掉 $z_1,\cdots ,z_v$ 就得到形如 $n{x}_{v+1}^2=y_i^2+\lambda y^2$ 的 $x_{v+1}$ 非平凡的解.

至此结论得证.

$\square$

上面这个准则足够有效, 以至于大概一半的不存在差分集的情况能被该准则否决掉. 关于否定一个集合是差分集, 还有一些比较神秘而且复杂的定理, 这些定理大都需要十分冗长的讨论, 在此按下不表.

分圆

本节参考 DECOMPOSITION FIELDS OF DIFFERENCE SETS by Koichi Yamamoto *

5第五幕

数点