---
title: "General Design Constructions"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Designs/operation.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Designs/operation.md"
part: "Combinatorics"
chapter: "Incidence Structures and Designs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Incidence Structures and Designs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Designs/index-designs.md"}
prev: {"title": "The Point-Set and Block-Set of an Incidence Structure", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Designs/point-block-set.md"}
next: {"title": "Elementary Invariants of an Incidence Structure", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Designs/invariant.md"}
intrinsics:
  - {"name": "Complement", "signature": "Complement(D): Inc -> Inc"}
  - {"name": "Dual", "signature": "Dual(D): Inc -> Inc"}
  - {"name": "Contraction", "signature": "Contraction(D, p): Inc, IncPt -> Inc"}
  - {"name": "Contraction", "signature": "Contraction(D, b): Inc, IncBlk -> Inc"}
  - {"name": "Residual", "signature": "Residual(D, b): Inc, IncBlk -> Inc"}
  - {"name": "Residual", "signature": "Residual(D, p): Inc, IncPt -> Inc"}
  - {"name": "Simplify", "signature": "Simplify(D): Inc -> Inc"}
  - {"name": "Sum", "signature": "Sum(Q): [ Inc ] -> Inc"}
  - {"name": "Union", "signature": "Union(D, E): Inc, Inc -> Inc"}
  - {"name": "Restriction", "signature": "Restriction(D, S): IncNsp, { Incpt } -> IncNsp"}
  - {"name": "WittDesign", "signature": "WittDesign(n): RngIntElt -> Dsgn"}
  - {"name": "DifferenceSet", "signature": "DifferenceSet(p, t): RngIntElt, MonStgElt -> { RngIntResElt }"}
  - {"name": "SingerDifferenceSet", "signature": "SingerDifferenceSet(n, q): RngIntElt, RngIntElt -> { RngIntResElt }"}
  - {"name": "IsDifferenceSet", "signature": "IsDifferenceSet(B): SetEnum -> BoolElt, RngIntElt"}
  - {"name": "Development", "signature": "Development(B): { RngElt } -> Inc"}
  - {"name": "Development", "signature": "Development(T): { { Elt } } -> Inc"}
examples:
  - "ex-2db350"
  - "ex-9c4643"
  - "ex-b4f959"
---

# 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.

<a id="function-complement-inc"></a>
### `Complement(D): Inc -> Inc`

The complement of the incidence structure $D$.

<a id="function-dual-inc"></a>
### `Dual(D): Inc -> Inc`

The dual of the incidence structure $D$.

<a id="function-contraction-inc-incpt"></a>
### `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.

<a id="function-contraction-inc-incblk"></a>
### `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.

<a id="function-residual-inc-incblk"></a>
### `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$.

<a id="function-residual-inc-incpt"></a>
### `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$.

<a id="function-simplify-inc"></a>
### `Simplify(D): Inc -> Inc`

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

<a id="function-sum-inc"></a>
### `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)$.

<a id="function-union-inc-inc"></a>
### `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.

<a id="function-restriction-incnsp-incpt"></a>
### `Restriction(D, S): IncNsp, { Incpt } -> IncNsp`

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

<a id="example-ex-2db350"></a>
### `Example: Related Structures of a Design (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.

<a id="function-wittdesign-rngintelt"></a>
### `WittDesign(n): RngIntElt -> Dsgn`

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

<a id="example-ex-9c4643"></a>
### `Example: Contraction of a Witt Design (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.

<a id="function-differenceset-rngintelt-monstgelt"></a>
### `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 [[Hal86](https://docs.magma-maths.org/v2.30-1/references.md#cite-hall86)], pp. 141–142.

<a id="function-singerdifferenceset-rngintelt-rngintelt"></a>
### `SingerDifferenceSet(n, q): RngIntElt, RngIntElt -> { RngIntResElt }`

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

<a id="function-isdifferenceset-setenum"></a>
### `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.

<a id="function-development-rngelt"></a>
### `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.

<a id="function-development-elt"></a>
### `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 $\Z/m\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$.

<a id="example-ex-b4f959"></a>
### `Example: Developing a 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
```
