# New results on non-disjoint and classical strong external difference
families

Sophie Huczynska and Sophie Hume Email<EMAIL_ADDRESS>(Sophie
Huczynska)Email<EMAIL_ADDRESS>(Sophie Hume)

(School of Mathematics and Statistics, University of St Andrews,
St Andrews, Fife, KY16 9SS,UK)

###### Abstract

Classical strong external difference families (SEDFs) are much-studied
combinatorial structures motivated by information security applications; it is
conjectured that only one classical abelian SEDF exists with more than two
sets. Recently, non-disjoint SEDFs were introduced; it was shown that families
of these exist with arbitrarily many sets. We present constructions for both
classical and non-disjoint SEDFs, which encompass all known non-cyclotomic
examples for either type (plus many new examples) using a sequence-based
framework. Moreover, we introduce a range of new external difference
structures (allowing set-sizes to vary, and sets to be replaced by multisets)
in both the classical and non-disjoint case, and show how these may be applied
to various communications applications.

##  1 Introduction

††footnotetext: Keywords: strong external difference family, non-disjoint
strong external difference family, binary sequences, optical orthogonal codes,
AMD codes

Strong external difference families (SEDFs) are combinatorial structures
consisting of disjoint families of sets in a group $G$ satisfying a strong
uniformity condition on their external differences. These were introduced by
Paterson and Stinson in [14], motivated by an information security application
to AMD codes and secret-sharing schemes. In [14], various related
combinatorial objects were introduced, including generalised strong external
difference families (GSEDFs) in which the set-sizes are allowed to vary. These
combinatorial objects have been well-studied, with SEDFs gaining particular
notoriety since only one example with more than two sets is currently known
(comprising $11$ sets in a group of size $243$), despite extensive
investigation [1, 4, 7, 14, 17]. SEDFs appear to be very restricted in other
respects too, with no infinite families known for any fixed $\lambda$ greater
than $1$, and very few constructions known in general. Numerous non-existence
results have been proved for them [7, 8, 9, 11], and it is conjectured that no
further abelian examples with more than 2 sets exist [8]. We shall refer to
these structures (whose sets are disjoint) as the “classical” versions.

Recently in [5], non-disjoint SEDFs were introduced; these are defined
analogously to classical SEDFs except that $0$ is treated as a difference just
like any other group element, and hence the sets are non-disjoint. Unlike the
situation for classical SEDFs, it is shown in [5] that constructions exist
with any number of sets, and that 2-set constructions exist with any value of
$\lambda$.

All non-disjoint SEDF constructions so far, satisfy the property that the
external differences between any pair of sets satisfy the uniformity
condition; we call these non-disjoint PSEDFs. (All known classical SEDFs have
an analogous structure, with the exception of the single example with $11$
sets). Non-disjoint PSEDFs arise naturally in communications applications
because in $\mathbb{Z}_{v}$ they correspond precisely to optical orthogonal
codes (OOCs) in which the lowest-possible cross-correlation value
$\lambda_{c}$ is obtained [5]. Pairwise cross-correlation is also of interest
in other communications settings, e.g. pairwise shift invariant protocol
sequences [22].

In this paper, we further investigate non-disjoint SEDFs and classical SEDFs,
and provide a unified sequence-based framework for both. We present a
construction which encompasses all known non-disjoint SEDFs as special cases
(and provides many new ones), and another construction which encompasses all
known classical SEDF results not obtainable from cyclotomy. The latter is
useful for strong circular AMD codes and strong circular EDFs (SCEDFs),
recently introduced in [16] to construct non-malleable threshold schemes.
While the connection between sequences and difference structures is known, its
constructive use in describing and building external difference families is
novel.

We also extend the definition of non-disjoint PSEDFs and non-disjoint SEDFs in
two directions. Firstly, we allow distinct set-sizes, to obtain versions which
we call “generalised”. This is a precise analogue of the process by which a
classical SEDF is extended to a classical GSEDF in [14]. Again, in the non-
disjoint setting we can obtain a wider range of parameters than is currently
known for classical GSEDFs [10, 17]. Secondly, we allow the component sets to
be replaced by multisets. This may be viewed as an external analogue of the
“strong difference families” introduced in [2]; the multiset versions also
provide a useful technical tool in establishing non-multiset results.

We demonstrate ways in which new non-disjoint SEDFs and GPSEDFs can be made
from old, obtaining the first examples in non-cyclic abelian groups. We also
show that non-disjoint SEDFs and GSEDFs exist in non-abelian groups; there is
currently just one known infinite non-abelian family of classical SEDFs ([4]).

While non-disjoint PSEDFs in $\mathbb{Z}_{v}$ yield constant-weight OOCs, non-
disjoint GPSEDFs yield variable-weight OOCs (VW-OOCs), first introduced in
[19]. Our constructions (and adaptations of these) yield infinite families of
variable-weight OOCs for a wide range of parameters; a lack of systematic
constructions for VW-OOCs is noted in [3]. Non-disjoint GPSEDFs in
$\mathbb{Z}_{v}$ also provide examples of pairwise shift-invariant protocol
sequences [22].

For the aid of the reader throughout this paper, we end the introductory
section with Figure 1, a diagram indicating how the structures in this paper
are related to each other. If structure $A$ is higher in the diagram than
structure $B$ and there is a line between them, then any example of structure
$A$ is an example of structure $B$.

Figure 1: Diagrams of the classical and non-disjoint external difference
structuresClassical PSEDFClassical SEDFClassical SCEDFClassical
GPSEDFClassical GSEDFClassical MGPSEDFClassical EDFClassical GEDFClassical
MGSEDFNon-disjoint PSEDFNon-disjoint SEDFNon-disjoint GPSEDFNon-
disjointGSEDFNon-disjoint MGPSEDFNon-disjoint MGSEDF

##  2 Background

###  2.1 Definitions and context

For subsets $A,B$ of a group $G$ (written additively), we define the multiset
$\Delta(A,B)=\\{a-b:a\in A,b\in B\\}$. In multiplicative notation we can write
this as $\Delta(A,B)=\\{ab^{-1}:a\in A,b\in B\\}$. (In general we will use
additive notation except in situations where multiplicative notation is more
natural.) For $\lambda\in\mathbb{N}$ and $S\subseteq G$, we will write
$\lambda S$ to denote the multiset comprising $\lambda$ copies of $S$ (except
where this might cause confusion, e.g. in Section 4, where different phrasing
is used).

The concept of classical external difference family was first defined in [13],
motivated by an application to AMD codes:

######  Definition 2.1.

Let $G$ be a group of order $v$ and let $m>1$. A family of disjoint $k$-sets
$\\{A_{1},\ldots,A_{m}\\}$ in $G$ is a classical $(v,m,k,\lambda)$-EDF if the
multiset equation $\bigcup_{i\neq
j}\Delta(A_{i},A_{j})=\lambda(G\setminus\\{0\\})$ holds.

The strong version was first defined in [14], corresponding to a stronger
security model.

######  Definition 2.2.

Let $G$ be a group of order $v$ and let $m>1$. A family of disjoint $k$-sets
$\\{A_{1},\ldots,A_{m}\\}$ in $G$ is a classical $(v,m,k,\lambda)$-SEDF if,
for each $1\leq i\leq m$, the multiset equation $\bigcup_{j\neq
i}\Delta(A_{i},A_{j})=\lambda(G\setminus\\{0\\})$ holds.

######  Example 2.3.

The family of sets $\\{\\{0,1,2\\},\\{3,6,9\\}\\}$ form a classical
$(10,2,3,1)$-SEDF in $\mathbb{Z}_{10}$.

Classical SEDFs have been much studied, with various constructions and non-
existence results established. Currently only one parameter set with $m>2$ is
known, namely $(243,11,22,20)$; this was established independently in [17] and
[7]. The only value of $\lambda$ for which infinite families of constructions
are known is $\lambda=1$ (see [14] and [4]). Cyclotomic constructions are also
known (see [17]). Numerous non-existence results exist (see [8] and [5] for
recent summaries); it is conjectured that no further classical SEDFs with
$m>2$ exist in abelian groups, and this is supported by computational
evidence.

In [14], the generalised versions were introduced:

######  Definition 2.4.

Let $G$ be a group of order $v$ and $m\geq 1$.

  * •

A classical $(v,m;k_{1},\ldots,k_{m};\lambda)$-GEDF is a family of disjoint
sets $A=\\{A_{1},\dots,A_{m}\\}$ in $G$ such that such that $|A_{i}|=k_{i}$
for $1\leq i\leq m$ and the multiset equation $\cup_{i\neq
j}\Delta(A_{i},A_{j})=\lambda(G\setminus\\{0\\})$ holds.

  * •

A classical $(v,m;k_{1},\dots,k_{m};\lambda_{1},\dots,\lambda_{m}$)-GSEDF is a
family of disjoint sets $A=\\{A_{1},\dots,A_{m}\\}$ in $G$ such that for each
$1\leq i\leq m,|A_{i}|=k_{i}$ and the multiset equation $\cup_{j\neq
i}\Delta(A_{i},A_{j})=\lambda_{i}(G\setminus\\{0\\})$ holds.

Classical GSEDFs have been studied in [17] and [10]. The structure of those
partitioning $G$ or $G\setminus\\{0\\}$ is known, and there are some
cyclotomic constructions with $m=2$ or by taking the collections of cyclotomic
classes together with the zero singleton-set. It is known that for $m=3$ a
classical $(v,m;k_{1},k_{2},k_{2};\lambda_{1},\lambda_{2},\lambda_{3})$-GSEDF
does not exist when $k_{1}+k_{2}+k_{3}<v$, and for $k_{1}+k_{2}+k_{3}=v$ the
parameters are very restricted, with either
$\\{k_{1},k_{2},k_{3}\\}=\\{1,\frac{v-1}{2},\frac{v-1}{2}\\}$ (examples known)
or $\sqrt{v}<k_{1}<k_{2}<k_{3}$ (no examples known).

The following non-disjoint analogues of SEDFs were introduced in [5],
motivated by an application to optical orthogonal codes. While still
satisfying extremely restrictive conditions, there is a much richer landscape
of constructions for the non-disjoint versions.

######  Definition 2.5.

Let $G$ be a group of order $v$ and let $m>1$. We say that a family of
$k$-sets $\\{A_{1},\dots,A_{m}\\}$ in $G$ is a non-disjoint
$(v,m,k,\lambda)$-SEDF (Strong External Difference Family) if, for each $1\leq
i\leq m$, the multiset equation $\cup_{j\neq i}\Delta(A_{i},A_{j})=\lambda G$
holds.

######  Definition 2.6.

Let $G$ be a group of order $v$ and let $m>1$. We say that a family of
$k$-sets $\\{A_{1},\dots,A_{m}\\}$ in $G$ is a non-disjoint
$(v,m,k,\lambda)$-PSEDF (Pairwise Strong External Difference Family) if, for
each $1\leq i\neq j\leq m$, the multiset equation $\Delta(A_{i},A_{j})=\lambda
G$ holds.

The following basic results hold ((i) and (ii) are noted in [5]).

######  Proposition 2.7.

  * (i)

A non-disjoint $(v,m,k,\lambda)$-PSEDF is a non-disjoint
$(v,m,k,(m-1)\lambda)$-SEDF.

  * (ii)

A non-disjoint $(v,2,k,\lambda)$-SEDF is a non-disjoint
$(v,2,k,\lambda)$-PSEDF.

  * (iii)

A collection of sets $\\{A_{1},\ldots,A_{m}\\}$ in a group $G$ is a non-
disjoint $(v,m,k,\lambda)$-PSEDF if and only if, for each $1\leq i\neq j\leq
m$, $\\{A_{i},A_{j}\\}$ is a non-disjoint $(v,2,k,\lambda)$-PSEDF.

######  Example 2.8.

The family of sets $\\{\\{0,1,2\\}\\},\\{0,3,6\\}\\}$ form a non-disjoint
$(9,2,3,1)$-PSEDF (and so a non-disjoint $(9,2,3,1)$-SEDF) in
$\mathbb{Z}_{9}$.

In this paper, we introduce the non-disjoint analogue of the classical GSEDF:

######  Definition 2.9.

Let $G$ be a group of order $v$ and let $m\geq 1$. A non-disjoint
$(v,m,k_{1},\dots,k_{m};\lambda_{1},\dots,\lambda_{m})$-GSEDF is a family of
sets, $A=\\{A_{1},\dots,A_{m}\\}$ in $G$ such that for each $1\leq i\leq
m,|A_{i}|=k_{i}$ and the following equation holds:

$\cup_{j\neq i}\Delta(A_{i},A_{j})=\lambda_{i}G$

We present the pairwise version of this structure:

######  Definition 2.10.

Let $G$ be a group of order $v$. We say that a family of sets
$A=\\{A_{1},\dots,A_{m}\\}$ in $G$ is a non-disjoint
$(v,m,k_{1},\dots,k_{m})$-GPSEDF if $|A_{i}|=k_{i}$ ($1\leq i\leq m$) and the
following equation holds for all $1\leq i\neq j\leq m$:

$\Delta(A_{i},A_{j})=\lambda_{i,j}G\text{ where
}\lambda_{i,j}=\frac{k_{i}k_{j}}{v}$

Note that $\lambda_{j,i}=\lambda_{i,j}$.

######  Definition 2.11.

We define the $\lambda$-matrix of a non-disjoint
($v,m,k_{1},\dots,k_{m}$)-GPSEDF to be the $m\times m$ matrix $[a_{ij}]$, with
$a_{ii}=0$ and $a_{ij}=\lambda_{i,j}=\frac{k_{i}k_{j}}{v}$ ($1\leq i,j\leq
m$).

The following result presents a known classical GSEDF construction, and an
analogous new non-disjoint GSEDF construction.

######  Proposition 2.12.

  * (i)

In $\mathbb{Z}_{k_{1}k_{2}+1}$, the sets $A_{1}=\\{0,1,2\ldots,k_{1}-1\\}$ and
$A_{2}=\\{k_{1},2k_{1},\ldots,k_{1}k_{2}\\}$ form a classical
$(k_{1}k_{2}+1,2;k_{1},k_{2};1,1)$-GSEDF.

  * (ii)

In $\mathbb{Z}_{k_{1}k_{2}}$, the sets $B_{1}=\\{0,1,2\ldots,k_{1}-1\\}$ and
$B_{2}=\\{0,k_{1},2k_{1},\ldots,k_{1}(k_{2}-1)\\}$ form a non-disjoint
$(k_{1}k_{2},2;k_{1},k_{2};1,1)$-GSEDF which is a non-disjoint
$(k_{1}k_{2},2,k_{1},k_{2})$-GPSEDF.

###### Proof.

Part (i) is Theorem 4.4 of [10]. For (ii), direct checking shows that
$\Delta(B_{1},B_{2})=\Delta(B_{2},B_{1})=\mathbb{Z}_{k_{1}k_{2}}$. ∎

######  Proposition 2.13.

  * (i)

A non-disjoint $(v,m,k,\lambda)$-SEDF is a non-disjoint
$(v,m;k,\dots,k;\lambda,\dots,\lambda)$-GSEDF (with $m$ $\lambda$s and $m$
$k$s).

  * (ii)

A non-disjoint $(v,m,k,\lambda)$-PSEDF is a non-disjoint
$(v,m,k,\dots,k)$-GPSEDF with $m\times m$ $\lambda$-matrix $M=[a_{ij}]$, where
$a_{ii}=0$ and $a_{ij}=\frac{k^{2}}{v}$ for $i\neq j$.

  * (iii)

A non-disjoint $(v,2;k_{1},k_{2};\lambda_{1},\lambda_{2})$-GSEDF is a non-
disjoint $(v,2,k_{1},k_{2})$-GPSEDF. (Here $\lambda_{1}=\lambda_{2}$).

  * (iv)

A non-disjoint $(v,m,k_{1},\dots,k_{m})$-GPSEDF is a non-disjoint
$(v,m,k_{1},\dots,k_{m};\sum_{j\neq 1}\lambda_{1,j},\dots,\sum_{j\neq
m}\lambda_{m,j})$-GSEDF.

  * (v)

