betaFeedback

WorksMathematics

Explicit strong blocking sets and minimal codes from expander graphs using a new graph parameter

Abstract

A strong blocking set is a set of points in a finite projective space that intersects every hyperplane of the space in a spanning set of the hyperplane. These objects have been studied both in finite geometry and coding theory due to their equivalence with minimal codes. We give an explicit construction of strong blocking sets using expander graphs that improves the explicit construction of Alon et al. (Noga Alon, Anurag Bishnoi, Shagnik Das, Alessandro Neri, Strong blocking sets and minimal codes from expander graphs. Transactions of the American Mathematical Society ) by introducing a new geometrically motivated graph parameter that is better suited for this problem. Using this approach, we improve the constant CC in the explicit construction of a strong blocking set of size C(q+1)kC (q+1) k in the (k−1)(k - 1)-dimensional projective space over Fq\mathbb{F}_q for every prime power q≥7q \geq 7.

Introduction

Strong blocking sets in projective spaces have been studied extensively in the last ten years. These objects were first introduced by Davydov et al. [18] to construct saturating sets and then reintroduced by Hégr et al. [25] to study the qq-analog of a classic combinatorial search problem: identifying an unknown projective point using subspace queries. Since then, these objects have been reinvented and studied under various names, such as cutting blocking sets [1, 9, 13], generating sets [19], and the now commonly used term of strong blocking sets [4, 24, 30].

The recent flurry of results is primarily motivated by a connection with coding theory that was independently discovered by Alfarano et al. [1] and Tang et al. [39]. They showed that a strong blocking set of size nn in a finite projective space PG⁡(k−1,q)\operatorname{PG}(k-1,q) is equivalent to a minimal kk-dimensional linear code of length nn. Minimal codes are linear codes in which the support of a nonzero codeword uu is a subset of the support of a nonzero codeword vv if and only if u=λvu = \lambda v for some scalar λ\lambda. These codes have their own history dating back to 1993 in the work of Massey on secret sharing protocols [34]. Then Ashikhmin and Barg established sufficient conditions for their existence [7] which led to several interesting constructions [35] (also see [26] for minimal codes violating this condition). Recently, it was shown that minimal codes are in fact equivalent to strong blocking sets, thus converging these two threads of research. Since then, strong blocking sets and minimal codes have also found connections with perfect hashing [11] and additive combinatorics [14].

In [3], it was shown that the smallest length nn of a minimal code of dimension kk, or equivalently the smallest size nn of a strong blocking set in PG⁡(k−1,q)\operatorname{PG}(k-1,q), must be at least (q+1)(k−1)(q+1)(k-1). This lower bound was further improved in [11] and [38]. A probabilistic argument [11, 24] shows that such codes of length at most 2(q+1)k2(q+1)k exist. One of the main problems on minimal codes is to give explicit constructions of such codes that have length at most C(q+1)kC(q+1)k for some constant CC. The main regime of interest is fixed, but possibly large, qq and k→∞k \to\infty. The first author solved this problem in collaboration with Alon, Das and Neri [4] by giving a graph-theoretic construction that combined explicit construction of asymptotically good error-correcting codes with explicit constant degree expander graphs. While for q≤5q \le5, the best constant is obtained via earlier concatenation based constructions [10], for all q≥7q \ge7, the graph-theoretic construction is significantly better.

In this paper, we further optimize the graph-theoretic construction by following a similar general approach of [4] but using a better graph parameter that is fine-tuned for the geometry of finite projective spaces. This gives us a better constant for every q≥7q \ge7, summarized in Table 2. For example, the best construction for q=7q=7 was of size 46.32(q+1)k46.32(q+1)k, while our new construction is of size at most 44.62(q+1)k44.62(q+1)k. The key novelty of our work is the introduction of a new graph parameter fq(G)f_q(G) for a graph GG that incorporates the field size qq by using the geometrical property that through a fixed codimension-2 space there are exactly q+1q+1 hyperplanes. The previous graph parameter that was used in [4] is the vertex integrity of a graph, denoted by ι(G)\iota(G), which is independent of the field size. We show that fq(G)≥ι(G)f_q(G) \ge\iota(G) for all graphs GG and q≥2q \ge2, and we prove a spectral lower bound on fq(G)f_q(G) that is much better than the best known lower bound on ι(G)\iota(G). This spectral lower bound on fq(G)f_q(G) is the key source of improvement in the final optimization. From a coding-theoretic perspective, we reduce the length of the best known explicit constructions of kk-dimensional minimal linear codes, as the length corresponds to the size of the strong blocking set.

qqConstructionUpper bound using fq(G)f_q(G)Upper bound using ι(G)\iota(G)
23rd derivation116.43117.46
32nd derivation74.5176.38
42nd derivation58.2258.73
52nd derivation52.3952.59
71st derivation44.6246.32
81st derivation40.2341.45
91st derivation37.2638.19
111st derivation33.5134.09
131st derivation31.2331.63
161st derivation29.1129.37
171st derivation28.6128.83
191st derivation27.8027.97
23≤q≤2523\leq q\leq251st derivation26.6226.74
27≤q≤3227\leq q\leq321st derivation25.8525.93
37≤q≤4937\leq q\leq491st derivation24.7124.75
53≤q≤10953\leq q\leq1091st derivation23.8223.84
113≤q≤1217113\leq q\leq12171st derivation22.8122.82
1223≤q≤127631223\leq q\leq127631st derivation21.9321.93
q≥12769q\geq12769, qq non-square1st derivation21.9321.93
12769≤q≤7060312769\leq q\leq70603, qq squareoriginal20.5320.53
q>70603q>70603, qq squareoriginal20.0020.00

Table 2. For given ranges of prime powers qq (First Column), this table provides the best upper bound on the size of strong blocking sets in finite projective spaces over Fq\mathbb{F}_q that we have obtained in the normalized constant CC in front of k(q+1)k(q+1) (third column) together with an indication of which construction achieve this: Original (Theorem 5.1), 1st derivation (Theorem 5.2) or rthr^{th} derivation. The fourth columns contains the earlier bounds obtained using the vertex integrity of a graph.

In § 2, we provide the necessary background and required notation to the reader about coding theory, projective spaces, strong blocking sets and expander graphs. In § 3, we introduce the new graph parameter and prove a spectral lower bound on this parameter for the family of tt-regular graphs. In § 4, we analyze the graph theoretic construction of the strong blocking set in relation to the graph parameter and its geometric implications. In § 5, we show the new results by optimize the size of strong blocking set and compare them with those previously derived by vertex integrity using algebraic-geometric codes, almost Ramanujan graphs and the tool of field reduction to handle non-quadratic fields. Finally, in § 6, we conclude the results of this paper and discuss how this new parameter can give rise to new fruitful questions and research directions.

Preliminaries

We review the basic notions from coding theory that will be used throughout the paper, with particular emphasis on minimal linear codes and their geometric interpretation. For a more detailed exposition we refer to standard references like [31] and [22].

Minimal codes and strong blocking sets

An [n,k,d]q[n,k,d]_q code is a kk-dimensional vector subspace of Fqn\mathbb{F}_q^n with minimum Hamming distance dd. For a codeword c=(c1,…,cn)∈C\boldsymbol{c}=(c_1,\ldots,c_n)\in C, its support is given by σ(c)={i∈[n]:ci≠0}\sigma(\boldsymbol{c})=\{i\in[n]:c_i\ne0\} and w(c)=∣σ(c)∣w(\boldsymbol{c})=|\sigma(\boldsymbol{c})|. The rate and relative distance of CC are k/nk/n and d/nd/n, respectively.

The standard problem in coding theory is to study the extremal values of one parameter with respect to the others. For a family of [ni,ki,di]q[n_i,k_i,d_i]_q codes, with ni→∞n_i \to\infty, the asymptotic rate and relative distance are defined as

R=lim inf⁡i→∞kini,R=\liminf_{i\to\infty}\frac{k_i}{n_i},

and

δ=lim inf⁡i→∞dini.\delta= \liminf_{i\to\infty} \frac{d_i}{n_i}.

