How many points has an affine algebraic set in residue classes modulo n ?

技术摘要：“模 $n$ 剩余类中仿射代数集的点数有多少？”

问题陈述
本文探讨了确定定义在整数环 $\mathbb{Z}/n\mathbb{Z}$ 上的仿射代数集精确基数的题目。具体而言，给定一个具有整数系数和参数 $\vec{\lambda} \in \mathbb{Z}^s$ 的多项式方程组，目标是找到其在 $(\mathbb{Z}/n\mathbb{Z})^m$ 中的解的数量的闭式表达式。作者致力于将该表达式构建为一个算术项（arithmetic term），即由基础算术运算（加、减、乘、除以余数以及整数幂）组成的固定有限复合结构。

方法论
该方法依赖于卡尔马初等函数（Kalmar elementary functions）（也称为初等函数）理论，这类函数是可以在迭代指数时间内计算的非负整数序列。该方法通过以下逻辑步骤进行：

1. 算术项与初等函数： 本文利用了 Mazzanti 和 Marchenkov 的研究结果，这些结果确立了卡尔马初等函数可以表示为算术项。这些项包括运算如 $x \dot{-} y$（算术差）、$\lfloor x/y \rfloor$ 以及幂运算。
2. 通过汉明重量计数零点： 核心技术是将计算 $f(\vec{x}) = 0$ 的解的数量转化为计算一个特定大整数 $M$ 的汉明重量（二进制表示中 1 的个数）的问题。
   • 对于定义在域 $[0, t-1]^k$ 上且有界于 $2^w$ 的函数 $f$，作者构造了一个和 $M = \sum 2^{2^w v(\vec{a})} \delta(f(\vec{a}), w)$，其中 $\delta$ 是一个特定的算术项。
   • $M$ 的汉明重量与函数的零点数 $d$ 呈线性关系，从而可以通过算术运算提取出 $d$。
3. 向非负丢番图方程的转换： 为了将计数方法应用于 $\mathbb{Z}/n\mathbb{Z}$ 上的多项式方程，作者将方程组 $F_i(\vec{\lambda}, \vec{x}) = 0$ 转换为单个关于自然数 $\mathbb{N}$ 的非负丢番图方程 $G(\vec{\lambda}, n, \vec{x}, \vec{y}, \vec{z}) = 0$。
   • 这是通过使用模 $n$ 余数项（使用项 $c \pmod n$）替换系数和参数来实现的。
   • 该方程被构造为一个平方和形式：$\sum (G_i^2 - n^2 y_i^2)^2 + \sum (x_j + z_j - n + 1)^2 = 0$。
   • 这种转换确保了 $\mathbb{N}$ 中的解与 $(\mathbb{Z}/n\mathbb{Z})^m$ 中的解之间存在双射关系。
4. 限制搜索空间： 作者证明了存在算术项 $t(n)$ 和 $w(n)$ 来限制变量和丢番图方程的值。这确保了搜索空间是一个有限超立方体 $[0, t(n)]^k$，且函数值严格小于 $2^{w(n)}$，从而满足汉明重量计数技术的先决条件。
5. 广义几何级数： 对超立方体的求和是通过广义几何级数 $G_r(q, t) = \sum_{j=0}^t j^r q^j$ 完成的。论文指出，这些级数可以通过算术项进行计算，从而允许最终的求和表示为一个闭合形式的算术项。

主要贡献与结果

• 一般定理（定理 3.1）： 本文证明了对于任何由具有整数参数 $\vec{\lambda}$ 的多项式方程定义的仿型代数集族，都存在一个算术项 $f(\vec{\lambda}, n)$，能够精确计算该集合在 $\mathbb{Z}/n\mathbb{Z}$ 上的点数。
• 椭圆曲线（定理 4.1）： 作者为短魏尔斯特拉斯标准型（$x_2^2 = x_1^3 + Ax_1 + B$）下的椭圆曲线显式地构造了这样一个公式。他们推导出了特定的界限 $t(n) = (n+1)^2$ 和 $w(n) = n + 90$，并描述了所得算术项 $f(A, B, n)$ 的结构。
  • 该项涉及构造整数 $M(A, B, n)$ 的汉明重量，该整数是由 51 个子项（一个自由项和 50 个单项贡献）组成的和。
  • 该构造利用了直到 $G_{12}$ 的广义几何级数。

意义与主张
本文的意义主要在于这些公式的理论存在性，而非其实际用途。

• 闭式形式的存在性： 这项工作证明了 $\mathbb{Z}/n\mathbb{Z}$ 上代数集的基数不仅是可计算的，而且可以用初等算术运算的固定有限复合来表示。
• 对实用性的谦逊态度： 作者明确指出“这些公式过于复杂，不具备实际用途”。他们并非提出将这些公式用于密码学或数论算法的立即实现。
• 开放问题： 论文承认，虽然证明了这些项的存在性，但这些项的复杂度很高，目前尚不清楚是否存在更简单的等价公式。

总之，本文提供了一个构造性证明，证明了 $\mathbb{Z}/n\mathbb{Z}$ 上仿射代数集的点计数函数属于算术项类，将先前关于初等函数的成果扩展到了剩余环上代数几何的特定领域。