Pith. sign in

REVIEW 2 major objections 4 minor 15 references

Strong external difference families in abelian and non-abelian groups

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper constructs the first infinite family of strong external difference families (SEDFs) in non-abelian groups, and proves that for every $k>2$ at least two non-equivalent SEDFs with parameters $(k^2+1,2,k,1)$ exist.

desk verdict First non-abelian SEDFs with a clean proof, but the computational classification section has a real reproducibility gap: the printed search algorithm prunes valid branches and cannot be the one that produced the tables. read the letter →

arxiv 1908.03533 v2 pith:3TYIXZMO submitted 2019-08-09 math.CO

Sophie Huczynska , Christopher Jefferson , Silvia Nepsinska This is my paper · ORCID
classification math.CO MSC 05B1094B05
keywords strongexternaldifferencefamiliesnon-abeliangroupsdihedralequivalencecombinatorialenumerationalgebraicmanipulationdetectioncodesadmissibleparameters
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Strong external difference families are collections of disjoint subsets of a group in which all ordered differences from one subset to the union of the others cover every non-identity element equally often; they arise in algebraic manipulation detection codes. This paper extends them from abelian groups to all finite groups and establishes that non-abelian examples exist: for every odd $k>1$, the dihedral group of order $k^2+1$ contains a $(k^2+1,2,k,1)$-SEDF. It also introduces a workable notion of equivalence for these families, uses it to show that at least two non-equivalent such SEDFs exist for every $k>2$, and gives a recursive construction that produces many cyclic SEDFs from one seed. A computational search completes the classification of SEDFs in all groups up to order 24. If the results stand, SEDFs are not an abelian-only phenomenon, and the admissible parameter landscape is wider than previously known.

What carries the argument

The operative object is a strong external difference family: a set of $m\ge2$ disjoint $k$-subsets $A_1,\dots,A_m$ of a group such that, for each $i$, every non-identity group element appears exactly $\lambda$ times among ordered differences $xy^{-1}$ with $x\in A_i$ and $y$ in the union of the other subsets. The construction is carried by an explicit difference-table covering: in the dihedral group, the differences split into four cases depending on whether each factor is a rotation or a reflection, and after stripping the reflection factor each case reduces to covering every residue in $\mathbb{Z}_{(k^2+1)/2}$ exactly once by paired intervals. A second mechanism is the recursive blow-up of a cyclic seed SEDF, in which each seed element is replaced by a block of $a$ consecutive multiples so that each old difference expands into an interval and the intervals tile the larger cyclic group.

What would settle it

For $k=3$, take $A_1=\{e,s,r\}$ and $A_2=\{sr,r^3,sr^4\}$ in $D_{10}$ and compute the nine products $xy^{-1}$; any repetition or missing non-identity element disproves Theorem 6.2. For the enumeration claim, an independent exhaustive search over all groups of order 24 should reproduce the stated outcome: exactly one non-equivalent SEDF in $D_{10}$ and none in the order-21 non-abelian group.

Watch

Extended reading notes

Core claim

The central discovery is an explicit infinite family of non-abelian SEDFs. In the dihedral group $D_{k^2+1}$ with generators $r,s$ satisfying $s^2=e$, $r^{(k^2+1)/2}=e$, and $sr=r^{-1}s$, the paper's Theorem 6.2 takes, for odd $k>1$, the two $k$-sets $A_1=\{r^i:0\le i\le (k-1)/2\}\cup\{sr^j:0\le j\le (k-3)/2\}$ and $A_2=\{r^{ik}:1\le i\le (k-1)/2\}\cup\{sr^{jk+(k-1)/2}:0\le j\le (k-1)/2\}$, and proves they form a $(k^2+1,2,k,1)$-SEDF: the difference multiset $\{xy^{-1}:x\in A_1,y\in A_2\}$ contains every non-identity element exactly once, and the reverse differences are its inverses. This is the first non-abelian SEDF family. The paper then proves that for every $k>2$ there are at least two non-equivalent $(k^2+1,2,k,1)$-SEDFs, using the dihedral example for odd $k$ and two distinct cyclic constructions for even $k$.

