pith. sign in

arxiv: 2606.02819 · v1 · pith:QWOAZRRCnew · submitted 2026-06-01 · 💻 cs.IT · math.IT

Reed-Muller type codes over a combinatorial simplex: an algebraic description

Hiram H. L\'opez , Rodrigo San-Jos\'e , Nart Shalqini This is my paper

Pith reviewed 2026-06-28 12:30 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords combinatorial simplexCAP codesReed-Muller codesGröbner basisvanishing idealgeneralized Hamming weightspermutation groupfinite fields
0
0 comments X

The pith

The vanishing ideal of a combinatorial simplex has a universal Gröbner basis that determines the generalized Hamming weights of CAP codes.

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

This paper uses commutative algebra to study combinatorial simplices and the CAP codes defined over them as Reed-Muller type codes. It provides a universal Gröbner basis for the vanishing ideal of the simplex. The generalized Hamming weights of the CAP codes are then expressed using the footprint of this ideal, including a closed formula for the minimum distance. The approach also identifies generators for the dual code and determines the permutation group in certain cases. These results offer explicit algebraic descriptions for these high-rate codes as alternatives to Reed-Muller codes.

Core claim

We give a universal Gröbner basis for the vanishing ideal of a combinatorial simplex. We describe the generalized Hamming weights of a CAP code in terms of the footprint of the vanishing ideal. For the minimum distance case, we proved a closed formula. We give a set of polynomials whose evaluations on the combinatorial simplex generate the dual of the CAP code. We describe the affine permutations that leave invariant a combinatorial simplex and use this information to prove that, in some cases, the permutation group of a CAP code is a symmetric group.

What carries the argument

The universal Gröbner basis of the vanishing ideal of the combinatorial simplex, whose footprint determines the generalized Hamming weights of the associated CAP code.

If this is right

  • The footprint of the Gröbner basis gives the generalized Hamming weights of CAP codes.
  • A closed formula exists for the minimum distance of these codes.
  • The dual of the CAP code is generated by the evaluation of specific polynomials on the simplex.
  • In some cases the automorphism group of the CAP code is the full symmetric group.

Where Pith is reading between the lines

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

  • The same Gröbner basis methods could be tested on other point sets used to define algebraic codes to see if similar weight formulas emerge.
  • The cases where the permutation group is the full symmetric group may imply that those CAP codes are equivalent under any coordinate relabeling.
  • The explicit ideal generators might support new syndrome-based decoding procedures that operate directly in the polynomial ring.

Load-bearing premise

The combinatorial simplex is the common zero set of certain polynomials over the finite field, allowing its vanishing ideal to be analyzed with Gröbner basis techniques.

What would settle it

Direct enumeration of codewords in a small CAP code to compute its generalized Hamming weights and comparison against the values obtained from the footprint of the claimed universal Gröbner basis.

Figures

Figures reproduced from arXiv: 2606.02819 by Hiram H. L\'opez, Nart Shalqini, Rodrigo San-Jos\'e.