An infinite family of codes is called asymptotically good if R>0R>0 and δ>0\delta>0 (see [22 Section 1.8] or [31 Chapter 9]). Existence of such codes can be easily shown via a probabilistic argument [31 Section 5.1], but giving explicit constructions of such codes is highly nontrivial. Justensen gave the first explicit construction in [28]. Later, explicit constructions were found using modular curves that were even better than probabilistic constructions for all q≥49q\geq49 (see [17, 40, 41]).

Our main focus is on minimal codes, which we now define and discuss in detail. A nonzero codeword vv in a linear code is said to be minimal if the support σ(c)\sigma(c) is minimal with respect to the inclusion in the set

σ(C):={σ(x):x∈C∖{0⃗}}.\sigma(C) := \{\sigma(x): x\in C\setminus\{\vec{0}\}\}.

In a linear code, if c1c_1 is a minimal codeword then for any codeword c2c_2 we have σ(c2)⊆σ(c1)\sigma(c_2)\subseteq\sigma(c_1) if and only if c2=λc1c_2=\lambda c_1 for some scalar λ\lambda.

Definition 2.1. The (linear) code CC over a finite field Fq\mathbb{F}_q is called a minimal code if all of its nonzero codewords are minimal. Equivalently, a linear code is minimal if σ(c1)⊆σ(c2)⟺∃λ∈Fq c1=λc2\sigma(c_1)\subseteq\sigma(c_2)\Longleftrightarrow\exists\lambda\in\mathbb{F}_q\ c_1=\lambda c_2, for all c1,c2∈Cc_1,c_2\in C.

We now describe the equivalence between minimal codes and strong blocking sets that was discovered in [1] and [39]. Let PG⁡(k−1,q)\operatorname{PG}(k-1,q) denote the k−1k-1 dimensional projective space defined over the vector space Fqk\mathbb{F}_q^k. We identify the points of PG⁡(k−1,q)\operatorname{PG}(k-1,q) with the 11-dimensional vector subspaces of Fqk\mathbb{F}_q^k and lines with the 22-dimensional vector subspaces. For a set SS of points in the projective space we denote by ⟨S⟩\langle S\rangle the span of these points, that is, the smallest dimensional projective subspace containing SS.

Definition 2.2. A projective [n,k,d]q[n,k,d]_q system is a multiset of nn points, M⊆PG⁡(k−1,q)M\subseteq\operatorname{PG}(k-1,q), such that (i) ⟨M⟩=PG⁡(k−1,q)\langle M\rangle=\operatorname{PG}(k-1,q) and (ii) d=n−max⁡{∣H∩M∣:H is a hyperplane}d=n-\max\{|H\cap M|:H\text{ is a hyperplane}\}.

A projective [n,k,d]q[n,k,d]_q system can be viewed as a geometric representation of a nondegenerate [n,k,d]q[n,k,d]_q code. By choosing representatives of the points of the system as the columns of a k×nk\times n matrix yields a generator matrix of a nondegenerate code, that is, the row space of this matrix is an [n,k,d]q[n,k,d]_q code and there are no zero columns. Conversely, the columns of a generator matrix of an arbitrary nondegenerate [n,k,d]q[n,k,d]_q code define a multiset of points in PG⁡(k−1,q)\operatorname{PG}(k-1,q) that form an [n,k,d]q[n,k,d]_q system.

We now introduce the main finite geometric object studied in this paper.

Definition 2.3. A set M⊆PG⁡(k−1,q)M\subseteq\operatorname{PG}(k-1,q) is said to be a strong blocking set if ⟨H∩M⟩=H\langle H\cap M\rangle=H, for every hyperplane HH of PG⁡(k−1,q)\operatorname{PG}(k-1,q).

Theorem 2.4 (see [1], [39]). Let CC be a nondegenerate [n,k,d]q[n,k,d]_q code and let G=(g1∣⋯∣gn)∈Fqk×nG=(g_1\mid\cdots\mid g_n)\in\mathbb{F}_q^{k\times n} be any of its generator matrices. Then CC is a minimal code if and only if the projective system corresponding to CC is a strong blocking set in PG⁡(k−1,q)\operatorname{PG}(k-1,q).

With this equivalence in mind, the natural question of studying the shortest possible length of a (linear) minimal code of dimension kk over Fq\mathbb{F}_q translates to studying the smallest possible size of a strong blocking set in PG⁡(k−1,q)\operatorname{PG}(k-1,q). In [3], a lower bound of the form (q+1)(k−1)(q+1)(k-1) was proved, that follows from the polynomial method. The following is the best known lower bound for this problem.

Theorem 2.5 (see [11 Theorem 1.4], [38 Theorem 3.3]). For any prime power qq, there is a constant 1.52<cq≤2+1/21.52 < c_q \le\sqrt{2} + 1/2 such that every strong blocking set in PG(k−1,q)\mathrm{PG}(k - 1,q) has size at least (q+cq)(k−1)(q+c_q)(k-1), for large enough kk.

The best known existence results for the upper bounds on the size of the smallest strong blocking set have been proved via the probabilistic method for the cases when q=2q=2 in [36] and for q>2q>2 in [11, 2].

The key idea behind these probabilistic constructions, as well as many explicit constructions, is to consider points sets that are unions of lines in a projective space. If ℓ1,…,ℓm\ell_1,\ldots,\ell_m is the collection of lines, then their union forms a strong blocking set (of size at most (q+1)m(q+1)m) if and only if there is no pair (S,H)(S,H) where SS is a codimension-2 subspace and HH is a hyperplane containing SS such that for all ii, either ℓi⊆S\ell_i\subseteq S or ℓi∩H\ell_i\cap H is a single point contained in SS. These constructions often satisfy the following stronger property, synthesized in [19 Theorem 11].

Definition 2.6. A set L\mathcal{L} of lines in PG(k−1,q)\mathrm{PG}(k-1,q) is said to have the avoidance property if for all codimension-2 subspaces WW, there exists a line ℓ∈L\ell\in\mathcal{L} such that W∩ℓ=∅W\cap\ell=\varnothing.

Theorem 2.7. If a set L\mathcal{L} of lines satisfies the avoidance property, then the point-set B=⋃ℓ∈Lℓ\mathcal{B}=\bigcup_{\ell\in\mathcal{L}}\ell forms a strong blocking set.

We will use this avoidance property in our construction as well.

Expander Graphs

Throughout the paper, our constructions are based on tt-regular expander graphs. Informally, expander graphs can be thought of as graphs whose edges are well distributed, ensuring that every vertex subset that is not too large has many outgoing edges. For formal definitions of this concept, as well as a discussion of their properties and applications in combinatorics, coding theory, and computer science, we refer the reader to [27, 5, 21].

We study expander graphs through the lens of spectral graph theory. Let a graph G=(V,E)G=(V,E) with ∣V∣=n|V|=n vertices be a tt-regular graph with adjacency matrix A(G)A(G) and let the eigenvalues of its adjacency matrix be in the following decreasing order: t=μ1≥μ2≥⋯≥μnt=\mu_1\ge\mu_2\ge\cdots\ge\mu_n from the largest to the smallest one.

Definition 2.8 (Expander Graph). A graph GG is called an (n,t,λ)(n,t,\lambda)-graph if it is a tt-regular connected graph on nn vertices with ∣μi∣≤λ|\mu_i|\le\lambda for all i≥2i\ge2.

In our analysis, we will make use of a tight variant of the Expander Mixing Lemma. This lemma is often attributed to Alon and Chung [5], but it appears about 10 years earlier in the PhD thesis of Haemers [23].

Lemma 2.9. Let GG be an (n,t,λ)(n,t,\lambda)-graph. We set λ=max⁡{∣μ2∣,∣μn∣}\lambda=\max\{|\mu_2|,|\mu_n|\}. Let S,T⊂V(G)S,T\subset V(G). Denote by e(S,T)e(S,T) to be the number of pairs (x,y)∈S×T(x,y)\in S\times T such that xyxy is an edge of GG, then it holds,

