This module implements several constructions of Orthogonal Arrays. As their input can be complex, they all have a counterpart in the orthogonal_arrays_find_recursive module that automatically computes it.
All these constructions are automatically queried when the orthogonal_array() function is called.
construction_3_3() | Return an ![]() |
construction_3_4() | Return a ![]() |
construction_3_5() | Return an ![]() |
construction_3_6() | Return a ![]() |
construction_q_x() | Return an ![]() ![]() |
OA_and_oval() | Return a ![]() ![]() ![]() |
thwart_lemma_3_5() | Returns an ![]() |
thwart_lemma_4_1() | Returns an ![]() |
three_factor_product() | Returns an ![]() |
brouwer_separable_design() | Returns a ![]() |
Return a whose blocks contains
zeroes in the last
columns.
This is build from a projective plane of order
, in which there
exists an oval
of size
(i.e. a set of
points no three of which
are [colinear/contained in a common set of the projective plane]).
Removing an element and all sets that contain it, we obtain a
in which
intersects all columns except one. As
is an
oval, no block of the
intersects it more than twice.
INPUT:
Note
This function is called by construction_3_6(), an implementation of Construction 3.6 from [AC07].
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import OA_and_oval
sage: _ = OA_and_oval
Returns a using Brouwer’s result on separable designs.
This method is an implementation of Brouwer’s construction presented in [Brouwer80]. It consists in a systematic application of the usual transformation from PBD to OA, applied to a specific PBD.
Baer subplanes
When is a prime power, the projective plane
can be
partitionned into subplanes
(called Baer subplanes), giving
. As a result, every line of the
intersects one of the subplane on
points and all others on
point.
The are built by considering
, for a total of
points (to which
new points are then added). The blocks of
this subdesign belong to two categories:
Constructions
In the following, we write . The code is also heavily
commented, and will clear any doubt.
i) : in that case we build a resolvable
that will then be
completed into an
.
Sets of size
)
We take the product of each parallel class with the parallel classes of a resolvable
, yielding new parallel classes.
Sets of size
)
A
array is built whose rows are the sets of size
such that every value appears once per column. For each block of a
, the product with the rows of the matrix yields a parallel class.
Sets of size
)
Each set of size
gives a
, except if there is only one parallel class in which case a
is sufficient.
Sets of size
)
A
array
is built whose
rows are the sets of size
such that every value appears once per column. For each of the new
points
we build a matrix
obtained from
by adding a column equal to
. We add to the OA the product of all rows of the
with the block of the
parallel classes of a resolvable
.
Set of size
) An
Sets of size
)
All blocks of the
-th parallel class are extended with the
-th new point. The blocks are then replaced by a
or, if there is only one parallel class (i.e.
) by a
.
Set of size
)
They are replaced by
.
Set of size
) An
Sets of size
)
All blocks of the
-th parallel class are extended with the
-th new point (the other
new points are not touched at this step). The blocks are then replaced by a
or, if there is only one parallel class (i.e.
) by a
.
Sets of size
) Same as for ii)
Set of size
) An
Sets of size
)
The blocks of the first
parallel class are extended with the
new points, and replaced with
or, if
, by
The blocks of the other parallel classes are replaced by
or, if there is only one class left, by
Sets of size
)
They are replaced with
.
Set of size
) An
- Sets of size
) Same as in v) with an
equal to
.
- Sets of size
) Same as in vii)
- Set of size
) An
INPUT:
See also
REFERENCES:
[Brouwer80] | A Series of Separable Designs with Application to Pairwise Orthogonal Latin Squares, Andries E. Brouwer, Vol. 1, n. 1, pp. 39-41, European Journal of Combinatorics, 1980 http://www.sciencedirect.com/science/article/pii/S0195669880800199 |
EXAMPLES:
Test all possible cases:
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import brouwer_separable_design
sage: k,q,t=4,4,3; _=brouwer_separable_design(k,q,t,0,verbose=True)
Case i) with k=4,q=3,t=4,x=0
sage: k,q,t=3,3,3; _=brouwer_separable_design(k,t,q,t+q,verbose=True,check=True)
Case ii) with k=3,q=3,t=3,x=6,e3=1
sage: k,q,t=3,3,6; _=brouwer_separable_design(k,t,q,t+q,verbose=True,check=True)
Case ii) with k=3,q=3,t=6,x=9,e3=0
sage: k,q,t=3,3,6; _=brouwer_separable_design(k,t,q,q**2-q+1-t,verbose=True,check=True)
Case iii) with k=3,q=3,t=6,x=1,e2=0
sage: k,q,t=3,4,6; _=brouwer_separable_design(k,t,q,q**2-q+1-t,verbose=True,check=True)
Case iii) with k=3,q=4,t=6,x=7,e2=1
sage: k,q,t=3,4,6; _=brouwer_separable_design(k,t,q,q**2+1,verbose=True,check=True)
Case iv) with k=3,q=4,t=6,x=17,e4=1
sage: k,q,t=3,2,2; _=brouwer_separable_design(k,t,q,q**2+1,verbose=True,check=True)
Case iv) with k=3,q=2,t=2,x=5,e4=0
sage: k,q,t=3,4,7; _=brouwer_separable_design(k,t,q,3,verbose=True,check=True)
Case v) with k=3,q=4,t=7,x=3,e1=1,e2=1
sage: k,q,t=3,4,7; _=brouwer_separable_design(k,t,q,1,verbose=True,check=True)
Case v) with k=3,q=4,t=7,x=1,e1=1,e2=0
sage: k,q,t=3,4,7; _=brouwer_separable_design(k,t,q,q**2-q-t,verbose=True,check=True)
Case v) with k=3,q=4,t=7,x=5,e1=0,e2=1
sage: k,q,t=5,4,7; _=brouwer_separable_design(k,t,q,t+q+3,verbose=True,check=True)
Case vi) with k=5,q=4,t=7,x=14,e3=1,e4=1
sage: k,q,t=5,4,8; _=brouwer_separable_design(k,t,q,t+q+1,verbose=True,check=True)
Case vi) with k=5,q=4,t=8,x=13,e3=1,e4=0
sage: k,q,t=5,4,8; _=brouwer_separable_design(k,t,q,q**2,verbose=True,check=True)
Case vi) with k=5,q=4,t=8,x=16,e3=0,e4=1
sage: print designs.orthogonal_arrays.explain_construction(10,189)
Brouwer's separable design construction with t=9,q=4,x=0 from:
Andries E. Brouwer,
A series of separable designs with application to pairwise orthogonal Latin squares
Vol. 1, n. 1, pp. 39-41,
European Journal of Combinatorics, 1980
Return an .
This is Wilson’s construction with truncated columns of size 1 and such
that a block
of the incomplete OA intersects all truncated columns. As
a consequence, all other blocks intersect only
or
of the last
columns. This allow to consider the block
only up to its first
coordinates and then use a
instead of a
.
This is construction 3.3 from [AC07].
INPUT:
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_construction_3_3
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import construction_3_3
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array
sage: k=11;n=177
sage: is_orthogonal_array(construction_3_3(*find_construction_3_3(k,n)[1]),k,n,2)
True
sage: print designs.orthogonal_arrays.explain_construction(9,91)
Construction 3.3 with n=11,m=8,i=3 from:
Julian R. Abel, Nicholas Cavenagh
Concerning eight mutually orthogonal latin squares,
Vol. 15, n.3, pp. 255-261,
Journal of Combinatorial Designs, 2007
Return a .
This is Wilson’s construction applied to a truncated with
columns of size
and one column of size
.
The unique elements of the truncated columns are picked so that a block
contains them all.
This is construction 3.4 from [AC07].
INPUT:
k,n,m,r,s (integers) – we assume that and
The following designs must be available: ,
,
,
,
. Additionnally, it requires either a
or a
.
explain_construction (boolean) – return a string describing the construction.
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_construction_3_4
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import construction_3_4
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array
sage: k=8;n=196
sage: is_orthogonal_array(construction_3_4(*find_construction_3_4(k,n)[1]),k,n,2)
True
sage: print designs.orthogonal_arrays.explain_construction(8,164)
Construction 3.4 with n=23,m=7,r=2,s=1 from:
Julian R. Abel, Nicholas Cavenagh
Concerning eight mutually orthogonal latin squares,
Vol. 15, n.3, pp. 255-261,
Journal of Combinatorial Designs, 2007
Return an .
This is exactly Wilson’s construction with three truncated groups
except we make sure that all blocks have size , so we don’t
need a
but only
,
,`OA(k,m+3)`.
This is construction 3.5 from [AC07].
INPUT:
The following designs must be available : ,
,
,
,
,
,
.
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_construction_3_5
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import construction_3_5
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array
sage: k=8;n=111
sage: is_orthogonal_array(construction_3_5(*find_construction_3_5(k,n)[1]),k,n,2)
True
sage: print designs.orthogonal_arrays.explain_construction(8,90)
Construction 3.5 with n=11,m=6,r=8,s=8,t=8 from:
Julian R. Abel, Nicholas Cavenagh
Concerning eight mutually orthogonal latin squares,
Vol. 15, n.3, pp. 255-261,
Journal of Combinatorial Designs, 2007
Return a
This is Wilson’s construction with columns of order
, in which each
block intersects at most two truncated columns. Such a design exists when
is a prime power and is returned by OA_and_oval().
INPUT:
This is construction 3.6 from [AC07].
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_construction_3_6
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import construction_3_6
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array
sage: k=8;n=95
sage: is_orthogonal_array(construction_3_6(*find_construction_3_6(k,n)[1]),k,n,2)
True
sage: print designs.orthogonal_arrays.explain_construction(10,756)
Construction 3.6 with n=16,m=47,i=4 from:
Julian R. Abel, Nicholas Cavenagh
Concerning eight mutually orthogonal latin squares,
Vol. 15, n.3, pp. 255-261,
Journal of Combinatorial Designs, 2007
Return an using the
construction.
Let . If there exists a projective plane of order
(e.g. when
is a prime power) and
then there exists a
-GDD of type
(see [Greig99] or
Theorem 2.50, section IV.2.3 of [DesignHandbook]). By adding to the ground
set one point contained in all groups of the GDD, one obtains a
-PBD with exactly one set of size
.
Thus, assuming that we have the following:
Then we can build from the PBD an .
Construction of the PBD (shared by Julian R. Abel):
Start with a resolvable
-BIBD and put the points into a
array so that rows form a parallel class and columns form another.
Now delete:
- All
points from the first
columns and not in the first row
- All
points in the last
columns AND the first row.
Then add a point
to the blocks that are rows. Add a second point
to the
blocks that are columns of size
, plus the first row of size
.
INPUT:
k,q,x – integers such that and such that Sage can build:
- A projective plane of order
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 to True by default.
explain_construction (boolean) – return a string describing the construction.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import construction_q_x
sage: _ = construction_q_x(9,16,6)
sage: print designs.orthogonal_arrays.explain_construction(9,158)
(q-x)-construction with q=16,x=6 from:
Malcolm Greig,
Designs from projective planes and PBD bases,
vol. 7, num. 5, pp. 341--374,
Journal of Combinatorial Designs, 1999
REFERENCES:
[Greig99] | Designs from projective planes and PBD bases Malcolm Greig Journal of Combinatorial Designs vol. 7, num. 5, pp. 341–374 1999 |
Returns an
The three factor product construction from [DukesLing14] does the following:
Ifare such that there exists an
,
and
, then there exists a
.
It works with a modified product of orthogonal arrays ([Rees93], [Rees00])
which keeps track of parallel classes in the (the definition is given
for transversal designs).
A subset of blocks in anis called a
-parallel class if every point is covered exactly
times. A 1-parallel class is a parallel class.
The modified product:
If there exists an
, and if there exists an
whose blocks are partitionned into
![]()
-parallel classes and
parallel classes, then there exists an
whose blocks can be partitionned into
parallel classes and
![]()
-parallel classes.
Proof:
The product of the blocks of a parallel class with an
yields an
-parallel class of an
.
The product of the blocks of a
-parallel class of
with an
can be done in such a way that it yields
parallel classes of
. Those classes cover exactly the pairs that woud have been covered with the usual product.
This can be achieved by simple cyclic permutations. Let us build the product of the
-parallel class
with
: when computing the product of
with
the
-th coordinate should not be
but
(the sum is mod
) where
is the number of blocks of
we have already processed whose
-th coordinate is equal to
(note that
as
is
-parallel).
With these tools, one can obtain the designs promised by the three factors
construction applied to (thanks to Julian R. Abel’s help):
- Let
be the largest integer
. Apply the product construction to
and a resolvable
whose blocks are partitionned into
![]()
-parallel classes and
parallel classes. It results in a
partitionned into
parallel classes plus
![]()
-parallel classes.
- Add
parallel classes to every
-parallel class to turn them into
-parallel classes. Apply the product construction to this partitionned
with a resolvable
.
- As
is resolvable, the
-parallel classes of
are actually the union of
parallel classes, thus the
is resolvable and can be turned into an
INPUT:
See also
EXAMPLE:
sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import three_factor_product
sage: OA = three_factor_product(4,4,4,4)
sage: is_orthogonal_array(OA,5,64)
True
sage: OA = three_factor_product(4,3,4,5)
sage: is_orthogonal_array(OA,5,60)
True
sage: OA = three_factor_product(5,4,5,7)
sage: is_orthogonal_array(OA,6,140)
True
sage: OA = three_factor_product(9,8,9,9) # long time
sage: is_orthogonal_array(OA,10,8*9*9) # long time
True
sage: print designs.orthogonal_arrays.explain_construction(10,648)
Three-factor product with n=8.9.9 from:
Peter J. Dukes, Alan C.H. Ling,
A three-factor product construction for mutually orthogonal latin squares,
http://arxiv.org/abs/1401.1466
REFERENCE:
[DukesLing14] | A three-factor product construction for mutually orthogonal latin squares, Peter J. Dukes, Alan C.H. Ling, http://arxiv.org/abs/1401.1466 |
[Rees00] | Truncated Transversal Designs: A New Lower Bound on the Number of Idempotent MOLS of Side, Rolf S. Rees, Journal of Combinatorial Theory, Series A 90.2 (2000): 257-266. |
[Rees93] | Two new direct product-type constructions for resolvable group-divisible designs, Rolf S. Rees, Journal of Combinatorial Designs 1.1 (1993): 15-26. |
Returns an
(When `d=0`)
According to [Thwarts] when is a prime power and
, one
can build an
with three truncated columns of sizes
in
such a way that all blocks have size
.
(in order to build a the following designs must also exist:
,
,
,
,
,
)
Considering the complement of each truncated column, it is also possible to
build an with three truncated columns of sizes
in such a
way that all blocks have size
whenever
.
(in order to build a the following designs must also exist:
,
,
,
,
,
)
Here is the proof of Lemma 3.5 from [Thwarts] enriched with explanations from Julian R. Abel:
For any prime power
one can build
MOLS by associating to every nonzero
the latin square:
In particular
, whose
columns and lines are indexed by the elements of
. If we order the elements of
as
and reorder the columns and lines of
accordingly, the top-left
squares contains at most
distinct symbols.
(When )
If there exists an with three truncated columns of sizes
in such a way that all blocks have size
, by truncating
arbitrarily another column to size
one obtains an
with 4 truncated
columns whose blocks miss at least one value. Thus, following the proof
again one can build an
with four truncated columns of sizes
with blocks of size
.
(in order to build a the following designs must also
exist:
,
,
,
,
,
,
,
)
As before, this also shows that one can build an with four
truncated columns of sizes
in such a way that all blocks have size
whenever
(in order to build a the following designs must also
exist:
,
,
,
,
,
,
,
)
INPUT:
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_build_recursive import thwart_lemma_3_5
sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array
sage: OA = thwart_lemma_3_5(6,23,7,5,7,8)
sage: is_orthogonal_array(OA,6,23*7+5+7+8,2)
True
sage: print designs.orthogonal_arrays.explain_construction(10,408)
Lemma 4.1 with n=13,m=28 from:
Charles J.Colbourn, Jeffrey H. Dinitz, Mieczyslaw Wojtas,
Thwarts in transversal designs,
Designs, Codes and Cryptography 5, no. 3 (1995): 189-197.
With sets of parameters from [Thwarts]:
sage: l = [
....: [11, 27, 78, 16, 17, 25, 0],
....: [12, 19, 208, 11, 13, 16, 0],
....: [12, 19, 208, 13, 13, 16, 0],
....: [10, 13, 78, 9, 9, 13, 1],
....: [10, 13, 79, 9, 9, 13, 1]]
sage: for k,n,m,a,b,c,d in l: # not tested -- too long
....: OA = thwart_lemma_3_5(k,n,m,a,b,c,d,complement=True) # not tested -- too long
....: assert is_orthogonal_array(OA,k,n*m+a+b+c+d,verbose=True) # not tested -- too long
sage: print designs.orthogonal_arrays.explain_construction(10,1046)
Lemma 3.5 with n=13,m=79,a=9,b=1,c=0,d=9 from:
Charles J.Colbourn, Jeffrey H. Dinitz, Mieczyslaw Wojtas,
Thwarts in transversal designs,
Designs, Codes and Cryptography 5, no. 3 (1995): 189-197.
REFERENCE:
[Thwarts] | (1, 2, 3, 4) Thwarts in transversal designs Charles J.Colbourn, Jeffrey H. Dinitz, Mieczyslaw Wojtas. Designs, Codes and Cryptography 5, no. 3 (1995): 189-197. |
Returns an .
Implements Lemma 4.1 from [Thwarts].
If
is a prime power, then there exists a truncated
whose last four columns have size
and intersect every block on
or
values. Consequently, if there exists an
,
,
and a
then there exists an
Proof: form the transversal design by removing one point of the
(Affine Geometry) contained in the Desarguesian Projective Plane
.
The affine geometry on 9 points contained in the projective geometry
is given explicitly in [OS64] (Thanks to Julian R. Abel for
finding the reference!).
INPUT:
See also
EXAMPLE:
sage: print designs.orthogonal_arrays.explain_construction(10,408)
Lemma 4.1 with n=13,m=28 from:
Charles J.Colbourn, Jeffrey H. Dinitz, Mieczyslaw Wojtas,
Thwarts in transversal designs,
Designs, Codes and Cryptography 5, no. 3 (1995): 189-197.
REFERENCES:
[OS64] | Finite projective planes with affine subplanes, T. G. Ostrom and F. A. Sherk. Canad. Math. Bull vol7 num.4 (1964) |