A collection of sets $\\{A_{1},\ldots,A_{m}\\}$ in a group $G$ is a non-
disjoint $(v,m,k_{1},\ldots,k_{m})$-GPSEDF if and only if $\\{A_{i},A_{j}\\}$
is a non-disjoint $(v,2,k_{i},k_{j})$-GPSEDF for each $i\neq j$.

######  Example 2.14.

In $\mathbb{Z}_{12}$, the sets $\\{0,1,2,3,4,5\\}$, $\\{0,1,2,6,7,8\\}$ and
$\\{0,1,3,4,6,7,9,10\\}$ form a non-disjoint $(12,3,6,6,8)$-GPSEDF with
$\lambda_{1,2}=3=\lambda_{2,1},\lambda_{2,3}=4=\lambda_{3,2},\lambda_{1,3}=4=\lambda_{3,1}$.
Hence these sets also form a non-disjoint $(12,3;6,6,8;7,7,8)$-GSEDF. Note
this is in contrast to the situation with classical GSEDFs where
$|\\{k_{1},k_{2},k_{3}\\}|=2$ implies
$\\{k_{1},k_{2},k_{3}\\}=\\{1,\frac{v-1}{2},\frac{v-1}{2}$.)

######  Example 2.15.

In $\mathbb{Z}_{30}$, the sets
$\\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17\\}$,
$\\{0,1,2,6,7,8,12,13,14,18,19,20,24,25,26\\}$ and
$\\{0,1,3,4,6,7,9,10,12,13,15,16,18,19,21,22,24,25,27,28\\}$ form a non-
disjoint $(30,3,18,15,20)$-GPSEDF with
$\lambda_{1,2}=9=\lambda_{2,1},\lambda_{2,3}=10=\lambda_{3,2},\lambda_{1,3}=12=\lambda_{3,1}$.
Hence these sets also form a non-disjoint $(30,3;18,15,20;21,19,22)$-GSEDF.
Note that no examples of classical GSEDFs are known with all set-sizes
different.

We introduce a multiset version of these structures:

######  Definition 2.16.

Let $G$ be a group of order $v$. Let $m>1$. We say a family of multisets
$A=\\{A_{1},\dots,A_{m}\\}$ in $G$ is a:

  * (i)

non-disjoint ($v,m,k_{1},\dots,k_{m},\lambda_{1},\dots,\lambda_{m}$)-MGSEDF
(multiset generalised strong external difference family) if for each $1\leq
i\leq m$, $|A_{i}|=k_{i}$, and the following equation holds:

$\cup_{j\neq i}\Delta(A_{i},A_{j})=\lambda_{i}G$

  * (ii)

non-disjoint ($v,m,k_{1},\dots,k_{m}$)-MGPSEDF (multiset generalised pairwise
strong external difference family) if $|A_{i}|=k_{i}$ ($1\leq i\leq m$) and
the following equation holds for all $1\leq i\neq j\leq m$:

$\Delta(A_{i},A_{j})=\lambda_{i,j}G\text{ where
}\lambda_{i,j}=\frac{k_{i}k_{j}}{v}$

Since any set without repeated elements may be viewed as a multiset, this
definition includes the original versions (eg a non-disjoint GSEDF is an
example of a non-disjoint MGSEDF).

In this paper, we will write a multiset $M$ as
$\\{a_{1},b_{1};a_{2},b_{2};\dots;a_{n},b_{n}\\}$, where this indicates that
$M$ comprises $b_{1}$ occurrences of $a_{1}$, $b_{2}$ occurrences of $a_{2}$
and so on.

######  Example 2.17.

The multisets

  * •

$\\{0,2;1,2;2,2;3,2;4,2;5,2\\}$,

  * •

$\\{0,3;1,3;2,3;3,2;4,2;5,2;6,3;7,3;8,3;9,2;10,2;11,2\\}$

  * •

$\\{0,4;1,5;3,4;4,5;6,4;7,5;9,4;10,5\\}$

form a non-disjoint ($12,3,12,30,36$)-MGPSEDF in $\mathbb{Z}_{12}$. Here
$\lambda_{1,2}=30=\lambda_{2,1}$, $\lambda_{1,3}=36=\lambda_{3,1}$ and
$\lambda_{2,3}=90=\lambda_{3,2}$

Finally, we define classical versions of these new concepts:

######  Definition 2.18.

  * (i)

A _classical_ $(v,m,k,\lambda)$-PSEDF is a family of disjoint $k$-sets
$\\{A_{1},\dots,A_{m}\\}$ in $G$ such that, for each $1\leq i\neq j\leq m$,
the multiset equation $\Delta(A_{i},A_{j})=\lambda(G\setminus\\{0\\})$ holds.

  * (ii)

A _classical_ $(v,m,k_{1},\dots,k_{m})$-GPSEDF is a family of disjoint
$k$-sets $A=\\{A_{1},\dots,A_{m}\\}$ in $G$ such that $|A_{i}|=k_{i}$ ($1\leq
i\leq m)$ and the following equation holds for all $1\leq i\neq j\leq m$:

$\Delta(A_{i},A_{j})=\lambda_{i,j}(G\setminus\\{0\\})\text{ where
}\lambda_{i,j}=\frac{k_{i}k_{j}}{v-1}$

  * (iii)

The _classical_ MGSEDF and MGPSEDF are defined in the same way as the
classical GSEDF and GPSEDF respectively, except that
$A=\\{A_{1},\ldots,A_{m}\\}$ is now a family of _multisets_ rather than a
family of sets in each case.

######  Example 2.19.

In $\mathbb{Z}_{13}$, the multisets

$\\{1,2;3,2;4,2;9,2;10,2;12,2\\},\\{2,3;5,3;6,3;7,3;8,3;11,3\\}$

form a classical ($13,2,12,18$)-MGPSEDF and hence also a classical
($13,2,12,18$)-MGSEDF with $\lambda_{1,2}=18=\lambda_{2,1}$.

In [16], the following combinatorial object is introduced.

######  Definition 2.20.

Let $G$ be an abelian group of order $v$. A (classical)
$(v,m,k;\lambda)$-strong circular external difference family (or (classical))
$(v,m,k;\lambda)$-SCEDF) is a set of $m$ disjoint $k$-subsets,
$A=\\{A_{0},\ldots,A_{m-1}\\}$ of $G$, such that the following multiset
equation holds for every $j$ $(0\leq j\leq m-1)$:

$\Delta(A_{j+1\mod m},A_{j})=\lambda(G\setminus\\{0\\})$

Clearly any classical $(v,2,k,\lambda)$-SEDF is an example of a classical
$(v,2,k;\lambda)$-SCEDF. The following structural theorem is presented in
[15].

######  Theorem 2.21.

Let $G$ be an abelian group of order $v$. A set of $m$ disjoint $k$-subsets of
$G$, say $A=\\{A_{0},\ldots,A_{m-1}\\}$ is a classical $(v,m,k;\lambda)$-SCEDF
if and only if $\\{A_{i},A_{i+1\mod m}\\}$ is a classical
$(v,2,k,\lambda)$-SEDF for all $0\leq i\leq m-1$.

We observe that the existence of a classical $(v,m,k,\lambda)$-PSEDF implies
the existence of a classical $(v,m,k;\lambda)$-SCEDF. However, it is proved in
Theorem 6 of [18] that no classical abelian $(v,m,k;\lambda)$-SCEDF can exist
for $m\geq 3$. This leads to the following non-existence result for classical
PSEDFs:

######  Theorem 2.22.

In an abelian group of order $v$, there does not exist a classical
$(v,m,l,\lambda)$-PSEDF with $m\geq 3$.

The next result relates the multiset/non-multiset structures.

######  Theorem 2.23.

Let $A=\\{A_{1},\dots,A_{m}\\}$ be a family of sets in a group $G$.

  * (i)

$A$ is a non-disjoint GSEDF $\Leftrightarrow\\{A_{i},\cup_{j\neq i}A_{j}\\}$
is a non-disjoint MGPSEDF for all $1\leq i\leq m$.

  * (ii)

$A$ is a classical GSEDF $\Leftrightarrow\\{A_{i},\cup_{j\neq i}A_{j}\\}$ is a
classical GSEDF for all $1\leq i\leq m$

###### Proof.

For any $1\leq i\leq m$, observe that the multiset union $\uplus_{j\neq
i}\Delta(A_{i},A_{j})=\Delta(A_{i},\uplus_{j\neq i}A_{j})$. For (ii), note
that $\cup_{j\neq i}A_{j}$ is a set rather than a multiset by disjointness. ∎

###  2.2 Basic structural results

In this section, we present some useful structural results which will be used
in the paper.

We will use the following notation: for a set $S$, $\overline{S}=G\setminus S$
will denote the complement of $S$ in $G$. For $g\in G$ and $S\subseteq G$, we
denote $g+S=\\{g+s:s\in S\\}$. For $A,B\subseteq G$, $A\uplus B$ denotes the
multiset union of $A$ and $B$.

The next theorem allows us to obtain new examples from old in various natural
ways.

######  Theorem 2.24.

Let $A=\\{A_{1},\ldots,A_{m}\\}$ be a non-disjoint
$(v,m,k_{1},k_{2},\ldots,k_{m})$-GPSEDF in a group $G$ of order $v$, written
additively (we do not assume $G$ is abelian). Then:

  * (i)

For $1\leq j\leq m$, $\\{A_{1},A_{2},\ldots,\overline{A_{j}},\ldots,A_{m}\\}$
is a non-disjoint $(v,m,k_{1},k_{2},\ldots,v-k_{j},\ldots,k_{m})$-GPSEDF.

  * (ii)

$\\{\overline{A_{1}},\overline{A_{2}},\dots,\overline{A_{m}}\\}$ is a non-
disjoint $(v,m,v-k_{1},v-k_{2},\dots,v-k_{m})$-GPSEDF in $G$.

  * (iii)

For $g\in G$, $\\{A_{1},\dots,A_{m-1},g+A_{m}\\}$ is a non-disjoint
$(v,m,k_{1},k_{2},\ldots,k_{m})$-GPSEDF.

  * (iv)

Let $B=\\{A_{1},\dots,A_{m-1},B_{m}\\}$ be a non-disjoint
$(v,m,k_{1},\dots,k_{m-1},l_{m})$-MGPSEDF in $G$ (i.e. $B$ has the same sets
as $A$ except for one set). Then

$C=\\{A_{1},A_{2},\dots,A_{m-1},A_{m}\uplus B_{m}\\}$

is a non-disjoint $(v,m,k_{1},\dots,k_{m-1},k_{m}+l_{m})$-MGPSEDF. If $A$ and
$B$ are non-disjoint GPSEDFs and $A_{m}$ and $B_{m}$ are disjoint sets, then
$C$ is a non-disjoint GPSEDF.

  * (v)

Let $g_{1},\dots,g_{n}\in G$ for some $n\in\mathbb{N}$. Then
$\\{A_{1},\dots,A_{m-1},\uplus_{i=1}^{n}(g_{i}+A_{m}))$ is a non-disjoint
$(v,m,k_{1},\dots,k_{m-1},nk_{m})$-MGPSEDF. If all the sets
$\\{g_{i}+A_{m}\\}$ for $1\leq i\leq n$ are pairwise disjoint, then this
construction is in fact a non-disjoint GPSEDF.

###### Proof.

(i) Let $i\neq j$, $1\leq i\leq m$. Then

$\displaystyle\Delta(\overline{A_{j}},A_{i})$ $\displaystyle=\Delta(G\setminus
A_{j},A_{i})$ $\displaystyle=\\{g-b:g\in G,g\notin A_{j},b\in A_{i}\\}$
$\displaystyle=\\{g-b:g\in G,b\in A_{i}\\}\setminus\\{g-b:g\in A_{j},b\in
A_{i}\\}$ $\displaystyle=|A_{i}|G\setminus\lambda_{j,i}G$
$\displaystyle=(k_{i}-\lambda_{j,i})G$

By a similar argmuent,
$\Delta(A_{i},\overline{A_{j}})=(k_{i}-\lambda_{i,j})G$. All other external
differences are the same as in $A$. The result follows.
(ii) This follows by repeating the method from (i) $m$ times for each set in
$A$.
(iii) Let $g\in G$ and let $1\leq j\leq m-1$. Consider

$\displaystyle\Delta(g+A_{m},A_{j})$ $\displaystyle=\\{g+a-c:a\in A_{m},c\in
A_{j}\\}$ $\displaystyle=g+\\{a-c:a\in A_{m},c\in A_{j}\\}$
$\displaystyle=g+\Delta(A_{m},A_{j})$ $\displaystyle=\lambda_{m,j}G$

By a similar argument, $\Delta(A_{j},g+A_{m})=\\{c+(-a-g):c\in A_{j},a\in
A_{m}\\}=\Delta(A_{j},A_{m})+(-g)=\lambda_{j,m}G$ and the result follows.
(iv) Let $1\leq i\leq m-1$. We show that $\Delta(A_{i},A_{m}\uplus
B_{m})=\lambda_{i,m}$ for some $\lambda_{i,m}\in\mathbb{N}$.

$\displaystyle\Delta(A_{i},A_{m}\uplus B_{m})$
$\displaystyle=\\{a_{i}-a_{m}:a_{i}\in A_{i},a_{m}\in A_{m}\uplus B_{m}\\}$
$\displaystyle=\\{a_{i}-a_{m}:a_{i}\in A_{i},a_{m}\in
A_{m}\\}\uplus\\{a_{i}-b_{m}:a_{i}\in A_{i},a_{m}\in B_{m}\\}$
$\displaystyle=\Delta(A_{i},A_{m})\uplus\Delta(A_{i},B_{m})$
$\displaystyle=\lambda_{i,m}G+\mu_{i,m}G\quad\text{for some
}\lambda_{i,m},\mu_{i,m}\in\mathbb{N}$
$\displaystyle=(\lambda_{i,m}+\mu_{i,m})G$

By a similar argument, $\Delta(A_{m}\uplus
B_{m},A_{i})=(\lambda_{m,i}+\mu_{m,i})G$. Since $|A_{m}\uplus
B_{m}|=|A_{m}|+|B_{m}|$, the result follows. If $A$ and $B$ are non-disjoint
GPSEDFs and $A_{m}$ and $B_{m}$ are disjoint then $A_{m}\uplus B_{m}=A_{m}\cup
B_{m}$ and so $C$ is also a non-disjoint GPSEDF.
(v) Applying parts (iii) and (iv),
$\\{A_{1},\dots,A_{m-1},\uplus_{i=1}^{n}(g_{i}+A_{m})\\}$ is a non-disjoint
MGSEDF, which is a non-disjoint GPSEDF if $A_{m}$ and $B_{m}$ are disjoint. ∎

######  Theorem 2.25.

Let $G$ be a finite abelian group and let $H$ be a subgroup of $G$.
If $A=\\{a_{1},\ldots,a_{r}\\}$ and $B=\\{b_{1},\ldots,b_{s}\\}$ form a non-
disjoint $(|G/H|,2,r,s)$-GPSEDF in $G/H$, then
$A^{\prime}=\cup_{i=1}^{r}(a_{i}+H)$ and $B^{\prime}=\cup_{j=1}^{s}(b_{j}+H)$
form a non-disjoint $(|G|,2,r|H|,s|H|)$-GPSEDF in $G$.

###### Proof.

Let $1\leq i\leq r,1\leq j\leq s$. As a multiset,
$\Delta(a_{i}+H,b_{j}+H)=|H|((a_{i}-b_{j})+H)$. So
$\Delta(A^{\prime},B^{\prime})=\cup_{i=1}^{r}\cup_{j=1}^{s}\Delta(a_{i}+H,b_{j}+H)=|H|\cup_{i=1}^{r}\cup_{j=1}^{s}((a_{i}-b_{j})+H)$.

If $\\{A,B\\}$ is a non-disjoint GPSEDF in $G/H$ then the multiset
$\cup_{i=1}^{r}\cup_{j=1}^{s}(a_{i}-b_{j})=\lambda(G/H)$ where
$\lambda=\frac{rs}{|G/H|}$ and we have that $\Delta(A^{\prime},B^{\prime})$
comprises $\lambda|H|$ copies of each $x+H$ ($x\in G/H$), i.e. $\lambda|H|$
copies of $G$. ∎

A key technique in this paper is the use of binary sequences. We briefly
outline the relationship between sets and sequences. The binary sequence case
is well-known and summarized in our context in [5]; we give it here for
completeness, and also extend this to multisets.