∣e(S,T)−tn∣S∣∣T∣∣≤λ∣S∣∣T∣(1−∣S∣n)(1−∣T∣n)\left|e(S,T)-\frac{t}{n}|S||T|\right|\le\lambda\sqrt{|S||T|\left(1-\frac{|S|}{n}\right)\left(1-\frac{|T|}{n}\right)}

where λ\lambda is the largest absolute value of an eigenvalue other than μ1\mu_1.

It is worth noting that t∣S∣∣T∣/nt|S||T|/n is the expected number of edges from SS to TT if the GG was a random graph formed by picking each independently with probability t/nt/n. We are closer to this value if λ\lambda is small. Thus, it is natural to make λ\lambda as small as possible with respect to tt. The Alon–Boppana bound [37] places a fundamental limitation on how small λ\lambda can be. It states that for any infinite family of (n,t,λ)(n,t,\lambda)-graphs, λ≥2t−1−o(1)\lambda\ge2\sqrt{t-1}-o(1) as n→∞n \to\infty. This naturally leads to the definition of Ramanujan graphs, which constitute one of the most prominent families of expander graphs.

Definition 2.10. Let a tt-regular graph GG with eigenvalues sorted as follows, t=μ1≥μ2≥…≥μnt=\mu_1 \ge\mu_2 \ge\ldots\ge\mu_n. If max⁡{∣μi∣:∣μi∣<t}≤2t−1\max\{|\mu_i| : |\mu_i| < t\} \le2\sqrt{t-1}, then GG is called a Ramanujan graph.

Lubotsky, Phillips and Sarnak [32] and Margulis [33] gave explicit constructions of an (n,p+1,2p)(n,p+1,2\sqrt{p}) Ramanujan graphs for n=Θ(p3)n=\Theta(p^3), where pp is a prime such that p≡1(mod4)p \equiv1 \pmod{4} using linear algebraic groups. In general, the known constructions of Ramanujan graphs are very restrictive in their parameters. By a relaxation of the bound on λ\lambda, we can find constructions that works for every degree tt and n→∞n \to\infty. We will use this result instead.

Theorem 2.11 ([6], Theorem 1.3). For every positive integer tt, and every ε>0\varepsilon> 0, there is an n0(t,ε)n_0(t,\varepsilon) such that for all n≥n0(t,ε)n \ge n_0(t,\varepsilon) with ntnt to be even, there is an explicit construction of an (n,t,λ)(n,t,\lambda)-graph Gn,tεG_{n,t}^{\varepsilon} with λ≤2t−1+ε\lambda\le2\sqrt{t-1}+\varepsilon

A new graph parameter

The previously known explicit construction of strong blocking sets that are constructed from expander graphs were based on the vertex integrity of a graph [4], § 4 (see [8] for a survey on this graph parameter). The vertex integrity, denoted as ι(G)\iota(G), is defined as

ι(G):=min⁡S⊆V{∣S∣+max⁡D∈cc(G−S)∣D∣}.\iota(G) := \min_{S \subseteq V} \{|S| + \max_{D \in cc(G-S)} |D|\}.

where cc(G−S)cc(G-S) is the set of connected components in the graph obtained by deleting SS from GG.

The new graph parameter that we will use is motivated by the line avoidance property Definition 2.6 that we want to guarantee and the fact that the hyperplanes through any fixed codimension-2 subspace SS in PG(k−1,q)\mathrm{PG}(k-1,q) partition PG(k−1,q)\S\mathrm{PG}(k-1,q)\backslash S into q+1q+1 parts. If a collection L\mathcal{L} of lines does not have the avoidance property, then there exists a codimension-2 subspace WW such that all lines in our collection L\mathcal{L} intersect WW. Therefore, among the q+1q+1 hyperplanes H1,…,Hq+1H_1,\ldots,H_{q+1} containing WW, there is no pair Hi,HjH_i,H_j with a line ℓ∈L\ell\in\mathcal{L} that contains a point of Hi\WH_i \backslash W and a point of Hj\WH_j \backslash W. We define a graph parameter that captures this property and then we prove that this new parameter is stronger than vertex integrity.

Definition 3.1. For a graph GG and integer q≥2q \ge2, let

fq(G):=min⁡S⊆V{∣S∣+max⁡∣Ci∣:S⊔C1⊔⋯⊔Cq+1=V(G),e(Ci,Cj)=0 ∀i≠j}.f_q(G) := \min_{S \subseteq V} \{|S| + \max|C_i| : S \sqcup C_1 \sqcup\cdots\sqcup C_{q+1} = V(G), e(C_i,C_j)=0 \ \forall i \ne j\}.

Remark 3.2. The definition is sensible for any integer q≥1q \ge1, but for us qq will be a prime power and thus q≥2q \ge2 is a fair assumption.

Lemma 3.3. For every every graph GG, fq(G)≥ι(G)f_q(G) \ge\iota(G).

Proof. Take any subset S⊆V(G)S \subseteq V(G) for which it holds that fq(G)=∣S∣+max⁡i=1,…,q+1∣Ci∣f_q(G)=|S|+\max_{i=1,\ldots,q+1}|C_i| and let C1,C2,…,Cq+1C_1,C_2,\ldots,C_{q+1} to be q+1q+1 disjoint sets of size ∣Ci∣=ci|C_i|=c_i with no edges between them. We can observe that for such a subset SS, every connected component of G−SG-S must be contained in one of the CiC_i's for i=1,2,…,q+1i=1,2,\ldots,q+1, hence the maximum size of any connected component of G−SG-S is at most max⁡i=1,…,q+1∣Ci∣\max_{i=1,\ldots,q+1}|C_i|. Because the vertex integrity is the minimum over all subset SS we get that ι(G)≤∣S∣+max⁡i=1,…,q+1∣Ci∣=fq(G)\iota(G) \le|S|+\max_{i=1,\ldots,q+1}|C_i|=f_q(G) and the desired inequality follows. ∎

In [4], the authors established the following spectral lower bound on vertex integrity. For any (n,t,λ)(n,t,\lambda)-graph GG, we have that

ι(G)≥(t−λt+λ)n.\iota(G) \ge\left(\frac{t-\lambda}{t+\lambda}\right)n.

Lemma 3.3 then implies fq(G)≥(t−λt+λ)nf_q(G) \ge\left(\frac{t-\lambda}{t+\lambda}\right)n. The following lemma gives a strictly better bound.

Lemma 3.4. For any (n,t,λ)(n,t,\lambda)-graph GG, we have that

fq(G)≥(t−λ+2λ/qt+λ+2λ/q)n.(1)f_q(G) \ge\left(\frac{t-\lambda+2\lambda/q}{t+\lambda+2\lambda/q}\right)n. \tag*{(1)}

Proof. Let P={S,C1,C2,…,Cq+1}\mathcal{P}=\{S,C_1,C_2,\ldots,C_{q+1}\} be a partition of the vertex set of the graph GG, V(G)=C1⊔⋯⊔Cq+1V(G)=C_1\sqcup\cdots\sqcup C_{q+1}, such that there are no edges between the components CiC_i and CjC_j ∀i≠j\forall i\ne j and fq(G)=∣S∣+max⁡∣Ci∣f_q(G)=|S|+\max|C_i|. Without loss of generality, assume that the components have the following decreasing size ordering, c1≥c2≥⋯≥cq+1c_1\ge c_2\ge\cdots\ge c_{q+1} where ci=∣Ci∣c_i=|C_i| ∀i=1,2,…,q+1\forall i=1,2,\ldots,q+1. Therefore, fq(G)=s+c1f_q(G)=s+c_1, where s=∣S∣s=|S|.

We now give a lower bound on s+c1s+c_1. For the clarity of the analysis we define C=⋃i=1q+1CiC=\bigcup_{i=1}^{q+1}C_i and c=∣C∣=∑i=1q+1ci=n−sc=|C|=\sum_{i=1}^{q+1}c_i=n-s. By Lemma 2.9, we get

