Opened 5 years ago

Closed 5 years ago

#16323 closed enhancement (fixed)

Construction of BIBD with k=5

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorial designs Keywords:
Cc: vdelecroix, knsam, dimpase, brett Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 8eac6d0 (Commits) Commit: 8eac6d069e162aed9d4fc1ae3f654d0b446573da
Dependencies: #16279 Stopgaps:

Description (last modified by ncohen)

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

Change History (21)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16323
  • Commit set to 2ac6aef7804800da10594bb3c3df9bb00c7c552e
  • Description modified (diff)
  • Status changed from new to needs_review

Last 10 new commits:

5074eeetrac #16272: finer doctest to test the output of transversal_design
d81f265trac #16272: ultimate doctest
47798d2trac #16272: simplifying the structure of orthogonal_array
d34b012trac #16272: Merged with updated #16227
569c485trac #16279: BIBD from Transversal Designs
60e8d35trac #16279: Merged with updated #16272
927d325trac #16279: Merged with 6.2
e1b29bftrac #16279: Fixing the doc
e941a54trac #16279: Merged with updated #16091
2ac6aeftrac #16323: Construction of BIBD with k=5

comment:2 Changed 5 years ago by git

  • Commit changed from 2ac6aef7804800da10594bb3c3df9bb00c7c552e to 8529434c26b5acb95ead359de0a62c89afefeb16

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

c127a6dtrac #16272: Merged with updated #16231
e2749b3trac #16272: Merged with 6.3.beta0
4115b72trac #16279: Merged with updated #16272
8529434trac #16323: Merged with #16279

comment:3 Changed 5 years ago by ncohen

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

comment:4 Changed 5 years ago by leif

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 5 years ago by ncohen

  • Dependencies set to #16279

comment:6 Changed 5 years ago by ncohen

  • Component changed from combinatorics to combinatorial designs

comment:7 Changed 5 years ago by git

  • Commit changed from 8529434c26b5acb95ead359de0a62c89afefeb16 to 07a31304b9d48ef6e07f1dd96c1d3185b8fafc95

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

07a3130trac #16323: Merged with 6.3.beta1

comment:8 follow-up: Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_info

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

comment:9 in reply to: ↑ 8 Changed 5 years ago by ncohen

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

comment:10 Changed 5 years ago by ncohen

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

comment:11 Changed 5 years ago by ncohen

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

comment:12 Changed 5 years ago by vdelecroix

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

comment:13 Changed 5 years ago by vdelecroix

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

comment:14 Changed 5 years ago by ncohen

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

comment:15 Changed 5 years ago by vdelecroix

Hi Nathann,

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

Vincent

comment:16 Changed 5 years ago by ncohen

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

comment:17 follow-up: Changed 5 years ago by vdelecroix

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

comment:18 in reply to: ↑ 17 ; follow-up: Changed 5 years ago by ncohen

  • Branch changed from u/ncohen/16323 to u/vdelecroix/16323
  • Commit changed from 07a31304b9d48ef6e07f1dd96c1d3185b8fafc95 to 8eac6d069e162aed9d4fc1ae3f654d0b446573da

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:

0610c7dtrac #16323: external BIBD_from_DF and use Zmod
daae63etrac #16323: DF -> difference_family, change errors and more doc
8eac6d0trac #16323: several fix + doc

comment:19 in reply to: ↑ 18 ; follow-up: Changed 5 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_info to positive_review

Hello,

Replying to ncohen:

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

comment:20 in reply to: ↑ 19 Changed 5 years ago by ncohen

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

comment:21 Changed 5 years ago by vbraun

  • Branch changed from u/vdelecroix/16323 to 8eac6d069e162aed9d4fc1ae3f654d0b446573da
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.