pith. sign in

arxiv: 2411.10179 · v2 · submitted 2024-11-15 · 🧮 math.CO · cs.IT· math.IT

Explicit constructions of optimal blocking sets and minimal codes

Anurag Bishnoi , Istv\'an Tomon This is my paper

Pith reviewed 2026-05-23 17:17 UTC · model grok-4.3

classification 🧮 math.CO cs.ITmath.IT
keywords strong blocking setsminimal codesprojective spacesexpander graphshypergraphsfinite fieldsexplicit constructions
0
0 comments X

The pith

Strong s-blocking sets of size O_s(q^s k) can be built explicitly in (k-1)-dimensional projective space over F_q by layering hypergraphs on expander graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs explicit strong s-blocking sets that intersect every codimension-s subspace in a spanning set. The size achieved is linear in the ambient dimension k and a constant factor times q to the power s, matching known lower bounds up to the s-dependent constant. The same method produces explicit optimal affine blocking sets and s-minimal linear codes. A reader would care because these objects appear in finite geometry and coding theory, where non-explicit existence results have long outpaced concrete constructions.

Core claim

By placing a carefully chosen hypergraph on the vertex set of an expander graph whose vertices are vectors in F_q^k, the authors obtain tree-like subconfigurations whose corresponding points form a strong s-blocking set of the claimed size in PG(k-1,q). This generalizes an earlier expander-graph construction that worked only for s=1. The same objects yield affine blocking sets in AG(k,q) that meet every codimension-(s+1) flat in a spanning set and s-minimal codes over F_q of length O_s(q^s k).

What carries the argument

Hypergraphs built on expander graphs, in which tree-like configurations correspond to strong s-blocking sets

If this is right

  • Optimal explicit constructions of affine blocking sets in F_q^k with respect to codimension-(s+1) flats.
  • Optimal explicit constructions of s-minimal codes over F_q.
  • Explicit links between the size of these blocking sets and size-Ramsey numbers of the underlying hypergraphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The Ramsey-number connection may supply new upper bounds on size-Ramsey numbers for certain hypergraph families.
  • The method could be tested directly on small values of q and k to count how often the spanning condition holds in practice.
  • Similar expander-plus-hypergraph layering might produce explicit objects for other intersection properties in finite geometries.

Load-bearing premise

The hypergraph construction on the expander graph produces tree-like configurations that intersect every codimension-s subspace in a spanning set.

What would settle it

A single codimension-s subspace whose intersection with the constructed point set fails to span that subspace, for parameters where the O_s(q^s k) size bound is asserted.

Figures

Figures reproduced from arXiv: 2411.10179 by Anurag Bishnoi, Istv\'an Tomon.

