🔢 mathematics

Maximal quadrics over finite fields and minimal codewords of projective Reed-Muller codes

This paper classifies the minimal codewords of projective Reed-Muller codes of order 2 by proving that, with one exception over $\mathbb{F}_2$ , absolutely irreducible quadrics with nested rational point sets must be identical, thereby providing a precise characterization and exact count of these codewords for each weight.

Original authors: Alain Couvreur, Rati Ludhani

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alain Couvreur, Rati Ludhani

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 or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery in a world made of dots and lines. This paper is about finding the "smallest, most efficient clues" in a very specific type of digital puzzle called a Projective Reed–Muller code.

Here is the breakdown of the story, translated from "math-speak" into everyday language.

1. The Setting: A Digital City of Dots

Imagine a city built on a grid, but instead of streets, it's made of points (dots) and shapes (curves and surfaces). In this city, the rules are strict: everything is built using a limited set of colors (a "finite field").

The Code: Think of a "codeword" as a secret message written by lighting up specific dots in this city.
The Goal: We want to find the Minimal Codewords. These are the messages that are "minimal" in a very specific way: you can't remove a single dot from the message without breaking the pattern, and you can't find a smaller message hidden inside it. They are the fundamental building blocks of the code.

2. The Mystery: The Shape of the Message

The authors discovered that these minimal messages correspond to specific geometric shapes called Quadrics.

Analogy: If you draw a circle, a sphere, or a saddle shape on a piece of paper, that's a quadric. In this digital city, these shapes are made of dots.
The Problem: The researchers wanted to know: Which of these shapes are the "biggest" possible without being able to fit inside a bigger one?
- If Shape A is made of dots, and Shape B is made of dots, and all the dots of Shape A are also inside Shape B, then Shape A is "trapped" inside Shape B.
- The researchers wanted to find shapes that are maximal. You can't add any more dots to them without changing their fundamental nature.

3. The Big Discovery: "The Twin Rule"

The paper proves a fascinating rule about these shapes, which the authors call Theorem 1.1.

The Rule:
Imagine you have two perfectly smooth, complex shapes (called "absolutely irreducible quadrics"). If you find that every single dot of Shape A is also a dot of Shape B, then Shape A and Shape B are actually the exact same shape.

The Exception (The "Glitch"):
There is one tiny, weird exception. If the city is very small (specifically, if it only has 2 colors, or $q=2$ ), and one shape is an "Elliptic" type (like a perfect sphere) and the other is a "Hyperbolic" type (like a saddle), the Elliptic one can fit inside the Hyperbolic one. But everywhere else, in any other size city, this is impossible. If they share the dots, they are identical.

Why is this cool?
It's like saying: "If you have two different-looking clouds, and they are made of the exact same water droplets, they must be the same cloud." This helps mathematicians know that the shape is uniquely defined by the dots it contains.

4. The "Bad" Shapes (The Exclusions)

The paper also points out a few shapes that don't count as the "minimal" clues because they are too simple or too weird:

Double Layers: Shapes that are just a flat sheet doubled over itself (like a piece of paper folded perfectly in half).
Rank 3 & 4 Glitches: In very small cities (with 2 or 3 colors), some complex shapes actually hide inside simpler ones. The authors had to list these specific "glitches" to exclude them from the final list of minimal codes.

5. The Solution: Counting the Clues

Once they figured out which shapes are the "true" minimal ones, the authors did the math to count exactly how many of these exist for every possible size.

Type 1 (The Simple Ones): Two flat sheets crossing each other (like an 'X' or a plus sign).
Type 2 (The Complex Ones): The smooth, complex shapes (spheres, saddles, etc.) that follow the "Twin Rule" mentioned above.

They created a precise formula to tell you: "If you have a city of size $N$ and $q$ colors, here is exactly how many minimal messages of weight $W$ you can make."

Summary: Why Should You Care?

This isn't just about abstract shapes. These "minimal codewords" are crucial for:

Secret Sharing: Imagine splitting a secret password among a group of people. You need to know exactly which combinations of people can unlock the secret. These shapes tell you the rules of that game.
Error Correction: When you send data over the internet, errors happen. These codes help fix those errors. Knowing the "minimal" patterns helps engineers design systems that are faster and more reliable.

In a nutshell:
The authors solved a puzzle about the "shape of data." They proved that in almost all cases, if two complex geometric patterns share the same points, they are the same pattern. This allows them to perfectly count and categorize the most efficient ways to encode information in a digital world.

1. Problem Statement

The paper addresses the classification and enumeration of minimal codewords in Projective Reed–Muller (PRM) codes of order 2, denoted as $PRM_q(2, N)$ .

Context: A nonzero codeword is minimal if its support does not properly contain the support of any other nonzero codeword. Minimal codewords are crucial for secret sharing schemes, decoding algorithms, and understanding the matroid structure of linear codes.
Geometric Equivalence: The problem of finding minimal codewords in $PRM_q(2, N)$ is equivalent to identifying quadrics (zero loci of quadratic forms) over the finite field $\mathbb{F}_q$ whose sets of rational points are maximal with respect to set inclusion. Specifically, one seeks quadrics $Q$ such that there is no other quadric $Q'$ where $Q(\mathbb{F}_q) \subsetneq Q'(\mathbb{F}_q)$ .
Challenge: While minimal codewords for general codes are hard to find, and minimal codewords for PRM codes of order 1 (linear forms) are trivial, the order 2 case involves complex interactions between the geometry of quadrics and the arithmetic of finite fields, particularly in small characteristic and low dimensions.

2. Methodology

