Minjia Shi

Xiaoxiao Li

Alessandro Neri

Patrick Solé

How many weights can a cyclic code have ? *

Keywords: cyclic codes, irreducible cyclic codes, Hamming codes, Reed-Muller codes

Upper and lower bounds on the largest number of weights in a cyclic code of given length, dimension and alphabet are given. An application to irreducible cyclic codes is considered. Sharper upper bounds are given for the special cyclic codes (called here strongly cyclic), whose nonzero codewords have period equal to the length of the code. Asymptotics are derived on the function Γ(k, q), that is defined as the largest number of nonzero weights a cyclic code of dimension k over F q can have, and an algorithm to compute it is sketched. The nonzero weights in some infinite families of Reed-Muller codes, either binary or q-ary, as well as in the q-ary Hamming code are determined, two difficult results of independent interest.

Introduction

Recently, a series of works has been released on the study of the weight set of a code. In [START_REF] Shi | How many weights can a linear code have?[END_REF] Shi et al. conjectured that the maximum number of nonzero weigths that a k-dimensional block code over F q can have is q k -1 q-1 , giving an answer only for the case q = 2 or k = 2. The complete proof of this conjecture was given in [START_REF] Alderson | Maximum weight spectrum codes[END_REF] where the two authors provided two different constructions, and independently in [START_REF] Meneghetti | On linear codes and distinct weights[END_REF]. Shorter codes with the maximum number of weights for a given dimension were then discussed in [START_REF] Alderson | A note on full weight spectrum codes[END_REF][START_REF] Cohen | Maximum weight spectrum codes with reduced length[END_REF]. In the present paper we address the same type of questions for cyclic codes. Thus, we study the function Γ(k, q), defined as the largest number of nonzero weights a cyclic code of dimension k over F q can have. We derive upper bounds on that quantity by simple counting arguments bearing on the cycle structure of the code. An alternative approach is to use weight concentration theorems, derived first in [START_REF] Lidl | Finite fields[END_REF] in the language of linear recurrences. In the case of cyclic codes whose nonzero codewords have period equal to the length (called strongly cyclic codes in the sequel) we obtain smaller upper bounds than the ones derived for the class of all cyclic codes. This suggests to study Γ 0 (k, q), that is the largest number of nonzero weights a strongly cyclic code of dimension k over F q can have. This discrepancy in behaviour between Γ(k, q), and Γ 0 (k, q), is particularly evident in the asymptotic upper bounds. We also derive lower bounds on these two functions, using special codes, or the covering radius of the dual code. An algorithm is given to compute Γ(k, q), for small values of kq. A first appendix derives the number of weights in several infinite families of q-ary Reed-Muller codes, including the extended Hamming code and some binary, ternary and quinary Reed-Muller codes. A second appendix derives the number of weights in the q-ary Hamming code when q > 2. These last two technical results are of interest in their own right. While generating functions or recursions [START_REF] Kim | Weight distributions of Hamming codes[END_REF] are known in these cases, they are insufficient to determine the explicit weights in general. Exact enumeration of cyclic codes can require some deep techniques of Number Theory [START_REF] Hurt | Exponential Sums and Coding Theory: A Review[END_REF]. In particular, the codes of Melas and Zetterberg give interesting lower bounds for a wide range of parameters. The use of the celebrated Delsarte bound on the covering radius of codes [START_REF] Cohen | Covering codes[END_REF], leads us to define a new combinatorial function (T [n, k]) of independent interest. The material is organized as follows. The next section collects some background material on linear codes and cyclic codes. Section 3 is dedicated to upper bounds and Section 4 to lower bounds. Section 5 derives the asymptotic version of some of the preceding bounds. Section 6 gives an algorithm to compute Γ(k, q). Section 7 concludes the paper and mentions some challenging open problems. Appendix I derives the weight spectrum of some families of q-ary Reed-Muller codes. Appendix II determines the weights in the q-ary Hamming code for q ≥ 3.

Definitions and Notation

Linear codes

A (linear) code C of length n over a finite field F q is a F q vector subspace of F n q . The dimension of the code is its dimension as a F q vector space, and is denoted by k. The elements of C are called codewords.

The dual C ⊥ of a code C is understood with respect to the standard inner product.

The (Hamming) weight of x ∈ F N q is the number of indices i where x i = 0, and it is denoted by w H (x). The minimum nonzero weight d of a linear code is called the minimum distance. The dual distance of a code is the minimum distance of its dual. Every linear code satisfies the Singleton bound [START_REF] Macwilliams | The theory of error correcting codes[END_REF]Th 11,Chap. 1]

on its parameters d ≤ n -k + 1.
A code meeting that bound is called maximum distance separable (MDS). See [START_REF] Macwilliams | The theory of error correcting codes[END_REF]Chap. 11] for general knowledge on this family of codes.

Cyclic codes

A cyclic code of length n over a finite field F q is a F q linear code of length n invariant under the coordinate shift. Under the polynomial correspondence such a code can be regarded as an ideal in the ring F q [x]/(x n -1). It can be shown that this ideal is principal, with a unique monic generator g(x), called the generator polynomial of the code. The check polynomial h(x) is then defined as the quotient (x n -1)/g(x). A well-known fact is that the codewords satisfy a linear recurrence of characteristic polynomial the reciprocal polynomial of h(x) [16, p. 195]. Thus any codeword c can be continued by repetition into a bi-infinite periodic sequence c which is periodic of least period a divisor of n. The period of a codeword c is understood to be the smallest integer T 0 such c i+T 0 = c i for all integers i. Thus, the period is always a divisor of n. A cyclic code is irreducible over F q if its check polynomial h(x) is irreducible over

F q [x]. The period of a polynomial h(x) ∈ F q [x], such that h(0) = 0 is the smallest integer t such that h(x) divides x T -1 over F q [x].
If C is a cyclic code, its codewords are partitioned into orbits under the action of the shift. We call these orbits the cyclic classes of C.

Combinatorial functions

