A generalization of combinatorial designs and related codes

Abstract

In this paper we study a certain generalization of combinatorial designs related to almost difference sets, namely the t-adesign, which was coined by Ding (Codes from difference sets, 2015). It is clear that 2-adesigns are partially balanced incomplete block designs which naturally arise in many combinatorial and statistical problems. We discuss some of their basic properties and give several constructions of 2-adesigns (some of which correspond to new almost difference sets and some to new almost difference families), as well as two constructions of 3-adesigns. We discuss basic properties of the incidence matrices and make an initial investigation into the codes which they generate. We find that many of the codes have good parameters in the sense they are optimal or have relatively high minimum distance.

1 Introduction

Combinatorial designs have extensive applications in many fields, including finite geometry [6, 17], design of experiments [3, 14], cryptography [5, 22], and authentication codes and secret sharing schemes [20, 22]. We will assume some familiarity with combinatorial design theory. A t-$(v,k,\lambda )$ design (with $v>k>t>0$) is an incidence structure $(V,{\mathcal {B}})$ where V is a set of v points and ${\mathcal {B}}$ is a collection of k-subsets of V (called blocks), such that any t-subset of V is contained in exactly $\lambda$ blocks [22]. When $t=2$, a t-design is sometimes referred to as a balanced incomplete block design. Denoting the number of blocks by b and the number of blocks containing a given point by r, the identities

$$\begin{aligned} bk=vr \end{aligned}$$

and

$$\begin{aligned} r(k-1)=(v-1)\lambda \end{aligned}$$

restrict the possible parameter sets. A t-$(v,k,\lambda )$ design in which $b=v$ and $r=k$ is called symmetric, and any two blocks meet in $\lambda$ points. A t-$(v,k,\lambda )$ design is called quasi-symmetric if there are exactly two intersection numbers among pairs of blocks. The dual $(V,{\mathcal {B}})^{\perp }$ of an incidence structure $(V,{\mathcal {B}})$ is the incidence structure $({\mathcal {B}},V)$ with the roles of points and blocks interchanged. A symmetric incidence structure is always isomorphic to its dual.

Difference sets [16] and almost difference sets [19] also have applications in many areas such as digital communications [12, 26], sequence design [23, 25], and CDMA and cryptography [5]. We will also assume familiarity with difference sets and almost difference sets. Let G be a finite additive group with identity 0. Let k and $\lambda$ be positive integers such that $2\le k < v$. A $(v,k,\lambda )$ difference set in G is a subset $D \subseteq G$ that satisfies the following properties:

• 1. $|D|=k$,

• 2. the multiset $\{x-y \mid x,y \in D, x \ne y \}$ contains every member of $G-\{0\}$ exactly $\lambda$ times.

Almost difference sets are a generalization of difference sets. A $(v,k,\lambda ,t)$ almost difference set in G is a subset $D \subseteq G$ that satisfies the following properties:

• 1. $|D|=k$,

• 2. the multiset $\{x-y \mid x,y \in D, x \ne y\}$ contains t members of $G-\{0\}$ which appear $\lambda$ times and $v-1-t$ members of $G-\{0\}$ which appear $\lambda +1$ times.

Our motivation for studying t-adesigns is in constructing linear codes. Also, due to their having extensive applications, it is worthwhile to study the combinatorial objects arising from almost difference sets. In Sect. 2 we introduce the generalizations and discuss some basic properties. In Sect.  3 we give three constructions of 2-adesigns from quadratic residues, several constructions of 2-adesigns which are almost difference families are given in Sect. 4, and some constructions of 2-adesigns from symmetric t-designs are given in Sect. 5. In Sect. 6 we discuss 3-adesigns and two constructions are given, and in Sect.  7 we discuss the codes of t-adesigns (and some related structures), and include some of the codes with good parameters in a table. Section 8 concludes the paper.

2 Preliminaries

Let G be an additive group of order v. A k-element subset $D \subseteq G$ has difference levels $\mu _{1} < \cdots < \mu _{s}$ if there exist integers $t_{1},\ldots ,t_{s}$ such that the multiset

$$\begin{aligned} M=\{g-h \mid g,h \in D\} \end{aligned}$$

contains exactly $t_{i}$ members of $G-\{0\}$ each with multiplicity $\mu _{i}$ for all i, $1 \le i \le s$. We will denote the $t_{i}$ members of the multiset M with multiplicity $\mu _{i}$ by $T_{i}$. Note that the $T_{i}$’s form a partition of $G-\{0\}$. It is easy to see that in the case where $s=1$, D is a difference set [16], and in the case where $s=2$ and $\mu _{2}=\mu _{1}+1$, D is an almost difference set [19]. In this correspondence we are concerned only with those structures having two difference levels, and all groups are assumed to be additive. The basic equation describing a k-element subset $D \subseteq G$ with difference levels $\mu _{1}<\mu _{2}$ is given by

$$\begin{aligned} \mu _{1}t+\mu _{2}(v-1-t)=k(k-1). \end{aligned}$$

(1)

Let V be a v-set and ${\mathcal {B}}$ a collection of subsets of V, called blocks, each having cardinality k. If there are positive integers $\mu _{1} < \mu _{2}$ such that every subset of V of cardinality t is incident with exactly $\mu _{i}$ blocks for $i=1$ or 2, and for each $i,i=1,2$, there exists a subset of V of cardinality t that is incident with exactly $\mu _{i}$ blocks, then we say that the incidence structure $(V,{\mathcal {B}})$ has t-levels $\mu _{1} < \mu _{2}$. We denote $|{\mathcal {B}}|$ by b. An incidence structure $(V,{\mathcal {B}})$ is called symmetric if $b=v$. In the case where $s=2$, $(V,{\mathcal {B}})$ is a partially balanced incomplete block design, and if $\mu _{2}=\mu _{1}+1$, we call $(V,{\mathcal {B}})$ a t-$(v,k,\mu _{1})$ adesign (or simply a t-adesign), which was coined by Ding in [10]. It is easy to see that in the case where $s=1$, $(V,{\mathcal {B}})$ is simply a t-design [22].

We call the set $\{D+g \mid g \in G\}$ of translates of D, denoted by Dev(D), the development of D. We have the following lemmas whose proofs are omitted as they are simple counting exercises.

Lemma 2.1

Let D be a $(v,k,\lambda )$ almost difference set in an Abelian group G. Then (G, Dev(D)) is a 2-$(v,k,\lambda )$ adesign.

Let $(V,{\mathcal {B}})$ be an incidence structure with t-levels $\mu _{1} < \mu _{2}$. Let A be a v by b matrix whose rows and columns are indexed by points and blocks respectively and whose (i, j)-th entry is 1 if the point corresponding to the ith row is incident with the block corresponding to the jth row, and 0 otherwise. We call A the incidence matrix of $(V,{\mathcal {B}})$. We will denote the $n\times n$ identity and all-one matrices by $I_{n}$ and $J_{n}$ respectively, or, when it is clear from the context, simply by I and J.

Lemma 2.2

Let D be a k-subset of an Abelian group G of cardinality v with the two difference levels $\mu _{1} < \mu _{2}$. Let A be the $v \times v$ incidence matrix of the symmetric incidence structure (G, Dev(D)). Then

$$\begin{aligned} A^{T}A=AA^{T}=kI+\mu _{1}A_{1}+\mu _{2}(J-A-I). \end{aligned}$$

(2)

Next, we give some constructions of 2-adesigns from almost difference sets.

3 Constructions of 2-adesigns from quadratic residues

Cyclotomic classes have proven to be a powerful tool for constructing difference sets and almost difference sets, e.g. see [12, 13, 19]. Let q be a prime power, ${\mathbb {F}}_{q}$ a finite field, and e a divisor of $q-1$. For a primitive element $\alpha$ of ${\mathbb {F}}_{q}$ let $D_{0}^{e}$ denote $\langle \alpha ^{e} \rangle$, the multiplicative group generated by $\alpha ^{e}$, and let

$$\begin{aligned} D_{i}^{e} = \alpha ^{i}D_{0}^{e}, \text { for } i=1,2,\ldots ,e-1. \end{aligned}$$

We call $D_{i}^{e}$ the cyclotomic classes of order e. The cyclotomic numbers of order e are defined to be

$$\begin{aligned} (i,j)_{e} = \left| D_{i}^{e} \cap (D_{j}^{e} + 1) \right| . \end{aligned}$$

It is easy to see there are at most $e^{2}$ different cyclotomic numbers of order e. When it is clear from the context, we simply denote $(i,j)_{e}$ by (i, j). The cyclotomic numbers (h, k) of order e have the following properties [7]:

