pith. sign in

arxiv: 2605.22958 · v1 · pith:AKEJ53RXnew · submitted 2026-05-21 · 💻 cs.IT · math.CO· math.IT

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

Philipp Heering , Christian Kaspers , Vladislav Taranchuk This is my paper

Pith reviewed 2026-05-25 05:27 UTC · model grok-4.3

classification 💻 cs.IT math.COmath.IT
keywords Reed-Muller codessum-free functionslinear subcodesminimum distanceGrassmannian partitionsconstant-dimension codesaffine subspacesbinary vector spaces
0
0 comments X

The pith

The existence of kth-order sum-free functions on F_2^n equals the existence of codimension-m subcodes of RM(n-k,n) with minimum distance 3·2^{k-1}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an equivalence between non-degenerate F_2^m-valued kth-order sum-free functions on F_2^n and codimension-m linear subcodes of the Reed-Muller code RM(n-k,n) that achieve minimum distance exactly 3·2^{k-1}. This holds for parameters satisfying 2 ≤ k ≤ n-2 and m ≤ n. The link immediately produces a new family of Reed-Muller subcodes that avoid every minimum-weight vector of the parent code, raising the distance by a factor of 3/2. It also supplies new necessary conditions on the functions together with the first nontrivial lower bound on the output dimension m. The same functions further induce partitions of the Grassmannian of k-dimensional subspaces into constant-dimension subspace codes, with stronger partitioning results when functions that are simultaneously sum-free for several orders of k are assumed to exist.

Core claim

We prove that, for 2≤k≤n-2 and m≤n, the existence of a (non-degenerate) F_2^m-valued kth-order sum-free function on F_2^n is equivalent to the existence of a codimension m linear subcode of RM(n-k,n) with minimum distance 3·2^{k-1}. In particular this yields a new family of Reed-Muller subcodes that avoid all minimum-weight codewords of RM(n-k,n) and thus have minimum distance 3/2 times that of RM(n-k,n). We also derive new necessary conditions for the existence of kth-order sum-free functions and present the first nontrivial lower bound on m. Finally we observe that kth-order sum-free functions lead to a partition of the Grassmannian of all k-dimensional subspaces of F_2^n into constant-

What carries the argument

The direct translation of the kth-order sum-free condition (nonzero sums over every k-dimensional affine subspace) into the minimum-distance condition on linear subcodes of RM(n-k,n) obtained by excluding all minimum-weight vectors of the parent code.

If this is right

  • New linear subcodes of RM(n-k,n) achieve minimum distance 3/2 times larger than the parent code by excluding its minimum-weight vectors.
  • New necessary conditions restrict the possible parameters of kth-order sum-free functions.
  • A first nontrivial lower bound on the output dimension m is obtained.
  • kth-order sum-free functions produce partitions of the Grassmannian into constant-dimension subspace codes.
  • Functions that are simultaneously kth-order sum-free for several k improve the Grassmannian partitions and tighten the upper bound on the chromatic number of the associated Grassmann graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equivalence opens a route to construct one object by searching for the other when known results exist on either the coding or the function side.
  • The induced Grassmannian partitions may connect to existing constant-dimension code tables or designs that seek large minimum-distance subspace collections.
  • Direct verification of the distance claim on small (n,k) instances would confirm whether the modeling of the sum-free condition fully captures the weight distribution.

Load-bearing premise

Avoiding all minimum-weight codewords of RM(n-k,n) produces exactly the stated distance 3·2^{k-1} without introducing other low-weight vectors.

What would settle it

For concrete small parameters such as n=5, k=2, m=2, exhibit either a non-degenerate sum-free function whose induced subcode has minimum distance different from 6, or a codimension-2 subcode of RM(3,5) with minimum distance 6 whose corresponding function fails to be sum-free.

read the original 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 \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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that for 2≤k≤n-2 and m≤n, the existence of a non-degenerate F_2^m-valued kth-order sum-free function on F_2^n is equivalent to the existence of a codimension-m linear subcode of RM(n-k,n) with minimum distance 3·2^{k-1}. It derives new necessary conditions for existence, a first nontrivial lower bound on m, and shows that such functions induce a partition of the Grassmannian of k-dimensional subspaces into constant-dimension subspace codes, with stronger results under the assumption of functions that are simultaneously sum-free for multiple k.

