On metric regularity of Reed-Muller codes
share
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  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  coincides with A, then the set A is called a metrically regular set. The problem of investigating metrically regular sets appeared when studying 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 metric regularity of the codes RM(0,m) and RM(k,m) for k ≥ m-3. Additionally, metric regularity of the RM(1,5) code is proved. Combined with previous results by Tokareva N. (2012) concerning duality of affine and bent functions, this proves metric regularity of most Reed-Muller codes with known covering radius. It is conjectured that all Reed-Muller codes are metrically regular.
READ FULL TEXT