**On metric regularity of Reed-Muller codes**

*Alexey Oblaukhov*

**Abstract: **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 metric regularity of the codes $\mathcal{RM}(0,m)$ and $\mathcal{RM}(k,m)$ for $k \geqslant m-3$. Additionally, metric regularity of the $\mathcal{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.

**Category / Keywords: **foundations / metrically regular set; metric complement; covering radius; bent function; Reed-Muller code; deep hole

**Date: **received 23 Dec 2019

**Contact author: **oblaukhov at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20191223:153119 (All versions of this report)

**Short URL: **ia.cr/2019/1481

[ Cryptology ePrint archive ]