######  Definition 2.26.

  * (i)

Let $A$ be a $k$-subset of $\mathbb{Z}_{v}$ ($v\in\mathbb{N}$). We associate
to $A$ a binary sequence $X=(x_{t})_{t=0}^{v-1}$ of weight $k$, where
$x_{t}=1$ if $t\in A$ and $x_{t}=0$ if $t\notin A$.

  * (ii)

Let $X$ be a binary sequence $(x_{t})_{t=0}^{v-1}$ of weight $k$. We associate
to $X$ a $k$-subset $A$ of $\mathbb{Z}_{v}$, where $t\in A\Leftrightarrow
x_{t}=1$.

  * (iii)

Let $A$ be a multiset of elements of $\mathbb{Z}_{v}$ ($v\in\mathbb{N}$). We
associate to $A$ a sequence $X=(x_{t})_{t=0}^{v-1}$ of non-negative integers,
where $x_{t}$ equals the number of occurrences of $t$ in $A$.

  * (iv)

Let $X=(x_{t})_{t=0}^{v-1}$ be sequence of non-negative integers. We associate
to $X$ a multiset $A$ of elements of $\mathbb{Z}_{v}$, where $t$ occurs $i$
times in $A\Leftrightarrow x_{t}=i$.

The following result was given in [5].

######  Theorem 2.27.

Let $X_{A}=(x_{t})_{t=0}^{v-1}$ and $X_{B}=(y_{t})_{t=0}^{v-1}$ (with indices
taken modulo $v$) be two binary sequences corresponding to subsets $A$ and $B$
in $\mathbb{Z}_{v}$. Then:

  * (i)

For $\delta\in\\{0,\dots,v-1\\}$, $\sum_{t=0}^{v-1}x_{t}y_{t+\delta}$ equals
the number of occurrences of $\delta$ in $\Delta(B,A)$.

  * (ii)

$\sum_{t=0}^{v-1}x_{t}y_{t+\delta}=\lambda$ for all $0\leq\delta\leq
v-1\Leftrightarrow\Delta(B,A)=\lambda\mathbb{Z}_{v}$.

In fact we can generalize this to the multiset case:

######  Theorem 2.28.

Let $X_{A}=(x_{i})_{i=0}^{v-1}$, $X_{B}=(y_{i})_{i=0}^{v-1}$,
$(x_{i},y_{i}\in\mathbb{N}\cup\\{0\\})$, with indices taken modulo v, be the
sequences corresponding to multisets $A$ and $B$ of elements of
$\mathbb{Z}_{v}$. Then:

  * (i)

For $\delta\in\\{0,\dots,v-1\\}$, $\sum_{t=0}^{v-1}x_{t}y_{t+\delta}$ equals
the number of occurrences of $\delta$ in $\Delta(B,A)$.

  * (ii)

$\sum_{t=0}^{v-1}x_{t}y_{t+\delta}=\lambda$ for all $0\leq\delta\leq v-1$ if
and only if $\Delta(B,A)=\lambda\mathbb{Z}_{n}$.

###### Proof.

We prove (i); (ii) is then immediate. For fixed $\delta,t\in\mathbb{Z}_{v}$,
$x_{t}y_{t+\delta}$ is the product of the number of occurrences of $t$ in $A$
and the number of occurrences of $t+\delta$ in $B$. This is the number of
occurrences of $\delta$ as a difference between all the $(t+\delta)$s in $B$
and $t$s in $A$. Hence for a given $\delta$, the number of occurrences of
$\delta$ in $\Delta(B,A)$ is the sum of this quantity over all $t$ in the
sequence, as required. ∎

##  3 New results on non-disjoint SEDFs and GSEDFs using sequence methods

In [5], two main constructions were presented: one for a $2$-set non-disjoint
PSEDF with any value of $\lambda$ and another for a non-disjoint PSEDF with
any number of sets. Both were obtained using sequence methods. We summarize
the statements of these below.

######  Theorem 3.1.

  * (i)

For any $a,r\in\mathbb{N}$, there exists a non-disjoint
$(ra^{2},2,ra,r)$-PSEDF in $\mathbb{Z}_{ra^{2}}$ and hence a non-disjoint
$(ra^{2},2,ra,r)$-SEDF in $\mathbb{Z}_{ra^{2}}$.

  * (ii)

Let $N>1$. There exists a non-disjoint $(2^{N},N,2^{N-1},2^{N-2})$-PSEDF in
$\mathbb{Z}_{2^{N}}$ and hence a non-disjoint
$(2^{N},N,2^{N-1},(N-1)2^{N-2})$-SEDF in $\mathbb{Z}_{2^{N}}$.

The following key theorem generalizes these constructions, and yields many new
non-disjoint GPSEDFs. We will later discuss which non-disjoint PSEDFs are
obtainable from the theorem.

We use the following notation from [12] for a binary sequence
$X=(x_{t})_{t=0}^{v-1}$: a contiguous subsequence of length $r$ in $X$ is
called a _substring_ of length $r$; a substring consisting entirely of $0$’s
(not preceded or succeeded by the same symbol) is a _gap_ , and an analogous
substring of $1$’s is a _run_. We call $X+s=(x_{i+s})_{i=0}^{v-1}$ a (cyclic)
shift of $X$ by $s$ places (indices taken modulo $v$).

######  Theorem 3.2.

Let $m\geq 2$. Let $(a_{0},a_{1},\dots,a_{m})$ be a sequence of positive
integers such that for all $0\leq i\leq m-1$, $a_{i}=b_{i+1}a_{i+1}$ for some
$b_{i+1}(\geq 2)\in\mathbb{Z}$. Then, for all possible $1\leq\eta_{i}\leq
b_{i}-1$ there exists a non-disjoint

$(a_{0},m,\eta_{1}a_{1},\eta_{2}a_{2}\frac{a_{0}}{a_{1}},\eta_{3}a_{3}\frac{a_{0}}{a_{2}},\dots,\eta_{m}a_{m}\frac{a_{0}}{a_{m-1}})-\mbox{GPSEDF
in }\mathbb{Z}_{a_{0}}.$

The $\lambda$-matrix of this non-disjoint GPSEDF is $[a_{ij}]_{m\times m}$,
where $a_{ij}=0$ if $i=j$ and
$a_{ij}=\lambda_{i,j}=\frac{a_{0}\eta_{i}a_{i}\eta_{j}a_{j}}{a_{i-1}a_{j-1}}$
otherwise.

###### Proof.

Let $(a_{0},a_{1},\dots,a_{m})$ ($m\geq 2$) be a sequence of positive integers
such that for all $0\leq i\leq m-1$, $a_{i}=b_{i+1}a_{i+1}$ for some
$b_{i+1}(\geq 2)\in\mathbb{Z}$. Then fix $1\leq\eta_{i}\leq b_{i}-1$ for all
$1\leq i\leq m$.

Firstly, we note that $a_{j}|a_{i}$ for all $i\leq j$ since
$a_{j}|a_{j-1}|a_{j-2}\dots|a_{i}$.

Define $X_{i}=(x_{t})_{t=0}^{a_{0}-1}$ for all $i=1,\dots,m$, where:

$x_{t}=\begin{cases}1,&0\leq t\leq\eta_{i}a_{i}-1\\\ 0,&\eta_{i}a_{i}\leq
t\leq a_{i}b_{i}-1=a_{i-1}-1\\\ x_{t-a_{i}b_{i}},&a_{i}b_{i}\leq t\leq
a_{0}-1\quad(a_{i}b_{i}=a_{i-1})\end{cases}$

So we obtain:

$X_{i}=\overbrace{\overbrace{\underbrace{\underbrace{1\dots
1}_{a_{i}}\underbrace{1\dots 1}_{a_{i}}\dots\underbrace{1\dots
1}_{a_{i}}}_{\eta_{i}\text{copies}}\underbrace{\underbrace{0\dots
0}_{a_{i}}\underbrace{0\dots 0}_{a_{i}}\dots\underbrace{0\dots
0}_{a_{i}}}_{(b_{i}-\eta_{i})\text{copies}}}^{\text{length
}a_{i}b_{i}=a_{i-1}}\dots\overbrace{\underbrace{\underbrace{1\dots
1}_{a_{i}}\underbrace{1\dots 1}_{a_{i}}\dots\underbrace{1\dots
1}_{a_{i}}}_{\eta_{i}\text{copies}}\underbrace{\underbrace{0\dots
0}_{a_{i}}\underbrace{0\dots 0}_{a_{i}}\dots\underbrace{0\dots
0}_{a_{i}}}_{(b_{i}-\eta_{i})\text{copies}}}^{\text{length
}a_{i}b_{i}=a_{i-1}}}^{\frac{a_{0}}{a_{i-1}}\text{ repeats}}$

For all $1\leq i\leq m$, we let $A_{i}$ be the set in $\mathbb{Z}_{a_{0}}$
corresponding to $X_{i}$ and we let $A=\\{A_{1},A_{2},\dots,A_{m}\\}$.

Since $X_{i}$ repeats itself every $a_{i-1}$ entry and the first substring of
$X_{i}$ with length $a_{i-1}$ has weight $\eta_{i}a_{i}$ so does every other
length $a_{i-1}$ substring of $X_{i}$. So any substring of length $ca_{i-1}$,
($c\in\mathbb{N}$) has weight $c\eta_{i}a_{i}$. In particular, $X_{i}$ has
weight $\eta_{i}a_{i}\frac{a_{0}}{a_{i-1}}$ and so
$|A_{i}|=\eta_{i}a_{i}\frac{a_{0}}{a_{i-1}}$.

Let $i,j\in\\{1,\dots,m\\}$, $i<j$ and $\delta\in\\{0,\dots,a_{0}-1\\}$. We
let $X_{i}=(x_{t})_{t=0}^{a_{0}-1}$ and $X_{j}=(y_{t})_{t=0}^{a_{0}-1}$. We
consider the number of occurrences of $\delta$ in $\Delta(A_{i},A_{j})$
($=\Delta(A_{j},A_{i})$ since $\mathbb{Z}_{a_{0}}$ is abelian), which by
Theorem 2.27 is equal to:

$\displaystyle\sum_{t=0}^{a_{0}-1}x_{t}y_{t+\delta}$
$\displaystyle=\frac{a_{0}}{a_{i-1}}\sum_{t=0}^{a_{i-1}-1}x_{t}y_{t+\delta}$
($X_{i}$ and $X_{j}$ repeat every $a_{i-1}$ entry)
$\displaystyle=\frac{a_{0}}{a_{i-1}}\sum_{t=0}^{a_{i}\eta_{i}-1}y_{t+\delta}$
($x_{t}=1$ for $0\leq t\leq\eta_{i}a_{i}-1$, $x_{t}=0$ for $\eta_{i}a_{i}\leq
t\leq a_{i-1}$)
$\displaystyle=\frac{a_{0}}{a_{i-1}}\frac{a_{i}\eta_{i}}{a_{j-1}}\sum_{t=0}^{a_{j-1}-1}y_{t+\delta}$
($X_{j}$ repeats every $a_{j-1}$ entry, which divides $a_{i}\eta_{i}$)
$\displaystyle=\frac{a_{0}a_{i}\eta_{i}a_{j}\eta_{j}}{a_{i-1}a_{j-1}}$ (weight
of $a_{j-1}$ substring of $X_{j}$)

This is true for all $\delta\in\\{0,\dots,a_{0}-1\\}$ so
$\Delta(A_{i},A_{j})=\Delta(A_{j},A_{i})=\frac{a_{0}a_{i}\eta_{i}a_{j}\eta_{j}}{a_{i-1}a_{j-1}}\mathbb{Z}_{a_{0}}$.
Hence
$\Delta(A_{i},A_{j})=\frac{a_{0}a_{i}\eta_{i}a_{j}\eta_{j}}{a_{i-1}a_{j-1}}\mathbb{Z}_{a_{0}}$
for all $1\leq i\neq j\leq m$, and thus $A=\\{A_{1},\dots,A_{m}\\}$ forms a
non-disjoint
($a_{0},m,\eta_{1}a_{1},\eta_{2}a_{2}\frac{a_{0}}{a_{1}},\eta_{3}a_{3}\frac{a_{0}}{a_{2}},\dots,\eta_{m}a_{m}\frac{a_{0}}{a_{m-1}}$)-GPSEDF
with $\lambda$-matrix $[a_{ij}]_{m\times m}$, where $a_{ii}=0$ if $i=j$ and
$a_{ij}=\lambda_{i,j}=\frac{a_{0}\eta_{i}a_{i}\eta_{j}a_{j}}{a_{i-1}a_{j-1}}$
otherwise. ∎

We now present an equivalent form of this construction, which better shows the
achievable parameters.

######  Corollary 3.3.

Let $m\geq 2$. Given any $(c_{0},c_{1},\ldots,c_{m})$ with
$c_{0}\ldots,c_{m-1}(\geq 2)\in\mathbb{Z}$ and $c_{m}\in\mathbb{N}$, and any
$1\leq d_{i}\leq c_{i-1}-1$ ($1\leq i\leq m$), there exists a non-disjoint

$(v,m,d_{1}\frac{v}{c_{0}},d_{2}\frac{v}{c_{1}},\dots,d_{m}\frac{v}{c_{m-1}})-\mbox{GPSEDF}$

in $\mathbb{Z}_{v}$, where $v=c_{0}c_{1}\dots c_{m}$.

###### Proof.

In Theorem 3.2, we have $a_{i}=c_{i}c_{i+1}\dots c_{m}$ for all $0\leq i\leq
m$, where $b_{t+1}=c_{t}$ for $0\leq t\leq m-1$ and $a_{m}=c_{m}$. Note that
$c_{0}\ldots c_{i-1}=\frac{a_{0}}{a_{i}}$ and $c_{i+1}\ldots c_{m}=a_{i+1}$. ∎

We now consider the circumstances under which Theorem 3.2 yields a non-
disjoint PSEDF, using Corollary 3.3. This occurs when all the set sizes are
the same, i.e. when $d_{i}\frac{v}{c_{i-1}}=d_{j}\frac{v}{c_{j-1}}$ for all
$1\leq i,j\leq m$.

######  Theorem 3.4.

Let $m\geq 2$ and let $(d_{1},\dots,d_{m}),(c_{0},\dots,c_{m})$ be sequences
of not necessarily distinct natural numbers such that
$\frac{d_{i}}{c_{i-1}}=z$ for all $1\leq i\leq m$, for some $z\in\mathbb{Q}$
with $0<z<1$. (In other words, take $m$ expressions for $z$ as a fraction).
Then there exists a non-disjoint ($c_{0}\dots c_{m},m,c_{0}\dots
c_{m}z,c_{0}\dots c_{m}z^{2}$)-PSEDF in $\mathbb{Z}_{c_{0}\dots c_{m}}$.

Note the condition $0<z<1$ is necessary since Corollary 3.3 requires that
$d_{i}<c_{i-1}$ for all $1\leq i\leq m$.

Observe that Theorem 3.1(i) is the special case of Theorem 3.4 with
$c_{0}=c_{1}=a$, $c_{2}=r$ and $d_{1}=d_{2}=1$; while Theorem 3.1(ii) is the
special case of Theorem 3.4 with $c_{0}=c_{1}=\cdots=c_{N-1}=2$, $c_{N}=1$ and
$d_{1}=d_{2}=\cdots d_{N}=1$.

We next present particular infinite families of non-disjoint PSEDFs arising
from this construction.

######  Corollary 3.5.

  * (i)

Let $z\in\mathbb{Q}$, $0<z<1$, and let $z=\frac{a}{b}$ for some
$a,b\in\mathbb{N}$. Let $v=b^{m}f_{0}\dots f_{m}$, where
$f_{0},\dots,f_{m}\in\mathbb{N}$ and $m\geq 2$. Then there exists a non-
disjoint ($v,m,vz,vz^{2}$)-PSEDF in $\mathbb{Z}_{v}$.

  * (ii)

Let $v=b^{m}f$, where $f\in\mathbb{N}$ and $b,m\in\mathbb{Z}_{\geq 2}$. Let
$1\leq a<b$, $a,b\in\mathbb{N}$. Then there exists a non-disjoint
($b^{m}f,m,ab^{m-1}f,a^{2}b^{m-2}f$)-PSEDF in $\mathbb{Z}_{b^{m}f}$.

