Cython functions for combinatorial designs#

This module implements the design methods that need to be somewhat efficient.

Functions#

sage.combinat.designs.designs_pyx.is_difference_matrix(M, G, k, lmbda=1, verbose=False)#

Test if \(M\) is a \((G,k,\lambda)\)-difference matrix.

A matrix \(M\) is a \((G,k,\lambda)\)-difference matrix if its entries are element of \(G\), and if for any two rows \(R,R'\) of \(M\) and \(x\in G\) there are exactly \(\lambda\) values \(i\) such that \(R_i-R'_i=x\).

INPUT:

  • M – a matrix with entries from G

  • G – a group

  • k – integer

  • lmbda (integer) – set to \(1\) by default.

  • verbose (boolean) – whether to print some information when the answer is False.

EXAMPLES:

sage: from sage.combinat.designs.designs_pyx import is_difference_matrix
sage: q = 3**3
sage: F = GF(q,'x')                                                             # needs sage.rings.finite_rings
sage: M = [[x*y for y in F] for x in F]                                         # needs sage.rings.finite_rings
sage: is_difference_matrix(M,F,q,verbose=1)                                     # needs sage.rings.finite_rings
True

sage: B = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
....:      [0, 1, 2, 3, 4, 2, 3, 4, 0, 1],
....:      [0, 2, 4, 1, 3, 3, 0, 2, 4, 1]]
sage: G = GF(5)
sage: B = [[G(b) for b in R] for R in B]
sage: is_difference_matrix(list(zip(*B)),G,3,2)
True

Bad input:

sage: # needs sage.rings.finite_rings
sage: for R in M: R.append(None)
sage: is_difference_matrix(M,F,q,verbose=1)
The matrix has 28 columns but k=27
False
sage: for R in M: _=R.pop(-1)
sage: M.append([None]*3**3)
sage: is_difference_matrix(M,F,q,verbose=1)
The matrix has 28 rows instead of lambda(|G|-1+2u)+mu=1(27-1+2.0)+1=27
False
sage: _= M.pop(-1)
sage: for R in M: R[-1] = 0
sage: is_difference_matrix(M,F,q,verbose=1)
Columns 0 and 26 generate 0 exactly 27 times instead of the expected mu(=1)
False
sage: for R in M: R[-1] = 1
sage: M[-1][-1] = 0
sage: is_difference_matrix(M,F,q,verbose=1)
Columns 0 and 26 do not generate all elements of G exactly lambda(=1) times.
The element x appeared 0 times as a difference.
False
sage.combinat.designs.designs_pyx.is_group_divisible_design(groups, blocks, v, G=None, K=None, lambd=1, verbose=False)#

Checks that input is a Group Divisible Design on \(\{0,...,v-1\}\)

For more information on Group Divisible Designs, see GroupDivisibleDesign.

INPUT:

  • groups – a partition of \(X\). If set to None the groups are guessed automatically, and the function returns (True, guessed_groups) instead of True

  • blocks – collection of blocks

  • v (integers) – size of the ground set assumed to be \(X=\{0,...,v-1\}\).

  • G – list of integers of which the sizes of the groups must be elements. Set to None (automatic guess) by default.

  • K – list of integers of which the sizes of the blocks must be elements. Set to None (automatic guess) by default.

  • lambd – value of \(\lambda\). Set to \(1\) by default.

  • verbose (boolean) – whether to display some information when the design is not a GDD.

EXAMPLES:

sage: from sage.combinat.designs.designs_pyx import is_group_divisible_design
sage: TD = designs.transversal_design(4,10)                                     # needs sage.modules
sage: groups = [list(range(i*10,(i+1)*10)) for i in range(4)]
sage: is_group_divisible_design(groups,TD,40,lambd=1)                           # needs sage.modules
True
sage.combinat.designs.designs_pyx.is_orthogonal_array(OA, k, n, t=2, verbose=False, terminology='OA')#

Check that the integer matrix \(OA\) is an \(OA(k,n,t)\).

See orthogonal_array() for a definition.

INPUT:

  • OA – the Orthogonal Array to be tested

  • k,n,t (integers) – only implemented for \(t=2\).

  • verbose (boolean) – whether to display some information when OA is not an orthogonal array \(OA(k,n)\).

  • terminology (string) – how to phrase the information when verbose = True. Possible values are \("OA"\), \("MOLS"\).

EXAMPLES:

sage: # needs sage.schemes
sage: from sage.combinat.designs.designs_pyx import is_orthogonal_array
sage: OA = designs.orthogonal_arrays.build(8,9)
sage: is_orthogonal_array(OA,8,9)
True
sage: is_orthogonal_array(OA,8,10)
False
sage: OA[4][3] = 1
sage: is_orthogonal_array(OA,8,9)
False
sage: is_orthogonal_array(OA,8,9,verbose=True)
Columns 0 and 3 are not orthogonal
False
sage: is_orthogonal_array(OA,8,9, verbose=True, terminology="MOLS")
Squares 0 and 3 are not orthogonal
False
sage.combinat.designs.designs_pyx.is_pairwise_balanced_design(blocks, v, K=None, lambd=1, verbose=False)#

Checks that input is a Pairwise Balanced Design (PBD) on \(\{0,...,v-1\}\)

For more information on Pairwise Balanced Designs (PBD), see PairwiseBalancedDesign.

