Added new constructions for BIBDs

[Ivo-Maffei]

Constructed the biplanes with parameters (79,13,2) and (56,11,2).
The constructions are added to the BIBD_constructions dictionary in sage.combinat.designs.database.

After #29959, they will be available via designs.balanced_incomplete_block_design.

Depends on #29959

CC: @dimpase

Component: combinatorial designs

Keywords: bibd combinatorial-designs

Author: Ivo Maffei

Branch/Commit: b99b1eb

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/30004

[Ivo-Maffei]

Author: Ivo Maffei

[dimpase]

comment:3

Why do you use biplane rather than BIBD in the new function names?
(docstrings certainly should mention it).

One can also create a function designs.biplane(k), with k being the biplane order,
which would return an example for each k a construction is known to exist.

As to references, look up how it is done elsewhere in this file. You'd add

    REFERENCES:

    .. [Aschbacher71] \M. Aschbacher,
      On collineation groups of symmetric block designs.
      J. Combinatorial Theory Ser. A 11 (1971), pp. 272–281.

    .. [Hall71] \M. Hall, Jr.,
      Combinatorial designs and groups.
      Actes du Congrès International des Mathématiciens (Nice, 1970),
      v.3, pp. 217–222. Gauthier-Villars, Paris, 1971.

This part must only appear once.
Also, add

# -*- coding: utf-8 -*-

as the 1st line of the file, as the 2nd reference uses utf-8.

Then you can use tags
[Aschbacher71]_ and [Hall71]_ to describe the history in the docstrings.
(that the latter in particular fixed a typo in the former, etc)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

690b757

added references and changed names to BIBD

[sagetrac-git]

Changed commit from 13486dd to 690b757

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f016797

fixed typo in docstring

[sagetrac-git]

Changed commit from 690b757 to f016797

[Ivo-Maffei]

comment:6

I like the idea of a biplane function, I need a new ticket though. For testing that function I'll need the changes of #29959.
Can I branch off that ticket or do I need to always branch from develop?

[dimpase]

comment:7

Replying to @Ivo-Maffei:

I like the idea of a biplane function, I need a new ticket though. For testing that function I'll need the changes of #29959.
Can I branch off that ticket or do I need to always branch from develop?

it's perfectly fine, and actually safer, as the right merge is already done this way, to branch off that ticket (in this case it should be mentioned in Dependencies: field in the ticket description)

[dimpase]

comment:8

The code implementing the nonabelian group from scratch looks too complicated. It seems it's much easier to deal with this group as a subgroup of upper-triangular 2x2 matrices mod 11.
Indeed, please check that the following matrices satisy the required relations

x=matrix(GF(11),[[1,1],[0,1]])
y=matrix(GF(11),[[5,0],[0,9]])
z=matrix(GF(11),[[-1,0],[0,1]])

[Ivo-Maffei]

comment:9

Those matrices generate a group isomorphic to the one given.
However, I'm still looking for some concrete representation of the P_i's that would take advantage of the new group.
I tried representing the P_i's as vectors, projective points and matrices but with little luck.
Now I'm looking at polynomials.

If I can't find anything, then to compute the action of a matrix on P_i I would need to decompose the matrix into x,y,z and end up doing most of the ugly operations I already do.

[dimpase]

comment:10

you can use subgroup cosets, just as in Aschbacher's paper.

[Ivo-Maffei]

comment:11

Thanks!

If I understand the paper correctly, the P_i's are left abstract and the orbit of P_i is G/H_i, yet P_i != I H_i as otherwise P_2 = P_3.
I was hoping for something more concrete, but I ended up reducing the action of M on P_i to basically be P_i N for a unique representative N of M H_i. Hence, I represent P_i M by the pair (i, M).

My current implementation is extremely slow and it seems that the quotient method of MatrixGroup yields a NotImplementedError.

I'm now moving everything to GAP. Soon I'll push the new method.

[dimpase]

comment:12

in GAP you need FactorCosetAction function, which can take any group G and its subgroup H of finite index, and construct the action on the cosets of H in G.

[dimpase]

comment:13

here is what you can do, with x,y,z as in comment:8:

sage: G=libgap(MatrixGroup([x,y,z]))
sage: H=G.Subgroup([libgap(z)])
sage: G.FactorCosetAction(H).Image()
<permutation group of size 110 with 3 generators>
sage: G.FactorCosetAction(H).Image().OrbitLength(1)
55

[Ivo-Maffei]

comment:14

I've done something a bit different by preserving the homomorphism given by FactorCosetAction since I'll need a different action for each P_i. I've not pushed the changes yet because the tests are still running.

[sagetrac-git]

Changed commit from f016797 to b6ac057

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b6ac057

changed function to use GAP

[dimpase]

comment:16

Can you use libgap.function_factory instead of libgap.eval, where appropriate?

also, libgap.set_global looks dodgy, do you really need it?

[dimpase]

comment:17

the way you describe intial blocks looks ugly, as they are unions of orbits of certain subgroups. There is no need to do explicit enumeration of elements of these subgroups.

[Ivo-Maffei]

comment:18

I changed the eval's. I don't know how to get rid of the set_global's as I need to give the actions a name to use inside the function_factory's.

As far as the blocks are concerned, I can change B1, B2, B3 to the below

B1 = list(libgap.Orbit(H4, p1, action)) + list(libgap.Orbit(G, p2, action))
B2 = list(libgap.Orbit(H4, p1, action)) + list(libgap.Orbit(G, p3, action))
B3 = list(libgap([p1, p2, p3])) + list(libgap.Orbit(libgap.Group(Y), action(p4, X), action)) + list(libgap.Orbit(libgap.Group(Y), action(p4, X**4), action))
B1 = libgap.Set(B1)
B2 = libgap.Set(B2)
B3 = libgap.Set(B3)

I don't know how to write B4 as unions of orbits.

[dimpase]

comment:19

B4 is invariant under an element of order 2 (well, it's not a big saving, of course)

[dimpase]

comment:20

Replying to @Ivo-Maffei:

I changed the eval's. I don't know how to get rid of the set_global's as I need to give the actions a name to use inside the function_factory's.

Update the branch please, then I can comment on your latest code.

[sagetrac-git]

Changed commit from b6ac057 to 6c60867

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9fd36fd	used function_factory; rewrote initial blocks; clear GAP global var
6c60867	removed floating g

[dimpase]

comment:22

here is a bit of refactoring and simplification, but I believe it's better to combine all the actions into just one permutation action, and get rid of the points as pairs.

diff --git a/src/sage/combinat/designs/database.py b/src/sage/combinat/designs/database.py
index 0fb34910a5..779e7873eb 100644
--- a/src/sage/combinat/designs/database.py
+++ b/src/sage/combinat/designs/database.py
@@ -4618,22 +4618,12 @@ def BIBD_79_13_2():
     libgap.set_global("p23Act", P23Action)
     libgap.set_global("p4Act", P4Action)
 
-    get_action = libgap.function_factory("""ChooseMyAction := function(i)
-        if i = 1 then
-            return p1Act;
-        elif i = 4 then
-            return p4Act;
-        else
-            return p23Act;
-        fi;
-    end;""")
-
     action = libgap.function_factory("""MyAction := function(pair, g)
-        local i, C, hom;
+        local i, C, homs;
+        homs := [p1Act, p23Act, p23Act, p4Act];
         i := pair[1];
         C := pair[2];
-        hom := ChooseMyAction(i);
-        return [i, C^(ImageElm(hom,g))];
+        return [i, C^(ImageElm(homs[i],g))];
     end;""")
 
     p1 = (1,1)
@@ -4652,7 +4642,7 @@ def BIBD_79_13_2():
           action(p4, X * Y**2), action(p4, X**-1 * Y**2), action(p4, X*Y), action(p4, X**-1 * Y),
           action(p4, X**5 * Y), action(p4, X**-5 * Y), action(p4, X**5 * Y**4), action(p4, X**-5 * Y**4)])
 