e(C)≥tc22n−λ2c(1−cn)=(t+λ)c22n−λc2.(2)e(C)\ge\frac{tc^2}{2n}-\frac{\lambda}{2}c\left(1-\frac{c}{n}\right)=\frac{(t+\lambda)c^2}{2n}-\frac{\lambda c}{2}. \tag*{(2)}

and

e(Ci)≤(t−λ)ci22n+λci2,(3)e(C_i)\le\frac{(t-\lambda)c_i^2}{2n}+\frac{\lambda c_i}{2}, \tag*{(3)}

for all i=1,2,…,q+1i=1,2,\ldots,q+1. The upper bounds on e(Ci)e(C_i) imply

e(C)≤∑i=1q+1e(Ci)≤t−λ2n∑i=1q+1ci2+λ2∑i=1q+1ci=t−λ2n∑i=1q+1ci2+λc2.(4)\begin{aligned} e(C)&\le\sum_{i=1}^{q+1}e(C_i)\\ &\le\frac{t-\lambda}{2n}\sum_{i=1}^{q+1}c_i^2+\frac{\lambda}{2}\sum_{i=1}^{q+1}c_i\\ &=\frac{t-\lambda}{2n}\sum_{i=1}^{q+1}c_i^2+\frac{\lambda c}{2}. \tag*{(4)} \end{aligned}

By combining Equation (4) and Equation (2) we get

(t+λ)c22n−λc2≤t−λ2n∑i=1q+1ci2+λc2.\frac{(t+\lambda)c^2}{2n}-\frac{\lambda c}{2}\le\frac{t-\lambda}{2n}\sum_{i=1}^{q+1}c_i^2+\frac{\lambda c}{2}.

To simplify the right hand side, we use ci2=ci⋅ci≤c1cic_i^2=c_i\cdot c_i\le c_1c_i to get ∑i=1q+1ci2≤c1∑i=1q+1ci=c1c\sum_{i=1}^{q+1}c_i^2\le c_1\sum_{i=1}^{q+1}c_i=c_1c. Therefore, we get

(t+λ)c2−(t−λ)c1c≤2λnc.(t+\lambda)c^2-(t-\lambda)c_1c\le2\lambda nc.

Dividing by cc, then substituting c=n−sc=n-s, and rearranging the equation we get

(t+λ)s+(t−λ)c1≥(t−λ)n.(t+\lambda)s+(t-\lambda)c_1\ge(t-\lambda)n.

Now substitute s=f−c1s=f-c_1 and we are ready to prove the lower bound on ff, where f=fq(G)f=f_q(G). This gives

(t+λ)f≥2λc1+(t−λ)n.(5)(t+\lambda)f \ge2\lambda c_1+(t-\lambda)n. \tag*{(5)}

We now need a lower bound on c1c_1 in terms of the other parameters so that we can simplify this linear inequality into a lower bound on ff. Note that n−f=n−s−c1=∑i=2q+1ci≤(q+1−2+1)c1=qc1n-f=n-s-c_1=\sum_{i=2}^{q+1}c_i\le(q+1-2+1)c_1=qc_1. This implies c1≥(n−f)/qc_1\ge(n-f)/q. Substituting it to Equation (5) we get

(t+λ)f≥2λ(n−f)/q+(t−λ)n.(t+\lambda)f \ge2\lambda(n-f)/q+(t-\lambda)n.

Solving for ff gives us the following lower bound,

fq(G)=f≥(t−λ+2λ/qt+λ+2λ/q)n.f_q(G)=f\ge\left(\frac{t-\lambda+2\lambda/q}{t+\lambda+2\lambda/q}\right)n.

Equation (1) gives a lower bound on the new parameter fq(G)f_q(G) which is strictly better than the spectral lower bound on the vertex integrity of GG for all λ>0\lambda>0. For example, for q=2q=2, we get fq(G)≥(tt+2λ)nf_q(G)\ge\left(\frac{t}{t+2\lambda}\right)n, whereas the bound on vertex integrity is always ι(G)≥(t−λt+λ)n\iota(G)\ge\left(\frac{t-\lambda}{t+\lambda}\right)n.

In the following section we compare the improvements we get in the strong blocking set constructions using this new parameter.

Strong blocking sets from graphs

In this section, we give the graph-theoretic construction from [4], which we adapt to our new graph parameter. Let V={P1,…,Pn}V=\{P_1,\ldots,P_n\} be a set of nn points in PG⁡(k−1,q)\operatorname{PG}(k-1,q). Let G=(V,E)G=(V,E) be a graph on these points. From this graph, we define the set of lines

L(V,G):={⟨Pi,Pj⟩:PiPj∈E}\mathcal{L}(V,G):=\{\langle P_i,P_j\rangle:P_iP_j\in E\}

and the set of points

B(V,G):=⋃ℓ∈L(V,G)ℓ\mathcal{B}(V,G):=\bigcup_{\ell\in\mathcal{L}(V,G)}\ell

By carefully choosing the set of points VV in PG⁡(k−1,q)\operatorname{PG}(k-1,q) and graph GG, we will ensure that B(V,G)\mathcal{B}(V,G) is a strong blocking set. Note that the size of B(V,G)\mathcal{B}(V,G) is at most n+(q−1)∣E∣n+(q-1)|E|. Therefore, to get such a set of size linear in kk, both nn and ∣E∣|E| must be a linear function of kk. The following result provides a sufficient condition for the line-set L(V,G)\mathcal{L}(V,G) to satisfy the avoidance property, which then implies that B(V,G)\mathcal{B}(V,G) is a strong blocking set.

Lemma 4.1. Let V⊆PG⁡(k−1,q)V\subseteq\operatorname{PG}(k-1,q), with ∣V∣=n|V|=n such that every hyperplane HH contains at most n−dn-d points of VV, for some integer d>0d>0. Let G=(V,E)G=(V,E) be a graph such that fq(G)≥n−d+1f_q(G)\ge n-d+1. Then L={⟨x,y⟩:xy∈E}\mathcal{L}=\{\langle x,y\rangle:xy\in E\} has the avoidance property.

Proof. Let us suppose for the sake of contradiction that the set of lines L\mathcal{L} does not satisfy the avoidance property. Therefore, there exists a codimension-2 subspace WW such that every line ℓ∈L\ell\in\mathcal{L} contains a point of WW. Since WW is of codimension-2, there are exactly q+1q+1 distinct hyperplanes containing WW, which partition the points of PG⁡(k−1,q)\operatorname{PG}(k-1,q) outside WW into q+1q+1 parts. Define S=V∩WS=V\cap W and let Ci=(Hi∖W)∩VC_i=(H_i\setminus W)\cap V for i=1,…,q+1i=1,\ldots,q+1, where HiH_i is the ii-th hyperplane through W. Note that if a line contains two points of the subspace then it must be fully contained in it. Say, there exists an edge e=xye=xy with x∈Cix \in C_i and y∈Cjy \in C_j for some i≠ji \ne j, and let ℓ=⟨x,y⟩\ell= \langle x,y\rangle. Since x∈Hi∖Wx \in H_i \setminus W, ℓ\ell is not fully contained in WW. If ℓ∩W\ell\cap W contains a point zz, then ℓ\ell must be fully contained in both HiH_i and HjH_j, and thus ℓ⊆W=Hi∩Hj\ell\subseteq W = H_i \cap H_j, which is a contradiction. Therefore, there are no edges between any pair of components CiC_i and CjC_j for i≠ji \ne j and from the definition of fq(G)f_q(G), we get fq(G)≤∣S∣+max⁡i∈[q+1]∣Ci∣f_q(G) \le|S| + \max_{i \in[q+1]} |C_i|. Since S∪Ci⊆HiS \cup C_i \subseteq H_i, we have ∣S∣+∣Ci∣≤n−d|S| + |C_i| \le n-d for all ii. Therefore, fq(G)=∣S∣+max⁡i∣Ci∣≤n−df_q(G) = |S| + \max_i |C_i| \le n-d, contradicting our assumption that fq(G)>n−df_q(G) > n-d.

