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:
, as it is sometimes denoted, is a
-
design of points and
- flats (cosets of dimension
) in the affine
geometry
, 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 can also be defined as the
projective plane over a field of order
. 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 .
This is the unique extension of the Hadamard -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 -design
design meet in
or
points. More generally, it is true that any two
blocks of a Hadamard
-design meet in
or
points (for
).
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 (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 is a design whose parameters are 2-(11, 5, 2).
We verify that
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 has for points the lines
of
, and for blocks the
-dimensional subspaces of
,
each of which contains
lines.
INPUT:
EXAMPLES:
The set of -dimensional subspaces in a
-dimensional projective space
forms
-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 , the unique (up to isomorphism)
design. If n=12 then this function returns the small Witt design
, the unique (up to isomorphism)
design. The other
values of
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 lines (or blocks) and
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 is obtained from the projective plane
pplane by removing the point pt and the
lines that pass
through it`. These
lines form the
groups while the remaining
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: . Note that
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)