Identifying codewords in general Reed-Muller codes and determining their weights

1.   Introduction

For every nonnegative integers $r, n$ such that $r\leq n$, the Reed-Muller code $RM(r, n)$ of length^* $N = 2^n$ and order $r$ equals the vector space over $\mathbb F_2$ of $n$-variable Boolean functions of algebraic degree at most $r$. Recall that each $n$-variable Boolean function $f:\mathbb F_2^n\mapsto \mathbb F_2$ admits a representation in the form of a multivariate polynomial over $\mathbb F_2$ of a particular shape:

^*Usually in coding theory, the length of a code is denoted by $n$, but since we deal with Boolean functions, we keep $n$ for the number of variables; we denote then the length by $N$.

(the sum being calculated modulo 2). Such representation is unique for each function and is called its algebraic normal form (ANF). The global degree $\max \{|I|; a_I = 1\}$ of the ANF is called the algebraic degree of $f$.

For a binary block code needing to be a subset of $\mathbb F_2^N$ for some $N$, each Boolean function is identified with the list of its $N = 2^n$ values, some order on $\mathbb F_2^n$ being previously chosen. When we shall speak of codewords of Reed-Muller codes, we will not make the difference between an $n$-variable Boolean function and the corresponding vector of length $N$.

Reed-Muller codes were introduced in 1954 by David Muller in ^[27] and their decoding algorithm was given the same year by Irving Reed in ^[29]. These codes have originally played an important role in the theory of error correcting codes, as well as in their applications. It is well known that the Reed-Muller code $RM(1, 5)$ was used in the sixties for correcting the errors of transmission of the first photographs of Mars by Mariner. These photographs were in black and white. Every codeword corresponded to the level of brightness of a pixel. There were 64 different levels since there are 64 codewords in $RM(1, 5)$, and the minimum distance of this code was equal to 16, with up to $\left\lfloor\frac{16-1}{2}\right\rfloor = 7$ errors that could be corrected in the transmission of each codeword^†.

^†In the late seventies, for transmitting color photographs of Mars, Voyager used the extended binary Golay code and still later Reed-Solomon codes

Reed-Muller codes were also used in the 3rd generation (3G) of mobile phones (starting in 2000). Reed-Muller codes intervened in the initial "handshake'' between the mobile device and the base station, whose role was to inform the receiver of what type of communication would come next. Again, $RM(1, 5)$ was initially used for this purpose, and it was later replaced by a punctured subcode of the second-order Reed-Muller code $RM(2, 5)$, which had a dimension of 10 and a minimum distance of 12.

The parameters of Reed-Muller codes are not so good, except for the first order, but they contain optimal codes such as the Kerdock codes ^[19]. They still play an important role nowadays, thanks to their specific properties (see, e.g., ^[2,13]) and their roles with respect to new problematics, such as locally correctable codes ^[20]), low degree testing, private information retrieval, and compressed sensing. The interest in Reed-Muller codes has also been renewed because of polarization (see, e.g., ^[24]). At various block-lengths and rates, Reed-Muller codes can be superior to polar codes ^[25], even for 5G ^[14]. A nice survey on Reed-Muller codes can be found in ^[1].

We can easily generate the ANF (1.1) of (infinite classes of) codewords in any Reed-Muller codes, but in most cases, it is impossible to calculate (mathematically) their Hamming weight $w_H(f) = |\{x\in \mathbb F_2^n; f(x) = 1\}|$.

Determining Hamming weights (if possible, all weights of codewords, and, if possible, the whole weight distribution) in Reed-Muller codes has always been considered very important; see, e.g., the papers ^{[4,5,7,12,15,16,17,18,23,26,30]}, the data in ^[31], and the books ^[22,28]. The weight distributions of the Reed-Muller codes of length $2^n$ and orders $0, 1, 2, n-2, n-1, n$ are known. The weights in these codes equal $0, 2^n$ for the order 0, with additionally $2^{n-1}$ for the order 1, and $2^{n-1}\pm 2^i$ where $\frac n2\leq i\leq n$ for the order 2; see, e.g., ^[22]. The weights in $RM(n, n)$ are all integers between 0 and $2^n$ since $RM(n, n) = \mathbb F_2^{2^n}$; the weights in $RM(n-1, n)$ are all even integers between 0 and $2^n$; the weights in $RM(n-2, n)$ are all even integers between 0 and $2^n$ except 2 and $2^n-2$. For all these codes, the weight distributions are known (thanks to the Mac Williams identity for the orders $n-2, n-1$ ^[21,22], since the dual of $RM(r, n)$ equals $RM(n-r-1, n)$). The weight distributions of some Reed-Muller codes $RM(r, m)$ have been determined thanks to heavy computations, for $m$ small enough; they are reported in ^[31].

The weights in $RM(n-3, n)$ have been recently determined in ^[12]. They are all even integers in $\{0, 2, 4, ..., 2^n\}\setminus \{2, 4, 6, 10, 2^n -10, 2^n - 6, 2^n -4, 2^n -2\} = \{0, 8, 12+2i, 2^n-12, 2^n-8, 2^n\}$, where $i$ ranges over consecutive integers from 0 to $2^{n-1}-13$. They have been obtained by an induction (the Mac Williams identity does not allow us to determine the weight distribution, which is still unknown despite the fact that the weight distribution of $RM(2, m)$ is known, because the expression of the number of codewords of Hamming weight $2^{n-1}$ in $RM(2, n)$ is too complex). This induction does not allow us to determine the weight distribution, and new ideas to be found seem necessary for obtaining it. However, determining the weight spectrum^‡ of $RM(n-3, n)$ is already a step forward.

^‡In coding theory, contrary to Boolean function theory, the spectrum does not include the multiplicities of the values (when these multiplicities are taken into account, we speak of weight distribution).

The same method worked for determining the weights in $RM(n-4, n)$ ^[12], which are all integers in $\{0, 16, 24, 28+2i, 2^n-28, 2^n-24, 2^n-16, 2^n\}$, where $i$ ranges over the set of consecutive integers from 0 to $2^{n-1}-29$. The weights in $RM(n-5, n)$ could not be determined in ^[12], but they were found in ^[9]; they are all integers in $\{0, 32, 48, 56, 60, 62, 64, 68, 72+2i$, $2^n-68, 2^n-64, 2^n-62, 2^n-60, 2^n-56, 2^n-48, 2^n-32, 2^n\}$, where $i$ ranges over the set of consecutive integers from 0 to $2^{n-1}-72$.

For general Reed-Muller codes, bounds are known on the weight enumerators, which are useful for studying the capacity of Reed-Muller codes on the binary erasure channel and the binary symmetric channel (see [1, Chapter 4]), but our knowledge on the weights themselves is limited.

McEliece's theorem ^[23] shows that the weights in $RM(r, n)$ are divisible by $2^{\lfloor \frac{n-1}r \rfloor}$, and Kasami-Tokura's result (that we shall recall in Section 2) and Kasami-Tokura-Azumi's results ^[17] give the weights of $RM(r, n)$, which are between the minimum distance $d = 2^{m-r}$ and $2.5$ times $d$. It is conjectured in ^[12] that for every constant $c$ and for $n$ large enough, the weight spectrum of $RM(n-c, n)$ is made of 0 and $2^n$ and all the weights between the minimum distance $2^c$ and its complement to the length $2^n$, which are authorized by McEliece's theorem and Kasami-Tokura-Azumi's results. This means, in particular, that every even number between 2.5 times the minimum distance and its complement to $2^m$ would be a weight in $RM(m-c, m)$. This conjecture^§ is verified by the weight spectra of $RM(n-5, n), RM(n-4, n)$ and $RM(n-3, n)$. The method used in ^[9,12] for handling these three weight spectra is the same: There is a corollary in ^[30], which can easily be proved directly, and which says that the weight spectrum of $RM(r, n)$ includes $A+A$, where $A$ is the weight spectrum of $RM(r-1, n-1)$. This allows us to address the weight spectrum of $RM(n-c, n)$ by an induction on $n$, starting from a value $n_0$ such that the weight spectrum of $RM(n_0-c, n_0)$ is already generic, which means that it has, according to McEliece's theorem, a divisibility by 2 and not by a larger power of 2. This means that we need to start from $n_0\geq 2c$. Indeed, according to McEliece's theorem, all the weights in $RM(c-1, 2c-1)$ are divisible by 4, while those in $RM(c, 2c)$ are divisible by 2. We know from ^[6] that McEliece's divisibility bound is tight in the sense that there is at least a codeword in every $RM(r, n)$ code, with a weight congruent to $2^{\lfloor \frac{n-1}r \rfloor}$ modulo $2^{\lfloor \frac{n-1}r \rfloor +1}$. We can try to see whether the weights obtained from $A+A$, where $A$ is the weight spectrum of $RM(c, 2c)$, allow us to reach all the weights authorized by McEliece's theorem and Kasami-Tokura-Azumi's result. The first difficulty is then to reach all weights in $RM(c, 2c)$. In the case of $c = 3, 4$, this has been rather easy, but proving the conjecture recalled above for $c = 5$ with this method, which needs to start the induction with $n = 10$ (a value much larger than what can be reached with the heavy computations made by M. Terada, J. Asatani, and T. Koumoto and reported in ^[31]), has led to the construction of functions in 10 variables with an algebraic degree of at most 5 and having all possible even weights between 2.5 times the minimum distance 32, that is, 80 and $2^{10}-80$. The next step $c = 6$ needs to address the code $RM(6, 12)$, which has huge parameters [4096,2510], while the largest reached currently are [512,256] and [512,382]). It is shown in ^[9] how determining the weight spectrum of $RM(6, 12)$ needs to determine whether some specific values (such as 166), which are "holes" after general methods were applied, are the weights of codewords. This may not be as hard as expected for $c = 6$, but addressing larger values of $c$ will probably lead to more of such "holes". Hence, being able to build as many weights as possible in Reed-Muller codes is of a great importance, and in particular, reaching weights that are not obtained by classic constructions.

^§It seems a little risky to present this as a conjecture and in ^[9], it is then presented as an open question.

Providing weights can indeed be tried by investigating the known (primary and secondary) constructions of Boolean functions and deducing functions whose weight can be determined, as was done in ^[9]. Some weights are easily reached this way, but we can expect that these constructions will not suffice for addressing the weights in $RM(n-c, n)$ for larger values of $c$.

