# General Design Constructions

Each of these functions returns three values:

**(i)**
The incidence structure $D$;

**(ii)**
The point-set $P$ of $D$;

**(iii)**
The block-set $B$ of $D$.

## The Construction of Related Structures

All operations defined for incidence structures apply also to near–linear spaces, linear spaces and designs.

### `Complement(D): Inc -> Inc`

The complement of the incidence structure $D$.

### `Dual(D): Inc -> Inc`

The dual of the incidence structure $D$.

### `Contraction(D, p): Inc, IncPt -> Inc`

Given an incidence structure $D = (P, B)$, and a point $p \in P$, form the incidence structure

$$
E = ( P - \lbrace p \rbrace, \lbrace b - \lbrace p \rbrace : b \in B | p \in b \rbrace ).
$$

Thus, $E$ is constructed from $D$ by deleting $p$ and retaining only those blocks incident with it.

### `Contraction(D, b): Inc, IncBlk -> Inc`

Given an incidence structure $D = (P, B)$, and a block $b \in B$, form the incidence structure

$$
E = ( b, \lbrace b \cap c : c \in B | c \ne b \rbrace ).
$$

Thus, $E$ has point set $b$ and its blocks are the non–empty intersections of $b$ with the blocks of $D$ other than $b$ itself.

### `Residual(D, b): Inc, IncBlk -> Inc`

Given an incidence structure $D = (P, B)$, and a block $b \in B$, form the incidence structure $E = ( P - b, B - \lbrace b \rbrace ).$ Thus, $E$ has point set $P - b$ and its blocks are the non–empty intersections of $P-b$ with the blocks of $D$.

### `Residual(D, p): Inc, IncPt -> Inc`

Given an incidence structure $D = (P, B)$, and a point $p \in P$, form the incidence structure

$$
E = ( P - \lbrace p \rbrace, \lbrace x : x \in B | p \notin x \rbrace ).
$$

Thus, $E$ has point set $P - \lbrace p \rbrace$ and its blocks are the blocks of $D$ which do not contain $p$.

### `Simplify(D): Inc -> Inc`

Simplify the incidence structure $D$; i.e., remove repeated blocks from $D$.

### `Sum(Q): [ Inc ] -> Inc`

Given a sequence $Q = [ D_1, \ldots, D_l ]$ of incidence structures, each of which is defined over the same set $P$ of points, form the incidence structure obtained by taking the union of the block sets of $D_1, \ldots, D_l$. Thus, if $D_i = (P, B_i)$ then $D = (P, B_1 \cup \ldots \cup B_l)$.

### `Union(D, E): Inc, Inc -> Inc`

The union of incidence structures $D$ and $E$. That is, if $D = (P, B)$ and $E = (Q, C)$, then return $U = (P \cup Q, B \cup C)$. The point sets $P$ and $Q$ must be disjoint.

### `Restriction(D, S): IncNsp, { Incpt } -> IncNsp`

The restriction of the (near–)linear space $D$ to the set of points $S$.

### `Example: related (ex-2db350)`

We illustrate some of the above functions with an example.

```magma
> K := Design< 3, 8 | {1,3,7,8}, {1,2,4,8}, {2,3,5,8}, {3,4,6,8}, {4,5,7,8},
> {1,5,6,8}, {2,6,7,8}, {1,2,3,6}, {1,2,5,7}, {1,3,4,5}, {1,4,6,7}, {2,3,4,7},
> {2,4,5,6}, {3,5,6,7} >;
> CK := Contraction(K, Point(K, 8));
> RK := Residual(K, Block(K, 1));
> K: Maximal;
3-(8, 4, 1) Design with 14 blocks
Points: {@ 1, 2, 3, 4, 5, 6, 7, 8 @}
Blocks:
    {1, 3, 7, 8},
    {1, 2, 4, 8},
    {2, 3, 5, 8},
    {3, 4, 6, 8},
    {4, 5, 7, 8},
    {1, 5, 6, 8},
    {2, 6, 7, 8},
    {1, 2, 3, 6},
    {1, 2, 5, 7},
    {1, 3, 4, 5},
    {1, 4, 6, 7},
    {2, 3, 4, 7},
    {2, 4, 5, 6},
    {3, 5, 6, 7}
> CK: Maximal;
2-(7, 3, 1) Design with 7 blocks
Points: {@ 1, 2, 3, 4, 5, 6, 7 @}
Blocks:
    {1, 3, 7},
    {1, 2, 4},
    {2, 3, 5},
    {3, 4, 6},
    {4, 5, 7},
    {1, 5, 6},
    {2, 6, 7}
> RK: Maximal;
Incidence Structure on 4 points with 13 blocks
Points: {@ 2, 4, 5, 6 @}
Blocks:
    {2, 4},
    {2, 5},
    {4, 6},
    {4, 5},
    {5, 6},
    {2, 6},
    {2, 6},
    {2, 5},
    {4, 5},
    {4, 6},
    {2, 4},
    {2, 4, 5, 6},
    {5, 6}
> RKS := Simplify(RK);
> RKS: Maximal;
Incidence Structure on 4 points with 7 blocks
Points: {@ 2, 4, 5, 6 @}
Blocks:
    {2, 4},
    {2, 5},
    {4, 6},
    {4, 5},
    {5, 6},
    {2, 6},
    {2, 4, 5, 6}

```