Here we introduce the combinatorial functions we are going to study in this work. Let q be a prime power, 0 ≤ k ≤ n be non negative integers. We define Γ(k, q) as the largest number of nonzero weights of a cyclic code of dimension k over F q . Moreover, we define Γ(n, k, q) as the largest number of nonzero weights of a cyclic code of fixed length n and dimension k over F q , if such a code exists, and by zero otherwise. The same functions for strongly cyclic codes (to be defined below) are denoted by Γ 0 (k, q), and Γ 0 (n, k, q), respectively. Recall also the functions L(k, q) and L(n, k, q) introduced in [START_REF] Shi | How many weights can a linear code have?[END_REF], that represent respectively the maximum number of nonzero weights that a linear code of dimension k over F q , and the maximum number of nonzero weights for linear codes with a fixed length n. The function L(k, q) was completely determined and shown to be equal to q k -1 q-1 in [START_REF] Alderson | Maximum weight spectrum codes[END_REF], while for L(n, k, q) some partial answers were given in [START_REF] Alderson | A note on full weight spectrum codes[END_REF][START_REF] Shi | How many weights can a linear code have?[END_REF].

Upper bounds

Cycle structure

Let ρ : F n q -→ F n q denote the cyclic shift operator.

Lemma 1. Let C be an [n, k] q cyclic code and c ∈ C be a codeword of period t. Let moreover α ∈ F * q and i ∈ {0, . . . , n -1} such that

αc = ρ i (c).
Then, α r = 1, where r = t gcd(t,i) . Moreover, α belongs to the unique cyclic subgroup of F * q of order gcd(t, q -1). Proof. Let c be a codeword of period t and suppose αc = ρ i (c). Then c = ρ ri (c) = α r c, and this implies α r = 1. Let now H be the unique subgroup of F * q of order gcd(t, q -1). Since by definition r|t and also α q-1 = 1, we get α gcd(t,q-1) = 1, i.e. α ∈ H.

If C is a cyclic code, denote by B t the number of nonzero codewords of period t it contains. A cyclic code such that B t = 0 for 1 ≤ t < n shall be called strongly cyclic.

Lemma 2. If C is an [n, k] q cyclic code with s nonzero weights, then

s ≤ t|n B t lcm(t, q -1) ≤ 1 + 1<t|n B t lcm(t, q -1)
.

Proof. The number of cyclic classes of codewords of period t is at most Bt t . All codewords in the same class share the same weight. Then, we use the Lemma above. Let c be a codeword and H be the unique subgroup of F * q of order gcd(t, q -1). Now, for every representative α of F * q /H, the codeword αc gives a different class that obviously shares the same weight of the one of c. Hence, there are at most Bt gcd(t,q-1)

t(q-1) = Bt lcm(t,q-1)
distinct weights among these codewords, and this shows the first inequality. The second directly follows from the fact that if a codeword has period 1 then it is necessarily a multiple of the vector of all ones, and therefore B 1 ∈ {0, q -1}.

Example. Consider the code of dimension 2 over F 5 , with length 20 and check polynomial x 2 + x -1. This code contains the Fibonacci numbers read mod 5 [22, A082116]. It can be checked to contain 4 codewords of period 4 (namely 1, 3, 4, 2, repeated five times) and 20 codewords of period 20.

This simple counting lemma has two important applications. First, we improve the upper bound on L(k, q) of [21, Prop. 2] by a factor of at least n q-1 for some large class of cyclic codes, up to a factor n for another subclass.

Theorem 1. If C is a [n, k] q strongly cyclic code with s nonzero weights, then s ≤ q k -1 lcm(q -1, n) .
Thus Γ 0 (n, k, q) ≤ q k -1 lcm(q-1,n) .

Proof. We apply Lemma 2 when B t = 0 for t < n, so that the sum in the right handside contains only one summand.

One can observe that the function Γ 0 (n, k, q) has an intrisecly different behaviour than the one of L(n, k, q). Indeed, it was proved in [START_REF] Alderson | A note on full weight spectrum codes[END_REF] L(n, k, q) = q k -1 q-1 for n ≥ q 3k-4 , while it is easy to see that a strongly cyclic code with that restriction on n can not exist, i.e. Γ 0 (n, k, q) = 0 for n ≥ q 3k-4 (it is actually already true for n ≥ q k by Theorem 1). This also implies that lim n→∞ Γ 0 (n, k, q) = 0, and this is in contrast to the behaviour of the function L(n, k, q) that is non decreasing in n and lim n→∞ L(n, k, q) = L(k, q), As a second implication of Lemma 2, in the general case when many of the B t 's are nonzero, we can prove the following result.

Theorem 2. If C is an [n, k] q cyclic code with s nonzero weights, then s ≤ 1 + (q k -1) 1<t|n 1 lcm(t, q -1) 2 1 2 .
Proof. From the second inequality in Lemma 2, we get

s -1 ≤ 1<t|n B t lcm(t, q -1)
.

Squaring both sides of this inequality and applying Cauchy-Schwarz inequality we obtain

(s -1) 2 ≤ 1<t|n B 2 t 1<t|n 1 lcm(t, q -1) 2 .
By definition of the B t 's note that t|n B t = q k -1, implying t|n B 2 t ≤ (q k -1) 2 . The result follows by taking the square root of both sides.

Character sums

The following result can be derived by using the character sums techniques of [START_REF] Lidl | Finite fields[END_REF]Chapt. 8].

Theorem 3. If C is an [n, k] q strongly cyclic code with s nonzero weights, then s ≤ 2 1 - 1 q q k/2 . Thus Γ 0 (n, k, q) ≤ 2 1 - 1 q q k/2 .
Proof. By [START_REF] Lidl | Finite fields[END_REF]Cor. 8.83] we know that the weights w of C lie in the range

n 1 - 1 q -w ≤ 1 - 1 q q k/2 .
The result follows by computing the length of that interval.

Irreducible cyclic codes

The weight structure of irreducible cyclic codes has been a research topic since the first works of McEliece and others [START_REF] Lidl | Finite fields[END_REF][START_REF] Mceliece | Irreducible Cyclic Codes and Gauss Sums[END_REF][START_REF] Ding | Hamming weights of irreducible cyclic codes[END_REF] due to their connection to Gauss sums and L-functions, and its intrinsic complexity.

Theorem 4. If C is an [n = q k -1
N , k] q irreducible cyclic code with a check polynomial of period n, and s nonzero weights, then s ≤ N.

Proof. Since the check polynomial h(x) is irreducible, it generates the annihilating ideal of each sequence attached to a codeword. If the period of such a sequence were T < n, then h(x) would divide x T -1, contradicting the hypothesis on the period of h(x). Hence C is strongly cyclic, and we can apply Theorem 1. The result follows.