Corollary 4.2. If VV is a projective [n,k,d]q[n,k,d]_q system and G=(V,E)G=(V,E) is a graph with parameter fq(G)≥n−d+1f_q(G) \ge n-d+1, then B(V,G)\mathcal{B}(V,G) is a strong blocking set in PG⁡(k−1,q)\operatorname{PG}(k-1,q) of size at most n+(q−1)∣E∣n+(q-1)|E|.

Proof. A projective [n,k,d]q[n,k,d]_q system corresponds to a set VV of points in PG⁡(k−1,q)\operatorname{PG}(k-1,q) such that every hyperplane contains at most n−dn-d points of VV. We saw that L(V,G)\mathcal{L}(V,G) must be a set of ∣E∣|E| lines that satisfy the avoidance property, and hence B(V,G)\mathcal{B}(V,G) is a strong blocking set of size at most n+(q−1)∣E∣n+(q-1)|E|.

We proceed now to the proof of the main result by giving an explicit construction of strong blocking sets in PG⁡(k−1,q)\operatorname{PG}(k-1,q) of size at most Ck(q+1)Ck(q+1), with an improved constant than the one obtained in prior work [4].

Small explicit constructions of strong blocking sets

In this section we show how the explicit constructions via the new graph parameter that depends on the field size, can reduce the size of the explicit strong blocking sets, by using Algebraic-Geometric (AG) codes, expander graphs, and field reduction. This follows the same template given in [4] but with our new graph parameter, which then requires a new analysis and optimization of constants.

Analysis of the new parameter over quadratic fields

Our first result is obtained via a combination of Corollary 4.2 and Lemma 3.4 together with the expander graph explicit construction given by Theorem 2.11. Note that for every square prime power qq there exists an explicit AG-code families of rates R,δ>0R,\delta> 0 that satisfy R+δ≥1−(q−1)−1R+\delta\ge1-(\sqrt{q}-1)^{-1} [40, 17], that is, we can construct an (R,δ)q(R,\delta)_q-family of [ni,ki,di]q[n_i,k_i,d_i]_q codes for some increasing sequences {ni}i∈N\{n_i\}_{i \in\mathbb{N}}, {ki}i∈N\{k_i\}_{i \in\mathbb{N}} and {di}i∈N\{d_i\}_{i \in\mathbb{N}}.

Theorem 5.1. Let t≥3t \ge3 and let q>4q > 4 be a square prime power such that

1q−1<t−2t−1+4t−1qt+2t−1+4t−1q\frac{1}{\sqrt{q}-1} < \frac{t-2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q}}{t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q}}

and let ε>0\varepsilon> 0. Then there is a strictly increasing sequence of dimensions {ki}i∈N\{k_i\}_{i \in\mathbb{N}} for which we can explicitly construct strong blocking sets in PG⁡(ki−1,q)\operatorname{PG}(k_i-1,q) of size at most

(t(t+2t−1+4t−1q)(q−1)2(t(q−2)−2q(t−1)+4(q(t−1)−2t−1)q)+ε)kiq.\left(\frac{t\left(t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q}\right)(\sqrt{q}-1)}{2\left(t(\sqrt{q}-2)-2\sqrt{q(t-1)}+\frac{4(\sqrt{q(t-1)}-2\sqrt{t-1})}{q}\right)}+\varepsilon\right)k_iq.

Before analyzing the proof, we show what this result implies about the size of the strong blocking set in PG⁡(k−1,q)\operatorname{PG}(k-1,q), when qq is a square. We need to minimize the following function

Fq(t):=t(t+2t−1+4t−1q)(q−1)2(t(q−2)−2q(t−1)+4(q(t−1)−2t−1)q).F_q(t) := \frac{t\left(t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q}\right)(\sqrt{q}-1)}{2\left(t(\sqrt{q}-2)-2\sqrt{q(t-1)}+\frac{4(\sqrt{q(t-1)}-2\sqrt{t-1})}{q}\right)}.

First to simplify the analysis we substitute y=t−1y=\sqrt{t-1} and then we set the derivative of the function to 0, to find a local extrema. For this we need to find the zeros of the polynomial

ψq(y)=(q−1)[q5/2(y5−2y4−2y3+y+2)+8q3/2(y4+y2)−2q2(y+1)(y2+1)2+16qy3−16q(y2+y+1)y2−32y3].\psi_q(y)=(\sqrt{q}-1)\left[q^{5/2}(y^5-2y^4-2y^3+y+2)+8q^{3/2}(y^4+y^2)-2q^2(y+1)(y^2+1)^2+16\sqrt{q}y^3-16q(y^2+y+1)y^2-32y^3\right].

We can see that because we are working in the domain where (y>1)(y>1) while qq grows the roots of this polynomial converge to the roots of (y−1)(y+1)(y3−2y2−y−2)(y-1)(y+1)(y^3-2y^2-y-2) and the unique root is

y0=13(2+(44−3177)1/3+(44+3177)1/3).y_0=\frac{1}{3}\left(2+(44-3\sqrt{177})^{1/3}+(44+3\sqrt{177})^{1/3}\right).

All the other roots are either out of our domain (y=−1,y=1)(y=-1,y=1) or they are complex. So for large values of qq, then Fq(t)F_q(t) will be minimized for

t≈t0=1+y02=3+13(459−12177)1/3+13(459+12177)1/3≈8.0701t\approx t_0=1+y_0^2=3+\frac{1}{3}(459-12\sqrt{177})^{1/3}+\frac{1}{3}(459+12\sqrt{177})^{1/3}\approx8.0701

so in that case someone should take either t=8t=8 or t=9t=9 now for large enough qq we have that: Fq(8)<Fq(9)F_q(8)<F_q(9) and so while qq tends to infinity, the optimal constant that this construction provides is

lim⁡q→∞Fq(8)=49(23+87)≈19.63\lim_{q\to\infty}F_q(8)=\frac{4}{9}(23+8\sqrt{7})\approx19.63

because in the fraction that appears in Fq(8)F_q(8) the leading qq terms cancel. In Table 1 we can see for smaller values of qq the computation of optimal choice of tt and the corresponding constant in the upper bound. Motivated by the previous analysis we are ready to prove Theorem Theorem 5.1.

qqargmin⁡Fq(t)\operatorname{argmin} F_q(t)Upper bound using fq(G)f_q(G)Upper bound using ι(G)\iota(G)
9t=73t=73264.63292.68
16t=33t=3396.02104.60
25t=23t=2362.6066.86
49t=17t=1742.1743.91
64t=15t=1537.8239.07
81t=14t=1434.8835.83
121t=13t=1331.1531.76
169t=12t=1228.8929.31
256≤q≤361256\le q\le361t=11t=1126.7927.06
529≤q≤1024529\le q\le1024t=10t=1024.3224.44
1369≤q≤118811369\le q\le11881t=9t=922.4222.46
q≥12769q\ge12769t=8t=820.5220.52

Table 1. For given ranges of square prime powers qq, this table provides the degrees tt that minimize the size of strong blocking sets obtained by Theorem 5.1 and upper bounds the normalized constant CC in front of kqkq on the corresponding sizes (third column) and in fourth column we provide the previous bound in the normalized constant CC that was obtained using the graph parameter of vertex integrity.

Proof. Let ε1=ε1(t,q)>0\varepsilon_1=\varepsilon_1(t,q)>0 be sufficiently small and we set λ=2t−1+ε1\lambda=2\sqrt{t-1}+\varepsilon_1. We have (q−1)−1<t−λ+2λ/qt+λ+2λ/q−2ε1(\sqrt{q}-1)^{-1}<\frac{t-\lambda+2\lambda/q}{t+\lambda+2\lambda/q}-2\varepsilon_1 and we set also R=t−λ+2λ/qt+λ+2λ/q−ε1−(q−1)−1R=\frac{t-\lambda+2\lambda/q}{t+\lambda+2\lambda/q}-\varepsilon_1-(\sqrt{q}-1)^{-1} and δ=1−R−(q−1)−1=1−t−λ+2λ/qt+λ+2λ/q+ε1\delta=1-R-(\sqrt{q}-1)^{-1}=1-\frac{t-\lambda+2\lambda/q}{t+\lambda+2\lambda/q}+\varepsilon_1.

