Coding Theory and Galois Geometries
SIAM Conference on Applied Algebraic Geometry (AG23) - Minisymposium
10-14 July 2023, Eindhoven, the Netherlands
Aims and Scope
The minisymposium will focus on the interactions between algebraic coding theory and finite geometry. These two research areas developed together, each of them playing a crucial role in the advancement of the other. Renowned examples are given by the non-existence of the projective plane of order 10, which was shown using the theory of error-correcting codes, and the celebrated MDS conjecture, proved to be true over prime fields by means of geometric tools.
As a matter of fact, the interactions between these two areas have increased in recent years and the relative problems have been described in both coding theory and finite geometry. Concretely, speakers of this minisymposium will present recent developments on algebraic and geometric methods used in coding theory and finite geometry, the study of special linear codes together with their dual geometric counterparts, and the problem of designing error-correcting codes with certain properties via incidence and geometric structures.
The aim of this minisymposium is to bring together leading experts in the fields of coding theory and Galois geometries in order to present contemporary research directions on these topics. All levels of seniority are represented, from early-stage to more experienced researchers.
Speakers
Gianira Alfarano – Eindhoven University of Technology (the Netherlands)
Minimal Codes and Strong Blocking Sets
A linear code is said to be minimal if the support of each of its codewords does not contain the support of any other independent codeword, namely, all its codewords are minimal. The study of minimal codewords arises from their applications to secret sharing schemes and to decoding strategies. They have recently been shown to correspond to strong blocking sets which are sets of projective points, such that their intersection with each hyperplane generates the hyperplane itself.
In this talk we introduce the concepts of outer minimal codes and outer strong blocking sets. These are codes whose concatenation with minimal codes is minimal and sets whose field reduction is a strong blocking set. We investigate their structure and provide bounds on their length/size. We discuss an improvement on the best-known upper bound on the minimum size of a strong blocking set. Finally, we present a geometric construction of small strong blocking sets, with low computational cost.
This is a joint work with Martino Borello and Alessandro Neri.
Jessica Bariffi - German Aerospace Center (DLR) (Germany)
Constructing Moderate-Density Parity-Check Codes from Projective Bundles
Moderate-Density Parity-Check (MDPC) codes were introduced as an extension of low-density parity-check (LDPC) codes and are of high interest in cryptographic applications. In this talk we present a new construction of a family of MDPC codes using projective bundles in a Desarguesian projective plane. In a projective plane of order q such a bundle consists of q2+q+1 ovals that are mutually intersecting in a unique point. We define a parity check matrix as the incidence matrix between the points of a projective plane and the lines together with the ovals of a projective bundle. Furthermore, we completely determine their dimension and minimum distance for both q even and odd. In addition, we observe that we can design these codes to possess a quasi-cyclic structure of index 2.
Luca Bastioni - University of South Florida (US)
On Complete m-Arcs from Algebraic Curves
Let m and k be two positive integers and q be an odd prime power. Let PG(2,q) be the set of 𝔽q-points of the projective plane. A (k,m)-arc A in PG(2,q) is a set of k points such that there are no m+1 points that are collinear but there exist m collinear points. For fixed m,q, we have that the set Am(q) of all m-arcs in PG(2,q) is partially ordered by inclusion. A complete m-arc is a maximal element in Am(q) , i.e. it is an m-arc that is not contained in a strictly larger m-arc. The purpose of this talk is to provide a general theory to construct families of complete m-arcs arising from curves that satisfy explicit and generic geometric conditions.
This is a joint work with Giacomo Micheli.
Anurag Bishnoi - Delft University of Technology (the Netherlands)
Blocking Sets, Minimal Codes and Trifferent Codes
We prove new upper bounds on the smallest size of affine blocking sets, that is, sets of points in a finite affine space that intersect every affine subspace of a fixed codimension. We show an equivalence between affine blocking sets with respect to codimension-2 subspaces that are generated by taking a union of lines through the origin, and strong blocking sets in the corresponding projective space, which in turn are equivalent to minimal codes. Using this equivalence, we improve the current best upper bounds on the smallest size of a strong blocking set in finite projective spaces over fields of size at least 3. Furthermore, using coding theoretic techniques, we improve the current best lower bounds on strong blocking set. Over the finite field 𝔽3 , we prove that minimal codes are equivalent to linear trifferent codes. Using this equivalence, we show that any linear trifferent code of length n has size at most 3^n/4.55, improving the recent upper bound of Pohoata and Zakharov. Moreover, we show the existence of linear trifferent codes of length n and size at least 1/3(9/5)^(n/4), thus matching the best lower bound on trifferent codes. We also give explicit constructions of affine blocking sets with respect to codimension-2 subspaces that are a constant factor bigger than the best-known lower bound. By restricting to 𝔽3, we obtain trifferent codes of size at least 3^(n/48).
Matteo Bonini - Aalborg University (Denmark)
Saturating Systems and Covering Radius in the (sum-)rank Metric
The relationship between linear codes and sets of points in finite geometries have long been exploited by researchers, in fact it is a standard approach to construct generator matrices or parity check matrix of a linear code from a set of projective points. In this context, the supports of the codewords correspond to complements of hyperplanes in a fixed projective set, and this can be used to construct codes with bounded covering radius, related to saturating sets in projective space. The covering radius of a code is the least positive integer ρ such that the union of the spheres of radius ρ about each codeword equals the full ambient space. This fundamental coding theoretical parameter has been widely studied for codes in respect of the Hamming-metric. In this talk, we introduce the notion of saturating systems and their properties. In analogy with codes for the Hamming-metric, it turns out that a rank ρ-saturating system corresponds to a linear code of rank-metric covering radius ρ. Such codes have the property that every element of the ambient space is within rank-distance at most ρ of some codeword. Finally, we will also show how this approach can be also extended to the sum-rank metric.
Martino Borello - University of Paris 8 (France)
Geometric Dual and Sum-Rank Minimal Codes
In this talk we will present some results about minimal codes in the sum-rank metric. These objects, introduced in [4], form a bridge between the classical minimal codes in the Hamming metric, the subject of intense research over the past three decades partly because of their cryptographic properties [2], and the more recent rank-metric minimal codes [1]. They have rich connections with geometry, as shown in [1,3,4] and references therein. We will illustrate these connections, together with some bounds on their parameters and some existence results. Via a tool that we name geometric dual, we manage to construct minimal codes with few weights. A generalization of the celebrated Ashikhmin-Barg condition is proved and used to ensure minimality of certain constructions.
This is a joint work with Ferdinando Zullo.
[1] G. N. Alfarano, M. Borello, A. Neri, and A. Ravagnani. Linear cutting blocking sets and minimal codes in the rank metric. Journal of Combinatorial Theory, Series A, 192:105658, 2022.
[2] J. L. Massey. Minimal codewords and secret sharing. In Proceedings of the 6th joint Swedish-Russian international workshop on information theory, pages 276–279, 1993.
[3] A. Neri, P. Santonastaso, and F. Zullo. The geometry of one-weight codes in the sum-rank metric. Journal of Combinatorial Theory, Series A, 194:105703, 2023.
[4] P. Santonastaso and F. Zullo. On subspace designs. arXiv:2204.13069, 2022.
Jozefien D'haeseleer - Ghent University (Belgium)
On the Sunflower Bound for k-spaces Pairwise Intersecting in a Point
Let PG(n,q) be the projective space of dimension n over the finite field of order q. We look at families of k-spaces that pairwise intersect in exactly a t-space. These families can also be described within the context of subspace codes. We refer to them as t-intersecting constant dimension codes, or abbreviated SCID's. The classical example of a t-intersecting constant dimension code is the set of k-spaces pairwise intersecting in a fixed t-space α, which is called a sunflower through α. Within the theory on t-intersecting constant dimension codes, it is a known result that large t-intersecting constant dimension codes are equal to sunflowers. More precisely, the following result is known. Let C be a t-intersecting constant dimension code of k-spaces in PG(n,q), where
|C|>(qk+1−qt+1q−1)2+(qk+1−qt+1q−1)+1,
then C is a sunflower. This lower bound is called the sunflower bound and it is generally believed that the lower bound of the preceding theorem is too large. This motivates the research to improve this lower bound. In this talk, I will present an improvement on the sunflower bound for k-spaces, pairwise intersecting in a projective point.
This is a joint work with Aart Blokhuis and Maarten De Boeck.
Francesco Ghiandoni - University of Perugia (Italy)
Rational Almost Perfect Nonlinear Functions
Almost perfect nonlinear (APN) functions, and the exceptional ones in particular, have been also investigated in connection with algebraic varieties over finite fields, whose degree strictly depends on the the degree of the corresponding polynomial. In this direction, non-existence results were obtained by means of estimates on the number of 𝔽q-rational points of such varieties, as Hasse-Weil or Lang-Weil bounds, which can be applied only if the degree of the polynomial under investigation is small enough. On the one hand, using such a machinery non-existence results were obtained only in small-degree regime or of so-called exceptional APN functions. On the other hand, not all the examples of APN functions are described in the literature by polynomials. In fact, the inverse map x↦x^(−1) is known to be APN on 𝔽2n with n odd, and thus it is also exceptional. Such a map, seen as a polynomial function, has large degree (the function coincides with x^(2^n−2) and thus the previous machinery does not apply. Inspired by this example, we start the investigation of APN functions which can be represented as rational functions and we provide non-existence results exploiting the connection between these functions and specific algebraic varieties over finite fields. This approach allows to classify families of functions when previous approaches cannot be applied.
Hiram Lopez - Cleveland State University (US)
Relative Hulls and Quantum Codes
The relative hull of a code C1 with respect to another code C2 is the intersection C1∩C2^⊥ . We prove that the dimension of the relative hull can always be repeatedly reduced by one by replacing any of the two codes with an equivalent one. Specifically, we show how to construct an equivalent code C′1 of C1 such that the dimension of C′1∩C2^⊥ is one less than the dimension of C1∩C2^⊥ . These results apply to hulls taken with respect to the e-Galois inner product, which has as special cases both the Euclidean and Hermitian inner products. We study the consequences of the relative hull properties on quantum codes constructed via CSS construction.
This is joint work with S. Anderson (University of St. Thomas), E. Camps-Moreno (National Polytechnic Institute of Mexico), G. Matthews (Virginia Tech), D. Ruano (Universidad de Valladolid), and I. Soprunov (Cleveland State University).
Emily McMillon - Rice University (US)
Spatially Coupled LDPC Codes from Finite Geometries
Spatially coupled LDPC (SC-LDPC) codes are graph-based codes notable for their decoding threshold and performance. Their construction may be viewed in several ways, including replicating a small Tanner graph for a code and “spreading edges” so that the copies interact, or via algebraic graph lifts. In this talk, we provide some general distance bounds of SC-LDPC codes given properties of their base Tanner graph and provide explicit constructions of SC-LDPC codes based on finite geometries.
Martin Scotti - University of Paris 8 (France)
On the Lower Bound for the Length of Minimal Codes
In recent years, many connections have been made between minimal codes, a classical object in coding theory, and other remarkable structures in finite geometry and combinatorics. One of the main problem related to minimal codes is to give lower and upper bounds on the length m(k,q) of the shortest minimal codes of a given dimension k over the finite field 𝔽q. It is known that m(k,q)≥(q+1)(k−1).
In this note, we prove that liminf k→∞ m(k,q) ≥q+ 3/2, so that the previous lower bound is not tight for large enough k. We then focus on the binary case and prove some structural results on minimal codes of length 3(k−1). As a byproduct, we are able to show that, if k=5(mod8), the bound is never tight.
Giovanni Zini - University of Modena and Reggio Emilia (Italy)
Intertwined Results in Finite Geometry and Coding Theory
It has been known for many decades that finite geometry and coding theory are related areas, and many results can be equivalently stated in the two languages; for instance, the MDS conjecture for linear codes can be described in terms of arcs in a finite projective space. The relation between finite geometry and coding theory is not just a matter of language: geometric tools have been applied in coding theory, and coding-theoretic methods have played a role in geometric problems. Recently, many researchers have pushed forward with this relation in several directions: for instance, regarding new metrics for error-correcting codes; or the construction of quantum codes from classical ones; or the application of more refined algebraic methods. The talks of the minisymposium give evidence of the recent developments in many directions, and this talk will give an overview of some old and new results in the intertwined areas of finite geometry and coding theory.
Schedule
Wednsday (July 12 2023) - First Session
10:30 Giovanni Zini
11:00 Jessica Bariffi
11:30 Hiram Lopez
12:00 Francesco Ghiandoni
Wednsday (July 12 2023) - Second Session
2:00 Gianira Alfarano
2:30 Anurag Bishnoi
3:00 Martino Borello
3:30 Matteo Bonini
Thursday (July 13 2023) - Third Session
10:30 Martin Scotti
11:00 Luca Bastioni
11:30 Emily McMillon
12:00 Jozefien D'haeseleer
Organizers
Ghent University (Ghent, Belgium)
alessandro.neri@ugent.be
Università degli Studi della Campania "Luigi Vanvitelli" (Caserta, Italy)
ferdinando.zullo@unicampania.it