🔢 mathematics

Explicit constructions of optimal blocking sets and minimal codes

This paper presents an explicit construction of optimal strong $s$ -blocking sets in projective spaces and affine spaces, as well as optimal $s$ -minimal codes, by utilizing expander graphs and specific hypergraphs to achieve sizes of $O_s(q^s k)$ .

Original authors: Anurag Bishnoi, István Tomon

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anurag Bishnoi, István Tomon

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 city planner trying to build a network of "guard posts" (points) in a vast, multi-dimensional city (a mathematical space called a projective space). Your goal is to ensure that no matter where you draw a specific type of "road" (a subspace) through the city, your guard posts will always be able to "cover" that road completely.

In the world of mathematics, this is called a blocking set. But this paper introduces a stricter, more powerful version called a strong s-blocking set. Here, it's not enough for your guards to just stand on the road; they must be positioned in such a way that they can "reach" every single corner of that road, effectively spanning the entire area.

Here is a breakdown of what the authors, Anurag Bishnoi and István Tomon, achieved, using simple analogies.

The Big Problem: Finding the Smallest Network

For years, mathematicians knew that these "guard networks" existed, but they didn't know how to build the most efficient ones.

The Random Approach: If you just throw darts randomly to place your guards, you usually end up with way too many. It's like trying to cover a floor with tiles by throwing them from a helicopter; you'll need a massive pile to make sure there are no gaps.
The Goal: The authors wanted to build a network that is explicit (you can follow a clear recipe to build it) and optimal (it uses the absolute minimum number of guards possible, up to a small constant factor).

The Secret Weapon: Expander Graphs (The "Super-Connected" Map)

To solve this, the authors used a tool from computer science called an expander graph.

The Analogy: Imagine a social network where everyone knows a few people, but the network is so well-connected that if you start at any person, you can reach anyone else in the group very quickly. There are no "dead ends" or isolated islands.
Previous Work: A few years ago, researchers used these graphs to solve the problem for simple roads (1-dimensional). They built a network where the "edges" (connections) between people defined the guard posts.
The New Twist: The authors realized that to handle more complex roads (higher dimensions), they couldn't just use simple connections between two people. They needed to use hypergraphs.
- Analogy: Instead of a friendship between two people, imagine a "group chat" involving three, four, or more people. The authors built a structure where these large groups (hyperedges) were formed based on the "super-connected" map.

How the Construction Works

The authors created a specific recipe to build these optimal guard networks:

Pick a "General Position" Crowd: They start with a large group of vectors (mathematical arrows) that are all pointing in different, unique directions. Think of them as people standing in a field, all facing different ways so no one is blocking another's view.
Build the "Super-Map": They use an expander graph to connect these people.
Form "Groups": They look at the map and say, "If person A is close to person B, and person B is close to person C, then A, B, and C form a special group."
Create the Guard Posts: The actual "guard posts" are all the possible lines and planes that can be drawn through these groups.

The "Tree" Discovery

The most clever part of their proof involves trees.

The Analogy: Imagine you are trying to prove that your guard posts cover a specific road. You look at the groups of people that interact with that road. The authors proved that if you can find a "tree-like" structure within these groups (a shape with no loops, branching out like a family tree), then you are guaranteed to have enough guards to cover the whole road.
Because their "Super-Map" (the expander graph) is so well-connected, they proved that these tree-like structures always exist, no matter which road you pick. This guarantees the network works perfectly.

Why This Matters (According to the Paper)

The paper connects this geometry problem to coding theory (how we send data securely and efficiently).

The Connection: There is a mathematical mirror image (duality) between these guard networks and minimal codes.
The Result: By building the perfect guard network, they automatically built the perfect minimal code.
- Analogy: A minimal code is like a message where no part of the message is redundant. If you have two messages, one shouldn't be a "subset" of the other in a way that makes it useless.
The Achievement: Before this paper, we didn't have a clear, step-by-step recipe to build these perfect codes for complex scenarios. Now, the authors have provided the first explicit construction that is as small as mathematically possible.

Summary of Results

For Large Numbers: They found a way to build these networks that is nearly perfect, with the size growing in a predictable, efficient way.
For Small Numbers: They also provided a specific recipe for smaller, trickier scenarios.
The "Astronomical" Constant: In one of their methods, the numbers involved are so huge they are "astronomical," but the structure of the solution is still valid and explicit. In a later section, they improved this to make the numbers much more manageable.

In short, the authors took a messy, hard-to-solve geometry puzzle and solved it by building a "super-connected" map of groups, proving that this map always contains the hidden "tree" structures needed to cover any possible path through the space. This gives mathematicians and engineers a new, efficient blueprint for creating error-correcting codes.

Technical Summary: Explicit Constructions of Optimal Blocking Sets and Minimal Codes