Let {Ani,R}i∈N\{A_{n_i,R}\}_{i\in\mathbb{N}} be the (R,δ)q(R,\delta)_q-family of projective [ni,ki,di]q[n_i,k_i,d_i]_q systems. Theorem 2.11 shows that there exists some KK for which we obtain an explicit sequence {Gi}i>K\{G_i\}_{i>K} of (ni,t,λ)(n_i,t,\lambda)-graphs. By the spectral bound of Eq. (1) we have that

fq(Gni)≥ni(t−λ+2λ/qt+λ+2λ/q)≥ni(1−δ+ε1).f_q(G_{n_i})\ge n_i\left(\frac{t-\lambda+2\lambda/q}{t+\lambda+2\lambda/q}\right)\ge n_i(1-\delta+\varepsilon_1).

Since lim⁡i→∞dini=δ\lim_{i\to\infty}\frac{d_i}{n_i}=\delta, we have fq(Gni)≥ni−di+1f_q(G_{n_i})\ge n_i-d_i+1 for sufficiently large ii. Then from Corollary 4.2 B(Ani,R,Gni)\mathcal{B}(A_{n_i,R},G_{n_i}) is a strong blocking set in PG⁡(k−1,q)\operatorname{PG}(k-1,q). Since GniG_{n_i} has 12nit\frac{1}{2}n_it edges by the handshaking lemma, we have that

∣B(Ani,R,Gni)∣≤ni+(q−1)nit2<nit2q|\mathcal{B}(A_{n_i,R},G_{n_i})|\le n_i+(q-1)\frac{n_it}{2}<\frac{n_it}{2}q

Now, since the lim⁡i→∞kini=R\lim_{i\to\infty}\frac{k_i}{n_i}=R, there exists some ε1>0\varepsilon_1>0 such that kini≥R−ε1⟹niki≤1R−ε1⟹ni≤kiR−ε1\frac{k_i}{n_i}\ge R-\varepsilon_1\Longrightarrow\frac{n_i}{k_i}\le\frac{1}{R-\varepsilon_1}\Longrightarrow n_i\le\frac{k_i}{R-\varepsilon_1} for sufficiently large ii. After we make the substitution, and recall our choice of R=t−λ+2λqt+λ+2λq−ε1−(q−1)−1R=\frac{t-\lambda+\frac{2\lambda}{q}}{t+\lambda+\frac{2\lambda}{q}}-\varepsilon_1-(\sqrt{q}-1)^{-1} so the upper bound becomes.

nit2q≤t2(R−ε1)kiq=t(t+λ+2λq)(q−1)2(t−λ+2λq)(q−1)−2(t+λ+2λq)−4ε1(t+λ+2λq)(q−1)kiq\frac{n_i t}{2}q\le\frac{t}{2(R-\varepsilon_1)}k_iq=\frac{t(t+\lambda+\frac{2\lambda}{q})(\sqrt{q}-1)}{2(t-\lambda+\frac{2\lambda}{q})(\sqrt{q}-1)-2(t+\lambda+\frac{2\lambda}{q})-4\varepsilon_1(t+\lambda+\frac{2\lambda}{q})(\sqrt{q}-1)}k_iq

If we choose now ε1\varepsilon_1 to be sufficiently small, we obtain the upper bound to be:

∣B(Ani,R,Gni)∣≤(t(t+λ+2λq)(q−1)2((t−λ+2λq)(q−1)−(t+λ+2λq))+ε2)kiq|\mathcal{B}(\mathcal{A}_{n_i,R},G_{n_i})|\le\left(\frac{t(t+\lambda+\frac{2\lambda}{q})(\sqrt{q}-1)}{2((t-\lambda+\frac{2\lambda}{q})(\sqrt{q}-1)-(t+\lambda+\frac{2\lambda}{q}))}+\frac{\varepsilon}{2}\right)k_iq

and if we recall that λ=2t−1+ε1\lambda=2\sqrt{t-1}+\varepsilon_1 we get

t(t+λ+2λq)(q−1)2((t−λ+2λq)(q−1)−(t+λ+2λq))=\frac{t(t+\lambda+\frac{2\lambda}{q})(\sqrt{q}-1)}{2((t-\lambda+\frac{2\lambda}{q})(\sqrt{q}-1)-(t+\lambda+\frac{2\lambda}{q}))}=
t(t+2t−1+4t−1q)(q−1)+ε1t((q−1)+q−1q)2(t(q−2)−2q(t−1)−ε1q+4q(q(t−1)+2ε1q−2t−1−ε1))\frac{t(t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q})(\sqrt{q}-1)+\varepsilon_1t\left((\sqrt{q}-1)+\frac{\sqrt{q}-1}{q}\right)}{2\left(t(\sqrt{q}-2)-2\sqrt{q(t-1)}-\varepsilon_1\sqrt{q}+\frac{4}{q}\left(\sqrt{q(t-1)}+2\varepsilon_1\sqrt{q}-2\sqrt{t-1}-\varepsilon_1\right)\right)}

and the result follows provided that ε1\varepsilon_1 is sufficiently small.

General construction via field reduction

We extend the construction to arbitrary prime powers by using the field reduction method from [1] and [4]. The field reduction map, denoted by Fq,r\mathcal{F}_{q,r}, sends the points of PG⁡(K−1,qr)\operatorname{PG}(K-1,q^{r}) to rr-dimensional Fq\mathbb{F}_{q}-subspaces of FqK\mathbb{F}_{q}^{K} (see [29]). For a set L\mathcal{L} of lines in PG⁡(k−1,q2)\operatorname{PG}(k-1,q^{2}) we select a so-called viable set [4], denoted by Λ\Lambda that consist of four points on each line of L\mathcal{L} that are not contained in any Fq\mathbb{F}_{q}-subline. It was shown in [3, 4] that if the union of a set L\mathcal{L} of lines in PG⁡(K−1,q2)\operatorname{PG}(K-1,q^{2}) is a strong blocking set, then Fq,2(Λ)\mathcal{F}_{q,2}(\Lambda) is a strong blocking set in PG⁡(2K−1,q)\operatorname{PG}(2K-1,q). This gives us the following result.

Theorem 5.2. Let t≥3t \ge3, and let q>2q > 2 be such that

(q−1)−1<t−2t−1+4t−1q2t+2t−1+4t−1q2.(q-1)^{-1}<\frac{t-2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q^{2}}}{t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q^{2}}}.

For every ε>0\varepsilon> 0, there is a strictly increasing sequence of dimensions {ki}i∈N\{k_i\}_{i\in\mathbb{N}} for which we can explicitly construct strong blocking sets in PG⁡(ki−1,q)\operatorname{PG}(k_i-1,q) of size at most

((t+1)(t+2t−1+4t−1q2)(q−1)2(t(q−2)−2qt−1+4(qt−1−2t−1)q2)+ε)ki(q+1)\left(\frac{(t+1)(t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q^{2}})(q-1)}{2\left(t(q-2)-2q\sqrt{t-1}+\frac{4(q\sqrt{t-1}-2\sqrt{t-1})}{q^{2}}\right)}+\varepsilon\right)k_i(q+1)

