Construction of BIBD with k=5

[nathanncohen]

Heeeeeere it is ! At long last. We can build all BIBD with k=5 thanks to this construction :
http://www.argilo.net/files/bibd.pdf

As usual no design is returned without being checked first, so the code is extremely safe.

Nathann

Depends on #16279

CC: @videlec @KPanComputes @dimpase @brettpim

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 8eac6d0

Reviewer: Vincent Delecroix

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

[nathanncohen]

Last 10 new commits:

5074eee	trac #16272: finer doctest to test the output of transversal_design
d81f265	trac #16272: ultimate doctest
47798d2	trac #16272: simplifying the structure of orthogonal_array
d34b012	trac #16272: Merged with updated #16227
569c485	trac #16279: BIBD from Transversal Designs
60e8d35	trac #16279: Merged with updated #16272
927d325	trac #16279: Merged with 6.2
e1b29bf	trac #16279: Fixing the doc
e941a54	trac #16279: Merged with updated #16091
2ac6aef	trac #16323: Construction of BIBD with k=5

[nathanncohen]

Commit: 2ac6aef

[nathanncohen]

Branch: u/ncohen/16323

[sagetrac-git]

Changed commit from 2ac6aef to 8529434

[sagetrac-git]

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

c127a6d	trac #16272: Merged with updated #16231
e2749b3	trac #16272: Merged with 6.3.beta0
4115b72	trac #16279: Merged with updated #16272
8529434	trac #16323: Merged with #16279

[nathanncohen]

comment:3

If anybody wants to really test it :

for i in range(2,2000):
    if designs.BalancedIncompleteBlockDesign(i,5,existence=True):
        print i
        _ = designs.BalancedIncompleteBlockDesign(i,5)

Nathann

[nathanncohen]

Dependencies: #16279

[sagetrac-git]

Changed commit from 8529434 to 07a3130

[sagetrac-git]

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

07a3130

trac #16323: Merged with 6.3.beta1

[videlec]

comment:8

Hi Nathann,

Perhaps not everything for that ticket but I would like to discuss several points.

1. BalancedIncompleteBlockDesign is upper case whereas we start to agree on lower case would be for "build me one if you know how to" and CamelCase would be for "build me this precise design". Should I open a ticket for that ?

2. BIBD errors are not smart (compared to TD/OA/MOLS)

sage: designs.BalancedIncompleteBlockDesign(5,6)
...
ValueError: No such design exists !
sage: designs.BalancedIncompleteBlockDesign(1,6)
...
RuntimeError: maximum recursion depth exceeded while calling a Python object
sage: D=designs.BalancedIncompleteBlockDesign(1,5)
...
EmptySetError: No Transversal Design exists when k>=n+2 if n>=2

3. It would be nice to have BIBD_from_difference_family as a public function as it
   may serve other purposes. Moreover, the G(x if some_reason else [x]) is
   ugly. I know it is because of AdditiveAbelianGroup but it is ugly. There are
   ways to avoid that (e.g. use Zmod for cyclic groups instead of
   AdditiveAbelianGroup). For that particular point, I do have implementation that smooth everything in u/vdelecroix/16323.

4. More generally, there are recursive strategies to build difference family and
   difference matrices... it would be nice to have functions

def difference_family(G, k, l=1, existence=False):
    r"""
    Return a (G,k,l)-difference family if we know how to...
    """

def difference_matrix(G, k, l=1, existence=False):
    r"""
    Return a (G,k,l)-difference matrix if we know how to... 
    """"

And moreover, such function might be used to simplify the database.

5. (not very helpful comment) For v=81, one can write in shorter form

sage: G = AdditiveAbelianGroup([3]*4)
sage: a,b,c,d = G.gens()
sage: D = [[d,    -a+d,  -c+d,    a-b-d,   b+c+d],
....:      [c,    -b+c,   a+b-d,  a-b+d,   a+b+c],
....:      [a+b,  -a+c-d, b-c+d,  a-b-c-d, -a-b+c+d],
....:      [-b-d,  a+b+d, a-b+c, -b+c+d,    a-b+c-d]]