INPUT:

  • blocks – collection of blocks

  • v (integers) – size of the ground set assumed to be \(X=\{0,...,v-1\}\).

  • K – list of integers of which the sizes of the blocks must be elements. Set to None (automatic guess) by default.

  • lambd – value of \(\lambda\). Set to \(1\) by default.

  • verbose (boolean) – whether to display some information when the design is not a PBD.

EXAMPLES:

sage: from sage.combinat.designs.designs_pyx import is_pairwise_balanced_design
sage: sts = designs.steiner_triple_system(9)
sage: is_pairwise_balanced_design(sts,9,[3],1)
True
sage: TD = designs.transversal_design(4,10).blocks()                            # needs sage.modules
sage: groups = [list(range(i*10,(i+1)*10)) for i in range(4)]
sage: is_pairwise_balanced_design(TD + groups, 40, [4,10], 1, verbose=True)     # needs sage.modules
True
sage.combinat.designs.designs_pyx.is_projective_plane(blocks, verbose=False)#

Test whether the blocks form a projective plane on \(\{0,...,v-1\}\)

A projective plane is an incidence structure that has the following properties:

  1. Given any two distinct points, there is exactly one line incident with both of them.

  2. Given any two distinct lines, there is exactly one point incident with both of them.

  3. There are four points such that no line is incident with more than two of them.

For more informations, see Wikipedia article Projective_plane.

is_t_design() can also check if an incidence structure is a projective plane with the parameters \(v=k^2+k+1\), \(t=2\) and \(l=1\).

INPUT:

  • blocks – collection of blocks

  • verbose – whether to print additional information

EXAMPLES:

sage: from sage.combinat.designs.designs_pyx import is_projective_plane
sage: p = designs.projective_plane(4)                                           # needs sage.schemes
sage: b = p.blocks()                                                            # needs sage.schemes
sage: is_projective_plane(b, verbose=True)                                      # needs sage.schemes
True

sage: # needs sage.schemes
sage: p = designs.projective_plane(2)
sage: b = p.blocks()
sage: is_projective_plane(b)
True
sage: b[0][2] = 5
sage: is_projective_plane(b, verbose=True)
the pair (0,5) has been seen 2 times but lambda=1
False

sage: is_projective_plane([[0,1,2],[1,2,4]], verbose=True)
the pair (0,3) has been seen 0 times but lambda=1
False

sage: is_projective_plane([[1]], verbose=True)
First block has less than 3 points.
False

sage: # needs sage.schemes
sage: p = designs.projective_plane(2)
sage: b = p.blocks()
sage: b[2].append(4)
sage: is_projective_plane(b, verbose=True)
a block has size 4 while K=[3]
False
sage.combinat.designs.designs_pyx.is_quasi_difference_matrix(M, G, k, lmbda, mu, u, verbose=False)#

Test if the matrix is a \((G,k;\lambda,\mu;u)\)-quasi-difference matrix

Let \(G\) be an abelian group of order \(n\). A \((n,k;\lambda,\mu;u)\)-quasi-difference matrix (QDM) is a matrix \(Q_{ij}\) with \(\lambda(n-1+2u)+\mu\) rows and \(k\) columns, with each entry either equal to None (i.e. the ‘missing entries’) or to an element of \(G\). Each column contains exactly \(\lambda u\) empty entries, and each row contains at most one None. Furthermore, for each \(1\leq i<j\leq k\), the multiset

\[\{q_{li}-q_{lj}:1\leq l\leq \lambda (n-1+2u)+\mu, \text{ with } q_{li}\text{ and }q_{lj}\text{ not empty}\}\]

contains \(\lambda\) times every nonzero element of \(G\) and contains \(\mu\) times \(0\).

INPUT:

  • M – a matrix with entries from G (or equal to None for missing entries)

  • G – a group

  • k,lmbda,mu,u – integers

  • verbose (boolean) – whether to print some information when the answer is False.

EXAMPLES:

Differences matrices:

sage: from sage.combinat.designs.designs_pyx import is_quasi_difference_matrix
sage: q = 3**3
sage: F = GF(q,'x')                                                             # needs sage.rings.finite_rings
sage: M = [[x*y for y in F] for x in F]                                         # needs sage.rings.finite_rings
sage: is_quasi_difference_matrix(M,F,q,1,1,0,verbose=1)                         # needs sage.rings.finite_rings
True

sage: B = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
....:      [0, 1, 2, 3, 4, 2, 3, 4, 0, 1],
....:      [0, 2, 4, 1, 3, 3, 0, 2, 4, 1]]
sage: G = GF(5)
sage: B = [[G(b) for b in R] for R in B]
sage: is_quasi_difference_matrix(list(zip(*B)),G,3,2,2,0)
True

A quasi-difference matrix from the database:

sage: from sage.combinat.designs.database import QDM
sage: G,M = QDM[38,1][37,1,1,1][1]()
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=1,u=1)
True

Bad input:

sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=1,u=3,verbose=1)
The matrix has 39 rows instead of lambda(|G|-1+2u)+mu=1(37-1+2.3)+1=43
False
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=2,u=1,verbose=1)
The matrix has 39 rows instead of lambda(|G|-1+2u)+mu=1(37-1+2.1)+2=40
False
sage: M[3][1] = None
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=1,u=1,verbose=1)
Row 3 contains more than one empty entry
False
sage: M[3][1] = 1
sage: M[6][1] = None
sage: is_quasi_difference_matrix(M,G,k=6,lmbda=1,mu=1,u=1,verbose=1)
Column 1 contains 2 empty entries instead of the expected lambda.u=1.1=1
False