Note that the codes $RM(n-c, n)$ considered above, being such that $n\geq 2c$, are of the form $RM(r, n)$ with $n\geq 2(n-r)$, that is, $r\geq \frac n2$. Another case where more weights in Reed-Muller codes $RM(r, n)$ are useful information is when $r < \frac n2$.

Recall that when Boolean functions in $n$ variables are given, for instance, by their ANF, with $n$ ranging over $\mathbb N$, it is rarely possible to mathematically evaluate their Hamming weights. Of course, it is always possible when the function is affine (belonging then to the Reed-Muller code of order 1), but this provides only three weights for each $n$. When the function is taken quadratic (i.e., belonging to the second-order Reed-Muller code), there are methods for determining its weight (see a survey in [8, Chapter 4]). However, these methods allow us to concretely address only a few cases (even the first step, which consists of determining the linear kernel of the function, is impossible to complete systematically). The weights of quadratic functions are very specific. The indicators of affine spaces (flats) are also addressable, but their weights are minimal in the Reed-Muller codes to which they belong. It needs specific work to study the weights of Boolean functions obtained by the constructions evoked above, and we shall describe in Section 2, as nothing automatic exists.

The problem we want to address in this paper is not as hard as determining the weight of any given Boolean function: We only want to find as many weights as possible in general Reed-Muller codes. However, it is not so easy to provide codewords of Reed-Muller codes whose weights can be determined.

For finding more weights, methods complementary to the usual constructions are needed. In the present paper, we give such a method to automatically generate codewords in Reed-Muller codes of any lengths $2^n$. These codewords depend on the number of variables $n$, the order $r$, a parameter $t$, and the choice of $t$ vectors $a_i$. We have, thanks to a property of the corresponding functions, an upper bound on their algebraic degree (but determining the degree exactly would be difficult, and even trying to directly show this upper bound by working on the ANF of the functions seems quite hard). The weights of these functions can be evaluated or at least bounded from above, because when these Boolean functions are given as the sums (modulo 2) of atomic ones, the only limitation for evaluating their weights is to determine the number of these atomic functions which appear an odd number of times in the expression.

There is a case (when the vectors $a_i$ involved in the construction are linearly independent) where we can ensure that all these atomic functions are distinct, which allows us to exactly calculate the Hamming weight. This provides information on the weight spectra of Reed-Muller codes when they are unknown (that is, currently, for the orders from 3 to $n-6$). For instance, we shall see in the tables provided that our method gives weights in $RM(r, n)$ that are much larger than twice the minimum distance and have low valuation.

The case mentioned above, where the vectors $a_i$ are linearly independent, provides at most $\frac n2$ distinct weights for each Reed-Muller code, and this is not much. We then investigate two cases where the vectors are linearly dependent. We do not cover all the cases where the vectors are linearly dependent (it seems impossible to do so), but other cases could be similarly investigated.

We also study the weights of the sums of the designed functions, in a case where we know they have disjoint supports. This provides many more weights.

The paper is structured as follows. In Section 2, we recall the state of the art in the determination of weights in Reed-Muller codes by using the classic constructions (Maiorana-McFarland, etc.). We show the difficulties presented by this method and why it suits better for low orders. In Section 3, we introduce our new construction of Reed-Muller codewords and we study some particular cases. We determine the weights under a condition that is rather general (namely, some vectors $a_i$ involved in the construction are linearly independent), and we also study two cases where this condition is not satisfied; this provides a list of weights for each Reed-Muller code, which is longer for larger orders. We then show that more weights - a huge number when the order is large enough - can be obtained as the additions of some of these weights. To conclude this section, we determine the ANF of the constructed functions when the vectors $a_i$ are linearly independent. We conclude with some observations on future work.

2.   State of the art on the Hamming weights of Reed-Muller codewords

It is well-known that the minimum nonzero Hamming weight of $RM(r, n)$ equals $2^{n-r}$ (see [22, Chapter 13], and see [8, Chapter 4] for a more direct proof), and that the nonzero minimum weight codewords in this code are the indicators of the $(n-r)$-dimensional affine subspaces of $\mathbb F_2^n$.

All the low Hamming weights are known in all Reed-Muller codes, and there are very few: Berlekamp and Sloane ^[4] (see the Addendum in this paper) and Kasami and Tokura ^[16] have shown that, for $r\geq 2$, the only Hamming weights in $RM(r, n)$ occurring in the range $[2^{n-r}; 2^{n-r+1}[$ are of the form $2^{n-r+1}-2^{n-r+1-i}$, where we have $i\leq \max(\min(n-r, r), \frac{n-r+2}2)$. The latter has completely characterized the codewords: The corresponding functions are affinely equivalent either to $x_1\cdots x_{r-2}(x_{r-1}x_r+ x_{r+1}x_{r+2}+ \dots + x_{r+2l-3}x_{r+2l-2})$, $2\leq 2l\leq n-r+2$, or to $x_1\cdots x_{r-l}(x_{r-l+1}\cdots x_r+ x_{r+1}\cdots x_{r+l})$, $3\leq l\leq \min(r, n-r)$. The functions whose Hamming weights are strictly less than 2.5 times the minimum distance $2^{n-r}$ have later been studied in ^[17].

Recall that, on the contrary, the general weights in $RM(r, n)$ can be rather diverse, as soon as $r\geq 3$ and $n$ is large enough. Indeed, as shown in ^[7], for every Boolean function $f$ on $\Bbb{F}_2^n$, there exist an integer $m$ and a Boolean function $g$ of an algebraic degree of at most $3$ on $\Bbb{F}_2^{n+2m}$, such that $\sum_{x\in \mathbb F_2^{n+2m}}(-1)^{g(x)} = 2^m\sum_{x\in \mathbb F_2^n}(-1)^{f(x)}$, which gives the following relation between the Hamming weights of $f$ and $g$: $2^{n+2m}-2w_H(g) = 2^m(2^n-2w_H(f))$. Hence, the Hamming weight of $f$ is related in a simple way to the Hamming weight of a cubic function (in a number of variables which can be exponentially larger). This shows that the weights in $RM(3, n)$ (that is, the distances) can be complex, contrary to those in $RM(2, n)$. Unfortunately, this result does not provide an efficient method for finding weights in third-order Reed-Muller codes: Trying to find new weights in these codes by starting with Boolean functions $f$ of any degree in less variables and applying the result does not work well, because $m$ in this result is exponentially large compared to $n$.

The possible weights of the codewords in the Reed-Muller codes of orders $3, \dots, n-6$ whose values lie between $2.5\, d$ and $2^n-2.5\, d$ are unknown^¶, except for some functions that we shall describe, and which hardly allow to provide non-peculiar weights for general Reed-Muller codes:

^¶But when $n = 2r+1$, they are known in some cases by using invariant theory, because the code is then self-dual, see ^[22,28]).

● Quadratic functions, in the form $f(x) = l_1(x)l_2(x)+l_3(x)l_4(x)+\dots +l_{2k-1}(x)l_{2k}(x)+l_{2k+1}(x)$, possibly added with constant 1 (that is, complemented), when we are able to ensure that the linear functions $l_1, \dots, l_{2k}$ are linearly independent. Then $f$ equals the function $x_1x_2+\dots +x_{2k-1}x_{2k}$ composed on the right by a linear or an affine automorphism (we say that such a function is linearly, respectively affine, equivalent to $x_1x_2+\dots +x_{2k-1}x_{2k}$), added with an affine function (we say then that the function is extended affine equivalent to $x_1x_2+\dots +x_{2k-1}x_{2k}$; see more on equivalences in [8, Chapter 2]), and we can evaluate its Hamming weight. This provides weights $0, 2^{n-1}, 2^{n-1}\pm 2^i$, where $i = \lceil\frac n2\rceil$, $2^n$, which are all weights in $RM(2, n)$ (all being easy to produce), but are rather peculiar in the larger Reed-Muller codes. We can also calculate the weights of the concatenations of such functions, of course, whose weights are a little more general (but the algebraic degree needs to then be determined).

● Indicators of flats (and their concatenations as well), that is, minimum nonzero weight codewords in Reed-Muller codes (see [22, Chapter 13]), in the form $\prod_{i\in I} (a_i\cdot x+\epsilon_i)$, where $a_i\in \mathbb F_2^n$, $\epsilon_i\in \mathbb F_2$, when we are able to ensure that the vectors $a_i$ are linearly independent. This provides weights $2^i$, where $i = 0, \dots, n$, which are also easy to produce but are peculiar, too. Note that this class of functions is (as the previous one) preserved by affine equivalence.

● Functions whose weight is smaller than twice-and-a-half the minimum distance $d$ of the Reed-Muller codes to which they belong. We have recalled above what these weights are when they are smaller than $2d$; between $2d$ and $2.5d$, the weights (determined in ^[17]) are too numerous for being recalled here; They are easy to produce but we encounter the same difficulty as for quadratic functions if we want to exhibit all functions with such weights: We know that they are affine equivalent to some particular functions, but ensuring such affine equivalence is not mathematically possible in an exhaustive way. Anyway, this strong result by Kasami, Tokura, and Azumi allows us to reach in Reed-Muller codes all weights smaller than 2.5 times the minimum distance (and their complements to $2^n$). The question is then to find as many other weights as possible.

● Some functions obtained by using the classic primary constructions of Boolean functions, in particular, Maiorana-McFarland, Niho, and ${\cal PS}_{ap}$-like constructions; see [8, Chapter 4]. This allows us to reach some weights, but numerous subclasses of functions have to be separately investigated for allowing us to cover enough weights. Finding the weights that are reachable often poses technical issues, to be overcome for each subclass, such as solving equations, which can be done in some cases but not in general. To give an example, the weights of those particular Maiorana-McFarland functions of the form $f(x, y) = x\cdot \phi(y)$, where $x\in \mathbb F_2^t, y\in \mathbb F_2^{n-t}$, $\phi$ is a function from $\mathbb F_2^{n-t}$ to $\mathbb F_2^t$, and "$\cdot$" is an inner product, are deduced from the relation $\sum_{(x, y)\in \mathbb F_2^n}(-1)^{f(x, y)} = 2^n-2w_H(f) = 2^t\, |\phi^{-1}(0)|$, which theoretically makes the study of the weights of these particular functions simpler. However, this replaces the difficulty of determining the weights of the functions having algebraic degrees of at most $r$ by that of determining the possible values of the size $|\phi^{-1}(0)|$ when $\phi$ has an algebraic degree of at most $r-1$, that is, when all its coordinate functions have algebraic degrees of at most $r-1$. This latter problem, which is interesting to study for its own sake, may be hard since it results in determining the possible numbers of solutions of nonlinear systems of equations. Denoting the coordinate functions of $\phi$ by $\phi_1, \dots, \phi_t$, the solutions of the equation $\phi(y) = 0$ are the elements of the support of the Boolean function $\prod_{i = 1}^t (\phi_i(y)+1)$, which has an algebraic degree of at most $t\, (r-1)$. In the case $t = 1$, we only get that the weights in $RM(r-1, n-1)$ are also weights in $RM(r, n)$ (which is clear since, denoting $x_i = y_{i-1}$ for $i = 2, \dots, n$, the $n$-variable function $x_1g(x_2, \dots, x_n)$ has the same Hamming weight as the $(n-1)$-variable function $g$), and as soon as $t\geq 2$, the situation becomes complex. For instance, for $r = 3$ and $t = 2$, we will arrive in general to the determination of the support of a function of degree 4, which instead of reducing the degree, increases it. Moreover, the weights that are easier to obtain correspond to a large value of $t$ and are then not quite general, since they have a valuation of at least $t$. The same kind of situation happens with the general Maiorana-McFarland, Niho, and ${\cal PS}_{ap}$-like constructions. Hence, even if it is possible to try using these classic constructions to reach weights in Reed-Muller codes, it is necessary, for reaching many weights, to have other approaches posing less problems; this is the purpose of the present paper.

● Direct sums of monomials and threshold functions (see a complete study of the cryptographic parameters of these functions in ^[10]). These are two cases where we can give the Hamming weights. The character sum $\sum_{x\in \mathbb F_2^t, y\in \mathbb F_2^{n-t}}(-1)^{f(x, y)}$ of a direct sum $f(x, y) = f_1(x)+f_2(y)$, of functions $f_1, f_2$ being the product of the character sums $\sum_{x\in \mathbb F_2^t}(-1)^{f_1(x)}$ and $\sum_{y\in \mathbb F_2^{n-t}}(-1)^{f_2(y)}$ of these functions, the Hamming weight of the direct sum $\prod_{i\in I_1}x_i+\dots +\prod_{i\in I_k}x_i$ of monomials (where the index sets $I_1, \dots, I_k$ are disjoint and $n = \sum_{j = 1}^k |I_j|$) satisfies $2^n-2w_H(f) = \prod_{j = 1}^k (2^{|I_j|}-2)$. The Hamming weight of the function whose support equals all vectors of a Hamming weight of at least $k$ equals $\sum_{i = k}^n {n\choose i}$. We find in both cases rather peculiar weights and, in the latter case, the algebraic degree needs to be determined.

There exist also secondary constructions of Boolean functions:

● The direct sum, already recalled above in the particular context of monomials, consists of adding functions whose sets of variables are disjoint. It gives weights that are a little peculiar: We have recalled above that if $f$ is the direct sum of a $t$-variable function $f_1$ and a $(n-t)$-variable function $f_2$, then the character sum of $f$ equals the product of the character sums of $f_1$ and $f_2$, and this implies:

This construction is interesting because it does not need particular precautions about the algebraic degree of $f$, which equals the maximum of the algebraic degrees of $f_1$ and $f_2$. Hence, for every weight $w_1$ in $RM(r, t)$ and every weight $w_2$ in $RM(r, n-t)$, the number $w$ such that $2^n-2w = (2^t-2w_1)(2^{n-t}-2w_2)$ is a weight in $RM(r, n)$), with the convention that if $r > t$, then $RM(r, t)$ equals $RM(t, t)$ (and can then have the weight of any integer between 0 and $2^t$). With this construction, there is a systematic way of building weights in $RM(r, n)$ from weights in $RM(r, t)$ and $RM(r, n-t)$.