Figure 1
Figure 1. Figure 1: Set B(1, 3), a 1-dimensional simplex of side length 3. We also have that B(2, 3) = {(b0, b0),(b0, b1),(b0, b2),(b1, b0),(b1, b1),(b2, b0)}. If we define the order b0 < b1 < b2, then B(2, 3) can be seen as a triangle in F 2 q ; see [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Set B(2, 3), a 2-dimensional simplex of side length 3 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 2
Figure 2. Figure 2: The CAP code CAP(B, 2, 1) is obtained by evaluating all the bivariate polynomials up to degree one on the points that appear in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The footprint of JB(m) on the monomial grid [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Regions considered in the proof of Theorem 5.5. 6. Permutation group We continue with the same notation from previous sections. In particular, B = {b0, b1, . . . , bℓ−1} is an ordered subset of Fq, B(m) denotes the combinatorial simplex, and CAP(B, m, ν) is the CAP code of degree ν. In this section, we focus on the permutation group of CAP(B, m, ν). We prove that when ν < ℓ/2, its permutation group is give… view at source ↗
read the original abstract

Given an ordered set $B$ of a finite field, a combinatorial simplex over $B$ is defined as the set of vectors such that the positions of the entries, with respect to $B$, sum up to a fixed integer. CAP codes are Reed-Muller type codes defined over a combinatorial simplex. They were recently introduced by Kopparty et al. as a high-rate alternative to classical Reed-Muller codes, capable of achieving arbitrarily high rates close to one for any fixed minimum distance. In this paper, we use tools from commutative algebra to analyze a combinatorial simplex and its associated CAP code. We give a universal Gr\"obner basis for the vanishing ideal of a combinatorial simplex. We describe the generalized Hamming weights of a CAP code in terms of the footprint of the vanishing ideal. For the minimum distance case, we proved a closed formula. We give a set of polynomials whose evaluations on the combinatorial simplex generate the dual of the CAP code. We describe the affine permutations that leave invariant a combinatorial simplex and use this information to prove that, in some cases, the permutation group of a CAP code is a symmetric group.

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

0 major / 3 minor

Summary. The manuscript analyzes combinatorial simplices and associated CAP codes (Reed-Muller type codes over these simplices) via commutative algebra. It claims a universal Gröbner basis for the vanishing ideal of the simplex, a description of the generalized Hamming weights of a CAP code via the footprint of the vanishing ideal, a closed formula for the minimum distance, a set of polynomials whose evaluations generate the dual code, and results on affine permutations preserving the simplex that imply the permutation group is the symmetric group in some cases.

Significance. If the derivations hold, the work supplies explicit algebraic tools (universal Gröbner basis, footprint description, closed-form distance) for a recently introduced family of high-rate codes. These are load-bearing strengths for explicit computation and duality results in algebraic coding theory, extending standard Gröbner and footprint techniques to the new combinatorial object without apparent hidden assumptions on field characteristic or ordering.

minor comments (3)
  1. [Abstract] Abstract: the sentence 'For the minimum distance case, we proved a closed formula' does not reference the theorem or section number; adding a parenthetical pointer (e.g., 'Theorem 4.2') would improve readability without altering content.
  2. §1 (or wherever the combinatorial simplex is first defined): the definition via positions summing to a fixed integer w.r.t. ordered set B would benefit from a small explicit example (e.g., |B|=3, sum=2) to illustrate the point set before the algebraic constructions begin.
  3. Notation: the monomial order used for the universal Gröbner basis is not named in the abstract or early sections; state it explicitly (e.g., 'graded reverse lexicographic order with respect to the ordering of B') at first use.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our manuscript on algebraic descriptions of CAP codes over combinatorial simplices. The recommendation for minor revision is noted. No specific major comments were listed in the report, so we address the overall evaluation below and confirm our willingness to make any minor adjustments required by the editor.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained algebraic analysis

full rationale

The paper defines the combinatorial simplex directly from the ordered set B and fixed integer sum condition, then applies standard commutative algebra (universal Gröbner bases for vanishing ideals, footprint bound for generalized Hamming weights) to derive the stated results. CAP codes are introduced via external citation to Kopparty et al., not self-citation. The closed-form minimum distance and dual generators follow from explicit polynomial evaluations and monomial orders on the defined point set; no step reduces a claimed prediction or uniqueness result to a fitted parameter or prior self-result by construction. The central claims are verifiable once the explicit basis and order are written down, with no load-bearing self-citation chain or ansatz smuggling.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract introduces the combinatorial simplex and CAP codes as definitions rather than derived objects; no free parameters, additional axioms, or invented entities with independent evidence are stated.

axioms (1)
  • domain assumption Standard properties of finite fields and ordered sets B
    Invoked in the definition of the combinatorial simplex.

pith-pipeline@v0.9.1-grok · 5736 in / 1138 out tokens · 31493 ms · 2026-06-28T12:30:11.891422+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

46 extracted references · 2 canonical work pages

  1. [1]

    T. Ball, E. Camps, H. Chimal-Dzul, D. Jaramillo-Velez, H. H. L’opez, N. S. Nichols, M. Perkins, I. Soprunov, G. Vera-Mart’inez, and G. R. Whieldon. Coding theory package for macaulay2.ArXiv, abs/2007.06795, 2020

    work page arXiv 2007

  2. [2]

    Beckwith, A

    L. Beckwith, A. Esser, E. Persichetti, P. Santini, and F. Zweydinger. LESS is even more: Optimizing digital signatures from code equivalence. Cryptology ePrint Archive, Paper 2025/1424, 2025. 21

    2025

  3. [3]

    Beelen and M

    P. Beelen and M. Datta. Generalized Hamming weights of affine Cartesian codes.Finite Fields Appl., 51:130– 145, 2018

    2018

  4. [4]

    Biasse, G

    J.-F. Biasse, G. Micheli, E. Persichetti, and P. Santini. Less is more: Code-based signatures without syn- dromes. InProgress in Cryptology - AFRICACRYPT 2020: 12th International Conference on Cryptology in Africa, Cairo, Egypt, July 20 – 22, 2020, Proceedings, page 45–65, Berlin, Heidelberg, 2020. Springer-Verlag

    2020

  5. [5]

    Bioglio, I

    V. Bioglio, I. Land, and C. Pillet. Group properties of polar codes for automorphism ensemble decoding. IEEE Transactions on Information Theory, 69(6):3731–3747, 2023

    2023

  6. [6]

    Buchberger

    B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Dissertation an dem Math. Inst. der Universit¨ at von Innsbruck, 1965

    1965

  7. [7]

    Camps-Moreno, I

    E. Camps-Moreno, I. Garc´ ıa-Marco, H. H. L´ opez, I. M´ arquez-Corbella, E. Mart´ ınez-Moro, and E. Sarmiento. On the generalized Hamming weights of hyperbolic codes.Journal of Algebra and Its Applications, 23(07):2550062, 2024

    2024

  8. [8]

    Camps-Moreno, H

    E. Camps-Moreno, H. H. L´ opez, G. L. Matthews, and R. San-Jos´ e. The weight hierarchy of decreasing norm-trace codes.Des. Codes Cryptogr., 93(7):2873–2894, 2025

    2025

  9. [9]

    Carvalho, H

    C. Carvalho, H. L´ opez, and R. San-Jos´ e. Cartesian square-free codes.ArXiv 2511.08304, 2025

    work page arXiv 2025

  10. [10]

    Carvalho, V

    C. Carvalho, V. G. L. Neumann, and H. H. L´ opez. Projective nested cartesian codes.Bull. Braz. Math. Soc. (N.S.), 48(2):283–302, 2017

    2017

  11. [11]

    H. Chen, R. Cramer, S. Goldwasser, R. De Haan, and V. Vaikuntanathan. Secure computation from random error correcting codes. InAnnual International Conference on the Theory and Applications of Cryptographic Techniques, pages 291–310. Springer, 2007

    2007

  12. [12]

    S. M. Cooper, A. Seceleanu, c. O. Toh˘ aneanu, M. V. Pinto, and R. H. Villarreal. Generalized minimum distance functions and algebraic invariants of Geramita ideals.Adv. in Appl. Math., 112:101940, 34, 2020

    2020

  13. [13]

    D. A. Cox, J. Little, and D. O’Shea.Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015. An introduction to computational algebraic geometry and commutative algebra

    2015

  14. [14]

    G. L. Feng and T. R. N. Rao. Decoding algebraic-geometric codes up to the designed minimum distance. 39(1):37–45, 1993

    1993

  15. [15]

    S. R. Ghorpade. A note on Nullstellensatz over finite fields.Contemp. Math., 738:23–32, 2019

    2019

  16. [16]

    Gonz´ alez-Sarabia, H

    M. Gonz´ alez-Sarabia, H. Mu˜ noz George, J. A. Ordaz, E. S´ aenz-de Cabez´ on, and R. H. Villarreal. Indicator functions, v-numbers and Gorenstein rings in the theory of projective Reed-Muller-type codes.Des. Codes Cryptogr., 92(11):3317–3353, 2024

    2024

  17. [17]

    Gopalan, V

    P. Gopalan, V. Guruswami, and P. Raghavendra. List decoding tensor products and interleaved codes.SIAM J. Comput., 40(5):1432–1462, 2011

    2011

  18. [18]

    Grassl and M

    M. Grassl and M. Roetteler. Leveraging automorphisms of quantum codes for fault-tolerant quantum com- putation. In2013 IEEE International Symposium on Information Theory, pages 534–538, 2013

    2013

  19. [19]

    D. R. Grayson and M. E. Stillman. Macaulay2, a software system for research in algebraic geometry. Available athttp://www.math.uiuc.edu/Macaulay2/

  20. [20]

    Guruswami

    V. Guruswami. List decoding from erasures: bounds and code constructions.IEEE Trans. Inform. Theory, 49(11):2826–2833, 2003

    2003

  21. [21]

    M. Hamada. Concatenated quantum codes constructible in polynomial time: efficient decoding and error correction.IEEE Trans. Inform. Theory, 54(12):5689–5704, 2008

    2008

  22. [22]

    Heijnen and R

    P. Heijnen and R. Pellikaan. Generalized Hamming weights ofq-ary Reed-Muller codes.IEEE Trans. Inform. Theory, 44(1):181–196, 1998

    1998

  23. [23]

    W. C. Huffman and V. Pless.Fundamentals of Error-Correcting Codes. Cambridge University Press, 2003

    2003

  24. [24]

    Jaramillo, M

    D. Jaramillo, M. Vaz Pinto, and R. H. Villarreal. Evaluation codes and their basic parameters.Des. Codes Cryptogr., 89(2):269–300, 2021

    2021

  25. [25]

    Johannsen, C

    L. Johannsen, C. Kestel, M. Geiselhart, T. Vogt, S. T. Brink, and N. Wehn. Successive cancellation auto- morphism list decoding of polar codes. In2023 12th International Symposium on Topics in Coding (ISTC), pages 1–5, 2023

    2023

  26. [26]

    Kamenev, Y

    M. Kamenev, Y. Kameneva, O. Kurmaev, and A. Maevskiy. Permutation decoding of polar codes. In2019 XVI International Symposium ”Problems of Redundancy in Information and Control Systems” (REDUN- DANCY), pages 1–6, 2019

    2019

  27. [27]

    Kasami, S

    T. Kasami, S. Lin, and W. W. Peterson. New generalizations of the Reed-Muller codes. I. Primitive codes. IEEE Trans. Inform. Theory, IT-14:189–199, 1968. 22

    1968

  28. [28]

    Ketkar, A

    A. Ketkar, A. Klappenecker, S. Kumar, and P. K. Sarvepalli. Nonbinary stabilizer codes over finite fields. IEEE Trans. Inform. Theory, 52(11):4892–4914, 2006

    2006

  29. [29]

    Kopparty, M

    S. Kopparty, M. Kumar, and H. Sha. High rate multivariate polynomial evaluation codes. InSTOC’25— Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 810–821. ACM, New York, [2025]©2025

    2025

  30. [30]

    Kudekar, S

    S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. S ¸a¸ so˘ glu, and R. Urbanke. Reed-Muller codes achieve capacity on erasure channels. InProceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 658–669, New York, NY, USA, 2016. Association for Computing Machinery

    2016

  31. [31]

    Kudekar, S

    S. Kudekar, S. Kumar, M. Mondelli, H. D. Pfister, E. S ¸a¸ soˇ glu, and R. L. Urbanke. Reed–Muller codes achieve capacity on erasure channels.IEEE Transactions on Information Theory, 63(7):4298–4316, 2017

    2017

  32. [32]

    Kurihara, T

    J. Kurihara, T. Uyematsu, and R. Matsumoto. Secret sharing schemes based on linear codes can be pre- cisely characterized by the relative generalized hamming weight.IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E95.A(11):2067–2075, 2012

    2067

  33. [33]

    H. H. L´ opez, C. Renter´ ıa-M´ arquez, and R. H. Villarreal. Affine cartesian codes.Des. Codes Cryptogr., 71(1):5– 19, Apr. 2014

    2014

  34. [34]

    H. H. L´ opez, I. Soprunov, and R. H. Villarreal. The dual of an evaluation code.Des. Codes Cryptogr., 89(7):1367–1403, July 2021

    2021

  35. [35]

    Y. Luo, C. Mitrpant, A. J. H. Vinck, and K. Chen. Some new characters on the wire-tap channel of type II. IEEE Trans. Inform. Theory, 51(3):1222–1229, 2005

    2005

  36. [36]

    H. H. L´ opez, F. Manganiello, and G. L. Matthews. Affine cartesian codes with complementary duals.Finite Fields and Their Applications, 57:13–28, 2019

    2019

  37. [37]

    Munuera and D

    C. Munuera and D. Ramirez. The second and third generalized hamming weights of hermitian codes.IEEE Transactions on Information Theory, 45(2):709–712, 1999

    1999

  38. [38]

    Patanker and S

    N. Patanker and S. K. Singh. Generalized Hamming weights of toric codes over hypersimplices and squarefree affine evaluation codes.Adv. Math. Commun., 17(3):626–643, 2023

    2023

  39. [39]

    San-Jos´ e

    R. San-Jos´ e. About the generalized Hamming weights of matrix-product codes.Comput. Appl. Math., 44(4):Paper No. 186, 2025

    2025

  40. [40]

    San-Jos´ e

    R. San-Jos´ e. An algorithm for computing generalized Hamming weights and the Sage packageGHWs.ACM Trans. Math. Software, 51(4):Art. 26, 20, 2025

    2025

  41. [41]

    San-Jos´ e

    R. San-Jos´ e. GHWs: A Sage package for computing the generalized Hamming weights of a linear code. GitHub repository. Available online:https://github.com/RodrigoSanJose/GHWs, 2025

    2025

  42. [42]

    A. B. Sørensen. Projective Reed-Muller codes.IEEE Trans. Inform. Theory, 37(6):1567–1576, 1991

    1991

  43. [43]

    https://www.sagemath.org

    The Sage Developers.SageMath, the Sage Mathematics Software System (Version 10.9), 2026. https://www.sagemath.org

    2026

  44. [44]

    A. Vardy. The intractability of computing the minimum distance of a code.IEEE Trans. Inform. Theory, 43(6):1757–1766, 1997

    1997

  45. [45]

    R. H. Villarreal.Monomial algebras. Monographs and Research Notes in Mathematics. CRC Press, Boca Raton, FL, third edition, 2026

    2026

  46. [46]

    V. Wei. Generalized hamming weights for linear codes.IEEE Transactions on Information Theory, 37(5):1412–1418, 1991. (Hiram H. L´ opez)Department of Mathematics, Virginia Tech, Blacksburg, V A USA Email address:hhlopez@vt.edu (Rodrigo San-Jos´ e)Department of Mathematics, Virginia Tech, Blacksburg, V A USA Email address:rsanjose@vt.edu (Nart Shalqini)Depa...

    1991