###### Proof.

  * (i)

Let $v=b^{m}f_{0}\dots f_{m}$ and $z=\frac{a}{b}$ as above. We define the
sequences $(d_{1},\dots,d_{m})=(af_{0},af_{1},\dots,af_{m-1})$ and
$(c_{0},\dots,c_{m})=(bf_{0},bf_{1},\dots,bf_{m-1},f_{m})$. We see that
$\frac{d_{i}}{c_{i-1}}=\frac{af_{i-1}}{bf_{i-1}}=\frac{a}{b}=z$ for all $1\leq
i\leq m$. So Theorem 3.4 implies the existence of a non-disjoint ($c_{0}\dots
c_{m},m,c_{0}\dots c_{m}z,c_{0}\dots c_{m}z^{2}$)-PSEDF. We note that
$c_{0}\dots c_{m}=b^{m}f_{0}\dots f_{m}=v$, so a non-disjoint
($v,m,vz,vz^{2}$)-PSEDF exists in $\mathbb{Z}_{v}$ as required.

  * (ii)

$f=f\cdot 1^{m}$ so we can take $f_{0}=f$, $f_{1},\dots,f_{m}=1$ and
$z=\frac{a}{b}$ and apply part (i).

∎

######  Corollary 3.6.

  * (i)

Let $S>1$, $N>2$. There exists a non-disjoint ($S^{N}$, $N$, $S^{N-1}$,
$S^{N-2}$)-PSEDF in $\mathbb{Z}_{S^{N}}$ and hence a non-disjoint
($S^{N},N,S^{N-1},(N-1)S^{N-2}$)-SEDF.

  * (ii)

Let $x,y\in\mathbb{N}$, $x<y$, then there exists a non-disjoint
($y^{2},2,xy,x^{2}$)-PSEDF in $\mathbb{Z}_{y^{2}}$ and hence a a non-disjoint
($y^{2},2,xy,x^{2}$)-SEDF.

###### Proof.

  * (i)

Take $b=S$, $m=N$, $a=1$ and $f=1$ in Corollary 3.5(ii).

  * (ii)

Take $b=y$, $m=2$, $a=x$ and $f=1$ in Corollary 3.5(ii) (note $a<b$).

∎

Next, we present a new 2-set construction for non-disjoint PSEDFs and GPSEDFs,
which produces some examples which are not obtainable from our previous
constructions. The new construction uses a ‘modular arithmetic’ viewpoint, and
involves less repetition of blocks in the sequences.

######  Theorem 3.7.

Let $v=ab$ for some $a,b\in\mathbb{N}$. For any $1\leq k_{1}\leq b-1$ and
$1\leq k_{2}\leq a-1$, there exists a non-disjoint
$(v,2,k_{1}a,k_{2}b)$-GPSEDF in $\mathbb{Z}_{v}$.

###### Proof.

Let $v=ab$ for some $a,b\in\mathbb{N}$ and fix $1\leq k_{1}\leq b-1$, $1\leq
k_{2}\leq a-1$. Let $R=\\{r_{i,j}:r_{i,j}\in\mathbb{Z},0\leq r_{i,j}\leq
a-1\,(0\leq i\leq b-1,0\leq j\leq k_{2}-1)\\}$ be a set with the property that
$j_{1}\neq j_{2}\Rightarrow r_{i,j_{1}}\neq r_{i,j_{2}}$. Let
$S=\\{s_{i}:0\leq s_{i}\leq b-1\,(0\leq i\leq k_{1}-1)\\}$ be a set of $k_{1}$
distinct integers.

We next define two binary sequences of length $v$. Let $X=(x_{t})_{t=0}^{v-1}$
and $Y=(y_{t})_{t=0}^{v-1}$, where:

$x_{t}=\begin{cases}1,&jb+s_{i}\quad(0\leq j\leq a-1,0\leq i\leq k_{1}-1)\\\
0,&\text{otherwise}\end{cases}$

$y_{t}=\begin{cases}1,&r_{i,j}b+i\quad(0\leq i\leq b-1,0\leq j\leq k_{2}-1)\\\
0,&\text{otherwise}\end{cases}$

To see that the values $r_{i,j}b+i$ (which lie in the range from $0$ to
$ab-1$) are distinct: there is no repetition for fixed $i$ by choice of
$r_{i,j}$, and no repetition between distinct $i$ as each fixed $i$
corresponds to a different equivalence class mod $b$.

Denote by $A$ the $ak_{1}$-subset of $\mathbb{Z}_{v}$ corresponding to $X$,
and by $B$ the $bk_{2}$-subset of $\mathbb{Z}_{v}$ corresponding to $Y$. Here
$A$ comprises all the elements in $\mathbb{Z}_{v}$, which are in the
congruence classes of $s_{0},\dots,s_{k_{1}-1}$ modulo $b$, and $B$ comprises
$k_{2}$ elements in each congruence class modulo $b$.

Let $\delta\in\mathbb{Z}_{v}$. By Theorem 2.27, the number of occurrences of
$\delta$ in $\Delta(A,B)$ ($=\Delta(B,A)$) equals:

$\displaystyle\sum_{t=0}^{v-1}x_{t}y_{t+\delta}$
$\displaystyle=\sum_{i=0}^{k_{1}-1}\sum_{j=0}^{a-1}y_{jb+s_{i}+\delta}$ (by
the definition of $X$, since it is 0 for all other values)
$\displaystyle=\sum_{i=0}^{k_{1}-1}k_{2}$ (since there are $k_{2}$ elements of
$B$ congruent to $s_{i}+\delta$ modulo $b$) $\displaystyle=k_{1}k_{2}$

This holds for all $\delta\in\mathbb{Z}_{v}$ and so
$\Delta(A,B)=\Delta(B,A)=k_{1}k_{2}\mathbb{Z}_{v}$. So $\\{A,B\\}$ forms a
non-disjoint $(v,2,k_{1}a,k_{2}b)$-GPSEDF as required. ∎

######  Corollary 3.8.

Let $v=ab$ for some $a,b\in\mathbb{N}$. Let $k_{1}\in\\{1,\ldots,b-1\\}$ and
$k_{2}\in\\{1,\ldots,a-1\\}$. Then there exist at least ${a\choose
k_{2}}^{b}{b\choose k_{1}}$ different families of sets which are non-disjoint
$(v,2,k_{1}a,k_{2}b)$-GPSEDFs in $\mathbb{Z}_{v}$.

###### Proof.

We analyse the number of choices in the construction of Theorem 3.7. For the
elements of $R$ there are ${a\choose k_{2}}^{b}$ choices, then ${b\choose
k_{1}}$ choices for the elements of $S$. Now we consider the sets $A$ and $B$
defined by the sequences $X$ and $Y$.

Firstly, note if
$\\{s_{0},\dots,s_{k_{1}-1}\\}\neq\\{t_{0},\dots,t_{k_{1}-1}\\}$ then
$\\{jb+s_{0},\dots,jb+s_{k_{1}-1}:1\leq j\leq
a-1\\}\neq\\{jb+t_{0},\dots,jb+t_{k_{1}-1}:1\leq j\leq a-1\\}$ so each of the
$b\choose k_{1}$ choices for $S$ will give us a different $X$. Similarly, if
$\\{r_{i,0},r_{i,1},\dots,r_{i,k_{2}-1}\\}\neq\\{t_{i,0},t_{i,1},\dots,t_{i,k_{2}-1}\\}$
then
$\\{r_{i,0}b+i,r_{i,1}b+i,\dots,r_{i,k_{2}-1}b+i\\}\neq\\{t_{i,0}b+i,t_{i,1}b+i,\dots,t_{i,k_{2}-1}b+i\\}$
and so we obtain a different $Y$ for each of the ${a\choose k_{1}}^{b}$
choices of $R$. ∎

We illustrate this construction with an example.

######  Example 3.9.

We let the parameters from Theorem 3.7 be as follows: $v=20=4*5$, $a=4$,
$b=5$, $k_{1}=2$, $k_{2}=3$, $s_{0}=1$, $s_{1}=3$ and we define $r_{i,j}$ and
the values of $y_{t}$ according to the following tables respectively:

i j | $0$ | $1$ | $2$
---|---|---|---
$0$ | $0$ | $1$ | $3$
$1$ | $0$ | $2$ | $3$
$2$ | $0$ | $1$ | $2$
$3$ | $1$ | $2$ | $3$
$4$ | $0$ | $2$ | $3$
i j | $0$ | $1$ | $2$
---|---|---|---
$0$ | $0$ | $5$ | $15$
$1$ | $1$ | $11$ | $16$
$2$ | $2$ | $7$ | $12$
$3$ | $8$ | $13$ | $18$
$4$ | $4$ | $14$ | $19$

We obtain the sequences:

$X=01010010100101001010$

$Y=11101101100111111011$

These sequences correspond to the sets:

$A=\\{1,3,6,8,11,13,16,18\\}$

$B=\\{0,1,2,4,5,7,8,11,12,13,14,15,16,18,19\\}$

We next present constructions for more than two sets which use the modular
arithmetic viewpoint.

######  Theorem 3.10.

Let $v\in\mathbb{N}$ and let $a_{1},\dots,a_{m}$ be coprime factors of $v$.

  * (i)

There exists a non-disjoint
$(v,m,\frac{v}{a_{1}},\dots,\frac{v}{a_{m}})$-GPSEDF in $\mathbb{Z}_{v}$.

  * (ii)

Let $0\leq\mu_{i}\leq a_{i}-1$ for $1\leq i\leq m$. Then there exists a non-
disjoint $(v,m,\mu_{1}\frac{v}{a_{1}},\dots,\mu_{m}\frac{v}{a_{m}})$-GPSEDF in
$\mathbb{Z}_{v}$.

###### Proof.

(i) We let $a_{1},\dots,a_{m}$ be coprime factors of $v$. Then we define
sequences $X_{i}=(x_{t})_{t=0}^{v-1}$ where:

$x_{t}=\begin{cases}1,&t=la_{i}\quad(0\leq l\leq\frac{v}{a_{i}}-1)\\\
0,&\text{otherwise}\end{cases}$

We let $X_{i}$ correspond to the set $A_{i}$ in $\mathbb{Z}_{v}$. Then let
$1\leq i,j\leq m$, such that $i\neq j$. We let $X_{i}=(x_{t})_{t=0}^{v-1}$ and
$X_{j}=(y_{t})_{t=0}^{v-1}$. Let $\delta\in\mathbb{Z}_{v}$ and consider the
number of occurrences of $\delta$ in
$\Delta(A_{i},A_{j})$($=\Delta(A_{j},A_{i})$), which by Theorem 2.27 is equal
to:

$\displaystyle\sum_{t=0}^{v-1}x_{t}y_{t+\delta}$
$\displaystyle=\frac{v}{a_{i}a_{j}}\sum_{t=0}^{a_{i}a_{j}-1}x_{t}y_{t+\delta}\quad$
$\displaystyle(X_{i}\text{ and }X_{j}\text{ repeat every }a_{i}\text{ or
}a_{j})$
$\displaystyle=\frac{v}{a_{i}a_{j}}\sum_{l=0}^{a_{j}-1}y_{la_{i}+\delta}\quad$
$\displaystyle(\text{by }X_{i}\text{'s definition, it is 0 for all other
values})$
$\displaystyle=\frac{v}{a_{i}a_{j}}\sum_{l=0}^{a_{j}-1}y_{la_{i}+ba_{j}+d}\quad$
$\displaystyle(\delta=ba_{j}+d\text{ for some }0\leq
b\leq\frac{v}{a_{j}}-1,0\leq d\leq a_{j}-1)$
$\displaystyle=\frac{v}{a_{i}a_{j}}\sum_{l=0}^{a_{j}-1}y_{la_{i}+d}\quad$
$\displaystyle(X_{j}\text{ repeats every }a_{j})$
$\displaystyle=\frac{v}{a_{i}a_{j}}$

To see that sum on the penultimate line equals 1, note that the set of indices
$\\{la_{i}+d:0\leq l\leq a_{i}\\}$ comprises all elements between $0$ and
$a_{i}a_{j}-1$ which are congruent to $d$ mod $a_{i}$, then by the definition
of $X_{j}$ the sum counts those set members congruent to $0$ mod $a_{j}$. This
sum will be 1 because $a_{i}$ and $a_{j}$ are coprime and so by the Chinese
Remainder Theorem there is precisely one value between 0 and $a_{i}a_{j}-1$,
which is $d$ mod $a_{i}$ and 0 mod $a_{j}$.

This holds for all $\delta\in\mathbb{Z}_{v}$ and $1\leq i,j\leq m,i\neq j$. So
$\Delta(A_{i},A_{j})=\frac{v}{a_{i}a_{j}}$ for all $1\leq i,j\leq m,i\neq j$.
Hence, $\\{A_{1},\dots,A_{m}\\}$ forms a non-disjoint
$(v,m,\frac{v}{a_{1}},\dots,\frac{v}{a_{m}})$-GPSEDF in $\mathbb{Z}_{v}$.
(ii) From (i), there exists a non-disjoint
$(v,m,\frac{v}{a_{1}},\dots,\frac{v}{a_{m}})$-GPSEDF
$A=\\{A_{1},\ldots,A_{m}\\}$ in $Z_{v}$, where
$A_{i}=\\{0,a_{i},\ldots,(\frac{v}{a_{i}}-1)a_{i}\\}$. For each $A_{i}$, any
choice of $\mu_{i}$ elements $g_{j}(1\leq j\leq\mu_{i})$ from
$\\{0,1,\ldots,a_{i}-1\\}$ will yield $\mu_{i}$ sets $g_{j}+A_{i}$ which are
disjoint. By Theorem 2.24 (v), replacing each $A_{i}$ in $A$ with such a union
of $g_{j}+A_{i}$, yields a non-disjoint GPSEDF with the stated parameters. ∎

######  Example 3.11.

Let $v=15$ and let $a_{1}=5$ and $a_{2}=3$. The sets $A_{1}=\\{0,5,10\\}$ and
$A_{1}=\\{0,3,6,9,12\\}$ form a non-disjoint $(15,2,3,5)$-GPSEDF in
$\mathbb{Z}_{15}$.
Let $\mu_{1}=3$ and $\mu_{2}=2$; taking the unions of
$\\{A_{1},1+A_{1},2+A_{1}\\}$ and $\\{A_{2},1+A_{2}\\}$ we obtain

$\\{\\{0,1,2,5,6,7,10,11,12\\},\\{0,1,3,4,6,7,9,10,12,13\\}\\}$

which is a non-disjoint $(15,2,9,10)$-GPSEDF in $\mathbb{Z}_{15}$.

We end this section with a multiset version of Theorem 3.2.

######  Theorem 3.12.

Let $(a_{0},a_{1},\dots,a_{m})$ ($m\geq 2$) be a sequence of positive integers
such that for all $1\leq i+1\leq m$, $a_{i}=b_{i+1}a_{i+1}$ for some
$b_{i+1}(\geq 2)\in\mathbb{Z}$. Then, for all possible $1\leq k_{i}\leq b_{i}$
there exists a non-disjoint
($a_{0},m,(l_{1,1}+l_{1,2}+\dots+l_{1,k_{1}})a_{1},\dots,(l_{m,1}+l_{m,2}+\dots+l_{m,k_{m}})a_{m}\frac{a_{0}}{a_{m-1}}$)-MGPSEDF,
where $l_{i,j}$ is an arbitrary natural number for all $1\leq i\leq m,1\leq
j\leq k_{m}$. Its $\lambda$-matrix is $[a_{ij}]_{m\times m}$, where $a_{ij}=0$
if $i=j$ and
$a_{ij}=\lambda_{i,j}=\frac{a_{0}(l_{i,1}+l_{i,2}+\dots+l_{i,k_{i}})a_{i}(l_{j,1}+l_{j,2}+\dots+l_{j,k_{j}})a_{j}}{a_{i-1}a_{j-1}}$
otherwise.

###### Proof.

Let $(a_{0},a_{1},\dots,a_{m})$ ($m\geq 2$) be a sequence of positive integers
such that for all $1\leq i+1\leq m$, $a_{i}=b_{i+1}a_{i+1}$ for some
$b_{i+1}\geq 2$. Then fix $1\leq k_{i}\leq b_{i}$ for all $1\leq i\leq m$.