-    actionOnSet = libgap.function_factory("""MyActionOnSets := function(block, g)
+    actionOnSet = libgap.function_factory("""function(block, g)
         local set, p, q;
         set := Set([]);
         for p in block do
@@ -4670,9 +4660,7 @@ def BIBD_79_13_2():
     libgap.unset_global("p1Act")
     libgap.unset_global("p23Act")
     libgap.unset_global("p4Act")
-    libgap.unset_global("ChooseMyAction")
     libgap.unset_global("MyAction")
-    libgap.unset_global("MyActionOnSets")
     return blocks
 
 def BIBD_56_11_2():

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3b15980	pyflakes errors
a6059a3	changed to use only 1 permutation action

[sagetrac-git]

Changed commit from 6c60867 to a6059a3

[Ivo-Maffei]

comment:24

I combined the action into 1 permutation action. I hope that is what you meant.
I haven't run all tests on the above, but only checked that file. I'll do all the doctests when we reach a nice version of that function.

[dimpase]

comment:25

I think you better convert the block data into Sage's ZZ - at the moment they are still GAP integers (and also re-index from 0), as something goes wrong:

sage: designs.balanced_incomplete_block_design(79,13,2)
---------------------------------------------------------------------------
GAPError                                  Traceback (most recent call last)
...
AttributeError: 'sort' is not defined in GAP

[dimpase]

comment:26

this is a fix:

diff --git a/src/sage/combinat/designs/database.py b/src/sage/combinat/designs/database.py
index ecc17faa54..2437c0362e 100644
--- a/src/sage/combinat/designs/database.py
+++ b/src/sage/combinat/designs/database.py
@@ -4646,7 +4646,7 @@ def BIBD_79_13_2():
     libgap.unset_global("p1Act")
     libgap.unset_global("p23Act")
     libgap.unset_global("p4Act")
-    return blocks
+    return [[int(t)-1 for t in y] for y in blocks]
 
 def BIBD_56_11_2():
     r"""

[sagetrac-git]

Changed commit from a6059a3 to b99b1eb

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b99b1eb

change gap int to int

[dimpase]

comment:28

subject to tests passing, this looks good.
There is one more bug (or perhaps something not implemented at all), for a follow-up ticket:
removing a block from a symmetric BIBD(v,k,l) should give BIBD(v-k,k-l,l),
as by symmetry any 2 blocks intersect in l points,
but this does not work e.g. for BIBD_79_13_2, as

sage: designs.balanced_incomplete_block_design(66,11,2)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-23-f4a04be51fbf> in <module>()
----> 1 designs.balanced_incomplete_block_design(Integer(66),Integer(11),Integer(2))

/home/dimpase/sage/local/lib/python3.7/site-packages/sage/combinat/designs/bibd.py in balanced_incomplete_block_design(v, k, lambd, existence, use_LJCR)
    270         return Unknown
    271     else:
--> 272         raise NotImplementedError("I don't know how to build a ({},{},{})-BIBD!".format(v, k, lambd))
    273 
    274 def steiner_triple_system(n):

NotImplementedError: I don't know how to build a (66,11,2)-BIBD!

[dimpase]

Reviewer: Dima Pasechnik

[Ivo-Maffei]

comment:29

I'm now running all tests.
However, I'm a bit confused by your code examples, as on this branch the function balanced_incomplete_block_design only works for lambda = 1. Have you merged this with #29959 to run the tests? (that's actually a great idea, so I'll run the tests on this merged version)

Anyway, the balanced_incomplete_block_design code doesn't seem to include the recursive construction you mentioned.
I'll make a small ticket for it.

[dimpase]

Dependencies: #29959

[dimpase]

comment:30

Replying to @Ivo-Maffei:

I'm now running all tests.
However, I'm a bit confused by your code examples, as on this branch the function balanced_incomplete_block_design only works for lambda = 1. Have you merged this with #29959 to run the tests? (that's actually a great idea, so I'll run the tests on this merged version)

yes, sure. I've made #29959 a dependency of this ticket.

[Ivo-Maffei]

comment:31

So I finally finished testing this branch merged with #29959 and all tests pass.

[dimpase]

comment:32

OK, all clear.

[vbraun]

Changed branch from u/gh-Ivo-Maffei/biplanes to b99b1eb