Simpler construction improves small strong blocking sets in projective space
A Simple Explicit Construction of Smaller Strong Blocking Sets
Information Theory
Summary
The paper addresses a problem about constructing special mathematical objects called strong blocking sets, which relate to codes used in data transmission. Previous work made big progress but was complicated and less efficient for smaller cases. The authors present a simpler way that works better for smaller numbers, making certain minimal codes shorter and easier to build. Their method avoids complex tools like expander graphs, making it more accessible even though it is less effective for large numbers.
What this means in practice
- •For coding theory engineers: Construct explicit minimal codes with shorter lengths for smaller finite fields improving code design simplicity.
- •For error correction developers: Design reliable communication codes with positive rate using simpler strong blocking sets in smaller field sizes.
Authors
Hao Chen
Abstract
Alon, Bishnoi, Das and Neri constructed sequences of strong blocking sets in $(k-1)$-dimension projective space $P({\bf F}_q, k-1)$ with sizes at most $Cqk$, where $k$ goes to the infinity and $C$ is a fixed positive constant not depending on $q$, in their paper published in Transactions AMS, vol. 277, pp. 5389-5410, 2024. This is equivalent to a sequence of minimal $[n_i,k_i]_q$ codes with positive rate $\frac{k_i}{n_i} \geq c$, where $k_i$ goes to the infinity and $c$ is a fixed positive constant only depending on $q$. They solved one of the main open problems on minimal codes. The Alon-Bishnoi-Das-Neri construction was based on asymptotically good sequences of algebraic geometric codes and expander graphs. However, the constant $C$ is large for small prime power $q$. In this paper, based on a simple approach using $(q-1)$-power intersecting algebraic geometric codes via concatenation to construct minimal codes, we construct explicit strong blocking sets in $(k-1)$-dimension projective space with sizes around $2(q^2-1)k$, equivalently, explicit minimal $[n,k]_q$ codes with length around $2(q^2-1)k$. This is an essential improvement on the previous result of Alon-Bishnoi-Das-Neri, when $q \leq 11$. For large $q$, strong blocking sets and minimal codes in our construction are worse than the previous construction of Alon-Bishnoi-Das-Neri. However, our approach is much simpler and does not depend on expander graphs.