Gianira N Alfarano

Martino Borello

Alessandro Neri

Alberto Ravagnani

Three Combinatorial Perspectives on Minimal Codes

We develop three approaches of combinatorial flavour to study the structure of minimal codes and cutting blocking sets in finite geometry, each of which has a particular application. The first approach uses techniques from algebraic combinatorics, describing the supports in a linear code via the Alon-Füredi Theorem and the Combinatorial Nullstellensatz. The second approach combines methods from coding theory and statistics to compare the mean and variance of the nonzero weights in a minimal code. Finally, the third approach regards minimal codes as cutting blocking sets and studies these using the theory of spreads in finite geometry. Applying and combining these approaches with each other, we derive several new bounds and constraints on the parameters of minimal codes. Moreover, we obtain two new constructions of cutting blocking sets of small cardinality in finite projective spaces. In turn, these allow us to give explicit constructions of minimal codes having short length for the given field and dimension.

Introduction

In a linear code, a codeword is minimal if its support does not contain the support of any codeword other than its scalar multiples. A code is minimal if its codewords are all minimal.

Minimal codewords in linear codes were originally studied in connection with decoding algorithms [START_REF] Hwang | Decoding linear block codes for minimizing word error rate[END_REF] and have been used by Massey [START_REF] Massey | Minimal codewords and secret sharing[END_REF] to determine the access structure in his code-based secret sharing scheme. However, describing the minimal codewords of a linear code is in general a difficult problem, even for highly structured families of codes.

General properties of the minimal codewords of a code are studied in [START_REF] Ashikhmin | Minimal vectors in linear codes[END_REF], where a sufficient condition for a code to be minimal is presented (often called the Ashikhmin-Barg condition).

The latter shows that a linear code in which the minimum and maximum weight are close enough to each other is necessarily minimal. Recently, estimates for the number of minimal codewords in a given code have been also found; see [START_REF] Cruz | On the minimum number of minimal codewords[END_REF].

In the last decade, minimal codes have been the subject of intense mathematical research, yet their structural properties are far from being understood. First results on minimal codes were presented in [START_REF] Chabanne | Towards secure two-party computation from the wire-tap channel[END_REF], where the main motivation arises from secure two-party computation.

Moreover, in the same paper an upper bound on the rate of a minimal code is established, which was recently improved in [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF]. Other bounds on the minimum and maximum weight of minimal codes can be found in [START_REF] Cohen | On minimal and quasi-minimal linear codes[END_REF].

Various explicit constructions of minimal codes relying on the aforementioned Ashikhmin-Barg condition are known; see [START_REF] Carlet | Linear codes from perfect nonlinear mappings and their secret sharing schemes[END_REF][START_REF] Ding | Linear codes from some 2-designs[END_REF] among many others. Constructions that exploit in other ways the minimal structure of the code are based, for example, on functions over finite fields [START_REF] Bartoli | Minimal linear codes in odd characteristic[END_REF][START_REF] Bonini | Minimal linear codes arising from blocking sets[END_REF][START_REF] Mesnager | Linear codes with few weights from weakly regular bent functions based on a generic construction[END_REF][START_REF] Mesnager | Linear codes from weakly regular plateaued functions and their secret sharing schemes[END_REF]. A geometric approach was proposed in [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF][START_REF] Lu | The parameters of minimal linear codes[END_REF][START_REF] Tang | Full characterization of minimal linear codes as cutting blocking sets[END_REF], where minimal codes are characterized as cutting blocking sets.

A remarkable property of minimal codes is that they form an asymptotically good family [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF][START_REF] Cohen | On minimal and quasi-minimal linear codes[END_REF]. Since the proofs of [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF][START_REF] Cohen | On minimal and quasi-minimal linear codes[END_REF] are nonconstructive, this naturally poses the problem of explicitly constructing families of minimal codes of short length for a given dimension, which is equivalent to constructing small cutting blocking set in a given projective space. Problems of this type are very natural and yet wide open challenges in the realm of extremal combinatorial structures; see e.g. [START_REF] Ball | Multiple blocking sets and arcs in finite planes[END_REF][START_REF] Barát | Multiple blocking sets in PG(n, q), n ≥ 3[END_REF][START_REF] Blokhuis | Blocking sets in projective spaces[END_REF]]. An important contribution in this direction is [START_REF] Fancsali | Lines in higgledy-piggledy arrangement[END_REF], where the authors construct small cutting blocking sets in PG(k -1, q), under the assumption that the characteristic of the field is strictly greater than k -1 and the field size is at least 2k -3. Because of the constraints imposed on the field size, the construction of [START_REF] Fancsali | Lines in higgledy-piggledy arrangement[END_REF] is of limited applicability in coding theory and does not address the problem of constructing asymptotically good families of minimal codes (where q is fixed and k tends to infinity together with the code length). More recently, a construction of cutting blocking sets in PG(3, q) and PG (5, q), which are smaller that the previously known ones, has been given in [START_REF] Bartoli | On cutting blocking sets and their codes[END_REF]. This construction produces minimal codes of dimension respectively 4 and 6 over a finite field of arbitrary size.

Our contribution.

In this paper, we propose three different approaches of strong combinatorial flavour to the study of minimal codes, each of which has a particular application. Most methods apply more generally to arbitrary linear codes, but give the best and most explicit results when combined with the minimality property of the underlying code.

The idea behind the first approach is to associate to a code a multivariate polynomial, which we call the support polynomial. This allows us to capture the combinatorics of the nonzero codewords of a code in an algebraic fashion, characterizing the inclusion relations among supports as the nonvanishing of a polynomial of bounded degree. We then study the support polynomial using tools from algebraic combinatorics, most notably the Alon-Füredi Theorem. As an application of this method, we obtain new lower bounds for both the minimum distance and the length of a minimal code. This improves on known results and excludes the existence of minimal codes for several new parameter sets.

The second approach uses instead ideas from statistics. More precisely, we regard the weight of a nonzero codeword as a discrete random variable and use Pless' equations, along with classical inequalities, to compare its mean and variance. All of this establishes inequalities between the maximum and minimum weight in a linear code, which are sharp for certain code families. In turn, these yield a new upper bound for the minimum distance of a minimal code and exclude the existence of such codes for yet other parameter sets.

Finally, the third approach is based on the correspondence between minimal codes and cutting blocking sets in finite geometry. We first reduce the problem of constructing short minimal codes to that of constructing cutting blocking sets of small cardinality. Then we show how to use the theory of spreads in projective spaces to obtain cutting blocking sets whose parameters can be computed explicitly. The applications of this geometric approach are twofold: On the one hand, we obtain new explicit constructions of short minimal codes; on the other hand, we establish a recursive upper bound for the least length of a minimal code over F q having prescribed dimension.

For convenience of the reader we conclude the Introduction by listing the main contributions made by this paper, pointing to the corresponding statements.

-As an application of methods from algebraic combinatorics, in particular the Alon-Füredi Theorem and the Combinatorial Nullstellensatz:

1. a lower bound on the minimum distance of a minimal code (Theorem 2.8); 2. a structural result on the maximal codewords in a linear code (Theorem 2.13); 3. a lower bound on the block length of a minimal code (Theorem 2.14).

-Combining ideas from coding theory and statistics with the algebraic combinatorial approach outlined above: 4. an upper bound on the minimum distance of a minimal code and a constraint on its parameters (Corollary 3.7); 5. a result connecting the relative difference between maximum and minimum weights in a linear code with its block length (Corollary 3.10).

-Using methods from projective geometry, most notably the theory of spreads: 6. a construction of cutting blocking sets from spreads in finite geometry and of the corresponding minimal codes (Theorems 4.1 and 4.2); 7. an inductive construction of cutting blocking sets of small cardinality and of the corresponding minimal codes (Proposition 4.5 and Theorem 4.6); 8. two new general constructions of short minimal codes (Constructions A and B).

Outline. The paper is overall organized into four sections. Section 1 contains the preliminaries on minimal codes and illustrates their connection with cutting blocking sets. Each of the remaining three sections is devoted to a different approach to minimal codes, using algebraic combinatorics (Section 2), statistics (Section 3), and finite geometry (Section 4).

Preliminaries

In this section we establish the terminology for the remainder of the paper and state some preliminary results on the parameters of minimal codes. These will be applied in several instances in the sequel. All codes considered in this work are linear. Notation 1.1. Throughout this paper, q is a prime power, F q is the finite field with q elements, and n, k are integers with

n ≥ k ≥ 1. For i ∈ N = {0, 1, 2, . . .} we let [i] := {j ∈ N : 1 ≤ j ≤ i}.
We only consider row-vectors and for any matrix M ∈ F a×b we denote by rowsp(M ) the rowspace of M over F, that is the F-subspace of F b generated by the rows of M . Finally, for i ∈ N ≥1 we denote by e i the i-th standard basis vector.

Minimal Codes

In this short subsection we define minimal codes and briefly survey some of their main properties. We will use them repeatedly throughout the paper.

Definition 1.2. The (Hamming) support of a vector v ∈ F n q is σ(v) = {i | v i = 0} ⊆ [n] and its (Hamming) weight is ω(v) = |σ(v)|. An [n, k] q code is a nonzero F q -linear subspace C ⊆ F n q of dimension k. Its elements are called codewords. The minimum distance of C is the integer d(C) = min{ω(c) | c ∈ C, c = 0} and its maximum weight is max{ω(c) | c ∈ C}. If d = d(C) is known, we say that C is an [n, k, d] q code. A generator matrix G ∈ F k×n q of C is a matrix such that rowsp(G) = C.
Finally, codes C and C ′ are called (monomially) equivalent if there exists an F q -linear isometry f : F n q → F n q with f (C) = C ′ ; see [26, page 24]. Recall that an [n, k] q code C is nondegenerate if there is no i ∈ [n] with c i = 0 for all c ∈ C. Furthermore, C is called projective if in one (and thus in all) generator matrix G of C no two columns are proportional. Note that a projective code is necessarily nondegenerate.

In this paper we mostly concentrate on codes whose codewords are all minimal.

Definition 1.3. Let C be an [n, k] q code. A nonzero codeword c ∈ C is called minimal if every codeword c ′ ∈ C with σ(c ′ ) ⊆ σ(c) is a multiple of c.
We say that C is minimal if all its codewords are minimal.

Remark 1.4. Following the notation of Definition 1.3, in a minimal code C any nonzero codeword c is minimal, but also maximal (i.e., every other codeword

c ′ ∈ C with σ(c ′ ) ⊇ σ(c) is a multiple of c).
The following simple result states that every minimal codeword c in a [n, k] q code C has weight upper bounded by nk + 1. To see this, it suffices to puncture C on the nonzero positions of c, obtaining a new code whose length is nω(c) and whose dimension is k -1.

Proposition 1.5. Let C be an [n, k] q code. Every minimal codeword c ∈ C has ω(c) ≤ n -k + 1.
The following result shows that minimal codes have relatively large length with respect to their dimension and field size; see also Remark 3.4.

Theorem 1.6 (see [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF][START_REF] Lu | The parameters of minimal linear codes[END_REF]). Let C be an [n, k] q minimal code with k ≥ 2. We have n ≥ (k-1)q+1.