Define $X_{i}=(x_{t})_{t=0}^{a_{0}-1}$ for all $i=1,\dots,m$, where:

$x_{t}=\begin{cases}l_{i,j},&(j-1)a_{i}\leq t\leq ja_{i}-1,j=1,\dots,k_{i}\\\
0,&k_{i}a_{i}\leq t\leq a_{i}b_{i}-1=a_{i-1}-1\\\
x_{t-a_{i}b_{i}},&a_{i}b_{i}\leq t\leq
a_{0}-1\quad(a_{i}b_{i}=a_{i-1})\end{cases}$

The proof is analogous to that of Theorem 3.2, using Theorem 2.28. ∎

##  4 New results on non-disjoint SEDFs and GSEDFs using group theory

In this section we show how adopting a group theoretic viewpoint can be a
productive way to yield further constructions in $\mathbb{Z}_{n}$ and other
abelian and non-abelian groups. We write groups multiplicatively except when
working in specific additive groups. We require the following group theoretic
results.

######  Lemma 4.1.

Let $G$ be a finite group and let $H,K\leq G$. Define the map $f:H\times
K\rightarrow HK$ by $(h,k)\mapsto hk$

  * (i)

$HK$ is a subgroup of $G$ if and only if $HK=KH$.

  * (ii)

Under $f$, the preimage of any element of $HK$ has cardinality $|H\cap K|$.

  * (iii)

$|HK|=\frac{|H||K|}{|H\cap K|}$;

  * (iv)

$G=HK\Leftrightarrow|G|=|HK|\Leftrightarrow[G:H\cap K]=[G:H][G:K]$.

###### Proof.

We prove (ii) and (iii). Define the map $f:H\times K\rightarrow HK$ by
$(h,k)\mapsto hk$. Clearly this map is surjective. Let $x\in HK$; say $x=hk$
for some fixed $h\in H,k\in K$. For $h^{\prime}\in H,k^{\prime}\in K$ we have
$f(h^{\prime},k^{\prime})=x\Leftrightarrow
h^{\prime}k^{\prime}=hk\Leftrightarrow h^{-1}h^{\prime}=kk^{\prime-1}\in H\cap
K\Leftrightarrow$ for some $y\in H\cap K$, $h^{\prime}=hy$ and
$k^{\prime}=y^{-1}k$. Hence the preimage under $f$ of $hk$ is the set
$\\{(hy,y^{-1}k):y\in H\cap K\\}$ which is clearly in bijective correspondence
with $H\cap K$. So $|H\times K|=|HK||H\cap K|$ and so $|H||K|=|HK||H\cap K|$.
∎

######  Lemma 4.2.

Let $G$ be a finite group and let $H,K\leq G$. If $[G:H]$ and $[G:K]$ are
coprime integers then $G=HK$.

We next present a non-disjoint GPSEDF construction which utilises these group
theoretic properties.

######  Theorem 4.3.

Let $G$ be a finite group and let $H=\\{H_{1},\ldots,H_{m}\\}$ be a collection
of distinct subgroups of $G$. If $G=H_{i}H_{j}$ for all pairs $i\neq j$
($1\leq i,j\leq m$) then

  * (i)

$H$ is a non-disjoint $(|G|,m,|H_{1}|,\ldots,|H_{m}|)$-GPSEDF with
$\lambda_{i,j}=|H_{i}\cap H_{j}|$ for all $i\neq j$.

  * (ii)

Any $H_{i}\in H$ can be replaced in $H$ by a union of $\mu_{i}$ distinct
cosets of $H_{i}$ to obtain a new non-disjoint
$(|G|,m,|H_{1}|,\ldots,\mu_{i}|H_{i}|,\ldots,|H_{m}|)$-GPSEDF.

###### Proof.

We first prove (i). Let $i\neq j$. The multiset
$\Delta(H_{i},H_{j})=\\{xy^{-1}:x\in H_{i},y\in H_{j}\\}=\\{xy:x\in H_{i},y\in
H_{j}\\}$ since $H_{j}$ is a subgroup. By Lemma 4.1, for each $g\in
H_{i}H_{j}=G$, there are $|H_{i}\cap H_{j}|$ pairs $(x,y)\in H_{i}\times
H_{j}$ such that $xy=g$. Hence $\Delta(H_{i},H_{j})$ comprises $|H_{i}\cap
H_{j}|$ occurrences of each element of $G$. Part (ii) follows by applying
Theorem 2.24 (v). ∎

The following result presents some specific constructions obtainable from
Theorem 4.3. Since there is no requirement for the group $G$ to be abelian,
this yields our first examples of non-abelian non-disjoint SEDFs, PSEDFs and
GPSEDFs.

######  Corollary 4.4.

  * (i)

Let $G=\mathbb{Z}_{p}\times\mathbb{Z}_{p}$, where $p$ is prime. Let $H$ be the
collection of all $p+1$ distinct subgroups of $G$ of order $p$. Then $H$ is a
non-disjoint $(p^{2},p+1,p,1)$-PSEDF.

  * (ii)

Let $G=D_{2n}$ (the dihedral group of order $2n$) with $n$ odd. Let $\alpha$
and $\beta$ be the standard generators for $D_{2n}$ such that
$|\alpha|=n,|\beta|=2$. Then $\\{\langle\alpha\rangle,\langle\beta\rangle\\}$
is a non-disjoint $(2n,2,2,n)$-GPSEDF.

  * (iii)

Let $G=\mathbb{Z}_{n}$. Let $\\{a_{1},\ldots,a_{m}\\}$ be a collection of
divisors of $n$ which are pairwise coprime. For $1\leq i\leq m$, let $H_{i}$
be the additive subgroup generated by $a_{i}$. Then
$H=\\{H_{1},\ldots,H_{m}\\}$ is a non-disjoint
$(n,m,\frac{n}{a_{1}},\ldots,\frac{n}{a_{m}})$-GPSEDF.

Observe that the construction of Corollary 4.4(iii) corresponds to Proposition
3.10 (i), while its extension via Theorem 4.3 (ii) corresponds to Proposition
3.10 (ii).

There are many other constructions in both abelian and non-abelian groups
which result from an application of Theorem 4.3. We present the following
examples.

######  Example 4.5.

Let $G=D_{8}$ be the dihedral group of order 8, which is generated by
$\alpha,\beta$ where $|\alpha|=4,|\beta|=2$. Then
$H=\\{e,\beta,\alpha^{2},\alpha^{2}\beta\\}$ and
$K=\\{e,\alpha\beta,\alpha^{2},\alpha^{3}\beta\\}$ are subgroups of $D_{8}$,
such that $HK=KH=D_{8}$ and $H\cap K=\\{e,\alpha^{2}\\}$. By Theorem 4.3,
$\\{H,K\\}$ is a non-disjoint $(8,2,4,4)$-GPSEDF; the following subtraction
table illustrates that $\Delta(H,K)=2D_{8}$

$*$ | $e$ | $\alpha\beta$ | $\alpha^{2}$ | $\alpha^{3}\beta$
---|---|---|---|---
$e$ | $e$ | $\alpha\beta$ | $\alpha^{2}$ | $\alpha^{3}\beta$
$\beta$ | $\beta$ | $\alpha^{3}$ | $\alpha^{2}\beta$ | $\alpha$
$\alpha^{2}$ | $\alpha^{2}$ | $\alpha^{3}\beta$ | $e$ | $\alpha\beta$
$\alpha^{2}\beta$ | $\alpha^{2}\beta$ | $\alpha$ | $\beta$ | $\alpha^{3}$

######  Example 4.6.

Let $G=Q_{8}$ be the quaternion group, with its elements written in usual
notation as $\\{1,-1,i,-i,j,-j,k,-k\\}$. The subgroups $\langle i\rangle$ and
$\langle j\rangle$ in $Q_{8}$ form a non-disjoint ($8,2,4,2$)-PSEDF. The
subgroups $\langle i\rangle,\langle j\rangle$ and $\langle k\rangle$ form a
non-disjoint ($8,3,4,2$)-PSEDF. The following table illustrates
$\Delta(\langle i\rangle,\langle j\rangle)$.

$*^{-1}$ | $1$ | $j$ | $-j$ | $-1$
---|---|---|---|---
$1$ | $1$ | $-j$ | $j$ | $-1$
$i$ | $i$ | $-k$ | $k$ | $-i$
$-i$ | $-i$ | $k$ | $-k$ | $i$
$-1$ | $-1$ | $-j$ | $j$ | $1$

In fact, we can develop a more flexible construction in $\mathbb{Z}_{n}$ than
that of Corollary 4.4(iii) - one which does not require the individual
subgroups to have coprime index. In $\mathbb{Z}_{n}$, we return to additive
notation. For $a|n$, we will denote the additive subgroup of
$(\mathbb{Z}_{n},+)$ generated by $a\in\mathbb{Z}_{n}$ (the set
$\\{0,a,\ldots,n-a\\}$) by $a\mathbb{Z}_{n}$, to make it clear in which group
the cyclic subgroup lies. Here we avoid the use of $\lambda S$ for $\lambda$
copies of set $S$, which we have used in other sections.

We will need the following preliminary result.

######  Lemma 4.7.

Let $a,b$ be distinct divisors of $n$ ($a,b,n\in\mathbb{N}$). Let $d=gcd(a,b)$
and $l=lcm(a,b)$. Then

  * (i)

The multiset $\Delta(a\mathbb{Z}_{n},b\mathbb{Z}_{n})$ comprises $\frac{n}{l}$
copies of $d\mathbb{Z}_{n}$;

  * (ii)

If $d>1$ then

$\Delta(\cup_{r=0}^{d-1}(r+a\mathbb{Z}_{n}),b\mathbb{Z}_{n})=\Delta(a\mathbb{Z}_{n},\cup_{r=0}^{d-1}(r+b\mathbb{Z}_{n}))=\frac{n}{l}\mbox{
copies of }\mathbb{Z}_{n}$

i.e. $\\{\\{\cup_{r=0}^{d-1}(r+a\mathbb{Z}_{n})\\},b\mathbb{Z}_{n}\\}$ and
$\\{a\mathbb{Z}_{n},\\{\cup_{r=0}^{d-1}(r+b\mathbb{Z}_{n})\\}\\}$ both form
2-set non-disjoint GPSEDFs with $\lambda=\frac{n}{l}$.

###### Proof.

For (i), by Lemma 4.1, $a\mathbb{Z}_{n}+b\mathbb{Z}_{n}$ is the subgroup of
$\mathbb{Z}_{n}$ with order
$\frac{|a\mathbb{Z}_{n}||b\mathbb{Z}_{n}|}{|a\mathbb{Z}_{n}\cap
b\mathbb{Z}_{n}|}=\frac{(n/a)(n/b)}{n/l}=\frac{n}{d}$, i.e. $d\mathbb{Z}_{n}$,
and in the internal difference multiset
$\Delta(a\mathbb{Z}_{n},b\mathbb{Z}_{n})$, each element of $d\mathbb{Z}_{n}$
occurs $\frac{n}{l}$ times. Part (ii) then follows. ∎

We first present the most general version of our non-disjoint GPSEDF
construction, using an algorithm which allows considerable flexibility.

######  Definition 4.8.

Let $n\in\mathbb{N}$ and let $a_{1},\dots,a_{m}\in\mathbb{N}$ be distinct
divisors of $n$. We define $chunk(a_{i})$ to be the final value after the
following algorithm has been run:

  1. 1.

Set $chunk(a_{i})=1$ for $1\leq i\leq m$

  2. 2.

For all $i$ from $1$ to $m-1$

  3. 3.

For all $j$ from $i+1$ to $m$

    1. (a)

Let $d=gcd(a_{i},a_{j})$

    2. (b)

Arbitrarily choose $i$ or $j$; call this $k$.

    3. (c)

Redefine $chunk(a_{k}):=lcm(chunk(a_{k}),d)$

######  Theorem 4.9.

Let $G=\mathbb{Z}_{n}$. Let $\\{a_{1},\ldots,a_{m}\\}$ be a collection of
distinct divisors of $n$. Let $ch(a_{i})$ be the value of $chunk(a_{i})$ as
defined in Definition 4.8 ($1\leq i\leq m$). Define

$H_{i}=\cup_{r=0}^{ch(a_{i})-1}(r+a_{i}\mathbb{Z}_{n}).$

Then $H=\\{H_{1},\ldots,H_{m}\\}$ is a non-disjoint
$(n,m,\frac{n}{a_{1}}ch(a_{1}),\frac{n}{a_{2}}ch(a_{2}),\ldots,\frac{n}{a_{m}}ch(a_{m}))$-GPSEDF
in $\mathbb{Z}_{n}$ with
$\lambda_{i,j}=\frac{n}{a_{i}a_{j}}ch(a_{i})ch(a_{j})$.

###### Proof.

Let $1\leq i<j\leq m$. We aim to show that $\\{H_{i},H_{j}\\}$ is a non-
disjoint GPSEDF with the stated parameters. We may replace precisely one of
$H_{i}$ or $H_{j}$ by $a_{i}\mathbb{Z}_{n}$ or $a_{j}\mathbb{Z}_{n}$
respectively, then apply Theorem 2.24(v) to complete the result.

Let $l=lcm(a_{i},a_{j})$. Then $a_{i}\mathbb{Z}_{n}$ and $a_{j}\mathbb{Z}_{n}$
are unions of cosets of $l\mathbb{Z}_{n}$; specifically
$a_{i}\mathbb{Z}_{n}=l\mathbb{Z}_{n}\cup(a_{i}+l\mathbb{Z}_{n})\cup\cdots\cup((\frac{l}{a_{i}}-1)a_{i}+l\mathbb{Z}_{n})$
and
$a_{j}\mathbb{Z}_{n}=l\mathbb{Z}_{n}\cup(a_{j}+l\mathbb{Z}_{n})\cup\cdots\cup((\frac{l}{a_{j}}-1)a_{j}+l\mathbb{Z}_{n})$.

At some point in the algorithm of Definition 4.8, the pair $i<j$ was
considered, one of $\\{chunk(a_{i}),chunk(a_{j})\\}$ was arbitrarily chosen,
and assigned a new value divisible by $\gcd(a_{i},a_{j})$. We may assume wlog
that this was $chunk(a_{i})$ (if it was $chunk(a_{j})$ then the following
argument is exactly analogous with $i$ and $j$ switched). From the algorithm,
this divisibility property persists irrespective of any subsequent updates to
the value of $chunk(a_{i})$, so we have that $\gcd(a_{i},a_{j})|ch(a_{i})$. We
now consider

$\Delta(H_{i},a_{j}\mathbb{Z}_{n})=\Delta(\cup_{r=0}^{ch(a_{i})-1}\cup_{s=0}^{\frac{l}{a_{i}}-1}(r+sa_{i}+l\mathbb{Z}_{n}),\cup_{t=0}^{\frac{l}{a_{j}}-1}ta_{j}+l\mathbb{Z}_{n})$

By Theorem 2.25, this equals $\lambda$ copies of $\mathbb{Z}_{n}$ for some
$\lambda$ if the sets $\\{r+sa_{i}:0\leq r\leq ch(a_{i})-1,0\leq
s\leq\frac{l}{a_{i}}-1\\}$ and $\\{ta_{j}:0\leq t\leq\frac{l}{a_{j}}-1\\}$
form a non-disjoint GPSEDF in $G/l\mathbb{Z}_{n}\cong\mathbb{Z}_{l}$.

The relevant difference multiset in $\mathbb{Z}_{l}$ is

$\Delta(a_{i}\mathbb{Z}_{l}\cup(1+a_{i}\mathbb{Z}_{l})\cup\cdots\cup((ch(a_{i})-1)+a_{i}\mathbb{Z}_{l}),a_{j}\mathbb{Z}_{l})$