Figure 1
Figure 1. Figure 1: An illustration of a 3-tree-like subhypergraph [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of a 3-uniform tight path of length [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An illustration for the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An illustration for the proof of Theorem [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
read the original abstract

A strong $s$-blocking set in a projective space is a set of points that intersects each codimension-$s$ subspace in a spanning set of the subspace. We present an explicit construction of such sets in a $(k - 1)$-dimensional projective space over $\mathbb{F}_q$ of size $O_s(q^s k)$, which is optimal up to the constant factor depending on $s$. This also yields an optimal explicit construction of affine blocking sets in $\mathbb{F}_q^k$ with respect to codimension-$(s+1)$ affine subspaces, and of $s$-minimal codes. Our approach is motivated by a recent construction of Alon, Bishnoi, Das, and Neri of strong $1$-blocking sets, which uses expander graphs with a carefully chosen set of vectors as their vertex set. The main novelty of our work lies in constructing specific hypergraphs on top of these expander graphs, where tree-like configurations correspond to strong $s$-blocking sets. We also discuss some connections to size-Ramsey numbers of hypergraphs, which might be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims an explicit construction of strong s-blocking sets in PG(k-1,q) of size O_s(q^s k), optimal up to an s-dependent constant. The construction places a hypergraph on the vertex set of an expander graph (from the s=1 case of Alon-Bishnoi-Das-Neri) so that certain tree-like subconfigurations intersect every codimension-s subspace in a spanning set; the cardinality bound follows by counting these configurations and using the expander mixing lemma. The same method yields optimal explicit affine blocking sets in F_q^k (w.r.t. codimension-(s+1) flats) and s-minimal codes, plus a discussion of connections to hypergraph size-Ramsey numbers.

Significance. If the central correspondence holds, the result supplies the first explicit constructions of strong s-blocking sets that are optimal up to an s-dependent constant for s>1, extending the s=1 expander-graph technique. The applications to affine blocking sets and minimal codes are direct corollaries, and the size-Ramsey link may be of separate interest. The manuscript ships an explicit, combinatorial construction rather than an existence argument.

major comments (2)
  1. [hypergraph construction and size analysis (the section following the expander-graph setup)] The load-bearing step is the assertion that every codimension-s flat meets at least one tree-like hypergraph configuration in a spanning set. The manuscript must contain an explicit argument showing that the linear dependence relations induced by the hypergraph edges cover all possible s-dimensional quotients; if this fails for even one family of subspaces, the claimed O_s(q^s k) upper bound collapses.
  2. [introduction and main theorem statement] The optimality statement (up to the s-dependent constant) rests on both the upper bound from the construction and a matching lower bound. The lower-bound reference or derivation should be stated explicitly in the same section that derives the O_s(q^s k) count, so that the constant-factor optimality claim is self-contained.
minor comments (2)
  1. [construction section] Notation for the hypergraph edges and the precise definition of 'tree-like configuration' should be introduced with a short displayed definition or diagram before the counting argument begins.
  2. [size bound derivation] The dependence on the underlying expander parameters (degree, expansion constant) inherited from Alon-Bishnoi-Das-Neri should be tracked explicitly when the final O_s(q^s k) expression is written, to make the s-dependence transparent.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [hypergraph construction and size analysis (the section following the expander-graph setup)] The load-bearing step is the assertion that every codimension-s flat meets at least one tree-like hypergraph configuration in a spanning set. The manuscript must contain an explicit argument showing that the linear dependence relations induced by the hypergraph edges cover all possible s-dimensional quotients; if this fails for even one family of subspaces, the claimed O_s(q^s k) upper bound collapses.

    Authors: We agree this step is central to the argument. The manuscript establishes the required spanning property in the section on the hypergraph construction by combining the expander mixing lemma with an analysis of the tree-like subconfigurations and the linear dependencies they induce; this is designed to ensure every codimension-s flat (equivalently, every s-dimensional quotient) is hit. To make the covering argument fully explicit and self-contained as requested, we will add a dedicated lemma in the revision that enumerates the possible linear dependence relations and verifies coverage over all s-dimensional quotients. revision: yes

  2. Referee: [introduction and main theorem statement] The optimality statement (up to the s-dependent constant) rests on both the upper bound from the construction and a matching lower bound. The lower-bound reference or derivation should be stated explicitly in the same section that derives the O_s(q^s k) count, so that the constant-factor optimality claim is self-contained.

    Authors: The lower bound is the standard one obtained by a double-counting argument on the number of codimension-s subspaces (or equivalently from the known minimal size of s-blocking sets). We will revise the introduction and the main theorem section to include an explicit short derivation or reference to this lower bound immediately alongside the O_s(q^s k) upper-bound count, thereby making the constant-factor optimality claim self-contained in one place. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained.

full rationale

The paper presents an explicit combinatorial construction of strong s-blocking sets by layering hypergraphs with tree-like configurations onto expander graphs from prior work. The claimed size bound O_s(q^s k) is obtained by counting these configurations and applying the expander mixing lemma to guarantee spanning intersections with every codimension-s subspace. This counting argument and the hypergraph construction are independent of the target bound; they do not reduce to fitted parameters, self-definitions, or a load-bearing self-citation chain. The cited expander graphs supply a black-box mixing property whose verification lies outside the present manuscript, satisfying the criterion for independent support. No step equates the output size to the input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard facts about projective spaces over finite fields, the existence of expander graphs with suitable expansion, and the combinatorial definition of the hypergraph ensuring the spanning property for all codimension-s subspaces.

axioms (2)
  • standard math Projective space PG(k-1,q) has the usual incidence properties between points and subspaces.
    Invoked in the definition of strong s-blocking set.
  • domain assumption Expander graphs with the required vertex set and expansion exist for the relevant parameters.
    Used as the base for the hypergraph construction.

pith-pipeline@v0.9.0 · 5722 in / 1253 out tokens · 40148 ms · 2026-05-23T17:17:01.981832+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    G. N. Alfarano, M. Borello, A. Neri. A geometric characterization of minimal codes and their asymptotic performance. Adv. Math. Commun. 16 (1) (2022): 115–133

    work page 2022

  2. [2]

    G. N. Alfarano, M. Borello, A. Neri. Outer strong blocking sets. Preprint arXiv:2301.09590 (2023)

    work page arXiv 2023

  3. [3]

    N. Alon. Explicit expanders of every degree and size. Combinatorica 41 (2021): 447–463

    work page 2021

  4. [4]

    N. Alon, A. Bishnoi, S. Das, A. Neri. Strong blocking sets and minimal codes from expander graphs. Trans. Amer. Math. Soc. 377 (2024): 5389–5410

    work page 2024

  5. [5]

    N. Alon, J. Bruck, J. Naor, M. Naor, R. M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inf. Theory 38 (2) (1992): 509–516

    work page 1992

  6. [6]

    Ashikhmin, S

    A. Ashikhmin, S. Litsyn, M. A. Tsfasman. Asymptotically good quantum codes. Phys. Rev. A 63 (2001): 032311

    work page 2001

  7. [7]

    S. Ball. The polynomial method in Galois geometries. In Current Research Topics in Galois Geometry, J. De Beule and L. Storme (eds.), Nova Sci. Publ. (2011): 105– 130, Chapter 5

    work page 2011

  8. [8]

    J. Beck. On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory 7 (1983): 115–129

    work page 1983

  9. [9]

    P. Beelen. A survey on recursive towers and Ihara’s constant. Preprint arXiv:2203.03310 (2022)

    work page arXiv 2022

  10. [10]

    Bishnoi, J

    A. Bishnoi, J. D’haeseleer, D. Gijswijt, A. Potukuchi. Blocking sets, minimal codes and trifferent codes. J. Lond. Math. Soc. 109 (6) (2024): e12938

    work page 2024

  11. [11]

    Blokhuis, P

    A. Blokhuis, P. Sziklai, T. Szonyi. Blocking sets in projective spaces. In Current Research Topics in Galois Geometry , Nova Sci. Publ., New York, NY, USA (2011): 61–84

    work page 2011

  12. [12]

    Bonini, M

    M. Bonini, M. Borello. Minimal linear codes arising from blocking sets. J. Algebr. Comb. 53 (2021): 327–341

    work page 2021

  13. [13]

    A. E. Brouwer, A. Schrijver. The blocking number of an affine space. J. Comb. Theory Ser. A 24 (2) (1978): 251–253

    work page 1978

  14. [14]

    Couvreur, H

    A. Couvreur, H. Randriambololona. Algebraic geometry codes and some applications. In Concise Encyclopedia of Coding Theory, Chapman and Hall/CRC (2021) : 307–362

    work page 2021

  15. [15]

    A. A. Davydov, M. Giulietti, S. Marcugini, F. Pambianco . Linear nonbinary covering codes and saturating sets in projective spaces. Adv. Math. Commun. 5 (1) (2011): 119–147

    work page 2011

  16. [16]

    Erdős, R

    P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp. The size Ramsey number. Period. Math. Hungar. 9 (1978): 145–161

    work page 1978

  17. [17]

    Fancsali, P

    S. Fancsali, P. Sziklai. Lines in higgledy-piggledy arrangement. Electron. J. Comb. 21 (2014). 16

    work page 2014

  18. [18]

    Sz. L. Fancsali, P. Sziklai. Higgledy-piggledy subspaces and uniform subspace designs . Des. Codes Cryptogr. 79 (2016): 625–645

    work page 2016

  19. [19]

    Guruswami, S

    V. Guruswami, S. Kopparty. Explicit subspace designs. Combinatorica 36 (2) (2016): 161–185

    work page 2016

  20. [20]

    Héger, Z

    T. Héger, Z. L. Nagy. Short minimal codes and covering codes via strong blocking s ets in projective spaces. IEEE Trans. Inf. Theory 68 (2) (2021): 881–890

    work page 2021

  21. [21]

    Høholdt, J

    T. Høholdt, J. H. Van Lint, R. Pellikaan. Algebraic geometry codes. Handbook of Coding Theory 1 (Part 1) (1998): 871–961. Elsevier Amsterdam

    work page 1998

  22. [22]

    Justesen

    J. Justesen. Class of constructive asymptotically good algebraic codes . IEEE Trans. Inf. Theory 18 (5) (1972): 652–656

    work page 1972

  23. [23]

    Letzter, A

    S. Letzter, A. Pokrovskiy, L. Yepremyan. Size-Ramsey numbers of powers of hypergraph trees and long subdivisions. Preprint arXiv:2103.01942 (2021)

    work page arXiv 2021

  24. [24]

    Lubotzky, R

    A. Lubotzky, R. Phillips, P. Sarnak. Ramanujan graphs. Combinatorica 8 (3) (1988): 261–277

    work page 1988

  25. [25]

    F. J. MacWilliams, N. J. A. Sloane, J. G. Thompson. Good self-dual codes exist. Discrete Math. 3 (1-3) (1972): 153–162

    work page 1972

  26. [26]

    H. G. Quebbemann. On even codes. Discrete Math. 98 (1991): 29–34

    work page 1991

  27. [27]

    Sipser, D

    M. Sipser, D. A. Spielman. Expander codes. IEEE Trans. Inf. Theory 42 (6) (1996): 1710–1722

    work page 1996

  28. [28]

    Stichtenoth

    H. Stichtenoth. Transitive and Self-dual Codes Attaining the Tsfasman-Vla dut-Zink Bound. IEEE Trans. Inf. Theory 52 (2006): 2218–2224

    work page 2006

  29. [29]

    C. Tang, Y. Qiu, Q. Liao, Z. Zhou. Full characterization of minimal linear codes as cutting blocking sets. IEEE Trans. Inf. Theory 67 (6) (2021): 3690–3700

    work page 2021

  30. [30]

    Tsfasman, S

    M. Tsfasman, S. G. Vladut. Algebraic-geometric codes. Springer Science & Business Media, Vol. 58 (2013)

    work page 2013

  31. [31]

    Tsfasman, S

    M. Tsfasman, S. G. Vladut, T. Zink Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound. Math. Nachr. 109 (1) (1982): 21–28

    work page 1982

  32. [32]

    Y. Xu, H. Kan, G. Han. r-minimal codes with respect to rank metric. Preprint arXiv:2408.15592 (2024). 17

    work page arXiv 2024