Significance. If the equivalence and distance claim hold, the work supplies a coding-theoretic characterization of these functions that yields new families of RM subcodes with distance improved by a factor of 3/2, plus new necessary conditions and Grassmannian applications. The multi-k partitioning result is a notable combinatorial consequence.

major comments (2)
  1. [Abstract] Abstract (sentence on new family of subcodes): the claim that any codimension-m subcode avoiding all minimum-weight codewords of RM(n-k,n) automatically satisfies d(C) ≥ 3·2^{k-1} is load-bearing for the '3/2 times' improvement. This holds only if RM(n-k,n) contains no nonzero codewords of weight w with 2^k < w < 3·2^{k-1}; otherwise a subcode can avoid the weight-2^k vectors (characteristic functions of k-flats) while still containing an intermediate-weight vector, so the asserted distance does not follow. The manuscript must supply an explicit weight-distribution argument or citation establishing the gap.
  2. [Main theorem] Equivalence statement (main theorem, likely §2 or §3): the reduction from the sum-free condition (nonzero sum over every k-flat) to the subcode containing none of the minimum-weight vectors of RM(n-k,n) must be verified for completeness; the abstract supplies no derivation steps, so any implicit handling of non-degeneracy, linearity of the subcode, or the precise translation of the sum condition needs to be checked against possible edge cases for m > 1.
minor comments (2)
  1. [Introduction] Define 'non-degenerate' for the F_2^m-valued functions at the first appearance rather than later.
  2. [Grassmannian section] The Grassmannian partition construction would benefit from an explicit small example (e.g., n=4, k=2) to illustrate the constant-dimension code property.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and valuable comments on our manuscript. We address each major comment below and indicate where revisions will be made.

read point-by-point responses

  1. Referee: [Abstract] Abstract (sentence on new family of subcodes): the claim that any codimension-m subcode avoiding all minimum-weight codewords of RM(n-k,n) automatically satisfies d(C) ≥ 3·2^{k-1} is load-bearing for the '3/2 times' improvement. This holds only if RM(n-k,n) contains no nonzero codewords of weight w with 2^k < w < 3·2^{k-1}; otherwise a subcode can avoid the weight-2^k vectors (characteristic functions of k-flats) while still containing an intermediate-weight vector, so the asserted distance does not follow. The manuscript must supply an explicit weight-distribution argument or citation establishing the gap.

    Authors: We acknowledge that the distance improvement claim relies on the absence of intermediate weights in RM(n-k,n). This is a standard property of Reed-Muller codes: nonzero codewords have weight at least the minimum distance 2^k, and the next possible weight is at least 3·2^{k-1}. This follows from the correspondence with Boolean functions of degree ≤ n-k and known results on their weight distributions (e.g., divisibility properties and the structure of affine subspaces). To make this explicit as requested, we will add a short paragraph with the relevant argument and a citation (such as to the weight distribution results in MacWilliams and Sloane or papers on RM codes) in the revised version. revision: yes

  2. Referee: [Main theorem] Equivalence statement (main theorem, likely §2 or §3): the reduction from the sum-free condition (nonzero sum over every k-flat) to the subcode containing none of the minimum-weight vectors of RM(n-k,n) must be verified for completeness; the abstract supplies no derivation steps, so any implicit handling of non-degeneracy, linearity of the subcode, or the precise translation of the sum condition needs to be checked against possible edge cases for m > 1.

    Authors: The equivalence is established in full detail in Section 3, including the precise mapping from the vector-valued sum-free condition to the subcode avoiding the characteristic vectors of k-flats, the role of non-degeneracy in ensuring codimension exactly m, and preservation of linearity. The argument treats the m components jointly while handling the F_2^m-valued sums. For m>1 we explicitly address the vector space structure to rule out edge cases. If additional explicit steps or expanded edge-case verification would improve clarity, we are happy to include them in the revision. revision: partial

Circularity Check

0 steps flagged

No significant circularity; equivalence is a direct proof between independent objects

full rationale

The paper states an equivalence between the existence of non-degenerate F_2^m-valued kth-order sum-free functions and the existence of codimension-m linear subcodes of RM(n-k,n) with minimum distance 3·2^{k-1}. This is framed as a theorem relating two separately defined combinatorial objects via their definitions (sum over k-flats nonzero vs. subcode avoiding all weight-2^k vectors). No parameter is fitted to data and then renamed a prediction. No load-bearing self-citation appears; the sole external reference is to Carlet's prior introduction of the sum-free notion. The distance claim follows from the minimum-distance definition once minimum-weight codewords are excluded, which is a standard coding-theoretic step rather than a reduction to the paper's own inputs. The Grassmannian partition observation is likewise a direct translation, not a renaming of a known result under new coordinates. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