Proof. Let ε1=ε1(t,q,λ)>0\varepsilon_1=\varepsilon_1(t,q,\lambda)>0 be sufficiently small and we set λ=2t−1+ε1\lambda=2\sqrt{t-1}+\varepsilon_1. We have (q−1)−1<t−λ+2λq2t+λ+2λq2−2ε1(q-1)^{-1}<\frac{t-\lambda+\frac{2\lambda}{q^{2}}}{t+\lambda+\frac{2\lambda}{q^{2}}}-2\varepsilon_1 and we set also R=t−λ+2λq2t+λ+2λq2−ε1−(q−1)−1R=\frac{t-\lambda+\frac{2\lambda}{q^{2}}}{t+\lambda+\frac{2\lambda}{q^{2}}}-\varepsilon_1-(q-1)^{-1} and δ=1−R−(q−1)−1=1−t−λ+2λq2t+λ+2λq2+ε1\delta=1-R-(q-1)^{-1}=1-\frac{t-\lambda+\frac{2\lambda}{q^{2}}}{t+\lambda+\frac{2\lambda}{q^{2}}}+\varepsilon_1. When we consider some {Ani,R}i∈N\{\mathcal{A}_{n_i,R}\}_{i\in\mathbb{N}} to be an (R,δ)q2(R,\delta)_{q^{2}}-family of projective [ni,Ki,di]q2[n_i,K_i,d_i]_{q^{2}} systems, and {Gi}i>K\{G_i\}_{i>K} to be a sequence of (ni,t,λ)(n_i,t,\lambda) graphs. If we take ii to be sufficiently large then we have that fq2(G)≥ni−di+1f_{q^{2}}(G)\ge n_i-d_i+1. We conclude that L=L(Ani,R,G)\mathcal{L}=\mathcal{L}(\mathcal{A}_{n_i,R},G) has the avoidance property in PG⁡(K−1,q2)\operatorname{PG}(K-1,q^{2}). Therefore, by Theorem 2.7, the union B(Ani,R,G)\mathcal{B}(\mathcal{A}_{n_i,R},G) of those lines forms a strong blocking set. Then by [4 Lemma 5.5], we can find a viable set Λ\Lambda for L\mathcal{L} that has size at most ∣Ani,R∣+2e(Gni)=ni(t+1)|\mathcal{A}_{n_i,R}|+2e(G_{n_i})=n_i(t+1). The set Fq,2(Λ)\mathcal{F}_{q,2}(\Lambda) gives a strong blocking set in PG⁡(2Ki−1,q)\operatorname{PG}(2K_i-1,q). Because each line in PG⁡(2Ki−1,q)\operatorname{PG}(2K_i-1,q) has q+1q+1 points, this strong blocking set has size at most ni(t+1)(q+1)n_i(t+1)(q+1). We know as well that R=lim⁡i→∞KiniR=\lim_{i\to\infty}\frac{K_i}{n_i}, and recalling our choices for the parameters RR and λ\lambda and setting ki=2Kik_i=2K_i then gives the result.

We again determine the optimal degree tt to use by minimizing the following quantity:

Mq(t):=(t+1)(t+2t−1+4t−1q2)(q−1)2(t(q−2)−2qt−1+4(qt−1−2t−1)q2).M_q(t):=\frac{(t+1)(t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q^{2}})(q-1)}{2\left(t(q-2)-2q\sqrt{t-1}+\frac{4(q\sqrt{t-1}-2\sqrt{t-1})}{q^{2}}\right)}.

The optimum corresponds to t0≈9.0967t_0\approx9.0967. The asymptotically optimal degree must then be t=9t=9 or t=10t=10, and after some inspection in the values we have that Mq(10)>Mq(9)→549(113+722)≈21.92M_q(10)>M_q(9)\to\frac{5}{49}(113+72\sqrt{2})\approx21.92 while q→∞q\to\infty.

Note that the process of derivation can be repeated by using maps Fq,2h\mathcal{F}_{q,2^h} for h≥2h\ge2 as well. This leads to a construction of strong blocking sets in PG⁡(ki−1,q)\operatorname{PG}(k_i-1,q) of size at most

(2r−2(t+1)(t+2t−1+4t−1q2)(q2r−1−1)t(q2r−1−2)−2q2r−1t−1+4(q2r−1t−1−2t−1)q2r+ε)ki(q+1)\left(\frac{2^{r-2}(t+1)(t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q^{2}})(q^{2^{r-1}}-1)}{t(q^{2^{r-1}}-2)-2q^{2^{r-1}}\sqrt{t-1}+\frac{4(q^{2^{r-1}}\sqrt{t-1}-2\sqrt{t-1})}{q^{2^{r}}}}+\varepsilon\right)k_i(q+1)

for some increasing sequence {ki}i∈N\{k_i\}_{i\in\mathbb{N}} provided that (q2r−1−1)−1<t−2t−1+4t−1q2rt+2t−1+4t−1q2r(q^{2^{r-1}}-1)^{-1}<\frac{t-2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q^{2r}}}{t+2\sqrt{t-1}+\frac{4\sqrt{t-1}}{q^{2r}}}.

We summarize all the results of our optimizations in Table 2, where we give the size of the smallest strong blocking sets obtained from this explicit construction.

Conclusion

We introduced a new graph parameter that incorporates the size of the finite field and used it to give improved explicit constructions of strong blocking sets. Specifically, we provide a lower bound on this new graph parameter for the family of tt–regular graphs that depends on both the eigenvalues of the adjacency matrix and the size of the finite filed Fq\mathbb{F}_q, this deviating from the earlier work [4] that relied on a graph parameter which was independent of the field size.

In a recent preprint, Chen [15] has improved the explicit construction of strong blocking sets in PG(k−1,q)\mathrm{PG}(k-1,q) for all 4≤q≤114\leq q\leq11 using concatenation of codes. For q=2q=2 the best construction is described in [14] which gives a strong blocking set of size roughly 5.83k5.83k in PG(k−1,2)\mathrm{PG}(k-1,2). For q=3q=3 the best construction can be obtained by using the trifferent code of length 24 and dimension 3 as described in [11], which gives an explicit strong blocking set of size roughly 13.56k13.56k in PG(k−1,3)\mathrm{PG}(k-1,3). For q≥13q \ge13, however, the strong blocking sets from Theorem 5.2 and Theorem 5.1 are smaller than those described in [15] and all previous constructions [10, 16, 15, 4].

Several directions for future work remain. Firstly, it would be nice to find a graph theoretic construction of strong blocking sets that does not require the stronger line avoidance property. Such a construction might involve a new graph parameter that further optimizes the constant and leads to a smaller explicit constructions of strong blocking sets. Second, motivated by [12], it would be interesting to extend our constructions based on the new graph parameter to strong blocking sets with respect to codimension–2 spaces. Specifically, we would like to define and analyze similar parameter for 3–uniform hypergraphs which could improve the bounds from [12]. Finally, one can try generalizing our constructions to strong ss-blocking sets in other ways. It would be interesting to match, or improve, the recent bounds of Guo et al. [20] using these graph-theoretic techniques on strong ss-blocking sets.

Acknowledgments

The work of the first author has been supported by the Dutch Research Council (NWO) through the NWO Talent Programme Vidi project “Extremal problems in finite geometry” (project number VI.Vidi.243.039).

The work of the second author has been partially supported by the MEYS of the Czech Republic under the INTER-EXCELLENCE II program (project No. LUAUS26294), the European Union under the project Robotics and advanced industrial production (reg. no. CZ.02.01.01/00/22_008/0004590) and also supported by the Grant Agency of the Czech Technical University in Prague, grant No.SGS26/181/OHK3/3T/18. The research visit of the second author to TU Delft was supported by the Vidi grant of the first author.

Statement on software use

The authors did not use generative AI to produce any mathematical proofs or writing. WolframAlpha was used for finding minima for large values of qq in Table 1 and for searching for optimal values of rr in Table 2. Google search, that often included AI-generated overviews, was used to explore relevant literature and to obtain citation information.