## The Witt Designs

The $5$–($12$, $6$, $1$) and $5$–($24$, $8$, $1$) designs constructed by Witt, also known as the small and large Mathieu designs, respectively, can be constructed in Magma with the following function.

### `WittDesign(n): RngIntElt -> Dsgn`

The Witt $5$–design on $n$ points, where $n = 12$ or $24$.

### `Example: wittex (ex-9c4643)`

We construct the Witt $5$–($24$, $8$, $1$) design and take its contraction at a point. This contraction is in fact isomorphic to the design constructed above from the unextended binary Golay code.

```magma
> D, P, B := WittDesign(24);
> D;
5-(24, 8, 1) Design with 759 blocks
> p := P.1;
> Cp := Contraction(D, p);
> Cp;
4-(23, 7, 1) Design with 253 blocks

```

## Difference Sets and their Development

Let $G$ be a group of order $v$ and let $k$ and $\lambda$ be positive integers such that $1 < k < v$. A $(v, k, \lambda)$ *difference set* for $G$ is a set $D$ of $k$ group elements such that the set

$$
\lbrace gh^{-1} : g, h \in D | g \neq h \rbrace
$$

contains every non–identity element of $G$ exactly $\lambda$ times.

### `DifferenceSet(p, t): RngIntElt, MonStgElt -> { RngIntResElt }`

The difference set of type given by $t$ (which must be one of `"Q"`, `"H6"`, `"T"`, `"B"`, `"B0"`, `"O"`, `"O0"`, or `"W4"`) corresponding to the prime $p$. The types have the same interpretation as given by Marshall Hall in [[Hall, 1986](../../references.md#cite-hall86)], pp. 141–142.

### `SingerDifferenceSet(n, q): RngIntElt, RngIntElt -> { RngIntResElt }`

The Singer difference set corresponding to a hyperplane of PG$(n, q)$.

### `IsDifferenceSet(B): SetEnum -> BoolElt, RngIntElt`

Returns `true` iff $B$ is a difference set over an integer residue class ring or a finite group (with an iterator). If `true`, the value of the parameter $\lambda$ (i.e., the number of times each non–identity group/ring element appears as a “difference” of elements of $B$) is also returned.

### `Development(B): {  RngElt } -> Inc`

Let $B$ be a subset of a magma $A$ which is a difference set relative to $A$, where $A$ is either the ring $Z/mZ$, a finite abelian group or an arbitrary finite group (with an iterator). This function constructs the symmetric design having point set $A$ and whose blocks consist of the sets obtained by translating $B$ by each element of $A$ in turn.

### `Development(T): { { Elt } } -> Inc`

Let $T = \lbrace B_1, \ldots, B_l \rbrace$ be a difference family consisting of subsets of a magma $A$ which is either the ring ${\mathbb{Z}}/m{\mathbb{Z}}$, a finite abelian group or an arbitrary finite group (with an iterator). This function constructs the incidence structure with point set $A$ and whose $i$-th block is the set $\lbrace B_1 \cup \ldots \cup B_l \rbrace$ translated by the $i$-th element of $A$.

### `Example: Develop Difference Set (ex-b4f959)`

The set $\lbrace 1, 3, 4, 5, 9 \rbrace$, where the elements are residues modulo $11$, forms an $(11, 5, 2)$ difference set. We develop this set and construct a $2$-$(11, 5, 2)$ design.

```magma
> Z11 := IntegerRing(11);
> B := { Z11 | 1, 3, 4, 5, 9};
> IsDifferenceSet(B);
true 2
> D := Development(B);
> D: Maximal;
2-(11, 5, 2) Design with 11 blocks
Points: {@ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 @}
Blocks:
    {1, 3, 4, 5, 9},
    {2, 4, 5, 6, 10},
    {0, 3, 5, 6, 7},
    {1, 4, 6, 7, 8},
    {2, 5, 7, 8, 9},
    {3, 6, 8, 9, 10},
    {0, 4, 7, 9, 10},
    {0, 1, 5, 8, 10},
    {0, 1, 2, 6, 9},
    {1, 2, 3, 7, 10},
    {0, 2, 3, 4, 8}

```

We now construct the twin primes (type “T”) difference set modulo 323 ($= 17 \times 19$), and its development.

```magma
> B := DifferenceSet(17, "T");
> D := Development(B);
> D;
2-(323, 161, 80) Design with 323 blocks

```