Example. Consider the case of N = 2, and q = p an odd prime. Such a code is well-known to be a two-weight code [START_REF] Mceliece | Irreducible Cyclic Codes and Gauss Sums[END_REF].

A slightly sharper bound can be derived using the results in [START_REF] Ding | Hamming weights of irreducible cyclic codes[END_REF].

Theorem 5. If C is an [n = q k -1
N , k] q irreducible cyclic code with a check polynomial of period n, and s nonzero weights then

s ≤ N k = gcd N, q k -1 q -1 .
Proof. Follows by [8, (12)] which involves Gaussian periods of order N k .

This shows that Theorem 4 can only be tight when N = N k , or, equivalently, N divides q k -1 q-1 . Using Theorem 3, another bound can be derived.

Theorem 6. If C is an [n = q k -1 N , k] q irreducible cyclic
code with a check polynomial of period n, and s nonzero weights then s ≤ 2(1

-1 q ) √ 1 + nN .
Proof. As explained in the proof of Theorem 4 we know that all nonzero codewords have period n. Thus the code C is strongly cyclic, and we can apply Theorem 3. We get rid of k in Theorem 3 by writing q k = 1 + nN.

Remark. Depending on the relative values of n and N, either Theorem 6, or Theorem 5 is sharper than the other.

A slight improvement on Theorem 6 can be derived for irreducible cyclic codes.

Theorem 7. If C is an [n = q k -1 N , k] q irreducible cyclic
code with a check polynomial of period n, and s nonzero weights then

s ≤ 2 1 - 1 q n h - 1 N √ 1 + nN ,
where h = lcm(n, q -1).

Proof. The proof follows the lines of Theorem 6 with [15, Th. 8.84, (8.37)] replacing [START_REF] Lidl | Finite fields[END_REF]Cor. 8.83]. We get rid of k by writing q k = 1 + nN.

4 Lower bounds

Special values

We begin with an easy bound.

Proposition 1. For all prime powers q, we have Γ(k, q) ≥ k.

Proof. The universe code, the cyclic [k, k] q code with generator the constant polynomial g(x) = 1, has k nonzero weights. This shows that Γ(k, k, q) ≥ k. The result follows by Γ(k, k, q) ≤ Γ(k, q).

The following result is immediate by [START_REF] Shi | Two-weight codes and second order recurrences[END_REF]. The proof is omitted.

Proposition 2. For all prime powers q, we have Γ(2, q) = 2.

We recall now some classical cyclic codes. The repetition code R(n, q) is the ideal of F q [x]/(x n -1) with generator x n -1

x-1 . Its dual is P (n, q) = (x-1) . The binary Hamming code H m is the binary cyclic code of length n = 2 m -1 with generator any primitive irreducible polynomial of F 2 [x] of degree m. Its dual the simplex code S m is a one-weight code.

Theorem 8. For all integers n ≥ 1 and all prime powers q with (n, q) = 1, we have that Γ(n, 1, q) = 1, and that Γ(n, n -1, q) is the number of nonzero weights in P (n, q). For all primes m ≥ 2, we have Γ(n, n -m, 2) = n -4, and Γ(n, m, 2) = 1, where n = 2 m -1.

Proof. The first statement follows by the unicity of cyclic codes with dimension (resp. codimension) one. These are the repetition codes (resp. their duals). Their number of weights are easy to compute. To prove the second statement, observe that x 2 m -x is the product of all monic irreducible polynomials whose degree divides m [16, Chap. 4, Th. 11]. If m is a prime number, any divisor of x 2 m -1 -1 of degree m will have then to be irreducible. Thus, cyclic codes of dimension (resp. codimension) m will have to be S m (resp. H m ) or replicated versions of S m ′ (resp. H m ′ ) for m a proper divisor of m ′ . The result follows on observing that the number of nonzero weights of H m is 2 m -5 ([16, Chap. 6, Ex. (E2)]), and the fact that S m is a one-weight code [16, Chap.1 §9 , Ex].

Remark. The fact that the number of nonzero weights of H m is 2 m -5 can also be derived applying part (1) of Theorem 16 of the Appendix if we notice that H m is a punctured R(m -2, m). Theorem 9. Let q > 2 be a prime power and r ≥ 2 such that gcd(r, q -1) = 1. We have the bound

Γ q r -1 q -1 , q r -1 q -1 -r, q ≥ q r -1 q -1 -2.
Proof. Note that the q-ary Hamming code of length q r -1 q-1 is equivalent to a cyclic code iff gcd(r, q -1) = 1 [START_REF] Huffman | Fundamentals of error correcting codes[END_REF]. The result follows then by Theorem 19 of Appendix II.

The next result also uses Reed-Muller codes. We will need some generalization of the binomial coefficients given by the following generating function

(1 + z + . . . + z q-1 ) m = m(q-1) ℓ=0 B(q, m, ℓ)z ℓ .
Theorem 10. With the notations above, we have the following results.

Γ 2 m -1, m-3 i=0 m i , 2 ≥ 2 m-1 -9 for m ≥ 6, Γ 3 m -1, 2m-2 i=0 B(3, m, i), 3 ≥ 3 m -3 for m ≥ 1, Γ 3 m -1, 2m-3 i=0 B(3, m, i), 3 ≥ 3 m -7 for m ≥ 3, Γ 5 m -1, 4m-3 i=0 B(5, m, i), 5 ≥ 5 m -4 for m ≥ 1. Γ q m -1, (q-1)m-r-1 i=0 B(q, m, i), q ≥ q m -r -2 for 0 ≤ r ≤ q -3 2 .
Proof. The result combines Appendix I with the fact that punctured Reed Muller codes are cyclic [3, p.1312]. Note that the dimensions are not affected by puncturing due to the large minimum weights. The number of weights can decrease by at most 1 by transitivity of the automorphism group.

The next two theorems rely on some deep algebraic geometric enumeration of cyclic codes [START_REF] Lachaud | The weights of the orthogonals of the extended quadratic binary Goppa codes[END_REF][START_REF] Schoof | Families of curves and weight distributions of codes[END_REF][START_REF] Van Der Geer | Artin-Schreier curves and codes[END_REF]. See [START_REF] Hurt | Exponential Sums and Coding Theory: A Review[END_REF] for a survey.

Theorem 11. For all integers m ≥ 3, we have

