Classification of B(3,5,7) = RM(5,7)/RM(2,7)

This page reports the numerical experiments related to the classification of Boolean functions in B(3,5,7), which we computed in autumn 2026. They can be used to prove that the covering radius of RM(2,8) is smaller than 96, a result obtained during the M2 internship of Jean-Baptiste Nguyen.

Definitions

Let m be a positive integer. The space of Boolean functions from GF(2)^m into GF(2) of degree at most k is denoted by RM(k,m). This notation comes from coding theory: it is the Reed-Muller code of order k in m variables. The affine group AGL(m,2) acts on the spaces RM(k,m), and thus on RM(k,m)/RM(r,m) when r ≤ k. Two Boolean functions f and g are said to be equivalent modulo RM(r,m), or r-equivalent for short, if there exists an affine transformation A in AGL(m,2) such that

g = f ∘ A modulo RM(r,m),

where AGL(m,2) is the affine group of order

#AGL(m,2) = 2^m (2^m − 1)(2^m − 2) … (2^m − 2^m−1).

It can be generated by three transformations: the shift S, a transvection T and a nontrivial translation U. The affine group acts on RM(k,m) and also on B(s,t,m) := RM(t,m)/RM(s−1,m). A formula for the rank n(s,t,m) of the action of AGL(m,2) on B(s,t,m) was determined by Xiang-Dong Hou [2].

It satisfies

n(s,t,m) = n(m−t, m−s, m).

Notations

NL₂(f) is the nonlinearity of order 2 of f: the minimum Hamming distance between f and RM(2,m).
B(s,t,m) denotes the quotient space RM(t,m)/RM(s−1,m).
δ_a is the indicator function of the vector a.
A coset f + RM(2,7) is an urcoset if NL₂(f + δ_a) < NL₂(f) for every a in GF(2)^m.

Objectives

Class numbers of B(s,t,7)
s/t	1	2	3	4	5	6	7
0	3	12	3486	10^13.5	10^19.8	10^21.9	10^22.2
1	2	8	1890	10^13.1	10^19.5	10^21.6	10^21.9
2		4	179	10^11.0	10^17.3	10^19.5	10^19.8
3			12	68443	10^11.0	10^13.1	10^13.5
4				12	179	1890	3486
5					4	8	12
6						2	3
7							2

The objective of this numerical experiment is to provide the classification of B(3,5,7) = RM(5,7)/RM(2,7). This is an almost unreasonable task, because the class number n(3,5,7) equals 118 140 881 980. It can be used to prove that the covering radius of RM(2,8) is smaller than 96.

Methodology

Recall that the classification of B(3,4,7) is already available; it is described on that project page. The descending method and the classification of B(3,4,7) = RM(4,7)/RM(2,7) are presented in [6]; the same approach was applied in eight variables in [7]. For earlier bounds on the covering radius of RM(2,7), see [5].

We use the descending method, starting from the classification of B(4,5,7). For an element h of B(4,5,7) whose 3-stabilizer is denoted by S, we use two ways to compute the classification of h + B(3,3,7) under the boundary action of S. The main issue is how to store the data. There are 179 classes in B(4,5,7), and we focus on those of degree 5.

For each element h of B(4,5,7), identified by a number between 1 and 179, we provide a text file rho/rho-{id} and a 2 GB binary file data/{id}-3-3-7.zip that describe the orbit of h in a table of 2³² bytes. A homogeneous cubic of B(3,3,7) is represented by a 35-bit word. If bit number i of the byte T[j] is on, then j×8 + i is the 35-bit integer representing an element of the orbit of h under its 3-stabilizer.

standard basis of B(3,3,7):
abc  abd  acd  bcd  abe  ace  bce  ade  bde  cde  abf  acf  bcf  adf  bdf  cdf  aef  bef  cef  def  abg  acg  bcg  adg  bdg  cdg  aeg  beg  ceg  deg  afg  bfg  cfg  dfg  efg

[ class info B(3,5,7) ] [ data ]

The cubic parts of the members of the orbit of the class {num} is stored in the file {num}-3-3-7.zip.gz which a compression of the bit file indicator {num}-3-3-7.zip.

Application: ρ(2,8) < 96

We show that the covering radius of RM(2,8) cannot equal 96, that is, no Boolean function in 8 variables is at distance 96 from RM(2,8). The proof relies on an analysis of 7-variable functions of quadratic nonlinearity NL₂ = 40, which is the maximum possible in dimension 7, since the covering radius of RM(2,7) is 40 [3] (the covering radius of RM(2,6) is 18, by Schatz [1]).

Using the classification of B(3,4,7), we found 4 classes of quartics with NQ = 40.
Using the classification of B(3,5,7), we found 50 classes with NQ ≥ 38
Prange filter eliminates most of representative with NQ< 38
13 classes of quintics with NQ = 38;
no quintic with nonquadraticity 40.

All the quintics with nonquadraticity 38 are orphans, which proves that functions of degree 6 or 7 have NQ < 40.

Finally, applying Wang's arguments [3], [4] gives ρ(2,8) < 96.

[ NQ 38-40 ]

References

J. Schatz, The second order Reed-Muller code of length 64 has covering radius 18, IEEE Transactions on Information Theory 27 (1981), 529–530.
X.-D. Hou, AGL(m,2) acting on R(r,m)/R(s,m), Journal of Algebra 171(3) (1995).
Q. Wang, The covering radius of the Reed-Muller code RM(2,7) is 40, arXiv:1809.04864 (2018).
Q. Wang, P. Stănică, New bounds on the covering radius of the second order Reed-Muller code of length 128, Cryptography and Communications, doi:10.1007/s12095-018-0289-2.
Q. Wang, On the covering radius of the second order Reed-Muller code of length 128, arXiv:1510.08535 (2015).
V. Gillot, P. Langevin, Classification of some cosets of the Reed-Muller code, arXiv:2208.02469 (2022).
V. Gillot, P. Langevin, Covering radius of RM(4,8), arXiv:2305.03493 (2023).

[ NQ 38-40 ] [ slides ] [ abstract ] [ article ] [ data ] [ clip ]

Valérie Gillot, Philippe Langevin, at IMATH in Toulon.
Last modification: autumn 2026.