Moreover, writing that way it avoids the conversion from tuple to elements of
the group G.

Vincent

[nathanncohen]

comment:9

Yooooooooo !!

Perhaps not everything for that ticket but I would like to discuss several points.

Thanks for reading it, though !

1. BalancedIncompleteBlockDesign is upper case whereas we start to agree on lower case would be for "build me one if you know how to" and CamelCase would be for "build me this precise design". Should I open a ticket for that ?

Ahahahah... Yes, probably... :-)

2. BIBD errors are not smart (compared to TD/OA/MOLS)

sage: designs.BalancedIncompleteBlockDesign(5,6)
...
ValueError: No such design exists !
sage: designs.BalancedIncompleteBlockDesign(1,6)
...
RuntimeError: maximum recursion depth exceeded while calling a Python object
sage: D=designs.BalancedIncompleteBlockDesign(1,5)
...
EmptySetError: No Transversal Design exists when k>=n+2 if n>=2

Well, the first one is correct, I am pretty sure I fixed the second somewhere but let's fix it again here, and the third one is really a mistake. I will write a ticket for the last two bugs in a second

3. It would be nice to have BIBD_from_difference_family as a public function as it
   may serve other purposes. Moreover, the G(x if some_reason else [x]) is
   ugly. I know it is because of AdditiveAbelianGroup but it is ugly.

Yes. But you know, it REALLY is because of AdditiveAbelianGroup ! Anyway now we have real cartesian products, I will use that.

There are
ways to avoid that (e.g. use Zmod for cyclic groups instead of
AdditiveAbelianGroup). For that particular point, I do have implementation that smooth everything in u/vdelecroix/16323.

Oh... But Zmod is ugly too, because you have to change the way you think of the code.. We can use cartesian products now that we have them !

4. More generally, there are recursive strategies to build difference family and
   difference matrices... it would be nice to have functions

def difference_family(G, k, l=1, existence=False):
    r"""
    Return a (G,k,l)-difference family if we know how to...
    """

def difference_matrix(G, k, l=1, existence=False):
    r"""
    Return a (G,k,l)-difference matrix if we know how to... 
    """"

And moreover, such function might be used to simplify the database.

I know nothing about ways to build difference families and differences matrices.

Nathann

[nathanncohen]

comment:10

Okay, I just loaded your branch and saw what you did. If you want to expose such a function you must really document it, a bit like the documentation of OA_from_quasi_difference_matrix and OA_from_Vmt. Definine difference matrices, and how the BIBD is produced.

I don't know how to do that. That's why I left it as an inlined function.

BTW, I think that the name should end with "difference_family", not DF.

I will create the bugix ticket in a second.

Nathann

[nathanncohen]

comment:11

Okay, actually it seems that the infinite recursion cannot happen when we avoid the stupid cases v=1 and k=1. SOoooooooooooo instead of creating a ticket we can fix it here !

