二次剩余与二次非剩余的分布问题（Distribution of Quadratic Residues and Non-Residues）
字数 2951 2025-12-18 05:52:25

二次剩余与二次非剩余的分布问题（Distribution of Quadratic Residues and Non-Residues）

这一词条主要探讨模素数 \(p\) 下，二次剩余与二次非剩余在集合 \(\{1,2,\dots,p-1\}\) 中的分布模式，包括它们的序结构、最小非剩余、相邻间隔以及相关的猜想与结果。以下讲解将循序渐进展开。

1. 基本定义与回顾
首先明确概念。设 \(p\) 为奇素数，\(a\) 为整数且 \(p \nmid a\)。

  • 若同余方程 \(x^2 \equiv a \pmod{p}\) 有解，则称 \(a\) 是模 \(p\) 的二次剩余（QR）。
  • 若无解，则称 \(a\) 是模 \(p\) 的二次非剩余（QNR）。
    在模 \(p\) 的简化剩余系（即 \(\{1,2,\dots,p-1\}\)）中，二次剩余与非剩余恰好各占一半，即各有 \(\frac{p-1}{2}\) 个。这是由模 \(p\) 乘法群的循环结构及原根的存在所保证的。

2. 序结构中的分布问题
我们关心的是：当把数 \(1,2,\dots,p-1\) 按自然顺序排列时，二次剩余与非剩余是如何交错出现的？这并非完全随机。例如：

  • 最小二次非剩余 \(n_p\)：定义为最小的正整数 \(a\)（\(1 \le a \le p-1\)）使得 \(a\) 是模 \(p\) 的二次非剩余。这是一个经典的研究对象。
  • 已知 \(n_p\) 的增长非常缓慢。著名的林尼克定理（Vinogradov 提出，Linnik 证明）指出：存在绝对常数 \(C, L > 0\)，使得对任意素数 \(p\)，有 \(n_p \le C \, p^{\frac{1}{2\sqrt{e}} + \varepsilon}\) 型上界（实际上更佳的结果已证明 \(n_p = O(p^{\alpha})\)，其中 \(\alpha\) 可小至约 0.1616…）。广义黎曼猜想（GRH）可推出 \(n_p = O((\log p)^2)\)。
  • 另一方面，最小二次剩余 总是 1（因为 1 总是二次剩余），但次小的二次剩余可以很小，这依赖于 \(p\) 模 4 或模 8 的余数。

3. 二次剩余与非剩余的间隔
考虑序列 \(a_1 < a_2 < \dots < a_{(p-1)/2}\) 表示所有二次剩余。研究相邻二次剩余之间的差 \(a_{i+1} - a_i\)。

  • 可以证明，存在相邻二次剩余的差为 1（即连续整数都是二次剩余）。事实上，若 \(a\) 和 \(a+1\) 均为二次剩余，则方程 \(x^2 \equiv a, y^2 \equiv a+1 \pmod{p}\) 给出 \(y^2 - x^2 \equiv 1\)，即 \((y-x)(y+x) \equiv 1\)，这总是有解。
  • 更一般地，伯吉斯（Burgess）定理关于特征和估计可以推出：二次剩余（视为乘法群中平方元）在区间 \([1, p-1]\) 中分布相当均匀。具体地，对任意区间 \(I \subset [1, p-1]\) 长度约 \(p^{1/2+\varepsilon}\)，其中的二次剩余个数接近于期望值 \(\frac{|I|}{2}\)。
  • 关于最大间隔：存在常数 \(c > 0\)，使得最大间隔至少为 \(c \log p\)。这可由抽屉原理与二次剩余集的“乘法平移不变性”（即若 \(r\) 是二次剩余，则对任意非零 \(t\)，\(tr^2\) 仍是二次剩余）部分推出。

4. 二次剩余的模 p 序结构的模式
一个深刻现象是二次剩余的“乘法结构”。设 \(g\) 是模 \(p\) 的一个原根，则二次剩余恰好是集合 \(\{ g^{2k} : k=0,1,\dots,(p-3)/2 \}\)。因此，在离散对数意义下，二次剩余对应指数为偶数的元素。但当我们按自然数顺序观察时，分布呈现出某种“伪随机”但又有算术约束的性质。

  • 例如，二次剩余的倒数仍是二次剩余，因为若 \(a \equiv x^2\)，则 \(a^{-1} \equiv (x^{-1})^2\)。
  • 另一个著名结果是：连续三个整数不可能都是二次剩余。因为若 \(a, a+1, a+2\) 均为二次剩余，则存在 \(x,y,z\) 使 \(x^2 \equiv a, y^2 \equiv a+1, z^2 \equiv a+2\)，通过消去可导出矛盾（需用到勒让德符号的完全积性及值域为 \(\{ -1,0,1 \}\)）。

