A block design is a set together with a family of subsets (repeated subsets are allowed) whose members are chosen to satisfy some set of properties that are deemed useful for a particular application. See Wikipedia article Block_design.
REFERENCES:
[1] | Block design from wikipedia, Wikipedia article Block_design |
[2] | What is a block design?, http://designtheory.org/library/extrep/extrep-1.1-html/node4.html (in ‘The External Representation of Block Designs’ by Peter J. Cameron, Peter Dobcsanyi, John P. Morgan, Leonard H. Soicher) |
[We07] | Charles Weibel, “Survey of Non-Desarguesian planes” (2007), notices of the AMS, vol. 54 num. 10, pages 1294–1303 |
AUTHORS:
Vincent Delecroix (2014): rewrite the part on projective planes trac ticket #16281
Peter Dobcsanyi and David Joyner (2007-2008)
This is a significantly modified form of the module block_design.py (version 0.6) written by Peter Dobcsanyi peter@designtheory.org. Thanks go to Robert Miller for lots of good design suggestions.
Todo
Implement finite non-Desarguesian plane as in [We07] and Wikipedia article Non-Desarguesian_plane.
Return an Affine Geometry Design.
INPUT:
\(AG_{n,d} (F)\), as it is sometimes denoted, is a \(2\) - \((v, k, \lambda)\) design of points and \(d\)- flats (cosets of dimension \(n\)) in the affine geometry \(AG_n (F)\), where
Wraps some functions used in GAP Design’s PGPointFlatBlockDesign. Does not require GAP’s Design package.
EXAMPLES:
sage: BD = designs.AffineGeometryDesign(3, 1, GF(2))
sage: BD.is_t_design(return_parameters=True)
(True, (2, 8, 2, 1))
sage: BD = designs.AffineGeometryDesign(3, 2, GF(2))
sage: BD.is_t_design(return_parameters=True)
(True, (3, 8, 4, 1))
With an integer instead of a Finite Field:
sage: BD = designs.AffineGeometryDesign(3, 2, 4)
sage: BD.is_t_design(return_parameters=True)
(True, (2, 64, 16, 5))
Return the Desarguesian projective plane of order n as a 2-design.
The Desarguesian projective plane of order \(n\) can also be defined as the projective plane over a field of order \(n\). For more information, have a look at Wikipedia article Projective_plane.
INPUT:
See also
EXAMPLES:
sage: designs.DesarguesianProjectivePlaneDesign(2)
Incidence structure with 7 points and 7 blocks
sage: designs.DesarguesianProjectivePlaneDesign(3)
Incidence structure with 13 points and 13 blocks
sage: designs.DesarguesianProjectivePlaneDesign(4)
Incidence structure with 21 points and 21 blocks
sage: designs.DesarguesianProjectivePlaneDesign(5)
Incidence structure with 31 points and 31 blocks
sage: designs.DesarguesianProjectivePlaneDesign(6)
Traceback (most recent call last):
...
ValueError: the order of a finite field must be a prime power
Return the Hadamard 3-design with parameters \(3-(n, \frac n 2, \frac n 4 - 1)\).
This is the unique extension of the Hadamard \(2\)-design (see HadamardDesign()). We implement the description from pp. 12 in [CvL].
INPUT:
EXAMPLES:
sage: designs.Hadamard3Design(12)
Incidence structure with 12 points and 22 blocks
We verify that any two blocks of the Hadamard \(3\)-design \(3-(8, 4, 1)\) design meet in \(0\) or \(2\) points. More generally, it is true that any two blocks of a Hadamard \(3\)-design meet in \(0\) or \(\frac{n}{4}\) points (for \(n > 4\)).
sage: D = designs.Hadamard3Design(8)
sage: N = D.incidence_matrix()
sage: N.transpose()*N
[4 2 2 2 2 2 2 2 2 2 2 2 2 0]
[2 4 2 2 2 2 2 2 2 2 2 2 0 2]
[2 2 4 2 2 2 2 2 2 2 2 0 2 2]
[2 2 2 4 2 2 2 2 2 2 0 2 2 2]
[2 2 2 2 4 2 2 2 2 0 2 2 2 2]
[2 2 2 2 2 4 2 2 0 2 2 2 2 2]
[2 2 2 2 2 2 4 0 2 2 2 2 2 2]
[2 2 2 2 2 2 0 4 2 2 2 2 2 2]
[2 2 2 2 2 0 2 2 4 2 2 2 2 2]
[2 2 2 2 0 2 2 2 2 4 2 2 2 2]
[2 2 2 0 2 2 2 2 2 2 4 2 2 2]
[2 2 0 2 2 2 2 2 2 2 2 4 2 2]
[2 0 2 2 2 2 2 2 2 2 2 2 4 2]
[0 2 2 2 2 2 2 2 2 2 2 2 2 4]
REFERENCES:
[CvL] | P. Cameron, J. H. van Lint, Designs, graphs, codes and their links, London Math. Soc., 1991. |
As described in Section 1, p. 10, in [CvL]. The input n must have the property that there is a Hadamard matrix of order \(n+1\) (and that a construction of that Hadamard matrix has been implemented...).
EXAMPLES:
sage: designs.HadamardDesign(7)
Incidence structure with 7 points and 7 blocks
sage: print designs.HadamardDesign(7)
HadamardDesign<points=[0, 1, 2, 3, 4, 5, 6], blocks=[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]]>
For example, the Hadamard 2-design with \(n = 11\) is a design whose parameters are 2-(11, 5, 2). We verify that \(NJ = 5J\) for this design.
sage: D = designs.HadamardDesign(11); N = D.incidence_matrix()
sage: J = matrix(ZZ, 11, 11, [1]*11*11); N*J
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
[5 5 5 5 5 5 5 5 5 5 5]
REFERENCES:
Return a projective geometry design.
A projective geometry design of parameters \(n,d,F\) has for points the lines of \(F^{n+1}\), and for blocks the \(d+1\)-dimensional subspaces of \(F^{n+1}\), each of which contains \(\frac {|F|^{d+1}-1} {|F|-1}\) lines.
INPUT:
EXAMPLES:
The set of \(d\)-dimensional subspaces in a \(n\)-dimensional projective space forms \(2\)-designs (or balanced incomplete block designs):
sage: PG = designs.ProjectiveGeometryDesign(4,2,GF(2))
sage: PG
Incidence structure with 31 points and 155 blocks
sage: PG.is_t_design(return_parameters=True)
(True, (2, 31, 7, 7))
sage: PG = designs.ProjectiveGeometryDesign(3,1,GF(4,'z'))
sage: PG.is_t_design(return_parameters=True)
(True, (2, 85, 5, 1))
Check that the constructor using gap also works:
sage: BD = designs.ProjectiveGeometryDesign(2, 1, GF(2), algorithm="gap") # optional - gap_packages (design package)
sage: BD.is_t_design(return_parameters=True) # optional - gap_packages (design package)
(True, (2, 7, 3, 1))
INPUT:
Wraps GAP Design’s WittDesign. If n=24 then this function returns the large Witt design \(W_{24}\), the unique (up to isomorphism) \(5-(24,8,1)\) design. If n=12 then this function returns the small Witt design \(W_{12}\), the unique (up to isomorphism) \(5-(12,6,1)\) design. The other values of \(n\) return a block design derived from these.
EXAMPLES:
sage: BD = designs.WittDesign(9) # optional - gap_packages (design package)
sage: BD.is_t_design(return_parameters=True) # optional - gap_packages (design package)
(True, (2, 9, 3, 1))
sage: BD # optional - gap_packages (design package)
Incidence structure with 9 points and 12 blocks
sage: print BD # optional - gap_packages (design package)
WittDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8], blocks=[[0, 1, 7], [0, 2, 5], [0, 3, 4], [0, 6, 8], [1, 2, 6], [1, 3, 5], [1, 4, 8], [2, 3, 8], [2, 4, 7], [3, 6, 7], [4, 5, 6], [5, 7, 8]]>
Return True if the parameters (v,k,lmbda) are the one of hyperplanes in a (finite Desarguesian) projective space.
In other words, test whether there exists a prime power q and an integer d greater than two such that:
If it exists, such a pair (q,d) is unique.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.combinat.designs.block_design import are_hyperplanes_in_projective_geometry_parameters
sage: are_hyperplanes_in_projective_geometry_parameters(40,13,4)
True
sage: are_hyperplanes_in_projective_geometry_parameters(40,13,4,return_parameters=True)
(True, (3, 3))
sage: PG = designs.ProjectiveGeometryDesign(3,2,GF(3))
sage: PG.is_t_design(return_parameters=True)
(True, (2, 40, 13, 4))
sage: are_hyperplanes_in_projective_geometry_parameters(15,3,1)
False
sage: are_hyperplanes_in_projective_geometry_parameters(15,3,1,return_parameters=True)
(False, (None, None))
TESTS:
sage: sgp = lambda q,d: ((q**(d+1)-1)//(q-1), (q**d-1)//(q-1), (q**(d-1)-1)//(q-1))
sage: for q in [3,4,5,7,8,9,11]:
....: for d in [2,3,4,5]:
....: v,k,l = sgp(q,d)
....: assert are_hyperplanes_in_projective_geometry_parameters(v,k,l,True) == (True, (q,d))
....: assert are_hyperplanes_in_projective_geometry_parameters(v+1,k,l) is False
....: assert are_hyperplanes_in_projective_geometry_parameters(v-1,k,l) is False
....: assert are_hyperplanes_in_projective_geometry_parameters(v,k+1,l) is False
....: assert are_hyperplanes_in_projective_geometry_parameters(v,k-1,l) is False
....: assert are_hyperplanes_in_projective_geometry_parameters(v,k,l+1) is False
....: assert are_hyperplanes_in_projective_geometry_parameters(v,k,l-1) is False
Return a projective plane of order n as a 2-design.
A finite projective plane is a 2-design with \(n^2+n+1\) lines (or blocks) and \(n^2+n+1\) points. For more information on finite projective planes, see the Wikipedia article Projective_plane#Finite_projective_planes.
If no construction is possible, then the function raises a EmptySetError whereas if no construction is available the function raises a NotImplementedError.
INPUT:
EXAMPLES:
sage: designs.projective_plane(2)
Incidence structure with 7 points and 7 blocks
sage: designs.projective_plane(3)
Incidence structure with 13 points and 13 blocks
sage: designs.projective_plane(4)
Incidence structure with 21 points and 21 blocks
sage: designs.projective_plane(5)
Incidence structure with 31 points and 31 blocks
sage: designs.projective_plane(6)
Traceback (most recent call last):
...
EmptySetError: By the Bruck-Ryser theorem, no projective plane of order 6 exists.
sage: designs.projective_plane(10)
Traceback (most recent call last):
...
EmptySetError: No projective plane of order 10 exists by C. Lam, L. Thiel and S. Swiercz "The nonexistence of finite projective planes of order 10" (1989), Canad. J. Math.
sage: designs.projective_plane(12)
Traceback (most recent call last):
...
NotImplementedError: If such a projective plane exists, we do not know how to build it.
sage: designs.projective_plane(14)
Traceback (most recent call last):
...
EmptySetError: By the Bruck-Ryser theorem, no projective plane of order 14 exists.
TESTS:
sage: designs.projective_plane(2197, existence=True)
True
sage: designs.projective_plane(6, existence=True)
False
sage: designs.projective_plane(10, existence=True)
False
sage: designs.projective_plane(12, existence=True)
Unknown
Return the orthogonal array built from the projective plane pplane.
The orthogonal array \(OA(n+1,n,2)\) is obtained from the projective plane pplane by removing the point pt and the \(n+1\) lines that pass through it`. These \(n+1\) lines form the \(n+1\) groups while the remaining \(n^2+n\) lines form the transversals.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.block_design import projective_plane_to_OA
sage: p2 = designs.DesarguesianProjectivePlaneDesign(2)
sage: projective_plane_to_OA(p2)
[[0, 0, 0], [0, 1, 1], [1, 0, 1], [1, 1, 0]]
sage: p3 = designs.DesarguesianProjectivePlaneDesign(3)
sage: projective_plane_to_OA(p3)
[[0, 0, 0, 0],
[0, 1, 2, 1],
[0, 2, 1, 2],
[1, 0, 2, 2],
[1, 1, 1, 0],
[1, 2, 0, 1],
[2, 0, 1, 1],
[2, 1, 0, 2],
[2, 2, 2, 0]]
sage: pp = designs.DesarguesianProjectivePlaneDesign(16)
sage: _ = projective_plane_to_OA(pp, pt=0)
sage: _ = projective_plane_to_OA(pp, pt=3)
sage: _ = projective_plane_to_OA(pp, pt=7)
Return the design’s parameters: \((t, v, b, r , k, L)\). Note that \(t\) must be given.
EXAMPLES:
sage: BD = designs.BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: from sage.combinat.designs.block_design import tdesign_params
sage: tdesign_params(2,7,3,1)
(2, 7, 7, 3, 3, 1)