On Reed-Muller subcodes, Grassmannian partitions and sum-free functions
Philipp Heering, Christian Kaspers, Vladislav Taranchuk · 2026
Read On Reed-Muller subcodes, Grassmannian partitions and sum-free functions by Philipp Heering, Christian Kaspers, Vladislav Taranchuk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22958.txt.
Introduction
Heering, Kaspers, and Taranchuk link kth-order sum-free functions to Reed-Muller subcodes. A function is kth-order sum-free when its outputs over any k-dimensional affine subspace sum to a nonzero value. For k between 2 and n minus 2, they prove an equivalence. Such a function exists when a codimension m linear subcode of RM(n-k,n) exists. That subcode has minimum distance 3 times 2 to the k minus 1. This yields new subcodes avoiding all minimum-weight codewords. It gives a partition of the Grassmannian into codes.
Catalog record
| CREATOR | Philipp Heering, Christian Kaspers, Vladislav Taranchuk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60509 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22958
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Reed-Muller subcodes, Grassmannian partitions and sum-free functions Philipp Heering, Christian Kaspers, Vladislav Taranchuk Abstract 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\leq k\leq n . We prove that, for 2\leq k\leq n-2 , 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. Keywords: Reed-Muller code, subcode, k th-order sum-free function, almost perfect non-linear function, Grassmann graph, coloring MSC (2020): 94B05, 11T06, 05C15 1 Introduction The r th-order Reed-Muller code \RM(r,n) of length 2^{n} is the set of value vectors of all Boolean functions on n variables of algebraic degree at most r . It is well-known that the code \RM(r,n) has minimum distance 2^{n-r} and dimension \sum_{i=0}^{r}\binom{n}{i} . Since their introduction in 1954 by Muller [ 34 ] and Reed [ 37 ] , these linear codes have been intensively studied and have become one of the most important and best understood families of codes [ 32 ] . Despite their long history, they are still highly relevant; we refer to the survey [ 1 ] for an overview of recent developments. Identifying good subcodes of Reed-Muller codes can increase the available choices of code rate and can make Reed-Muller codes more attractive in practice [ 40 ] . This seems to be a difficult problem which has seen considerable attention over the years [ 9 ] . It has long been known that almost perfect non-linear (APN) functions produce (linear) subcodes of the extended Hamming code (which is the Reed-Muller code RM (n-2,n) ) with minimum distance 6 and dimension 2^{n}-2n-1 [ 9 ] . Dually, one can also obtain a subcode of RM (2,n) with minimum distance 3\cdot 2^{n-3} and dimension \binom{n}{2}+1 . When n is even, Preparata-like codes form a class of optimal (non-linear) subcodes of the extended Hamming code, whose size is equal to the size of a linear code with dimension 2^{n}-2n [ 2 , 42 ] . The “dual” of the Preparata code is the Kerdock code, which is a non-linear subcode of RM (2,n) and has size equal to that of a linear code with dimension \binom{n}{2}+2 . For a deeper background on these codes we refer the reader to [ 32 ] . In [ 26 , 41 ] , Reed-Muller subcodes are obtained by removing selected rows from the generator matrix of the Reed-Muller code. Moreover, \RM(1,n_{1})\otimes\RM(1,n_{2}) is a subcode of \RM(2,n_{1}+n_{2}) with minimum distance 2^{n_{1}+n_{2}-2} , and dimension (n_{1}+1)(n_{2}+1) [ 38 ] . Recursive subproduct codes have also been studied, see [ 40 ] . A function F\colon\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{m} is called k th-order sum-free if \sum_{x\in A}F(x)\neq 0 for any affine k -subspace A\subseteq\mathbb{F}_{2}^{n} . Recently, Carlet [ 12 , 13 ] introduced these functions as a generalization of APN functions. An APN function is a function F\colon\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n} , such that the equation F(x+a)+F(x)=b has at most 2 solutions for all non-zero a\in\mathbb{F}_{2}^{n} and all b\in\mathbb{F}_{2}^{n} . APN functions have been extensively studied due to their optimal resistance to differential attacks in cryptography [ 35 ] . It is well-known [ 6 , 25 ] that a function F is APN if and only if \sum_{x\in A}F(x)\neq 0 for all affine 2 -subspaces A\subseteq\mathbb{F}_{2}^{n} , so APN functions are second-order sum-free. Since their introduction, k th-order sum-free functions have been studied by a number of authors [ 11 , 12 , 13 , 16 , 22 , 23 , 28 ] , however, to the best of the authors’ knowledge, no connection to coding theory has been established yet. For more background on the properties of these functions and their connections to cryptography, we refer to [ 13 ] . In this paper, we establish a correspondence between subcodes of \RM(r,n) and (n-r) th-order sum-free functions which satisfy a natural non-degeneracy condition. This correspondence enables us to give explicit constructions of subcodes in \RM(r,n) of codimension n for each r and n satisfying 2\leq r\leq n-2 . For the range 2<r<n-2 , these codes appear to be new. The subcodes we construct have a minimum distance of 3\cdot 2^{n-r-1} , compared with the minimum distance 2^{n-r} of \RM(r,n) . Interestingly, the codimension of these subcodes is only n . Our construction is inspired by the subcodes of RM (n-2,n) arising from APN functions. Theorem 1.1 . Let r,m,n be positive integers satisfying 2\leq r\leq n-2 and m\leq n . Any codimension m (linear) subcode of the Reed-Muller code \RM(r,n) , which has minimum distance 3\cdot 2^{n-r-1} , gives rise to a non-degenerate (n-r) th-order sum-free (n,m) -function. Conversely, any non-degenerate (n-r) th-order sum-free (n,m) -function yields a codimension m (linear) subcode of \RM(r,n) , with minimum distance 3\cdot 2^{n-r-1} . Besides the new subcodes of \RM(r,n) , our work also leads to new results on the existence of k th-order sum-free functions. Up to now, only one infinite family of k th-order sum-free functions, introduced by Carlet [ 11 , 13 ] , is known. While more k th-order sum-free functions from \mathbb{F}_{2}^{n} to \mathbb{F}_{2}^{m} do exist when m=n , as was shown by the second author [ 28 ] , it is not clear if they exist for m<n . Therefore, Carlet [ 13 ] asked for each k : What is the smallest value of m such that a k th-order sum-free (n,m) -function exists? It is well known that for m<n , a function cannot be APN (second-order sum-free), unless n=2 as was shown by Nyberg [ 35 ] . Carlet [ 13 ] observed that a Boolean function cannot be k th-order sum-free for all 1\leq k\leq n-1 . For 1<m<n and k\geq 3 however, the question is completely open. In 3.5 we present the first nontrivial lower bound: m\geq\max\{n-k+2,k+2\} . Moreover, we show that for the only known infinite family of k th-order sum-free functions, we always have m=n . Finally, we obtain results related to partitioning the Grassmannian of all (linear) k -subspaces of \mathbb{F}_{2}^{n} into constant-dimension subspace codes, a topic which has seen much activity in recent years [ 14 , 15 , 19 , 18 , 21 , 29 , 39 ] . Our results are best stated in terms of the chromatic number of the Grassmann graphs J_{2}(n,k) whose