5. 二次非剩余的分布与最小原根
由于原根一定是二次非剩余（因为原根的阶是 \(p-1\)，而二次剩余的阶至多 \((p-1)/2\)），所以最小原根 \(g_p\) 满足 \(g_p \ge n_p\)。对最小原根的上界估计与最小二次非剩余类似，也是数论中长期研究的问题。在 GRH 下，\(g_p = O((\log p)^6)\)（后来改进为 \(O((\log p)^2)\)）。

6. 与特征和与 L 函数的联系
设 \(\chi\) 为模 \(p\) 的勒让德符号（即二次特征）。则二次剩余的分布问题可转化为研究特征和

\[S(N) = \sum_{n=1}^{N} \chi(n). \]

\(S(N)\) 表示区间 \([1, N]\) 中二次剩余个数减去二次非剩余个数（差）。波利亚-维诺格拉多夫不等式给出：

\[|S(N)| \le C \sqrt{p} \log p, \]

其中 \(C\) 为绝对常数。这表明在长度远大于 \(\sqrt{p} \log p\) 的区间中，二次剩余与非剩余的数量大致平衡。更精细的估计依赖于 L 函数 \(L(s, \chi)\) 在临界线上的界。

7. 公开问题与猜想

  • 最小二次非剩余的阶：无条件证明 \(n_p = O((\log p)^A)\) 对某个固定 \(A\) 是一个未解决问题。这等价于 L 函数零点分布的非区域性问题。
  • 二次剩余序列的伪随机性：在加性与乘性组合数论中，研究二次剩余序列的相关性、等差数列中的分布等是活跃领域。
  • 埃尔德什（Erdős）猜想：对任意素数 \(p\)，存在整数 \(a, b\) 使得 \(a, b, ab\) 均为模 \(p\) 的二次非剩余，且 \(a+b \equiv 1 \pmod{p}\)。这类问题涉及二次剩余集的加法组合结构。

总结：二次剩余与二次非剩余的分布问题连接了初等数论、解析数论（特征和、L 函数）、组合数论与算术几何，是理解模素数结构的核心窗口之一。其研究不仅推进了最小非剩余等经典问题的认识，也为更一般的伪随机序列理论提供了原型。

