Coverage for local/lib/python2.7/site-packages/sage/combinat/designs/block

EmptySetError: No projective plane of order 10 exists by C. Lam, L. Thiel and S. Swiercz "The nonexistence of finite projective planes of order 10" (1989), Canad. J. Math.

sage: designs.projective_plane(12)

Traceback (most recent call last):

...

NotImplementedError: If such a projective plane exists, we do not know how to build it.

sage: designs.projective_plane(14)

Traceback (most recent call last):

...

EmptySetError: By the Bruck-Ryser theorem, no projective plane of order 14 exists.

TESTS::

sage: designs.projective_plane(2197, existence=True)

True

sage: designs.projective_plane(6, existence=True)

False

sage: designs.projective_plane(10, existence=True)

False

sage: designs.projective_plane(12, existence=True)

Unknown

"""

from sage.rings.sum_of_squares import is_sum_of_two_squares_pyx

if n <= 1:

if existence:

return False

raise EmptySetError("There is no projective plane of order <= 1")

if n == 10:

if existence:

return False

ref = ("C. Lam, L. Thiel and S. Swiercz \"The nonexistence of finite "

"projective planes of order 10\" (1989), Canad. J. Math.")

raise EmptySetError("No projective plane of order 10 exists by %s"%ref)

if (n%4) in [1,2] and not is_sum_of_two_squares_pyx(n):

if existence:

return False

raise EmptySetError("By the Bruck-Ryser theorem, no projective"

" plane of order {} exists.".format(n))

if not is_prime_power(n):

if existence:

return Unknown

raise NotImplementedError("If such a projective plane exists, we do "

"not know how to build it.")

if existence:

return True

else:

return DesarguesianProjectivePlaneDesign(n, point_coordinates=False, check=check)

def AffineGeometryDesign(n, d, F, point_coordinates=True, check=True):

r"""

Return an affine geometry design.

The affine geometry design `AG_d(n,q)` is the 2-design whose blocks are the

`d`-vector subspaces in `\GF{q}^n`. It has parameters

.. MATH::

v = q^n,\ k = q^d,\ \lambda = \binom{n-1}{d-1}_q

where the `q`-binomial coefficient `\binom{m}{r}_q` is defined by

.. MATH::

\binom{m}{r}_q = \frac{(q^m - 1)(q^{m-1} - 1) \cdots (q^{m-r+1}-1)}

{(q^r-1)(q^{r-1}-1)\cdots (q-1)}

.. SEEALSO::

:func:`ProjectiveGeometryDesign`

INPUT:

- ``n`` (integer) -- the Euclidean dimension. The number of points of the

design is `v=|\GF{q}^n|`.

- ``d`` (integer) -- the dimension of the (affine) subspaces of `\GF{q}^n`

which make up the blocks.

- ``F`` -- a finite field or a prime power.

- ``point_coordinates`` -- (optional, default ``True``) whether we use

coordinates in `\GF{q}^n` or plain integers for the points of the design.

- ``check`` -- (optional, default ``True``) whether to check the output.

EXAMPLES::

sage: BD = designs.AffineGeometryDesign(3, 1, GF(2))

sage: BD.is_t_design(return_parameters=True)

(True, (2, 8, 2, 1))

sage: BD = designs.AffineGeometryDesign(3, 2, GF(4))

sage: BD.is_t_design(return_parameters=True)

(True, (2, 64, 16, 5))

sage: BD = designs.AffineGeometryDesign(4, 2, GF(3))

sage: BD.is_t_design(return_parameters=True)

(True, (2, 81, 9, 13))

With ``F`` an integer instead of a finite field::

sage: BD = designs.AffineGeometryDesign(3, 2, 4)

sage: BD.is_t_design(return_parameters=True)

(True, (2, 64, 16, 5))

Testing the option ``point_coordinates``::

sage: designs.AffineGeometryDesign(3, 1, GF(2), point_coordinates=True).blocks()[0]

[(0, 0, 0), (0, 0, 1)]

sage: designs.AffineGeometryDesign(3, 1, GF(2), point_coordinates=False).blocks()[0]

[0, 1]

