On Reed-Muller subcodes, Grassmannian partitions and sum-free functions
This work provides theoretical insights into sum-free functions and Reed-Muller codes, with implications for coding theory and graph theory, but is incremental in nature.
The authors establish an equivalence between kth-order sum-free functions and certain Reed-Muller subcodes, yielding subcodes with minimum distance 3/2 times that of RM(n-k,n). They also derive new necessary conditions and a first nontrivial lower bound on m, and show applications to Grassmannian partitions and chromatic numbers of Grassmann graphs.
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 \leq 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.