References

  1. [1]G. N. Alfarano, M. Borello, and A. Neri. “A geometric characterization of minimal codes and their asymptotic performance”. In: Advances in Mathematics of Communications 16.1 (2022), pp. 115–133.
  2. [2]G. N. Alfarano, M. Borello, and A. Neri. “Outer strong blocking sets”. In: The Electronic Journal of Combinatorics 31.2 (2024), P2.18.arxiv.org/abs/2301.09590
  3. [3]G. N. Alfarano, M. Borello, A. Neri, and A. Ravagnani. “Three combinatorial perspectives on minimal codes”. In: SIAM Journal on Discrete Mathematics 36.1 (2022), pp. 461–489.arxiv.org/abs/2010.16339
  4. [4]N. Alon, A. Bishnoi, S. Das, and A. Neri. “Strong blocking sets and minimal codes from expander graphs”. In: Transactions of the American Mathematical Society 377.8 (2024), pp. 5389–5410.arxiv.org/abs/2305.15297
  5. [5]N. Alon and F. K. Chung. “Explicit construction of linear sized tolerant networks”. In: Discrete Mathematics 72.1–3 (1988), pp. 15–19.
  6. [6]Noga Alon. “Explicit expanders of every degree and size”. In: Combinatorica 41.4 (2021), pp. 447–463.arxiv.org/abs/2003.11673
  7. [7]A. Ashikhmin and A. Barg. “Minimal vectors in linear codes”. In: IEEE Transactions on Information Theory 44.5 (1998), pp. 2010–2017.DOI
  8. [8]K. S. Bagga, L. W. Beineke, W. D. Goddard, M. J. Lipman, and R. E. Pippert. “A survey of integrity”. In: Discrete Applied Mathematics 37–38 (1992), pp. 13–28.DOI
  9. [9]D. Bartoli, A. Cossidente, G. Marino, and F. Pavese. “On cutting blocking sets and their codes”. In: Forum Mathematicum 34.2 (2022), pp. 347–368.arxiv.org/abs/2011.11101
  10. [10]Daniele Bartoli and Martino Borello. “Small strong blocking sets by concatenation”. In: SIAM Journal on Discrete Mathematics 37.1 (2023), pp. 65–82.arxiv.org/abs/2109.00584
  11. [11]A. Bishnoi, J. D’haeseleer, D. Gijswijt, and A. Potukuchi. “Blocking sets, minimal codes and trifferent codes”. In: Journal of the London Mathematical Society 109.6 (2024), e12938.arxiv.org/abs/2301.09457
  12. [12]A. Bishnoi and István Tomon. “Explicit constructions of optimal blocking sets and minimal codes”. In: Combinatorica 46.2 (2026), p. 13.DOI
  13. [13]M. Bonini and M. Borello. “Minimal linear codes arising from blocking sets”. In: Journal of Algebraic Combinatorics 53 (2021), pp. 327–341.arxiv.org/abs/1907.04626
  14. [14]M. Borello, W. Schmid, and M. Scotti. “The geometry of intersecting codes and applications to additive combinatorics and factorization theory”. In: Journal of Combinatorial Theory, Series A 214 (2025), p. 106023.arxiv.org/abs/2406.04034
  15. [15]H. Chen. A simple explicit construction of smaller strong blocking sets. 2026. arXiv: 2610.12819 [math.CO].arxiv.org/abs/2610.12819
  16. [16]G. Cohen, S. Mesnager, and H. Randriam. “Yet another variation on minimal linear codes”. In: Advances in Mathematics of Communications 10.1 (2016), pp. 53–61.
  17. [17]A. Couvreur and H. Randriambololona. “Algebraic geometry codes and some applications”. In: Concise Encyclopedia of Coding Theory. Ed. by W. C. Huffman, J.-L. Kim, and P. Solé. Chapman and Hall/CRC, 2021, pp. 307–362.arxiv.org/abs/2009.01281
  18. [18]A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco. “Linear nonbinary covering codes and saturating sets in projective spaces”. In: Advances in Mathematics of Communications 5.1 (2011), pp. 119–147.arxiv.org/abs/0904.3835
  19. [19]S. Fancsali and P. Sziklai. “Lines in higgledy-piggledy arrangement”. In: The Electronic Journal of Combinatorics 21.2 (2014), P2.56.DOI
  20. [20]Z. Guo, R. Raj, C. Shangguan, and Z. Zhang. “Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets”. In: arXiv preprint arXiv:2604.13431 (2026).arxiv.org/abs/2604.13431
  21. [21]V. Guruswami and P. Indyk. “Expander-based constructions of efficiently decodable codes”. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE. 2001, pp. 658–667.DOI
  22. [22]V. Guruswami, A. Rudra, and M. Sudan. Essential coding theory. Draft. 2022. URL: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/.
  23. [23]W. H. Haemers. “Eigenvalue Techniques in Design and Graph Theory”. PhD thesis. Eindhoven University of Technology, 1979.DOI
  24. [24]T. Héger and Z. L. Nagy. “Short minimal codes and covering codes via strong blocking sets in projective spaces”. In: IEEE Transactions on Information Theory 68.2 (2022), pp. 881–890.arxiv.org/abs/2103.07393
  25. [25]T. Héger, B. Patkós, and M. Takáts. “Search problems in vector spaces”. In: Designs, Codes and Cryptography 76.2 (2015), pp. 207–216.DOI
  26. [26]Z. Heng, C. Ding, and Z. Zhou. “Minimal linear codes over finite fields”. In: Finite Fields and Their Applications 54 (2018), pp. 176–196.arxiv.org/abs/1803.09988
  27. [27]S. Hoory, N. Linial, and A. Wigderson. “Expander graphs and their applications”. In: Bulletin of the American Mathematical Society 43.4 (2006), pp. 439–561.DOI
  28. [28]J. Justesen. “Class of constructive asymptotically good algebraic codes”. In: IEEE Transactions on Information Theory 18.5 (1972), pp. 652–656.DOI
  29. [29]M. Lavrauw and G. Van de Voorde. “Field reduction and linear sets in finite geometry”. In: Topics in Finite Fields. Ed. by G. Kyureghyan, G. L. Mullen, and A. Pott. Vol. 632. Contemporary Mathematics. American Mathematical Society, 2015, pp. 271–293.arxiv.org/abs/1310.8522
  30. [30]S. Lia and G. Van de Voorde. “A note on strong blocking sets and higgledy-piggledy sets of lines”. In: The Electronic Journal of Combinatorics 32.3 (2025), P3.27.arxiv.org/abs/2402.06939
  31. [31]J. H. van Lint. Introduction to Coding Theory. Vol. 86. Graduate Texts in Mathematics. Berlin, Heidelberg: Springer-Verlag, 1982.
  32. [32]A. Lubotzky, R. Phillips, and P. Sarnak. “Ramanujan graphs”. In: Combinatorica 8.3 (1988), pp. 261–277.
  33. [33]G. A. Margulis. “Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators”. In: Problemy Peredachi Informatsii 24.1 (1988), pp. 51–60.
  34. [34]J. L. Massey. “Minimal codewords and secret sharing”. In: Proceedings of the 6th joint Swedish-Russian international workshop on information theory. 1993, pp. 276–279.
  35. [35]S. Mesnager and A. Sinak. “Several classes of minimal linear codes with few weights from weakly regular plateaued functions”. In: IEEE Transactions on Information Theory 66.4 (2019), pp. 2296–2310.arxiv.org/abs/1808.03877
  36. [36]D Miklós. “Linear binary codes with intersection properties”. In: Discrete Applied Mathematics 9.2 (1984), pp. 187–196.DOI
  37. [37]A. Nilli. “On the second eigenvalue of a graph”. In: Discrete Mathematics 91.2 (1991), pp. 207–210.DOI
  38. [38]Martin Scotti. “On the lower bound for the length of minimal codes”. In: Discrete Mathematics 347.1 (2024), p. 113676.arxiv.org/abs/2302.05350
  39. [39]C. Tang, Y. Qiu, Q. Liao, and Z. Zhou. “Full characterization of minimal linear codes as cutting blocking sets”. In: IEEE Transactions on Information Theory 67.6 (2021), pp. 3690–3700.arxiv.org/abs/1911.09867
  40. [40]M. A. Tsfasman and S. G. Vlădut. Algebraic-geometric codes. Vol. 58. Springer Science & Business Media, 2013.
  41. [41]M. A. Tsfasman, S. G. Vlădut, and T. Zink. “Modular curves, Shimura curves, and Goppa codes, better than the Varshamov–Gilbert bound”. In: Mathematische Nachrichten 109.1 (1982), pp. 21–28.DOI

Paper details

vlnc:W_b786y3jq
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents