covering radius code RM(2,7), RM(3,7), RM(2,8) and RM(3,8)

Covering radius of RM-code in 7-8 variables

This page reports our numerical experiments related the determination of covering radii of Reed-Muller 7 and 8 variables started in Autmun 2023. Mainly, we use the classification :

[classification of B(6) ] [classification of B(7) ]

Reed-Muller codes

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)

Covering radius

All the classical parameters of RM-codes are easy to determine execept for the covering radius. The covering radii of RM-codes in less than 8 variables are known thanks to the following papers.

 
E. Berlekamp and  L. R. Welch,  
Weight distributions of  the cosets of  the (32,6)  Reed-Muller code
IEEE Trans. Inform. Theory,  vol. IT-18,  pp..203-207,  1972 .

J. Mykkelveit. The covering radius of the [128,8] Reed-Muller code is
56. IEEE Trans. Inform. Theory, vol. 26 (3), pp. 359-362, 1980.

James R. Schatz:
The second order Reed-Muller code of length 64 has covering radius 18. 
IEEE Trans. Inf. Theory 27(4): 529-530 (1981)

MR1385376 - Covering radius of the Reed-Muller code R(1,7) -- a simpler proof
Hou, Xiang-Dong
J. Combin. Theory Ser. A 74 (1996), no. 2, 337–341.

MR4604461 - The covering radius of the third-order Reed-Muller code RM(3,7) is 20
Gao, Jinjie; Kan, Haibin; Li, Yuan; Wang, Qichun
IEEE Trans. Inform. Theory 69 (2023), no. 6, 3663–3673.

MR3990033 - The covering radius of the Reed-Muller code RM(2,7) is 40
Wang, Qichun
Discrete Math. 342 (2019), no. 12, 111625, 7 pp.

The covering radius of the Reed-Muller code RM(4,8) 
Gillot, Valérie; Langevin, Philippe
Communication in Cryptography  (2023)
doi:10.1007/s12095-023-00652-4

covering radii of RM-codes in 7-8 variables
m\k	1	2	3	4	5	6	7	8
r(k,8)	120	88-96	50-60	26	10	2	1	0
r(k,7)	56	40	20	8	2	1	0	-
r(k,6)	28	18	8	2	1	0	-	-

The case of the second and third Reed-Muller codes are still open!

Methodology

r( k, m ) ≤ r(k,m-1) + r(k-1, m-1)

[student project 1] Use the classification of B(3,4,7) to determine the classification of Boolean functions having high nonlinearity of order 2 in B(3,4,7).
[student project 2] Use the classification of B(4,7,7) to determine the classification of Boolean functions having large nonlinearity of order 3 in B(7).
Combine the above classificiations to check new upper/lower bounds on the (relative?) covering radii of RM(2,8) and RM(3,8).

Link to the student code M1 2024 : code on githhub

Non linearity of order 2 in 7 variables

Applying non probabilist methode to the ~B(3,4,7) x B(5,5,7) :

The script rho27.sh determines a cover set of Boolean functions in the space B(3,5,7) having non linearity of order 2 greater or equal to 36.

[36 ≤ NL_2(7) ≤ 40, in B(3,5,7)] [optimal]

Non linearity of order 3 in 7 variables

Applying probabilist methode to the ~B(4,4,7) :

The script rho37.sh determines a cover set of Boolean functions in the space B(4,7,7) having non linearity of order 3 greater or equal to 16.

[16 ≤ NL_3(7) ≤ 20] [optimal]

Covering radius of RM(2,8)

Covering radius of RM(3,8)

Valérie Gillot, Philippe Langevin,
Institut Mathématiques de Toulon,
last modifications : june, november 2023, february 2024.