The previous bound is not tight in general. More precisely, in [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF] it was conjectured (and then proved in [START_REF] Tang | Full characterization of minimal linear codes as cutting blocking sets[END_REF]) that the length n of an [n, k] q minimal code satisfies the following lower bound.

Theorem 1.7 (see [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF][START_REF] Tang | Full characterization of minimal linear codes as cutting blocking sets[END_REF]). Let C be an [n, k] q minimal code with k ≥ 2. We have

n ≥ (k -1)(q -1) + 1 + k-1 i=1 (k -1)(q -1) + 1 q i .
In Section 2 we will further improve the bound in Theorem 1.7 using methods from algebraic combinatorics; see Theorem 2.14.

Minimal Codes and Cutting Blocking Sets

The concept of a cutting blocking set was introduced in [START_REF] Bonini | Minimal linear codes arising from blocking sets[END_REF] with the goal of constructing a family of minimal codes. The same objects were know earlier under various names and in different contexts. In [START_REF] Davydov | Linear nonbinary covering codes and saturating sets in projective spaces[END_REF] these are called N -fold strong blocking set and are used for constructing small saturating sets in projective spaces over finite fields. In [START_REF] Fancsali | Lines in higgledy-piggledy arrangement[END_REF], cutting blocking sets are referred to as generator sets and are constructed as union of disjoint lines. In [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF] and [START_REF] Tang | Full characterization of minimal linear codes as cutting blocking sets[END_REF] it was independently shown that cutting blocking sets are in one to one correspondence with minimal linear codes. In this subsection, we recall some properties of (cutting) blocking sets and known results about their size.

Consider the finite projective geometry of dimension N and order q, denoted by PG(N, q). Recall that PG(N, q) :=

F N +1 q \ {0} / ∼ ,
where ∼ denotes the proportionality relation, i.e., u ∼ v if and only if u = λv for some nonzero λ ∈ F q . A d-flat in PG(N, q) is a subspace Π isomorphic to PG(d, q). A 1-flat is a line, while a 2-flat is a plane. If d = N -1, then Π is called a hyperplane.

In our approach, projective systems are crucial geometric objects for the study of linear codes and their properties. Definition 1.8. A projective [n, k, d] q system P is a finite set of n points (counted with multiplicity) of PG(k -1, q) that do not all lie on a hyperplane and such that

d = n -max{|H ∩ P| : H ⊆ PG(k -1, q), dim(H) = k -2}.
Projective [n, k, d] q systems P and P ′ are equivalent if there exists a projective isomorphism φ of PG(k -1, q) mapping P to P ′ which preserves the multiplicities of the points.

There is a well-known correspondence between the (monomial) equivalence classes of nondegenerate [n, k, d] q linear codes and the equivalence classes of projective [n, k, d] q systems; see [START_REF] Tsfasman | Algebraic-geometric codes[END_REF]Theorem 1.1.6]. More precisely, let G be a k × n generator matrix of an [n, k] q linear code. Consider the set P of one-dimensional subspaces of F n q spanned by the columns of G, which gives a set of points in PG(k -1, q). Conversely, let P be a projective [n, k, d] q system. Choose a representative for any point of P and consider the code generated by the matrix having these representatives as columns. Now observe that for any nonzero vector u = (u 1 , u 2 , . . . , u k ) in F k q the hyperplane u

1 x 1 + u 2 x 2 + • • • + u k x k = 0
contains |P|w points of P if and only if the codeword uG has weight w.

Definition 1.9. Let t, r, N be positive integers with r < N . A t-fold r-blocking set in PG(N, q) is a set M ⊆ PG(N, q) such that for every (Nr)-flat Λ of PG(N, q) we have |Λ ∩ M| ≥ t.

When r = 1, we will refer to M as a t-fold blocking set. When t = 1, we will refer to it as an r-blocking set. When r = t = 1, M is simply a blocking set.

Cutting blocking sets are defined as follows.

Definition 1.10. Let r, N be positive integers with r < N . An r-blocking set M in PG(N, q) is cutting if for every pair of (Nr)-flats Λ, Λ ′ of PG(N, q) we have

M ∩ Λ ⊆ M ∩ Λ ′ ⇐⇒ Λ = Λ ′ .
Equivalently, an r-blocking set M ⊆ PG(N, q) is cutting if and only if for every (Nr)dimensional subspace Λ of PG(N, q) we have M ∩ Λ = Λ; see [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF].

It is shown in [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF][START_REF] Tang | Full characterization of minimal linear codes as cutting blocking sets[END_REF] that the correspondence described above between projective [n, k, d] q systems and nondegenerate [n, k, d] q linear codes extends to a correspondence between equivalence classes of [n, k, d] q minimal codes and equivalence classes of projective [n, k, d] q systems that are cutting blocking sets. This geometric interpretation of minimal codes will be crucial in Section 4.

Remark 1.11. As already mentioned in the Introduction, we are particularly interested in finding lower bounds on the length of minimal codes or, equivalently, lower bounds on the size of cutting blocking sets in projective spaces. From this point of view, it is not restrictive to only consider projective codes, which correspond to projective systems in which all the points have multiplicity one.

It immediately follows from the definitions that a cutting blocking set M in PG(N, q) is necessarily an N -fold blocking set. The following theorem is obtained by combining a well-known result of Beutelspacher (which gives a lower bound on the cardinality of an N -fold blocking set in PG(N, q) when N ≤ q) and the correspondence between minimal codes and cutting blocking sets.

Theorem 1.12 (see [START_REF] Beutelspacher | On Baer subspaces of finite projective spaces[END_REF]Theorem 2]). Let C be an [n, k] q minimal code. If k -1 ≤ q, then n ≥ (q + 1)(k -1).

The above results uses the fact that cutting blocking sets in PG(k -1, q) are in particular (k -1)-fold blocking sets. Beutelspacher also characterized (k -1)-fold blocking sets in PG(k -1, q) with cardinality (q + 1)(k -1), under the further assumption that k ≤ √ q + 2. Recall that, when q is a square, a Baer subspace of PG(N, q) is a subgeometry isomorphic to PG(N, √ q). Theorem 1.13 (see [START_REF] Beutelspacher | On Baer subspaces of finite projective spaces[END_REF]Theorem 3]). Let 4 ≤ k ≤ √ q + 2 and let M be a (k -1)-fold blocking set in PG(k -1, q). Then |M| ≥ (q + 1)(k -1). Moreover, equality holds if and only if one of the following scenarios occurs:

1. M is the set of points on k -1 mutually skew lines.

2. k = √ q + 2 and M is the point set of a 3-dimensional Baer subspace of PG(k -1, q).

3. q = 4, k = 4, and M is the complement of a hyperoval in a plane of PG(k -1, q), where an hyperoval is a set of q + 2 points in a plane, no three of which are collinear.

In [1, Lemma 4.9] and in [START_REF] Tang | Full characterization of minimal linear codes as cutting blocking sets[END_REF] it was observed that cutting blocking sets in PG(2, q) and 2-fold blocking sets are actually the same object. Moreover, in PG(2, q) one can always construct a 2-fold blocking set of size 3q, or equivalently a [3q, 3] q minimal code, by considering the union of three lines that do not intersect in the same point. When q is a square, one can construct a cutting blocking set as union of two disjoint Baer subplanes, producing a minimal code of length 2q + 2 √ q + 2. We thus survey the known results on the cardinality of 2-fold blocking sets in PG(2, q), which turn out to be an accurate estimates also for the length of minimal codes of dimension 3.

Theorem 1.14 (see [START_REF] Ball | On the size of a double blocking set in PG(2, q)[END_REF]Theorem 3.1]). Let M be a 2-fold blocking set in PG(2, q). The following hold.

1. If q < 9, then |M| ≥ 3q.

2. If q > 4 is a square, then |M| ≥ 2q + 2 √ q + 2.

3. If q > 19, q = p 2d+1 , then |M| ≥ 2q + p d (p d+1 +1) (p d +1)

+ 2.

4. If q = 11, 13, 17, 19 is not a square, then |M| ≥ (5q+7)

2

.

The bounds in Theorem 1.14, parts (3) and (4), are believed not to be sharp; see [6, page 133]. In particular, we are not aware of any construction of 2-fold blocking sets achieving these sizes.

Remark 1.15. In the literature, there are two general constructions of small cutting blocking sets we are aware of, which we briefly sketch in this remark.

The first one was proposed by Fancsali and Sziklai in [START_REF] Fancsali | Lines in higgledy-piggledy arrangement[END_REF] and it works as follows. One chooses any 2k -3 distinct points on the rational normal curve in PG(k -1, q) and takes the union of the tangent lines at these points. The resulting set is a cutting blocking set, under the assumption that the characteristic of the field is at least k. We call this set the rational normal tangent set. The corresponding codes are minimal [(2k -3)(q + 1), k] q codes whose minimum distance was proved to be at least kq in [START_REF] Bartoli | On cutting blocking sets and their codes[END_REF]. The drawback of this construction is the constraint on both the size (q) and the characteristic (p) of the underlying field, reading q ≥ 2k -3 and p ≥ k. For a fixed value of q, the approach of [START_REF] Fancsali | Lines in higgledy-piggledy arrangement[END_REF] constructs cutting blocking sets in PG(k -1, q) for only a finite number of values of k.

A second construction that instead works for every choice of the parameters k and q can be found in [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF][START_REF] Bartoli | An inductive construction of minimal codes[END_REF][START_REF] Lu | The parameters of minimal linear codes[END_REF]. Consider k points P 1 , . . . , P k in general position in PG(k -1, q) and let ℓ i,j := P i , P j . Then the union of these lines gives a cutting blocking set. From this construction, called tetrahedron, one obtains a family of [(q -1) k 2 + k, k, (q -1)(k -1) + 1] q minimal codes. As a consequence of Theorem 1.14, when k = 3 this construction provides a minimal 2-fold blocking set in PG(2, q) for any q < 9.

Algebraic Combinatorial Approach

This section develops an algebraic combinatorial approach to study minimal codes. The method uses a generator matrix of a linear code to build a multivariate polynomial "machinery". This allows us to study the maximal codewords of a code by applying classical results on the number of roots of multivariate polynomials over finite grids. As an application of our method, with the aid of Alon's Combinatorial Nullstellensatz [START_REF] Alon | Combinatorial nullstellensatz[END_REF] and the Alon-Füredi Theorem [START_REF] Alon | Covering the cube by affine hyperplanes[END_REF], we improve known lower bounds on the minimum distance and the length of minimal codes.

It is interesting to observe that the results contained in this section are mainly exploiting the fact that in a minimal code all the codewords are maximal, as already observed in Remark 1.4. Although in a minimal code this code property is equivalent to all codewords being minimal, the focus on maximal codewords is crucial for deriving both the lower bound on the minimum distance (Theorem 2.8) and the lower bound on the length (Theorem 2.14) of minimal codes.

Combinatorial Nullstellensatz and Alon-Füredi Theorem

We start by surveying tools from algebraic combinatorics that will be applied repeatedly. Among these are Alon's Combinatorial Nullstellensatz and the Alon-Füredi Theorem.

Notation 2.1. We state the results of this subsection and of the next one for an arbitrary field F. In Subsection 2.3 we will resume focusing on the case F = F q and on linear codes.

