Covering radius of RM(4,8)

This page reports the numerical experiments related to the classification of the Boolean Functions in 8 variables that we computed in Autumn 2022. Mainly, we use a part of the classification obtained in 7 variables to classify the space RM(6,8)/RM(4,8) from which we deduce novelties about the covering radius of RM(4,8).


Let m be a positive integer. The space of Boolean functions from GF(2)^m into GF(2) 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 AG(2, m) acts over 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) if there exists an affine transformation A in AG(2,m) such that

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

Affine group

The affine group has order :

#AG(2, m) = 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 over RM(k,m) and also over B(s,t,m) := RM(t,m)/RM(s-1,m). A formula for the rank n(s, t, m) of the action of AG(2,m) over B(s,t,m) was determined by Xiang-Dong Hou,

AGL(m, 2) Acting on R(r, m)/R(s, m), journal of algebra 171/3 (1995)
It satisfies :
n(s, t, m ) = n( m-t, m - s, m)


s/t 2 3 4 5 6 7 8
1 9 38148301027.61044.51052.91055.31055.6
2 5 207481025.21042.01050.51052.91053.2
3 321016.71033.61042.01044.51044.8
4 9991016.71025.21027.61027.9
5 32 20748 3814830 7611801
6 5 9 14
7 2 3
8 2
some class numbers of B(s,t,8)

The objective of this numerical experiment consists in providing the classifications of B(5,6,8) = RM(6,8)/RM(4,8) to deduce the covering radius of RM(4,8).

Methodology - Result - Application

The details are given in the following
[ ALCOCRYPT slides ] [ abstract ] [ FQ15 slides ] [ FQ15 abstract ] [ article ] [ data ] [ clip ]

Valérie Gillot, Philippe Langevin,
Institut Mathématiques de Toulon,
last modification : june 2023.