"""

try:

q = int(F)

except TypeError:

q = F.cardinality()

else:

from sage.rings.finite_rings.finite_field_constructor import GF

F = GF(q)

n = int(n)

d = int(d)

from itertools import islice

from sage.combinat.q_analogues import q_binomial

from sage.matrix.echelon_matrix import reduced_echelon_matrix_iterator

points = {p:i for i,p in enumerate(reduced_echelon_matrix_iterator(F,1,n+1,copy=True,set_immutable=True)) if p[0,0]}

blocks = []

l1 = int(q_binomial(n+1, d+1, q) - q_binomial(n, d+1, q))

l2 = q**d

for m1 in islice(reduced_echelon_matrix_iterator(F,d+1,n+1,copy=False), l1):

b = []

for m2 in islice(reduced_echelon_matrix_iterator(F,1,d+1,copy=False), l2):

m = m2*m1

m.echelonize()

m.set_immutable()

b.append(points[m])

blocks.append(b)

B = BlockDesign(len(points), blocks, name="AffineGeometryDesign", check=check)

if point_coordinates:

rd = {i:p[0][1:] for p,i in six.iteritems(points)}

for v in rd.values(): v.set_immutable()

B.relabel(rd)

if check:

if not B.is_t_design(t=2, v=q**n, k=q**d, l=q_binomial(n-1, d-1, q)):

raise RuntimeError("error in AffineGeometryDesign "

"construction. Please e-mail sage-devel@googlegroups.com")

return B

def CremonaRichmondConfiguration():

r"""

Return the Cremona-Richmond configuration

The Cremona-Richmond configuration is a set system whose incidence graph

is equal to the

:meth:`~sage.graphs.graph_generators.GraphGenerators.TutteCoxeterGraph`. It

is a generalized quadrangle of parameters `(2,2)`.

For more information, see the

:wikipedia:`Cremona-Richmond_configuration`.

EXAMPLES::

sage: H = designs.CremonaRichmondConfiguration(); H

Incidence structure with 15 points and 15 blocks

sage: g = graphs.TutteCoxeterGraph()

sage: H.incidence_graph().is_isomorphic(g)

True

"""

from sage.graphs.generators.smallgraphs import TutteCoxeterGraph

from sage.combinat.designs.incidence_structures import IncidenceStructure

g = TutteCoxeterGraph()

H = IncidenceStructure([g.neighbors(v)

for v in g.bipartite_sets()[0]])

H.relabel()

return H

def WittDesign(n):

"""

INPUT:

- ``n`` is in `9,10,11,12,21,22,23,24`.

Wraps GAP Design's WittDesign. If ``n=24`` then this function returns the

large Witt design `W_{24}`, the unique (up to isomorphism) `5-(24,8,1)`

design. If ``n=12`` then this function returns the small Witt design

`W_{12}`, the unique (up to isomorphism) `5-(12,6,1)` design. The other

values of `n` return a block design derived from these.

.. NOTE::

Requires GAP's Design package (included in the gap_packages Sage spkg).

EXAMPLES::

sage: BD = designs.WittDesign(9) # optional - gap_packages (design package)

sage: BD.is_t_design(return_parameters=True) # optional - gap_packages (design package)

(True, (2, 9, 3, 1))

sage: BD # optional - gap_packages (design package)

Incidence structure with 9 points and 12 blocks

sage: print(BD) # optional - gap_packages (design package)

Incidence structure with 9 points and 12 blocks

"""

from sage.interfaces.gap import gap

gap.load_package("design")

gap.eval("B:=WittDesign(%s)"%n)

v = eval(gap.eval("B.v"))

gblcks = eval(gap.eval("B.blocks"))

gB = []

for b in gblcks:

gB.append([x-1 for x in b])

return BlockDesign(v, gB, name="WittDesign", check=True)

def HadamardDesign(n):

"""

As described in Section 1, p. 10, in [CvL]. The input n must have the

property that there is a Hadamard matrix of order `n+1` (and that a

construction of that Hadamard matrix has been implemented...).

EXAMPLES::

sage: designs.HadamardDesign(7)

Incidence structure with 7 points and 7 blocks

