This module implements several functions to find recursive constructions of Orthogonal Arrays.
The main function of this module, i.e. find_recursive_construction(), queries all implemented recursive constructions of designs. It is used by Sage’s function orthogonal_array().
REFERENCES:
[AC07] | (1, 2, 3, 4, 5, 6, 7, 8, 9) Concerning eight mutually orthogonal latin squares Julian R. Abel, Nicholas Cavenagh Journal of Combinatorial Designs Vol. 15, n.3, pp. 255-261 2007 |
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_recursive import OA_and_oval
sage: _ = OA_and_oval
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_recursive import find_construction_3_3
sage: from sage.combinat.designs.orthogonal_arrays_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
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
.
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_construction_3_4
sage: from sage.combinat.designs.orthogonal_arrays_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
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
.
This is construction 3.5 from [AC07].
INPUT:
The following designs must be available :
.
See also
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_construction_3_5
sage: from sage.combinat.designs.orthogonal_arrays_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
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_recursive import find_construction_3_6
sage: from sage.combinat.designs.orthogonal_arrays_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
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.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import construction_q_x
sage: _ = construction_q_x(9,16,6)
REFERENCES:
[Greig99] | Designs from projective planes and PBD bases Malcolm Greig Journal of Combinatorial Designs vol. 7, num. 5, pp. 341–374 1999 |
Finds a decomposition for construction 3.3 from [AC07]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_construction_3_3
sage: find_construction_3_3(11,177)[1]
(11, 11, 16, 1)
sage: find_construction_3_3(12,11)
Finds a decomposition for construction 3.4 from [AC07]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_construction_3_4
sage: find_construction_3_4(8,196)[1]
(8, 25, 7, 12, 9)
sage: find_construction_3_4(9,24)
Finds a decomposition for construction 3.5 from [AC07]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_construction_3_5
sage: find_construction_3_5(8,111)[1]
(8, 13, 6, 11, 11, 11)
sage: find_construction_3_5(9,24)
Finds a decomposition for construction 3.6 from [AC07]
INPUT:
See also
OUTPUT:
A pair f,args such that f(*args) returns the requested OA.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_construction_3_6
sage: find_construction_3_6(8,95)[1]
(8, 13, 7, 4)
sage: find_construction_3_6(8,98)
Look for a factorization of in order to build an
.
If Sage can build a and a
such that
then a
can be built by a product construction (which
correspond to Wilson’s construction with no truncated column). This
function look for a pair of integers
with
,
and such that both an
and an
are
available.
INPUT:
OUTPUT:
A pair f,args such that f(*args) is an or False if no
product decomposition was found.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_product_decomposition
sage: f,args = find_product_decomposition(6, 84)
sage: args
(6, 7, 12, ())
sage: _ = f(*args)
Find integers such that the
construction yields an
.
See the documentation of construction_q_x() to find out what
hypotheses the integers must satisfy.
Warning
For efficiency reasons, this function checks that Sage can build an
and an
, which is stronger than checking
that Sage can build a
and a
. The latter would trigger a lot of
independent set computations in
sage.combinat.designs.orthogonal_arrays.incomplete_orthogonal_array().
INPUT:
See also
EXAMPLE:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_q_x
sage: find_q_x(10,9)
False
sage: find_q_x(9,158)[1]
(9, 16, 6)
Find a recursive construction of a
This determines whether an can be built through the following
constructions:
INPUT:
OUTPUT:
Return a pair f,args such that f(*args) returns the requested
if possible, and False otherwise.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_recursive_construction
sage: from sage.combinat.designs.orthogonal_arrays import is_orthogonal_array
sage: count = 0
sage: for n in range(10,150):
....: k = designs.orthogonal_array(None,n,existence=True)
....: if find_recursive_construction(k,n):
....: count = count + 1
....: f,args = find_recursive_construction(k,n)
....: OA = f(*args)
....: assert is_orthogonal_array(OA,k,n,2,verbose=True)
sage: print count
54
Helper function for Wilson’s construction with one truncated column.
This function looks for possible integers satisfying that
and
such that Sage knows how to build a
and a
.
INPUT:
OUTPUT:
A pair f,args such that f(*args) is an or False if no
decomposition with one truncated block was found.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_wilson_decomposition_with_one_truncated_group
sage: f,args = find_wilson_decomposition_with_one_truncated_group(4,38)
sage: args
(4, 5, 7, (3,))
sage: _ = f(*args)
sage: find_wilson_decomposition_with_one_truncated_group(4,20)
False
Helper function for Wilson’s construction with two trucated columns.
Look for integers satisfying
and
and such that the following designs exist :
,
,
,
,
,
.
INPUT:
OUTPUT:
A pair f,args such that f(*args) is an or False if no
decomposition with two truncated blocks was found.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import find_wilson_decomposition_with_two_truncated_groups
sage: f,args = find_wilson_decomposition_with_two_truncated_groups(5,58)
sage: args
(5, 7, 7, (4, 5))
sage: _ = f(*args)
Return an from Wilson construction.
INPUT:
Todo
As soon as wilson construction accepts an empty master design we should remove this intermediate functions.
EXAMPLES:
sage: from sage.combinat.designs.orthogonal_arrays_recursive import simple_wilson_construction
sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array
sage: OA = simple_wilson_construction(6,7,12,())
sage: is_orthogonal_array(OA,6,84)
True
sage: OA = simple_wilson_construction(4,5,7,(3,))
sage: is_orthogonal_array(OA,4,38)
True
sage: OA = simple_wilson_construction(5,7,7,(4,5))
sage: is_orthogonal_array(OA,5,58)
True