Orthogonal arrays (find recursive constructions)

Orthogonal arrays (find 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 implemented in orthogonal_arrays_build_recursive in order to obtain an OA(k,n).

find_recursive_construction() is called by the orthogonal_array() function.

find_recursive_construction() Find a recursive construction of an OA(k,n) (calls all others find_* functions)
find_product_decomposition() Find n_1n_2=n to obtain an OA(k,n) by the product construction
find_wilson_decomposition_with_one_truncated_group() Find rm+u=n to obtain an OA(k,n) by Wilson’s construction with one truncated column.
find_wilson_decomposition_with_two_truncated_groups() Find rm+r_1+r_2=n to obtain an OA(k,n) by Wilson’s construction with two truncated columns.
find_construction_3_3() Find a decomposition for construction 3.3 from [AC07].
find_construction_3_4() Find a decomposition for construction 3.4 from [AC07].
find_construction_3_5() Find a decomposition for construction 3.5 from [AC07].
find_construction_3_6() Find a decomposition for construction 3.6 from [AC07].
find_q_x() Find integers q,x such that the q-x construction yields an OA(k,n).
find_thwart_lemma_3_5() Find the values on which Lemma 3.5 from [Thwarts] applies.
find_thwart_lemma_4_1() Find a decomposition for Lemma 4.1 from [Thwarts].
find_three_factor_product() Find n_1n_2n_3=n to obtain an OA(k,n) by the three-factor product from [DukesLing14]
find_brouwer_separable_design() Find t(q^2+q+1)+x=n to obtain an OA(k,n) by Brouwer’s separable design construction.
find_brouwer_van_rees_with_one_truncated_column() Find rm+x_1+...+x_c=n such that the Brouwer-van Rees constructions yields a OA(k,n).

REFERENCES:

[AC07](1, 2, 3, 4, 5, 6, 7, 8) 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_find_recursive.find_brouwer_separable_design(k, n)

Find t(q^2+q+1)+x=n to obtain an OA(k,n) by Brouwer’s separable design construction.

INPUT:

  • k,n (integers)

The assumptions made on the parameters t,q,x are explained in the documentation of brouwer_separable_design().

EXAMPLE:

sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_brouwer_separable_design
sage: find_brouwer_separable_design(5,13)[1]
(5, 1, 3, 0)
sage: find_brouwer_separable_design(5,14)
False
sage.combinat.designs.orthogonal_arrays_find_recursive.find_brouwer_van_rees_with_one_truncated_column(k, n)

Find rm+x_1+...+x_c=n such that the Brouwer-van Rees constructions yields a OA(k,n).

Let n=rm+\sum_{1\leq i\leq c} such that c\leq r. The generalization of Wilson’s construction found by Brouwer and van Rees (with one truncated column) ensures that an OA(k,n) exists if the following designs exist: OA(k+1,r), OA(k,m), OA(k,\sum_{1\leq i\leq c} u_i), OA(k,m+x_1)-OA(k,x_1), ..., OA(k,m+x_c)-OA(k,x_c).

For more information, see the documentation of wilson_construction().

INPUT:

  • k,n (integers)

EXAMPLE:

sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_brouwer_van_rees_with_one_truncated_column
sage: find_brouwer_van_rees_with_one_truncated_column(5,53)[1]
(None, 5, 7, 7, [[(2, 1), (2, 1)]])
sage: find_brouwer_van_rees_with_one_truncated_column(6,96)[1]
(None, 6, 7, 13, [[(3, 1), (1, 1), (1, 1)]])
sage.combinat.designs.orthogonal_arrays_find_recursive.find_construction_3_3(k, n)

Find 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_find_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_find_recursive.find_construction_3_4(k, n)

Find 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_find_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_find_recursive.find_construction_3_5(k, n)

Find 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_find_recursive import find_construction_3_5
sage: find_construction_3_5(8,111)[1]
(8, 13, 6, 9, 11, 13)
sage: find_construction_3_5(9,24)
sage.combinat.designs.orthogonal_arrays_find_recursive.find_construction_3_6(k, n)

Find 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_find_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_find_recursive.find_product_decomposition(k, n)

Find n_1n_2=n to obtain an OA(k,n) by the product construction.

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_find_recursive import find_product_decomposition
sage: f,args = find_product_decomposition(6, 84)
sage: args
(None, 6, 7, 12, (), False)
sage: _ = f(*args)
sage.combinat.designs.orthogonal_arrays_find_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_find_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_find_recursive.find_recursive_construction(k, n)

Find a recursive construction of an OA(k,n) (calls all others find_* functions)

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_find_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_arrays.largest_available_k(n)
....:     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
56
sage.combinat.designs.orthogonal_arrays_find_recursive.find_three_factor_product(k, n)

Find n_1n_2n_3=n to obtain an OA(k,n) by the three-factor product from [DukesLing14]

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_find_recursive import find_three_factor_product
sage: find_three_factor_product(10,648)[1]
(9, 8, 9, 9)
sage: find_three_factor_product(10,50)
False
sage.combinat.designs.orthogonal_arrays_find_recursive.find_thwart_lemma_3_5(k, N)

Find the values on which Lemma 3.5 from [Thwarts] applies.

OUTPUT:

A pair (f,args) such that f(*args) returns an OA(k,n) or False if the construction is not available.

EXAMPLES:

sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import find_thwart_lemma_3_5
sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array

sage: f,args = find_thwart_lemma_3_5(7,66)
sage: args
(7, 9, 7, 1, 1, 1, 0, False)
sage: OA = f(*args)
sage: is_orthogonal_array(OA,7,66,2)
True

sage: f,args = find_thwart_lemma_3_5(6,100)
sage: args
(6, 8, 10, 8, 7, 5, 0, True)
sage: OA = f(*args)
sage: is_orthogonal_array(OA,6,100,2)
True

Some values from [Thwarts]:

sage: kn = ((10,1046), (10,1048), (10,1059), (11,1524),
....:       (11,2164), (12,3362), (12,3992),  (12,3994))
sage: for k,n in kn:
....:     print k,n,find_thwart_lemma_3_5(k,n)[1]
10 1046 (10, 13, 79, 9, 1, 0, 9, False)
10 1048 (10, 13, 79, 9, 1, 0, 11, False)
10 1059 (10, 13, 80, 9, 1, 0, 9, False)
11 1524 (11, 19, 78, 16, 13, 13, 0, True)
11 2164 (11, 27, 78, 23, 19, 16, 0, True)
12 3362 (12, 16, 207, 13, 13, 11, 13, True)
12 3992 (12, 19, 207, 16, 13, 11, 19, True)
12 3994 (12, 19, 207, 16, 13, 13, 19, True)

sage: for k,n in kn:                                                     # not tested -- too long
....:     assert designs.orthogonal_array(k,n,existence=True) is True    # not tested -- too long
sage.combinat.designs.orthogonal_arrays_find_recursive.find_thwart_lemma_4_1(k, n)

Find a decomposition for Lemma 4.1 from [Thwarts].

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_find_recursive import find_thwart_lemma_4_1
sage: find_thwart_lemma_4_1(10,408)[1]
(10, 13, 28)
sage: find_thwart_lemma_4_1(10,50)
False
sage.combinat.designs.orthogonal_arrays_find_recursive.find_wilson_decomposition_with_one_truncated_group(k, n)

Find rm+u=n to obtain an OA(k,n) by 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_find_recursive import find_wilson_decomposition_with_one_truncated_group
sage: f,args = find_wilson_decomposition_with_one_truncated_group(4,38)
sage: args
(None, 4, 5, 7, (3,), False)
sage: _ = f(*args)

sage: find_wilson_decomposition_with_one_truncated_group(4,20)
False
sage.combinat.designs.orthogonal_arrays_find_recursive.find_wilson_decomposition_with_two_truncated_groups(k, n)

Find rm+r_1+r_2=n to obtain an OA(k,n) by Wilson’s construction with two truncated 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_find_recursive import find_wilson_decomposition_with_two_truncated_groups
sage: f,args = find_wilson_decomposition_with_two_truncated_groups(5,58)
sage: args
(None, 5, 7, 7, (4, 5), False)
sage: _ = f(*args)
sage.combinat.designs.orthogonal_arrays_find_recursive.int_as_sum(value, S, k_max)

Return a tuple (s_1, s_2, \ldots, s_k) of less then k_max elements of S such that value = s_1 + s_2 + \ldots + s_k. If there is no such tuples then the function returns None.

INPUT:

  • value (integer)
  • S – a list of integers
  • k_max (integer)

EXAMPLE:

sage: from sage.combinat.designs.orthogonal_arrays_find_recursive import int_as_sum
sage: D = int_as_sum(21,[5,12],100)
sage: for k in range(20,40):
....:     print k, int_as_sum(k,[5,12],100)
20 (5, 5, 5, 5)
21 None
22 (12, 5, 5)
23 None
24 (12, 12)
25 (5, 5, 5, 5, 5)
26 None
27 (12, 5, 5, 5)
28 None
29 (12, 12, 5)
30 (5, 5, 5, 5, 5, 5)
31 None
32 (12, 5, 5, 5, 5)
33 None
34 (12, 12, 5, 5)
35 (5, 5, 5, 5, 5, 5, 5)
36 (12, 12, 12)
37 (12, 5, 5, 5, 5, 5)
38 None
39 (12, 12, 5, 5, 5)

Table Of Contents

Previous topic

Orthogonal arrays (build recursive constructions)

Next topic

Difference families

This Page