二次剩余与二次非剩余的分布问题（Distribution of Quadratic Residues and Non-Residues） 这一词条主要探讨模素数 \( p \) 下，二次剩余与二次非剩余在集合 \(\{1,2,\dots,p-1\}\) 中的分布模式，包括它们的序结构、最小非剩余、相邻间隔以及相关的猜想与结果。以下讲解将循序渐进展开。 1. 基本定义与回顾 首先明确概念。设 \( p \) 为奇素数，\( a \) 为整数且 \( p \nmid a \)。 若同余方程 \( x^2 \equiv a \pmod{p} \) 有解，则称 \( a \) 是模 \( p \) 的 二次剩余 （QR）。 若无解，则称 \( a \) 是模 \( p \) 的 二次非剩余 （QNR）。 在模 \( p \) 的简化剩余系（即 \(\{1,2,\dots,p-1\}\)）中，二次剩余与非剩余恰好各占一半，即各有 \(\frac{p-1}{2}\) 个。这是由模 \( p \) 乘法群的循环结构及原根的存在所保证的。 2. 序结构中的分布问题 我们关心的是：当把数 \( 1,2,\dots,p-1 \) 按自然顺序排列时，二次剩余与非剩余是如何交错出现的？这并非完全随机。例如： 最小二次非剩余 \( n_ p \)：定义为最小的正整数 \( a \)（\( 1 \le a \le p-1 \)）使得 \( a \) 是模 \( p \) 的二次非剩余。这是一个经典的研究对象。 已知 \( n_ p \) 的增长非常缓慢。著名的 林尼克定理 （Vinogradov 提出，Linnik 证明）指出：存在绝对常数 \( C, L > 0 \)，使得对任意素数 \( p \)，有 \( n_ p \le C \, p^{\frac{1}{2\sqrt{e}} + \varepsilon} \) 型上界（实际上更佳的结果已证明 \( n_ p = O(p^{\alpha}) \)，其中 \( \alpha \) 可小至约 0.1616…）。广义黎曼猜想（GRH）可推出 \( n_ p = O((\log p)^2) \)。 另一方面， 最小二次剩余 总是 1（因为 1 总是二次剩余），但次小的二次剩余可以很小，这依赖于 \( p \) 模 4 或模 8 的余数。 3. 二次剩余与非剩余的间隔 考虑序列 \( a_ 1 < a_ 2 < \dots < a_ {(p-1)/2} \) 表示所有二次剩余。研究相邻二次剩余之间的差 \( a_ {i+1} - a_ i \)。 可以证明，存在相邻二次剩余的差为 1（即连续整数都是二次剩余）。事实上，若 \( a \) 和 \( a+1 \) 均为二次剩余，则方程 \( x^2 \equiv a, y^2 \equiv a+1 \pmod{p} \) 给出 \( y^2 - x^2 \equiv 1 \)，即 \((y-x)(y+x) \equiv 1\)，这总是有解。 更一般地， 伯吉斯（Burgess）定理 关于特征和估计可以推出：二次剩余（视为乘法群中平方元）在区间 \([ 1, p-1]\) 中分布相当均匀。具体地，对任意区间 \( I \subset [ 1, p-1 ] \) 长度约 \( p^{1/2+\varepsilon} \)，其中的二次剩余个数接近于期望值 \(\frac{|I|}{2}\)。 关于最大间隔：存在常数 \( c > 0 \)，使得最大间隔至少为 \( c \log p \)。这可由抽屉原理与二次剩余集的“乘法平移不变性”（即若 \( r \) 是二次剩余，则对任意非零 \( t \)，\( tr^2 \) 仍是二次剩余）部分推出。 4. 二次剩余的模 p 序结构的模式 一个深刻现象是 二次剩余的“乘法结构” 。设 \( g \) 是模 \( p \) 的一个原根，则二次剩余恰好是集合 \(\{ g^{2k} : k=0,1,\dots,(p-3)/2 \}\)。因此，在离散对数意义下，二次剩余对应指数为偶数的元素。但当我们按自然数顺序观察时，分布呈现出某种“伪随机”但又有算术约束的性质。 例如， 二次剩余的倒数仍是二次剩余 ，因为若 \( a \equiv x^2 \)，则 \( a^{-1} \equiv (x^{-1})^2 \)。 另一个著名结果是： 连续三个整数不可能都是二次剩余 。因为若 \( a, a+1, a+2 \) 均为二次剩余，则存在 \( x,y,z \) 使 \( x^2 \equiv a, y^2 \equiv a+1, z^2 \equiv a+2 \)，通过消去可导出矛盾（需用到勒让德符号的完全积性及值域为 \(\{ -1,0,1 \}\)）。 5. 二次非剩余的分布与最小原根 由于原根一定是二次非剩余（因为原根的阶是 \( p-1 \)，而二次剩余的阶至多 \((p-1)/2\)），所以最小原根 \( g_ p \) 满足 \( g_ p \ge n_ p \)。对最小原根的上界估计与最小二次非剩余类似，也是数论中长期研究的问题。在 GRH 下，\( g_ p = O((\log p)^6) \)（后来改进为 \( O((\log p)^2) \)）。 6. 与特征和与 L 函数的联系 设 \( \chi \) 为模 \( p \) 的勒让德符号（即二次特征）。则二次剩余的分布问题可转化为研究特征和 \[ S(N) = \sum_ {n=1}^{N} \chi(n). \] \( S(N) \) 表示区间 \([ 1, N]\) 中二次剩余个数减去二次非剩余个数（差）。 波利亚-维诺格拉多夫不等式 给出： \[ |S(N)| \le C \sqrt{p} \log p, \] 其中 \( C \) 为绝对常数。这表明在长度远大于 \( \sqrt{p} \log p \) 的区间中，二次剩余与非剩余的数量大致平衡。更精细的估计依赖于 L 函数 \( L(s, \chi) \) 在临界线上的界。 7. 公开问题与猜想 最小二次非剩余的阶 ：无条件证明 \( n_ p = O((\log p)^A) \) 对某个固定 \( A \) 是一个未解决问题。这等价于 L 函数零点分布的非区域性问题。 二次剩余序列的伪随机性 ：在加性与乘性组合数论中，研究二次剩余序列的相关性、等差数列中的分布等是活跃领域。 埃尔德什（Erdős）猜想 ：对任意素数 \( p \)，存在整数 \( a, b \) 使得 \( a, b, ab \) 均为模 \( p \) 的二次非剩余，且 \( a+b \equiv 1 \pmod{p} \)。这类问题涉及二次剩余集的加法组合结构。 总结：二次剩余与二次非剩余的分布问题连接了初等数论、解析数论（特征和、L 函数）、组合数论与算术几何，是理解模素数结构的核心窗口之一。其研究不仅推进了最小非剩余等经典问题的认识，也为更一般的伪随机序列理论提供了原型。