🔢 mathematics

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

This paper establishes an equivalence between the existence of $k$ th-order sum-free functions and specific Reed-Muller subcodes, thereby deriving new necessary conditions and lower bounds for such functions while demonstrating their utility in partitioning Grassmannians and improving bounds on Grassmann graph chromatic numbers.

Original authors: Philipp Heering, Christian Kaspers, Vladislav Taranchuk

Published 2026-05-25

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Philipp Heering, Christian Kaspers, Vladislav Taranchuk

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a massive library of books, but instead of words, the books are made of patterns of zeros and ones (binary code). This library is called a Reed-Muller code. It's a very organized system used in digital communication to ensure messages get through without errors.

However, sometimes you want to create a special section within this library. You want a smaller collection of books (a subcode) that avoids certain "bad" patterns. Specifically, you want to avoid the simplest, most common patterns (called "minimum weight codewords") because they are too easy to confuse with noise.

This paper is about finding a magical key to unlock these special, cleaner sections of the library. Here is how the authors did it, explained through simple analogies:

1. The "Sum-Free" Magic Trick

The authors focus on a special type of mathematical function they call a "kth-order sum-free function."

The Analogy: Imagine you have a group of friends (points in a space). You ask them to stand in a specific shape, like a flat table (a "k-dimensional flat").
The Rule: If you take everyone standing at that table and add up their "scores" (the values the function gives them), the total score must never be zero.
Why it matters: If the total is never zero, no matter which table you pick, the function is "sum-free." It's like a rule that says, "No matter how you group these people, they can never cancel each other out completely."

2. The Big Discovery: Two Sides of the Same Coin

The main breakthrough of this paper is proving that these "sum-free" functions and the "clean" library sections are actually the same thing, just looking at it from different angles.

The Connection: The authors proved that if you can find a function that never sums to zero on any table of a certain size, you automatically have a blueprint for building a special subcode of the Reed-Muller library.
The Result: This new subcode is "cleaner" than the original. The original library had a minimum distance (a measure of how different two books must be to be distinct) of $2^{n-r}$ . The new subcode has a minimum distance of 1.5 times larger ( $3 \cdot 2^{n-r-1}$ ).
Simple Takeaway: They found a way to build a stronger, more distinct version of the code by using these special math functions.

3. The "Grassmann" Party Game

The paper also connects this to a game involving Grassmann graphs.

The Analogy: Imagine a party where every guest is a "table" (a subspace). Two guests are considered "neighbors" if their tables overlap significantly (they share a big chunk of space).
The Goal: You want to give everyone a name tag (a color) so that no two neighbors have the same color. This is called "coloring the graph."
The Solution: The authors showed that if you have a "sum-free" function, you can use it to hand out name tags perfectly. If two tables overlap too much, the function guarantees they will get different name tags.
The Bonus: If you have a function that works for multiple sizes of tables at once (called "multiorder sum-free"), you can create even better, more efficient colorings for these party games.

