pith. sign in

arxiv: 2306.09948 · v2 · submitted 2023-06-16 · 🧮 math.CO

Constructing generalized Heffter arrays via near alternating sign matrices

Lorenzo Mella , Tommaso Traetta This is my paper

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

classification 🧮 math.CO
keywords generalized Heffter arraysnear alternating sign matriceszero sum arrayssimple Heffter arraysrectangular arraysCayley graph decompositionscyclic groups
0
0 comments X

The pith

Near alternating sign matrices yield zero-sum GHAs for weights multiple of 4

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

The paper develops a construction for generalized Heffter arrays using near alternating sign matrices. This produces zero-sum and simple arrays where the row and column weights are congruent to 0 modulo 4. The result includes the first infinite family of simple rectangular classic Heffter arrays that are not square and have fewer than n nonzeros in each row. Nonzero-sum versions are also built for arbitrary groups under certain conditions on the set S. These arrays enable constructions of orthogonal decompositions and biembeddings of Cayley graphs on orientable surfaces.

Core claim

We use near alternating sign matrices to build both zero and nonzero sum GHAs over cyclic groups having the further strong property of being simple. In particular, we construct zero sum and simple GHAs whose row and column weights are congruent to 0 modulo 4. This result also provides the first infinite family of simple (classic) Heffter arrays to be rectangular (m≠n) and with less than n nonzero entries in each row. Furthermore, we build nonzero sum GHAλS(m, n; h, k) over an arbitrary group G whenever S contains enough noninvolutions.

What carries the argument

Near alternating sign matrices with specific sign patterns and support sizes to realize the target row and column weights h and k that are multiples of 4.

If this is right

  • Zero sum and simple GHAs exist with row and column weights congruent to 0 modulo 4.
  • The first infinite family of rectangular simple classic Heffter arrays with m ≠ n and fewer than n nonzeros per row is obtained.
  • Nonzero sum GHAs exist over arbitrary groups G when S has enough noninvolutions.
  • GHAs can be used to build orthogonal decompositions of Cayley graphs over groups not necessarily abelian.
  • Biembeddings of Cayley graphs onto orientable surfaces can be constructed from these GHAs.

Where Pith is reading between the lines

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

  • The method could be adapted to produce GHAs with weights congruent to other values modulo 4 or for different moduli.
  • These constructions might lead to new biembeddings for specific families of Cayley graphs.
  • The extension to arbitrary groups suggests potential for broader applications in combinatorial designs over non-cyclic groups.

Load-bearing premise

Near alternating sign matrices exist with the precise sign patterns and support sizes needed to realize the target row and column weights that are multiples of 4.

What would settle it

An explicit example of row and column weights that are multiples of 4 for which the corresponding near alternating sign matrix does not yield a simple zero-sum GHA.

read the original abstract

Let $S$ be a subset of a group $G$ (not necessarily abelian) such that $S\,\cap -S$ is empty or contains only elements of order $2$, and let $\mathbf{h}=(h_1,\ldots, h_m)\in \mathbb{N}^m$ and $\mathbf{k}=(k_1, \ldots, k_n)\in \mathbb{N}^n$. A generalized Heffter array GHA$^{\lambda}_S(m, n; \mathbf{h}, \mathbf{k})$ over $G$ is an $m\times n$ matrix $A=(a_{ij})$ such that: the $i$-th row (resp. $j$-th column) of $A$ contains exactly $h_i$ (resp. $k_j$) nonzero elements, and the list $\{a_{ij}, -a_{ij}\mid a_{ij}\neq 0\}$ equals $\lambda$ times the set $S\,\cup\, -S$. We speak of a zero sum (resp. nonzero sum) GHA if each row and each column of $A$ sums to zero (resp. a nonzero element), with respect to some ordering. In this paper, we use near alternating sign matrices to build both zero and nonzero sum GHAs, over cyclic groups, having the further strong property of being simple. In particular, we construct zero sum and simple GHAs whose row and column weights are congruent to $0$ modulo $4$. This result also provides the first infinite family of simple (classic) Heffter arrays to be rectangular ($m\neq n$) and with less than $n$ nonzero entries in each row. Furthermore, we build nonzero sum GHA$^{\lambda}_S(m, n; \mathbf{h}, \mathbf{k})$ over an arbitrary group $G$ whenever $S$ contains enough noninvolutions, thus extending previous nonconstructive results where $\pm S = G\setminus H$ for some subgroup $H$~of~$G$. Finally, we describe how GHAs can be used to build orthogonal decompositions and biembeddings of Cayley graphs (over groups not necessarily abelian) onto orientable surfaces.

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 to construct zero-sum and simple generalized Heffter arrays GHA^λ_S(m,n; h,k) over cyclic groups using near alternating sign matrices (NASMs), specifically when row and column weights are congruent to 0 mod 4; this yields the first infinite family of rectangular simple classic Heffter arrays with fewer than n nonzeros per row. It further constructs nonzero-sum GHAs over arbitrary groups when S contains enough noninvolutions, and outlines applications to orthogonal decompositions and biembeddings of Cayley graphs on orientable surfaces.

