Mathematicians crack optimal code construction problem with real-world applications
Researchers have solved a decades-old mathematical puzzle about constructing optimal blocking sets—a fundamental problem in coding theory used in error correction, data storage, and quantum computing. The explicit construction method scales efficiently and could improve the performance of systems that protect data from corruption during transmission or storage.
Originaltitel: Explicit Constructions of Optimal Blocking Sets and Minimal Codes
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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -dimensional projective space over $$\mathbb {F}_q$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:math> of size $$O_s(q^s k)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>O</mml:mi> <mml:mi>s</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>q</mml:mi> <mml:mi>s</mml:mi> </mml:msup> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>F</mml:mi> <mml:mi>q</mml:mi> <mml:mi>k</mml:mi> </mml:msubsup> </mml:math> with respect to codimension- $$(s+1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>s</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> 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.