Γ(2 m -1, 2m, 2) ≥ ⌈2 m/2 ⌉, and
Γ(2 m + 1, 2m, 2) ≥ ⌈2 m/2 ⌉.
Proof. The dual of the binary Melas code is cyclic of parameters [2 m -1, 2m]. It is proved in [14, Th. 6.3] that its nonzero weights are all the even integers w in the range

w - 2 m -1 2 ≤ 2 m/2 .
Similarly, the dual of the Zetterberg code is an irreducible cyclic code of parameters [2 m + 1, 2m]. It is proved in [START_REF] Lachaud | The weights of the orthogonals of the extended quadratic binary Goppa codes[END_REF]Th. 6.6] that its nonzero weights are all the even integers w in the range

w - 2 m + 1 2 ≤ 2 m/2 .
The result follows after elementary calculations.

A ternary analogue is as follows.

Theorem 12. For all integers m ≥ 2 we have

Γ(3 m -1, 2m, 3) ≥ ⌈2 × 3 m-2 2 ⌉.
Proof. The dual of the ternary Melas code is cyclic of parameters [3 m -1, 3m]. It is proved in [START_REF] Van Der Geer | Artin-Schreier curves and codes[END_REF] that its nonzero weights are of the form 3 m -1+t 3 with t ∈ Z, satisfying t ≡ 1 (mod 3), and t 2 < 3 m . The result follows after elementary calculations.

It is remarkable that the last two theorems imply lower bounds on Γ(k, q), that are exponential in the dimension. It would be desirable to extend these results to Γ(k, q) with q a prime power > 3.

Covering radius

Recall that the covering radius ρ(C) of a code C is the smallest integer t such that every point in F n q is at distance at most t from some codeword of C. A combinatorial function that is, as far as we know, new, is T [n, k, q], the largest covering radius of a cyclic code of length n and dimension k over F q . Note that the closest classical function in that context is, for q = 2, the quantity t[n, k], the smallest covering radius of a binary linear code of length n and dimension k

Γ(n, k, q) ≥ T [n, n -k, q].
Proof. Upon using Delsarte bound for the dual of an [n, k] q code with Γ(n, k, q) nonzero weights, which is, in particular, an [n, n -k] q code we see that Γ

(n, k, q) ≥ T [n, n -k, q].

Asymptotics

To consider the number of weights of long codes of given rate, we study the behavior of γ q (R) defined for 0 < R < 1 as

γ q (R) = lim sup n→∞ 1 n
log q (Γ(n, ⌊Rn⌋, q)).

Theorem 13. For all rates R ∈ (0, 1) we have

γ q (R) ≤ R.
In particular, γ q (R) ≤ t(q), the unique solution in (0, q-1 q ) of the equation H q (x) = x.

Proof. The bound comes from the immediate inequalities Γ(n, k, q) ≤ Γ(k, q) ≤ q k -1.

Similarly for strongly cyclic codes we define

γ 0 q (R) = lim sup n→∞ 1 n log q (Γ 0 (n, ⌊Rn⌋, q)).
We obtain a different upper bound.

Theorem 14. For all rates R ∈ (0, 1) we have

γ 0 q (R) ≤ R 2 .
In particular, γ q (R) ≤ t 0 (q), the unique solution in (0, q-1 q ) of the equation

H q (x) = x 2 .
Proof. The bound comes from the immediate inequalities Γ 0 (n, k, q) ≤ Γ 0 (k, q) and Theorem 3.

Numerics

We conjecture, but cannot prove, based on the figures of Table 1, that some local maxima of n → Γ(n, k, 2), for fixed k of the form k = s(s+1) 2 are met for codes with check polynomials of the form s i=1 h i (x), where h i is irreducible of degree i. Another motivation for the conjecture is that cyclic codes with irreducible check polynomials are one-weight codes in primitive length.

Table 1: lower bounds on Γ(k, q) What can be noted from Table 1 is that the bound Γ(k, q) ≥ k of Proposition 1 is weak.

Γ(k, q) ≥ q k n h(x) 8 2 6 21 (1 + x)(1 + x + x 2 )(1 + x + x 3 ) 15 2 10 105 (1 + x)(1 + x + x 2 )(1 + x + x 3 )(1 + x + x 4 ) 11
A systematic algorithm to compute Γ(k, q) can be sketched as follows.

(i) Find all polynomials h of degree k of F q [x], such that h(0) = 0;

(ii) For each h compute its period T h ;

(iii) Count the number s h of nonzero weights of the cyclic code of length T h and check polynomial h;

(iv) Maximize s h over all h's in Step (i).

We justify this algorithm as follows.

Proof. View h as the check polynomial of an [n, k] cyclic code C. If h(x) = x a H(x), with a ≥ 1, and H(0) = 0, then gcd(x n -1, h) = H(x) and C has for dimension the degree of H < k. Contradiction. Since h(0) = 0, the period of h is well-defined. All cyclic codes with check polynomial h will have lengths a multiple of T h , and will be repetitions of the code of length T h , with the same number of weights.

We illustrate this algorithm by the special case k = 3, q = 2. The polynomials h can take the following values (i) x 3 + x + 1, x 3 + x 2 + 1, when T = 7 and s = 1 (Simplex code) (ii) x 3 + 1 when T = 3 and s = 3 (Universe code)

(iii) x 3 + x 2 + x + 1 = x 4 +1
x+1 when T = 4 and s = 2 (Even weight code)

We conclude that Γ(3, 2) = 3. More generally, we have the following results for q = 2 and q = 3. If the number s h of nonzero weight of the cyclic code of check polynomial h(x) meets Γ(k, q), we call h(x) the optimal polynomial. We list some optimal polynomials h(x) as follows. The coefficients of the polynomial h(x) are written in increasing powers of x, for example for k = 3, the entry 1001 means 1 + x 3 .