For a multivariate polynomial p ∈ F[x 1 , . . . , x k ] and a subset A ⊆ F k , denote by V A (p) the set of zeros of p in A, and by U A (p) the nonzeros of p in A, i.e.,

V A (p) = {v ∈ A | p(v) = 0} , U A (p) = {u ∈ A | p(u) = 0} .
The Alon-Füredi Theorem [START_REF] Alon | Covering the cube by affine hyperplanes[END_REF]Theorem 5] gives a lower bound on the cardinality of U A (p) when A is a finite grid and p is not identically zero on A. Equivalently, it provides an upper bound on the number of zeros of p. We recall it for convenience of the reader.

Theorem 2.2 (Alon-Füredi Theorem [3]). Let

A = A 1 × . . . × A k ⊆ F k be a finite grid with A i ⊆ F and |A i | = n i , where n 1 ≥ n 2 ≥ . . . ≥ n k ≥ 2. Let p ∈ F[x 1 , . . . , x k ]
be a polynomial that is not identically 0 on A, and let p be the polynomial p modulo the ideal (f 1 (x 1 ), . . . , f k (x k )), where

f i (x i ) = a∈A i (x i -a). Then |U A (p)| ≥ (n s -ℓ) s-1 i=1 n i ,
where ℓ and s are the unique integers satisfying deg p

= k i=s+1 (n i -1) + ℓ, with 1 ≤ s ≤ k and 1 ≤ ℓ ≤ n s -1.
The above theorem relies on the fact that the polynomial p is not identically zero on the finite grid we are interested in. However, when dealing with polynomials that are not explicitly given, this property is not always easy to verify. In this direction, the celebrated Alon's Combinatorial Nullstellensatz helps determining a sufficient condition for a polynomial to be nonzero on a finite grid. We state it here for completeness.

Theorem 2.3 (Combinatorial Nullstellensatz [2]). Let p ∈ F[x 1 , . . . , x k ] and let deg p = k i=1 r i , for some r 1 , . . . , r k ∈ N. Suppose that the coefficient of the monomial x r 1 1 x r 2 2 • • • x r k k in p is nonzero. Let A := A 1 × . . . × A k ⊆ F k be a grid with |A i | ≥ r i + 1 for all i ∈ [k]. Then U A (p) = ∅.

The Support Polynomials

We denote by g (i) the i-th column vector of a matrix G ∈ F k×n . Moreover, we consider the vector x = (x 1 , . . . , x k ) whose entries are algebraically independent variables over F. Definition 2.4. The support polynomial associated with a matrix G ∈ F k×n and a subset

I ⊆ [n] is p G,I (x) := i∈I x • g (i) ∈ F[x 1 , . . . , x k ].
In our approach, support polynomials are crucial for the study of minimal codes (taking as G a generator matrix of an [n, k, d] q code and as I a subset of a codeword's support). However, for the moment we focus on general properties of support polynomials that do not necessarily arise from codes. The following result is straightforward and its proof is omitted.

Proposition 2.5. Let G ∈ F k×n and I ⊆ [n]. 1. For every A ∈ GL(k, F) p AG,I (x) = p G,I (xA) = (p G,I • L A )(x),
where L A denotes the linear map associated to the matrix A, that is v -→ vA.

For every

τ ∈ S n p G,τ (I) (x) = p GPτ ,I (x),
where P τ is the permutation matrix associated to τ , such that

(v 1 , . . . , v n )P τ = v τ (1) , . . . , v τ (n) . 3. For every v ∈ F n p GDv,I (x) = i∈I v i p G,I (x),
where D v denotes the diagonal matrix whose diagonal is v.

We now study a support polynomial in connection with the rowspace of the matrix G ∈ F k×n that defines it. We first show how the zeros and nonzeros of support polynomials are related when we choose matrices with the same rowspace.

Let G 1 , G 2 ∈ F k×n be two matrices such that rowsp(G 1 ) = rowsp(G 2 ). It is easy to see that there exists A ∈ GL(k, F) such that

U F k q (p G 1 ,I ) = U F k q (p G 2 ,I ) • A := uA | u ∈ U F k q (p G 1 ,I ) , V F k q (p G 1 ,I ) = V F k q (p G 2 ,I ) • A := vA | v ∈ V F k q (p G 1 ,I ) .
Indeed, any matrix A with G 2 = AG 1 satisfies the desired properties. Moreover, the nonzeros of a support polynomial are closely related to the support of vectors belonging to the rowspace of the defining matrix. This is shown by the following simple result, whose proof is omitted.

Lemma 2.6. Let G ∈ F k×n be a matrix. For all I ⊆ [n] we have

U F k (p G,I ) = u ∈ F k | σ(uG) ⊇ I .
In particular, U F k (p G,I ) = ∅ if and only if there exists c ∈ rowsp(G) such that σ(c) ⊇ I.

Minimum Distance of Minimal Codes

In this subsection we investigate the support polynomials of generator matrices of linear codes and their set of zeros. As a corollary of our results, we establish1 a conjecture from [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF]. We start with the following lemma, whose proof directly follows from Lemma 2.6 and Remark 1.4. Lemma 2.7. Let G ∈ F k×n q be a generator matrix of an [n, k] q code C. Let c = uG be a maximal codeword of C and I := σ(c). Then

U F k q (p G,I ) = {λu | λ ∈ F * q }.
In particular, if C is a minimal code then the above statement holds for every nonzero codeword.

Theorem 2.8. Let C be an [n, k, d] q code, and let c be a maximal codeword. Then ω(c)

≥ (q -1)(k -1) + 1. In particular, if C is minimal then d ≥ (q -1)(k -1) + 1.
Proof. Let c = (c 1 , . . . , c n ) ∈ C be a maximal codeword of weight w and let I := σ(c), i.e., c i ∈ F * q if and only if i ∈ I. Take a generator matrix G ∈ F k×n q for C and consider the polynomial p G,I (x) ∈ F q [x 1 , . . . , x k ]. Observe that p G,I does not vanish identically on F k q . Indeed, let u ∈ F k q be the vector such that uG = c. Then p G,I (u) = i∈I c i = 0. This also ensures that deg p G,I = w. Since c is a maximal codeword, by Lemma 2.7 we have

U F k q (p G,I ) = {αλ | α ∈ F * q }, which has cardinality q -1.
On the other hand, let pG,I denote the reduction of the polynomial p G,I modulo the ideal

({x q i -x i | i ∈ [k]}). By Theorem 2.2 we have |U F k q (p G,I )| ≥ (q -ℓ)q s-1 ,
where ℓ and s are the unique integers satisfying deg pG,I = (q -1)(ks) + ℓ, with 1 ≤ s ≤ k and 1 ≤ ℓ ≤ q -1. Thus, combining this with the exact value of |U F k q (p G,I )|, we obtain q -1 = |U F k q (p G,I )| ≥ (qℓ)q s-1 , from which we deduce s = 1. Therefore,

w = deg p G,I ≥ deg pG,I = (q -1)(k -1) + ℓ ≥ (q -1)(k -1) + 1.
Remark 2.9. The Alon-Füredi Theorem (Theorem 2.2) gives a lower bound on the number of nonzeros of a multivariate polynomial in a finite grid in terms of the degree of the polynomial and the size of the grid. This result has been used in coding theory for deriving the minimum distance of generalized Reed-Muller codes; see e.g. [START_REF] Geil | Weighted Reed-Muller codes revisited[END_REF][START_REF] López | Affine cartesian codes[END_REF]. It is interesting to observe that in our Theorem 2.8 the Alon-Füredi Theorem is applied in the "opposite" direction, i.e., we use it to derive a lower bound on the degree of the support polynomial associated to a maximal codeword, knowing the number of its nonzeros.

Maximal Codewords in Linear Codes

In this subsection we use support polynomials to study the structure of maximal codewords in a linear code C. In particular, we show that for any maximal codeword c ∈ C there exist several codewords whose support contains a large subset of the support of c. This property will be crucial for deriving a lower bound on the length of minimal codes in Subsection 2.5.

For v = (v 1 , . . . , v k ) ∈ F k q , define f v (x) := k i=1 s∈Fq\{v i } (x i -s) .
Next, consider the ideal I q := (x q 1 -x 1 , . . . , x q k -x k ) and denote by f the reduction of a polynomial f ∈ F q [x 1 , . . . , x k ] modulo I q . It is easy to check that for every v ∈ F k q we have fv = f v . One can also easily prove that the set {f v | v ∈ F k q } is an F q -basis for the space F q [x 1 , . . . , x k ]/I q . Moreover, regarding the polynomials f v 's as maps from F k q to F q , the set {f v | v ∈ F k q } is an F q -basis of {ϕ : F k q -→ F q }. This is due to the following well-known result.

Proposition 2.10. The evaluation map on F q [x 1 , . . . , x k ] induces the isomorphism of F q -vector spaces

F q [x 1 , . . . , x k ]/I q ∼ = {ϕ : F k q -→ F q }. (2.1)
In particular, for every p ∈ F q [x 1 , . . . , x k ] there exist unique

µ v ∈ F q for v ∈ U F k q (p), such that p = v∈U F k q (p) µ v f v .
Proposition 2.11. Let C be an [n, k] q code and let c = (c 1 , . . . , c n ) ∈ C be a maximal codeword of C with weight w and support I := σ(c). Let w 1 be the unique integer in [q -1] such that w 1 ≡ w mod (q -1). Then, for any A ∈ GL(k, q) such that the first row of A -1 G is equal to c, we have pG,I (x) = p c (xA), where

p c (x) = w i=1 c i x w 1 1 k i=2 (1 -x q-1 i ).
Proof. We first prove the statement in the case where the first row of G is equal to c. Observe that pc = p c , that is, the polynomial p c is already reduced modulo I q . Therefore, by the isomorphism given in (2.1), we only need to show that p G,I (v) = p c (v) for every v ∈ F k q . By definition of p c we have

p c (v) =    λ w 1 w i=1 c i if v = λe 1 , 0 otherwise.
On the other hand, by the choice of G and Lemma 2.7 we have

p G,I (λe 1 ) = w i=1 (λc i ) = λ w 1 w i=1 c i ,
where the last inequality follows using the identity λ q = λ. Moreover, p G,I (v) = 0 for every v / ∈ {λe 1 | λ ∈ F * q }. The general case follows from the previous one. We first transform G into A -1 G, where the first row of A -1 G is equal to c. This implies that p A -1 G,I (x) = p c (x). Then, using Proposition 2.5, we find p G,I (x) = p A -1 G,I (xA) = p c (xA). Notation 2.12. In the remainder of the section we write x = (x 1 , . . . , x k ) and for α = (α 1 , . . . , α k ) ∈ N k we denote by x α the monomial

x α 1 1 • • • x α k k .
Moreover, we let α := α 1 + . . . + α k . Finally, for a polynomial p(x) ∈ F q [x 1 , . . . , x k ] and a monomial x α , we denote by [x α ]p(x) the coefficient of the monomial

x α = x a 1 1 • • • x a k k in p(x).
The following result on maximal codewords will be crucial in the next subsection for deriving a lower bound on the length of a minimal code. Theorem 2.13. Let C be an [n, k] q code and let c = (c 1 , . . . , c n ) ∈ C be a maximal codeword. For every j ∈ σ(c) there exist I j ⊆ σ(c) \ {j} of cardinality (q -1)(k -1) and a codeword z ∈ C such that σ(z) ∩ σ(c) ⊇ I j .

Proof. Let c ∈ C be a nonzero codeword with support I := σ(c) and weight w = (q-1)(k-1)+w 1 . By Theorem 2.8 we have w 1 ≥ 1.

Assume first that w ≤ (q -1)k, which implies 1 ≤ w 1 ≤ q -1. We choose a generator matrix G for C whose first row is equal to c, and assume that c i = 1 for every i ∈ I. This can be done without loss of generality, up to replacing the code with an equivalent one. By Proposition 2.11 we have

pG,I (x) = p c (x) = x w 1 1 k i=2 (1 -x q-1 i ).
Let j ∈ I and assume that the j-th column of G is (1, 0, . . . , 0) ⊤ . Define L I,j := {L ⊆ I : j / ∈ L, |L| = (q -1)(k -1)} and β := (w 1 , q -1, q -1, . . . , q -1). We have

(-1) k-1 = [x β ]p G,I (x) = [x β ]p G,I (x) = L∈L I,j [x q-1 2 • • • x q-1 k ]p G,L (x).
The first equality follows from direct inspection of p c (x). The second equality is due to the fact that the degree p G,I is equal to (q -1)(k -1) + w 1 , which is also the degree of pG,I . The third equality follows from the fact that the coefficients of x 1 in the matrix G are all equal to 1. Therefore, there exists

I j ∈ L I,j such that [x q-1 2 • • • x q-1 k ]p G,I j (x) = 0. Let x ′ := (x 2 , .
. . , x k ) and consider the polynomial f (x ′ ) := p G,I j (0, x 2 , . . . , x k ). This polynomial has degree |I j | = (q -1)(k -1) and [x q-1 2

• • • x q-1 k ]f (x ′ ) = [x q-1 2 • • • x q-1 k ]p G,I j (x) = 0.
Hence, by Theorem 2.3, there exists v ∈ F k-1 q such that f (v) = p G,I j (0, v) = 0. By Lemma 2.6, this implies that the codeword z := (0, v)G ∈ C satisfies σ(z) ⊇ I j . Now assume that w > (q -1)k, from which w 1 ≥ q. Let us write w 1 = a(q -1) + b with 1 ≤ b ≤ q -1. Since w > (q -1)k, we have a ≥ 1. Denote the vector β := (b, q -1, q -1, . . . , q -1). Consider the set T := {α ∈ N k : α = a(q -1), α i ≡ 0 mod (q -1) for every i ∈

[k]}. Then (-1) k-1 = [x β ]p G,I (x) = α∈T [x β+α ]p G,I (x).
This means that there exists γ ∈ T such that [x β+γ ]p G,I (x) = 0. Define L (γ)

I,j := {L ⊆ I : |L| = w -b -γ 1 , j /
∈ L}, γ ′ := (0, γ 2 , . . . , γ k ), and β ′ := (0, q -1, . . . , q -1). We have

[x β+γ ]p G,I (x) = L∈L (γ) I,j [x β ′ +γ ′ ]p G,L (x)
and there exists K ∈ L (γ)

I,j such that [x β ′ +γ ′ ]p G,K (x) = 0.
At this point we can consider the set

X K := {M ⊆ K : |M | = (q -1)(k -1)} and write [x β ′ +γ ′ ]p G,K (x) = M ∈X K λ M [x β ′ ]p G,M (x)
for some λ M ∈ F q . Since this sum is nonzero, there exists M such that [x β ′ ]p G,M (x) = 0. As in the previous case, we use Theorem 2.3 and Lemma 2.6 to deduce that there exists a codeword z ∈ C such that σ(z) ⊇ M .

The Length of Minimal Codes

As an application of Theorem 2.13, we derive the following lower bound on the length of a minimal code.

Theorem 2.14. Let C be an [n, k, d] q minimal code. We have n ≥ (q + 1)(k -1).

Proof. Let c ∈ C be a codeword of minimum weight d with support I := σ(c). Up to considering an equivalent code, we can assume c i = 1 for every i ∈ I. Since c is in particular a maximal codeword of C, by Theorem 2.13 there exists a codeword z ∈ C such that |I ∩σ(z)| ≥ (q-1)(k-1). Let J := I ∩ σ(z) and for every λ ∈ F * q define J λ := {j ∈ J | z j = λ}. Clearly, J = λ∈F * q J λ and the union is disjoint. Thus by generalized pigeonhole principle there exists λ ′ ∈ F * q such that

|J λ ′ | ≥ |J| q -1 ≥ k -1. Now consider the codeword z -λ ′ c. Its support is σ(z -λ ′ c) = (σ(c) ∪ σ(z)) \ J λ ′ and ω(z -λ ′ c) = |σ(c)| + |σ(z)| -|J| -|J λ ′ | ≤ d + ω(z) -q(k -1).
Combining this with ω(zλ ′ c) ≥ d we obtain ω(z) ≥ q(k -1). Furthermore, by Proposition 1.5 we have ω(z) ≤ nk + 1, from which we finally obtain n ≥ (q + 1)(k -1).

Remark 2.15. The lower bound of Theorem 2.14 is an improvement on the bound in Theorem 1.7. Indeed, we have

(q + 1)(k -1) ≥ k-1 i=0 (q -1)(k -1) + 1 q i . (2.2)
We do not go into the details of the proof.

Remark 2.16. Observe that Theorem 2.14 is an improvement on the bound of Theorem 1.12, since it does not require the extra assumption that k ≤ q + 1.

We conclude this section with a detailed example building on [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF]Example 5.11].

