Digraph-defined external difference families and new circular external difference families

Sophie Huczynska, Christopher Jefferson, Struan McCartney · 2025

Read Digraph-defined external difference families and new circular external difference families by Sophie Huczynska, Christopher Jefferson, Struan McCartney (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20959.txt.

Introduction

Sophie Huczynska, Christopher Jefferson, and Struan McCartney frame, in 2025 work, difference families by graphs and arrow maps. Such families are sets whose gaps cover a group in set counts; they were born for safe-code craft in the early 2000s. Strong and ring forms came later, still hunted one by one.

Their graph frame gives one view of all the forms and seeds fresh asks. Builds by field counts and by plain group craft yield new ring families without end. One such family is the first of its kind in non-ring groups, with odd marks. A first ring family in a non-swap group also lands. The frame pays in new cases.

Catalog record

CREATORSophie Huczynska, Christopher Jefferson, Struan McCartney
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20959

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Digraph-defined external difference families and new circular external difference families Sophie Huczynska, Christopher Jefferson, Struan McCartney Abstract External difference families (EDFs) are combinatorial objects which were introduced in the early 2000s, motivated by information security applications; various generalizations have since been defined and investigated, in particular strong EDFs (SEDFs) and circular EDFs (CEDFs). We present a framework based on graphs and digraphs which offers a new unified way to view these structures, and leads to natural new research questions. We present constructions and structural results about these digraph-defined EDFs, and we obtain new explicit constructions for infinite families of CEDFs, in particular ( m ​ l 2 , m , l , 1 ) (ml^{2},m,l,1) -CEDFs. We construct the first infinite family of such CEDFs in non-cyclic abelian groups; these have odd values of m m and l l . We also present the first CEDF in a non-abelian group. 1 Introduction External difference families (EDFs) are combinatorial objects which were introduced in the early 2000s, motivated by information security applications [ 6 , 14 ] . Several variants of these have been introduced subsequently - e.g. strong external difference families (SEDFs) [ 15 ] , circular external difference families (CEDFs) [ 18 ] and others. Such a family consists of a collection \mathcal{A} of disjoint same-size subsets of a group G , with the property that the multiset of pairwise differences between elements of certain distinct sets in \mathcal{A} contains every non-identity element of G the same number of times. This is an external analogue of traditional difference families, which have been studied since the 1930s; for these, the pairwise differences between elements within each set are considered, and their multiset union is required to contain each non-identity element of G equally often. Connections between graphs and certain internal/external difference families are well known, and have been explored for example in [ 4 ] and [ 11 ] . In these papers, the vertices of the graph correspond to the elements of the group G and (labelled) edges between them represent the differences. This provides a link to graph decomposition problems. In [ 3 ] , the concept of strong difference family (SDF) is introduced as a collection of multisets such that the multiset union of their internal differences contains every element of G (inlcuding the identity) equally often. In [ 4 ] , a generalised definition of SDF introduced, in which the set of internal differences is defined via the edges of a digraph \Gamma , and the original definition is retrieved upon taking \Gamma to be complete. In [ 11 ] , graph decompositions are considered which correspond directly to certain EDFs in \mathbb{Z}_{n} via the process of development. In this paper, we present a different connection between graph theory and external difference families and their generalizations, inspired by - but distinct from - these ideas. We observe that the sets of such a family may be associated with the vertices of a digraph, with directed edges between precisely those pairs of vertices for which the external (directed) differences between the corresponding sets contribute to the multiset of external differences. This provides a natural and useful framework in which to view EDFs and their variants, particularly SEDFs and CEDFs. We note that a somewhat-related idea arises implicitly in [ 16 ] when an initial directed cycle is constructed, then a blow-up construction is applied to it to create a CEDF in a cyclic group. However our definition does not require any construction-based relationship between the digraph and the sets involved. The “graceful directed graphs” of [ 2 ] give examples of our structures in the specific case when the group is cyclic and every set is a singleton set. Our work was underpinned by search for examples in GAP [ 8 ] , using a constraint-satisfaction modelling language [ 1 ] and solver [ 9 ] . The paper is structured as follows: we first set up the necessary background and new definitions. We present constructions and examples of EDFs defined by complete graphs, cycles and complete bipartite graphs (both oriented and undirected). Those defined by oriented cycles (with the natural orientation) correspond to CEDFs, and we present various new results on CEDFs. In particular, we present a new infinite family of (ml^{2}+1,m,l,1) -CEDFs in non-cyclic abelian groups; these have both m and l odd. We also give the first example of a CEDF in a non-abelian group. We end by indicating further research questions emerging from this work. 2 Background Throughout, G will denote a finite group. Unless otherwise stated, we will write G additively. For subsets A,B of G , we define the multiset \Delta(A,B)=\{a-b:a\in A,b\in B\} . All unions are multiset unions unless otherwise stated. We will frequently work in \mathbb{Z}_{n} , the additive group of integers modulo n . We consider its elements as \{0,1,\ldots,n-1\} , with the natural order 0<1<\cdots<n-1 . For a,b\in\mathbb{Z}_{n} , we refer to the set of consecutive elements \{a,a+1,\ldots,b\} as the interval [a,b] . Note that this includes wraparound, so that for example in \mathbb{Z}_{5} , [3,1]=\{3,4,0,1\} whereas [1,3]=\{1,2,3\} . The concept of classical external difference family was first defined in [ 14 ] , motivated by an application to AMD codes: Definition 2.1 . Let G be a group of order n and let m>1 . A family of disjoint l -sets \{A_{1},\ldots,A_{m}\} in G is an (n,m,l,\lambda) -EDF if the multiset equation \bigcup_{\{i,j:i\neq j\}}\Delta(A_{i},A_{j})=\lambda(G\setminus\{0\}) holds. The strong version was first defined in [ 15 ] , corresponding to a stronger security model. Definition 2.2 . Let G be a group of order n and let m>1 . A family of disjoint l -sets \{A_{1},\ldots,A_{m}\} in G is an (n,m,l,\lambda) -SEDF if, for each i with 1\leq i\leq m , the multiset equation \bigcup_{\{j:j\neq i\}}\Delta(A_{i},A_{j})=\lambda(G\setminus\{0\}) holds. Note that a strong EDF will always be an EDF, but the converse need not be true. Recently, Stinson and Veitch introduced new objects called circular external difference families [ 18 ] . We note that the definition is still valid when the requirement for G to be abelian is removed. We further note that, except in those cases when the number of sets is at most three, CEDFs are not special cases of the standard EDFs. Definition 2.3 . Let G be an additive abelian group of order n . Suppose m\geq 2 and 1\leq c\leq m-1 . A family of disjoint l -sets \{A_{1},\ldots,A_{m}\} in G is an (n,m,l,\lambda) - c -CEDF if the following multiset equation holds: \bigcup_{i=0}^{m-1}\Delta(A_{i+c\mod m},A_{i})=\lambda(G\setminus\{0\}) . If c=1 then the c is sometimes omitted from the notation (as in [ 16 ] ). We present the following observation which clarifies the structure of c -CEDFs: Lemma 2.4 . Let \mathcal{A}=\{A_{1},\ldots,A_{m}\} be a disjoint collection of l -subsets of a group G . Suppose \mathcal{A} is a c -CEDF. Then, if \gcd(c,m)=d , the multiset in the definition may be written as a disjoint union of d multiset unions, each involving m/d sets, as follows (where all indices are taken modulo m ): \bigcup_{i=0}^{m-1}\Delta(A_{i+c\mod m},A_{i})=\bigcup_{j=0}^{d-1}\left(\bigcup_{i=0}^{(m/d-1)}\Delta(A_{(i+1)c+j},A_{ic+j})\right)=\lambda(G\setminus\{0\}) Proof. The decomposition of the m sets into d disjoint collections of m/d sets follows from the result on permutations

Read the complete text