k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 k = 9 q = 2
k = 3 k = 4 k = 5 k = 6 q = 3 3 5 8 12 h(x) (

Conclusion and open problems

In this paper, we have studied the largest number of distinct nonzero weights a cyclic code of given length and dimension could have. We have derived some upper bounds on that quantity that seem especially sharp for irreducible cyclic codes. Lower bounds appear weak so far, being mostly linear in k, when the upper bounds are exponential. The Melas and Zetterberg codes provided lower bounds exponential in the dimension and it is worth extending these bounds to other range of parameters. The results on the weights of q-ary Reed-Muller and Hamming codes, while of interest in their own right only provide lower bounds that are polynomial in the dimension.

So sharpening the lower bounds is the main open problem. Finding a pattern in the local maxima of n → Γ(n, k, q) by running extensively the algorithm of the last section for large n's might help. This programming effort could lead to a table of the function Γ(k, q) for modest values of kq, let us say kq ≤ 100 for instance.

Appendix I: Reed-Muller codes

In both the appendices, the symbol wt(C) denotes the set of weights of the code

C, i.e. wt(C) = {i ∈ N | ∃ c ∈ C s.t. w H (c) = i}.
Moreover, let t be a positive integer. Given t sets of integers A 1 , . . . , A t we define the set of sums

t i=1 A i := {a 1 + a 2 + . . . + a t | a i ∈ A i } .
Let m be a positive integer and F q be a finite field. Consider R m := F q [x 1 , . . . , x m ] the ring of polynomials in m variables over F q . Moreover, list all the points of F m q as P 1 , . . . , P n , where n = q m , and consider the evaluation map ev m : R m -→ F n q f -→ (f (P 1 ), . . . , f (P n )).

Definition 1. Let r, m be positive integers such that 0 ≤ r ≤ (q -1)m. The q-ary Reed-Muller code of order r in m variables is defined by

RM q (r, m) := {ev m (f ) | f ∈ R m , deg(f ) ≤ r} .
Observe that the choice of the order of the points P i of F m q does not matter. Indeed, different choices lead to equivalent codes. However, it is possible to define the order in a smart way, such that we have an inductive construction of the q-ary Reed-Muller codes. Let γ be a primitive element of F q . For m = 1 we consider P 1 = 0 and P i = γ i-1 for i = 2, . . . , q. Inductively, if {P 1 , . . . , P n } is the set of points chosen for n = q m , then for m + 1 we choose {P ′ 1 , . . . , P ′ N }, where N = q m+1 , as follows.

P ′ i = (P i , 0) for 1 ≤ i ≤ n. P ′ nj+i = (P i , γ j ) for 1 ≤ i ≤ n, 1 ≤ j ≤ q -1.
With this choice of the order of the points, one can prove the following result whose proof is omitted since it can be found in [START_REF] Blackmore | Matrix product codes over F q , Applicable Algebra in Engineering[END_REF]. For the rest of this section, for any integers s, t, we denote by G q (s, t) a generator matrix for the q-ary-Reed Muller code of order s in t variables. Proposition 4. There exist λ i,j ∈ F q for 1 ≤ i < j ≤ q such that

G q (r, m+1) =       G q (r, m) λ 1,2 G q (r, m) . . . λ 1,q G q (r, m) 0 . . . . . . . . . G q (r -q + 2, m) λ q-1,q G q (r -q + 2, m) 0 0 G q (r -q + 1, m)       .
Remark 1. Observe that, in the case m = 1, the Reed-Muller code RM q (r, 1) is simply the extended Reed-Solomon code of length q and dimension r + 1. It is wellknown that in this case wt(RM q (r, 1)) = {q -r, q -r + 1, . . . , q} (see [START_REF] Ezerman | The weights in MDS codes[END_REF]Theorem 6]).

Let now denote by n q (r, m), k q (r, m) and d q (r, m) respectively the length, dimension and minimum distance of the Reed-Muller code R q (r, m). The following result can be found in [START_REF] Blackmore | Matrix product codes over F q , Applicable Algebra in Engineering[END_REF], and explains more about the structure of this family of codes.

Proposition 5. Let r, m be integers such that 0 ≤ r ≤ (q -1)m. Then (2) k(r, m) = r i=0 B(q, m, i), where B(q, m, i) denotes the coefficient of z i in the polynomial (1 + z + . . . + z q-1 ) m .

(3) d(r, m) = (q -S)q m-1-Q , where r = Q(q -1) + S with 0 ≤ S ≤ q -2.

(4) RM q (r, m) ⊥ = RM q (m(q -1) -r -1, m), and therefore G q (r, m) is a parity check matrix for the code RM q (m(q -1) -r -1, m).

Corollary 1. Let r, m be integers such that m ≥ 1 and 0 ≤ r ≤ m(q -1). Let blueu 1 , . . . , u q ∈ RM q ((m -1)(q -1) -r -1, m -1).

Then (u 1 | . . . | u q ) ∈ RM q (m(q -1) -r -1, m).
Proof. Let u 1 , . . . , u q ∈ RM q ((m -1)(q -1) -r -1, m -1). By Proposition 5 we know that RM q ((m -1)(q -1) -r -1, m -1) ⊥ = RM q (r, m -1), and therefore, G q (r, m -1)u i T = 0 for i = 1, . . . , q. Moreover, for every s ≤ r we have RM q (r, m -1) ⊇ RM q (s, m -1). This implies, by part (4) of Proposition 5, that RM q ((m -1)(q -1) -r -1, m -1) ⊆ RM q ((m -1)(q -1) -s -1, m -1). Hence, we also have that G q (s, m -1)u i T = 0. Using the characterization given in Proposition 4, we get that G q (r, m)(u 1 | . . . | u q ) T = 0 and this completes the proof.

As a direct consequence of Corollary 1, we get the following result.

Corollary 2. Let r, m be integers such that m ≥ 1 and 0 ≤ r ≤ m(q -1). Then

wt(RM q (m(q -1) -r -1, m)) ⊇ q i=1
wt(RM q ((m -1)(q -1) -r -1, m -1)).

We can finally give a general statement on the set of weights for some classes of q-ary Reed-Muller codes.

Theorem 15. For every positive integer m and every integer r such that 0 ≤ r ≤ q-3 2 , it holds that wt(RM q (m(q -1) -r -1, m)) = {0, r + 2, r + 3, . . . , q m }.

Proof. We proceed by induction on m. For m = 1 we get that RM q (q -r -2, 1) is the Reed-Solomon code of length q and dimension q -r -1. Therefore, wt(RM q (qr -2, 1)) = {r + 2, r + 3, . . . , q} by [START_REF] Ezerman | The weights in MDS codes[END_REF]Theorem 6].

Suppose now it is true for m -1 and we want to prove the statement for m. Let n = q m-1 and N = q m = qn. We already know by part (3) of Proposition 5, that the minimum distance is equal to r + 2. Moreover, by Corollary 2 and inductive hypothesis, we have that wt(RM q (m(q -1) -r -1, m)) ⊇ q i=1 {0, r + 2, . . . , n}.