Load-bearing premise

The classification tables for groups up to order 24 are complete only if the custom backtracking search and the equivalence filtering are correct, and the paper supplies no code or data files for an independent check.

Editorial extensions

If this is right

  • Non-abelian groups support SEDFs, so every existing statement that presupposes abelian groups must be re-examined for non-abelian analogues.
  • For every $k>2$, the parameter set $(k^2+1,2,k,1)$ is witnessed by at least two non-equivalent SEDFs, giving an infinite supply of inequivalent designs.
  • The recursive construction generates infinitely many cyclic SEDFs from a single seed, and inequivalent seeds can lead to inequivalent larger SEDFs.
  • The enumeration up to order 24 is complete: the only non-trivial non-abelian SEDF in that range is the $(10,2,3,1)$-SEDF in the dihedral group $D_{10}$.
  • Any non-trivial SEDF with $\lambda=1$ and $m>2$ cannot also be a coSEDF, which narrows the search for possible non-abelian $m>2$ examples.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same dihedral difference-table idea should be tried in other groups with an involutory generator, such as dicyclic groups or semidirect products, where conjugating a rotation by a reflection changes which interval identities are available.
  • Because Proposition 4.7's abelian rigidity used commutativity, the admissible parameter sets in the paper's Table 1 with $m>2$ are natural targets for a computational search in non-abelian groups up to order 64.
  • The new equivalence notion can be applied retrospectively to existing constructions, so some SEDFs previously counted as different may collapse into one equivalence class once translations and automorphisms are allowed; the paper already exhibits this for $k=5$.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper extends the notion of strong external difference families (SEDFs) from abelian to arbitrary finite groups, introduces an equivalence relation for EDFs and SEDFs, proves parameter restrictions and new existence/non-existence results, gives recursive constructions for cyclic SEDFs and GSEDFs, and exhibits the first infinite family of non-abelian SEDFs using dihedral groups. It also reports a computational enumeration of SEDFs in all groups of order at most 24, claiming complete classification results in Tables 7 and 8. The main theoretical results are Theorem 6.2, giving a (k^2+1,2,k,1)-SEDF in the dihedral group D_{k^2+1} for every odd k>1, and Corollary 6.3, which uses it to show that at least two non-equivalent (k^2+1,2,k,1)-SEDFs exist for every k>2.

Significance. If the results stand, this is the first construction of non-abelian SEDFs, a structural development that opens a new direction in the area. The equivalence notion and the recursive framework in Section 5 are useful contributions, as is the result that at least two non-equivalent SEDFs exist for all k>2. The paper is generally well written, with detailed proofs and helpful examples. The computational enumeration, however, is not reproducible from the information given, and the printed search algorithm contains a concrete off-by-one error in its pruning condition, so the completeness claims for the tables need verification or correction before the computational contribution can be accepted.

major comments (2)
  1. [Section 7.1, Algorithm 1, line 4] The pruning inequality is off by one. At a recursive call with current position p, the values that can still be added are G[p], ..., G[n], which number n-p+1 elements, not n-p. The test `m*k - sum|s| > n-p` therefore rejects branches that would need exactly all remaining elements. For example, the trivial (n,n,1,1)-SEDF is pruned at the initial call (p=2) because n-1 > n-2, so the algorithm as printed does not return all SEDFs as claimed. The same defect prunes the (5,2,2,1) branch L=[{0,1},{2}] at p=5, even though adding element 4 would complete a valid SEDF. This means the completeness of Tables 7 and 8 is unsupported unless the implemented code used the corrected bound n-p+1. Please correct the pseudocode or specify precisely what bound the actual implementation used.
  2. [Section 7.2, Tables 7 and 8] The classification is presented as complete for all groups up to order 24, but no code, data files, or version information are supplied. The equivalence filtering relies on the GAP Images package but gives no script or details of the canonicalization. Combined with the off-by-one error in the printed algorithm, an independent reader cannot verify the exhaustive enumeration or the zero counts for (21,2,10,5) and (21,6,2,1). I ask that the authors provide the search program and output, or at least state the exact pruning condition and filtering steps used in the computation.