which is
$\cup_{r=0}^{ch(a_{i})-1}\Delta(r+a_{i}\mathbb{Z}_{l},a_{j}\mathbb{Z}_{l})$.
By Lemma 4.7, the elements of
$\Delta(a_{i}\mathbb{Z}_{l},a_{j}\mathbb{Z}_{l})$ are those of
$\gcd(a_{i},a_{j})\mathbb{Z}_{l}$, each occurring
$\frac{l}{lcm(a_{i},a_{j})}=1$ times. Hence the elements of
$\cup_{r=0}^{ch(a_{i})-1}\Delta(r+a_{i}\mathbb{Z}_{l},a_{j}\mathbb{Z}_{l},)$
are the elements of
$\cup_{r=0}^{ch(a_{i})-1}(r+gcd(a_{i},a_{j})\mathbb{Z}_{l})$, i.e.
$\frac{ch(a_{i})}{\gcd(a_{i},a_{j})}$ copies of the multiset
$\cup_{r=0}^{gcd(a_{i},a_{j})-1}(r+gcd(a_{i},a_{j})\mathbb{Z}_{l})=\mathbb{Z}_{l}$.
So we have a non-disjoint
$(l,2,\frac{ch(a_{i})l}{a_{i}},\frac{l}{a_{j}})$-GPSEDF in $\mathbb{Z}_{l}$
with $\lambda_{1,2}=\frac{ch(a_{i})}{\gcd(a_{i},a_{j})}$ . Hence in $G$ we
have a non-disjoint $(n,2,\frac{ch(a_{i})n}{a_{i}},\frac{n}{a_{j}})$-GPSEDF
with
$\lambda=\frac{ch(a_{i})n}{\gcd(a_{i},a_{j})l}=\frac{ch(a_{i})n}{a_{i}a_{j}}$.
Finally, $\\{H_{i},H_{j}\\}$ form a non-disjoint
$(n,2,\frac{ch(a_{i})n}{a_{i}},\frac{ch(a_{j})n}{a_{j}})$-GPSEDF in $G$ with
$\lambda_{i,j}=\frac{ch(a_{i})ch(a_{j})n}{a_{i}a_{j}}$ and so the result
follows. ∎

From Theorem 4.9, we can obtain various corollaries, whose statements give
explicit parameters. For example, we have the following three-set
construction.

######  Corollary 4.10.

Let $G=\mathbb{Z}_{n}$. Let $\\{a_{1},a_{2},a_{3}\\}$ be a collection of
distinct divisors of $n$. Taking the indices on the $a$’s modulo $3$, define
(for $1\leq i\leq 3$):

$H_{i}=\cup_{r=0}^{\gcd(a_{i},a_{i+1})-1}(r+a_{i}\mathbb{Z}_{n}).$

Then $H=\\{H_{1},H_{2},H_{3}\\}$ is a non-disjoint
$(n,3,\frac{n}{a_{1}}gcd(a_{1},a_{2}),\frac{n}{a_{2}}gcd(a_{2},a_{3}),\frac{n}{a_{3}}gcd(a_{3},a_{1}))$-GPSEDF
in $\mathbb{Z}_{n}$ with
$\lambda_{i,i+1}=\lambda_{i+1,i}=\frac{n\gcd(a_{i+1},a_{i+2})}{lcm(a_{i},a_{i+1})}$.

###### Proof.

Apply the algorithm of Definition 4.8 as follows: for $i=1$ and $j=2$ take
$k=1$; for $i=1$ and $j=3$ take $k=3$; and for $i=2$ and $k=3$ take $k=2$. So
$ch(a_{1})=\gcd(a_{1},a_{2})$, $ch(a_{2})=\gcd(a_{2},a_{3})$ and
$ch(a_{3})=\gcd(a_{3},a_{1})$. Now apply Theorem 4.9. ∎

######  Example 4.11.

Let $G=\mathbb{Z}_{24}$ and let $a_{1}=4$, $a_{2}=6$ and $a_{3}=8$. From
Corollary 4.10 we obtain the non-disjoint GPSEDF with sets
$\\{0,1,4,5,8,9,12,13,16,17,20,21\\}$, $\\{0,1,6,7,12,13,18,19\\}$, and
$\\{0,1,2,3,8,9,10,11,16,17,18,19\\}$ where $\lambda_{1,2}=4$,
$\lambda_{2,3}=4$ and $\lambda_{3,1}=6$ These correspond to the sequences:

  * $110011001100110011001100$

  * $110000110000110000110000$

  * $111100001111000011110000$

In the final section of this paper, we show how an adaptation of this approach
will yield a construction for VW-OOCs with minimum cross-correlation, which do
not possess the GPSEDF property.

Finally, the following general result demonstrates a connection to classical
EDFs and GEDFs (though not the strong versions). Recall that a family of
subgroups of a group $G$ is called a partition of $G$ if every non-identity
element of $G$ belongs to precisely one subgroup in the family [21].

######  Theorem 4.12.

Let $G$ be a finite group and let $H=\\{H_{1},\ldots,H_{m}\\}$ be a collection
of subgroups of $G$ such that $|G|=|H_{i}||H_{j}|$ for all $i\neq j$ and $H$
is a partition of $G$. Then

  * (i)

$H$ is a non-disjoint GPSEDF with $\lambda_{i,j}=1$ for all $i,j$ (a non-
disjoint PSEDF when all $|H_{i}|$ are equal);

  * (ii)

$H^{\prime}=\\{H_{1}\setminus\\{e\\},\ldots,H_{m}\setminus\\{e\\}\\}$ is a
classical GEDF (classical EDF when all $|H_{i}|$ are equal) which is not
strong.

###### Proof.

Part (i) is immediate from Lemma 4.1 and Theorem 4.3. For (ii), removing the
identity from each $H_{k}$ ($1\leq k\leq m$) makes the sets in $H^{\prime}$
pairwise disjoint. From each $\Delta(H_{i},H_{j})$, it removes the occurrence
of $\\{e\\}$, one copy of $H_{i}\setminus\\{e\\}$ and one copy of
$H_{j}\setminus\\{e\\}$. Overall, an equal number of copies of all sets in
$H^{\prime}$ are removed from the original external difference multiset of the
non-disjoint GPSEDF $H$, together with all occurrences of the identity. Since
the subgroups of $H$ form a subgroup partition of $G$, the resulting external
difference multiset yields each non-identity element an equal number of times,
and so $H^{\prime}$ is a classical GEDF. This is not strong since, from
$\cup_{j\neq i}\Delta(H_{i},H_{j})$ ($i$ fixed), $m-1$ copies of $H_{i}$ would
be removed but only one copy each of $H_{j}$ , $j\neq i$. ∎

This can be applied to the construction in
$\mathbb{Z}_{p}\times\mathbb{Z}_{p}$ in Corollary 4.4(i). The classical EDF
case of this result relates to the classical EDF case of a partition
construction given in [6].

##  5 Non-disjoint PSEDF and GPSEDF Constructions in External Direct Products

In this section, we show how we can combine non-disjoint PSEDFs and non-
disjoint SEDFs to create new ones in external direct products. This is in
contrast to classical SEDFs, in which no extensions to direct products are
known.

We first show how to combine individual non-disjoint PSEDFs to create new ones
in direct products of groups.

######  Theorem 5.1.

Let $A=\\{A_{1},A_{2},\dots,A_{m}\\}$ and $B=\\{B_{1},B_{2},\dots,B_{m}\\}$ be
a non-disjoint $(n_{a},m,k_{a},\lambda_{a})$-PSEDF and a non-disjoint
$(n_{b},m,k_{b},\lambda_{b})$-PSEDF in groups $G_{a}$ and $G_{b}$
respectively. Then $L=\\{A_{i}\times B_{i}:1\leq i\leq m\\}$ is a non-disjoint
$(n_{a}n_{b},m,k_{a}k_{b},\lambda_{a}\lambda_{b})$-PSEDF in $G_{a}\times
G_{b}$.

###### Proof.

Let $C_{i}=A_{i}\times B_{i}$ ($1\leq i\leq m$). Then $L=\\{C_{i}:1\leq i\leq
m\\}$, with $|C_{i}|=|A_{i}||B_{i}|=k_{a}k_{b}$ and $C_{i}\subseteq
G_{a}\times G_{b}$ for each $i$.
Now fix $(\delta_{1},\delta_{2})\in G_{a}\times G_{b}$ and consider the number
of occurrences of $(\delta_{1},\delta_{2})$ in $\Delta(C_{i},C_{j})$ ($1\leq
i,j\leq m$, $i\neq j$). This is the number of
$\\{(a_{i},b_{i}),(a_{j},b_{j})\\}\in C_{i}\times C_{j}$ such that:

$(\delta_{1},\delta_{2})=(a_{i},b_{i})-(a_{j},b_{j})=(a_{i}-a_{j},b_{i}-b_{j})$

The number of pairs of elements $a_{i}\in A_{i}$ and $a_{j}\in A_{j}$ such
that $a_{i}-a_{j}=\delta_{1}$ is $\lambda_{a}$ (as $A_{i},A_{j}$ are sets of a
non-disjoint $(n_{a},m,k_{a},\lambda_{a})$-PSEDF). Similarly, there are
$\lambda_{b}$ possibilities for pairs of elements $b_{i}$ and $b_{j}$. So
there are $\lambda_{a}\lambda_{b}$ occurrences of
$(\delta_{1},\delta_{2})\in\Delta(C_{i},C_{j})$. This holds for all
$(\delta_{1},\delta_{2})\in G_{a}\times G_{b}$ and all $1\leq i,j\leq m,i\neq
j$. The result follows. ∎

######  Example 5.2.

In the Klein four-group $K_{4}=\\{e,a,b,c\\}$, the sets
$\\{A_{a}=\\{e,a\\},A_{b}=\\{e,b\\},A_{c}=\\{e,c\\}\\}$ form a non-disjoint
$(4,3,2,1)$-PSEDF. The sets $L=\\{A_{a}\times A_{a},A_{b}\times
A_{b},A_{c}\times A_{c}\\}$ form a non-disjoint $(16,3,4,1)$-PSEDF in
$K_{4}\times K_{4}\cong(\mathbb{Z}_{2})^{4}$. The external difference table
for $A_{a}\times A_{a}$ and $A_{b}\times A_{b}$ is below.

$*^{-1}$ | $(e,e)$ | $(e,b)$ | $(b,e)$ | $(b,b)$
---|---|---|---|---
$(e,e)$ | $(e,e)$ | $(e,b)$ | $(b,e)$ | $(b,b)$
$(e,a)$ | $(e,a)$ | $(e,c)$ | $(b,a)$ | $(b,c)$
$(a,e)$ | $(a,e)$ | $(a,b)$ | $(c,e)$ | $(c,b)$
$(a,a)$ | $(a,a)$ | $(a,c)$ | $(c,a)$ | $(c,c)$

Analogous proof techniques yield the following:

######  Corollary 5.3.

Let $A=\\{A_{1},\dots,A_{m}\\}$ and $B=\\{B_{1},\dots,B_{m}\\}$ be families of
sets in groups $G_{a}$ and $G_{b}$ respectively. Let $L=\\{A_{i}\times
B_{i}:1\leq i\leq m\\}$.

  * (i)

If $A$ and $B$ are a non-disjoint $(n_{a},m,k_{a_{1}},\dots,k_{a_{m}})$-GPSEDF
and a non-disjoint $(n_{b},m,k_{b_{1}},\dots,k_{b_{m}})$-GPSEDF respectively,
then $L$ is a non-disjoint
$(n_{a}n_{b},m,k_{a_{1}}k_{b_{1}},\dots,k_{a_{m}}k_{b_{m}})$-GPSEDF in
$G_{a}\times G_{b}$. If the $\lambda$-matrices of $A$ and $B$ are
$[a_{ij}]_{m\times m}$ and $[b_{ij}]_{m\times m}$ respectively, then the
$\lambda$-matrix of $L$ is $[a_{ij}b_{ij}]_{m\times m}$

  * (ii)

If $A$ and $B$ are a non-disjoint
$(n_{a},m,k_{a_{1}},\dots,k_{a_{m}})$-MGPSEDF and a non-disjoint
$(n_{b},m,k_{b_{1}},\dots,k_{b_{m}})$-MGPSEDF respectively, then $L$ is a non-
disjoint $(n_{a}n_{b},m,k_{a_{1}}k_{b_{1}},\dots,k_{a_{m}}k_{b_{m}})$-MGPSEDF
in $G_{a}\times G_{b}$. If the $\lambda$-matrices of $A$ and $B$ are
$[a_{ij}]_{m\times m}$ and $[b_{ij}]_{m\times m}$ respectively, then the
$\lambda$-matrix of $L$ is $[a_{ij}b_{ij}]_{m\times m}$

  * (iii)

If $A$ and $B$ are a non-disjoint
$(n_{a},m,k_{a_{1}},\dots,k_{a_{m}};\lambda_{1},\dots,\lambda_{m})$-GSEDF and
a non-disjoint
$(n_{b},m,k_{b_{1}},\dots,k_{b_{m}};\mu_{1},\dots,\mu_{m})$-GSEDF
respectively, then $L$ is non-disjoint
$(n_{a}n_{b},m,k_{a_{1}}k_{b_{1}},\dots,k_{a_{m}}k_{b_{m}};\lambda_{1}\mu_{1},\dots,\lambda_{m}\mu_{m})$-GSEDF.

  * (iv)

If $A$ and $B$ are a non-disjoint $(n_{a},m,k_{a_{1}},\dots,k_{a_{m}})$-MGSEDF
and non-disjoint $(n_{b},m,k_{b_{1}},\dots,k_{b_{m}})$-MGSEDF respectively,
then $L$ is a non-disjoint
$(n_{a}n_{b},m,k_{a_{1}}k_{b_{1}},\dots,k_{a_{m}}k_{b_{m}})$-MGSEDF in
$G_{a}\times G_{b}$. If the $\lambda$-matrices of $A$ and $B$ are
$[a_{ij}]_{m\times m}$ and $[b_{ij}]_{m\times m}$ respectively, then the
$\lambda$-matrix of $L$ is $[a_{ij}b_{ij}]_{m\times m}$

This technique can be applied recursively to create constructions in direct
products of more than two groups.

##  6 New results on classical SEDFs and GSEDFs

In this section we show how the sequence techniques of Section 3 may be used
to establish results about classical SEDFs. We note that for a classical SEDF
(with sets corresponding to the sequences $(x_{t})_{t=0}^{v-1}$ and
$(y_{t})_{t=0}^{v-1}$) we now want $\sum_{t=0}^{v-1}x_{t}y_{t+\delta}=\lambda$
for all $1\leq\delta\leq v-1$ and $\sum_{t=0}^{v-1}x_{t}y_{t}=0$.

The next theorem encompasses all known classical SEDFs which are not
obtainable from cyclotomy, via a single direct sequence-based construction
which elucidates their structure. We note that these could be obtained
recursively by taking a suitable initial classical GPSEDF and repeatedly
applying the recursive construction of [4]; our result does not require prior
knowledge of a suitable initial structure.

(We observe that the cyclotomic construction of a 2-set classical SEDF using
the non-zero squares and non-squares of a finite field can also be proved via
sequence techniques, but do not include this here.)

######  Theorem 6.1.

Let $h_{1},h_{2},h_{3},h_{4}\in\mathbb{N}$. There exists a classical
($h_{1}h_{2}h_{3}h_{4}+1,2,h_{1}h_{3},h_{2}h_{4},1,1$)-GSEDF in
$\mathbb{Z}_{h_{1}h_{2}h_{3}h_{4}+1}$ with sets given by

$A=\cup_{i=0}^{h_{3}-1}\\{ih_{1}h_{2}+\alpha:0\leq\alpha\leq h_{1}-1\\}$

and

$B=\cup_{i=0}^{h_{4}-1}\\{ih_{1}h_{2}h_{3}+h_{1}h_{2}(h_{3}-1)+\beta
h_{1}:1\leq\beta\leq h_{2}\\}$

###### Proof.

Let $X=(x_{t})_{t=0}^{h_{1}h_{2}h_{3}h_{4}}$ and
$Y=(y_{t})_{t=0}^{h_{1}h_{2}h_{3}h_{4}}$, be the sequences corresponding to
$A$ and $B$ respectively so:

$x_{t}=\begin{cases}1,&0\leq t\leq h_{1}-1\\\ 0,&h_{1}\leq t\leq
h_{1}h_{2}-1\\\ x_{t-h_{1}h_{2}},&h_{1}h_{2}\leq t\leq h_{1}h_{2}h_{3}-1\\\
0,&h_{1}h_{2}h_{3}\leq t\leq h_{1}h_{2}h_{3}h_{4}\end{cases}$