Example 2.17. We fix q = 3, k = 4 and take the minimal [START_REF] Bonini | Minimal linear codes arising from blocking sets[END_REF][START_REF] Ashikhmin | Minimal vectors in linear codes[END_REF][START_REF] Barát | Multiple blocking sets in PG(n, q), n ≥ 3[END_REF] 3 code C whose generator matrix is

G :=     0 0 0 0 0 0 0 1 2 1 1 1 2 1 1 1 1 0 0 0 0 0 0 0 1 2 1 1 0 1 2 1 1 1 0 0 0 0 0 0 2 2 0 0 0 0 1 2 1 1 1 0 0 0 1 2     .
Let I := {8, 9, . . . , 14} be the support of the codeword c given by the first row of G and let x = (x 1 , x 2 , x 3 , x 4 ). We compute the associated support polynomial

p G,I (x) = x 1 (x 2 3 -x 2 1 )(x 2 1 -x 2 4 )((x 4 -x 2 ) 2 -(x 3 -x 1 ) 2 ).
An easy calculation shows that the reduction of p G,I (x) modulo

I 3 = (x 3 1 -x 1 , x 3 2 -x 2 , x 3 3 - x 3 , x 3 4 -x 4 ) is pG,I (x) = x 1 (1 -x 2 2 )(1 -x 2 3 )(1 -x 2 4 ) = p c (x)
, as we can also deduce from Proposition 2.11.

Moreover, since C is a minimal code, we can actually see that for every j ∈ I there exists a codeword z (j) ∈ C such that σ(z (j) ) ⊇ I \ {j}, as stated in Theorem 2.13. These 7 codewords (up to their nonzero scalar multiples) are z (8) = (0, 0, 0, 0, 2, 1, 2, 0, 1, 1, 1, 1, 1, 2), z (9) = (0, 1, 2, 1, 2, 0, 1, 2, 0, 1, 1, 1, 2, 2), z (10) = (1, 2, 0, 1, 2, 0, 1, 1, 1, 0, 1, 2, 1, 2), z (11) = (2, 1, 0, 2, 2, 2, 0, 1, 2, 1, 0, 2, 2, 2), z (12) = (1, 2, 0, 1, 1, 1, 0, 1, 2, 1, 2, 0, 2, 1), z (13) = (0, 2, 1, 2, 2, 2, 0, 1, 2, 1, 1, 1, 0, 2), z (14) = (0, 1, 2, 1, 1, 1, 0, 1, 2, 1, 1, 1, 1, 0). Finally, note that, in order to derive the lower bound on the length of minimal codes given in Theorem 2.14, we use in its proof that each of the codewords z (j) has weight at least q(k -1) = 9. However, in this case only z (8) has weight 9, while all the other codewords have weight 11.

Remark 2.18. It is natural to ask whether the bound of Theorem 2.14 is sharp or not. As stated in Subsection 1.2, minimal codes of dimension k over F q correspond to cutting blocking sets in PG(k -1, q) and a cutting blocking set is in particular a (k -1)-fold blocking set. When we restrict to the case 4 ≤ k ≤ √ q + 2, Theorem 1.13 characterizes a (k -1)-fold blocking set M in PG(k -1, q) of cardinality (q + 1)(k -1). This only happens in three cases.

Case I: M is the union of k -1 disjoint lines. In this case M cannot be a cutting blocking set. To see this, write

M = ℓ 1 ∪ . . . ∪ ℓ k-1 . Pick P 1 ∈ ℓ 1 , . . . , P k-1 ∈ ℓ k-1 and let Λ := P 1 , . . . , P k-1 . If dim(Λ) ≤ k -3, then Λ is contained in a (k -3)-flat Λ ′ .
Consider the sheaf of hyperplanes containing Λ ′ . They are q + 1 and only k -1 of them contain other points of M in addition to P 1 , . . . , P k-1 . Since k -1 < q + 1 there is at least one hyperplane H such that H ∩ M = {P 1 , . . . , P k-1 } and H ∩ M ⊆ Λ ′ = H. This implies that, in this case, M is not a cutting blocking set. Suppose then that dim(Λ) = k -2. Fix P 1 , . . . , P k-3 and consider the flat Γ := P 1 , . . . , P k-3 , ℓ k-2 . If dim(Γ) < k -2, then there exists Q k-2 ∈ ℓ k-2 ∩ P 1 , . . . , P k-3 . Thus, if we replace P k-2 by Q k-2 , we get that dim(Λ) < k-2, and we can conclude as done before that M is not cutting. Hence, assume dim(Γ) = k -2. In this case Γ

∩ ℓ k-1 = ∅. Take Q k-1 ∈ Γ ∩ ℓ k-1 . If Q k-1 ∈ P 1 , .
. . , P k-3 , we substitute P k-1 with Q k-1 and get again dim(Λ) < k -2, which implies M not being cutting. Therefore, assume that the space P 1 , . . . , P k-3 , Q k-1 is a hyperplane in Γ. Since Γ also contains ℓ k-2 , there exists R k-2 ∈ ℓ k-2 ∩ P 1 , . . . , P k-3 , Q k-1 . Thus, replacing P k-1 with Q k-1 and P k-2 with R k-2 , we again obtain that dim(Λ) < k -2 and M is not cutting.