● The indirect sum (see [8, Sections 6.1.16 and 7.1.9]) also deals with functions whose sets of variables are disjoint, but in a more complex way: We have two functions $f_1, f_2$ on the same set of $t$ variables, two functions $g_1$ and $g_2$ on the same set of $n-t$ variables, disjoint from the previous one, and $f(x, y) = f_1(x)+g_1(x)+(f_1(x)+f_2(x))(g_1(x)+g_2(x))$. We then have $\sum_{x\in \mathbb F_2^t, y\in \mathbb F_2^{n-t}}(-1)^{f(x, y)}$=$\frac 12(\sum_{x\in \mathbb F_2^t}(-1)^{f_1(x)})[\sum_{y\in \mathbb F_2^{n-t}}(-1)^{g_1(y)}+\sum_{y\in \mathbb F_2^{n-t}}(-1)^{g_2(y)}]$+$\frac 12(\sum_{x\in \mathbb F_2^t}(-1)^{f_2(x)})[\sum_{y\in \mathbb F_2^{n-t}}(-1)^{g_1(y)}-\sum_{y\in \mathbb F_2^{n-t}}(-1)^{g_2(y)}]$ and, therefore:

The algebraic degree of $f$ is not automatically bounded by $r$ from above, unless we take the initial functions $f_1, f_2$ in $RM(s, t)$ with $s\leq r$ and the initial functions $g_1, g_2$ in $RM(r-s, n-t)$ but this does not allow to provide interesting weights. If we take $f_1, f_2$ in $RM(r, t)$ and $g_1, g_2$ in $RM(r, n-t)$, this construction provides weights that are possibly less peculiar than with the direct sum, but in a much less systematic way, because we need to take care of the algebraic degree.

● The sum without extension of the number of variables (see [8, Sections 6.1.16 and 7.1.9]) takes three $n$-variable Boolean functions $f_1, f_2, f_3$ and defines the Boolean function $f = f_1f_2+f_1f_3+f_2f_3$. We have:

This secondary construction has been introduced because of the nice behavior of its Walsh transform, but it has the same drawback as the indirect sum about the algebraic degree of $f$.

● The so-called $(u|u+v)$-construction (see ^[22]) allows us to construct all of $RM(r, n)$ from $RM(r-1, n-1)$ and $RM(r, n-1)$. It corresponds to the fact that an $n$-variable Boolean function $f(x_1, \dots, x_n)$ can be written in the form $f_0(x_1, \dots, x_{n-1})+x_nf_1(x_1, \dots, x_{n-1})$ and has an algebraic degree of at most $r$ if and only if $f_0$ has an algebraic degree of at most $r$ and $f_1$ has an algebraic degree of at most $r-1$. The corresponding codeword is the concatenation of the codewords in $RM(r, n-1)$ associated to $f_0$ and $f_0+f_1$, and for the Hamming weight, it has the sum of the Hamming weights of these two functions.

The pairs $(f_0, f_0+f_1)$, when $f_0$ ranges over $RM(r, n-1)$ and $f_1$ ranges over $RM(r-1, n-1)$, do not provide all possible pairs of codewords in $RM(r, n-1)$ because of the restriction that $f_1$ has an algebraic degree of at most $r-1$, but if we impose that $f_0$ itself ranges over $RM(r-1, n-1)$, then the weights of the resulting codewords of $RM(r, n)$ range over the sums of two weights in $RM(r-1, n-1)$. This leads to a result given in ^[30] and used in ^[12]: For all pairs of integers $(r, n)$ with $0 \le r \le n$, the weight spectrum of $RM(r, n)$ includes as a subset $S+S,$ where $S$ is the weight spectrum of $RM(r-1, n-1)$. This result has allowed us to obtain the weight spectra of infinite classes of Reed-Muller codes, but only for orders that are very close to $n$.

A completely different way of evaluating weights in Reed-Muller codes consists of the fact that, for every Boolean function $f$ of an algebraic degree of at most $r$, we have ${\big (}\sum_{x\in \mathbb F_2^n}(-1)^{f(x)} {\Big)}^2 = \sum_{a\in \mathbb F_2^n}\sum_{x\in \mathbb F_2^n}(-1)^{D_af(x)}$, where for every $a$, the so-called derivative $D_af(x) = f(x)+f(x+a)$ has an algebraic degree of at most $r-1$. If we are able to determine the weights of all these derivatives, we obtain the absolute value of $\sum_{x\in \mathbb F_2^n}(-1)^{f(x)} = 2^n-2w_H(f)$, and since every Reed-Muller code is invariant under the complementation of its codewords, this provides two weights if $\sum_{x\in \mathbb F_2^n}(-1)^{f(x)}\neq 0$. However, this method, which is clearly more efficient for low orders $r$, is better suited for determining some specific weights than for systematically finding new weights in infinite classes of Reed-Muller codes.

It is then useful to find a new way, as systematic as possible, for providing weights (hopefully previously unknown) and codewords having such weights.

3.   A new construction of Boolean functions with an algebraic degree bounded from above

In this section, we present our construction. It comes from a formula that is satisfied by all Boolean functions of an algebraic degree bounded from above by some number $s$ (and therefore by all vectorial functions $F:\mathbb F_2^n\mapsto \mathbb F_2^m$ of an algebraic degree of at most $s$). This formula has been originally found and used (in ^[11]) in the framework of countermeasures against side channel attacks, a domain of applied cryptography. It also corresponds to what we call zero-sum sets, a notion used in the cryptanalysis of block ciphers. It could seem rather unrelated to coding theory in general and to the determination of weights in Reed-Muller codes in particular, but it is not, as we shall see. This formula depends on parameters (that are elements of $\mathbb F_2^n$) and will lead to numerous Boolean functions $f$ of the algebraic degree bounded from above, since the Hamming weight of these functions can be determined, to numerous weights in Reed-Muller codes.

3.1.   Degree-$s$ zero-sum sets as Reed-Muller codewords

