On Reed-Muller subcodes, Grassmannian partitions and sum-free functions

Abstract

A function $F:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^m$ is called $k$th-order sum-free if the sum of its values over any $k$-dimensional affine subspace of ${\mathbb{F}}_2^n$ is non-zero. Carlet recently introduced this notion and constructed such functions for every $2\le k\le n$. We prove that, for $2\le k\le n-2$ and $m\le n$, the existence of a (non-degenerate) ${\mathbb{F}}_2^m$-valued $k$th-order sum-free function on ${\mathbb{F}}_2^n$ is equivalent to the existence of a codimension $m$ linear subcode of the Reed-Muller code $\mathrm{RM}(n-k,n)$ with minimum distance $3\cdot 2^{k-1}$. In particular, this yields a new family of Reed-Muller subcodes that avoid all minimum weight codewords of $\mathrm{RM}(n-k,n)$, and thus have minimum distance $3/2$ times that of $\mathrm{RM}(n-k,n)$. We also derive new necessary conditions for the existence of $k$th-order sum-free functions and present the first nontrivial lower bound on $m$. Finally, we observe that $k$th-order sum-free functions lead to a partition of the Grassmannian of all $k$-dimensional (linear) subspaces of ${\mathbb{F}}_2^n$ into constant-dimension subspace codes. Under the assumption that functions exist that are $k$th-order sum-free for multiple values of $k$, we obtain an improved partitioning result and a stronger upper bound on the chromatic number of the Grassmann graphs.