No free parameters, invented entities, or ad-hoc axioms are visible in the abstract; the work rests on standard definitions of Reed-Muller codes, affine subspaces, and minimum distance.

axioms (2)
  • standard math Reed-Muller code RM(r,n) consists of all evaluations of degree-at-most-r polynomials over F_2^n
    This is the classical definition invoked when relating subcodes to the parent code's weight distribution.
  • domain assumption The sum of function values over a k-dimensional affine subspace corresponds to a linear functional on the dual code
    This translation between the sum-free condition and codeword weights is required for the equivalence but is standard in the field.

pith-pipeline@v0.9.0 · 5850 in / 1528 out tokens · 44699 ms · 2026-05-25T05:27:13.340345+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    E. Abbe, A. Shpilka, and M. Ye. Reed-Muller codes: theory and algorithms.IEEE Trans. Inform. Theory, 67(6, part 1):3251–3277, 2021.doi:10.1109/TIT.2020. 3004749. 22

    work page doi:10.1109/tit.2020 2021

  2. [2]

    R. D. Baker, J. van Lint, and R. Wilson. On the Preparata and Goethals codes.IEEE Trans. Inform. Theory, 29(3):342–345, 1983.doi:10.1109/TIT.1983.1056675

    work page doi:10.1109/tit.1983.1056675 1983

  3. [3]

    Baudrin, P

    J. Baudrin, P. Galissant, and L. Perrin. Exploring the set of APN functions. InBFA 2025 - 10th International Workshop on Boolean Functions and their Applications, Larnaca, Cyprus, September 2025. URL:https://hal.science/hal-05376704

    work page 2025

  4. [4]

    E. R. Berlekamp and N. J. A. Sloane. Restrictions on weight distribution of Reed-Muller codes.Inform. and Control, 14:442–456, 1969.doi:10.1016/S0019-9958(69)90150-8

    work page doi:10.1016/s0019-9958(69)90150-8 1969

  5. [5]

    Blondeau, A

    C. Blondeau, A. Canteaut, and P. Charpin. Differential properties ofx7→x 2t−1.IEEE Trans. Inform. Theory, 57(12):8127–8137, 2011.doi:10.1109/TIT.2011.2169129

    work page doi:10.1109/tit.2011.2169129 2011

  6. [6]

    Brinkmann and G

    M. Brinkmann and G. Leander. On the classification of APN functions up to dimension five.Des. Codes Cryptogr., 49(1-3):273–288, 2008.doi:10.1007/s10623-008-9194-6

    work page doi:10.1007/s10623-008-9194-6 2008

  7. [7]

    A. R. Calderbank and G. M. McGuire. Construction of a (64,2 37,12) code via Galois rings.Des. Codes Cryptogr., 10(2):157–165, 1997.doi:10.1023/A:1008240319733

    work page doi:10.1023/a:1008240319733 1997

  8. [8]

    Calderini

    M. Calderini. On the EA-classes of known APN functions in small dimensions.Cryptogr. Commun., 12(5):821–840, 2020.doi:10.1007/s12095-020-00427-1

    work page doi:10.1007/s12095-020-00427-1 2020

  9. [9]

    Carlet.Boolean functions for cryptography and coding theory

    C. Carlet.Boolean functions for cryptography and coding theory. Cambridge University Press, New York, 2020.doi:10.1017/9781108606806

    work page doi:10.1017/9781108606806 2020

  10. [10]

    C. Carlet. A notion on S-boxes for a partial resistance to some integral attacks. Cryptol- ogy ePrint Archive, Paper 2024/1693, 2025. URL:https://eprint.iacr.org/2024/ 1693

    work page 2024

  11. [11]

    C. Carlet. On the vector subspaces ofF 2n over which the multiplicative inverse function sums to zero.Des. Codes Cryptogr., 93(4):1237–1254, 2025.doi:10.1007/ s10623-024-01531-6

    work page 2025

  12. [12]

    C. Carlet. Two generalizations of almost perfect nonlinearity.J. Cryptology, 38(2):Paper No. 20, 32, 2025.doi:10.1007/s00145-025-09538-5

    work page doi:10.1007/s00145-025-09538-5 2025

  13. [13]

    Carlet, P

    C. Carlet, P. Charpin, and V. Zinoviev. Codes, bent functions and permutations suitable for DES-like cryptosystems.Des. Codes Cryptogr., 15(2):125–156, 1998.doi:10.1023/ A:1008344232130

    work page 1998

  14. [14]

    D’haeseleer, F

    J. D’haeseleer, F. Pavese, P. Santonastaso, and V. Taranchuk. Chromatic number of Grassmann graphs and MRD codes, 2026.arXiv:2602.10777

    work page arXiv 2026

  15. [15]

    D’haeseleer and V

    J. D’haeseleer and V. Taranchuk. On the chromatic number of Grassmann graphs, 2025. arXiv:2505.22055. 23

    work page arXiv 2025

  16. [16]

    Ebeling, X-d

    A. Ebeling, X-d. Hou, A. Rydell, and S. Zhao. On sum-free functions.Finite Fields Appl., 110:Paper No. 102744, 32, 2026.doi:10.1016/j.ffa.2025.102744

    work page doi:10.1016/j.ffa.2025.102744 2026

  17. [17]

    Edel and A

    Y. Edel and A. Pott. On the equivalence of nonlinear functions. InEnhancing Crypto- graphic Primitives with Techniques from Error Correcting Codes, volume 23 ofNATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., pages 87–103. IOS, Amsterdam, 2009. doi:10.3233/978-1-60750-002-5-87

    work page doi:10.3233/978-1-60750-002-5-87 2009

  18. [18]

    T. Etzion. Partialk-parallelisms in finite projective spaces.J. Combin. Des., 23(3):101– 114, 2015.doi:10.1002/jcd.21392

    work page doi:10.1002/jcd.21392 2015

  19. [19]

    Etzion and N

    T. Etzion and N. Silberstein. Error-correcting codes in projective spaces via rank- metric codes and Ferrers diagrams.IEEE Trans. Inform. Theory, 55(7):2909–2919, 2009.doi:10.1109/TIT.2009.2021376

    work page doi:10.1109/tit.2009.2021376 2009

  20. [20]

    Godsil and G

    C. Godsil and G. Royle.Algebraic Graph Theory, volume 207. 2001.doi:10.1007/ 978-1-4613-0163-9

    work page 2001

  21. [21]

    Heering and V

    P. Heering and V. Taranchuk. Line-parallelisms of PG(n,2) from Preparata-like codes, 2025.arXiv:2508.19901

    work page arXiv 2025

  22. [22]

    X-d. Hou. GL(m,2) acting onR(r, m)/R(r−1, m).Discrete Math., 149(1-3):99–122, 1996.doi:10.1016/0012-365X(94)00342-G

    work page doi:10.1016/0012-365x(94)00342-g 1996

  23. [23]

    X-d. Hou. Affinity of permutations ofF n 2.Discrete Appl. Math., 154(2):313–325, 2006. doi:10.1016/j.dam.2005.03.022

    work page doi:10.1016/j.dam.2005.03.022 2006

  24. [24]

    Hou and S

    X-d. Hou and S. Zhao. On a conjecture about the sum-freedom of the binary mul- tiplicative inverse function.Des. Codes Cryptogr., 94(4):Paper No. 86, 2026.doi: 10.1007/s10623-026-01819-9

    work page doi:10.1007/s10623-026-01819-9 2026

  25. [25]

    Hou and S

    X-d. Hou and S. Zhao. Two absolutely irreducible polynomials overF 2 and their appli- cations to a conjecture by Carlet.Finite Fields Appl., 109:Paper No. 102713, 17, 2026. doi:10.1016/j.ffa.2025.102713

    work page doi:10.1016/j.ffa.2025.102713 2026

  26. [26]

    M. V. Jamali, M. Fereydounian, H. Mahdavifar, and H. Hassani. Low-complexity de- coding of a class of Reed-Muller subcodes for low-capacity channels. InICC 2022 - IEEE International Conference on Communications, pages 123–128, 2022. URL: https://api.semanticscholar.org/CorpusID:246652576

    work page 2022

  27. [27]

    Kasami and N

    T. Kasami and N. Tokura. On the weight structure of Reed-Muller codes.IEEE Trans. Inform. Theory, IT-16:752–759, 1970.doi:10.1109/tit.1970.1054545

    work page doi:10.1109/tit.1970.1054545 1970

  28. [28]

    C. Kaspers. Nonvanishingk-flats of Boolean and vectorial functions, 2026.arXiv: 2603.28266. 24

    work page arXiv 2026

  29. [29]

    Koetter and F

    R. Koetter and F. R. Kschischang. Coding for errors and erasures in random network coding.IEEE Trans. Inform. Theory, 54(8):3579–3591, 2008.doi:10.1109/TIT.2008. 926449

    work page doi:10.1109/tit.2008 2008

  30. [30]

    Langevin and G

    P. Langevin and G. Leander. Classification of Boolean quartic forms in eight variables. InBoolean functions in cryptology and information security, volume 18 ofNATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., pages 139–147. IOS, Amsterdam, 2008.doi: 10.3233/978-1-58603-878-6-139

    work page doi:10.3233/978-1-58603-878-6-139 2008

  31. [31]

    Langevin, E

    P. Langevin, E. Saygi, and Z. Saygi. Classification of APN cubics in dimension 6 over GF(2), 2012. URL:https://langevin.univ-tln.fr/project/apn-6/apn-6.html

    work page 2012

  32. [32]

    F. J. MacWilliams and N. J. A. Sloane.The Theory of Error-Correcting Codes, volume 16 ofNorth-Holland Mathematical Library. North-Holland, Amsterdam, 1977. URL:https://www.sciencedirect.com/bookseries/ north-holland-mathematical-library/vol/16/suppl/C

    work page 1977

  33. [33]

    M. Meszka. The chromatic index of projective triple systems.J. Combin. Des., 21(11):531–540, 2013.doi:10.1002/jcd.21368

    work page doi:10.1002/jcd.21368 2013

  34. [34]

    D. E. Muller. Application of Boolean algebra to switching circuit design and to error detection.Trans. I.R.E. Prof. Group Electron. Comput., EC-3(3):6–12, 1954.doi: 10.1109/IREPGELC.1954.6499441

    work page doi:10.1109/irepgelc.1954.6499441 1954

  35. [35]

    K. Nyberg. Differentially uniform mappings for cryptography. InAdvances in Cryptology - EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings, volume 765 ofLecture Notes in Computer Science, pages 55–64, 1993.doi:10.1007/3-540-48285-7_6

    work page doi:10.1007/3-540-48285-7_6 1993

  36. [36]

    A. Pott. Almost perfect and planar functions.Des. Codes Cryptogr., 78(1):141–195, 2016.doi:10.1007/s10623-015-0151-x

    work page doi:10.1007/s10623-015-0151-x 2016

  37. [37]

    I. S. Reed. A class of multiple-error-correcting codes and the decoding scheme.Trans. IRE Prof. Group Inf. Theory, (PGIT-, PGIT-4):38–49, 1954.doi:10.1109/TIT.1954. 1057465

    work page doi:10.1109/tit.1954 1954

  38. [38]

    Salomon and O

    A. Salomon and O. Amrani. Augmented product codes and lattices: Reed-Muller codes and Barnes-Wall lattices.IEEE Trans. Inform. Theory, 51:3918 – 3930, 12 2005.doi: 10.1109/TIT.2005.856937

    work page doi:10.1109/tit.2005.856937 2005

  39. [39]

    Silberstein and T

    N. Silberstein and T. Etzion. Large constant dimension codes and lexicodes.Adv. Math. Commun., 5(2):177–189, 2011.doi:10.3934/amc.2011.5.177

    work page doi:10.3934/amc.2011.5.177 2011

  40. [40]

    Subcodes of second-order Reed-Muller codes via recursive subproducts, 2025.arXiv:2501.10700

    A P Vaideeswaran, Madireddi Sai Harish, and Lakshmi Prasad Natarajan. Subcodes of second-order Reed-Muller codes via recursive subproducts, 2025.arXiv:2501.10700. 25

    work page arXiv 2025

  41. [41]

    Van Wonterghem, J

    J. Van Wonterghem, J. J. Boutros, and M. Moeneclaey. On constructions of Reed- Muller subcodes.IEEE Commun. Lett., 22(2):220–223, 2018.doi:10.1109/LCOMM. 2017.2772247

    work page doi:10.1109/lcomm 2018

  42. [42]

    G. V. Zaitsev, V. A. Zinoviev, and N. V. Semakov. Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-error-correcting codes. InProceedings of the 2nd International Symposium on Information Theory, pages 257– 263, 1973. 26

    work page 1973