A set $S\subseteq \mathbb F_2^n$ is called degree-$s$ zero-sum^|| if we have $\sum_{x\in S}f(x) = 0$ for every $n$-variable Boolean function $f$ of an algebraic degree of at most $s$ (and then $\sum_{x\in S}F(x) = 0$ for every vectorial function $F$ in $n$ variables of an algebraic degree of at most $s$).

^||This term comes from ^[3], which denotes by $d$ what we denote here by $s$; we prefer using $s$ to avoid any confusion with the minimum distance of codes.

The degree-$s$ zero-sum sets are then the supports of the codewords in the dual code of $RM(s, n)$. The dual of $RM(s, n)$ equals $RM(r, n)$ where $r = n-s-1$ ^[22] and degree-$s$ zero-sum sets are then the supports of the $n$-variable Boolean functions of an algebraic degree of at most $r$, that is, of the codewords of $RM(r, n)$. Hence, determining the possible sizes of degree-$s$ zero-sum sets is directly related to determining the weights in Reed-Muller codes.

3.2.   A construction of Boolean functions with bounded algebraic degree

We know from [11, Corollary 1] that if an $n$-variable Boolean function $f: \mathbb F_2^n\mapsto \mathbb F_2$ or, more generally a vectorial $(n, m)$-function $F: \mathbb F_2^n\mapsto \mathbb F_2^m$, has an algebraic degree of at most $s$, then for every $t > s$ and for every $a_1, \dots, a_{t}\in \mathbb F_2^n$, we have

(the sum, of course, being calculated modulo 2) where

for every $j \leq s$, with the conventions ${l\choose 0} = 1$ for every $l$ and $\sum_{i\in \emptyset}a_i = 0$.

According to (3.1), the set of all the elements $a$ of $\mathbb F_2^n$, which appear an odd number of times as $a = \sum_{i = 1}^{t} a_i$, or $a = \sum_{i\in J}a_i$ where $J$ has size at most $s$ and $\mu_{{t}, s }(|J|) = 1$, is a degree-$s$ zero-sum set. We then have the following result, in which, for every $a\in \mathbb F_2^n$, we denote by $\delta_a$ the Boolean function over $\mathbb F_2^n$ which takes value 1 at $a$ and 0 everywhere else (such a function can be called an atomic, or Dirac, or Kronecker function):

Theorem 1. Let $n$, $s\geq 0$ and $t\geq 1$ be integers such that $s < t$ and $s < n$. Given any elements $a_1, \dots, a_{t}$ of $\mathbb F_2^n$, the Boolean function:

(where $\mu_{{t}, s }(j) = {{t}-j-1\choose s -j} \bmod 2 = {{t}-j-1\choose t-s -1} \bmod 2$), has an algebraic degree of at most $r = n-s-1$.

Remark 1. (1) $f^{(s)}_{a_1, \dots, a_{t}}$ is in general not a symmetric function (that is, its value changes when we permute its input bits) despite the fact that its expression (3.2) is symmetric with respect to $a_1, \dots, a_t$ (i.e., its value does not change when we permute the $a_i$'s).

(2) For every positive integers $n, s, t$ such that $s < n$ and $s < t$, and every $a_1, \dots, a_t$ in $\mathbb F_2^n$, all the functions $f^{(s)}_{a_1, \dots, a_{t}}, f^{(s+1)}_{a_1, \dots, a_{t}}, \dots, f^{(t-1)}_{a_1, \dots, a_{t}}$ have algebraic degrees of at most $r$.

(3) Suppose that for some $n, s, t$, the function $f^{(s)}_{a_1, \dots, a_{t}}$ has an algebraic degree $r' < n-s-1$, then it is orthogonal to every codeword of the Reed-Muller code $RM(n-r'-1, n)$ with $n-r'-1 > s$, and it is, therefore, orthogonal to the Reed-Muller code $RM(s+1, n)$, whose elements satisfy the Relation (3.1). There seems to most often exist codewords of $RM(s+1, n)$ which do not satisfy Relation (3.1). We deduce that, most often, $f^{(s)}_{a_1, \dots, a_{t}}$ has in fact an algebraic degree of $r = n-s-1$ exactly. Examples 1 and 2 will illustrate this, but there are also examples where $f^{(s)}_{a_1, \dots, a_{t}}$ has an algebraic degree strictly smaller; see, for instance, Proposition 1.

Example 1. (toy example) Let $n = 3, s = 1$ (and, therefore, $r = 1$), $t = 4, a_1 = (1, 0, 0), a_2 = (0, 1, 0), a_3 = (0, 0, 1)$, and $a_4 = (1, 1, 1)$. We have $\mu_{t, s}(0) = {3\choose 1}\pmod 2 = 1, \mu_{t, s}(1) = {2\choose 0}\pmod 2 = 1$. Hence, $f^{(s)}_{a_1, a_2, a_3, a_{4}} = \delta_{a_1+a_2+a_3+a_{4}}+\delta_{(0, 0, 0)}+ \delta_{a_1}+ \delta_{a_2}+ \delta_{a_3}+ \delta_{a_4}$ is the indicator function of the affine plane $\{a_1, a_2, a_3, a_4\}$.

3.2.1.   Linear equivalence between the constructed functions when $a_1, \dots, a_{t}$ are linearly independent

We say that two $n$-variable Boolean functions $f, g$ are linearly (resp., affinely) equivalent if there exists a linear automorphism (resp., an affine automorphism) $L$ of $\mathbb F_2^n$ such that $g = f\circ L$, then $f$ and $g$ have the same Hamming weight and the same algebraic degree. All the functions in a same equivalence class contribute then for the same weight in the weight spectrum of the corresponding Reed-Muller code. We are then interested, when we find a function with a known algebraic degree and weight, to know whether it is inequivalent to previously found functions. For $t\leq n$, two choices "$a_1, \dots, a_{t}$", respectively, "$a'_1, \dots, a'_{t}$", of linearly independent elements give linearly equivalent functions $f^{(s)}_{a_1, \dots, a_{t}}$ and $f^{(s)}_{a'_1, \dots, a'_{t}}$, because there exists a linear automorphism $L$, mapping $a_1, \dots, a_{t}$ to $a'_1, \dots, a'_{t}$, respectively, and, therefore, mapping $\sum_{i\in J}a_i$ to $\sum_{i\in J}a'_i$ for every $J$. We then have $f^{(s)}_{a_1, \dots, a_{t}} = f^{(s)}_{a'_1, \dots, a'_{t}}\circ L$.

3.2.2.   Studying some particular cases of $(t, s)$ when $a_1, \dots, a_t$ are not necessarily linearly independent

For two choices $a_1, \dots, a_{t}$ and $a'_1, \dots, a'_{t}$, of linearly dependent elements, the corresponding functions $f^{(s)}_{a_1, \dots, a_{t}}$ and $f^{(s)}_{a'_1, \dots, a'_{t}}$ may not be affine equivalent. Of course, if $a_1, \dots, a_{t}$ and $a'_1, \dots, a'_{t}$ satisfy exactly the same linear relations over $\mathbb F_2$, then there is again a linear automorphism mapping $a_1, \dots, a_{t}$ to $a'_1, \dots, a'_{t}$, respectively (indeed, the two families have the same rank $k$; we can choose in each family $k$ elements generating the other elements of the family by the same relations and deduce such linear automorphism), but if not, then the functions $f^{(s)}_{a_1, \dots, a_{t}}$ and $f^{(s)}_{a'_1, \dots, a'_{t}}$ may be inequivalent.

Before seeing an example where $f^{(s)}_{a_1, \dots, a_{t}}$ and $f^{(s)}_{a'_1, \dots, a'_{t}}$ are not affine equivalent, let us systematically visit the first possible values of $s$ (for any $t > s$):

● Case $s = 0$: For $t\geq 1$, we have $f^{(0)}_{a_1, \dots, a_{t}} = \delta_{\sum_{i = 1}^{t} a_i}+ \delta_0$, which can have a weight of either 0 or 2; we get then only the two smallest weights of $RM(n, n-1)$;

● Case $s = 1$: For $t\geq 2$, we have $f^{(1)}_{a_1, \dots, a_{t}} = \delta_{\sum_{i = 1}^{t} a_i}+ ({t}-1)\, \delta_0+\sum_{i = 1}^t \delta_{a_i}$ (we omit the "$\bmod 2$"); if $t$ is even, then we get $\delta_{\sum_{i = 1}^{t} a_i}+ \delta_0+\sum_{i = 1}^t \delta_{a_i}$, which has an even weight of at most $t+2$, and if $n$ is odd, then we get $\delta_{\sum_{i = 1}^{t} a_i}+ \sum_{i = 1}^t \delta_{a_i}$, which has an even weight as well of at most $t+1$; Since $t$ is not bounded above, we get all possible weights of $RM(n, n-2)$ (and this case is then very different from the previous one): We can easily check that the weights 2 and $2^n-2$ are impossible and all other even weights between 0 and $2^n$ are possible; for instance, weight 4 is achieved by taking either $t = 2$ and $a_1, a_2$ nonzero and distinct (i.e., linearly independent over $\mathbb F_2$) or $t = 3$ and $a_1, a_2, a_3$ distinct;

● Case $s = 2$: For $t\geq 3$, we have $f^{(2)}_{a_1, \dots, a_{t}} = \delta_{\sum_{i = 1}^{t} a_i}+{{t}-1\choose 2 }\delta_0+({t}-2)\sum_{i = 1}^t \delta_{a_i}+ \sum_{1\leq i < j\leq t} \delta_{a_i+a_j}$; hence, if all the sums $a_i+a_j$ and the $a_i$ are nonzero and distinct, we have a function of a Hamming weight in $\left[\!\left[ \left. {t\choose 2}+t-1, {t\choose 2}+t+2\right]\!\right] \right.$ if $t$ is odd and in $\left[\!\left[ \left. {t\choose 2}-1, {t\choose 2}+2\right]\!\right] \right.$ if $t$ is even. If we only assume that all the sums $a_i+a_j$ are distinct, we have a function of a Hamming weight of at least ${t\choose 2}-2-t = \frac{t^2-3t-4}2$ if $t$ is odd and ${t\choose 2}-2 = \frac{t^2-t-4}2$ if $t$ is even.

