Orthogonal arrays (Recursive constructions)

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

Functions

sage.combinat.designs.orthogonal_arrays_recursive.OA_and_oval(q)

Return a OA(q+1,q) whose blocks contains \leq 2 zeroes in the last q columns.

This OA is build from a projective plane of order q, in which there exists an oval O of size q+1 (i.e. a set of q+1 points no three of which are [colinear/contained in a common set of the projective plane]).

Removing an element x\in O and all sets that contain it, we obtain a TD(q+1,q) in which O intersects all columns except one. As O is an oval, no block of the TD intersects it more than twice.

INPUT:

  • q – a prime power

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
sage.combinat.designs.orthogonal_arrays_recursive.construction_3_3(k, n, m, i)

Return an OA(k,nm+i).

This is Wilson’s construction with i truncated columns of size 1 and such that a block B_0 of the incomplete OA intersects all truncated columns. As a consequence, all other blocks intersect only 0 or 1 of the last i columns. This allow to consider the block B_0 only up to its first k coordinates and then use a OA(k,i) instead of a OA(k,m+i) - i.OA(k,1).

This is construction 3.3 from [AC07].

INPUT:

  • k,n,m,i (integers) such that the following designs are available : OA(k,n),OA(k,m),OA(k,m+1),OA(k,r).

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
sage.combinat.designs.orthogonal_arrays_recursive.construction_3_4(k, n, m, r, s)

Return a OA(k,nm+rs).

This is Wilson’s construction applied to a truncated OA(k+r+1,n) with r columns of size 1 and one column of size s.

The unique elements of the r truncated columns are picked so that a block B_0 contains them all.

  • If there exists an OA(k,m+r+1) the column of size s is truncated in order to intersect B_0.
  • Otherwise, if there exists an OA(k,m+r), the last column must not intersect B_0

This is construction 3.4 from [AC07].

INPUT:

  • k,n,m,r,s (integers) – we assume that s<n and 1\leq r,s

    The following designs must be available: OA(k,n),OA(k,m),OA(k,m+1),OA(k,m+2),OA(k,s). Additionnally, it requires either a OA(k,m+r) or a OA(k,m+r+1).

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
sage.combinat.designs.orthogonal_arrays_recursive.construction_3_5(k, n, m, r, s, t)

Return an OA(k,nm+r+s+t).

This is exactly Wilson’s construction with three truncated groups except we make sure that all blocks have size >k, so we don’t need a OA(k,m+0) but only OA(k,m+1),OA(k,m+2),OA(k,m+3).

This is construction 3.5 from [AC07].

INPUT:

  • k,n,m (integers)
  • r,s,t (integers) – sizes of the three truncated groups, such that r\leq s and (q-r-1)(q-s) \geq (q-s-1)*(q-r).

The following designs must be available : OA(k,n),OA(k,r),OA(k,s),OA(k,t),OA(k,m+1),OA(k,m+2),OA(k,m+3).

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
sage.combinat.designs.orthogonal_arrays_recursive.construction_3_6(k, n, m, i)

Return a OA(k,nm+i)

This is Wilson’s construction with r columns of order 1, in which each block intersects at most two truncated columns. Such a design exists when n is a prime power and is returned by OA_and_oval().

INPUT:

  • k,n,m,i (integers) – n must be a prime power. The following designs must be available: OA(k+r,q),OA(k,m),OA(k,m+1),OA(k,m+2).

This is construction 3.6 from [AC07].

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
sage.combinat.designs.orthogonal_arrays_recursive.construction_q_x(k, q, x, check=True)

Return an OA(k,(q-1)*(q-x)+x+2) using the q-x construction.

