[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
General Design Constructions

General Design Constructions

Each of these functions returns three values:

Subsections

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 - { p }, { b - { p } : b in B | p in b } ). 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, { b intersect c : c in B | c != b } ). 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 - { b } ). 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 - { p }, { x : x in B | p notin x } ). Thus, E has point set P - { p } 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, ..., 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, ..., D_l. Thus, if D_i = (P, B_i) then D = (P, B_1 union ... union 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 union Q, B union 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 Design_related (H56E3)

We illustrate some of the above functions with an example.

> 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 Design_wittex (H56E4)

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.

> 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

Hadamard Matrices and their 3-Designs

Many designs can be constructed from Hadamard matrices. Magma provides functions to create such designs, as well as functions to test if a matrix is Hadamard or if two Hadamard matrices are Hadamard equivalent.

IsHadamard(H) : AlgMatElt -> BoolElt
True iff H is a Hadamard matrix. H may be defined over any ring.
IsHadamardEquivalent(H, J) : AlgMatElt, AlgMatElt -> BoolElt
True iff the Hadamard matrices H and J are Hadamard equivalent.
HadamardRowDesign(H, i) : AlgMatElt, RngIntElt -> Dsgn
Given an n x n Hadamard matrix H (with n >= 4) and an integer i such that 1 <= i <= n, return the Hadamard 3-design corresponding to the row i of H.
HadamardColumnDesign(H, i) : AlgMatElt, RngIntElt -> Dsgn
Given an n x n Hadamard matrix H (with n >= 4) and an integer i such that 1 <= i <= n, return the Hadamard 3-design corresponding to the column i of H.

Example Design_hadamard (H56E5)

There is only one Hadamard equivalence class of 8 x 8 Hadamard matrices. We construct one matrix, and two of its designs.

> R := MatrixRing(Integers(), 8);
> H := R![1, 1, 1, 1, 1, 1, 1, 1,
>       1, 1, 1, 1, -1, -1, -1, -1,
>       1, 1, -1, -1, 1, 1, -1, -1,
>       1, 1, -1, -1, -1, -1, 1, 1,
>       1, -1, 1, -1, 1, -1, -1, 1,
>       1, -1, 1, -1, -1, 1, 1, -1,
>       1, -1, -1, 1, -1, 1, -1, 1,
>       1, -1, -1, 1, 1, -1, 1, -1];
> IsHadamard(H);
true
> DR := HadamardRowDesign(H, 3);
> DR: Maximal;
3-(8, 4, 1) Design with 14 blocks
Points: {@ 1, 2, 3, 4, 5, 6, 7, 8 @}
Blocks:
    {1, 2, 5, 6},
    {1, 2, 7, 8},
    {1, 2, 3, 4},
    {1, 4, 5, 7},
    {1, 4, 6, 8},
    {1, 3, 6, 7},
    {1, 3, 5, 8},
    {3, 4, 7, 8},
    {3, 4, 5, 6},
    {5, 6, 7, 8},
    {2, 3, 6, 8},
    {2, 3, 5, 7},
    {2, 4, 5, 8},
    {2, 4, 6, 7}
> DC := HadamardColumnDesign(H, 8);
> DC;
3-(8, 4, 1) Design with 14 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 { gh^(-1) : g, h in D | g != h } 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 Combinatorial Theory (New York: Wiley, 2nd ed. 1986), 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
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 = { B_1, ..., B_l } be a difference family consisting of subsets of a magma A which is either the ring Z/mZ, 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 { B_1 union ... union B_l } translated by the i-th element of A.

Example Design_DevelopDifferenceSet (H56E6)

The set { 1, 3, 4, 5, 9 }, 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.

> 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 x 19), and its development.

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

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]