● Case $s = 3$: For $t\geq 4$, we have $f^{(3)}_{a_1, \dots, a_{t}} = \delta_{\sum_{i = 1}^{t} a_i}+{{t}-1\choose 3 }\delta_0+{{t}-2\choose 2}\sum_{i = 1}^t \delta_{a_i}+ ({t}-3)\sum_{1\leq i < j\leq t} \delta_{a_i+a_j}+ \sum_{1\leq i < j < k\leq t} \delta_{a_i+a_j+a_k}$; hence, if all the sums $a_i+a_j+a_k$ are distinct, we have a function of a Hamming weight of at least ${t\choose 3}-2-t-{t\choose 2} = \frac{t^3-6t^2-t-12}6$ if $t$ is even and ${t\choose 3}-2-t = \frac{t^3-3t^2-4t-12}6$ if $t$ is odd.

Since, for the same value of $n$ and the same value of $t$, $f^{(1)}_{a_1, \dots, a_{t}} = \delta_{\sum_{i = 1}^{t} a_i}+ ({t}-1)\, \delta_0+\sum_{i = 1}^t \delta_{a_i}$ can have different Hamming weights according to the values of the $a_i$'s when they are linearly dependent, we have an example where $f^{(s)}_{a_1, \dots, a_{t}}$ and $f^{(s)}_{a'_1, \dots, a'_{t}}$ are not affine equivalent, even if $a_1, \dots, a_{t}$ are distinct as well as $a'_1, \dots, a'_{t}$.

Let us now systematically visit the first possible values of $t > s$ (for any $s$):

● For $t = s+1$, we have $\mu_{{t}, s }(j) = {s-j\choose s -j} \bmod 2 = 1$ for all $j\leq s$. Note that this was expected since Relation (3.1) expresses, in particular, that for a function of degree of at most $s$, the sum of the values of the function taken over any $(s+1)$-dimensional affine space equals 0. The Hamming weight $w_{s+1, s}$ of $f^{(s)}_{a_1, \dots, a_{s+1}}$ is at most $1+\sum_{j = 0}^s{t\choose j} = 2^{s+1}$. Hence, since $2^{s+1}$ equals the minimum distance of $RM(r, n)$, the Hamming weight of $f^{(s)}_{a_1, \dots, a_{s+1}}$ is either zero or $2^{s+1}$ (depending on the choice of $a_1, \dots, a_{s+1}$). More precisely:

Proposition 1. For every $s\geq 0$ and every linearly independent $a_1, \dots, a_{s+1}$ in $\mathbb F_2^n$, $f^{(s)}_{a_1, \dots, a_{s+1}}$ is the minimum weight codeword in $RM(r, n)$ whose support equals $\langle a_1, \dots, a_{s+1}\rangle$, the vector space over $\mathbb F_2$ generated by $a_1, \dots, a_{s+1}$. If $a_1, \dots, a_{s+1}$ are linearly dependent, then $f^{(s)}_{a_1, \dots, a_{s+1}}$ equals the zero function.