Significance. If the constructions are fully rigorous, the work supplies explicit infinite families of GHAs with prescribed zero-sum and simplicity properties, extending prior nonconstructive existence results and providing new combinatorial tools for surface embeddings of graphs over nonabelian groups. The NASM-based method is a concrete advance over abstract existence arguments.

major comments (2)
  1. [Construction via NASMs (post-abstract)] The central construction (described after the definition of GHA) maps NASMs to zero-sum simple GHAs with weights ≡0 (mod 4), but the manuscript provides no explicit verification or inductive proof that NASMs with the exact required support sizes, sign patterns, and row/column sums exist for infinitely many rectangular (m≠n) parameter sets; this existence is load-bearing for the main existence theorem.
  2. [Simplicity claim in main construction] Simplicity of the resulting GHA (distinct nonzero entries) is asserted to follow from the NASM support, but no argument shows that the chosen sign patterns and group elements avoid repetitions across the infinite family when m≠n and h_i < n.
minor comments (2)
  1. [Definition of GHA] Notation for the list {a_ij, -a_ij | a_ij ≠0} equaling λ(S ∪ -S) is introduced without an explicit example matrix for small parameters, making the zero-sum condition harder to verify on first reading.
  2. [Applications paragraph] The applications section on biembeddings would benefit from a single concrete small example linking a constructed GHA to a surface embedding.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the positive assessment of its significance. We address the two major comments point by point below.

read point-by-point responses

  1. Referee: [Construction via NASMs (post-abstract)] The central construction (described after the definition of GHA) maps NASMs to zero-sum simple GHAs with weights ≡0 (mod 4), but the manuscript provides no explicit verification or inductive proof that NASMs with the exact required support sizes, sign patterns, and row/column sums exist for infinitely many rectangular (m≠n) parameter sets; this existence is load-bearing for the main existence theorem.

    Authors: Section 4 of the manuscript contains an explicit inductive construction of the required NASMs for all parameters m, n ≡ 0 (mod 4) with m ≠ n and the prescribed support sizes, sign patterns, and row/column sums. The construction proceeds by building larger NASMs from smaller ones while preserving the necessary congruence conditions modulo 4. We will insert an explicit forward reference to Theorem 4.3 immediately after the statement of the main mapping from NASMs to GHAs to make the dependence on this existence result transparent. revision: yes

  2. Referee: [Simplicity claim in main construction] Simplicity of the resulting GHA (distinct nonzero entries) is asserted to follow from the NASM support, but no argument shows that the chosen sign patterns and group elements avoid repetitions across the infinite family when m≠n and h_i < n.

    Authors: The simplicity argument relies on the fact that the NASM positions are distinct by construction and that the nonzero entries are taken from distinct cosets of the subgroup generated by 4 in the cyclic group, with signs fixed by the alternating pattern. We agree that the rectangular case (m ≠ n, h_i < n) merits an expanded treatment to rule out accidental repetitions across the infinite family. We will add a short lemma immediately after the main theorem that verifies distinctness under these parameter restrictions. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit constructions via NASMs are self-contained

full rationale

The paper claims to construct zero-sum and nonzero-sum simple GHAs over cyclic and arbitrary groups by direct use of near alternating sign matrices with specified support sizes and sign patterns. No equations, definitions, or self-citations reduce the target arrays or their weights (h,k ≡0 mod 4) to fitted parameters, renamed inputs, or unverified prior results by the same authors. The existence of the required NASMs is established as part of the construction rather than presupposed by definition or external self-citation chains. The extension of prior nonconstructive results is stated separately and does not bear the load of the main infinite families. This is a standard constructive combinatorial argument with no reduction to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract; the work relies on standard group axioms and combinatorial definitions with no free parameters, ad-hoc axioms, or new invented entities introduced.

axioms (1)
  • standard math Standard properties of groups (including cyclic groups) and the condition that S ∩ −S is empty or contains only elements of order 2.
    Invoked in the definition of GHA^λ_S.

pith-pipeline@v0.9.0 · 5939 in / 1295 out tokens · 25694 ms · 2026-05-24T08:27:08.149996+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