Case II: k = √ q +2 and M is a 3-dimensional Baer subspace. If k ≥ 5, then M = PG(k -1, q), so M cannot be a cutting blocking set. For the remaining case, where k = q = 4, one can observe that for a (hyper)plane H in PG(3, q), H intersects M in a Baer subplane or in a Baer subline. In the latter case, one has M ∩ H = H, and so M is not a cutting blocking set. The fact that for k = q = 4 a 3-dimensional Baer subspace M cannot be cutting could be also deduced from Example 3.8, since the cardinality of M is 15.

Case III: q = k = 4 and M is the complement of a hyperoval in a plane of PG (3, q). In this case M = PG(3, q) and M cannot be a cutting blocking set. Therefore, when 4 ≤ k ≤ √ q + 2, the bound in Theorem 2.14 is never sharp.

Corollary 2.19. Let C be a minimal [n, k] q code with 3 ≤ k ≤ √ q+2. Then n ≥ (q+1)(k-1)+1, unless q = 2 and k = 3.

Proof. The case k ≥ 4 has been discussed in Remark 2.18. When k = 3, cutting blocking sets are equivalent to 2-fold blocking set. Using Theorem 1.14, one can easily verify that the only case in which a 2-fold blocking set has cardinality 2q + 2 is when q = 2.

Statistical Approach

Most bounds for minimal codes we are aware of involve either (q, n, k), or (q, k, d). Bounds involving all the four parameters (q, n, k, d) can in turn be obtained combining these with classical bounds for Hamming-metric codes, such as the Singleton or the Griesmer bound.

In this section, we develop a method to establish new inequalities that directly involve all the four parameters of a minimal code, namely (q, n, k, d). As an application, we obtain an upper bound for the minimum distance d of a minimal code in terms of (q, n, k). As we will see in the examples, this bound excludes the existence of minimal codes with parameter sets that do not violate any of the known bounds.

Our approach combines Theorem 2.8 with ideas from statistics, interpreting the weight of the codewords of a linear code as a discrete random variable and computing/estimating its mean and variance. As simple corollaries of our bounds, we recover classical results on constant-weight codes.

Throughout this section, C denotes a nondegenerate code. Our results can be made more precise when C is projective; see Section 1 for the definition.

Mean and Variance of the Nonzero Weights in a Linear Code

We start with an upper bound for the sum of the squares of the weights in a nondegenerate linear code. The proof uses one of the Pless' identities.

Lemma 3.1. Let C be a nondegenerate [n, k] q code. We have c∈C ω(c) 2 ≥ q k-2 n (q -1) [n(q -1) + 1].
Moreover, equality holds if and only if C is projective.

Proof. For i ∈ {0, . . . , n} we denote by W i (C ⊥ ) the number of codewords of weight i in the dual code C ⊥ . Since C is nondegenerate, we have W 1 (C ⊥ ) = 0. Moreover, C is projective if and only if W 2 (C ⊥ ) = 0. Using Pless' identities [START_REF] Huffman | Fundamentals of error-correcting codes[END_REF]Theorem 7.2

.3(P1)] we can write

c∈C ω(c) 2 = 2 ν=0 ν! S(2, ν) q k-ν (q -1) ν n n -ν + 4W 2 (C ⊥ )S(2, 2)q k-2 , (3.1)
where S(a, b) ≥ 0 is the Stirling number of the second kind indexed by (a, b).

Therefore c∈C ω(c) 2 ≥ 2 ν=0 ν! S(2, ν) q k-ν (q -1) ν n n -ν ,
with equality if and only if C is projective. The lemma now follows from the fact that S(2, 0) = 0 and S(2, 1) = S(2, 2) = 1.

The next step consists in defining the mean and variance of the nonzero weights in a linear code and to study the latter via Lemma 3.1. Notation 3.2. For a code C, let

E(C) := (q k -1) -1 c∈C ω(c), Var(C) := (q k -1) -1 c∈C ω(c) 2 -E(C) 2 .
We now compute/estimate these two quantities. Theorem 3.3. Let C be a nondegenerate [n, k] q code. Let ℓ = n(q -1)/(q k -1). We have E(C) = q k-1 ℓ and Var(C) ≥ q k-2 ℓ(1ℓ). Moreover, equality holds if and only if C is projective.

Proof. Since C is nondegenerate, we have

E(C) = (q k -1) -1 n i=1 (q k -q k-1 ) = n(q k -q k-1 )/(q k -1) = q k-1 ℓ.
Combining this with Lemma 3.1 we obtain

Var(C) ≥ q k-2 n(q -1)[n(q -1) + 1] q k -1 -q 2k-2 n 2 (q -1) 2 (q k -1) 2 = q k-2 ℓ[n(q -1) + 1] -ℓ 2 q 2k-2 = q k-2 ℓ(1 -ℓ),
as desired.

Remark 3.4. The quantity E(C) in Notation 3.2 expresses the average weight of C and can be used to extend Theorem 1.6 as follows. Suppose that C is a nondegenerate [n, k] q code with maximum weight w. Using E(C) ≤ w one obtains

n ≥ (n -w) q k -1 q k-1 -1 ≥ (n -w)q + 1.
In particular, if C is minimal then w ≤ nk + 1 by Proposition 1.5, from which Theorem 1.6 follows.

As an immediate consequence of Theorem 3.3 we obtain the well-known fact that constantweight codes have large length; see e.g. [START_REF] Bonisoli | Every equidistant linear code is a sequence of dual Hamming codes[END_REF]. Corollary 3.5. Let C be a constant-weight [n, k, d] q code. Then n ≥ (q k -1)/(q -1). Moreover, if C is projective then n = (q k -1)/(q -1) and d = q k-1 .

Proof. Without loss of generality, C is nondegenerate. By Theorem 3.3 we have 0 ≥ q k-2 ℓ(1-ℓ), from which ℓ ≥ 1. If C is projective then ℓ = 1 and so d = E(C) = q k-1 , as claimed.

Bounds

By applying the result of the previous subsection, we can finally derive an upper bound for the minimum distance of a code C as a function of q, n, k and the maximum weight in C. Theorem 3.6. Let C be a nondegenerate [n, k, d] q code of maximum weight w > d. Let ℓ = n(q -1)/(q k -1). We have w > n(q kq k-1 )/(q k -1) and

d ≤ q k-1 ℓ - q k-2 ℓ(1 -ℓ) w -q k-1 ℓ . (3.2)
Moreover, equality holds in (3.2) if and only if C is a projective two-weight code.

Proof. The first inequality follows from the fact that w > E(C), since C is not constant-weight.

Using the inequality of Bhatia-Davis [START_REF] Bhatia | A better bound on the variance[END_REF] we obtain

Var(C) ≤ (w -E(C))(E(C) -d).
Since C is nondegenerate and not constant-weight we have E(C) = q k-1 ℓ < w. Therefore we conclude by Theorem 3.3.

The second part of the statement follows from the fact that the bound of Theorem 3.3 is sharp if and only if C is projective, and that the Bhatia-Davis inequality is met with equality if and only if the underlying distribution takes only two values; see [START_REF] Bhatia | A better bound on the variance[END_REF]Proposition 1].

As an application of Theorem 3.6 we obtain the following bound for the minimum distance of a minimal code. Corollary 3.7. Let C be a minimal nondegenerate [n, k, d] q code. If C is not constant-weight, then nk + 1 > n(q kq k-1 )/(q k -1) and

d ≤ n(q -1)q k-2 [n -1 -q(k -1)] n(q k-1 -1) -(k -1)(q k -1) . (3.3)
In particular, we have

q k-2 n 2 -Bn + C ≥ 0, (3.4)
where

       B = q k-2 + (k -1)(2q k-1 -1) + q k-1 -1 q -1 , C = (k -1) 2 (q k -1) + (k -1)(q k -1) q -1 .
Proof. The maximum weight of C satisfies w ≤ nk + 1 by Proposition 1.5. Combining this with Theorem 3.6 one gets nk + 1 > n(q kq k-1 )/(q k -1) and

d ≤ q k-1 ℓ - q k-2 ℓ(1 -ℓ) n -k + 1 -q k-1 ℓ , (3.5)
where ℓ = n(q -1)/(q k -1). Lengthy computations show that the RHS of (3.5) is equal to the RHS of (3.3). The second part of the statement follows by combining (3.3) with Theorem 2.8, after lengthy computations.

Example 3.8. There is no minimal [START_REF] Carlet | Linear codes from perfect nonlinear mappings and their secret sharing schemes[END_REF][START_REF] Ashikhmin | Minimal vectors in linear codes[END_REF] 4 code. To see this, observe that if such a code existed, then (3.4) would give -42 ≥ 0, a contradiction. So the minimum length of a minimal code of dimension 4 over F 4 is at least 17.

Consider the parameters (q, n, k) = (4, 17, 4) and suppose that there exists an [START_REF] Chabanne | Towards secure two-party computation from the wire-tap channel[END_REF][START_REF] Ashikhmin | Minimal vectors in linear codes[END_REF] 4 nondegenerate minimal code C. Since n < (q k -1)/(q-1), C cannot be constant weight by Corollary 3.5. Therefore by Corollary 3.7 we conclude that d ≤ 10. The existence of a minimal nondegenerate [START_REF] Chabanne | Towards secure two-party computation from the wire-tap channel[END_REF][START_REF] Ashikhmin | Minimal vectors in linear codes[END_REF][START_REF] Beutelspacher | On Baer subspaces of finite projective spaces[END_REF] 4 code is therefore excluded by Corollary 3.7, but it is not excluded by any of the other known bounds for the parameters of minimal codes. Note moreover that, by Theorem 2.8, we have d ≥ 10. Therefore the minimum distance of a putative [START_REF] Chabanne | Towards secure two-party computation from the wire-tap channel[END_REF][START_REF] Ashikhmin | Minimal vectors in linear codes[END_REF] 4 nondegenerate minimal code is exactly 10 (when the largest minimum distance of an "unrestricted" [START_REF] Chabanne | Towards secure two-party computation from the wire-tap channel[END_REF][START_REF] Ashikhmin | Minimal vectors in linear codes[END_REF] 4 linear code is instead known to be 12).

Remark 3.9. The constraints imposed by Corollary 3.7 and Theorem 2.14 are in general incomparable. More precisely, each of the two results excludes the existence of some minimal codes that are not excluded by the other.

One can see that Corollary 3.7 improves on Theorem 2.14 if and only if (3.4) is violated when specialized to n = (q + 1)(k -1). After lengthy computations, one sees that this happens if and only if

k < q k-1 + 2q k-2 -2q k-3 + q -2 (q k-3 + 1)(q -1)
.

Manipulating this inequality it can be checked that Corollary 3.7 improves on Theorem 2.14 for the parameter set {(k, q) | 3 ≤ k ≤ q + 3, q ≥ 3}. When q is at least 3, this is an improvement also on Corollary 2.19. On the other hand, Theorem 2.14 provides a strictly sharper estimate than Corollary 3.7 if and only if (3.4) is satisfied for n = (q + 1)(k -1) -1. For instance, this happens for the parameter set {(k, q) : k ≥ 2q}.

We include in Table 1

Other Applications

In this short subsection we illustrate how Theorem 3.6 can be applied to study codes that are not necessarily minimal. We start with a generalization of Corollary 3.5. More precisely, we show that the relative difference between the maximum and minimum weight of a code, (wd)/n, gives a lower bound on the code's length. In other words, if the maximum and minimum weight of a code are relatively close to each other, then the code length is necessarily large.