sage: print(designs.HadamardDesign(7))

Incidence structure with 7 points and 7 blocks

For example, the Hadamard 2-design with `n = 11` is a design whose parameters are 2-(11, 5, 2).

We verify that `NJ = 5J` for this design. ::

sage: D = designs.HadamardDesign(11); N = D.incidence_matrix()

sage: J = matrix(ZZ, 11, 11, [1]*11*11); N*J

[5 5 5 5 5 5 5 5 5 5 5]

REFERENCES:

- [CvL] P. Cameron, J. H. van Lint, Designs, graphs, codes and

their links, London Math. Soc., 1991.

"""

from sage.combinat.matrices.hadamard_matrix import hadamard_matrix

from sage.matrix.constructor import matrix

H = hadamard_matrix(n+1) #assumed to be normalised.

H1 = H.matrix_from_columns(range(1,n+1))

H2 = H1.matrix_from_rows(range(1,n+1))

J = matrix(ZZ,n,n,[1]*n*n)

MS = J.parent()

A = MS((H2+J)/2) # convert -1's to 0's; coerce entries to ZZ

# A is the incidence matrix of the block design

return IncidenceStructure(incidence_matrix=A,name="HadamardDesign")

def Hadamard3Design(n):

"""

Return the Hadamard 3-design with parameters `3-(n, \\frac n 2, \\frac n 4 - 1)`.

This is the unique extension of the Hadamard `2`-design (see

:meth:`HadamardDesign`). We implement the description from pp. 12 in

[CvL]_.

INPUT:

- ``n`` (integer) -- a multiple of 4 such that `n>4`.

EXAMPLES::

sage: designs.Hadamard3Design(12)

Incidence structure with 12 points and 22 blocks

We verify that any two blocks of the Hadamard `3`-design `3-(8, 4, 1)`

design meet in `0` or `2` points. More generally, it is true that any two

blocks of a Hadamard `3`-design meet in `0` or `\\frac{n}{4}` points (for `n

> 4`).

sage: D = designs.Hadamard3Design(8)

sage: N = D.incidence_matrix()

sage: N.transpose()*N

[4 2 2 2 2 2 2 2 2 2 2 2 2 0]

[2 4 2 2 2 2 2 2 2 2 2 2 0 2]

[2 2 4 2 2 2 2 2 2 2 2 0 2 2]

[2 2 2 4 2 2 2 2 2 2 0 2 2 2]

[2 2 2 2 4 2 2 2 2 0 2 2 2 2]

[2 2 2 2 2 4 2 2 0 2 2 2 2 2]

[2 2 2 2 2 2 4 0 2 2 2 2 2 2]

[2 2 2 2 2 2 0 4 2 2 2 2 2 2]

[2 2 2 2 2 0 2 2 4 2 2 2 2 2]

[2 2 2 2 0 2 2 2 2 4 2 2 2 2]

[2 2 2 0 2 2 2 2 2 2 4 2 2 2]

[2 2 0 2 2 2 2 2 2 2 2 4 2 2]

[2 0 2 2 2 2 2 2 2 2 2 2 4 2]

[0 2 2 2 2 2 2 2 2 2 2 2 2 4]

REFERENCES:

.. [CvL] \P. Cameron, J. H. van Lint, Designs, graphs, codes and

their links, London Math. Soc., 1991.

"""

if n == 1 or n == 4:

raise ValueError("The Hadamard design with n = %s does not extend to a three design." % n)

from sage.combinat.matrices.hadamard_matrix import hadamard_matrix

from sage.matrix.constructor import matrix, block_matrix

H = hadamard_matrix(n) #assumed to be normalised.

H1 = H.matrix_from_columns(range(1, n))

J = matrix(ZZ, n, n-1, [1]*(n-1)*n)

A1 = (H1+J)/2

A2 = (J-H1)/2

A = block_matrix(1, 2, [A1, A2]) #the incidence matrix of the design.

return IncidenceStructure(incidence_matrix=A, name="HadamardThreeDesign")

Coverage for local/lib/python2.7/site-packages/sage/combinat/designs/block_design.py : 80%

274 statements 218 run 56 missing 0 excluded