minor comments (4)
  1. [Proof of Theorem 5.1] In the case analysis after 'If this is C1', the inequality '1 ≤ f(x+1) < a−2' seems to be a typo; the intended bound is likely of the form f(x+1) ≤ a−1. The argument is still understandable, but the displayed inequality should be corrected.
  2. [Section 7.1, text after Algorithm 1] The phrase 'After SEDFSearchState has produced a list' appears to be a typo; it should read 'After SEDFSearch has produced a list'.
  3. [Table 7] The row for (9,2,4,2) lists Z9 with 0 SEDFs; placing the explanation 'ruled out by Theorem 4.2 of [8]' in the table caption or a note would improve readability.
  4. [Throughout] There are several minor grammatical and typographical slips (e.g., 'definition' in Section 2, variable spacing in the pseudocode). These do not affect the mathematics but should be cleaned up in a revision.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the new SEDF constructions are proved from explicit block definitions and direct difference-multiset verification, not from their own conclusions.

full rationale

The central claims of the paper are existence and non-equivalence theorems for SEDFs. Theorem 5.1 explicitly defines B1 and B2 and verifies the subtraction table; Theorem 5.3 takes an existing SEDF as an input and constructs a larger one, which is a legitimate recursive construction rather than a circular one; Theorem 5.5 proves non-equivalence of the recursively obtained SEDFs by a direct automorphism/translation argument rather than assuming the desired result; Theorem 6.2 explicitly defines the two blocks in the dihedral group and verifies that the external difference multiset contains each non-identity element exactly once via the displayed interval arithmetic. The only self-citations are to prior published results of one or more of the authors, notably [6], [7], and [9]. These are used as external lemmas or software citations, not as an unverified uniqueness theorem, and they are not the load-bearing content of the main new constructions. The computational enumeration in Section 7 is an exhaustive-search claim; it is not a fitted parameter renamed as a prediction, and any concern about the pruning bound in Algorithm 1 is a correctness/reproducibility issue rather than a circularity. No derivation step reduces by construction to its own input, so the paper is essentially self-contained for its main results.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No additional free parameters are fitted to data; the constructions are parameterized by integers like k, a, r, but these are variables, not fitted values. The paper introduces the coSEDF/coEDF definitions, but these are definitions, not postulated entities.

assumptions (4)
  • domain assumption The classical (k^2+1, 2, k, 1)-SEDF in Z_{k^2+1} described in Proposition 4.6(1) (from [14]) is valid.
    Used as the base case for the recursive construction in Theorem 5.3 and as one of the two non-equivalent SEDFs in Corollary 6.3 for odd k; not proven in this paper.
  • domain assumption The non-existence results compiled in Proposition 4.5 (from [1], [6], [10], [12]) are correct.
    These external results rule out many abelian parameter sets in Section 7.2, and the paper's completeness claim for abelian groups depends on them.
  • domain assumption GAP's SmallGroups library and Images package perform group enumeration and canonical image computation correctly (Section 7).
    The computational classification of all groups up to order 24 relies on these external software tools; the paper describes the algorithm but does not audit the software.
  • standard math Standard facts about cyclic group automorphisms and dihedral group presentations.
    The non-equivalence arguments in Theorems 5.1 and 5.5 use the fact that automorphisms of Z_n are multiplications by units; the dihedral construction uses s^2=1, r^{n/2}=1, sr=r^{-1}s.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strong external difference families in abelian and non-abelian groups." pith.science (2026). https://pith.science/paper/3TYIXZMO