Proof. We have $f^{(s)}_{a_1, \dots, a_{s+1}} = \sum_{J\subseteq \{1, \dots, {s+1}\}} \delta_{\sum_{i\in J}a_i}$. If $a_1, \dots, a_{s+1}$ are linearly independent, then $f^{(s)}_{a_1, \dots, a_{s+1}}$ equals the indicator of the vector space generated by $a_1, \dots, a_{s+1}$ (and we obtain with the functions $f^{(s)}_{a_1, \dots, a_{t}}$ all the minimum weight codewords in $RM(r, n)$). If $a_1, \dots, a_{s+1}$ are linearly dependent, then the Hamming weight of $f^{(s)}_{a_1, \dots, a_{t}}$ is strictly less than the minimum distance of $RM(r, n)$, and it is then 0. Note that, assuming (without loss of generality, thanks to the invariance of $f^{(s)}_{a_1, \dots, a_{t}}$ when permuting the $a_i$'s) that $a_t = a_1+\dots +a_k$, for some $k < t$, it is easily seen that each Dirac function obtained after replacing $a_t$ by its value in the expression of $f^{(s)}_{a_1, \dots, a_{s+1}}$ appears an even number of times. This implies that this expression cancels. □

● For $t = s+2$, we have $\mu_{{t}, s }(j) = {s+1-j\choose s -j} \bmod 2 = (s+1-j) \bmod 2$ and $f^{(s)}_{a_1, \dots, a_{t}} = \delta_{\sum_{i = 1}^{t} a_i}+\sum_{k = 0}^{\lfloor \frac s2\rfloor }\sum_{J\subseteq \{1, \dots, {t}\}\atop |J| = s-2k} \delta_{\sum_{i\in J}a_i}$.

We have $w_{s+2, s}\leq 1+\sum_{k = 0}^{\lfloor \frac s2\rfloor }{s+2\choose s-2k} = 1+\sum_{k = 0}^{\lfloor \frac s2\rfloor }{s+2\choose 2k+2} = 2^{s+1}$. More precisely:

Proposition 2. For every $s\geq 0$ and every linearly independent $a_1, \dots, a_{s+2}$ in $\mathbb F_2^n$, $f^{(s)}_{a_1, \dots, a_{s+2}}$ is a minimum weight codeword in $RM(r, n)$. If $a_1, \dots, a_{s+1}$ are linearly dependent, then $f^{(s)}_{a_1, \dots, a_{s+1}}$ can equal a minimum weight codeword in $RM(r, n)$ or the zero function.

● For $t = s+3$, we have that $\mu_{{t}, s }(j) = {s+2-j\choose s -j} \bmod 2 = {s+2-j\choose 2} \bmod 2$ equals $\left\{\begin{array}{l}1\mbox{ if }s+2-j\bmod 4\in \{2, 3\}\\0\mbox{ if }s+2-j\bmod 4\in \{0, 1\}\end{array}\right.$, and we have:

3.3.   On the weights of the constructed functions

The interest of Theorem 1 is that it is possible to calculate mathematically, under some conditions, the Hamming weight of $f^{(s)}_{a_1, \dots, a_{t}}$, and that the weights obtained do not look peculiar.

Proposition 3. Let $n$, $s\geq 0$ and $t\geq 1$ be integers such that $s < t$ and $s < n$. For any elements $a_1, \dots, a_{t}$ of $\mathbb F_2^n$, let $f^{(s)}_{a_1, \dots, a_{t}}$ be the Boolean function given by (3.2). If $a_1, \dots, a_t$ are linearly independent over $\mathbb F_2$, then $f^{(s)}_{a_1, \dots, a_{t}}$ has Hamming weight:

where $\mu_{{t}, s }(j) = {{t}-j-1\choose s -j} \bmod 2$, and otherwise, it has a Hamming weight of at most $w_{t, s}$.

Indeed, the former assertion comes from the fact that, for any two distinct $J$, the corresponding elements $\sum_{i\in J}a_i$ are distinct, since $a_1, \dots, a_t$ are linearly independent over $\mathbb F_2$, and the latter is obvious. Note that the Hamming weight of $f^{(s)}_{a_1, \dots, a_{t}}$ has necessarily the same parity as $w_{t, s}$ since the atomic functions involved in (3.2) cancel by pairs, but since we already know that this weight is even because $r = n-s-1$ is strictly smaller than $n$, this only tells us that $w_{t, s}$ is even (while it may not always be a weight in $RM(r, n)$ when $t > n$). Note also that $w_{t, s}\geq 1+{t\choose s}$ since $\mu_{{t}, s }(s) = 1$ (and then the weight of $f^{(s)}_{a_1, \dots, a_{t}}$ cannot equal $w_{t, s}$ if ${t\choose s}\geq 2^n$), and that if $t-s$ is odd, then $w_{t, s}\geq 1+{t\choose s-1}+{t\choose s}$, since $\mu_{{t}, s }(s-1) = t-s$ (and then the weight of $f^{(s)}_{a_1, \dots, a_{t}}$ cannot equal $w_{t, s}$ if ${t\choose s-1}+{t\choose s}\geq 2^n$).

Example 2. Let us take $n = 12$, $r = 8$. We can check that $f^{(s)}_{a_1, \dots, a_{t}}$ can reach weight 166 in two cases where $a_1, \dots, a_t$ are linearly independent over $\mathbb F_2$. Indeed, for having $r = n-s-1 = 8$, we need to take $s = 3$. For the weight $w_{t, s} = 1+\sum_{j\in \{0, \dots, s\}; \atop \mu_{{t}, s }(j) = 1}{t\choose j}$ given by Proposition 3 to equal 166, we need to take $t\in\{10, 11\}$. Recall that all these functions are affine equivalent, for a fixed value of $t$. Denoting by $(e_1, \dots, e_{12})$ the canonical basis of $\mathbb F_2^{12}$ (made of all weight 1 vectors), we obtain then two classes of functions, that are respectively affine equivalent to $f^{(3)}_{e_1, \dots, e_{10}} = \delta_{\sum_{i = 1}^{10} e_i}+\sum\limits_{0\leq j\leq 3\atop {9-j\choose 3 -j} \bmod 2 = 1 } \sum\limits_{J\subseteq \{1, \dots, {10}\}; |J| = j} \delta_{\sum_{i\in J}e_i}$= $\delta_{\sum_{i = 1}^{10} e_i}+ \sum\limits_{J\subseteq \{1, \dots, {10}\}; |J| = 2} \delta_{\sum_{i\in J}e_i}+ \sum\limits_{J\subseteq \{1, \dots, {10}\}; |J| = 3} \delta_{\sum_{i\in J}e_i}$ and $f^{(3)}_{e_1, \dots, e_{11}} = \delta_{\sum_{i = 1}^{11} e_i}+\sum\limits_{0\leq j\leq 3\atop {10-j\choose 3 -j} \bmod 2 } \sum\limits_{J\subseteq \{1, \dots, {11}\}; |J| = j} \delta_{\sum_{i\in J}e_i} = \delta_{\sum_{i = 1}^{11} e_i}+\sum\limits_{J\subseteq \{1, \dots, {11}\}; |J| = 3} \delta_{\sum_{i\in J}e_i}$.

Recall (see e.g., [8, Subsection 10.1.1]) that denoting by $1_{E_{n, j}}$ the $n$-variable Boolean function whose support is the set $E_{n, j}$ of all vectors of a Hamming weight of $j$ in $\Bbb{F}_2^n$, we have $1_{E_{n, j}}(x) = \sum_{I\subseteq \{1, \dots, n\}\atop {|I|\choose j} = 1\pmod 2} x^I$. We then have $f^{(3)}_{e_1, \dots, e_{10}}(x) = (x_{11}+1)(x_{12}+1){\Big [}\prod\limits_{i = 1}^{10} x_j+ \sum\limits_{I\subseteq \{1, \dots, 10\}\atop |I|\in \{2, 3, 6, 7, 10\}}\prod\limits_{i\in I}x_i+ \sum\limits_{I\subseteq \{1, \dots, 10\}\atop |I|\in \{3, 7\}}\prod\limits_{i\in I}x_i{\Big]}$ and $f^{(3)}_{e_1, \dots, e_{11}}(x) = (x_{12}+1){\Big [}\prod\limits_{i = 1}^{11} x_j+ \sum\limits_{I\subseteq \{1, \dots, 11\}\atop |I|\in \{3, 7, 11\}}\prod\limits_{i\in I}x_i{\Big]}$ and these two functions both have an algebraic degree of 8.

It is interesting to notice that $w_{t, s}$, defined in Relation (3.3), does not depend on $n$ (we only have the condition that $n\geq t$). Of course, $n$ plays a role through the value of $r$.

We can see that the weights provided by Proposition 3 are few for low orders (since $t$ ranges from $n-r$ to $n$) and a little more numerous for large orders.

We now observe a property of $w_{t, s}$ that seems easier to show by considering Relation (3.3) than to infer directly from the way $f^{(s)}_{a_1, \dots, a_{t}}$ was derived:

Lemma 1. For every $s, i\geq 0$, we have $w_{s+2i+1, s} = w_{s+2i+2, s}\leq w_{s+2i+3, s}$ and this latter inequality is strict for $s > 0$.

Proof. According to Lucas' theorem (see, e.g., [22, Page 404]), we have that $\mu_{s+2i+1, s }(s-j) = {2i+j\choose j}\bmod 2$ equals 1 if, and only if, the binary expansion of $j$ is covered by that of $2i+j$, then $\mu_{s+2i+1, s }(s-j)$ has the same value for $j = 2k$ and $j = 2k+1$, while $\mu_{s+2i+2, s }(s-j) = {2i+j+1\choose j}\bmod 2$ shares the same value if $j = 2k$ and equals 0 if $j = 2k+1$. We deduce that $w_{s+2i+2, s} = 1+\sum_{0\leq j\leq s; j\, even; \atop \mu_{s+2i+1, s }(s-j) = 1}{s+2i+2\choose s-j} = 1+\sum_{0\leq j\leq s; j\, even; \atop \mu_{s+2i+1, s }(s-j) = 1}{\Big (}{s+2i+1\choose s-j}+{s+2i+1\choose s-j-1}{\Big)} = 1+\sum_{j\geq 0; j\, even; \atop \mu_{s+2i+1, s }(s-j) = 1}{s+2i+1\choose s-j}+\sum_{j\geq 0; j\, odd; \atop \mu_{s+2i+1, s }(s-j) = 1}{s+2i+1\choose s-j} = w_{s+2i+1, s}$. This proves the equality.

We have $\mu_{s+2i+3, s }(s-j) = {2i+2+j\choose j}\bmod 2 = {\Big (}{2i+1+j\choose j}+{2i+1+j\choose j-1}{\Big)}\bmod 2 = \mu_{s+2i+2, s }(s-j)+\mu_{s+2i+3, s }(s-j+1)$. If $\mu_{s+2i+3, s }(s-j+1) = 0$, then $\mu_{s+2i+3, s }(s-j) = \mu_{s+2i+2, s }(s-j)$. Using for $\mu_{s+2i+3, s }(s-j+1) = 0$ that ${s+2i+3\choose s-j}$ is strictly larger than ${s+2i+2\choose s-j}$ and for $\mu_{s+2i+3, s }(s-j+1) = 1$ that ${s+2i+3\choose s-j+1}$ equals ${s+2i+2\choose s-j}+{s+2i+2\choose s-j+1}$, we deduce that $w_{s+2i+3, s} = 1+\sum_{j\in \{0, \dots, s\}; \atop \mu_{s+2i+3, s }(s-j) = 1}{s+2i+3\choose s-j}\geq w_{s+2i+2, s} = 1+\sum_{j\in \{0, \dots, s\}; \atop \mu_{s+2i+2, s }(s-j) = 1}{s+2i+2\choose s-j}$ and the inequality is then verified. Moreover, if $s > 0$, then the inequality is strict. □

Open problem: Find a direct explanation of Lemma 1, from the proofs of [11, Theorem 1 and Corollary 1].

Remark 2. We have seen in the proof of Lemma 1 that $\mu_{s+2i+2, s }(s-j)$ equals 0 for every odd $j$. Hence, if all the elements $\sum_{i\in J}a_i$ are distinct for all $J\subset \{1, \dots, s+2i+2\}$ whose sizes are at most $s$ and have the same parity as $s$, then $f^{(s)}_{a_1, \dots, a_{s+2i+2}}$ has a Hamming weight of $w_{s+2i+2, s}$ as well. This is possible with $s+2i+2 > n$: Take, for instance, $s = 2$, $i = 1$, $n = s+2i+1 = 5$, $t = 6$, and $a_6 = a_5 +a_4$, then $\mu(t, s)(0) = 0, \mu_{t, s}(1) = 0, \mu_{t, s}(2) = 1$, and $a_1+\dots +a_6 = a_1+a_2 +a_3$, $a_1+a_2, a_1+a_3, a_1+a_4, a_12+a_5, a_1+a_6 = a_1$+$a_4+a_5, a_2+a_3$, $a_2+a_4, a_2+a_5, a_2+a_6$ = $a_2+a_4+a_5, a_3+a_4$, $a_3+a_5, a_3+a_6 = a_3+a_4+a_5$, $a_4+a_5, a_4+a_6 = a_5$, $a_5+a_6 = a_4$ are all distinct.

Open problem: Determine the exact Hamming weight of $f^{(s)}_{a_1, \dots, a_{t}}$ by means of $s$, $n$ and $a_1, \dots, a_t$ when the latter are linearly dependent over $\mathbb F_2$.

In the next corollary we call the weight spectrum of $RM(r, n)$ the list of all possible weights in $RM(r, n)$)

Corollary 1. Whatever the positive integers of $n$ and $r < n$ are, the weight spectrum of $RM(r, n)$ contains all the numbers:

Indeed, for every $t\leq n$, there exist $t$ linearly independent elements.

In Table 1, we give for $n\leq 21$ and for all $r = 1, \dots, n-1$, the list in regular roman^** of the values $w_{t, n-r-1}$ where $t$ ranges from $n-r$ to $n$. All these numbers are weights in $RM(r, n)$, and all the lists displayed for the input pairs $(n, r), (n, r-1), \dots, (n, 1)$ provide weights in $RM(r, n)$. We can check on these lists that Lemma 1 is verified, that is, the numbers go by pairs of consecutive equal values and the lists are nondecreasing.

^**The values in bold will be obtained below in Subsection 3.3.1.

We can find in Table 1 many numbers which were not known before as weights in $RM(r, n)$, such as 3004 or 6436 in $RM(6, 14)$.

3.3.1.   The weights in some cases where $a_1, \dots, a_t$ are linearly dependent

We have seen that restricting ourselves to the case where $a_1, \dots, a_t$ are linearly independent over $\mathbb F_2$ reduces the number of the weights, which can be found by using Theorem 1, because $t$ is then necessarily in the range $\{n-r, \dots, n\}$ and since, for fixed $n$ and $r$ (i.e., for fixed $n$ and $s$), all the obtained functions corresponding to the same $t$ have the same Hamming weight. In the present section, we investigate two cases where $a_1, \dots, a_t$ are linearly dependent. We shall see that the first does not provide more weights but the second does.

Case where two elements are equal: We study this case by curiosity, to check whether with $t$ elements $a_1, \dots, a_t$, it is identical to the case of $t-2$ elements or not (the formulas are different but the functions and/or the weights may be the same).

To ease the comparison, we start with $t+2$ elements $a_1, \dots, a_{t+2}$ such that (without loss of generality) $a_{t+2} = a_{t+1}$, then for every $J\subseteq \{1, \dots, t+2\}$, we have that $\sum_{i\in J}a_i$ equals $\left\{\begin{array}{l}\sum_{i\in J}a_i\mbox{ if }\{t+1, t+2\}\cap J = \emptyset\\\sum_{i\in J\setminus \{t+1, t+2\}}a_i\mbox{ if }\{t+1, t+2\}\subseteq J\end{array}\right.$. We get the same atomic function (which cancels then) if exactly one element among $\{t+1, t+2\}$ belongs to $J$, whether we choose $t+1$ or $t+2$.

We deduce that:

that is: $f^{(s)}_{a_1, \dots, a_{t+2}} =$

where $\mu_{t, s }(j)$ equals ${t-j-1\choose s-j}\bmod 2$ if $0\leq j\leq s$ and equals 0 otherwise.

For $s < t$, we obtain $f^{(s)}_{a_1, \dots, a_{t+2}} = f^{(s)}_{a_1, \dots, a_{t}}$. Indeed, $\mu_{{t+2}, s }(j)+ \mu_{{t+2}, s}(j+2) = {\Big (}{t-j+1\choose s-j}+{t-j-1\choose s-j-2}{\Big)}\bmod 2$ equals ${t-j-1\choose s-j}\bmod 2 = \mu_{t, s}(j)$.

Remark 3. We could additionally consider the cases $s = t$ and $s = t+1$ since, having $s < t+2$, we can still use Relation (3.2), with $t+2$ in the place of $t$. The only difference with the case $s < t$ is that the atomic function $\delta_{\sum_{i = 1}^{t} a_i}$ may equal one of the other atomic functions appearing in (3.4). When we evaluate the Hamming weight, we then have to consider particular cases according to whether $\delta_{\sum_{i = 1}^{t} a_i}$ is present in $\sum_{j = 0}^{s } {\Big (}\mu_{{t+2}, s }(j)+ \mu_{{t+2}, s}(j+2){\Big)}\sum_{J\subseteq \{1, \dots, {t}\}; |J| = j} \delta_{\sum_{i\in J}a_i}$ (that is, in $\sum_{j = s-1}^{s } {\Big (}\mu_{{t+2}, s }(j)+ \mu_{{t+2}, s}(j+2){\Big)}\sum_{J\subseteq \{1, \dots, {t}\}; |J| = j} \delta_{\sum_{i\in J}a_i}$), and then cancels, or not. Anyway, the sum $\sum_{j = 0}^s{\Big (}\mu_{{t+2}, s }(j)+ \mu_{{t+2}, s}(j+2){\Big)}{s\choose j}$ is smaller than or equal to $\sum_{j = 0}^s {s\choose j} = 2^s$ and the sum $\sum_{j = 0}^s {\Big (}\mu_{{t+2}, s }(j)+ \mu_{{t+2}, s}(j+2){\Big)}{s-1\choose j}$ is still smaller, and we will necessarily obtain 0 since $2^s$ is strictly smaller than the minimum distance of $RM(r, n)$.

Case where one element equals the sum of two others: We start with $t+1$ elements $a_1, \dots, a_{t+1}$ such that (without loss of generality) $a_{t+1} = a_t+a_{t-1}$ (and $t\geq 3$, so that there remains one element after cancellation in the sum $\sum_{i = 1}^y a_i$). For every $J\subseteq \{1, \dots, t+1\}$, we have that $\sum_{i\in J}a_i$ equals:

then:

where $\mu_{t, s }(j)$ equals ${t-j-1\choose s-j}\bmod 2$ if $0\leq j\leq s$ and equals 0 otherwise.

Proposition 4. Let $n\geq 3$, $s\geq 0$, and $t\geq 3$ be integers such that $s < t$ and $s < n$. For any elements $a_1, \dots, a_{t}$ of $\mathbb F_2^n$, let $f^{(s)}_{a_1, \dots, a_{t+1}}$ be the Boolean function given by (3.2) with $a_{t+1} = a_t+a_{t-1}$. If $a_1, \dots, a_t$ are linearly independent over $\mathbb F_2$, then $f^{(s)}_{a_1, \dots, a_{t+1}}$ has Hamming weight:

where $\mu_{t+1, s }(j)$ equals ${t-j\choose s-j}\bmod 2$ if $0\leq j\leq s$ and equals 0 otherwise (and the additions "$\mu_{{t+1}, s }(j)+\mu_{{t+1}, s }(j+3)$", etc., are made modulo 2). Here, $\epsilon$ equals $-1$ if $s\geq t-2$ and $\mu_{t+1, s}(t-2) = 1$, and equals 1 otherwise. If $a_1, \dots, a_{t}$ are linearly dependent, then $f^{(s)}_{a_1, \dots, a_{t+1}}$ has a Hamming weight of at most $w'_{t, s}$.

The value of $\epsilon$ is $-1$ when $\delta_{\sum_{i = 1}^{t-2} a_i}$ is equal to one of the other atomic functions present in the formula, and this is possible only when $s\geq t-2$ and $\mu_{{t+1}, s }(t-2)+\mu_{{t+1}, s }(t+1) = 1$, that is, $\mu_{{t+1}, s }(t-2) = 1$.

We obtain again the weights that we had obtained with linearly independent vectors $a_1, \dots, a_{t}$, and we obtain about 50% additional weights, which we display in bold (after these ones) in Table 1.

3.3.2.   Making linear combinations of the constructed functions

We have seen in the previous subsection that taking $a_1, \dots, a_t$ linearly dependent provides more weights than taking them linearly independent, but not in a large proportion (at least for the two cases that we studied: two elements equal and one element equal to the sum of two others). We need then to find other ways to provide more weights. One is very simple. Since all the functions $f^{(s)}_{a_1, \dots, a_{t}}$ have an algebraic degree of at most $r = n-s-1$, we can sum, for every choice of $s$, some of the functions $f^{(s)}_{a_1, \dots, a_{t}}, f^{(s+1)}_{a_1, \dots, a_{t}}, \dots, f^{(t-1)}_{a_1, \dots, a_{t}}$ for different choices of $t > s$ and of $a_1, \dots, a_t$.

The difficulty is to evaluate the Hamming weight of the resulting functions, but there is a case where the weight is easily determined: when we take disjoint families of vectors $a_i$ whose union is made of linearly independent vectors.

In the simplest case, we have (globally) $t$ linearly independent vectors $a_1, \dots, a_t$ in $\mathbb F_2^n$ (with $t\leq n$), and we partition $\{1, \dots, t\}$ in two subsets (without loss of generality, we can take these subsets equal to $\{1, \dots, l\}$ and $\{l+1, \dots, t\}$), then two functions $f^{(s)}_{a_1, \dots, a_{l}}$ and $f^{(s')}_{a_{l+1}, \dots, a_{t}}$ with $s < l$ and $s' < t-l$ have algebraic degrees of at most $r = n-s-1$ and $r' = n-s'-1$, respectively, and they have disjoint supports. Their sum has then an algebraic degree of at most $\max(r, r')$ and has for Hamming weight the sum of their Hamming weights, that is, $w_{l, s}+w_{t-l, s'}$.

Example 3. Let us take $n = t = 12$ and $s = s' = 2$, that is, $r = r' = 9$. We must take $l$ and $12-l$ strictly larger than $2$, that is, $l$ between 3 and 9. We find in Table 1 that, when $l$ ranges from 3 to 9, $(w_{l, 2}, w_{t-l, 2})$ takes the following values, indicated in the row corresponding to $n = 12$ and $r = 9$: $(8, 46), (8, 30), (16, 30), (16, 16), (30, 16), (30, 8), (46, 8)$, respectively. We obtain then the weights $54, 38, 46, 32, 46, 38, 54$ in $RM(9, 12)$. This way, we obtain two new weights (38 and 54) in $RM(9, 12)$.

Example 3 can be generalized:

Proposition 5. Let $n$ and $r < n$ be any positive integers. All the numbers $w_{l, n-r_1-1}+w_{t-l, n-r_2-1}$, where $t\leq n$, $n-r_1\leq l\leq t- n+r_2$, $r_1\leq r$, $r_2\leq r$ and $r_1+r_2\geq 2n-t$ are weights in $RM(r, n)$.

This is straightforward. The condition $l\leq t- n+r_2$ is for having $t-l\geq n-r_2$ and the condition $r_1+r_2\geq 2n-t$ is for having $n-r_1\leq t- n+r_2$. The condition $l\leq t$ is automatically satisfied thanks to $l\leq t- n+r_2$.

Of course, Proposition 5 can be generalized to sums of more than two numbers (taking more than two families partitioning $\{a_1, \dots, a_t\}$).

Remark 4. The conditions $r\geq r_1, r_2$ and $r_1+r_2\geq 2n-t$ imply that $2r\geq 2n-t$, that is, $t\geq 2n-2r$ and since $t$ cannot be larger than $n$, this means that Proposition 5 can be used only if $n\geq 2n-2r$, that is, $r\geq \frac n2$. Our results are then unfortunately limited to those of Proposition 3 (that is, those of Table 1) for the orders in the lower half of $[0, n]$ (those for which the table provides the least values), in particular for the smallest order for which the weight spectrum is unknown: $r = 3$. We shall see below that, on the contrary, we can derive a very large number of weights as soon as $r$ is large enough.

Note that if we partition $\{a_1, \dots, a_t\}$ in three families $\{a_1, \dots, a_l\}$, $\{a_{l+1}, \dots, a_k\}$ and $\{a_{k+1}, \dots, a_t\}$, we get the weight $w_{l, n-r_1-1}+w_{k-l, n-r_2-1}+w_{t-k-l, n-r_3-1}$ (instead of $w_{l, n-r_1-1}+w_{t-l, n-r_2-1}$ that we had with two families), and conditions $l\geq n-r_1$, $k-l\geq n-r_2$ and $t-k-l\geq n-r_3$ imply $t\geq 3n-(r_1+r_2+r_3)$, that is, $3r\geq r_1+r_2+r_3\geq 3n-t\geq 2n$, and the condition $r\geq \frac n2$ becomes $r\geq \frac{2n}3$.

For each $n\leq 23$, the weights provided by Proposition 5 can be obtained by adding in Table 1 any number located in any row $r_1\leq r$ at the $k$-th position (by taking $k = l-(n-r_1)+1$ so that it starts at position 1 in the list given by Table 1) where $k\leq t- n+r_2-(n-r_1)+1 = t-2n+r_1+r_2+1$, and the number located in any row $r_2\leq r$ such that $r_1+r_2\geq 2n-t$, at the position corresponding to $t-l$, that is at the position $t-(k+n-r_1-1)-(n-r_2)+1 = t-k-2n+r_1+r_2+2$. It is for large orders that our method gives the best results, since the weights are then more numerous in Table 1; and making sums (applying Proposition 5) is also possible only when $r\geq \frac n2$, and these sums are more numerous when $r$ is larger.

Example 3, revisited: For $n = 12$ and $r = 9$, the condition $t\geq 2n-2r$ writes $t\geq 6$, and we obtain the following:

For $t = 12$: The conditions $r_1, r_2\leq r$ and $r_1+r_2\geq 2n-t$ allow $(r_1, r_2) = (3, 9); (4, 8), (4, 9); (5, 7), (5, 8), (5, 9); \dots; (9, 3), (9, 4), \dots, (9, 9)$, which provide the following weights:

For (3, 9): 520

for (4, 8): 272

for (4, 9): 264 and 264

for (5, 7): 160

for (5, 8): 144 and 144

for (5, 9): 144 and 136 and 264

for (6, 6): 128

for (6, 7): 96 and 96

for (6, 8): 100 and 80 and 152

for (6, 9): 80 and 80 and 144 and 144

for(7, 5), we have the same as for the swap (5, 7)

for (7, 6), we have the same as for the swap

for (7, 7): 104 and 64 and 104

for (7, 8): 68 and 68 and 88 and 88

for (7, 9): 62 and 48 and 88 and 80 and 264

for (8, 4), (8, 5), (8, 6), (8, 7), we have the same as for their swaps,

for (8, 8): 110 and 52 and 72 and 52 and 110

for (8, 9): 46 and 46 and 52 and 52 and 102 and 102

for (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8) we obtain the same as for their swaps

for (9, 9): 54 and 38 and 46 and 32 and 46 and 38 and 54.

For this single value of $t$, we have then obtained in addition to the weights present in Table 1 and to the two weights 38 and 54 found above: 48, 52, 62, 72, 80, 88, 96,100,102,104,110,136,144,152,160,264,272,520.

We would also have to consider all the other values of $t$, from 11 down to 6.

As mentioned after Proposition 5, we could find more weights by partioning $\{a_1, \dots, a_t\}$ in more than two families.

We see that our method gives in fact a large number of weights, for sufficiently large orders, that is, when the usual constructions of Boolean functions (Maiorana-McFarland, etc.) give the worst results. It is then nicely complementary to the method using classic constructions.

Example 4. We have seen in introduction that trying to determine the weight spectrum of all codes $RM(n-c, n)$ for $c = 6$ (the smallest value of $c$ for which this is an open problem) requires determining the weights in $RM(6+k, 12+k)$, for some $k\geq 0$.

– Let us first consider $RM(6, 12)$. Table 1 already provides the weights 64,128,136,208,256,384,496,512,628,736,784,992, 1024, 1288, 1420, 1472, 1744, 2016, 2048, 3004. We could complete with the weights provided by Kasami-Tokura. We could also add the weights obtained by adding 16 weights from $RM(2, 8)$ (that are 0, 64, 96,112,120,128,136,144,160,192,256 according to what we know on quadratic functions) and adding 8 weights of $RM(3, 9)$ (that are 0, 64, 96,112,120,128,136,144,148,152,156,160,164,168,172,176,180,184,188,192,196,200,204,208,212,216,220,224,228,232,236,240,244,248,252,256,260,264,268,272,276,280,284,288,292,296,300,304,308,312,316,320,324,328,332,336,340,344,348,352,356,360,364,368,376,384,392,400,416,448,512, see the URL: https://isec.ec.okayama-u.ac.jp/home/kusaka/wd/RM/tomita/RM512_130.wd).

The weights of $RM(4, 10)$ and $RM(5, 11)$ are unknown (but we know from Table 1 that they include respectively 64,128,136,208,256,384,496,512,628 and 64,128,136,208,256,384,496,512,628,736,784,992, 1024, 1420. We can add the weights obtained by adding weights from $RM(r_1, 12)$ and $RM(r_2, 12)$ in Table 1 as explained above. For $n = 12$ and $r = 6$, the condition $n\geq t\geq 2n-2r$ writes $t = 12$. The conditions $r_1, r_2\leq r$ and $r_1+r_2\geq 2n-t$ allow only one possibility: $(r_1, r_2) = (6, 6)$, which provides only one weight (since the number $k\in \{1, t-2n+r_1+r_2+1\}$ in the description we gave can take value 1 only): 128, which is already there.

– Let us then consider $RM(7, 13)$. Table 1 already provides the weights 64,128,136,208,256,384,496,512,628,736,784,992, 1024, 1288, 1420, 1472, 1744, 1948, 2016, 2048, 3004, 3008, 3664, 4096, 6008. Note also that the weights of $RM(6, 12)$ are also weights of $RM(7, 13)$, but this provides no new weight. We could complete with the weights provided by Kasami-Tokura, and we can add the weights obtained by adding weights from $RM(r_1, 13)$ and $RM(r_2, 13)$ in Table 1 as explained above. For $n = 13$ and $r = 7$, the condition $n\geq t\geq 2n-2r$ writes $t\in \{12, 13\}$.

- For $t = 13$, the conditions $r_1, r_2\leq r$ and $r_1+r_2\geq 2n-t$ allow (up to a swap between $r_1$ and $r_2$): $(r_1, r_2) = (7, 6), (7, 7)$. The case (7, 6) provides one weight (the number $k\in \{1, t-2n+r_1+r_2+1\}$ can take value 1 only): 96. The case (7, 7) provides one weight (the number $k\in \{1, t-2n+r_1+r_2+1\}$ can take values 1 and 2, which give the same weight): 64 which was already there.

- For $t = 12$, the conditions $r_1, r_2\leq r$ and $r_1+r_2\geq 2n-t$ allow: $(r_1, r_2) = (7, 7)$, which provides the weight 64 also already obtained.

We could continue by visiting $RM(8, 14)$ (which is the first case where we obtain a weight not divisible by 4: 3474) etc., but with this example, we see the huge difference between low and high orders.

We leave as an open problem the determination of more weights in $RM(6, 12)$ (and in particular, some that are not divisible by 4), which will probably need to find another method than exploiting Relation (3.1).

3.4.   The ANF of the constructed functions when $a_1, \dots, a_{t}$ are linearly independent over $\mathbb F_2$

We have seen that for $t\leq n$, two choices "$a_1, \dots, a_{t}$", respectively "$a'_1, \dots, a'_{t}$", of linearly independent elements give linearly equivalent functions, having then the same weight and the same algebraic degree.

Let us then determine the ANF of $f^{(s)}_{e_1, \dots, e_{t}}$, where $t\leq n$. We shall need the following lemma:

Lemma 2. Let $n\geq 1, t\geq 1, j\geq 0$ be integers such that $j\leq t\leq n$ and let $e_1, \dots, e_{t}$ be the $t$ first elements of the canonical basis of $\mathbb F_2^n$. The Boolean function:

has for ANF:

where $|\dots |$ denotes the size and $j\preceq m$ means that if $j = \sum_{k\in K}2^k$ and $m = \sum_{l\in L}2^l$ are the binary expansions of $j$ and $m$, then $K\subseteq L$.

Proof. Since $\sum_{i\in J}e_i$ is the vector of support $J$, we have, denoting $x = (x_{1}, \dots, x_{n})$:

where these sums are taken modulo 2 and ${|\{1, \dots, t\}\cap I|\choose j}$ equals 0 if $|\{1, \dots, t\}\cap I| < j$. The proof is complete thanks to Lucas' theorem [22, page 404]. □

We deduce:

Proposition 6. Let $n\geq 1$, $s\geq 0$ and $t\geq 1$ be integers such that $s < t$ and $s < n$. Given any linearly independent elements $a_1, \dots, a_{t}$ of $\mathbb F_2^n$, the Boolean function (3.2) is linearly equivalent to the function of ANF:

where $\mu_{{t}, s }(j) = {{t}-j-1\choose s -j} \bmod 2 = {{t}-j-1\choose t-s -1} \bmod 2$.

This is straightforward since $f^{(s)}_{e_1, \dots, e_{t}} = h_{t, e_1, \dots, e_t}+\sum_{j = 0}^{s } \mu_{{t}, s }(j)\, h_{j, e_1, \dots, e_t}$. □

Remark 5. Even after these caculations, it is not obvious to see (what we already know) that $f^{(s)}_{e_1, \dots, e_{t}}$ has an algebraic degree of at most $r = n-s-1$, that is, for every $I\subseteq \{1, \dots, n\}$ whose size is strictly larger than $r$, we have $\sum_{0\leq j\leq s\atop j\preceq |\{1, \dots, t\}\cap I|} \mu_{{t}, s }(j) = 1\bmod 2$ if $\{1, \dots, t\}\subseteq I$ and $\sum_{0\leq j\leq s\atop j\preceq |\{1, \dots, t\}\cap I|} \mu_{{t}, s }(j) = 0\bmod 2$ otherwise.

Open problem: Determine the exact algebraic degree of $f^{(s)}_{a_1, \dots, a_{t}}$ by means of $s$, $n$ and $a_1, \dots, a_t$.

Subproblem: Determine the algebraic degree of $f^{(s)}_{a_1, \dots, a_{t}}$ by means of $s$ and $n$ when $a_1, \dots, a_t$ are linearly independent.

Still more complex is the following:

Open problem: Determine what can be the ANF of $f^{(s)}_{a_1, \dots, a_{t}}$ when $a_1, \dots, a_{t}$ are linearly dependent.

4.   Conclusions

We have introduced a novel way of constructing Reed-Muller codewords. It consists of exploiting relations satisfied by all $n$-variable Boolean or vectorial functions $F$ of an algebraic degree of at most $s$ (corresponding when $F$ is Boolean to codewords in $RM(s, n)$), these relations being interpretable in terms of the orthogonality between some Boolean function, say $f$, and (the coordinate functions of) all such $F$. Function $f$ belongs then to $RM(r, n)$, where $r = n-s-1$. This construction depends on $n$, $s$ (or $r$), a parameter $t$ and the choice of $t$ vectors $a_i$. We showed how it allows us to determine weights in Reed-Muller codes that are not accessible by other methods, as far as we know, and in a simpler way. As a matter of fact, our method for determining weights in Reed-Muller codes is complementary of the classic method, which consists of using the known constructions, since the latter is more efficient for low orders and our method is more efficient for large orders. Anyway, the method using the known constructions poses technical problems (and provides a number of weights that is small compared to the amount of work needed) while ours provides weights with less difficulties. Functions having the weights we can derive with our method can be deduced, as well as a general form of their ANF when the vectors $a_i$ are linearly independent, but determining mathematically their exact algebraic degree seems difficult. This is one of the open problems we proposed. We also found more weights by considering cases where the vectors are linearly dependent. We could also identify that with some of the constructed functions having disjoint supports, the weights of the sums are equal to the sums of the weights; this provided for each Reed-Muller code of a sufficiently large order a very large number of new weights.

More work is possible in many directions, for instance, by investigating as many cases of functions as possible where the vectors $a_i$ are linearly dependent and studying sums of such functions as well. Moreover, there may be other relations to find that are interpretable in terms of orthogonality, leading to more codewords and weights in Reed-Muller codes. This may provide an avenue for further results, with the ultimate goal of determining all the weight spectra of Reed-Muller codes (starting with those of high orders when they are still unknown, since they seem to be more accessible than those of low orders larger than 2), and still better, their weight distributions.

Use of AI tools declaration

The author declares he has not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

We deedply thank Stjepan Picek for his kind help with the tables; we are indebted to him.

The research of the author is partly supported by the Norwegian Research Council.

Conflict of interest

The author declares no conflict of interest.