$$\begin{aligned} (h,k)= & {} (e-h,k-h), \end{aligned}$$

(3)

$$\begin{aligned} (h,k)= & {} {\left\{ \begin{array}{ll} (k,h), &{} \text {if } f \text { even},\\ (k+\frac{e}{2},h+\frac{e}{2}), &{} \text {if } f \text { odd}. \end{array}\right. } \end{aligned}$$

(4)

Our first three constructions make use of quadratic residues. We will need the following lemma [7].

Lemma 3.1

If $q \equiv 1$ (mod 4) then the cyclotomic numbers of order two are given by

$$\begin{aligned} (0,0)= & {} \frac{q-5}{4}, \\ (0,1)= & {} (1,0) = (1,1) = \frac{q-1}{4}. \end{aligned}$$

If $q \equiv 3$ (mod 4) then the cyclotomic numbers of order two are given by

$$\begin{aligned} (0,1)= & {} \frac{q+1}{4}, \\ (0,0)= & {} (1,0) = (1,1) = \frac{q-3}{4}. \end{aligned}$$

We are ready to give our first construction.

Theorem 3.2

Let q be an odd prime power and $\alpha$ a primitive member of ${\mathbb {F}}_{q}$. Define $C_{i}=\{z\in {\mathbb {Z}}_{q-1} \mid \alpha ^{z}\in D_{i}^{2}-1\}$ for $i=0,1$. Then the incidence structure $({\mathbb {Z}}_{q-1}\cup \{\infty \},Dev^{\infty }(C_{0}) \cup Dev(C_{1}))$, where $Dev^{\infty }(C_{0})$ denotes the blocks of $Dev(C_{0})$ each modified by adjoining the point “$\infty$”, is a 2-$(q,\frac{q-1}{2},\frac{q-5}{2})$ adesign.

Proof

We will denote $\{\alpha ^z\mid z\in C_{i}\}$ by $\alpha ^{C_{i}}$. For $w \in {\mathbb {Z}}_{q-1}$ we have

$$\begin{aligned} \left| C_{0} \cap (C_{0}+w) \right| =\left| \alpha ^{C_{0}} \cap \alpha ^{C_{0}+w} \right| \end{aligned}$$

which, since $\alpha ^{z}$ is nonzero and

$$\begin{aligned} |((D_{0}^{2}-1)-\{0\})\cap ((D_{0}^{2}-\alpha ^{w})-\{0\}) |=|((D_{0}^{2}-\{1\})-1)\cap ((\alpha ^{w}D_{0}^{2}-\{\alpha ^{w}\})-\alpha ^{w})|, \end{aligned}$$

is

$$\begin{aligned} {\left\{ \begin{array}{ll} \left| (D_{0}^{2}-\{1\})\cap (D_{0}^{2}-\{\alpha ^{w}\}+(1-\alpha ^{w}))\right| &{} \text { if } w \text { even},\\ \left| (D_{0}^{2}-\{1\})\cap (D_{1}^{2}-\{\alpha ^{w}\}+(1-\alpha ^{w}))\right| &{} \text { if } w \text { odd}.\end{array}\right. } \end{aligned}$$

Since $\alpha ^{w}(1-\alpha ^{w})^{-1}=(1-\alpha ^{w})^{-1}-1$, this becomes

$$\begin{aligned}{\left\{ \begin{array}{ll} \left| (D_{0}^{2}-\{(1-\alpha ^{w})^{-1}\})\cap (D_{0}^{2}-\{(1-\alpha ^{w})^{-1}-1\}+1)\right| &{} \text { if } w \text { even},\\ \left| (D_{0}^{2}-\{(1-\alpha ^{w})^{-1}\})\cap (D_{1}^{2}-\{(1-\alpha ^{w})^{-1}-1\}+1)\right| &{} \text { if } w \text { odd},\end{array}\right. } \end{aligned}$$

which simplifies to

$$\begin{aligned}{\left\{ \begin{array}{ll} \left| D_{0}^{2}\cap (D_{0}^{2}+1)-\{(1-\alpha ^{w})^{-1}\}\right| &{} \text { if } w \text { even},\\ \left| D_{0}^{2}\cap (D_{1}^{2}+1)-\{(1-\alpha ^{w})^{-1}\}\right| &{} \text { if } w \text { odd}.\end{array}\right. } \end{aligned}$$

There are four cases depending on the parity of w and whether $(1-\alpha ^{w})^{-1} \in D_{0}^{2}$ or $D_{1}^{2}$. By Theorem 3.1 we have

$$\begin{aligned} \left| C_{0} \cap (C_{0}+w) \right| ={\left\{ \begin{array}{ll} (0,0)-1 &{} \text { if } w \text { even and } (1-\alpha ^{w})^{-1}\in D_{0}^{2},\\ (0,0) &{} \text { if } w \text { even and } (1-\alpha ^{w})^{-1}\in D_{1}^{2},\\ (0,1)-1 &{} \text { if } w \text { odd and } (1-\alpha ^{w})^{-1}\in D_{0}^{2},\\ (1,0)-1 &{} \text { if } w \text { even and } (1-\alpha ^{w})^{-1}\in D_{0}^{2}.\end{array}\right. } \end{aligned}$$

Thus if $q \equiv 1($mod 4) then

$$\begin{aligned} \left| C_{0} \cap (C_{0}+w) \right| ={\left\{ \begin{array}{ll} \frac{q-9}{4} &{} \text { if } w \text { even and } (1-\alpha ^{w})^{-1}\in D_{0}^{2}, \\ \frac{q-5}{4} &{} \text { otherwise}, \end{array}\right. } \end{aligned}$$

and if $q \equiv 3 ($mod 4) then

$$\begin{aligned} \left| C_{0} \cap (C_{0}+w) \right| \!=\!{\left\{ \begin{array}{ll} \frac{q-3}{4} &{} \text { if } w \text { odd and } (1-\alpha ^{w})^{-1}\in D_{0}^{2} \text { or if } w \text { even and } (1-\alpha ^{w})^{-1}\in D_{1}^{2}, \\ \frac{q-7}{4} &{} \text { otherwise}. \end{array}\right. } \end{aligned}$$

Also, we have

$$\begin{aligned} \left| C_{1} \cap (C_{1}+w) \right| ={\left\{ \begin{array}{ll} \left| D_{1}^{2}\cap (D_{1}^{2}+1)+(1-\alpha ^{w})\right| &{} \text { if } w \text { even},\\ \left| D_{1}^{2}\cap (D_{1}^{2}+1)+(1-\alpha ^{w})\right| &{} \text { if } w \text { odd}.\end{array}\right. } \end{aligned}$$

Thus if $q \equiv 1 ($mod 4) then

$$\begin{aligned} \left| C_{1} \cap (C_{1}+w) \right| ={\left\{ \begin{array}{ll} \frac{q-5}{4} &{} \text { if } w \text { even and } (1-\alpha ^{w})^{-1}\in D_{1}^{2},\\ \frac{q-1}{4} &{} \text { otherwise}. \end{array}\right. } \end{aligned}$$

and if $q \equiv 3 ($mod 4) then

$$\begin{aligned} \left| C_{1} \cap (C_{1}+w) \right| ={\left\{ \begin{array}{ll} \frac{q+1}{4} &{} \text { if } w \text { odd and } (1-\alpha ^{w})^{-1}\in D_{1}^{2},\\ \frac{q-3}{4} &{} \text { otherwise}. \end{array}\right. } \end{aligned}$$

We need to compute the number of blocks of $({\mathbb {Z}}_{q-1},Dev(C_{0})\cup Dev(C_{1}))$ in which an arbitrary pair of points appear. Consider the incidence structures $({\mathbb {Z}}_{q-1},Dev(C_{i}))$ for $i=0,1$. Let $C_{i}^{\perp },(C_{i}+w)^{\perp }$ denote the points of the dual structures $(Dev(C_{i}),{\mathbb {Z}}_{q-1})$ corresponding to the blocks $C_{i},C_{i}+w$. We have that $({\mathbb {Z}}_{q-1},Dev(C_{i}))$ is a self-dual incidence structure and by Lemma 2.2 the number of blocks of $({\mathbb {Z}}_{q-1},Dev(C_{0}) \cup Dev(C_{1}))$ in which the points $C_{i}^{\perp },(C_{i}+w)^{\perp }$ appear is, if $q\equiv 1($mod 4),

$$\begin{aligned} {\left\{ \begin{array}{ll} \frac{q-9}{4}+\frac{q-1}{4}=\frac{2q-10}{4} &{} \text { if } w \text { even and } (1-\alpha ^{w})^{-1} \in D_{0}^{2},\\ \frac{q-5}{4}+\frac{q-5}{4}=\frac{2q-10}{4} &{} \text { if } w \text { even and } (1-\alpha ^{w})^{-1} \in D_{1}^{2},\\ \frac{q-5}{4}+\frac{q-1}{4}=\frac{2q-6}{4} &{} \text { otherwise}, \end{array}\right. } \end{aligned}$$

and if $q\equiv 3($mod 4),

$$\begin{aligned} {\left\{ \begin{array}{ll} \frac{q-3}{4}+\frac{q-3}{4}=\frac{2q-6}{4} &{} \text { if } w \text { odd and } (1-\alpha ^{w})^{-1} \in D_{0}^{2},\\ \frac{q-7}{4}+\frac{q+1}{4}=\frac{2q-6}{4} &{} \text { if } w \text { even and } (1-\alpha ^{w})^{-1} \in D_{1}^{2},\\ \frac{q-7}{4}+\frac{q-3}{4}=\frac{2q-10}{4} &{} \text { otherwise}. \end{array}\right. } \end{aligned}$$

It is easy to see that the block sizes of the incidence structures $({\mathbb {Z}}_{q-1},Dev(C_{0}))$ and $({\mathbb {Z}}_{q-1},Dev(C_{1}))$ are $\frac{q-3}{2}$ and $\frac{q-1}{2}$ respectively and that the number of blocks containing a given point in $({\mathbb {Z}}_{q-1},Dev(C_{0}))$ is $\frac{2q-6}{4}$. Then the incidence structure $({\mathbb {Z}}_{q-1}\cup \{\infty \},Dev^{\infty }(C_{0}) \cup Dev(C_{1}))$, where $Dev^{\infty }(C_{0})$ denotes the blocks of $Dev(C_{0})$ each modified by adjoining the point $\infty$, is a 2-adesign. $\square$

Note that appending the symbol “$\infty$” to certain blocks in a combinatorial design has been done before, e.g. see [18, Chapter 8 ]. Our constructions in this section also use this symbol only, rather than extending complimentary blocks to obtain a 3-design, we first consider various other ways of obtaining a set of blocks where any two have lengths differing by at most one, and then extend the shorter blocks to obtain a 2-adesign.

Example 3.3

With $q=11$ and $C_{i}$ defined as in Theorem 3.2 we get that $({\mathbb {Z}}_{10}\cup \{\infty \},Dev^{\infty }(C_{0}) \cup Dev(C_{1}))$ is a 2-(10, 5, 3) adesign with blocks:

The next two constructions will use the following lemmas.

Lemma 3.4

[1] Let p be a prime. The number of pairs of consecutive quadratic residues mod p is

$$\begin{aligned} N(p)=\frac{1}{4}\left( p-4-(-1)^{\frac{p-1}{2}}\right) \end{aligned}$$

and the number of pairs of consecutive quadratic non-residues mod p is

$$\begin{aligned} N'(p)=\frac{1}{4}\left( p-2+(-1)^{\frac{p-1}{2}}\right) . \end{aligned}$$

In the sequel we will sometimes use the following lemma without making reference to it.

Lemma 3.5

[2] Let $p\equiv 1 ($mod 4) be a prime. The the set of quadratic residues mod p forms a $\left( p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{2}\right)$ almost difference set in ${\mathbb {Z}}_{p}$.

Lemma 3.6

Let $p \equiv 1 ($mod 4) be a prime and $D \subseteq {\mathbb {Z}}_{p}$ be the set of quadratic residues. Two distinct points $x,y \in D$ occur together in exactly $\frac{p-5}{4}$ translates of D if and only if $x-y$ is a quadratic residue. Dually, $D+x$ and $D+y$ are translates of D with $x-y \in D$ if and only if $|(D+x)\cap (D+y)|=\frac{p-5}{4}$.

Proof

Let $x,y \in D$ be distinct. Denote $\frac{p-5}{4}$ by $\lambda$. Without loss of generality we can take $y=1$. Let

$$\begin{aligned} D, D+\alpha _{1},\ldots , D+\alpha _{\lambda -1} \end{aligned}$$

be precisely the $\lambda$ translates of D in which x and 1 appear together. Then

$$\begin{aligned} x=x_{1}+\alpha _{1}=\cdots =x_{\lambda -1}+\alpha _{\lambda -1} \end{aligned}$$

for some distinct quadratic residues $x_{1},\ldots ,x_{\lambda -1}$ and

$$\begin{aligned} 1=y_{1}+\alpha _{1}=\cdots =y_{\lambda -1}+\alpha _{\lambda -1} \end{aligned}$$

for some distinct quadratic residues $y_{1},\ldots ,y_{\lambda -1}$. Now suppose that $x-1$ is a quadratic non-residue. Then

$$\begin{aligned} x-1=x_{1}-y_{1}=\cdots =x_{\lambda -1}-y_{\lambda -1}. \end{aligned}$$

Since $p \equiv 1 ($mod 4) we have $(x-1)^{-1}$ is also a quadratic nonresidue. Then we have

$$\begin{aligned} 1=(x-1)^{-1}x-(x-1)^{-1}=(x-1)^{-1}x_{i}-(x-1)^{-1}y_{i} \end{aligned}$$

for $i=1,\ldots ,\lambda -1$. This gives precisely $\lambda$ pairs of consecutive non-residues, these being the only pairs of consecutive quadratic non-residues. But this contradicts Lemma 3.4, from which we have that the number of pairs of consecutive quadratic non-residues is $\lambda +1$. The condition is necessary and sufficient, and the dual argument follows from the fact that the 2-adesign $({\mathbb {Z}}_{p},Dev(D))$ is symmetric. $\square$

We are now ready to construct two more families of 2-adesigns.

Theorem 3.7

Let $p\equiv 1 ($mod 4) be a prime greater than 5, and let $D \subseteq {\mathbb {Z}}_{p}$ be the set of quadratic residues. Let ${\mathcal {B}}=\{b\cap D \mid b \in Dev(D),b\ne D\}$, and let ${\mathcal {B}}_{\infty }$ be the set containing all members of ${\mathcal {B}}$ of size $\frac{p-1}{4}$, as well as all members of ${\mathcal {B}}$ of size $\frac{p-5}{4}$ modified by adjoining the point $\infty$. Then $(D\cup \{\infty \},{\mathcal {B}}_{\infty })$ is a 2-$(\frac{p+1}{2},\frac{p-1}{4},\frac{p-9}{4})$ adesign.

Proof

Let $x,y \in D$ be distinct. Denote $\frac{p-5}{4}$ by $\lambda$ and $\frac{p-1}{2}$ by k. If x and y appear together in exactly $\lambda$ translates of D, then x and y appear together in exactly $\lambda$ blocks in ${\mathcal {B}}_{\infty }$. Similarly, if x and y appear together in $\lambda +1$ translates of D then x and y appear together in $\lambda +1$ blocks in ${\mathcal {B}}_{\infty }$. We want to show that x and $\infty$ appear together in exactly $\lambda$ blocks in ${\mathcal {B}}_{\infty }$. Without loss of generality, we can take $x=1$. There are $k-1$ blocks in ${\mathcal {B}}_{\infty }$ containing 1. Let

$$\begin{aligned} D, D+\alpha _{1},\ldots ,D+\alpha _{w} \end{aligned}$$

be precisely the translates of D containing 1. By Lemma 3.6, if $|D\cap (D+\alpha _{i})|=\lambda$, then $\alpha _{i}$ is a quadratic residue. If $y+\alpha _{i}=1$ then we have a pair $y,-\alpha _{i}$ of consecutive quadratic residues. By Lemma 3.4, the number of pairs of consecutive quadratic residues is exactly $\lambda$.

To see that there are pairs $x,y \in D$ of distinct points appearing in $\lambda -1$ blocks as well as those appearing in $\lambda$ blocks, suppose that $y_{1},\ldots ,y_{k-1}$ be the $k-1$ points in $D-\{1\}$. We can again, without loss of generality, take $x=1$. Suppose that 1 and $y_{i}$ appear together in exactly $\lambda$ translates of D for each i, $1\le i\le k-1$. Then $y_{i}-1 \in D$ for all $y_{i}$. By Lemma 3.4 this gives too many pairs of consecutive quadratic residues, which completes the proof. $\square$

Example 3.8

With $p=13$ we apply Theorem 3.7 and get that $(D\cup \{\infty \},{\mathcal {B}}_{\infty })$ is a 2-(7, 3, 1) adesign and ${\mathcal {B}}_{\infty }$ contains the following blocks:

Let ${\mathcal {B}}$ and ${\mathcal {B}}_{\infty }$ be defined as in Theorem 3.7. The second construction is the following.

Theorem 3.9

Let $p\equiv 1 ($mod 4) be a prime greater than 5, and let $D \subseteq {\mathbb {Z}}_{p}$ be the set of quadratic residues. Let $\bar{{\mathcal {B}}}_{\infty }$ be the set of complements of members of ${\mathcal {B}}_{\infty }$ in ${\mathbb {Z}}_{p}\cup \{\infty \}$. Then $(D\cup \{\infty \},\bar{{\mathcal {B}}}_{\infty })$ is a 2-$\left( \frac{p+1}{2},\frac{p+3}{4},\frac{p-1}{4}\right)$ adesign.

Proof

Let $x,y \in D\cup \{\infty \}$ be distinct. Denote $\frac{p-5}{4}$ by $\lambda$ and $\frac{p-1}{2}$ by k. Suppose x and y appear together in $\lambda$ blocks in ${\mathcal {B}}_{\infty }$. Then there are $\lambda$ blocks in $\bar{{\mathcal {B}}}_{\infty }$ not containing x or y. Also there are $k-1$ blocks in $\bar{{\mathcal {B}}}_{\infty }$ not containing x and $k-1$ blocks not containing y. Then the number of blocks in $\bar{{\mathcal {B}}}_{\infty }$ containing x and y is

$$\begin{aligned} |\bar{{\mathcal {B}}}_{\infty }|-(|\{b\in \bar{{\mathcal {B}}}_{\infty }\mid x \notin b\}|+|\{b \in \bar{{\mathcal {B}}}_{\infty } \mid y \notin b\}|)+|\{b\in \bar{{\mathcal {B}}}_{\infty }\mid x,y \notin b\}| \end{aligned}$$

which is easily seen to be $\lambda +1$. A similar calculation shows that if x and y appear together in $\lambda -1$ blocks in ${\mathcal {B}}_{\infty }$ then x and y appear together in $\lambda$ blocks $\bar{{\mathcal {B}}}_{\infty }$. $\square$

Example 3.10

With $p=13$ we apply Theorem 3.9 and get that $(D\cup \{\infty \},\bar{{\mathcal {B}}}_{\infty })$ is a 2-(7, 4, 3) adesign and $\bar{{\mathcal {B}}}_{\infty }$ contains the following blocks:

4 Constructions of 2-adesigns that are almost difference families

Almost difference families were studied by Ding and Yin in [11]. Suppsoe G is a finite Abelian group of order v in which the identity element is denoted “0”. Let k and $\lambda$ be positive integers such that $2\le k<v$. A $(v,k,\lambda )$ difference family in G is a collection of subsets $D_{0},\ldots ,D_{l}$ of G such that

• 1. $\left| D_{i}\right| =k$ for all $i,0\le i\le l$,

• 2. the multiset union $\cup _{i=1}^{l}\{x-y \mid x,y \in D_{i}, x \ne y\}$ contains each member of $G-\{0\}$ $\lambda$ times,

and a $(v,k,\lambda ,t)$ almost difference family is defined similarly only the multiset union $\cup _{i=1}^{l}\{x-y \mid x,y \in D_{i}, x \ne y\}$ contains t members of $G-\{0\}$ with multiplicity $\lambda$ and $v-t-1$ members of G with multiplicity $\lambda +1$.

It is trivial that an almost difference family is a 2-adesign. All of the 2-adesigns in this section are also almost difference families, however, our treatment will still be in terms of 2-adesigns.

Our next two constructions make use of quadratic residues. We will need the following lemma [7].

Lemma 4.1

Let $q=4f+1=x^{2}+4y^{2}$ be a prime power with $x,y \in {\mathbb {Z}}$ and $x \equiv 1$ (mod 4) (here, y is two-valued depending on the choice of the primitive root $\alpha$ defining the cyclotomic classes). The five distinct cyclotomic numbers of order four for odd f are

$$\begin{aligned} (0,0)= & {} (2,2) = (2,0) = \frac{q-7+2x}{16}, \\ (0,1)= & {} (1,3) = (3,2) = \frac{q+1+2x-8y}{16}, \\ (1,2)= & {} (0,3) = (3,1) = \frac{q+1+2x+8y}{16}, \\ (0,2)= & {} \frac{q+1-6x}{16}, \\ \text {all others}= & {} \frac{q-3-2x}{16}, \end{aligned}$$

and those for even f are

$$\begin{aligned} (0,0)= & {} \frac{q-11-6x}{16}, \\ (0,1)= & {} (1,0) = (3,3) = \frac{q-3+2x+8y}{16}, \\ (0,2)= & {} (2,0) = (2,2) = \frac{q-3+2x}{16}, \\ (0,3)= & {} (3,0) = (1,1) = \frac{q-3+2x-8y}{16}, \\ \text {all others}= & {} \frac{q+1-2x}{16}. \end{aligned}$$

When computing difference levels of a subset C of a group G, it is sometimes convenient to use the difference function which is defined as $d(w) = \left| C \cap (C+w)\right|$ where $C+w$ denotes the set $\{c+w \mid c\in C\}$. We are now ready to give our first construction of a 2-adesign that is a difference family.

Theorem 4.2

Let $q=4f+1=x^{2}+4y^{2}$ be a prime power with f odd. Let $C_{0} = D_{0}^{4} \cup D_{1}^{4}, C_{1}=D_{0}^{4} \cup D_{2}^{4}$, and $C_{2}=D_{0}^{4} \cup D_{3}^{4}$. Then $({\mathbb {F}}_{q},Dev(C_{0}) \cup Dev(C_{1}) \cup Dev(C_{2}))$ is a 2-$(q,\frac{q-1}{2},\frac{3q-11}{4})$ adesign.

Proof

Let $w^{-1} \in D_{h}^{4}$. First we let C denote $D_{i}^{4} \cup D_{i+1}^{4}$. Then when we expand $\left| C \cap (C+w)\right|$ we get

$$\begin{aligned} \left| D_{i+h}^{2} \cap (D_{i+h}^{2}+1) \right| + \left| D_{i+h}^{4} \cap (D_{i+h+1}^{4}+1) \right| + \left| D_{i+h+1}^{4} \cap (D_{i+h}^{4}+1) \right| +\left| D_{i+h+1}^{4} \cap (D_{i+h+1}^{4}+1) \right| \end{aligned}$$

whence

$$\begin{aligned} \left| C \cap (C+w)\right|= & {} (i+h,i+h) + (i+h,i+h+1) + (i+h+1,i+h) +(i+h+1,i+h+1) \\= & {} {\left\{ \begin{array}{ll} \frac{q-2y-3}{4} &{} \text {for } i = 0 \text { and } h=0 \text { or } 2, \\ \frac{q+2y-3}{4} &{} \text {for } i = 0 \text { and } h=1 \text { or } 3,\\ \frac{q-2y-3}{4} &{} \text {for } i = 3 \text { and } h=0 \text { or } 2,\\ \frac{q+2y-3}{4} &{} \text {for } i = 3 \text { and } h=1 \text { or } 3. \end{array}\right. } \quad (\text {by Lemmas 3.1 and 4.1}) \end{aligned}$$

We also have

$$\begin{aligned} \left| C_{1} \cap (C_{1}+w)\right|= & {} {\left\{ \begin{array}{ll}\ \frac{q-5}{4} &{} \text {for } h = 0 \text { or } 2, \\ ~\frac{q-1}{4} &{} \text {for } h = 1 \text { or } 3. \end{array}\right. } \end{aligned}$$

Now consider the incidence structures $({\mathbb {F}}_{q},DevC_{i})$ for $i=0,1,2$. Let $C_{i}^{\perp },(C_{i}+w)^{\perp }$ denote the points of the dual structures $(Dev(C_{i}),{\mathbb {F}}_{q})$ corresponding to the blocks $C_{i},C_{i}+w$. We have that $({\mathbb {F}}_{q},Dev(C_{i}))$ is a self-dual incidence structure and by Lemma 2.2 the number of blocks of $({\mathbb {F}}_{q},Dev(C_{0}) \cup Dev(C_{1}) \cup Dev(C_{2}))$ which the points $C_{i}^{\perp },(C_{i}+w)^{\perp }$ appear in is

$$\begin{aligned} {\left\{ \begin{array}{ll} \frac{3p-11}{4} &{} \text { if } w^{-1} \in D_{0}^{4}\cup D_{2}^{4},\\ \frac{3p-7}{4} &{} \text { if } w^{-1} \in D_{1}^{4}\cup D_{3}^{4}. \end{array}\right. } \end{aligned}$$

$\square$

Another construction is the following.

Theorem 4.3

Let $q=4f+1=x^{2}+4y^{2}$ be a prime power with f even and $x=1$ or $-3$. Then $({\mathbb {F}}_{q},Dev(D_{0}^{4}) \cup Dev(D_{2}^{4}))$ is a 2-$\left( q,\frac{q-1}{4},\frac{q-7-2x}{8}\right)$ adesign.

Proof

We have, by Lemma 4.1,

$$\begin{aligned} \left| D_{i}^{4} \cap (D_{i}^{4}+w)\right|= & {} \left| D_{h}^{4} \cap (D_{h}^{4}+1)\right| \\= & {} (i+h,i+h) \\= & {} {\left\{ \begin{array}{ll} \frac{q-11-6x}{16} &{} \text { if } h = 0,i=0 \text { or } h = 2,i=2, \\ \frac{q-3+2x-8y}{16} &{} \text { if } h = 1,i=0\text { or } h = 2,i=2,\\ \frac{q-3+2x}{16} &{} \text { if } h = 2,i=0\text { or } h = 3,i=2,\\ \frac{q-3+2x+8y}{16} &{} \text {for } h = 3,i=0\text { or } h = 0,i=2.\\ \end{array}\right. } \end{aligned}$$

Now consider the incidence structures $({\mathbb {F}}_{q},Dev(D_{i}^{4}))$ for $i=0,2$. Let $C_{i}^{\perp },(C_{i}+w)^{\perp }$ denote the points of the dual structures $(Dev(D_{i}^{4}),{\mathbb {F}}_{q})$ corresponding to the blocks $C_{i},C_{i}+w$. We have that $({\mathbb {F}}_{q},Dev(C_{i}))$ is a self-dual incidence structure and by Lemma 2.2 the number of blocks of $({\mathbb {F}}_{q},Dev(D_{0}^{4}) \cup Dev(D_{2}^{4}))$ which the points $C_{i}^{\perp },(C_{i}+w)^{\perp }$ appear in is

$$\begin{aligned} {\left\{ \begin{array}{ll} \frac{2q-14-4x}{16} &{} \text { if } w^{-1} \in D_{0}^{4}\cup D_{2}^{4},\\ \frac{2q-6+4x}{16} &{} \text { if } w^{-1} \in D_{1}^{4}\cup D_{3}^{4}.\end{array}\right. } \end{aligned}$$

Thus, we have $({\mathbb {F}}_{q},Dev(D_{0}^{4}) \cup Dev(D_{2}^{4}))$ is a 2-adesign whenever $x=1$, or $-3$. $\square$

We close this section with yet a few more constructions. Now let q be an odd prime power, and $C \subseteq {\mathbb {F}}_{q}$. According to [19], if

• 1. $C=D_{i}^{4}\cup D_{i+1}^4$, $q\equiv 5($mod 8) and $q=s^{2}+4$ with $s\equiv 1($mod 4), or

• 2. $C=D_{0}^{8}\cup D_{1}^{8}\cup D_{2}^{8}\cup D_{5}^{8}$, $q=l^{2}$ where l is a prime power of form $l=t^{2}+2\equiv 3($mod 8), or

• 3. $C=\cup _{i\in I}D_{i}^{\sqrt{q}+1}$ where $I \subseteq \{0,1,\ldots ,\sqrt{q}\}$ with $\left| I\right| =\frac{\sqrt{q}+1}{2}$ and $q=l^{2}$ for some prime power l,

then C is a $\left( q,\frac{q-1}{2},\frac{q-5}{4},\frac{q-1}{2}\right)$ almost difference set in ${\mathbb {F}}_{q}$.

It is easy to show, also, that if q is an odd prime power, $({\mathbb {F}}_{q},Dev(D_{0}^{2})\cup Dev(D_{1}^{2}))$ is a 2-$\left( q,\frac{q-1}{2},\frac{2q-6}{4}\right)$ design. We then have the following.

Theorem 4.4

Let q be an odd prime power, and $C \subseteq {\mathbb {F}}_{q}$. If

• 1. $C=D_{i}^{4}\cup D_{i+1}^{4}$, $q\equiv 5($mod 8) and $q=s^{2}+4$ with $s\equiv 1($mod 4), or

• 2. $C=D_{0}^{8}\cup D_{1}^{8}\cup D_{2}^{8}\cup D_{5}^{8}$, $q=l^{2}$ where l is a prime power of form $l=t^{2}+2\equiv 3($mod 8), or

• 3. $C=\cup _{i\in I}D_{i}^{\sqrt{q}+1}$ where $I \subseteq \{0,1,\ldots ,\sqrt{q}\}$ with $\left| I\right| =\frac{\sqrt{q}+1}{2}$, I contains both even and odd numbers, and $q=l^{2}$ for some prime power l,

then $({\mathbb {F}}_{q},Dev(D_{0}^{2})\cup Dev(D_{1}^{2})\cup Dev(C))$ is a 2-$(q,\frac{q-1}{2},\frac{3q-11}{4})$ adesign.

5 Constructions of 2-adesigns from symmetric designs

Let $(V,{\mathcal {B}})$ be an incidence structure with $\left| {\mathcal {B}}\right| =b$. The numbers of blocks in which given single points appear (called the replication numbers) become the block sizes of the dual $(V,{\mathcal {B}})^{\perp }$, and the intersection numbers among pairs of blocks become the numbers of blocks of $(V,{\mathcal {B}})^{\perp }$ in which any two points appear. Then the following is clear.

Lemma 5.1

Let $(V,{\mathcal {B}})$ be an incidence structure with $\left| V\right| =v$, and in which the replication numbers are a constant k and the intersection numbers among pairs of blocks are integers $\lambda$ and $\lambda +1$. Then $(V,{\mathcal {B}})^{\perp }$ is a 2-$(b,k,\lambda )$ adesign.

Remark 5.1

The dual of a quasi-symmetric design whose intersection numbers x, y are such that $y-x=1$ is always a 2-adesign.

In [2] constructions of almost difference sets from difference sets were introduced. In this section we further generalize this idea. We will use the following lemma which is actually a trivial construction in itself.

Lemma 5.2

Let $(V,{\mathcal {B}})$ be a symmetric 2-$(v,k,\lambda )$ design. Let $\mathbf {b}_{1},\ldots ,\mathbf {b}_{k}$ be any k blocks in ${\mathcal {B}}$. Let “$\infty$” denote a point. Let ${\mathcal {B}}'$ denote the blocks of ${\mathcal {B}}$ modified by adjoining the point “$\infty$” to each of $\mathbf {b}_{1},\ldots ,\mathbf {b}_{k}$. Then $(V,{\mathcal {B}}')^{\perp }$ is a 2-$(v,k,\lambda )$ adesign.

Proof

The replication numbers in the incidence structure $(V,{\mathcal {B}}')$ are all k, and the intersection numbers among pairs of blocks in ${\mathcal {B}}'$ are $\lambda$ and $\lambda +1$. The result follows from Lemma 5.1. $\square$

Note that the number of times which Lemma 5.2 can be applied to any given symmetric 2-$(v,k,\lambda )$ design is $\lfloor \frac{v}{k} \rfloor$.

The following theorem gives another construction.

Theorem 5.3

Let $(V,{\mathcal {B}})$ be a symmetric 2-$(v,k,\lambda )$ design. Let $\mathbf {b}=\{b_{1},\ldots ,b_{k}\}$ be a block. Suppose that $\mathbf {b}_{1},\ldots ,\mathbf {b}_{k}$ are k blocks not equal to $\mathbf {b}$ such that

• 1. $b_{i} \not \in \mathbf {b}_{i}$ for all $i,1\le i \le k$, and

• 2. $b_{j} \in \mathbf {b}_{l}$ implies $b_{l} \not \in \mathbf {b}_{j}$ for all $j \ne l,1\le j,l\le k$.

Let ${\mathcal {B}}'$ denote the blocks of ${\mathcal {B}}$ modified by adjoining the point $b_{i}$ to the block $\mathbf {b}_{i}$ for all $i,1\le i \le k$, and then removing the block $\mathbf {b}$. Then $(V,{\mathcal {B}}')^{\perp }$ is a 2-$(v,k,\lambda )$ adesign.

Proof

It is easy to see that the replication numbers of $(V,{\mathcal {B}}')$ are all k. The second condition in the statement ensures that the intersection numbers among pairs of blocks of ${\mathcal {B}}'$ are either $\lambda$ or $\lambda +1$. The result then follows from Lemma 5.1. $\square$

Next, we show how to construct almost difference sets from planar difference sets. The following constructions are not optimal but, for certain dimensions, give the best known value for $d_{1}$. A $(v,k,\lambda )$ difference set is called planar if $\lambda =1$. It is easy to show that, given a planar difference set D in an (additive) Abelian group G of order v, if we choose any $a_{0}\in G-D$ such that $2a_{0}$ cannot be written as the sum of two distinct members of D, then $D\cup \{a_{0}\}$ will be an almost difference set with $\lambda =1$. This is simply due to the fact that, because of the way we chose $a_{0}$, we cannot have $a_{0}-a=b-a_{0}$ for any $a,b \in D$, thereby forcing each member of G to appear as a difference of two distinct members of $D\cup \{a_{0}\}$ only one or two times.

Again, let D be a (v, k, 1) difference set in an Abelian group G of order v. Also let $\kappa : G\rightarrow {\mathbb {Z}}_{2} \times G$ by $x \mapsto (0,x)$. Suppose $a_{0},\ldots ,a_{s-1}\in G$ are such that the differences $(1,\tau )$ in $\kappa (D)\cup \{(1,a_{0}),\ldots ,(1,a_{s-1})\}$ cover $\{1\}\times G$ each having multiplicity at most 2, that exactly one of the $a_{i}$s is a member of D, and twice any $a_{i}$ is not the sum of two other distinct $a_{i}$s. If there is at least one difference in $\kappa (D)\cup \{(1,a_{0}),\ldots ,(1,a_{s-1})\}$ having multiplicity 1, then since the difference (1, 0) occurs exactly twice (because exactly one of the $a_{i}$s is in D), we have both 1 and 2 occurring as multiplicities. No difference can occur with multiplicity greater than 2 since G is planar and twice any $a_{i}$ is not the sum of two other distinct $a_{i}$s. We also have the differences in $\kappa (D)\cup \{(1,a_{0}),\ldots ,(1,a_{s-1})\}$ covering ${\mathbb {Z}}_{2}\times G$: the differences $(0,\tau )$ cover $\{0\}\times G$ due to G being a planar difference set and we have assumed that the differences $(1,\tau )$ cover $\{1\}\times G$. This discussion is summarized in the following.

Theorem 5.4

Let D be a (v, k, 1) difference set in an (additive) Abelian group G. Suppose $a_{0},\ldots ,a_{s-1}\in G$ are such that the differences $(1,\tau )$ in $\kappa (D)\cup \{(1,a_{0}),\ldots ,(1,a_{s-1})\}$ cover $\{1\}\times G$ each having multiplicity at most 2, that exactly one of the $a_{i}$s is a member of D, and twice any $a_{i}$ is not the sum of two other distinct $a_{i}$s. If there is at least one difference in $\kappa (D)\cup \{(1,a_{0}),\ldots ,(1,a_{s-1})\}$ having multiplicity 1 then $\kappa (D)\cup \{(1,a_{0}),\ldots ,(1,a_{s-1})\}$ is a $(2v,k+s,1,t)$ almost difference set in ${\mathbb {Z}}_{2}\times G$. The resulting symmetric 2-adesign $({\mathbb {Z}}_{2}\times G,$ Dev$(\kappa (D)\cup \{(1,a_{0}),\ldots ,(1,a_{s-1})\}))$ has parameters $(2v,k+s,1)$.

Example 5.5

Consider the Singer difference set $\{1,2,4\}$ in ${\mathbb {Z}}_{7}$. With $a_{0}=0$ we have $2a_{0}$ is not the sum of two distinct members of D, and $\kappa (D)\cup \{(1,0)\}$ is a (14, 4, 0, 1) almost difference set in ${\mathbb {Z}}_{14}$. With $a_{1}=1$ we have $\kappa (D)\cup \{(1,0),(1,1)\}$ is a (14, 5, 1, 6) almost difference set in ${\mathbb {Z}}_{14}$

Example 5.6

Consider the Singer difference set $D=\{0,1,5,11\}$ in ${\mathbb {Z}}_{13}$. With $a_{0}=10$, we have $2a_{0}$ is not the sum of two distinct members of D, and it is easily checked that $\kappa (D)\cup \{(1,10)\}$ is a (26, 5, 0, 5) almost difference set in ${\mathbb {Z}}_{26}$. With $a_{1}=11$ we have that $\kappa (D)\cup \{(1,a_{0}),(1,a_{1})\}$ is a (26, 6, 1, 11) almost difference set.

Example 5.7

Now consider the Singer difference set $D=\{0,3,13,15,20\}$ in ${\mathbb {Z}}_{21}$. We have $\{9,13,16\}$ are such that the differences $(1,\tau )$ cover $\{1\}\times {\mathbb {Z}}_{21}$ with multiplicities no more than 2 and that 13 is the only member that is also in D. It is also easy to see that the difference (1, 9) can only occur as the difference $(1,9)-(0,0)$. Thus we have $\kappa (D)\cup \{(1,9),(1,13),(1,16)\}$ is a (42, 8, 1, 16) almost difference set.

6 Constructions of 3-adesigns

In this section we will give two constructions each of which produce infinitely many 3-adesigns.

Our first constructions makes use of quadratic residues.

Theorem 6.1

Let $q\equiv 3($mod 4) be an odd prime power. Then $({\mathbb {F}}_{q},Dev(D_{0}^{2})\cup Dev(D_{1}^{2}))$ is a 3-$(q,\frac{q-1}{2},\frac{q-7}{4})$ adesign.

Proof

Denote $\frac{q-1}{2}$ by k and $\frac{q-3}{4}$ by $\lambda '$. Let $x,y,z\in {\mathbb {F}}_{q}$ be arbitrary. To count the number of blocks in which x, y, z appear together, we first count the number of blocks of $Dev(D_{0}^{2})\cup Dev(D_{1}^{2}\cup \{0\})$ in which x, y, z appear together. Suppose that the three points x, y, z appear in $\mu$ blocks in $Dev(D_{0}^{2})$. Using the fact that $({\mathbb {F}}_{q},Dev(D_{0}^{2}))$ is a 2-$(q,k,\lambda ')$ design, a simple counting argument gives that there are $q-3k+3\lambda '-\mu$ blocks in $Dev(\overline{D_{0}^{2}}){:}{=}Dev(D_{1}^{2}\cup \{0\})$ containing x, y, z. Thus, there are $q-3k+3\lambda '=\lambda '$ blocks in $Dev(D_{0}^{2})\cup Dev(\overline{D_{0}^{2}})$ containing x, y, z. Since $w\in D_{1}^{2}\cup \{0\}+w$ for all $w\in {\mathbb {F}}_{q}$, we want to know how many of the $q-3k+3\lambda '-\mu$ blocks in $Dev(\overline{D_{0}^{2}})$ are also in $\{\overline{D_{0}^{2}}+x,\overline{D_{0}^{2}}+y,\overline{D_{0}^{2}}+z\}$. Without loss of generality suppose that both $\overline{D_{0}^{2}}+x$ and $\overline{D_{0}^{2}}+y$ contain the three points x, y, z. Then we must have $y-x,z-x \not \in D_{0}^{2}$ and $x-y,z-y \not \in D_{0}^{2}$. But this would imply that $x-y,y-x \in D_{1}^{2}$ where both $x-y$ and $y-x$ are nonzero. But this is impossible as the additive inverse of any member of $D_{1}^{2}$ cannot also be a member whenever $q\equiv 3($mod 4). Then no more than one of the blocks $\overline{D_{0}^{2}}+x,\overline{D_{0}^{2}}+y,\overline{D_{0}^{2}}+z$ can contain all three of x, y, z. We now need to show that there are two different 3-levels, i.e. that $({\mathbb {F}}_{q},Dev(D_{0}^{2})\cup Dev(D_{1}^{2}))$ is not a 3-design, but a 3-adesign. To show this we assume that $({\mathbb {F}}_{q},Dev(D_{0}^{2})\cup Dev(D_{1}^{2}))$ is a 3-$(q,k,\lambda )$-design for some $\lambda$. Then the number of blocks must be given by $\lambda \frac{\left( {\begin{array}{c}q\\ 3\end{array}}\right) }{\left( {\begin{array}{c}k\\ 3\end{array}}\right) }$. The only choices for $\lambda$ are $\lambda '$ or $\lambda '-1$. If $\lambda =\lambda '$ then we get that $q-5=q-4$. If $\lambda =\lambda '-1$ then we get that $(q-3)(q-5)=(q-7)(q-2)$. Either way we get a contradiction, which completes the proof. $\square$

Example 6.2

With $q=11$ we apply Theorem 6.1 and get that $({\mathbb {Z}}_{11},Dev(D_{0}^{2})\cup Dev(D_{1}^{2}))$ is a 3-(11, 5, 1) adesign with blocks:

Our second construction is related to graphs, though it is simple enough to avoid graph-theoretical preliminaries.

Theorem 6.3

Let n $(\ge$7) be an odd integer not divisible by 3. Consider, for fixed $a\in {\mathbb {Z}}_{n}$, all pairs $\lbrace a-i\pmod n, a+i\pmod n \rbrace$ for $i=1,\cdots ,\frac{n-1}{2}$. The union of any two distinct pairs gives a block consisting of four points. Denote, for fixed $a\in {\mathbb {Z}}_{n}$, the set of all blocks obtained in this way by $B_{a}$. Then $({\mathbb {Z}}_{n},\cup _{a\in {\mathbb {Z}}_{n}}B_{a})$ is a 3-(n, 4, 2) adesign.

Proof

Arrange all the points in a circle as is shown in the graph below. For any three points $x, y, z \in {\mathbb {Z}}_{n}$, denote $|x-y|$, $|x-z|$, $|y-z|$ by $d_{xy}$, $d_{xz}$, $d_{yz}$ respectively.

Since n is not divisible by 3, $d_{xy}=d_{xz}=d_{yz}$ cannot happen. Then suppose two of them are equal. Without loss of generality, suppose $d_{xz}=d_{yz}$. Then when x and y are in a pair, z must be the fixed point so that there is no block containing all three of x, y and z. When x and z are in a pair or y and z are in pair, we can find exactly one block containing the three points in each case. If $d_{xy},d_{xz}$ and $d_{yz}$ are distinct, then we can find one block containing these three points when any two points are in pair, in which case we have three blocks containing these three points together.

$\square$

Example 6.4

With $n=7$ we apply Theorem 6.3 and get that $({\mathbb {Z}}_{7},\cup _{a\in {\mathbb {Z}}_{7}}B_{a})$ is a 3-(7, 4, 2) adesign with blocks:

Let $(V,{\mathcal {B}})$ be an incidence structure. Let $p\in V$, and define ${\mathcal {B}}_{p}=\{{\mathcal {B}}-\{p\}\mid {\mathcal {B}}\in {\mathcal {B}}\text { and }p\in {\mathcal {B}}\}$. We call the incidence structure $(V-\{p\},{\mathcal {B}}_{p})$ the contraction of $(V,{\mathcal {B}})$ at p. It is clear that contracting at points of a 3-adesign will give a 2-adesign as long as not all 3-sets of points occur in the same number of blocks of the contraction.

Example 6.5

The contraction at the point $p=1$ of the 3-(11, 5, 1) adesign in Example 6.2 is a symmetric 2-(10, 4, 1) adesign with the ten blocks:

Remark 6.1

Interestingly, a contraction at any point of the incidence structure $({\mathbb {F}}_{q},Dev(D_{0}^{2})\cup Dev(D_{1}^{2}))$ from Theorem 6.1 gives a symmetric 2-$\left( q-1,\frac{q-3}{2},\frac{q-7}{4}\right)$ adesign and, since it contains punctured translates of both $D_{0}^{2}$ and $D_{1}^{2}$, cannot be the development of any almost difference set.

7 Related codes

A linear binary code C of length n and dimension k (or simply an $\left[ n,k\right]$ code), is a k-dimensional linear subspace of the n-dimensional binary vector space ${\mathbb {F}}_{2}^{n}$. The dual $C^{\perp }$ of an $\left[ n,k\right]$ code C is the $\left[ n,n-k\right]$ code that is the orthogonal space of C with respect to the inner product of the binary field. Any basis of C is called a generator matrix of C, and any basis of $C^{\perp }$ is called a parity check matrix of C. The Hamming distance between two vectors $x=(x_{1},\ldots ,x_{n})$ and $y=(y_{1},\ldots ,y_{n})$ is the number of indices i such that $x_{i} \ne y_{i}$. The Hamming weight of a vector is the number of its nonzero coordinates. The minimum distance d of a code is smallest possible distance between pairs of distinct codewords. An $\left[ n,k\right]$ code C is self-orthogonal if $C \subseteq C^{\perp }$. An $\left[ n,k\right]$ code C is optimal if, given its length and dimension, has the largest possible minimum distance. The best codes for a given length and dimension can be found in the code tables in [15].

7.1 Cyclic codes

We assume some familiarity with cyclic codes. For more details on the subject the reader is referred to [10]. An $\left[ n,k\right]$ code C over ${\mathbb {F}}_{2}$ is called cyclic if $(c_{0},c_{1},\ldots ,c_{n-1})\in C$ implies that the circular shift $(c_{n-1},c_{0},\ldots ,c_{n-2})$ is also in C. By identifying any vector $(c_{0},c_{1},\ldots ,c_{n-1})\in {\mathbb {F}}_{2}^{n}$ with the polynomial

$$\begin{aligned} c_{0}+c_{1}x+c_{2}x^{2}+\cdots +c_{n-1}x^{n-1}\in {\mathbb {F}}_{2}\left[ x\right] /(x^{n}-1), \end{aligned}$$

any linear code C of length n over ${\mathbb {F}}_{2}$ corresponds to a subset of ${\mathbb {F}}_{2}\left[ x\right] /(x^{n}-1)$. The code is cyclic if and only if the corresponding subset is an ideal in the ring ${\mathbb {F}}_{2}\left[ x\right] /(x^{n}-1)$. Note that every ideal of ${\mathbb {F}}_{2}\left[ x\right] /(x^{n}-1)$ is principal. Let $g(x)\in {\mathbb {F}}_{2}\left[ x\right] /(x^{n}-1)$ be monic and of minimum degree, and let $C=\langle g(x) \rangle$. Then g(x) is called the generator polynomial of C, and $h(x)=(x^{n}-1)/g(x)$ is referred to as the parity-check polynomial. The dimension of C is given by the degree of h(x).

The following theorem is easy to prove.

Lemma 7.1

Let D be subset of ${\mathbb {Z}}_{n}$ with two difference levels. Define $D(x)=\sum _{i\in D}x^{i}\in {\mathbb {F}}_{2}\left[ x\right]$, $g(x)=gcd(x^{n}-1,D(x))$, and $h(x)=(x^{n}-1)/g(x)$. Then the code $C=\langle g(x) \rangle$ is an $\left[ n, k \right]$ cyclic code where $k=deg(h(x))$.

7.2 Known results on cyclic codes from 2-adesigns

It is known that when $p\equiv 1 ($mod 4) the code $C=\langle D_{0}^{2}(x) \rangle$ is a quadratic residue code if 2 is a square in ${\mathbb {F}}_{p}^{*}$, and a trivial cyclic code otherwise [10]. When $p=9+4y^{2}\equiv 1 ($mod 4) resp. $p=49+4y^{2}\equiv 1$(mod 4) is a prime, $D_{0}^{4}$ resp. $D_{0}^{4}\cup \{0\}$ is an almost difference set [19]. If D is either of these almost difference sets, then some parameters for the code $C=\langle D(x) \rangle$ are known and can be found in [9]. When $p_{1}$ and $p_{2}$ are primes such that $p_{2}-p_{1}=4$, the set $E=E_{1}^{(2)}\cup \{p_{1},2p_{1},\ldots ,(p_{2}-1)p_{1}\}$, where $E_{1}^{(2)}=\{0\le i\le p_{1}p_{2} \mid \frac{i}{p_{1}p_{2}}=-1\}$, is an almost difference set [19], and some of the parameters of $C=\langle E(x) \rangle$ are known and can be found in [8]. Lastly, when q is a prime power and $\alpha$ a generator of ${\mathbb {F}}_{q^{2}}^{*}$, the set $D_{q}=\{0\le i \le n-1 \mid Tr(\alpha ^{i})=1\}$ is a planar almost difference set (i.e. with difference levels 0 and 1), and the code $C=\langle D_{q}(x) \rangle$ has parameters $\left[ q^{2}-1,q+1,q-1\right]$ [10]. There are many other constructions of almost difference sets, and the parameters of their linear codes are open in general.

7.3 Cyclic codes from sets with two difference levels

Sets with two difference levels that are not almost difference sets can also generate codes with good parameters. For example, when $q\equiv 1 ($mod 8) is a prime power with unique representation $q=x^{2}+4y^{2}=a^{2}+2b^{2}$ where $x,a \equiv 1 ($mod 4), and $\alpha$ is a generator of ${\mathbb {F}}_{q}^{*}$, we can define $D=D_{0}^{8}\cup D_{1}^{8}\cup D_{2}^{8}\cup D_{5}^{8}$ and $\Delta _{j}=|(D+\alpha ^{j}\cap D|$. It was shown in [13] that

$$\begin{aligned} \Delta _{0}=\Delta _{2}=\Delta _{4}=\Delta _{6}= & {} \frac{16q-48+8x-8a-16y}{64} \end{aligned}$$

(5)

$$\begin{aligned} \Delta _{1}=\Delta _{5}= & {} \frac{16q-80-16x+16a-32y}{64} \end{aligned}$$

(6)

$$\begin{aligned} \Delta _{3}=\Delta _{7}= & {} \frac{16q-16}{64}. \end{aligned}$$

(7)

Thus, if $3(a-x)-2y=4$, we have that $({\mathbb {F}}_{q},Dev(D))$ is an incidence structure with two difference levels given by $\mu _{1}=\frac{16q-48+8x-8a-16y}{64}$ and $\mu _{2}=\frac{16q-16}{64}$.

Example 7.2

With $q=73$ we have the unique representation is given by $x=-3,y=4$ and $a=1,b=6$. Thus the two difference levels are $\mu _{1}=16$ and $\mu _{2}=18$. Since the difference levels are $\equiv 0 ($mod 2), the inner product over the field ${\mathbb {F}}_{2}$ of any two rows of the incidence matrix will be 0, making the code $C=\langle D(x) \rangle$ self-orthogonal. We checked using MAGMA, and C is a $\left[ 73,18,24\right]$ code. According the code tables in [15], the best binary code with length 73 and dimension 18 has minimum weight 24.

We also have computed the following example using cyclotomic classes of order ten. The cyclotomic numbers of order ten are known and can be found in [24].

Example 7.3

Let $q=151$, and define $D=D_{4}\cup D_{5}\cup D_{8}\cup D_{9}$. Then D has the two difference levels $\mu _{1}=22$ and $\mu _{2}=24$ and the code $C=\langle D(x) \rangle$ is self-orthogonal. We checked using MAGMA, and C is a $\left[ 151,30,48\right]$ code. According the code tables in [15], the best binary code with length 151 and dimension 30 has minimum weight 48.

Lemma 7.4

Let A be a $v \times v$ incidence matrix of the symmetric incidence structure $(G,{\mathcal {B}})$ obtained from the development of some k-subset D in the Abelian group G (where $\left| G\right| =v$) with difference levels $\mu _{1} <\cdots <\mu _{s}$. Suppose that $k \equiv \mu _{1}\equiv \cdots \equiv \mu _{s} ($mod 2).

• 1. If k is even the binary code of length v with generator matrix A is self-orthogonal.

• 2. If k is odd the matrix

  $$\begin{aligned} \left[ \begin{array}{cc} 1 &{} \\ \vdots &{} A \\ 1 &{} \\ \end{array}\right] \end{aligned}$$

  generates a binary self-orthogonal code of length $v+1$.

Proof

By Lemma 2.2 we can see that, in both cases, the weights of the rows of the generator matrix are all even and the inner product of any two rows is even as well. $\square$

We will refer to an incidence structure $(V,{\mathcal {B}})$ whose incidence matrix generates a self-orthogonal code simply as self-orthogonal.

We will use the following lemma.

Lemma 7.5

Let $(G,{\mathcal {B}})$ be a symmetric incidence structure coming from the development of a k-subset D of the Abelian group G (where $\left| G\right| =v$) with difference levels $\mu _{1}$ and $\mu _{2}$. Let t denote the number of members of $G-\{0\}$ which appear $\mu _{1}$ times in the multiset $\{x-y \mid x,y \in D, x \ne y \}$. The the number of pairs of points in G appearing in exactly $\mu _{1}$ blocks in ${\mathcal {B}}$ is $\frac{vt}{2}$ and the number of pairs of points of V appearing in $\mu _{2}$ blocks is $\frac{v(v-1-t)}{2}$.

Proof

For each $x \in V$, there are t points in $V-\{x\}$ each appearing together with x in exactly $\mu _{1}$ blocks. Thus, there are $\frac{vt}{2}$ pairs of points of V appearing in $\mu _{1}$ blocks. Similarly, there are $\frac{v(v-1-t)}{2}$ pairs of points of V appearing in $\mu _{2}$ blocks. It is easily seen that $\frac{vt}{2}+\frac{v(v-1-t)}{2}=\left( {\begin{array}{c}v\\ 2\end{array}}\right)$. $\square$

We were able to come up with the following bound on the minimum distance of a code generated by a self-orthogonal incidence structure with two difference levels. However, as is clear from Examples 7.2 and 7.3, there is much room for improvement.

Theorem 7.6

Let A be the incidence matrix of a self-orthogonal incidence structure $(G,{\mathcal {B}})$ coming from the development of a k-subset D of the Abelian group G (where $\left| G\right| =v$) with difference levels $\mu _{1}$ and $\mu _{2}$. Let t denote the number of members of $G-\{0\}$ which appear $\mu _{1}$ times in the multiset $\{x-y \mid x,y \in D, x \ne y \}$. The dual of the binary code with generator matrix A has minimum distance

$$\begin{aligned} d \ge \frac{(\mu _{2}+k)+\sqrt{(\mu _{2}+k)^{2}+4 \mu _{2}(\mu _{2}-\mu _{1})vt}}{2 \mu _{2}}. \end{aligned}$$

Proof

Let S be a minimal set of linearly dependent columns of A. Then every row of A must intersect an even number of these columns in 1s. Let $n_{i}$ denote the number of rows of A intersecting exactly i columns of S in 1s. Let $d=|S|$. Since every column of A contains k 1s (because the incidence structure $(G,{\mathcal {B}})$ is symmetric) and the scalar product (over the reals) of any two columns is either $\mu _{1}$ or $\mu _{2}$, using Lemma 7.5 we have

$$\begin{aligned} \sum 2i n_{2i} = kd \end{aligned}$$

and

$$\begin{aligned} \sum 2i (2i-1) n_{2i} = \mu _{2} d (d-1) - (\mu _{2} - \mu _{1}) vt. \end{aligned}$$

Subtracting the first equation from the second we have

$$\begin{aligned} \sum 2i (2i-2) n_{2i}=d((d-1)\mu _{2}-k)-(\mu _{2}-\mu _{1})vt\ge 0. \end{aligned}$$

On one hand we get that $d((d-1)\mu _{2}-k)\ge (\mu _{2}-\mu _{1})vt\ge 0$ and on the other hand we get that $d^{2}\mu _{2}-d(\mu _{2}+k)-(\mu _{2}-\mu _{1})vt\ge 0$. The result follows from solving the quadratic. $\square$

7.4 Noncyclic codes from adesigns

In general, the parameters of codes generated from adesigns are open. Using MAGMA we have computed the parameters of the codes generated by the transpose of the incidence matrix of many of our constructions. We have included the parameters and construction information in the following two tables.

Table 1 Parameters of codes from new 2-adesigns computed by MAGMA

Remark 7.1

The $\left[ 159,52,36\right]$ code corresponding to the 2-(53, 26, 37) adesign in Table 1 actually improves the lower bound for the minimum weight given in [15] for the best binary code with length 53 and dimension 26.

Remark 7.2

The code corresponding to the 3-(7, 4, 2) adesign in Table 2 is in fact an optimal, projective two-weight $\left[ 21,6,8\right]$ code, and so is an optimal code that corresponds to a strongly regular graph [4].

Remark 7.3

The codes corresponding to the 3-(7, 3, 0) and 3-(19, 9, 3) adesigns in Table 2 are both extremal self-dual codes [21].

Table 2 Parameters of codes from new 3-adesigns computed by MAGMA

8 Concluding remarks

We have investigated some generalizations of combinatorial designs arising from almost difference sets, especially the t-adesigns. We have discussed some of their basic properties and have given several constructions for 2-adesigns, and two constructions for 3-adesigns. Many of the codes arising from these structures have good parameters, as was discussed in Sect. 7, and we have included some of these in the tables of the previous section. Questions concerning the parameters of the codes arising from adesigns are open in general and, as good codes are arising from many of these structures, further investigation would be worthwhile.