Proposition 3.10. Let C be a nondegenerate [n, k, d] q code of maximum weight w. We have

1 n ≤ q -1 q k -1 + 1 4 w -d n 2 q k -1 q k-2 (q -1)
.

Note that in the extreme case where w = d we recover Corollary 3.5.

Proof of Proposition 3.10. Using Popoviciu's inequality for the variance, along with Theorem 3.3, we find

q k-2 ℓ(1 -ℓ) ≤ Var(C) ≤ 1 4 (w -d) 2 ,
where ℓ = n(q -1)/(q k -1). Re-arranging the terms, after tedious computations one obtains the desired inequality.

A second application of Theorem 3.6 consists in obtaining constraints on the parameters of a code having few weights. A classical result about these codes is the following theorem by Delsarte.

Theorem 3.11 (see [START_REF] Delsarte | Four fundamental parameters of a code and their combinatorial significance[END_REF]). Let C be an [n, k] q code and let s = |{ω(c) | c ∈ C, c = 0}|. We have

q k ≤ s i=0 n i (q -1) i .
Specializing to s = 2, the previous theorem shows that, for example, any two-weight [n, k] q code satisfies

q k ≤ 1 + n(q -1) + n(n -1) 2 (q -1) 2 . (3.6)
This result however does not take into account which values the weight distribution can take. Exploiting this information, Theorem 3.6 provides in general different constraints on n than those in (3.6). We illustrate this with an example.

Example 3.12. Following the notation of Theorem 3.6 and Theorem 3.

Geometric Approach

As already illustrated in Subsection 1.2, minimal codes are in one-to-one correspondence with cutting blocking sets. In this section we focus on this point of view on minimal codes, exploiting their geometric characterization to construct new, general and infinite families of minimal codes.

In particular, we provide a construction of cutting blocking sets derived from Desarguesian (r -1)-spreads of PG(rt -1, q). In turn, this leads to a an inductive construction of small cutting blocking sets or, equivalently, of minimal codes with short length. In contrast to previous approaches, our construction works over any (possibly very small) finite field.

Minimal Codes from Spreads

We start by recalling the definition of t-spread in PG(k -1, q), which we will use to obtain a new construction of minimal codes. A t-spread S of PG(k -1, q) is a partition of PG(k -1, q) in t-flats. It is well known that such a t-spread exists if and only if t + 1 divides k; see [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF]. In particular, a 1-spread of PG(k -1, q) is a partition of its points into disjoint lines and it is also called a linespread. It exists if and only if k is even. An algebraic representation of an (r -1)-spread of PG(2r -1, q) can be obtained as follows. Let γ ∈ F q r be a primitive element and let M ∈ F r×r q be the companion matrix of the minimal polynomial of γ over F q . It is well known that

F q r ∼ = F q [γ] ∼ = F q [M ] = {0}∪{M i : 1 ≤ i ≤ q r -1} as F q -algebras. For i ∈ [q r -1] define V i := {[x : xM i ] | x ∈ PG(r -1, q)}, V 0 := {[x : 0] | x ∈ PG(r -1, q)} and V q r := {[0 : y] | y ∈ PG(r -1, q)}.
Then the set {V 0 , . . . , V q r } is an (r -1)-spread of PG(2r -1, q). Theorem 4.1. Let S be the (r -1)-spread of PG(2r -1, q) defined above and let B = V 0 ∪ V i ∪ V j ∪ V q r ⊆ PG(2r -1, q), with 0 < i < j < q r . Suppose that for every s > 1 dividing r we have ji ≡ 0 mod q s -1 q-1 . Then B is a cutting blocking set. Proof. For ease of exposition we switch to vector notation, in which we represent V 0 , V i , V j , V q 2 as elements of the Grassmannian Gr q (r, 2r). In this representation we have

V 0 = rowsp(I r | 0), V q r = rowsp(0 | I r ), V i = rowsp(I r | M i ) and V j = rowsp(I r | M j ). Let H be a hyperplane in F 2r
q . We want to show that H ∩ B = H, or, equivalently, that

H ∩ B = H ∩ V 0 + H ∩ V q r + H ∩ V i + H ∩ V j has dimension at least 2r -1.
Observe first that if H contains one among the V ℓ 's, say V 0 , then there is nothing to prove, since H ∩ V 0 + H ∩ V i has already dimension (at least) 2r -1. Hence we can assume that H intersect both V 0 and V q r in an (r -1)-dimensional subspace. Then the space H ∩ V 0 + H ∩ V q r has dimension 2r -2. We can write the intersection spaces as

H ∩ V 0 = rowsp( X 1 | 0 ), H ∩ V i = rowsp(X 2 | X 2 M i ), H ∩ V q r = rowsp( 0 | X 3 ), H ∩ V j = rowsp(X 4 | X 4 M j ),
for some X 1 , X 2 , X 3 , X 4 ∈ F (r-1)×r q of rank r -1. Suppose by contradiction that H ∩ B has dimension exactly 2r -2. This implies

rowsp X 2 X 2 M i X 4 X 4 M j ⊆ rowsp X 1 0 0 X 3 ,
which in turn implies rowsp(X 2 ) = rowsp(X 4 ) = rowsp(X 1 ) and rowsp(X 3 ) = rowsp(X 2 M i ) = rowsp(X 4 M j ). Without loss of generality, we can assume that X 1 = X 2 = X 4 =: X, which reduces the above condition to rowsp(X 3 ) = rowsp(XM i ) = rowsp(XM j ).

Thus, there exists a matrix A ∈ GL(r -1, q) such that AX -XM j-i = 0. (4.1)

The matrix equation in (4.1), where the matrix X is the unknown, is a Sylvester equation. This is known to have a unique solution if the minimal polynomials of A and M j-i are coprime; see e.g. [START_REF] Horn | Matrix analysis[END_REF]Theroem 2.4.4.1]. Observe that the minimal polynomial of M j-i is irreducible of degree r, since M j-i corresponds to the element γ j-i and by the assumption on ji in the statement we have F q [γ j-i ] = F q r . Moreover, the minimal polynomial of A has degree at most r -1, and hence it is coprime with the one of M j-i 's. Therefore (4.1) has a unique solution, which is clearly X = 0. This leads to a contradiction and concludes the proof.

We now concentrate on the more general case of (r -1)-spreads in PG(rt -1, q). These can be constructed using the so-called field reduction; see [START_REF] Lavrauw | Field reduction and linear sets in finite geometry[END_REF][START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF]. This technique identifies points in PG(t -1, q r ) with (r -1)-flats in PG(rt -1, q). The idea is exactly the same as for the algebraic (r -1)-spread of PG(2r -1, q) described above. Let γ be a primitive element in F q r and let M be the companion matrix of the minimal polynomial of γ over F q . As already explained, there is an isomorphism F q r ∼ = F q [M ] = {0} ∪ {M i : 1 ≤ i ≤ q r -1}, which we call φ.

We can then extend it to vectors in F t q r componentwise, obtaining an injective map

ϕ : F t q r -→ F r×rt q (v 1 , . . . , v t ) -→ (φ(v 1 ) | . . . | φ(v t )).
This map can in turn be extended to a map φ : PG(t -1, q r ) -→ Gr q (r, tr), the Grassmannian, defined by P = [v] -→ rowsp(ϕ(v)). Note that φ is well-defined since it does not depend on the choice of the representative v for the point P . Indeed, for a nonzero scalar multiple of v, say γ i v, we have ϕ(γ i v) = M i ϕ(v) and since M i is invertible, rowsp(M i ϕ(v)) = rowsp(ϕ(v)).

It is then well-known that Im( φ) is a (vectorial) r-spread of F rt q , which naturally gives rise to a projective (r -1)-spread of PG(rt -1, q). Such a spread is known as Desarguesian spread; see [START_REF] Segre | Teoria di Galois, fibrazioni proiettive e geometrie non desarguesiane[END_REF].

In the sequel we will need the following special points in PG(t -1, q r ): P ℓ := [e ℓ ] for ℓ ∈ [t] and Q ℓ,m,i := [u ℓ,m,i ], where u ℓ,m,i := e ℓ + γ i e m for 1 ≤ ℓ < m ≤ t and i ∈ [q r -1]. These will be used in the next result to extend the construction of Theorem 4.1 from two to t blocks. Theorem 4.2. For each pair of integers (ℓ, m) such that 1 ≤ ℓ < m ≤ t, let j ℓ,m , i ℓ,m ∈ [q r -1] be integers with the following property: for all s > 1 dividing r, j ℓ,mi ℓ,m ≡ 0 mod q s -1 q-1 . Define the set

T := 1≤ℓ≤t φ(P ℓ ) ∪ 1≤ℓ<m≤t ( φ(Q ℓ,m,i ℓ,m ) ∪ φ(Q ℓ,m,j ℓ,m )) .
Then the projectivization of T is a cutting blocking set in PG(rt -1, q). Proof. Once again we work in vector notation. Let H be a hyperplane in F rt q . Let a := |{ℓ : φ(P ℓ ) ⊆ H}|. Then 0 ≤ a ≤ t -1 and dim( H ∩ T ) ≥ ra + (r -1)(ta). Without loss of generality assume that {ℓ : φ(P ℓ ) ⊆ H} = [a]. Hence H ∩ T contains the span of the first a • r standard basis vectors. By taking the quotient on this span, we reduce ourselves to proving the same statement for a = 0, replacing t by ta. Therefore we can also assume a = 0 without loss of generality.

We have that Λ := H ∩ ℓ φ(P ℓ ) has dimension (r -1)t. For all integers 1 ≤ ℓ < m ≤ t, define S ℓ,m := φ(P ℓ ) ∪ φ(P m ) ∪ φ(Q ℓ,m,i ℓ,m ) ∪ φ(Q ℓ,m,j ℓ,m ), Π ℓ,m := φ(P ℓ ) ∪ φ(P m ) = e i : (ℓ -1)r + 1 ≤ i ≤ ℓr, or (m -1)r ≤ i ≤ mr .

Then H ∩ Π ℓ,m is a hyperplane in Π ℓ,m ∼ = F 2r q . Moreover, using the same argument as in the proof of Theorem 4.1, there exists a vector v ℓ,m ∈ (H ∩ Π ℓ,m ) ∩ S ℓ,m ⊆ H ∩ S ℓ,m such that v ℓ,m / ∈ H ∩ ( φ(P ℓ ) ∪ φ(P m )) . Observe that the support of v ℓ,m is contained only in the ℓ-th and the m-th blocks and that we can write v ℓ,m = w ℓ,m ∈ φ(P j ) , i.e., it has support contained only in the j-th block, for j ∈ {ℓ, m}. Now consider the t -1 vectors v 1,2 , . . . , v 1,t . Since a = 0, none of the v 1,i 's belongs to Λ. It is left to show that for each i ≥ 3 we have v 1,i / ∈ Γ i-1 := Λ + v 1,2 , . . . , v 1,i-1 . By contradiction, suppose that v 1,i ∈ Γ i-1 . Let ρ i : F rt q → F r q denote the projection on the i-th block. We have

