Opened 6 years ago
Closed 6 years ago
#16323 closed enhancement (fixed)
Construction of BIBD with k=5
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.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 )
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 6 years ago by
 Branch set to u/ncohen/16323
 Commit set to 2ac6aef7804800da10594bb3c3df9bb00c7c552e
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit changed from 2ac6aef7804800da10594bb3c3df9bb00c7c552e to 8529434c26b5acb95ead359de0a62c89afefeb16
comment:3 Changed 6 years ago by
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 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:5 Changed 6 years ago by
 Dependencies set to #16279
comment:6 Changed 6 years ago by
 Component changed from combinatorics to combinatorial designs
comment:7 Changed 6 years ago by
 Commit changed from 8529434c26b5acb95ead359de0a62c89afefeb16 to 07a31304b9d48ef6e07f1dd96c1d3185b8fafc95
Branch pushed to git repo; I updated commit sha1. New commits:
07a3130  trac #16323: Merged with 6.3.beta1

comment:8 followup: ↓ 9 Changed 6 years ago by
 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, abd, b+c+d], ....: [c, b+c, a+bd, ab+d, a+b+c], ....: [a+b, a+cd, bc+d, abcd, ab+c+d], ....: [bd, a+b+d, ab+c, b+c+d, ab+cd]]
Moreover, writing that way it avoids the conversion from tuple to elements of the group G.
Vincent
comment:9 in reply to: ↑ 8 Changed 6 years ago by
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, theG(x if some_reason else [x])
is ugly. I know it is because ofAdditiveAbelianGroup
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 ofAdditiveAbelianGroup
). 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 6 years ago by
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 6 years ago by
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 (v1)%(k1) != 0): if existence:
Nathann
comment:12 Changed 6 years ago by
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 AbelBaratti 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 6 years ago by
Actually, I did a mistake: BIBD(1,k) always exists, just consider an empty set of blocks !!
comment:14 Changed 6 years ago by
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 6 years ago by
Hi Nathann,
My mistake, I did not commit the changes. Now everything is on trac.
Vincent
comment:16 Changed 6 years ago by
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 ((v1)%4 == 0 and (v*(v1))%20 == 0) + assert (v%20 == 5 or v%20 == 1)
Nathann
comment:17 followup: ↓ 18 Changed 6 years ago by
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
andv_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 ofsteiner_triple_system
,v_4_1_BIBD
andv_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 ; followup: ↓ 19 Changed 6 years ago by
 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
andv_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

comment:19 in reply to: ↑ 18 ; followup: ↓ 20 Changed 6 years ago by
 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 6 years ago by
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 6 years ago by
 Branch changed from u/vdelecroix/16323 to 8eac6d069e162aed9d4fc1ae3f654d0b446573da
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
trac #16272: finer doctest to test the output of transversal_design
trac #16272: ultimate doctest
trac #16272: simplifying the structure of orthogonal_array
trac #16272: Merged with updated #16227
trac #16279: BIBD from Transversal Designs
trac #16279: Merged with updated #16272
trac #16279: Merged with 6.2
trac #16279: Fixing the doc
trac #16279: Merged with updated #16091
trac #16323: Construction of BIBD with k=5