$y_{t}=\begin{cases}0,&t=0\\\ 0,&1\leq t\leq h_{1}h_{2}(h_{3}-1)\\\
0,&h_{1}h_{2}(h_{3}-1)+1\leq t\leq h_{1}h_{2}(h_{3}-1)+h_{1}-1\\\
1,&t=h_{1}h_{2}(h_{3}-1)+h_{1}\\\ y_{t-h_{1}},&h_{1}h_{2}(h_{3}-1)+h_{1}+1\leq
t\leq h_{1}h_{2}h_{3}\\\ y_{t-h_{1}h_{2}h_{3}},&h_{1}h_{2}h_{3}+1\leq t\leq
h_{1}h_{2}h_{3}h_{4}\end{cases}$

So we obtain:

$X=\overbrace{\overbrace{\overbrace{1\dots 1}^{h_{1}}\overbrace{0\dots
0}^{h_{1}}\dots\overbrace{0\dots 0}^{h_{1}}}^{h_{2}\text{ blocks of length
}h_{1}}\dots\overbrace{\overbrace{1\dots 1}^{h_{1}}\overbrace{0\dots
0}^{h_{1}}\dots\overbrace{0\dots 0}^{h_{1}}}^{h_{2}\text{ blocks of length
}h_{1}}}^{h_{3}\text{ repeats of length-}h_{1}h_{2}\text{
blocks}}\textbf{0}00\dots\dots\dots\dots 0$

$Y=\textbf{0}\overbrace{\overbrace{00\dots\dots
0\textbf{0}\underbrace{\underbrace{0\dots 01}_{h_{1}}\underbrace{0\dots
01}_{h_{1}}\dots\underbrace{00\dots 01}_{h_{1}}}_{h_{2}\text{
repeats}}}^{\text{length }h_{1}h_{2}h_{3}}\dots\overbrace{00\dots\dots
0\textbf{0}\underbrace{\underbrace{0\dots 01}_{h_{1}}\underbrace{0\dots
01}_{h_{1}}\dots\underbrace{0\dots 01}_{h_{1}}}_{h_{2}\text{
repeats}}}^{\text{length }h_{1}h_{2}h_{3}}}^{h_{4}\text{ repeats of
length-}h_{1}h_{2}h_{3}\text{ blocks}}$

Let $A$ and $B$ be the sets corresponding to $X$ and $Y$. We note that they
are both sets in $\mathbb{Z}_{h_{1}h_{2}h_{3}h_{3}+1}$ as $X$ and $Y$ both
have length $h_{1}h_{2}h_{3}h_{4}+1$.

We see that $X$ comprises $h_{3}$ length-$h_{1}h_{2}$ substrings (each
substring containing $h_{1}$ $1$s), followed by a gap of length
$h_{1}h_{2}h_{3}(h_{4}-1)+1$. So $X$ has weight $h_{1}h_{3}$. Sequence $Y$
comprises a $0$, then $h_{4}$ substrings each of length $h_{1}h_{2}h_{3}$,
each substring containing $h_{2}$ $1$s; hence $Y$ has weight $h_{2}h_{4}$.

$A$ and $B$ are disjoint since $X$’s rightmost 1 occurs in position
$h_{1}h_{2}h_{3}-1-h_{1}h_{2}+h_{1}=h_{1}h_{2}(h_{3}-1)+h_{1}-1$ but $Y$’s
leftmost 1 occurs in position $h_{1}h_{2}(h_{3}-1)+h_{1}$. So
$0\notin\Delta(A,B)$.

Let $\delta\in\\{1,\dots,h_{1}h_{2}h_{3}h_{4}\\}$. We consider the number of
occurrences of $\delta$ in $\Delta(A,B)$, which by Theorem 2.27 and the
definition is equal to:

$\sum_{t=0}^{h_{1}h_{2}h_{3}h_{4}}x_{t}y_{t+\delta}=\sum_{t=0}^{h_{1}h_{2}h_{3}-1}x_{t}y_{t+\delta}$

since $x_{t}=0$ for $h_{1}h_{2}h_{3}\leq t\leq h_{1}h_{2}h_{3}h_{4}$. We claim
that this sum equals $1$.

Excluding the first entry, sequence $Y$ repeats itself every $h_{1}h_{2}h_{3}$
entry. Let $Y(\delta)=y_{\delta}y_{\delta+1}\ldots
y_{\delta+h_{1}h_{2}h_{3}-1}$. Observe that, when the extra 0 at the start of
sequence $Y$ does not appear in this substring, $Y(\delta)$ must be a cyclic
shift of $Y(1)=y_{1}\ldots y_{h_{1}h_{2}h_{3}}$. We therefore consider two
cases: (i) those $\delta$ for which $y_{0}$ is not in $Y(\delta)$, and (ii)
those $\delta$ such that $y_{0}$ is in $Y(\delta)$, namely
$v-h_{1}h_{2}h_{3}+1\leq\delta\leq v-1$.

In case (i), $Y(\delta)$ contains exactly $h_{2}$ 1s which occur in a
substring of length $h_{1}h_{2}$. $X$ repeats itself every $h_{1}h_{2}$ entry
within the first $h_{1}h_{2}h_{3}$ entries (which we are summing over). So the
substring of $Y(\delta)$ of length $h_{1}h_{2}$ containing all the $h_{2}$ 1s
must coincide with some cyclic shift of this.
The substrings we obtain are:

$X\text{'s length-}h_{1}h_{2}\text{ substring $X^{\prime}$:
}\overbrace{\overbrace{11\dots 1}^{h_{1}}\overbrace{00\dots
0}^{h_{1}}\dots\overbrace{00\dots 0}^{h_{1}}}^{h_{2}\text{ blocks of length
$h_{1}$}}$

$Y\text{'s length-}h_{1}h_{2}\text{ substring $Y^{\prime}$:
}\underbrace{\underbrace{0\dots 01}_{h_{1}}\underbrace{0\dots
01}_{h_{1}}\dots\underbrace{0\dots 01}_{h_{1}}}_{h_{2}\text{ repeats of
length-$h_{1}$ blocks}}$

We see that these binary sequences are precisely those corresponding to a non-
disjoint ($h_{1}h_{2},2,h_{1},h_{2}$)-GPSEDF $\\{X_{1},X_{2}\\}$ of Theorem
3.2. Here $X^{\prime}=X_{1}$ with $a_{1}=h_{1},\eta_{1}=1,b_{1}=h_{2}$, while
$Y^{\prime}$ is a cyclic shift of $X_{2}$ with $a_{2}=1,\eta_{2}=1$ and
$b_{2}=h_{1}$. The corresponding $a_{0}$ is $a_{1}b_{1}=h_{1}h_{2}$. By the
proof of Theorem 3.2, for any cyclic shift of $X_{1}$ and $X_{2}$ there are a
constant number of 1s coinciding - this number is
$\eta_{1}a_{1}\eta_{2}a_{2}\frac{a_{0}}{a_{1}a_{0}}=\eta_{1}\eta_{2}a_{2}=1$.
So our sum equals 1.

We now consider case (ii), which has two subcases. Although the additional $0$
at the start of $Y$ must now be taken into account, there is a range of values
of $\delta$ for which the “cyclic shift” behaviour remains unaffected. When
$v-h_{1}h_{2}h_{3}+1\leq\delta\leq v-(h_{1}(h_{2}-1))-1$, due to the position
of the $0$s, $Y(\delta)$ is still a cyclic shift of $Y(1)$. To see this, note
that $Y(\delta)$ still comprises (some shift of) $h_{2}$ $1$’s each separated
by gaps of $h_{1}-1$ and all other entries $0$, i.e. a cyclic shift of
$y_{1}\ldots y_{h_{1}h_{2}h_{3}}$. So we can use the same argument as above.

Next, consider $\delta=v-(h_{1}(h_{2}-1))$. Let
$\delta^{\prime}=v-(h_{1}(h_{2}-1))$. Let
$Y(\delta^{\prime})=y_{\delta^{\prime}}y_{\delta^{\prime}+1}\ldots
y_{\delta^{\prime}+h_{1}h_{2}h_{3}-1}$; this is:

$\underbrace{\underbrace{0\dots 01}_{h_{1}}\underbrace{0\dots
01}_{h_{1}}\dots\underbrace{0\dots 01}_{h_{1}}}_{h_{2}-1\text{ blocks of
length }h_{1}}\textbf{0}\underbrace{0\dots
0}_{h_{1}h_{2}(h_{3}-1)}\underbrace{0\dots 0}_{h_{1}-1}$

These are the first $h_{1}h_{2}h_{3}$ terms of $Y$ after a shift by
$\delta^{\prime}$. Consider this shift of $Y$. After the first
length-$(h_{1}(h_{2}-1))$ substring, there is a gap of length
$h_{1}h_{2}h_{3}-h_{1}h_{2}+h_{1}$, i.e. the next leftmost position containing
symbol $1$ is position $h_{1}h_{2}h_{3}$. Thus, for
$Y(\delta)=y_{\delta}\ldots y_{\delta+h_{1}h_{2}h_{3}-1}$ with
$v-(h_{1}(h_{2}-1))+1\leq\delta\leq v-1$, i.e. $\delta=\delta^{\prime}+r$
where $1\leq r\leq h_{1}(h_{2}-1)-1$, the only $1$’s not arising from the
initial $h_{1}(h_{2}-1)$ substring of $Y(\delta^{\prime})$ (i.e. within the
initial $h_{1}(h_{2}-1)-r$ entries of $Y(\delta)$) must occur in positions of
$Y(\delta)$ greater than or equal to $h_{1}h_{2}h_{3}-r$ ($1\leq r\leq
h_{1}(h_{2}-1)-1)$, i.e. positions of $Y(\delta)$ between
$h_{1}h_{2}(h_{3}-1)+h_{1}+1$ and $h_{1}h_{2}h_{3}-1$. But $X$’s rightmost $1$
occurs in position $h_{1}h_{2}(h_{3}-1)+h_{1}-1$. This means that for
$v-(h_{1}(h_{2}-1))\leq\delta\leq v-1$, no contribution will be made to our
sum from these positions. Hence we need only sum over the first
$(h_{2}-1)h_{1}$ entries of $X$ and $Y(\delta)$ for $\delta$ in the range
$v-h_{1}(h_{2}-1)\leq\delta\leq v-1$.

Note that $x_{t}=1$ for $0\leq t\leq h_{1}-1$ and $0$ for $h_{1}\leq t\leq
h_{1}h_{2}-1$, so in fact we need only consider the first $h_{1}$ entries. The
initial length-$h_{1}(h_{2}-1)$ substring of $Y(\delta^{\prime})$ repeats
itself every $h_{1}$ entry. Since the first length-$h_{1}$-substring of this
substring has weight 1, so does every other length-$h_{1}$-substring of this
substring which lies within it. Finally the length-$h_{1}$ substrings of
$Y(\delta^{\prime})$ starting at positions to the right of $h_{1}h_{2}-2h_{1}$
also have weight $1$ due to the presence of at least $h_{1}-1$ subsequent
$0$s. So our sum becomes:

$\sum_{t=0}^{v-1}x_{t}y_{t+\delta}=\sum_{t=0}^{(h_{2}-1)h_{1}-1}x_{t}y_{t+\delta}=\sum_{t=0}^{h_{1}-1}y_{t+\delta}=1$

We have shown that this sum equals $1$ for all
$\delta\in\\{1,\dots,h_{1}h_{2}h_{3}h_{4}\\}$. So
$\Delta(A,B)=\mathbb{Z}_{h_{1}h_{2}h_{3}h_{4}+1}\setminus\\{0\\}$ and hence
$\\{A,B\\}$ forms a classical
($h_{1}h_{2}h_{3}h_{4},2,h_{1}h_{3},h_{2}h_{4},1,1$)-GSEDF in
$\mathbb{Z}_{h_{1}h_{2}h_{3}h_{4}+1}$. ∎

As one special case of this, we obtain Construction 3.8 of [6]

######  Theorem 6.2.

Let $k_{1},k_{2}\in\mathbb{N}$, then $\\{0,1,\dots,k_{1}-1\\}$ and
$\\{k_{1},2k_{1},\dots,k_{1}k_{2}\\}$ form a classical
($k_{1}k_{2}+1,2,k_{1},k_{2},1,1$)-GSEDF in $\mathbb{Z}_{k_{1}k_{2}+1}$.

###### Proof.

We take $h_{1}=k_{1},h_{2}=k_{2},h_{3}=h_{4}=1$ in the above theorem. ∎

As another special case, we obtain Theorem 5.1 of [4]:

######  Theorem 6.3.

Let $a\in\mathbb{N}$. Then $A=\\{0,\dots,a-1\\}\cup\\{2a,2a+1,\dots,3a-1\\}$
and $B=\cup_{i=1}^{a}\\{(4i-1)a,4ia\\}=\\{3a,4a,7a,8a,\dots,(4a-1)a,4a^{2}\\}$
form a classical ($4a^{2}+1,2,2a,1$)-SEDF in $\mathbb{Z}_{4a^{2}+1}$.

###### Proof.

We take $h_{1}=a$, $h_{2}=2$, $h_{3}=2$ and $h_{4}=a$ in the above theorem. ∎

We now state a general result for when the above Theorem gives a classical
SEDF.

######  Corollary 6.4.

Let $h_{1},h_{2},h_{3},h_{4}\in\mathbb{N}$, such that $h_{1}h_{3}=h_{2}h_{4}$.
Then there exists a classical $((h_{1}h_{3})^{2}+1,2,h_{1}h_{3},1)$-SEDF in
$\mathbb{Z}_{(h_{1}h_{3})^{2}+1}$ with sets given by
$A=\cup_{i=0}^{h_{3}-1}\\{ih_{1}h_{2}+\alpha:0\leq\alpha\leq h_{1}-1\\}$ and
$B=\cup_{i=0}^{h_{4}-1}\\{ih_{1}h_{2}h_{3}+h_{1}h_{2}(h_{3}-1)+\beta
h_{1}:1\leq\beta\leq h_{2}\\}$.

We observe that the recursive construction in Theorem 5.6 (and hence Theorem
5.3) of [4] can also be proved using sequences; we omit the details.

##  7 Applications in communications and cryptography

We end by outlining some of the applications in communications and
cryptography of the objects presented in this paper.

Non-disjoint PSEDFs have applications to optical orthogonal codes (OOCs) [5].
OOCs are sets of binary sequences used in optical multi-access communication
[3]. For distinct binary sequences $X=(x_{t})_{t=0}^{v-1}$ and
$Y=(y_{t})_{t=0}^{v-1}$, the autocorrelation of $X$ is a measure of how much
it collides with shifts of itself ($\sum_{t=0}^{v-1}x_{t}x_{t+\delta}$,
$1\leq\delta\leq v-1$), while the cross-correlation of $X$ and $Y$ is a
measure of how much $X$ collides with the shifts of $Y$
($\sum_{t=0}^{v-1}x_{t}y_{t+\delta}$, $0\leq\delta\leq v-1$). Sequences $X$
and $Y$ are said to _collide_ in position $i$ if $x_{i}=1=y_{i}$. The
following definitions follow [5].

######  Definition 7.1.

Let $v,w,\lambda_{a},\lambda_{c}$ be non-negative integers with $v\geq 2$,
$w\geq 1$. Let ${\cal{C}}=\\{X_{0},\ldots,X_{N-1}\\}$ be a family of $N$
binary sequences of length $v$ and weight $w$. Then ${\cal{C}}$ is a (constant
weight) $(v,w,\lambda_{a},\lambda_{c})$-OOC of size $N\geq 1$ if, writing
$X=(x_{i})_{i=0}^{v-1}$, $Y=(y_{i})_{i=0}^{v-1}$ (indices modulo $v$):

  * (i)

$\displaystyle{\sum_{t=0}^{v-1}}x_{t}x_{t+\delta}\leq\lambda_{a}\mbox{ for any
}X\in{\cal{C}},0<\delta\leq v-1$, and

  * (ii)

$\displaystyle{\sum_{t=0}^{v-1}}x_{t}y_{t+\delta}\leq\lambda_{c}\mbox{ for any
}X,Y\in{\cal{C}},0\leq\delta\leq v-1$.