w (i) 1,i = ρ i (v 1,i ) ∈ ρ i (Γ i ) = H ∩ φ(P i ) ,
since, by construction, the i-th block of any vector in Γ i-1 is equal to the i-th block of some element in φ(P i ) ∩ H. Therefore, also the vector w

(1)

1,i = v 1,i -w (i)
1,i belongs to H. This means that v 1,i ∈ H ∩ ( φ(P 1 ) ∪ φ(P i )) ⊆ Λ, which leads to a contradiction.

Remark 4.3. The construction of Theorem 4.2 for r = t = 2 (or, equivalently, the one of Theorem 4.1 for r = 2) coincides with the construction of cutting blocking sets of [19, Theorem 3.7], which consists of 4 disjoint lines in PG (3, q). Therefore, Theorem 4.2 can be viewed as a generalization of that result.

Example 4.4. We explicitly construct a cutting blocking set in PG(5, q) as explained in Theorem 4.2, with r = 2 and t = 3. We take as γ a primitive element of F q 2 whose minimal polynomial over F q is x 2p 1 xp 0 . We have P 1 = [1 : 0 : 0], P 2 = [0 : 1 : 0], P 3 = [0 : 0 : 1] and choose the following points in PG(2, q 2 ): Q

1,2,q 2 -1 = [1 : 1 : 0], Q 1,2,1 = [1 : γ : 0], Q 1,3,q 2 -1 = [1 : 0 : 1], Q 1,3,1 = [1 : 0 : γ], Q 2,3,q 2 -1 = [0 : 1 : 1], Q 2,3,1 = [0 : 1 : γ].
Therefore the set T is T = {(x, y, 0, 0, 0, 0) : x, y ∈ F q } ∪ {(0, 0, x, y, 0, 0) : x, y ∈ F q } ∪ {(0, 0, 0, 0, x, y) : x, y ∈ F q } ∪ {(x, y, x, y, 0, 0) : x, y ∈ F q } ∪ {(x, y, y, p 0 x + p 1 y, 0, 0) : x, y ∈ F q } ∪ {(x, y, 0, 0, x, y) : x, y ∈ F q } ∪ {(x, y, 0, 0, y, p 0 x + p 1 y) : x, y ∈ F q } ∪ {(0, 0, x, y, x, y) : x, y ∈ F q } ∪ {(0, 0, x, y, y, p 0 x + p 1 y) : x, y ∈ F q }. The projectivization of T gives the desired cutting blocking set in PG(5, q).

Inductive Constructions of Cutting Blocking Sets

As already observed in the Introduction, of particular interest is the study minimal codes of small length for a given dimension. Formally, for a fixed positive integer k and a prime power q, we are interested in determining the value of m(k, q) := min {n ∈ N ≥1 | there exists a minimal [n, k] q code} . This function has been explicitly studied in [START_REF] Lu | The parameters of minimal linear codes[END_REF], where it was observed that m(2, q) = q + 1 and that

q(k -1) + 1 ≤ m(k, q) ≤ (q -1) k 2 + k, (4.2)
(r -1)-flats in PG(k -1, q), where r is the smallest prime dividing k. However, when such a prime is big, the resulting code turns out to be quite long. The discussion in the previous paragraph motivates us to look for alternative constructions of minimal codes, with the ultimate goal of covering a larger dimension range. Our next move in this direction is an inductive result that allows us to construct a cutting blocking set in PG(k, q) starting from a smaller one in PG(k -1, q). The following result has already been shown in [START_REF] Davydov | Linear nonbinary covering codes and saturating sets in projective spaces[END_REF]Construction A]. We include a proof for completeness. Proposition 4.9 (see [START_REF] Davydov | Linear nonbinary covering codes and saturating sets in projective spaces[END_REF]Theorem 3.10]). Let B ′ be a cutting blocking set in PG(k -1, q). Fix a hyperplane Λ ⊆ PG(k, q) and take an isomorphic image T of B ′ in Λ. Moreover, select k points P 1 , . . . , P k ∈ T not lying all in the same (k -2)-flat and a point P ∈ PG(k, q) \ Λ. Define the lines ℓ i := P i , P . Then the set

B := T ∪ k i=1 ℓ i \ {P i }
is a cutting blocking set in PG(k, q). In particular, for every k ∈ N ≥1 we have

m(k + 1, q) ≤ m(k, q) + (q -1)k + 1. Proof. Let H be a hyperplane in PG(k, q). If H = Λ, then clearly H ∩ B = H. If H = Λ, then we have that Λ 0 := H ∩ Λ is a hyperplane in Λ. Hence H ∩ T = Λ 0 ∩ T = Λ 0 .
Moreover, H meets each of the lines ℓ i 's in a point Q i . Observe that not all of them can lie in Λ, because otherwise we would have Q i = P i for every i and H = Λ. Therefore, there exists a point Q i ∈ (ℓ i ∩ H) \ T . This implies that Q i ∈ H ∩ B \ Λ 0 and we can conclude that H ∩ B = H. Proposition 4.9 shows how to construct a cutting blocking set in PG(k, q) which contains a copy of a cutting blocking set T in PG(k -1, q). This is achieved by adding (q -1)k + 1 points to T . Moreover, among cutting blocking sets containing a copy of a smaller cutting blocking set (of codimension 1), the construction of Proposition 4.9 is optimal, as shown by the following result.

Proposition 4.10. Let B ⊆ PG(k, q) be a cutting blocking set such that it contains (an isomorphic image of) a cutting blocking set B ′ of PG(k -1, q). Then

|B| ≥ |B ′ | + (q -1)k + 1.
Proof. Let B be a cutting blocking set in PG(k, q) and suppose it contains a copy B ′ of a cutting blocking set in PG(k -1, q). Then B ′ is contained in a hyperplane H. By the correspondence between linear codes and projective systems (see page 5) we have

d ≤ |B| -|B ∩ H| ≤ |B| -|B ′ |.
Combining this with Theorem 2.8 we obtain the desired inequality. Remark 4.11. Proposition 4.10 shows that the inductive construction from Proposition 4.9 gives rise to a cutting blocking set that is minimal among all the cutting blocking sets containing a given cutting blocking set of codimension 1. It is interesting to observe that starting from PG(1, q) and iterating this construction k times, one obtains the tetrahedron, which is, therefore, minimal among the cutting blocking sets in PG(k -1, q) containing an isomorphic copy of a cutting blocking set of PG(i, q) for each i ≤ k -2. Note that its cardinality is ∼ 1 2 qk 2 for k large.

All of this seems to suggest that in order to obtain cutting blocking sets in PG(k -1, q) of size m(k, q) (or at least linear in k) one should look at sets that do not contain (isomorphic copies of) smaller cutting blocking sets.

Explicit Constructions of Short Minimal Codes

In this final subsection we combine the results obtained so far to construct minimal codes of short length. To our best knowledge, this constructions produce the shortest known minimal codes, for infinitely many dimensions and field sizes. In particular, the construction applies to all those pairs (k, q) for which the rational normal tangent set of [START_REF] Fancsali | Lines in higgledy-piggledy arrangement[END_REF] cannot be constructed in PG(k -1, q). Construction A. Assume that k = 2t, for some t ∈ N ≥1 . We use the construction from Theorem 4.2, selecting t 2 = k 2 4 disjoint lines from a linespread. The union of these t 2 lines a cutting blocking set in PG(k -1, q), and we denote the corresponding code by C k,q .

Proposition 4.12. The code C k,q of Construction A is a minimal [(q + 1) k 2 2 , k, q(k -1)] q code.

Proof. The minimality of C k,q trivially follows from the fact that the associated projective system is a cutting blocking set; see Theorem 4.2. The length of the code C k,q coincides with the cardinality of the cutting blocking set, which is (q + 1) k 2 4 . Therefore it remains to show that d = q(k -1). By the correspondence between projective systems and linear codes and Definition 1.8, we have that d = ns = (q + 1)t 2s, where k = 2t and s := max{| H ∩ T | : H ⊆ PG(k -1, q), dim( H) = k -2}, where T is the projectivization of the set T defined in Theorem 4.2. We switch to vector notation and let A ℓ,m = { φ(P ℓ ), φ(P m ), φ(Q ℓ,m,i ℓ,m ), φ(Q ℓ,m,j ℓ,m )} for all 1 ≤ ℓ < m ≤ t. Let H be a hyperplane of F k q = F 2t q . Define the set H T := {i : φ(P i ) ⊆ H} and the integers a := |H T | and a ℓ,m := |{A ∈ A ℓ,m : A ⊆ H}| for 1 ≤ ℓ < m ≤ t. Moreover, let b denote the number of lines forming T that are fully contained in the projectivization H of H. Since each of the lines forming T either intersects H in a point, or it is contained in H, we have s = (q + 1)b + t 2b = qb + t 2 .

(4.4)

Therefore, finding the maximum of s is the same as finding the maximum value of b. Now observe that a cannot be equal to t, as otherwise H would contain a basis of F 2t q . Moreover, we have that a ℓ,m ∈ {0, 1, 4}. Indeed, by construction, any two subspaces in A ℓ,m span the same 4-dimensional subspace, and if H contains two of them, then it contains all of them. It is readily seen that we have where the second equality and the inequality both follow from the fact that a ℓ,m can only be equal to 0, 1 or 4. The function f t is a quadratic polynomial in a with second derivative equal to 3 > 0. Hence, the maximum in the interval [0, t -1] is attained in one of the two interval extremes. One can see that this happens when a = t -1, from which b ≤ (t -1) 2 . Finally, combining this with (4.4) we have s = qb + t 2 ≤ q(t -1) 2 + t 2 = (q + 1)t 2q(2t -1) and d ≥ (q + 1)t 2s = q(2t -1) = q(k -1).

On the other hand, we can take any hyperplane H ′ containing φ(P i ), for each i ∈ [t -1]. The projectivization of such a hyperplane contains exactly b = (t -1) 2 lines forming T , and therefore n -| H′ ∩ T | = q(k -1).

Example 4.13. Let k = 6 and take the cutting blocking set obtained in Example 4.4. This is a cutting blocking set arising from Construction A. When q = 2, we take γ to be a root of x 2 + x + 1 and obtain a minimal [START_REF] Hwang | Decoding linear block codes for minimizing word error rate[END_REF][START_REF] Ball | On the size of a double blocking set in PG(2, q)[END_REF] 2 code C 6,2 whose generator matrix is

       
1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0

        .
Our second construction combines Theorem 4.2 with the concept of a Baer subplane.

Construction B. Assume that k = 3t for some t ∈ N and that q is a square. We first use the construction from Theorem 4.2 by selecting t 2 = k 2 9 disjoint planes from a 2-spread. Then we choose two disjoint Baer subplanes in each of these planes. The union of the selected 2t 2 Baer subplanes is a cutting blocking set in PG(k -1, q), and we denote the corresponding code by D k,q .

Proposition 4.14. The code D k,q of Construction B is a minimal [(q + √ q + 1) 2k 2 9 , k, d] q code, where d ≥ q 4 3 k -2 .