Problem Statement
The paper addresses the problem of constructing strong $s$ -blocking sets in finite projective spaces $PG(k-1, q)$. A set $B$ of points in $PG(k-1, q)$ is a strong $s$ -blocking set if it intersects every subspace $S$ of codimension $s$ in a set of points that spans $S$ . Equivalently, in the vector space $\mathbb{F}_q^k$ , $B$ is a collection of pairwise linearly independent vectors such that for every subspace $S$ of dimension $k-s$ , the span of $B \cap S$ equals $S$ .

Finding the smallest size of such sets is a major open problem in finite geometry. While random constructions yield sizes of order $O(q^{s+1} \cdot q^{(s+1)(k-s-1)})$ , which is roughly $s+1$ times the theoretical lower bound of $\Omega(q^s k)$ , explicit constructions have been lacking for $s > 1$ when $q$ and $s$ are fixed and $k \to \infty$ . This problem is intrinsically linked to the construction of $s$ -minimal codes (linear codes where no two distinct $s$ -dimensional subspaces have nested supports) and affine blocking sets.

Methodology
The authors generalize the recent approach by Alon, Bishnoi, Das, and Neri [5], which used constant-degree expander graphs to construct strong 1-blocking sets. The core methodology involves:

Expander Graphs: Utilizing explicit constructions of $(n, d, \lambda)$ -expander graphs (specifically Ramanujan or near-Ramanujan graphs) where the degree $d$ and spectral gap $\lambda$ depend on $s$ .
General Position Vectors: Selecting a set $W \subset \mathbb{F}_q^k$ of size $O(k)$ in "general position" (using explicit codes like Justesen codes, Goppa codes, or Reed-Solomon codes) such that any small subset is linearly independent and any large subset spans the space.
Hypergraph Construction: Instead of using the edges of the expander graph directly (as in the $s=1$ case), the authors construct an $(s+1)$ -uniform hypergraph $H$ on the vertex set $W$ . The edges of $H$ are defined based on the distance structure of the underlying expander graph $G$ . Specifically, edges correspond to $(s+1)$ -tuples of vertices that are "close" in $G$ (e.g., within distance $s+1$ of a common vertex, or forming specific configurations like "cherries" for $s=2$ ).
Tree-like Configurations: The proof relies on the Expander Mixing Lemma to show that for any codimension- $s$ subspace $L$ , the intersection of the blocking set with $L$ corresponds to a subhypergraph of $H$ containing large "tree-like" structures (specifically $s$ -tree-like hypergraphs).
Linear Algebra Argument: Using Lemma 10, the authors prove that if a hypergraph contains an $s$ -tree-like subhypergraph, its "proper span" (linear combinations with non-zero coefficients) intersects $L$ in a subspace of sufficiently high dimension to span $L$ .

Key Contributions and Results

The paper provides the first explicit constructions of strong $s$ -blocking sets that are optimal up to a constant factor depending on $s$ . The size of the constructed sets is $O_s(q^s k)$ . The authors present four distinct constructions depending on the parameters:

Warm-up ( $s=2$ ): An explicit construction for $s=2$ using "cherries" (3-vertex paths) in an expander graph, yielding a set of size $O(q^2 k)$ .
Large $q$ via Size-Ramsey Numbers: A construction for large prime powers $q$ utilizing results on size-Ramsey numbers of tight paths by Letzter, Pokrovskiy, and Yepremyan [26]. While this yields the correct asymptotic order $O_s(q^s k)$ , the constant hidden in the $O_s$ notation is "astronomical" (tower of exponentials) as a function of $s$ .
Optimal Large $q$ (Main Result): A refined construction for large $q$ that avoids the astronomical constants. By defining the hypergraph edges based on local neighborhoods in the expander graph (specifically $r$ -cliques of the $r$ -th power of the graph, where $r=s+1$ ), they achieve a size of $2^{O(s^2 \log s)} q^s k$ . This is optimal up to the constant factor depending on $s$ .
Small $q$ : A construction for small prime powers $q$ (where $q$ is bounded by a function of $s$ ) using similar expander-based techniques but with different parameters derived from asymptotically good codes. This yields a size of $q^{O(s^2)} k$ , which fits the $O_s(q^s k)$ form.

Significance and Claims
The paper claims to solve the main open problem of constructing short minimal codes explicitly for $s > 1$ . By establishing the duality between strong $s$ -blocking sets and $s$ -minimal codes (where the columns of the generator matrix of the code form the blocking set), these results provide the first explicit constructions of asymptotically optimal $s$ -minimal codes.

The authors emphasize that their approach is a "far-reaching generalization" of the $s=1$ case. They note that while random constructions exist, explicit constructions were previously unknown for fixed $q, s$ and large $k$ . The work also highlights connections to size-Ramsey numbers of hypergraphs, suggesting that the combinatorial structures used (tight paths and cliques in expander powers) are of independent interest in extremal combinatorics.

The paper does not claim to close the gap for the exact smallest size (as the lower bound is not known to be tight for all $s$ ), but rather to provide constructions that match the lower bound's dependence on $k$ and $q$ , differing only by a constant factor dependent on $s$ .