Block designs¶
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) |
[Hu57] | Daniel R. Hughes, “A class of non-Desarguesian projective planes”, The Canadian Journal of Mathematics (1957), http://cms.math.ca/cjm/v9/p378 |
[We07] | Charles Weibel, “Survey of Non-Desarguesian planes” (2007), notices of the AMS, vol. 54 num. 10, pages 1294–1303 |
AUTHORS:
Quentin Honoré (2015): construction of Hughes plane trac ticket #18527
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 more finite non-Desarguesian plane as in [We07] and Wikipedia article Non-Desarguesian_plane.
Functions and methods¶
-
sage.combinat.designs.block_design.
AffineGeometryDesign
(n, d, F)¶ Return an Affine Geometry Design.
INPUT:
(integer) – the Euclidean dimension. The number of points is
.
(integer) – the dimension of the (affine) subspaces of
which make up the blocks.
– a Finite Field (i.e.
FiniteField(17)
), or a prime power (i.e. an integer)
, 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))
-
sage.combinat.designs.block_design.
DesarguesianProjectivePlaneDesign
(n, check=True)¶ 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:
n
– an integer which must be a power of a prime numbercheck
– (boolean) Whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set toTrue
by default.
See also
EXAMPLES:
sage: designs.DesarguesianProjectivePlaneDesign(2) (7,3,1)-Balanced Incomplete Block Design sage: designs.DesarguesianProjectivePlaneDesign(3) (13,4,1)-Balanced Incomplete Block Design sage: designs.DesarguesianProjectivePlaneDesign(4) (21,5,1)-Balanced Incomplete Block Design sage: designs.DesarguesianProjectivePlaneDesign(5) (31,6,1)-Balanced Incomplete Block Design sage: designs.DesarguesianProjectivePlaneDesign(6) Traceback (most recent call last): ... ValueError: the order of a finite field must be a prime power
-
sage.combinat.designs.block_design.
Hadamard3Design
(n)¶ 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:
n
(integer) – a multiple of 4 such that.
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.
-
sage.combinat.designs.block_design.
HadamardDesign
(n)¶ 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) Incidence structure with 7 points and 7 blocks
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:
- [CvL] P. Cameron, J. H. van Lint, Designs, graphs, codes and their links, London Math. Soc., 1991.
-
sage.combinat.designs.block_design.
HughesPlane
(q2, check=True)¶ Return the Hughes projective plane of order
q2
.Let
be an odd prime, the Hughes plane of order
is a finite projective plane of order
introduced by D. Hughes in [Hu57]. Its construction is as follows.
Let
be a finite field with
elements and
be its unique subfield with
elements. We define a twisted multiplication on
as
The points of the Hughes plane are the triples
of points in
up to the equivalence relation
where
.
For
or
we define a block
as the set of triples
so that
. The rest of the blocks are obtained by letting act the group
by its standard action.
For more information, see Wikipedia article Hughes_plane and [We07].
See also
DesarguesianProjectivePlaneDesign()
to build the Desarguesian projective planesINPUT:
q2
– an even power of an odd prime numbercheck
– (boolean) Whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set toTrue
by default.
EXAMPLES:
sage: H = designs.HughesPlane(9) sage: H (91,10,1)-Balanced Incomplete Block Design
We prove in the following computations that the Desarguesian plane
H
is not Desarguesian. Let us consider the two trianglesand
. We show that the intersection points
,
and
are on the same line while
,
and
are not concurrent:
sage: blocks = H.blocks() sage: line = lambda p,q: (b for b in blocks if p in b and q in b).next() sage: b_0_1 = line(0, 1) sage: b_1_10 = line(1, 10) sage: b_10_0 = line(10, 0) sage: b_57_70 = line(57, 70) sage: b_70_59 = line(70, 59) sage: b_59_57 = line(59, 57) sage: set(b_0_1).intersection(b_57_70) {2} sage: set(b_1_10).intersection(b_70_59) {73} sage: set(b_10_0).intersection(b_59_57) {60} sage: line(2, 73) == line(73, 60) True sage: b_0_57 = line(0, 57) sage: b_1_70 = line(1, 70) sage: b_10_59 = line(10, 59) sage: p = set(b_0_57).intersection(b_1_70) sage: q = set(b_1_70).intersection(b_10_59) sage: p == q False
TESTS:
Some wrong input:
sage: designs.HughesPlane(5) Traceback (most recent call last): ... EmptySetError: No Hughes plane of non-square order exists. sage: designs.HughesPlane(16) Traceback (most recent call last): ... EmptySetError: No Hughes plane of even order exists.
Check that it works for non-prime
:
sage: designs.HughesPlane(3**4) # not tested - 10 secs (6643,82,1)-Balanced Incomplete Block Design
-
sage.combinat.designs.block_design.
ProjectiveGeometryDesign
(n, d, F, algorithm=None, check=True)¶ 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:
n
is the projective dimensiond
is the dimension of the subspaces ofwhich make up the blocks.
F
is a finite field.algorithm
– set toNone
by default, which results in using Sage’s own implementation. In order to use GAP’s implementation instead (i.e. itsPGPointFlatBlockDesign
function) setalgorithm="gap"
. Note that GAP’s “design” package must be available in this case, and that it can be installed with thegap_packages
spkg.
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))
-
sage.combinat.designs.block_design.
WittDesign
(n)¶ INPUT:
n
is in.
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) Incidence structure with 9 points and 12 blocks
-
sage.combinat.designs.block_design.
are_hyperplanes_in_projective_geometry_parameters
(v, k, lmbda, return_parameters=False)¶ 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 integerd
greater than two such that:If it exists, such a pair
(q,d)
is unique.INPUT:
v,k,lmbda
(integers)
OUTPUT:
- a boolean or, if
return_parameters
is set toTrue
a pair(True, (q,d))
or(False, (None,None))
.
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
-
sage.combinat.designs.block_design.
normalize_hughes_plane_point
(p, q)¶ Return the normalized form of point
p
as a 3-tuple.In the Hughes projective plane over the finite field
, all triples
with
represent the same point (where the multiplication is over the nearfield built from
). This function chooses a canonical representative among them.
This function is used in
HughesPlane()
.INPUT:
p
- point with the coordinates (x,y,z) (a list, a vector, a tuple...)q
- cardinality of the underlying finite field
EXAMPLES:
sage: from sage.combinat.designs.block_design import normalize_hughes_plane_point sage: K = FiniteField(9,'x') sage: x = K.gen() sage: normalize_hughes_plane_point((x, x+1, x), 9) (1, x, 1) sage: normalize_hughes_plane_point(vector((x,x,x)), 9) (1, 1, 1) sage: zero = K.zero() sage: normalize_hughes_plane_point((2*x+2, zero, zero), 9) (1, 0, 0) sage: one = K.one() sage: normalize_hughes_plane_point((2*x, one, zero), 9) (2*x, 1, 0)
-
sage.combinat.designs.block_design.
projective_plane
(n, check=True, existence=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 aNotImplementedError
.INPUT:
n
– the finite projective plane’s order
EXAMPLES:
sage: designs.projective_plane(2) (7,3,1)-Balanced Incomplete Block Design sage: designs.projective_plane(3) (13,4,1)-Balanced Incomplete Block Design sage: designs.projective_plane(4) (21,5,1)-Balanced Incomplete Block Design sage: designs.projective_plane(5) (31,6,1)-Balanced Incomplete Block Design 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
-
sage.combinat.designs.block_design.
projective_plane_to_OA
(pplane, pt=None, check=True)¶ Return the orthogonal array built from the projective plane
pplane
.The orthogonal array
is obtained from the projective plane
pplane
by removing the pointpt
and thelines that pass through it`. These
lines form the
groups while the remaining
lines form the transversals.
INPUT:
pplane
- a projective plane as a 2-designpt
- a point in the projective planepplane
. If it is not provided then it is set to.
check
– (boolean) Whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set toTrue
by default.
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)
-
sage.combinat.designs.block_design.
q3_minus_one_matrix
(K)¶ Return a companion matrix in
whose multiplicative order is
.
This function is used in
HughesPlane()
EXAMPLES:
sage: from sage.combinat.designs.block_design import q3_minus_one_matrix sage: m = q3_minus_one_matrix(GF(3)) sage: m.multiplicative_order() == 3**3 - 1 True sage: m = q3_minus_one_matrix(GF(4,'a')) sage: m.multiplicative_order() == 4**3 - 1 True sage: m = q3_minus_one_matrix(GF(5)) sage: m.multiplicative_order() == 5**3 - 1 True sage: m = q3_minus_one_matrix(GF(9,'a')) sage: m.multiplicative_order() == 9**3 - 1 True
-
sage.combinat.designs.block_design.
tdesign_params
(t, v, k, L)¶ 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)