On metric regularity of Reed-Muller codes

• Published in: arXiv.org 2020-04
• Main Author: Oblaukhov, Alexey
• Format: Article
• Language: English
• Subjects: Binary codes; Boolean; Boolean algebra; Cryptography; Reed-Muller codes; Regularity
• ISSN: 2331-8422

In this work we study metric properties of the well-known family of binary Reed-Muller codes. Let \(A\) be an arbitrary subset of the Boolean cube, and \(\widehat{A}\) be the metric complement of \(A\) -- the set of all vectors of the Boolean cube at the maximal possible distance from \(A\). If the metric complement of \(\widehat{A}\) coincides with \(A\), then the set \(A\) is called a {\it metrically regular set}. The problem of investigating metrically regular sets appeared when studying {\it bent functions}, which have important applications in cryptography and coding theory and are also one of the earliest examples of a metrically regular set. In this work we describe metric complements and establish the metric regularity of the codes \(\mathcal{RM}(0,m)\) and \(\mathcal{RM}(k,m)\) for \(k \geqslant m-3\). Additionally, the metric regularity of the codes \(\mathcal{RM}(1,5)\) and \(\mathcal{RM}(2,6)\) is proved. Combined with previous results by Tokareva N. (2012) concerning duality of affine and bent functions, this establishes the metric regularity of most Reed-Muller codes with known covering radius. It is conjectured that all Reed-Muller codes are metrically regular.