Covering radius of $ RM(4,8) $

Valérie Gillot; Philippe Langevin

doi:10.3934/amc.2023038

Article Contents

2024, Volume 18, Issue 2: 383-393. Doi: 10.3934/amc.2023038

This issue Previous Article On the minimum distance, minimum weight codewords, and the dimension of projective Reed-Muller codes Next Article Quasi-twisted codes as contractions of quasi-cyclic codes

Covering radius of $ RM(4,8) $

Valérie Gillot and
Philippe Langevin^,

Imath, université de Toulon, France

^*Corresponding author: Philippe Langevin
^*Corresponding author: Philippe Langevin

Received: April 2023

Revised: August 2023

Early access: October 10, 2023

Published online: October 10, 2023

This work is partially supported by the French Agence Nationale de la Recherche through the SWAP project under Contract ANR-21-CE39-0012.

Abstract / Introduction Full Text(HTML) Figure(1) / Table(4) Related Papers Cited by

Abstract

We propose an effective version of the lift by derivation, an invariant that allows us to provide the classification of $ B(5,6,8) = RM(6, 8)/RM(4, 8) $. The main consequence is to establish that the covering radius of the Reed-Muller $ RM(4,8) $ is equal to 26.

Keywords:

Mathematics Subject Classification: Primary: 11T71.

Citation:

Full Text(HTML)

Figure 1. Strategy to compute $ \rho(4,8) $

Download: Full-size image PowerPoint slide

Table 1. Updated Table of Handbook of coding theory

$k$	1	2	3	4	5	6	7	8
$\rho(k,8)$	120	$88^a$ – 96	$50^b$ – $67^f$	26$^c$	10	2	1	0
$\rho(k,7)$	56	$40^d$	$20^e$	8	2	1	0

| Show Table

DownLoad: CSV

Table LISTING 1. Invariant

Algorithm Invariant( f, s, t, m )

{ // f element of B(s, t, m)

for each v in $\mathbb{F}_2^m$

$\mathrm{g} \leftarrow \mathrm{d}_v f$

$\left.\mathrm{h} \leftarrow g\right|_{E_v}$

F[v] := ClassNumber(h, s-1, t-1, m-1)

return FourierTransform(F)

}

| Show Table

DownLoad: CSV

Table LISTING 2. Equivalence in $B(t-1, t, m)$

Algorithm Equivalent(f, f', iter)

{ // f, f' given elements of B(t-1, t, m)

// satisfying $\widehat{J}(f \prime)=\widehat{J}(f)$

// return Equiv or NotEquiv or Undefined

s ← random element of AGL(m)

f ← f ° s

$\text {basis } \leftarrow\left(b_1, \ldots, b_n\right) \text { a basis of } \mathbb{F}_2^m$

$\text {flag } \leftarrow \text { NotEquiv }$

// determine A* in GL(m)

:A*(0) ← 0

Search(1, basis)

return flag

}

| Show Table

DownLoad: CSV

Table LISTING 3. Search

Algorithm Search(i, basis)

{ // $basis\text{ }=\left( {{b}_{1}},\ldots ,{{b}_{n}} \right)\ \ \ \text{ }a\text{ }basis\text{ }of\text{ }\mathbb{F}_{2}^{m}$

// i index of basis elements in {1, 2, ..., m}

if (i > m)

// A* in GL(m) is fully constructed

// check the existence of a in $\mathbb{F}_2^m$

if CandidateChecking(A, f, f')

flag ← Equiv

return

iter ← iter - 1

if (iter < 0)

flag ← Undefined

return

else

// $\forall x \in\left\langle b_1, \ldots, b_{i-1}\right\rangle, \widehat{F}\left(f^{\prime}\right) \circ A^*(x)=\widehat{F}(f)(x)$

// continue construction of A*

for each y in $\mathbb{F}_2^m$

if Admissible(y, i) and (flag= NotEquiv)

Search(i+1, basis)

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	É. Brier and P. Langevin, Classification of Boolean cubic forms of 9 variables, ITW 2003, (2003), 179-182.
[2]	R. Dougherty, R. D. Mauldin and M. Tiefenbruck, The covering radius of the Reed-Muller code $RM(m-4,m)$ in $RM(m-3,m)$, IEEE Trans. Inform. Theory, 68 (2022), 560-571. doi: 10.1109/TIT.2021.3120754.
[3]	P. Langevin and G. Leander, Classification of Boolean quartic forms in eight variables, Boolean Functions in Cryptology and Information Security, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., IOS Press, Amsterdam, 18 (2005), 139-147.
[4]	J. Gao, H. Kan, Y. Li and Q. Wang, The covering radius of the third-order Reed-Muller codes $ RM(3,7)$ is 20, IEEE Trans. Inf. Theory, 69 (2023), 3663-3673. doi: 10.1109/TIT.2023.3242966.
[5]	V. Gillot and P. Langevin, Classification of some cosets of the Reed-Muller code, Communication in Cryptography, (2023). doi: 10.1007/s12095-023-00652-4.
[6]	V. Gillot and P. Langevin, Classification of $B(s, t, 7)$, (2022), http://langevin.univ-tln.fr/project/agl7/aglclass.html.
[7]	V. Gillot and P. Langevin, The covering radius of $RM(4, 8)$, (2022), http://langevin.univ-tln.fr/project/agl8/index.html.
[8]	V. S. Pless, W. C. Huffman and R. A. Brualdi, Handbook of Coding Theory. Vol. I, II, North-Holland, Amsterdam, 1998
[9]	Q. Wang, The covering radius of the Reed-Muller code $RM(2, 7)$ is 40, Discrete Math., 342 (2019), 111625, 7 pp. doi: 10.1016/j.disc.2019.111625.