As I don't know what we will do with your branch and mine I don't write the commit but the fix is easy :

     """
-    if ((binomial(v,2)%binomial(k,2) != 0) or
+    if (v<k or
+        k<2 or
+        (binomial(v,2)%binomial(k,2) != 0) or
         (v-1)%(k-1) != 0):
         if existence:

Nathann

[videlec]

comment:12

Hi Nathann,

I did the modif in my branch. I also put the case v == k before since [[1]] is a valid BIBD(1,1), isn't it? I also changed some of the ValueError to EmptySetError or NotImplementedError. Now we have

sage: designs.BalancedIncompleteBlockDesign(5,6)
...
EmptySetError: No such design exists !
sage: designs.BalancedIncompleteBlockDesign(1,6)
...
EmptySetError: No such design exists !
sage: designs.BalancedIncompleteBlockDesign(1,5)
...
EmptySetError: No such design exists !

For the BIBD_from_difference_family there is now a proper documentation. I also learn that there are some constructions of Wilson, Baratti and Abel-Baratti to build difference families.

I still have the Zmod in my branch and I do not know if you want to get rid of them.

Vincent

[videlec]

comment:13

Actually, I did a mistake: BIBD(1,k) always exists, just consider an empty set of blocks !!

[nathanncohen]

comment:14

Hello !

Did you push the changes ? The branch u/vdelecroix/16323 I just pulled contains the old version of your changes only : the function is still named BIBD_from_DF and contains almost no documentation.

Nathann

[videlec]

comment:15

Hi Nathann,

My mistake, I did not commit the changes. Now everything is on trac.

Vincent

[nathanncohen]

comment:16

Ahahahah very cool ! I did not even know how a difference family was defined. Quite straightforward :-)

Okay, I agree with your commits except for three things :

• The new function needs an INPUT section

• we have several "Design1_from_design2" functions already, so could it be BIBD_from_difference_family like before ?

• Those two tests are equivalent. Is that on purpose ?

+    assert ((v-1)%4 == 0 and (v*(v-1))%20 == 0)
+    assert (v%20 == 5 or v%20 == 1)

Nathann

[videlec]

comment:17

Hi Nathann,

I did the correction. Furthermore, there was a typo in the main BIBD (a n was used instead of a v).

Now that I read more carefully the code:

• why the construction using PBD can not be used from the main BIBD function? In particular, considering organization, I would like to see the functions BIBD_from_PBD, _check_PBD, _relabel_BIBD, PBD_4_5_8_9_12, _PBD_4_5_8_9_12_closure, PBD_from_TD much higher in the file, i.e. neither in the part "(v,4,1)-BIBD" nor in the part "(v,5,1)-BIBD".

• More generally, the functions steiner_triple_system, v_4_1_BIBD and v_5_1_BIBD currently follow various proofs. But we only care about constructing the BIBD and not checking the proofs, doesn't we? We certainly "check" the proof in the doctests but wouldn't it be possible to write in the main BIBD:

  if database.BIBD[v,k]:
      ...
  elif construction1(v,k,existence=True):
      ...
  elif construction2(v,k,existence=True):
      ...
  

  and getting rid of steiner_triple_system, v_4_1_BIBD and v_5_1_BIBD? I understand that it would be a dramatical change, so do not answer considering it as a task for that ticket.

Vincent

[nathanncohen]

Changed branch from u/ncohen/16323 to u/vdelecroix/16323

[nathanncohen]

comment:18

Hello !

Now that I read more carefully the code:

• why the construction using PBD can not be used from the main BIBD function?

You mean that if we had a constructor for PBD we could call it from the BIBD constructor using BIBD_from_PBD ? It is true, but we have no PBD constructor at the moment. Besides the two PBD constructors we already have we could add a PBD_from_TD, stuff like that, indeed.

In particular, considering organization, I would like to see the functions BIBD_from_PBD, _check_PBD, _relabel_BIBD, PBD_4_5_8_9_12, _PBD_4_5_8_9_12_closure, PBD_from_TD much higher in the file, i.e. neither in the part "(v,4,1)-BIBD" nor in the part "(v,5,1)-BIBD".

Move stuff around if you want. As far as I am concerned, it is totally pointless. This being said, some of those functions are together in the code because I implemented the, following the same reference, so if you move them apart please leave them linked together somehow.

• More generally, the functions steiner_triple_system, v_4_1_BIBD and v_5_1_BIBD currently follow various proofs. But we only care about constructing the BIBD and not checking the proofs, doesn't we? We certainly "check" the proof in the doctests but wouldn't it be possible to write in the main BIBD:

  if database.BIBD[v,k]:
      ...
  elif construction1(v,k,existence=True):
      ...
  elif construction2(v,k,existence=True):
      ...
  

Hmmmmm... You are right that it would be equivalent, you are right that we have no automatic way to chec that the proof is right, but as it is implemented you can deduce, from looking at the code, that this is the intent and so that it is what the function does. Also, these functions have a documentation and comments which are related to the papers I followed to implement them, and this would be much harder to see if you poured them all in the main constructors.

Another thing : sometimes the v_5_1_BIBD construction (for instance) needs a smaller BIBD to produce a larger one, but it does not call the main BIBD constructor because we know from the proof that this smaller bibd can be obtained by some specific construction. So well, it it implemented directly.

So well.... I rather like to have these functions which somehow claim that "these cases are all dealt with", which would not be straightforward to see if all constructors were included in the main function. And if something which those constructions require is of more general use we can of course expose it inside of the main constructor.

The original code for BIBD with k=5 was actually much larger... #16279 is one of these parts.

Nathann

---

New commits:

0610c7d	trac #16323: external BIBD_from_DF and use Zmod
daae63e	trac #16323: DF -> difference_family, change errors and more doc
8eac6d0	trac #16323: several fix + doc

[nathanncohen]

Changed commit from 07a3130 to 8eac6d0

[videlec]

comment:19

Hello,

Replying to @nathanncohen:

Hello !

Now that I read more carefully the code:

• why the construction using PBD can not be used from the main BIBD function?

You mean that if we had a constructor for PBD we could call it from the BIBD constructor using BIBD_from_PBD ? It is true, but we have no PBD constructor at the moment. Besides the two PBD constructors we already have we could add a PBD_from_TD, stuff like that, indeed.

I bet that there are some PBD constructions in the Handbook... We should keep in mind to reuse this code at some point.

In particular, considering organization, I would like to see the functions BIBD_from_PBD, _check_PBD, _relabel_BIBD, PBD_4_5_8_9_12, _PBD_4_5_8_9_12_closure, PBD_from_TD much higher in the file, i.e. neither in the part "(v,4,1)-BIBD" nor in the part "(v,5,1)-BIBD".

Move stuff around if you want. As far as I am concerned, it is totally pointless. This being said, some of those functions are together in the code because I implemented them, following the same reference, so if you move them apart please leave them linked together somehow.

I do not care too much. But, when I opened the file the first time it was difficult to found the logic.

[...]
And if something which those constructions require is of more general use we can of course expose it inside of the main constructor.

Indeed, this was my main question. (I had a look at various paper about difference families, and there are a lot about k=3,4,5, very few about k=6 and almost none about k>=7; excepted existence result for very large v).

I found the work done in the branch is enough for the ticket so I set to positive review.

Vincent

[videlec]

Reviewer: Vincent Delecroix

[nathanncohen]

comment:20

Yo !!

Thanks for the review !

I bet that there are some PBD constructions in the Handbook... We should keep in mind to reuse this code at some point.

Indeed, but my fear with PBD construction is that it may become harder to detect if we can build one. I mean.. If you have a (100,[4,6,8])-PBD and a (6,[3])-PBD then you have also a (100,[3,4,8])-PBD, stuff like that. You can really mix a lot of different things there, soooo... Well. It may be tricky. We will do it, but it will be tricky to do it well.

I do not care too much. But, when I opened the file the first time it was difficult to found the logic.

AHahah. ALl this is there for "historical reasons" I fear. Implemented one after the other. I expect that it will be cleaned several times in the future.

Indeed, this was my main question. (I had a look at various paper about difference families, and there are a lot about k=3,4,5, very few about k=6 and almost none about k>=7; excepted existence result for very large v).

Indeed, but Julian R. Abel told me that some recursive construction may be by itself sufficient to generate all (v,6,1)-BIBD with v>1000. Looks like when you have a lot of recursive construction you can do almost everything, and that some base cases will be the only missing things afterwards.

Ahahaah.

The point is that it is all a lot of work, and all an interesting work too. And I would like to add it someday, but for the moment I would like to finish implementing all the OA/TD/MOLS related code. I have some new constructions to add but I did not write the branch yet for it would depend on other tickets, and I am pretty sure that the main functions I need will be rewritten and changed during the reviews, so I don't dare write this yet as it will mean a lot of rebase. But when the OA/TD/MOLS stuff will be done, both PBD and BIBD with larger blocks will be on the table.

I found the work done in the branch is enough for the ticket so I set to positive review.

Thaaaaaaaaaaaaaanks ! I will write to the author of the pdf file tomorrow :-)

Nathann

[vbraun]

Changed branch from u/vdelecroix/16323 to 8eac6d0