Let v=(q-1)*(q-x)+x+2. If there exists a projective plane of order q (e.g. when q is a prime power) and 0<x<q then there exists a (v-1,\{q-x-1,q-x+1\})-GDD of type (q-1)^{q-x}(x+1)^1 (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 (v,\{q-x-1,q-x+1,q,x+2\})-PBD with exactly one set of size x+2.

Thus, assuming that we have the following:

  • OA(k,q-x-1)-(q-x-1).OA(k,1)
  • OA(k,q-x+1)-(q-x+1).OA(k,1)
  • OA(k,q)-q.OA(k,1)
  • OA(k,x+2)

Then we can build from the PBD an OA(k,v).

Construction of the PBD (shared by Julian R. Abel):

Start with a resolvable (q^2,q,1)-BIBD and put the points into a q\times q array so that rows form a parallel class and columns form another.

Now delete:

  • All x(q-1) points from the first x columns and not in the first row
  • All q-x points in the last q-x columns AND the first row.

Then add a point p_1 to the blocks that are rows. Add a second point p_2 to the q-x blocks that are columns of size q-1, plus the first row of size x+1.

INPUT:

  • k,q,x – integers such that 0<x<q and such that Sage can build:

    • A projective plane of order q
    • OA(k,q-x-1)-(q-x-1).OA(k,1)
    • OA(k,q-x+1)-(q-x+1).OA(k,1)
    • OA(k,q)-q.OA(k,1)
    • OA(k,x+2)
  • 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
sage.combinat.designs.orthogonal_arrays_recursive.find_construction_3_3(k, n)

Finds a decomposition for construction 3.3 from [AC07]

INPUT:

  • k,n (integers)

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)
sage.combinat.designs.orthogonal_arrays_recursive.find_construction_3_4(k, n)

Finds a decomposition for construction 3.4 from [AC07]

INPUT:

  • k,n (integers)

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)
sage.combinat.designs.orthogonal_arrays_recursive.find_construction_3_5(k, n)

Finds a decomposition for construction 3.5 from [AC07]

INPUT:

  • k,n (integers)

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)
sage.combinat.designs.orthogonal_arrays_recursive.find_construction_3_6(k, n)

Finds a decomposition for construction 3.6 from [AC07]

INPUT:

  • k,n (integers)

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)
sage.combinat.designs.orthogonal_arrays_recursive.find_product_decomposition(k, n)

Look for a factorization of n in order to build an OA(k,n).

If Sage can build a OA(k,n_1) and a OA(k,n_2) such that n=n_1\times
n_2 then a OA(k,n) 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 (n_1,n_2) with n1 \leq n_2, n_1
\times n_2 = n and such that both an OA(k,n_1) and an OA(k,n_2) are available.

INPUT:

  • k,n (integers) – see above.

OUTPUT:

A pair f,args such that f(*args) is an OA(k,n) 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)
sage.combinat.designs.orthogonal_arrays_recursive.find_q_x(k, n)

Find integers q,x such that the q-x construction yields an OA(k,n).

See the documentation of construction_q_x() to find out what hypotheses the integers q,x must satisfy.

Warning

For efficiency reasons, this function checks that Sage can build an OA(k+1,q-x-1) and an OA(k+1,q-x+1), which is stronger than checking that Sage can build a OA(k,q-x-1)-(q-x-1).OA(k,1) and a OA(k,q-x+1)-(q-x+1).OA(k,1). The latter would trigger a lot of independent set computations in sage.combinat.designs.orthogonal_arrays.incomplete_orthogonal_array().

INPUT:

  • k,n (integers)

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)
sage.combinat.designs.orthogonal_arrays_recursive.find_recursive_construction(k, n)

Find a recursive construction of a OA(k,n)

This determines whether an OA(k,n) can be built through the following constructions:

INPUT:

  • k,n (integers)

OUTPUT:

Return a pair f,args such that f(*args) returns the requested OA 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
sage.combinat.designs.orthogonal_arrays_recursive.find_wilson_decomposition_with_one_truncated_group(k, n)

Helper function for Wilson’s construction with one truncated column.

This function looks for possible integers m,t,u satisfying that mt+u=n and such that Sage knows how to build a OA(k,m), OA(k,m+1),OA(k+1,t) and a OA(k,u).

INPUT:

  • k,n (integers) – see above

OUTPUT:

A pair f,args such that f(*args) is an OA(k,n) 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
sage.combinat.designs.orthogonal_arrays_recursive.find_wilson_decomposition_with_two_truncated_groups(k, n)

Helper function for Wilson’s construction with two trucated columns.

Look for integers r,m,r_1,r_2 satisfying n=rm+r_1+r_2 and 1\leq r_1,r_2<r and such that the following designs exist : OA(k+2,r), OA(k,r1), OA(k,r2), OA(k,m), OA(k,m+1), OA(k,m+2).

INPUT:

  • k,n (integers) – see above

OUTPUT:

A pair f,args such that f(*args) is an OA(k,n) 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)
sage.combinat.designs.orthogonal_arrays_recursive.simple_wilson_construction(k, r, m, u)

Return an OA(k,rm + \sum u_i) from Wilson construction.

INPUT:

  • k,r,m – integers
  • u – list of positive integers

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

Table Of Contents

Previous topic

Orthogonal arrays

Next topic

Difference families

This Page