In other words, ${\cal{C}}$ is a $(v,w,\lambda_{a},\lambda_{c})$-OOC if auto-
correlation values are at most $\lambda_{a}$ and cross-correlation values are
at most $\lambda_{c}$.

Via Definition 2.26, OOCs can equivalently be expressed as subsets of
$\mathbb{Z}_{v}$ (see [5]). For each sequence $X_{i}$, let $A_{i}$ be the set
of integers modulo $v$ denoting the positions of the non-zero bits. The auto-
correlation condition becomes

$|A_{i}\cap(A_{i}+\delta)|\leq\lambda_{a}\mbox{ for all
$\delta\in\mathbb{Z}_{v}\setminus\\{0\\}$}$

i.e. any non-zero $\delta$ occurs in $\Delta(A_{i})$ at most $\lambda_{a}$
times, while the cross-correlation condition becomes

$|A_{i}\cap(A_{j}+\delta)|\leq\lambda_{c}\mbox{ for all
$\delta\in\mathbb{Z}_{v}$}$

i.e. any $\delta$ occurs in $\Delta(A_{i},A_{j})$ most $\lambda_{c}$ times.

For applications, OOCs are required with low cross-correlation; in [20] it is
stated that the “performance figure of merit” is the ratio between weight and
cross-correlation. In [5], the following was proved:

######  Proposition 7.2.

If ${\cal{C}}=\\{X_{0},\ldots,X_{N-1}\\}$ is a
$(v,w,\lambda_{a},\lambda_{c})$-OOC with $|{\cal{C}}|\geq 2$, then
$\lambda_{c}\geq\frac{w^{2}}{v}$. Moreover, a
$(v,w,\lambda_{a},\lambda_{c})$-OOC meeting the bound of (ii) with equality is
a non-disjoint $(v,N,w,\frac{w^{2}}{v})$-PSEDF in $\mathbb{Z}_{v}$.

All non-disjoint PSEDFs from Theorem 3.4 yield OOCs which satisfy the
conditions of Proposition 7.2 and hence have lowest-possible cross-
correlation.

In Definition 7.1, all sequence weights (and hence all corresponding set-sizes
in $\mathbb{Z}_{v}$) are equal. There is also a variable weight version of the
OOC, called a VW-OOC, in which sequence weights are permitted to vary. By the
natural sequence/subset correspondence of Definition 2.26, non-disjoint
GPSEDFs in $\mathbb{Z}_{v}$ yield examples of VW-OOCs (though we do not have
an analogue of Proposition 7.2). The following definition follows that of [3].

######  Definition 7.3.

Let $\mathcal{C}=\\{C_{a}:0\leq a\leq N-1\\}$ be a set of $N$ binary sequences
of length $v$, where $C_{a}=(c_{a}(t))_{t=0}^{v-1}$. Then $\mathcal{C}$ is a
$(v,W,\Lambda,\lambda_{c},R)$-VW-OOC with $W=\\{w_{1},\ldots,w_{m}\\}$,
$\Lambda=\\{\lambda_{a}(1),\ldots,\lambda_{a}(m)\\}$, and
$R=\\{r_{1},\ldots,r_{m}\\}$ if the following three conditions are satisfied:

  * (i)

there are exactly $r_{i}N$ codewords with weight $w_{i}$ for $1\leq i\leq m$,
where $r_{1}+\cdots+r_{m}=1$ and $r_{j}\geq 0$ for $1\leq j\leq m$;

  * (ii)

the autocorrelation of $C_{a}$ with weight $w_{i}$ in $C$ is upper bounded by
some positive integer $\lambda_{a}(i)$;

  * (iii)

the cross-correlation between $C_{a}$ and $C_{b}$ with $a\neq b$ in $C$ is
upper bounded by some positive integer $\lambda_{c}$.

All constructions of non-disjoint GPSEDFs in $\mathbb{Z}_{v}$ yield
corresponding VW-OOCs. Moreover, our approaches can be adapted to give new
constructions for VW-OOCs which do not have the GPSEDF property. We present an
example of such a construction, in which the VW-OOCs have lowest-possible
$\lambda_{c}=1$. (As with standard OOCs, low cross-correlation is a priority
for VW-OOCs). These are distinct from known constructions in [3] and [19].

######  Theorem 7.4.

Let $a_{1},\ldots,a_{m}$ be distinct divisors of $v$ such that for each $i\neq
j$, $v=lcm(a_{i},a_{j})$. For $1\leq i\leq m$, define the binary sequence
$X_{i}=(x_{t})_{t=0}^{v-1}$ where:

$x_{t}=\begin{cases}1,&t=la_{i}\quad(0\leq l\leq\frac{v}{a_{i}}-1)\\\
0,&\text{otherwise}\end{cases}$

Then $\\{X_{1},\ldots,X_{m}\\}$ form a VW-OOC in which $N=m$,
$r_{i}=\frac{1}{m}$, $w_{i}=\frac{v}{a_{i}}$, $\lambda_{a}(i)=\frac{v}{a_{i}}$
and $\lambda_{c}=1$.

###### Proof.

By construction, there is one sequence $X_{i}$ of each distinct weight
$w_{i}=\frac{v}{a_{i}}$, so $r_{i}=\frac{1}{m}$. Observe that the subset
$A_{i}$ of $\mathbb{Z}_{v}$ corresponding to the sequence $X_{i}$ is the
subgroup $A_{i}=a_{i}\mathbb{Z}_{v}$. The internal difference multiset
$\Delta(A_{i})$ comprises each element of $A_{i}$ precisely $|A_{i}|$ times
and so also $\lambda_{a}(i)=\frac{v}{a_{i}}$. By Lemma 4.7, for any pair
$i\neq j$, $\Delta(A_{i},A_{j})$ comprises $\frac{v}{lcm(a_{i},a_{j})}=1$ copy
of each element of $gcd(a_{i},a_{j})\mathbb{Z}_{v}\subseteq\mathbb{Z}_{v}$ and
$0$ copies of $\mathbb{Z}_{v}\setminus gcd(a_{i},a_{j})\mathbb{Z}_{v}$, so
$\lambda_{c}=1$. ∎

######  Example 7.5.

Let $v=p_{1}p_{2}\ldots p_{m}$ where the $p_{i}$ are distinct primes ($1\leq
i\leq m$). For $1\leq i\leq m$, let $a_{i}=\frac{v}{p_{i}}$. Clearly for
$i\neq j$, $lcm(a_{i},a_{j})=v$, so we may apply the construction of Theorem
7.4.
Specifically, let $v=30=2\cdot 3\cdot 5$, where $a_{1}=6$, $a_{2}=10$ and
$a_{3}=15$. Then $N=3$ and we obtain a
$(30,\\{2,3,5\\},\\{2,3,5\\},1,\\{\frac{1}{3},\frac{1}{3},\frac{1}{3}\\})$ VW-
OOC.

Theorem 7.4 can easily be extended, using Lemma 4.7(ii) and the approach of
Theorem 4.9, to yield VW-OOCs with larger weights and larger $\lambda_{c}$, by
taking suitable unions of cosets of subgroups of $\mathbb{Z}_{v}$.

In a different communications context, the sequence version of a non-disjoint
GPSEDF in $\mathbb{Z}_{v}$ will satisfy the requirement for a set of periodic
binary sequences (with common period $v$, or some divisor of $v$) to be
_pairwise shift invariant_ [22]. A binary sequence $S=(x_{i})$ (of unspecified
length) is said to be periodic with period $L$ if $x_{i}=x_{i+L}$ for all
$i\geq 1$ (with $L$ smallest possible).

######  Definition 7.6 ([22]).

Let $S_{1},\ldots,S_{k}$ be binary sequences with a common period $L$; denote
the $t$-th entry of $S_{i}$ by $S_{i}(t)$. Their $k$-wise Hamming cross-
correlation for relative shifts $\tau_{1},\ldots,\tau_{k-1}$ is defined as

$H_{S_{1},\ldots,S_{k}}(\tau_{1},\ldots,\tau_{k-1})=\sum_{t=0}^{L-1}S_{1}(t)S_{2}(t+\tau_{1})\ldots
S_{k}(t+\tau_{k-1})$

(the normalized version is
$\hat{H}_{S_{1},\ldots,S_{k}}=\frac{1}{L}H_{S_{1},\ldots,S_{k}})$. For $k=2$,
this is the usual Hamming cross-correlation. This is called shift invariant
(SI) if $\hat{H}_{S_{1},\ldots,S_{k}}$ is equal to a constant; a set of
sequences is completely $SI$ if this is constant for all choices of $k$
sequences and all $k$; pairwise SI if the 2-wise Hamming cross-correlation is
SI for all pairs.

In defining multiple access protocols, it can be desirable to have binary
sequences which are completely SI; for some applications it is of interest to
relax the condition to the pairwise case. Under certain conditions, a set of
pairwise SI sequences in fact satisfies the stronger property of being
completely SI:

######  Theorem 7.7.

[Theorem 3, [22]] Let $p$ be a prime. For binary sequence $S$ with period $L$,
its duty factor is defined to be $\frac{1}{L}\sum_{i=0}^{L-1}S(i)$. If $K$
pairwise SI protocol sequences with duty factors $\frac{n_{i}}{p}$, for
$i=1,2,\ldots,K$ have a common minimum period $p^{K}$ , then they are
completely SI.

All of our non-disjoint GPSEDFs in $\mathbb{Z}_{v}$ yield examples of pairwise
SI sequences with common period dividing $v$, and some of our constructions
(e.g. Corollary 3.6(i)) satisfy the condition of Theorem 7.7 to be completely
SI. Conversely, the constructions of pairwise SI sequences with common period
$L$ in [22] (defined via cyclotomic polynomials) give examples of non-disjoint
GPSEDFs in $\mathbb{Z}_{L}$.

######  Example 7.8.

Applying the non-disjoint GPSEDF construction of Corollary 4.10 in
$\mathbb{Z}_{30}$ with $a_{1}=6,a_{2}=15$ and $a_{3}=10$ yields Example 1 of
[22].

Finally, the classical two-set SEDFs obtainable from Theorem 6.1 and Corollary
6.4 have applications to classical circular external difference families
(CEDFs) and circular AMD codes [16, 18, 15], in particular the strong version
of these (SCEDFs). These are recently-introduced structures used in
cryptography to construct non-malleable threshold schemes. Classical two-set
SEDFs give examples of classical two-set SCEDFs; it has been shown that no
more than two sets are possible in classical SCEDF [18]. We note that, if the
non-disjoint version of the SCEDF is defined in the natural way, then any non-
disjoint PSEDF yields a non-disjoint SCEDF, and hence non-disjoint SCEDFs
exist with any number of sets.

##  8 Conclusion

We end with a table summarising the constructive and structural results
presented in this paper. We hope that these results will stimulate further
research in the area.

In the table, we use the following abbreviations; Thm: Theorem, Prop:
Proposition, Cor: Corollary and Lem: Lemma.

| Constructions | Structural Results
---|---|---
Classical SEDF | Thm 6.3, Cor 6.4 |
Classical PSEDF |  | Thm 2.22
Classical GSEDF | Thm 6.1, Thm 6.2 | Thm 2.23(ii)
Classical GEDF | Thm 4.12(ii) |

Table 1: A list of the classical results included in the paper

| Constructions | Structural Results
---|---|---
Non-Disjoint PSEDF | Thm 3.4, Cor 3.5, | Prop 2.7(iii)
| Cor 3.6, Cor 4.4(i), Thm 5.1 |
Non-Disjoint GPSEDF | Prop 2.12(ii), Prop 2.13(v), Thm 2.25, | Prop 2.13(v),
| Thm 3.2, Cor 3.3, Thm 3.7, | Thm 2.24
| Cor 3.8, Thm 3.10, Thm 4.3, |
| Cor 4.4, Lem 4.7, Thm 4.9, |
| Cor 4.10, Thm 4.12(i), Cor 5.3(i) |
Non-disjoint GSEDF | Prop 2.12(ii), Cor 5.3(iii) | Thm 2.23(i)
Non-disjoint MGPSEDF | Thm 3.12, Cor 5.3(ii) | Thm 2.24(iv,v)
Non-disjoint MGSEDF | Cor 5.3(iv) |

Table 2: A list of the non-disjoint results included in the paper

### Acknowledgements

The first author was funded by EPSRC grant EP/X021157/1. The second author was
funded by the London Mathematical Society grant URB-2023-75.

## References

  * [1] J. Bao, L. Ji, R. Wei and Y. Zhang, New existence and nonexistence results for strong external difference families, Discrete Math. 341 (2018) 1798-1805.
  * [2] M. Buratti, Old and new designs via difference multisets and strong difference families, J. Combin. Des. 7 (1999), 406–425.
  * [3] J-H. Chung and K. Yang, New Families of Optimal Variable-Weight Optical Orthogonal Codes With High Weights, IEEE Trans. Inform. Theory, 61 (2015), 4511-4517.
  * [4] S. Huczynska, C. Jefferson and S. Nepšinská, Strong external difference families in abelian and non-abelian groups, Cryptogr. Commun. 13 (2021), 331–341.
  * [5] S. Huczynska and S-L. Ng, Non-disjoint strong external difference families exist with any number of sets, Archiv der Mathematik (to appear).
  * [6] S. Huczynska and M.B. Paterson, Weighted external difference families and R-optimal AMD codes, Discrete Math. 342 (2019), 855-867.
  * [7] J. Jedwab and S. Li, Construction and nonexistence of strong external difference families, J. Algebraic Combin. 49 (2019), 21–48.
  * [8] K. H. Leung, S. Li and T. F. Prabowo, Nonexistence of strong external difference families in abelian groups of order being product of at most three primes, J. Combin. Theory Ser. A 178 (2021), Paper No. 105338, 27 pp.
  * [9] K. H. Leung and T. F. Prabowo, Some nonexistence results for (v, m, k, pq)-strong external difference families, J. Combin. Theory Ser. A 187 (2022), Paper No. 105575, 26 pp.
  * [10] X. Lu, X. Niu and H. Cao, Some results on generalized strong external difference families. Des. Codes Crypt., 86 (2018), 2857–2868.
  * [11] W. J. Martin and D. R. Stinson, Some nonexistence results for strong external difference families using character theory, Bull. Inst. Combin. Appl., 80 , 79-92 (2017).
  * [12] A. J. Menezes, P.C. van Oorschot and S.A.Vanstone, Handbook of Applied Cryptography, CRC Press Series on Discrete Mathematics and its Applications. CRC Press, Boca Raton, FL (1997).
  * [13] W. Ogata, K. Kurosawa, D.R. Stinson, H. Saido, New combinatorial designs and their applications to authentication codes and secret sharing schemes, Discrete Math. 279 (2004) 383–405.
  * [14] M. B. Paterson and D. R. Stinson, Combinatorial characterizations of algebraic manipulation detection codes involving generalized difference families, Discrete Math. 339, (2016) 2891–2906.
  * [15] M. B. Paterson and D. R. Stinson, Circular external difference families, graceful labellings and cyclotomy, ArXiV preprint.
  * [16] S. Veitch and D. R. Stinson. Unconditionally secure non-malleable secret sharing and circular external difference families, Des. Codes Cryptogr. (to appear)
  * [17] J. Wen, M. Yang, F. Fu and K. Feng, Cyclotomic construction of strong external difference families in finite fields, Des. Codes Cryptogr. 86 (2018), 1149–1159.
  * [18] H. Wu, J. Yang and K. Feng. Circular external difference families: construction and nonexistence, ArXiV preprint.
  * [19] G. C. Yang, Variable weight optical orthogonal codes for CDMA networks with multiple performance requirements, IEEE Trans. Commun. 44 (1996), 47-55.
  * [20] G. C Yang and T. E. Fuja, Optical Orthogonal Codes with Unequal Auto- and Cross- Correlation Constraints, IEEE Trans. Inf Theory 41 (1995), 96-106.
  * [21] G. Zappa, Partitions and other coverings of finite groups, Illinois Journal of Mathematics 47 (2003), 571–580.
  * [22] Y. Zhang, K. W. Shum and W. S. Wong, On Pairwise Shift-Invariant Protocol Sequences, IEEE Communications Letters 13, (2009), 453-455.