Let x ∈ {0, r + 2, . . . , qn}, we need to prove that we can write x = x 0 + x 1 + • • • + x q-1 with x i ∈ {0, r + 2, . . . , n}. By Euclidean division, we have x = an+ b, with 0 ≤ a < q and 0 ≤ b < n. At this point we distinguish two cases. Case 1: If b ∈ {0, r + 2, . . . , n -1}, then we choose

x 0 = b, x 1 = • • • = x a = n and x a+1 = • • • = x q-1 = 0.
Case 2: If b ∈ {1, . . . , r + 1}, then, necessarily a ≥ 1. By hypothesis we have n ≥ q ≥ 2r + 3. Therefore, n -r -2 + b ∈ {0, r + 2, . . . , n} and we choose x 0 = r + 2,

x 1 = n -r -2 + b, x 2 = • • • = x a = n and x a+1 = • • • = x q-1
= 0. This concludes the proof.

Binary Reed-Muller codes

Here we provide an additional result not covered by Theorem 15 for binary Reed-Muller codes. Proof. [START_REF] Alderson | A note on full weight spectrum codes[END_REF] We prove it by induction on m. In the case m = 3, a Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] It is easy to check that A = {0, 2, 4, . . . , 2 m+1 } \ {2, 2 m+1 -2}. We know, by minimum distance arguments in Proposition 5, that the integer 2 is not in wt(RM 2 (m -1, m + 1)). Moreover, since the all ones vector is a codeword, also 2 m -2 can not be a weight. This completes the proof.

(2) We also prove it by induction on m. In the case m = 6, a Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] This completes the proof.

Ternary Reed-Muller codes

In this subsection we give an additional result not covered by Theorem 15 for ternary Reed-Muller codes. (2) If m ≥ 3, then wt(RM 3 (2m -3, m)) ⊇ {0, 6, 8, 9, . . . , 3 m }. Definition 2. Let q be a prime power, and let r ≥ 2 be a positive integer. We define the q-ary Hamming code H r (q) as the [θ q (r -1), θ q (r -1) -r] linear code over F q whose parity check matrix H r is obtained by choosing all the vectors of P r (q) (without repetitions) as columns.

Observe that in Definition 2 the order of the choice of the columns does not really matter. Indeed, permuting the columns of the parity check matrix of a code gives rise to an equivalent code. All the parameters of a code, such that length, dimension and weight distribution are invariant under equivalence of codes. Therefore, for our purpose of studying the weight set of an Hamming code, we are free to choose the order of the columns of H r in the way we prefer by Definition 2. Lemma 3. Let H r-1 be the parity check matrix for the Hamming code H r-1 (q) as described in Definition 2. Then we can obtain a parity check matrix for H r (q) as

H r =       0 • • • 0 1 • • • 1 1 • • • 1 • • • 1 • • • 1 1 0 H r-1 γH r-1 γ 2 H r-1 • • • γ q-1 H r-1 . . . 0       ,
where γ is a primitive element of F q and H 1 = (1).

The Main Theorem

Hamming codes have been deeply studied in the theory of error correcting codes, since they represent the only existing infinite family of perfect codes. Indeed, in addition to Hamming codes, the only perfect linear codes that are non-trivial, are the binary Golay code and the ternary Golay code [START_REF] Huffman | Fundamentals of error correcting codes[END_REF][START_REF] Macwilliams | The theory of error correcting codes[END_REF][START_REF] Tietäväinen | On the nonexistence of perfect codes over finite fields[END_REF].

It is a well-known fact that q-ary Hamming codes always have minimum distance equal to 3. Moreover, a recursive formula for the weight distribution of a q-ary Hamming code H r (q) is known, and it can be found in [START_REF] Kim | Weight distributions of Hamming codes[END_REF]. Anyway, from that recursion, it is not immediate how to deduce wether the number of codewords of weight i in H r (q) is greater than zero or not. In the particular case that r = 2 we know more about the structure of H 2 (q). Lemma 4. For r = 2 the Hamming code H 2 (q) is an MDS code of parameters [q + 1, q -1, 3]. In particular, wt(H 2 (3)) = {0, 3} and wt(H 2 (q)) = {0, 3, 4, . . . , q + 1} for every q > 3.

Proof. The parameters of H 2 (q) are well-known to be [q + 1, q -1, 3]. From there we see that this code is MDS. The explicit determination of the weights follows then by [START_REF] Ezerman | The weights in MDS codes[END_REF]Theorem 10].

The above result represents, except for the case q = 3, the base step of our proof for induction. Now, we give some auxiliary tools that will enable us to prove our main results in this section.

Lemma 5. Let q > 2 be a prime power, and let r ≥ 1 be a positive integer. Then v∈F r q v = 0 and u∈Pr(q) u = e r , where e r = (0, 0, . . . , 0, 1) T .

Proof. For the first equality, we prove it by induction. Let r = 1, q ≥ 3, and γ be a primitive element of F q . Then

v∈Fq v = q-2 i=0 γ i = γ q-1 -1 γ -1 ,
since γ = 1. Moreover, γ q-1 = 1 and then we get the result.

For r > 1, we can write F r q = α∈Fq T α , where

T α := (α, v ′ ) | v ′ ∈ F r-1 q ,
and the union is clearly disjoint. Therefore,

v∈F r q v = α∈Fq v ′ ∈F r-1 q (α, v ′ ) = α∈Fq (q r-1 α, 0) = 0,
where q r-1 α denotes (with a slight abuse of notation) α + . . . + α q r-1 times , and the second equality holds for inductive hypothesis.

Concerning the second statement, we proceed again by induction. For r = 1 the statement is clearly true, since P 1 (q) is the set with the only element e 1 = (1).

Since α = 0, then |T | ≥ 1. We distinguish two cases.

Case 1: |T | ≥ 2. Let r, s ∈ T be two distinct elements. Consider a generic vector β = (β 0 , . . . , β q-1 ) whose entries are β i = 1 for i = r, s, and consider the elment (β, id) • (u 0 | . . . | u q-1 ). By Lemma 6, the vector ((β, id) • (u 0 | . . . | u q-1 ) | α) , belongs to H r (q), where α = -

Since q > 2, there exists (β r , β s ) ∈ F * q × F * q satisfying Equation (3), and we can conlcude.

Case 2: |T | = 1. Let r be the only element in T . We divide this case into two subcases:

(i) If u 0 , e = 0, then consider the transposition σ = (0, r) ∈ S q . Consider the element (e, σ) • (u 0 | . . . | u q-1 ) = (v 0 | . . . |v q-1 ).

By Lemma 6, we have (ii) Suppose now that u 0 , e = 0. Then there exists s ∈ {1, 2, . . . , q -1} such that s / ∈ T . We now consider the transposition σ = (0, s) and the corresponding vector (e, σ) • (u 0 | . . . | u q-1 ).

(v 0 | . . . | v q-1 | α) ∈ H r (q),
For this new vector we have now |T | = 2 and we can conclude by Case 1.

This completes the proof.

As a direct consequence, we immediately get the following result.

Corollary 3. Let q > 2 be a prime power, and let r ≥ 3 be a positive integer. Then wt(H r (q)) ⊇ q-1 i=0

wt(H r-1 (q)).

We are now ready to prove the main result.

Theorem 19. Let q > 2 be a prime power, and let r ≥ 2 be an integer. Then wt(H r (q)) = {0, 3, . . . , N},

where N := θ q (r -1), except when (q, r) = (3, 2), in which case wt(H 2 (3)) = {0, 3}.

Proof. We prove it by induction. The base step is divided in two cases Case 1: (q, 2) with q > 3. It follows from Lemma 4. Case 2: (q, r) = (3, 3). We computed it with the aid of the software Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF]. Now, suppose that the claim is true for (q, r -1) and we want to prove it for (q, r). By hypothesis we know that wt(H r-1 (q)) = {0, 3, . . . , n} where n = θ q (r -2), and observe that N = qn + 1. By Corollary 3, we know that wt(H r (q)) ⊇ q-1 i=0 wt(H r-1 (q)) = q-1 i=0 {0, 3, . . . , n} .

Moreover, since (q, r -1) = (3, 2), we have that n ≥ 5. By Proposition 6 we already know that N ∈ wt(H r (q)). Therefore it is enough to show that q-1 i=0 {0, 3, . . . , n} = {0, 3, . . . , qn} .

It is clear that N -1 = qn belongs to our set, since n ∈ wt(H r-1 (q)). Let x ∈ {0, 3, . . . , qn -1}, we need to prove that we can write x = x 0 + x 1 + • • • + x q-1 with x i ∈ {0, 3, . . . , n}. By Euclidean division, we have x = an + b, with 0 ≤ a < q and 0 ≤ b < n. At this point we distinguish two cases. Case 1: b ∈ {0, 3, . . . , n -1}. We choose x 0 = b, x 1 = • • • = x a = n and x a+1 = • • • = x q-1 = 0. Case 2: b ∈ {1, 2}. Then, necessarily a ≥ 1. Moreover, we already observed that n ≥ 5. Therefore, n -3 + b ∈ {0, 3, . . . , n} and we choose x 0 = 3, x 1 = n -3 + b, x 2 = • • • = x a = n and x a+1 = • • • = x q-1 = 0. This concludes the proof.

Proposition 3 .

 3 [START_REF] Cohen | Covering codes[END_REF]. Trivially t[n, k] ≤ T [n, k, 2]. The Delsarte bound[START_REF] Macwilliams | The theory of error correcting codes[END_REF], stated for the dual of a linear code C, is ρ(C ⊥ ) ≤ s(C)[START_REF] Macwilliams | The theory of error correcting codes[END_REF] Chap. 6, Th. 21]. With the above definitions, we can state the following result. For all integers n, k with 1 ≤ k ≤ n, we have

( 1 )

 1 n(r, m) = q m .

Theorem 16 .

 16 Let m be a positive integer, then we have(1) If m ≥ 3, then wt(RM 2 (m -2, m)) = {0, 2, 4, . . . , 2 m } \ {2, 2 m -2}.

( 2 )

 2 If m ≥ 6, then wt(RM 2 (m -3, m)) ⊇ {0, 2, 4, . . . , 2 m } \ {2, 4, 6, 10, 2 m -2, 2 m -4, 2 m -6, 2 m -10}.

Theorem 17 .

 17 Let m be a positive integer, then we have (1) If m ≥ 1, then wt(RM 3 (2m -2, m)) = {0, 3, 4, 5, . . . , 3 m }.

  u i , e + (1 -β r ) u r , e + (1 -β s ) u s , e = α + (1 -β r ) u r , e + (1 -β s ) u s , e .Imposing the condition α = 0 we get(1 -β s ) = -α + (1 -β r ) u r , e u s , e .

Table 2 :

 2 exact values of Γ(k, 2)

Table 3

 3

	: exact values of Γ(k, 3)

  30}. Now, suppose that the claim is true for m ≥ 3, by Corollary 2, we have wt(RM 2 (m -1, m + 1)) ⊇ A, where A = {i + j|i, j ∈ wt(RM 2 (m -2, m))}.

	com-
	putation shows that wt(RM 2 (1, 3)) = {0, 2, 4, 6, 8} \ {2, 6}, wt(RM 2 (2, 4)) = {0, 2, 4, 6, 8, 10, 12, 14, 16} \ {2, 14} and wt(RM 2 (3, 5)) = {0, 2, 4, 6, . . . , 32} \ {2,

  computation shows that wt(RM 2[START_REF] Assmus | Polynomial codes and finite geometries[END_REF][START_REF] Cohen | Covering codes[END_REF])) = {0, 2, 4, 6, 8, . . . , 64} \ {2, 4, 6, 10, 54, 58, 60, 62}. Now, suppose that the claim is true for m ≥ 6, then B = {i + j|i, j ∈ wt(RM 2 (m -3, m))}. It is also easy to check that B = {0, 2, 4, . . . , 2 m+1 } \ {2, 4, 6, 10, 2 m -2, 2 m -4, 2 m -6, 2 m -10}. We know, by minimum distance arguments in Proposition 5, that the integers 2, 4 and 6 are not in wt(RM 2 (m-1, m + 1)). However, we don't know whether 10 belongs to wt(RM 2 (m -1, m + 1)). Thus from Corollary 2, we have wt(RM 2 (m -1, m + 1)) ⊇ B.

Acknowledgements. The paper is dedicated to the memory of our friend and mentor G.D. Cohen (1951Cohen ( -2018)). The authors wish to thank Professor C. Ding for helpful discussions.