@misc{pith2026190803533,
  author       = {Pith},
  title        = {Pith review of: Strong external difference families in abelian and non-abelian groups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3TYIXZMO}},
  note         = {Machine review of arXiv:1908.03533}
}
abstract

Strong external difference families (SEDFs) have applications to cryptography and are rich combinatorial structures in their own right; until now, all SEDFs have been in abelian groups. In this paper, we consider SEDFs in both abelian and non-abelian groups. We characterize the order of groups possessing admissible parameters for non-trivial SEDFs, develop non-existence and existence results, several of which extend known results, and present the first family of non-abelian SEDFs. We introduce the concept of equivalence for EDFs and SEDFs, and begin the task of enumerating SEDFs. Complete results are presented for all groups up to order $24$, underpinned by a computational approach.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    J. Bao, L. Ji, R. Wei and Y. Zhang, New existence and nonexi stence results for strong external difference families, Discrete Math., 341(6): 1798- 1805, 2018

    work page 2018

  2. [2]

    Codes Cryptogr

    M.Buratti, On disjoint ( v, k, k− 1) difference families, Des. Codes Cryptogr. 87: 745-755, 2019. 19

    work page 2019

  3. [3]

    Chang and C

    Y. Chang and C. Ding, Constructions of external difference families and disjoint difference families, Des. Codes Cryptogr. 40: 167-185, 2006

    work page 2006

  4. [4]

    C. J. Colbourn and J. H. Dinitz, Handbook of Combinatoria l Designs (2nd Edition), Chap- man and Hall/CRC, 2006

    work page 2006

  5. [5]

    (https://www.gap-system.org)

    The GAP Group, GAP – Groups, Algorithms, and Programming , Version 4.10.2; 2019. (https://www.gap-system.org)

    work page 2019

  6. [6]

    Huczynska and M

    S. Huczynska and M. B. Paterson, Existence and non-exist ence results for strong external difference families, Discrete Math., 341(1): 87-95, 2018

    work page 2018

  7. [7]

    Huczynska and M

    S. Huczynska and M. B. Paterson, Weighted external differe nce families and R-optimal AMD codes, Discrete Math., 342(3): 855-867, 2019

    work page 2019

  8. [8]

    Jedwab and S

    J. Jedwab and S. Li, Construction and nonexistence of str ong external difference families, J. Algebraic Comb., 49(1): 21-48, 2019

    work page 2019

Show all 15 references
  1. [9]

    Jefferson, E

    C. Jefferson, E. Jonauskyte, M. Pfeiffer and R. Waldecker, Mi nimal and canonical images, J. Algebra 521: 481-506, 2019

    2019

  2. [10]

    Leung, S

    K.H. Leung, S. Li and T. F. Prabowo, Nonexistence of stro ng external difference families in abelian groups of order being product of at most three prim es, arXiv preprint

  3. [11]

    X. Lu, X. Niu and H. Cao, Some results on generalised exte rnal difference families, Des. Codes Cryptogr. (86) 12: 2857-2868, 2018

    2018

  4. [12]

    W. J. Martin and D. R. Stinson, Some nonexistence result s for strong external difference families using character theory, Bull. Inst. Combin. Appl. , 80: 79-92, 2017

    2017

  5. [13]

    Ogata, K

    W. Ogata, K. Kurosawa, D. R. Stinson and H. Saido, New com binatorial designs and their applications to authentication codes and secret sharing sc hemes, Discrete Math., 279(1): 383–405, 2004

    2004

  6. [14]

    M. B. Paterson and D. R. Stinson, Combinatorial charact erizations of algebraic manip- ulation detection codes involving generalized difference fa milies, Discrete Math., 339(12): 2891-2906, 2016

    2016

  7. [15]

    J. Wen, M. Yang, F. Fu and K. Feng, Cyclotomic constructi on of strong external difference families in finite fields, Des. Codes Cryptogr. 86(5): 1149-1 159, 2018. 20

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.