Proof. The minimality of D k,q trivially follows from the fact that the associated projective system B is a cutting blocking set (Theorem 4.2 and Proposition 4.5). The length of the code D k,q coincides with the cardinality of the cutting blocking set, which is (q + √ q + 1) 2k 2 9 . We only need to prove that d ≥ q 4 3 k -2 . We let k = 3t and proceed as before, finding an upper bound on s := max{| H ∩ B| : H ⊆ PG(k -1, q), dim( H) = k -2}.

Observe that B is obtained by first forming the cutting blocking set T as in Theorem 4.2, which is the union of t 2 planes Λ 1 , . . . , Λ t 2 , and then selecting two disjoint Baer subplanes B i,1 , B i,2 in each Λ i . Let H be a hyperplane in PG(k -1, q) and let b denote the number of planes Λ i that are fully contained in H. With this notation, we have |B ∩ H| = 2b(q + √ q + 1) + i : Λ i ⊆ H |B i,1 ∩ H| + |B i,2 ∩ H| ≤ 2(q + √ q + 1)b + 2( √ q + 1)(t 2b),

where the last inequality follows from the fact that a hyperplane H meets a Baer subplane in either 1, √ q + 1 or q + √ q + 1 points. Moreover, arguing as in the proof of Proposition 4.12, one proves that b ≤ (t-1) 2 . Combining this with (4.5) we obtain that s ≤ 2(q + √ q +1)t 2 -2q(2t-1)

and finally d = ns ≥ q 4 3 k -2 .

We conclude with a remark that summarizes the code lengths obtained from the constructions and results of this section. Remark 4.15. For every positive integer k and every prime power q, we have provided explicit constructions of minimal [n k,q , k] q codes with

n k,q =            1 4 (q + 1)k 2 if k ≡ 0 mod 2, 2 9 (q
+ √ q + 1)k 2 if k ≡ 0 mod 3 and q is a square, 2 9 (q + √ q + 1)(k -1) 2 + (q -1)(k -1) + 1 if k ≡ 1 mod 3 and q is a square, 1 4 (q + 1)(k + 1) 2 -(2k + q -2) otherwise.

b

  = a + ℓ,m∈H T , ℓ<m (a ℓ,m -2) + ℓ∈H T ,m / ∈H T , ℓ<m (a ℓ,m -1) + ℓ / ∈H T ,m∈H T , ℓ<m(a ℓ,m -

Table 1 :

 1 three collections of parameter sets that are excluded by Theorem 2.14 and Corollary 3.7. The first column contains parameters that are excluded by both results, while the other two contain parameters that are excluded by either Theorem 2.14 or Corollary 3.7 (and not by both). Code parameters for which the existence of minimal codes is excluded by Theorem 2.14 and/or Corollary 3.7.

	Some parameters of	Some parameters of	Some parameters of
	minimal codes excluded	minimal codes excluded	minimal codes excluded
	by both Theorem 2.14 and	by Theorem 2.14 and not	by Corollary 3.7 and not
	Corollary 3.7	by Corollary 3.7	by Theorem 2.14
	[8, 4] 2	[17, 7] 2	[16, 5] 3
	[15, 5] 3	[31, 9] 3	[16, 4] 4
	[24, 6] 4	[44, 10] 4	[25, 6] 4
	[35, 7] 5	[99, 21] 4	[36, 7] 5
	[63, 9] 7	[65, 12] 5	[26, 4] 7

  [START_REF] Beutelspacher | On Baer subspaces of finite projective spaces[END_REF], let (q, k, s, d, w) =[START_REF] Alon | Combinatorial nullstellensatz[END_REF][START_REF] Bartoli | Minimal linear codes in odd characteristic[END_REF][START_REF] Alon | Combinatorial nullstellensatz[END_REF][START_REF] Carlet | Linear codes from perfect nonlinear mappings and their secret sharing schemes[END_REF][START_REF] Geil | Weighted Reed-Muller codes revisited[END_REF]. We look for a nondegenerate binary two-weight code C of dimension 8 having weights 16 and 24. The constraints imposed on n by Theorem 3.6 imply 34 ≤ n ≤ 45, where the upper bound is met with equality if C is projective. The constraint imposed by (3.6) is instead n ≥ 23. It is known that there exists a projective binary two-weight code of parameters (n, k, d, w) = (45,[START_REF] Bartoli | Minimal linear codes in odd characteristic[END_REF][START_REF] Carlet | Linear codes from perfect nonlinear mappings and their secret sharing schemes[END_REF][START_REF] Geil | Weighted Reed-Muller codes revisited[END_REF].

While preparing the final version of this manuscript, we realized that the same conjecture has been also established in a recent preprint[START_REF] Tang | Full characterization of minimal linear codes as cutting blocking sets[END_REF], using different methods. The approach developed in this paper also serves to describe the structure of codes that are not necessarily minimal, proving general properties of their maximal codewords.

* Gianira N. Alfarano was supported by the Swiss National Science Foundation through grant no. 188430. † Alessandro Neri was supported by the Swiss National Science Foundation through grant no. 187711.

where the upper bound is constructive (the tetrahedron from page 6). The same results were independently obtained in [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF], where shorter minimal codes are constructed for k ∈ {3, 4, 5}. In this notation, Theorem 2.14 improves on the lower bound in (4.2), reading m(k, q) ≥ (q + 1)(k -1).

We already obtained improvements on this bound in Corollary 2.19 and Corollary 3.7, as shown in Table 1.

In [START_REF] Chabanne | Towards secure two-party computation from the wire-tap channel[END_REF] it has been shown that the upper bound on m(k, q) in (4.2) is far from being tight. More precisely, one has m(k, q) ≤ 2k log q q 2 q 2 -q+1 ,

indicating that, in principle, for a fixed q and k large enough one might construct much shorter minimal codes. In particular, a natural problem is that of finding, for a fixed q, an infinite family of minimal codes over F q whose length is linear in k. This problem is naturally motivated by the goal of explicitly constructing asymptotically good minimal codes. Indeed, while these codes are known to be asymptotically good, the proofs in [START_REF] Alfarano | A geometric characterization of minimal codes and their asymptotic performance[END_REF][START_REF] Cohen | On minimal and quasi-minimal linear codes[END_REF] are not constructive, as well as the bound in (4.3). We are currently unaware of any explicit general construction of minimal codes whose length is unbounded for a fixed q, and that are asymptotically shorter than the tetrahedron; see also the discussion in Remark 1.15.

In the sequel, we introduce two new families of minimal codes whose lengths are shorter than the one of the tetrahedron by a factor 2 and by a factor 9 4 , respectively. We start with a result that represents a first step towards inductive constructions of cutting blocking sets. Proposition 4.5. Let B = B 1 ∪ . . . ∪ B r be a cutting blocking set in PG(N, q). For each i ∈ [r], let Γ i := B i ∼ = PG(n i , q) for some n i ≤ N and let B ′ i ⊆ Γ i be the isomorphic image of a cutting blocking set in PG(n i , q). Then B ′ := B ′ 1 ∪ . . . ∪ B ′ r is a cutting blocking set.

Proof. Let H be a hyperplane in PG(N, q). We want to show that H ∩ B ′ = H. By hypothesis we have that

Consider the spaces Λ

We now examine two cases separately. Case I:

i is a cutting blocking set in B i , and hence

We are now ready to combine the above result with Theorem 4.2 and derive a recursive upper bound on m(k, q). Theorem 4.6. For all positive a, b ∈ N, m(ab, q) ≤ a 2 m(b, q). Proof. By Theorem 4.2 we know that we can construct a cutting blocking set in PG(ab -1, q) with the aid of a (b -1)-spread. More precisely, we only need to take a 2 disjoint (b -1)-flats Γ 1 , . . . , Γ a 2 ∼ = PG(b -1, q) from the spread. By Proposition 4.5, for each of them we can take the isomorphic image of a cutting blocking set in PG(b -1, q) with minimum cardinality m(b, q). Therefore, we finally obtain a cutting blocking set in PG(ab -1, q) of cardinality a 2 m(b, q).

Observe that the proof of Theorem 4.6 gives an explicit way of constructing a minimal [a 2 m(b, q), ab] q code, provided that there exists already a construction for an [m(b, q), b] q minimal code. We illustrate how this construction works with the following example.

Example 4.7. We fix k = 6 = 3 • 2 and assume q to be a square. Observe that under these assumptions we know the exact values of m(2, q) and m(3, q); see Section 1.2. Namely, we have m(2, q) = q + 1 and

Now we can use Theorem 4.6 in two ways. On the one hand, we deduce that m(6, q) ≤ 9 • m(2, q) = 9(q + 1).

Such a construction is obtained by taking 9 lines from a linespread in PG(5, q) as explained also in Example 4.4. On the other hand, by interchanging the roles of 2 and 3 we obtain

The corresponding cutting blocking set is constructed by first selecting 4 planes in PG(5, q) via Theorem 4.1, and then by choosing, in each of these planes, a minimal 2-fold blocking set: when q = 4, we take 3 lines not intersecting all in the same point; when q ≥ 9, we choose 2 disjoint Baer subplanes. It is easy to check that for q < 64 the cutting blocking set consisting of 9 lines is smaller, while for q ≥ 64 the 8 Baer subplanes give rise to a cutting blocking set with smaller cardinality. Notice that both constructions produce a smaller cutting blocking set than the tetrahedron, which contains 15q -9 points. For instance, let us consider the case q = 4. The 9 lines give rise to a minimal [45, 6] 4 code, the 8 Baer subplanes lead to a minimal [56, 6] 4 code, while the tetrahedron provides a [66, 4] 4 code. If we take q = 64, then the three constructions produce minimal codes whose parameters are [585,[START_REF] Ball | On the size of a double blocking set in PG(2, q)[END_REF] 64 , [584,[START_REF] Ball | On the size of a double blocking set in PG(2, q)[END_REF] 64 and [966, 6] 64 , respectively.

Remark 4.8. Very recently, a construction of cutting blocking sets in PG(5, q) as union of seven disjoint lines has been given in [START_REF] Bartoli | On cutting blocking sets and their codes[END_REF]. This gives an improvement on the known upper bound for m(6, q). In the same work, a construction of a cutting blocking set in PG(3, q 3 ) of size 3(q 3 + q 2 + q + 1) has been obtained as union of three suitable disjoint q-order subgeometries.

These results together yield the following bounds: m(4, q 3 ) ≤ 3(q 3 + q 2 + q + 1), m(6, q) ≤ 7(q + 1).

The proof of Theorem 4.6, which constructs minimal codes of dimension k = ab, heavily relies on the existence of a smaller minimal code, whose dimension divides k. Clearly, this recursive construction does not cover all dimensions, as for instance it does not provide any nontrivial minimal code of prime dimension. While for k = 5 one can rely on the construction provided in [1, Construction 2], which gives a [8q -3, 5] q minimal code, for primes greater than 5 we are not (yet) able to construct any short minimal code different from the tetrahedron. Also, we are not (yet) able to construct short minimal codes of odd dimension, unless the latter is divisible by 3 and q is a square. When k is odd one can construct minimal codes taking several The first length is given by Construction A, the second length is given by Construction B, and the last two lengths are obtained by combining Proposition 4.9 with these two constructions. It is easy to see that the minimum distance d of any code obtained using Proposition 4.9 meets the bound of Theorem 2.8 with equality, i.e., d = (q -1)(k -1) + 1.


à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.