{"id":"313827b2-4f12-48b4-90ea-37e1532cd245","arxiv_id":"1908.03533","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper constructs the first family of non-abelian strong external difference families, adds new recursive constructions in cyclic groups, and exhaustively classifies all such families in groups up to order 24.","lead":"This paper extends the study of strong external difference families, a class of structured subsets used in cryptography, from abelian groups to all finite groups. It presents the first known family of these objects in non-abelian groups and completely catalogues them for all groups up to order 24.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's pruning bound is off by one: it uses n-p instead of n-p+1, so the claimed exhaustive search for n≤24 would miss valid SEDFs.","rationale":"The reader's verdict was CONDITIONAL, citing unverified computational correctness. Stress-testing the central mathematical claim (Theorem 6.2) found no flaw: the dihedral construction for odd k is verified by hand, the difference tables cover each non-identity element exactly once, and the non-equivalence arguments in Corollary 6.3 are sound. However, the paper's abstract also claims complete enumeration for all groups up to order 24, and that claim relies on Algorithm 1. The printed pseudocode has a concrete off-by-one error in the pruning test: the number of available elements from position p to n is n-p+1, not n-p. This makes the search non-exhaustive, as demonstrated by the (5,2,2,1) case where a known SEDF is pruned away, and by the trivial (n,n,1,1) SEDF being rejected at the root. This is a correctness risk for the zero-count entries in Table 8 and the classification counts in Table 7, although it does not affect the hand-proved constructions. The appropriate response is to keep the conditional acceptance but strengthen the conditions: correct the pseudocode, supply the actual search implementation and equivalence-filtering artifacts, and re-verify the tables. The reader's weakest_assumption pointed at exactly this area; our analysis sharpens it from 'unverified' to 'incorrect as printed'.","tokens_in":22540,"tokens_out":27272,"duration_ms":233349,"concrete_test":"Implement Algorithm 1 exactly as printed and run it on Z5 with (n,m,k,lambda)=(5,2,2,1); record the outputs. If no SEDF is found (or the trivial (5,5,1,1) case is missed), the printed algorithm is not exhaustive. Then change line 4 to use n-p+1 and confirm all known SEDFs from Tables 7-8 are recovered; if counts change, the paper's completeness claim requires the corrected code and data.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Section 7, Algorithm 1 (SEDFSearch) line 4 prunes when m*k - sum|s| > n - p. But from position p the available values are G[p],...,G[n], i.e. n-p+1 elements, so the correct bound is n-p+1. As printed, any branch that needs exactly all remaining elements is rejected. For example, with G=Z5 and parameters (5,2,2,1), the branch L=[{0,1},{2}] at p=4 needs one more element; skipping element 3 and taking element 4 is pruned at p=5 because 1 > 0. The valid SEDF {0,1},{2,4} is therefore never output, contradicting Table 7. Even the trivial (n,n,1,1)-SEDF is pruned immediately at p=2 since n-1 > n-2. This does not affect the hand-proved Theorem 6.2, but it voids the claimed completeness of Tables 7 and 8 and the zero counts for (21,2,10,5) and (21,6,2,1) unless the implemented code used a corrected bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22709,"tokens_out":10015,"duration_ms":97849,"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":[{"comment":"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.","section":"Section 7.1, Algorithm 1, line 4"},{"comment":"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.","section":"Section 7.2, Tables 7 and 8"}],"minor_comments":[{"comment":"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.","section":"Proof of Theorem 5.1"},{"comment":"The phrase 'After SEDFSearchState has produced a list' appears to be a typo; it should read 'After SEDFSearch has produced a list'.","section":"Section 7.1, text after Algorithm 1"},{"comment":"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.","section":"Table 7"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The theoretical core of the paper, in particular the dihedral construction and the recursive abelian constructions, appears sound and is the main value of the work. The computational section is the weak point: the printed algorithm is demonstrably incorrect as written, and the lack of artifacts makes the enumeration claims unverifiable. If the authors provide a corrected algorithm and reproduce the tables with code or data, the computational claims could be salvaged; otherwise the completeness statements should be downgraded."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The new math is real and mostly clean. Theorem 6.2 gives the first non-abelian SEDFs, in dihedral groups, and the proof is a straightforward difference-table verification. Corollary 6.3 then gives two non-equivalent (k^2+1,2,k,1)-SEDFs for every k>2, using Theorem 5.5 for even k. The recursive constructions in Section 5 are a genuine advance over the scattered abelian examples in the literature. Proposition 4.3 is a small but nice non-existence result. The authors' notion of equivalence for EDFs/SEDFs is natural and handled correctly.\n\nThe soft spot is Section 7. The stress-test concern is correct: Algorithm 1's pruning bound is off by one. From position p the remaining usable values are G[p],...,G[n], which is n-p+1 elements, not n-p. As printed, any branch that still needs exactly the remaining elements is pruned. Concretely, the (5,2,2,1)-SEDF {0,1},{2,4} in Z5 is missed, and even the trivial (n,n,1,1)-SEDF gets pruned immediately. So the printed algorithm cannot be the one that produced Tables 7 and 8. This is a presentation or implementation inconsistency, not a fatal blow to the hand proofs, but it makes the computational claims unreproducible. No code, data files, or hashes are provided; the GAP Images equivalence filtering is a black box. I'd want the authors to either correct the bound and state it clearly, or release the search code and data. The zero counts for (21,2,10,5) and (21,6,2,1) rest entirely on that unverified search.\n\nOverall, the core mathematics deserves a proper referee. The paper is for design theorists and people working on AMD codes. I'd accept it for review, with major revisions or at least a corrected computational section. If I were the editor, I would not desk-reject.","headline":"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.","tokens_in":23356,"tokens_out":3978,"would_cite":true,"duration_ms":40380,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B10","94B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["strong external difference families","non-abelian groups","dihedral groups","difference families","equivalence","combinatorial enumeration","algebraic manipulation detection codes","admissible parameters"],"falsifier":"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.","tokens_in":22256,"feed_emoji":"🧩","tokens_out":15954,"duration_ms":146745,"temperature":0.7,"pith_summary":"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.","feed_headline":"First non-abelian strong external difference families constructed","feed_subtitle":"Dihedral groups give the first non-abelian examples; cyclic constructions make two inequivalent SEDFs for every k greater than 2.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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$."],"forward_implications":["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."],"supporting_citations":[{"why":"introduced SEDFs and the standard cyclic $(k^2+1,2,k,1)$ construction that the paper generalises","marker":"[14]"},{"why":"supplies the parameter conditions, the $\\lambda