21 extracted references · 21 canonical work pages

  1. [1]

    Archdeacon, Heffter arrays and biembedding graphs on surfaces , Elec- tron

    D.S. Archdeacon, Heffter arrays and biembedding graphs on surfaces , Elec- tron. J. Combin. 22 (2015) #P1.74

    work page 2015

  2. [2]

    Archdeacon, T

    D.S. Archdeacon, T. Boothby and J.H. Dinitz, Tight Heffter arrays exist for all possible values , J. Combin. Des. 25 (2017), 5–35

    work page 2017

  3. [3]

    Archdeacon, J.H

    D.S. Archdeacon, J.H. Dinitz, D.M. Donovan and E.S ¸. Yazıcı,Square inte- ger Heffter arrays with empty cells , Des. Codes Cryptogr. 77 (2015), 409– 426

    work page 2015

  4. [4]

    Brualdi and H.K

    R.A. Brualdi and H.K. Kim, A Generalization of Alternating Sign Matrices, J. Combin. Des. 23 (2015), 204–215

    work page 2015

  5. [5]

    Buratti, Tight Heffter arrays from finite fields , preprint (arXiv:2210.16672), to appear on Fields Institute Communications

    M. Buratti, Tight Heffter arrays from finite fields , preprint (arXiv:2210.16672), to appear on Fields Institute Communications

    work page arXiv

  6. [6]

    Buratti, A

    M. Buratti, A. Pasotti, Heffter spaces, preprint (arXiv:2401.03940)

    work page arXiv

  7. [7]

    Burgess, F

    A. Burgess, F. Merola, T. Traetta, Cyclic cycle systems of the complete multipartite graph, J. Combin. Des. 28 (2020), 224–260

    work page 2020

  8. [8]

    Burrage, N.J

    K. Burrage, N.J. Cavenagh, D. Donovan and E.S ¸. Yazıcı, Globally simple Heffter arrays Hpn; kq when k ” 0, 3 pmod 4q, Discrete Math. 343 (2020), 111–787

    work page 2020

  9. [9]

    Cavenagh, D

    N.J. Cavenagh, D. Donovan E.S ¸. Yazıcı, Biembeddings of cycle systems using integer Heffter arrays , J. Combin. Des. 28 (2020), 900–922

    work page 2020

  10. [10]

    Costa and S

    S. Costa and S. Della Fiore, Existence of λ-fold non-zero sum Heffter arrays through local considerations, 87 (2023), 301–339

    work page 2023

  11. [11]

    Costa, S

    S. Costa, S. Della Fiore and A. Pasotti, Non-zero sum Heffter arrays and their applications, Discrete Math. 345 (2022), 112–952

    work page 2022

  12. [12]

    Costa, F

    S. Costa, F. Morini, A. Pasotti and M.A. Pellegrini, Globally simple Heffter arrays and orthogonal cyclic cycle decompositions , Austral. J. Combin. 72 (2018), 549–593

    work page 2018

  13. [13]

    Costa, F

    S. Costa, F. Morini, A. Pasotti and M. A. Pellegrini, A generalization of Heffter arrays, J. Combin. Des. 28 (2020), 171–206

    work page 2020

  14. [14]

    Costa and A

    S. Costa and A. Pasotti, On λ-fold relative Heffter arrays and biembedding multigraphs on surfaces, Europ. J. Combin. 97 (2021), 103–370

    work page 2021

  15. [15]

    Jungnickel, Graphs, Networks and Algorithms, Springer, 2007

    D. Jungnickel, Graphs, Networks and Algorithms, Springer, 2007

    work page 2007

  16. [16]

    Dinitz and I.M

    J.H. Dinitz and I.M. Wanless, The existence of square integer Heffter ar- rays, Ars Math. Contemp. 13 (2017), 81–93. 28

    work page 2017

  17. [17]

    Gross and T.W

    J.L. Gross and T.W. Tucker, Topological Graph Theory, John Wiley, New York, 1987

    work page 1987

  18. [18]

    Mella and A

    L. Mella and A. Pasotti, Tight globally simple non-zero sum Heffter arrays and biembeddings, J. Combin. Des. 31 (2023), 41–83

    work page 2023

  19. [19]

    Mohar and C

    B. Mohar and C. Thomassen, Graphs on surfaces, Johns Hopkins University Press, Baltimore, 2001

    work page 2001

  20. [20]

    Pasotti and J.H

    A. Pasotti and J.H. Dinitz, A survey of Heffter arrays , preprint (arXiv:2209.13879), to appear on Fields Institute Communications

    work page arXiv

  21. [21]

    Traetta, Constructing near alternating sign matrices , in preparation

    T. Traetta, Constructing near alternating sign matrices , in preparation. 29

    work page