The authors employ a unified approach combining algebraic geometry, finite geometry, and combinatorics. Their methodology avoids reliance on asymptotic bounds (like Lang–Weil) which are ineffective for small fields, opting instead for structural induction.

Classification of Quadrics: The paper utilizes the standard classification of quadrics over $\mathbb{F}_q$ $F_{q}$ into four classes:
1. Double hyperplanes ( $L^2$ ).
2. Unions of distinct hyperplanes ( $L_1 L_2$ ).
3. Irreducible but not absolutely irreducible (unions of conjugate $\mathbb{F}_{q^2}$ -hyperplanes).
4. Absolutely irreducible quadrics (Parabolic $P_r$ , Hyperbolic $H_r$ , and Elliptic $E_r$ ).
Rank and Singular Loci: The authors analyze the rank of quadratic forms and the dimension of their singular loci. They utilize the property that a quadric is a cone over a smooth quadric in a lower-dimensional subspace.
Inductive Proof Strategy: The core of the proof (Theorem 1.1) relies on induction on the ambient dimension $N$ $N$ .
- They establish that if $Q(\mathbb{F}_q) \subseteq Q'(\mathbb{F}_q)$ , then the singular locus of $Q$ is contained in the singular locus of $Q'$ .
- By intersecting with hyperplanes that avoid the singular locus, they reduce the problem to lower dimensions ( $N-1$ ) while preserving the rank and absolute irreducibility.
Case Analysis: The proof carefully handles specific "exceptional" cases where inclusion might occur without equality, specifically involving small fields ( $q=2, 3$ ) and specific ranks (rank 3 and 4).
Counting: Once the classification of maximal quadrics is established, the authors count the number of such quadrics using the orbit-stabilizer theorem under the action of the projective general linear group $PGL_{N+1}(\mathbb{F}_q)$ , referencing known formulas by Hirschfeld and Thas.

3. Key Contributions and Results

A. The Main Geometric Theorem (Theorem 1.1)

The paper proves a fundamental result regarding the inclusion of rational points on absolutely irreducible quadrics:

Theorem: Let $Q$ and $Q'$ be two absolutely irreducible quadrics in $\mathbb{P}^N$ over $\mathbb{F}_q$ . If $Q(\mathbb{F}_q) \subseteq Q'(\mathbb{F}_q)$ , then $Q = Q'$ , except in the specific case where $q=2$ , $Q$ is an elliptic quadric of rank 4, and $Q'$ is a hyperbolic quadric of rank 4.

Significance: This result implies that, with one minor exception, the set of rational points uniquely determines the absolutely irreducible quadric. This resolves a long-standing question in finite geometry and provides a rigorous foundation for coding theory applications.
Corollary 1.2: A quadric is uniquely determined by its set of rational points unless it is irreducible but not absolutely irreducible (the union of conjugate hyperplanes).

B. Characterization of Minimal Codewords (Theorem 1.3)

Based on the geometric theorem, the authors provide a complete characterization of minimal codewords in $PRM_q(2, N)$ . A codeword $c = \text{Ev}(F)$ is minimal if and only if the quadratic form $F$ is of one of the following types:

Product of Linear Forms: $F = L_1 L_2$ , where $L_1, L_2$ are linearly independent homogeneous linear forms. (These correspond to unions of distinct hyperplanes).
Absolutely Irreducible Forms: $F$ $F$ is an absolutely irreducible quadratic form, excluding:
- Forms of rank 3 if $q \le 3$ .
- Forms of rank 4 if $q=2$ and the form is elliptic.

C. Exact Enumeration (Theorem 4.2)

The paper provides exact formulas for the number of minimal codewords for every possible weight $w$ . The weights correspond to the number of rational points on the quadrics:

Weight $w = q^N - q^{N-1}$ : Corresponds to unions of distinct hyperplanes.
Weight $w = q^N$ : Corresponds to Parabolic quadrics ( $P_r$ ).
Weight $w = q^N - q^{N-r/2}$ : Corresponds to Hyperbolic quadrics ( $H_r$ ).
Weight $w = q^N + q^{N-r/2}$ : Corresponds to Elliptic quadrics ( $E_r$ ).

The formulas involve Gaussian binomial coefficients (counting singular loci) and the number of orbits of smooth quadrics ( $N(P_r), N(H_r), N(E_r)$ ).

4. Significance and Impact

Theoretical Advancement: The paper settles the classification of minimal codewords for PRM codes of order 2, a problem that had remained open or only partially solved for specific parameters. It bridges the gap between the combinatorial properties of codes and the geometric properties of quadrics.
Unified Approach: The authors successfully handle both odd and even characteristics in a unified framework, overcoming difficulties that usually arise in characteristic 2 (where quadratic forms behave differently regarding polarization and rank).
Practical Applications:
- Secret Sharing: Since minimal codewords determine the access structure of linear secret sharing schemes, this work allows for the precise construction and analysis of schemes based on PRM codes.
- Decoding: Knowledge of minimal codewords aids in the design of decoding algorithms, particularly for identifying error patterns.
- Matroid Theory: The results provide the exact circuit structure of the vector matroid associated with PRM codes of order 2.
Finite Geometry: The main theorem (Theorem 1.1) is a significant result in its own right for finite geometry, clarifying the relationship between the inclusion of point sets and the equality of varieties over finite fields.

In summary, Couvreur and Ludhani provide a definitive solution to the minimal codeword problem for order-2 Projective Reed–Muller codes by proving a strong geometric rigidity theorem for quadrics over finite fields and deriving precise enumerative formulas based on this classification.