4. What They Found (and What They Didn't)

New Codes: They successfully built a whole new family of these "clean" subcodes.
Limits: They proved that you can't just use any small number of name tags (colors) to solve the party game. There is a minimum number of tags required, and they calculated a new, stricter lower bound for this number.
The "Gold" Standard: They checked the only known infinite family of these special functions (created by a mathematician named Carlet) and confirmed they are "non-degenerate" (meaning they are genuine, high-quality functions and not just tricks).
The Mystery: They tried to find functions that work for multiple table sizes simultaneously (multiorder) in small dimensions. They found a few examples (like in a 5-dimensional space), but for larger spaces, it's still a mystery. They even used computers to check thousands of known functions and found that most of them don't work for these stricter rules.

Summary

In short, this paper is a bridge between two worlds: coding theory (making sure data is sent correctly) and geometry (how shapes overlap in space).

The authors discovered that a specific mathematical "magic trick" (the sum-free function) is the secret ingredient to building stronger error-correcting codes. They also showed that these same tricks can solve complex coloring puzzles on geometric shapes. While they solved the main puzzle of how to build these codes, they left a few doors open for future explorers to find even more magical functions that work in multiple ways at once.

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

Problem Statement
The paper addresses three interconnected problems in coding theory and finite geometry:

Reed-Muller Subcodes: The construction of linear subcodes of Reed-Muller codes $RM(r, n)$ that avoid all minimum weight codewords, thereby achieving a minimum distance strictly greater than that of the parent code.
Existence of Sum-Free Functions: Determining the existence conditions and necessary bounds for $k$ -th order sum-free functions $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ . A function is $k$ -th order sum-free if the sum of its values over any $k$ -dimensional affine subspace is non-zero. While Carlet recently introduced this concept and provided an infinite family of such functions (where $m=n$ ), the existence of such functions for $m < n$ and for specific orders $k \ge 3$ remains largely open.
Grassmannian Partitioning: The problem of partitioning the set of all $k$ -dimensional linear subspaces of $\mathbb{F}_2^n$ (the Grassmannian) into constant-dimension subspace codes. This is equivalent to determining the chromatic number $\chi(J_2(n, k))$ of the Grassmann graph, where vertices are $k$ -spaces and edges connect spaces intersecting in dimension $k-1$ .

Methodology
The authors establish a rigorous correspondence between coding theory and the properties of sum-free functions.

Correspondence Construction: The paper proves that a non-degenerate $(n-r)$ -th order sum-free function $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ is equivalent to the existence of a linear subcode of $RM(r, n)$ with codimension $m$ and minimum distance $3 \cdot 2^{n-r-1}$ . This is achieved by constructing a parity-check matrix for the subcode using the evaluation vectors of the function $F$ .
Algebraic Analysis: The authors utilize the algebraic degree of Boolean functions, the properties of higher-order derivatives, and the structure of Reed-Muller codes (specifically the characterization of minimum and second-minimum weight codewords via flats and their symmetric differences) to derive necessary conditions for the existence of sum-free functions.
Graph Coloring via Functions: The paper utilizes the "witness function" $\omega_F(A) = \sum_{x \in A} F(x)$ to define colorings on Grassmann graphs. By ensuring that adjacent vertices (subspaces intersecting in dimension $k-1$ ) map to distinct non-zero values, the authors construct valid colorings.
Computational Verification: For small dimensions ( $n=5, 6, 7$ ), the authors perform computational searches to verify the existence of multiorder sum-free functions (functions that are sum-free for multiple orders $k$ ) among known Almost Perfect Non-linear (APN) functions.

Key Contributions and Results

Equivalence Theorem (Theorem 1.1):
The paper establishes a bijective correspondence: A non-degenerate $(n-r)$ -th order sum-free $(n, m)$ -function exists if and only if there exists a codimension $m$ linear subcode of $RM(r, n)$ with minimum distance $3 \cdot 2^{n-r-1}$ .
- Significance: This yields a new family of Reed-Muller subcodes that avoid all minimum weight codewords of $RM(r, n)$. These subcodes have a minimum distance $1.5$ times that of the original code, with a codimension of only $n$ . For the range $2 < r < n-2$ , these codes appear to be new.
New Lower Bounds on $m$ (Theorem 3.5):
The authors derive the first non-trivial lower bound on the output dimension $m$ for the existence of $k$ -th order sum-free functions. For $2 \le k \le n-2$ , if an $(n, m)$ -function is $k$ -th order sum-free, then:
$m \ge \max\{n - k + 2, k + 2\}$
This result implies that for $m < n$ , such functions cannot exist for certain ranges of $k$ , refining previous knowledge which was limited to the case $m=n$ .
Non-Degeneracy of Known Families (Theorem 3.6):
The paper proves that the infinite family of power functions $F_{k,j}(x) = x^{(2^{jk}-1)/(2^j-1)}$ introduced by Carlet are non-degenerate for $k < n$ . This confirms that these functions genuinely require the full output space dimension $n$ and cannot be reduced to lower-dimensional functions while maintaining the sum-free property.
Improved Grassmann Graph Colorings (Theorem 5.1):
The authors generalize previous coloring results. They show that if there exists a function $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ of algebraic degree $k$ that is both $(k-1)$ -th and $k$ -th order sum-free, then the Grassmann graph $J_2(n+1, k)$ admits a valid coloring with $\binom{m}{1}_2 = 2^m - 1$ colors.
- Application: Using the inverse function in odd dimensions (which is $\{1, 2, n-2, n-1\}$ -order sum-free), the authors derive a coloring for $J_2(n+1, n-1)$ .
- Specific Result: For $n=5$ , the existence of cubic $\{2, 3\}$ -order sum-free functions ( $x^7$ and $x^{21}$ ) leads to the bound $\chi(J_2(6, 3)) \le 31$ , improving upon previously known upper bounds.
Computational Findings on Multiorder Functions:
The paper reports that for $n=6$ , no known APN functions are third- or fourth-order sum-free. For $n=7$ , only functions equivalent to Gold APN functions ( $x^{15}, x^{77}, x^{85}$ ) were found to be fourth-order sum-free. This suggests that multiorder sum-free functions are rare and difficult to construct.

Significance and Claims
The paper claims to be the first to establish a direct link between $k$ -th order sum-free functions and the construction of Reed-Muller subcodes with enhanced minimum distances. This connection provides a new algebraic tool for generating subcodes that avoid minimum weight codewords.

Furthermore, the work provides the first non-trivial necessary conditions for the existence of sum-free functions with $m < n$ , addressing a specific open question posed by Carlet. By linking these functions to the chromatic number of Grassmann graphs, the paper offers a method to improve upper bounds on $\chi(J_2(n, k))$ , particularly for cases where $k > 2$ .

The authors remain modest regarding the construction of new sum-free functions, noting that constructing genuinely new examples beyond the known power functions remains difficult. They frame the existence of multiorder sum-free functions for $k \ge 3$ as a significant open problem with implications for both coding theory (non-linear codes) and graph theory.

1. The "Sum-Free" Magic Trick

2. The Big Discovery: Two Sides of the Same Coin

3. The "Grassmann" Party Game

4. What They Found (and What They Didn't)

Summary

More like this