The Covering Radius of the Reed–Muller Code RM(m – 4, m) in RM(m – 3, m)

DOI10.1109/TIT.2021.3120754MaRDI QIDQ5030307zbMATH OpenOpenAlexFDO

Authors Randall Dougherty, R. Daniel Mauldin, Mark Tiefenbruck

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.13910

zbMATH Keywords

covering radiusdistance from Boolean polynomialReed-Muller code

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75) Boolean functions (94D10)

Abstract: We present methods for computing the distance from a Boolean polynomial on $m$ variables of degree $m-3$ (i.e., a member of the Reed-Muller code $RM(m-3,m)$) to the space of lower-degree polynomials ($RM(m-4,m)$). The methods give verifiable certificates for both the lower and upper bounds on this distance. By applying these methods to representative lists of polynomials, we show that the covering radius of $RM(4,8)$ in $RM(5,8)$ is 26 and the covering radius of $RM(5,9)$ in $RM(6,9)$ is between 28 and 32 inclusive, and we get improved lower bounds for higher~$m$. We also apply our methods to various polynomials in the literature, thereby improving the known bounds on the distance from 2-resilient polynomials to $RM(m-4,m)$.

Recommendations

• On the covering radius of the third order Reed-Muller code \(\mathrm{RM}(3, 7)\)
• On the covering radius of Reed-Muller codes
• Some results on the covering radii of Reed-Muller codes
• Some inequalities about the covering radius of Reed-Muller codes
• The covering radius of the Reed-Muller code \(\text{RM}(2, 7)\) is \(40\)
• Further results on the covering radii of the Reed-Muller codes
• On the Generalized Covering Radii of Reed-Muller Codes
• Covering radius of the Reed-Muller code \(R(1,7)\) -- a simpler proof
• The covering radius of the<tex>(2^{15}, 16)</tex>Reed-Muller code is at least 16276
• On the Covering Radius of First-Order Generalized Reed–Muller Codes

Cited in

(2)

• Classification of some cosets of the Reed-Muller code
• Some algebraic questions about the Reed-Muller code

This page was built for publication: The Covering Radius of the Reed–Muller Code RM(m – 4, m) in RM(m – 3, m)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5030307)