🔢 mathematics

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

The paper demonstrates that for every uniform family of affine algebraic sets, including elliptic curves in Weierstrass normal form, there exists an arithmetic formula involving only basic operations and integer exponentiations that expresses the cardinality of the set within the ring $\mathbb{Z}/n\mathbb{Z}$ based on the family's parameters and $n$ .

Original authors: Mihai Prunescu

Published 2026-08-25✓ Author reviewed ⓘ

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Mihai Prunescu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of mathematics, there is a branch dedicated to counting the solutions to equations, but with a twist: instead of looking for answers among the infinite sea of all numbers, researchers restrict their search to a small, repeating cycle. Imagine a clock face where the numbers only go from one to twelve; if you add ten and four, the answer is not fourteen, but two. This is the world of modular arithmetic, a system where numbers wrap around after reaching a certain limit, known as the modulus. For centuries, mathematicians have been fascinated by how many points, or solutions, exist for complex geometric shapes when they are drawn on these clock-like grids. These shapes, defined by polynomial equations, can range from simple lines to intricate curves or surfaces. The challenge has always been that as the grid size changes, the number of solutions can behave unpredictably, jumping up and down in ways that seem to defy a simple rule. Understanding these counts is not just a game of numbers; it is fundamental to cryptography and the study of prime numbers, where the hidden structure of these solutions holds the keys to secure communication.

A researcher named Mihai Prunescu has now demonstrated that for any family of these geometric shapes defined by integer coefficients, there is indeed a single, fixed recipe to calculate the exact number of solutions for any grid size. This recipe is not a vague approximation or a computer simulation that runs for hours; it is a specific, finite sequence of basic arithmetic operations, addition, subtraction, multiplication, division with remainders, and exponentiation, that can be written down once and used forever. The paper proves that no matter how complex the shape or how large the grid, the count of points can be expressed as a "term," a self-contained mathematical instruction that takes the parameters of the shape and the size of the grid as inputs and outputs the precise number of points. This result applies to a broad category of shapes called affine algebraic sets, which includes the famous elliptic curves used in modern encryption.

The journey to this discovery began by translating the problem of finding points on a grid into a problem of counting zeros in a specific type of equation. The author showed that the solutions to the original geometric equations on the grid correspond perfectly to the solutions of a new, more complex equation built entirely from sums of squares. Because a sum of squares can only equal zero if every single part of it is zero, this new equation acts as a strict filter, isolating exactly the points of interest. The next step was to prove that all these solutions fit within a predictable, finite box. By carefully analyzing the maximum possible values the variables could take, the researcher established a boundary that grows in a known way as the grid size increases. This meant that the infinite search for solutions could be reduced to a finite search within a specific range.

Once the search was confined to a finite box, the paper employed a clever counting technique that treats the presence of a solution like a light switch. By constructing a massive number where the binary digits represent whether a solution exists at a specific location, the author could count the total number of solutions simply by counting the number of ones in that binary string. This counting process, which relies on specialized arithmetic functions capable of handling geometric progressions and digit sums, was then shown to be expressible using only the basic arithmetic operations allowed in the definition of "elementary functions." The result is a closed formula that works for every possible grid size and every possible set of parameters defining the shape.

The paper places special emphasis on elliptic curves, which are defined by a specific cubic equation and are central to modern number theory. For these curves, the author constructed the explicit formula that counts the points on the curve for any modulus. While the formula itself is incredibly long and complex, involving dozens of nested operations and large exponents, its existence is the true triumph. It proves that the behavior of these points is not chaotic or random but is governed by a rigid, computable rule. The author acknowledges that while these formulas are too complicated to be used for practical calculations in the real world, their existence settles a theoretical question about the nature of these counts. The work confirms that for every family of algebraic sets defined by integer coefficients, the number of points in a modular ring is not just a number that can be found by trial and error, but a value that can be generated by a fixed, finite arithmetic expression.

Technical Summary: "How many points has an affine algebraic set in residue classes modulo n?"

Problem Statement
The paper addresses the problem of determining the exact cardinality of affine algebraic sets defined over the ring of integers modulo $n$ ( $\mathbb{Z}/n\mathbb{Z}$ ). Specifically, given a system of polynomial equations with integer coefficients and parameters $\vec{\lambda} \in \mathbb{Z}^s$ , the goal is to find a closed-form expression for the number of solutions in $(\mathbb{Z}/n\mathbb{Z})^m$ . The author focuses on constructing this expression as an arithmetic term, defined as a fixed finite composition of basic arithmetic operations (addition, subtraction, multiplication, division with remainder, and integer exponentiation).

Methodology
The approach relies on the theory of Kalmar elementary functions (also known as elementary functions), which are sequences of non-negative integers computable in iterated exponential time. The methodology proceeds through the following logical steps:

Arithmetic Terms and Elementary Functions: The paper utilizes results by Mazzanti and Marchenkov, which establish that Kalmar elementary functions can be expressed as arithmetic terms. These terms include operations such as $x \dot{-} y$ (arithmetic difference), $\lfloor x/y \rfloor$ , and exponentiation.
Counting Zeros via Hamming Weight: The core technique involves converting the problem of counting solutions to $f(\vec{x}) = 0$ $f (x) = 0$ into a problem of calculating the Hamming weight (the number of 1s in the binary representation) of a specific large integer $M$ $M$ .
- For a function $f$ bounded by $2^w$ on a domain $[0, t-1]^k$ , the author constructs a sum $M = \sum 2^{2^w v(\vec{a})} \delta(f(\vec{a}), w)$ , where $\delta$ is a specific arithmetic term.
- The Hamming weight of $M$ relates linearly to the number of zeros $d$ of the function, allowing $d$ to be extracted via arithmetic operations.
Transformation to Non-Negative Diophantine Equations: To apply the counting method to polynomial equations over $\mathbb{Z}/n\mathbb{Z}$ $Z / n Z$ , the author transforms the system $F_i(\vec{\lambda}, \vec{x}) = 0$ $F_{i} (λ, x) = 0$ into a single non-negative Diophantine equation $G(\vec{\lambda}, n, \vec{x}, \vec{y}, \vec{z}) = 0$ $G (λ, n, x, y, z) = 0$ over natural numbers $\mathbb{N}$ $N$ .
- This is achieved by replacing coefficients and parameters with their residues modulo $n$ (using the term $c \pmod n$ ).
- The equation is constructed as a sum of squares: $\sum (G_i^2 - n^2 y_i^2)^2 + \sum (x_j + z_j - n + 1)^2 = 0$ .
- This transformation ensures that solutions in $\mathbb{N}$ correspond bijectively to solutions in $(\mathbb{Z}/n\mathbb{Z})^m$ .
Bounding the Search Space: The author proves the existence of arithmetic terms $t(n)$ and $w(n)$ that bound the variables and the value of the Diophantine equation, respectively. This ensures the search space is a finite hypercube $[0, t(n)]^k$ and the function values are strictly less than $2^{w(n)}$ , satisfying the prerequisites for the Hamming weight counting technique.
Generalized Geometric Progressions: The summation over the hypercube is performed using generalized geometric progressions $G_r(q, t) = \sum_{j=0}^t j^r q^j$ . The paper notes that these progressions can be computed via arithmetic terms, allowing the final summation to be expressed as a closed-form arithmetic term.

Key Contributions and Results

General Theorem (Theorem 3.1): The paper proves that for any family of affine algebraic sets defined by polynomial equations with integer parameters $\vec{\lambda}$ , there exists an arithmetic term $f(\vec{\lambda}, n)$ that exactly computes the number of points in the set over $\mathbb{Z}/n\mathbb{Z}$ .
Elliptic Curves (Theorem 4.1): The author explicitly constructs such a formula for elliptic curves in short Weierstraß normal form ( $x_2^2 = x_1^3 + Ax_1 + B$ $x_{2}^{2} = x_{1}^{3} + A x_{1} + B$ ). They derive the specific bounds $t(n) = (n+1)^2$ $t (n) = (n + 1)^{2}$ and $w(n) = n + 90$ $w (n) = n + 90$ and describe the structure of the resulting arithmetic term $f(A, B, n)$ $f (A, B, n)$ .
- The term involves the Hamming weight of a constructed integer $M(A, B, n)$ , which is a sum of 51 sub-terms (one free term and 50 monomial contributions).
- The construction utilizes generalized geometric progressions up to $G_{12}$ .

Significance and Claims
The paper claims significance primarily in the theoretical existence of these formulas rather than their practical utility.

Existence of Closed Forms: The work demonstrates that the cardinality of algebraic sets over $\mathbb{Z}/n\mathbb{Z}$ is not just computable but expressible as a fixed, finite composition of elementary arithmetic operations.
Modesty on Practicality: The author explicitly states that "the formulas are too complicated to be of practical use." They do not propose these formulas for immediate implementation in cryptography or number theory algorithms.
Open Question: The paper acknowledges that while the existence of such terms is proven, the complexity of these terms is high, and it remains unknown how simple equivalent formulas might be.

In summary, the paper provides a constructive proof that the point-counting function for affine algebraic sets over $\mathbb{Z}/n\mathbb{Z}$ belongs to the class of arithmetic terms, extending previous work on elementary functions to the specific domain of algebraic geometry over residue rings.

Technical Summary: "How many points has an affine algebraic set in residue classes modulo n?"

More like this