* This research is supported by National Natural Science Foundation of China (61672036), Excellent Youth Foundation of Natural Science Foundation of Anhui Province (1808085J20), Technology Foundation for Selected Overseas Chinese Scholar, Ministry of Personnel of China (05015133).

† The author was supported by the Swiss National Science Foundation through grant no. 169510.

Proof. [START_REF] Alderson | A note on full weight spectrum codes[END_REF] We prove it by induction on m. The cases m = 1, 2, 3 can be checked in Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] to be wt(RM 3 (0, 1)) = {0, 3}, wt(RM 3 (2, 2)) = {0, 3, 4, 5, 6, 7, 8, 9} and wt(RM 3 (4, 3)) = {0, 3, 4, . . . , 27}. Now, suppose that the claim is true for m ≥ 4, from Corollary 2, we have wt(RM 3 (2m, m+1)) ⊇ A = {i+j +l|i, j, l ∈ wt(RM 3 (2m -2, m))}. It is easy to check A = {i + j + l|i, j, l ∈ wt(RM 3 (2m -2, m))} = {0, 3, 4, 5, . . . , 3 m+1 }. According to part (3) of Proposition 5, d(2m -2, m) = 3. This completes the proof.

(2) We also prove it by induction on m. The cases m = 3, 4 can be checked in Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] to be wt(RM Proof. We also prove it by induction on m. The cases m = 1, 2 can be checked with the aid of the software Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] to be wt(RM 5 (1, 1)) = {0, 4, 5} and wt(RM 5 (5, 2)) = {0, 4, 5, 6, . . . , 25}. Now, suppose that the claim is true for m ≥ 3, then B = {i + j + l + s + t|i, j, l, s, t ∈ wt(RM 5 (4m -3, m))} = {0, 4, 5, 6, . . . , 5 m+1 }. From Corollary 2, we have wt(RM 5 (4m + 1, m + 1)) ⊇ {0, 4, 5, 6, . . . , 5 m+1 }. Finally, from part (3) of Proposition 5, we have d(4m -3, m) = 4. This completes the proof. 9 Appendix II: q-ary Hamming codes

Block Codes and Hamming Codes

Let q be a prime power, and let F q denote the finite field with q elements. We denote by F * q = F q \ {0} the multiplicative group of F q . It is well-known that F * q is a cyclic group, i.e. there always exists a generator γ such that

we denote by u, v the standard inner product between u and v, i.e.

Moreover, given two vectors u ∈ F n 1 q , v ∈ F n 2 q we will use the notation (u | v) to indicate the vector in F n 1 +n 2 q obtained by concatenating u and v, i.e.

Suppose r is a positive integer. On the set F r q \ {0} we can consider the following equivalence relation:

The projective geometry of order q and dimension r is defined as

A set of representatives for P G(r -1, q) is given by the set of all nonzero vectors of length r whose first nonzero entries is equal to 1. For this reason, the space P G(r -1, q) can be embedded in F r q . The image of this embedding will be denoted by P r (q). We will use this different notations in order not to confuse it with the space P G(r -1, q), since we will often use the elements of P r (q) as elements of F r q , where the notion of sum is well-defined. Since the cardinality of P r (q) is equal to the cardinality of P G(r -1, q), we have that θ q (r -1) := q r -1 q -1 = |P r (q)|.

Suppose now r > 1. Then we can write

Therefore,

where the second equality comes from inductive hypothesis and from the first part of this lemma.

Proposition 6. For every q > 2, and every integer r ≥ 2, there exists a codeword c ∈ H r (q) of full weight, i.e., such that w H (c) = θ q (r -1), except for the case (q, r) = (3, 2).

Proof. For r = 2 the statement trivially follows from Lemma 4. Suppose now r ≥ 3, and let γ be a primitive element of F q . Consider the set

where w 0 = e 1 = (1, 0, . . . , 0) and w i = (1, γ i , γ i , . . . , γ i ) for i = 1, 2, . . . , q -2 and w q-1 = (1, 1, . . . , 1, 0). It is easy to see that with this choice of D, we have q-1 i=0 w i + e r = 0.

Let α ∈ F q . We consider the sum

Choosing α ∈ F q \ {0, -1}, we have a linear combination of the columns of H r that gives the zero vector, and in which every column is multiplied by a nonzero coefficient. This gives a codeword that has all nonzero entries.

Proposition 6 proves the existence of a codeword of maximum weight in every Hamming code, with the exception of H 2 [START_REF] Assmus | Polynomial codes and finite geometries[END_REF]. For all the remaining weights we will use an induction argument based on the following two results. Lemma 6. If u i ∈ H r-1 (q) for i = 0, 1, . . . , q -1, then

and e denotes the vector with all entries equal to 1.

Proof. According to Lemma 3, it is straightforward to see that the vector (u 0 | u 1 | . . . | u q-1 | α) satisfies the check equations given by the rows i = 2, . . . , r of the parity check matrix. Moreover, the condition on α ensures that it also satisfies the first check equation.

Let q be a prime power, n be a positive integer. Consider the space (F n q ) q = F n q × . . . × F n q q times . Let S q denote the symmetric group on the set {0, 1, . . . , q -1}, id denote identical permutation and consider the action of the group (F * q ) q ⋊ S q on (F n q ) q defined as ϕ : ((F * q ) q ⋊ S q ) × (F n q ) q -→ (F n q ) q ((β, σ), (u 0 | . . . | u q-1 )) -→ (β 0 u σ(0) | . . . | β q-1 u σ(q-1) ).

It is straightforward to see that the same group acts on (H r-1 (q)) q . In order to simplify the notation, for (β, σ) ∈ ((F * q ) q ⋊ S q ), u ∈ (F n q ) q , we will write (β, σ) • u := ϕ((β, σ), u).

Proposition 7. Let q > 2 be a prime power and let (u 0 | . . . | u q-1 ) ∈ (H r-1 (q)) q . Then there exists (β, σ) ∈ (F * q ) q ⋊ S q such that (β 0 u σ(0) | . . . | β q-1 u σ(q-1) | 0) ∈ H r (q).

Proof. Let u 0 , u 1 , . . . , u q-1 ∈ H r-1 (q). By Lemma 6 we have that (u 0 | u 1 | . . . | u q-1 | α) ∈ H r (q), where α = -q-1 i=1 u i , e . If α = 0 we are done. Therefore, suppose α = 0, and consider the set T := {i ∈ {1, . . . , q -1} | u i , e = 0} .