Opened 7 years ago
Closed 7 years ago
#16227 closed enhancement (fixed)
Product construction of Transversal Designs
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  
Cc:  vdelecroix, knsam, dimpase  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  5cfee91 (Commits)  Commit:  5cfee91760bd3b73d19ebc1318a94861d62b226f 
Dependencies:  #15310  Stopgaps: 
Description
This branch implements a product construction of transversal designs. This allows to build new transversal designs that are needed for the general construction of bibd with k=5.
Nathann
Change History (17)
comment:1 Changed 7 years ago by
 Branch set to u/ncohen/16227
 Commit set to d0e33a6442be6048db925335fd006ab20fc5ffc3
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Commit changed from d0e33a6442be6048db925335fd006ab20fc5ffc3 to 054d2a2ffa441f675594a09b95cf943f41121b4c
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
054d2a2  trac #16227: Product construction of Transversal Designs

comment:3 Changed 7 years ago by
Hi,
Once you have fix the merge with #15310, here are other problems
 the product is sometimes called the Kronecker product and it should be mentioned in the doc.
 I do not like the way it works:
wilson_construction
andTD_product
have the same purpose, build more examples of TD. But first of all, the naming scheme are different. Why not TD_wilson_construction? More importantly, in Wilson construction, you do not have to feed the function with the TD(k,m), TD(k,m+1), TD(k+1,t) and TD(k,u) but for the product you have to. From what you started with in Wilson construction, I thought we would have a functiondef product(k, n1, n2):
.
It might be easier to do the whole review in #15310. I propose to merge the two tickets and set this one as won't fix.
comment:4 followup: ↓ 5 Changed 7 years ago by
1) As I mentioned in #15310, I would prefer to have TD_product
to be something called with arguments k,n1,n2
as it is for Wilson construction. Specifications def TD_product(k,n1,n2,TD1=None,TD2=None)
might be better. But then, if you provide TD1 and TD2, the arguments k,n1,n2 are redundant.
2) Is there any link between this product construction and the one for mols?
3) As Brett mentioned in #15310, it would make sense to have a more involved find_wilson_decomposition
which also contains product. There are tons of variants of Wilson decomposition and according to ColbourneDinitz this is how most of the current records are obtained. We might concentrate all the nondirect constructions into a global function build_TD_from_smaller_ones
or generalized_Wilson_construction
.
comment:5 in reply to: ↑ 4 ; followup: ↓ 8 Changed 7 years ago by
Yo !
1) As I mentioned in #15310, I would prefer to have
TD_product
to be something called with argumentsk,n1,n2
as it is for Wilson construction. Specificationsdef TD_product(k,n1,n2,TD1=None,TD2=None)
might be better. But then, if you provide TD1 and TD2, the arguments k,n1,n2 are redundant.
What is the point of having a function TD_product
which only takes integer as input ? What can it do that designs.transversal_design(...)
does not already do ?
What we could do is implement a second function TD_product_from_parameters which calls the other ?
3) As Brett mentioned in #15310, it would make sense to have a more involved
find_wilson_decomposition
which also contains product. There are tons of variants of Wilson decomposition and according to ColbourneDinitz this is how most of the current records are obtained. We might concentrate all the nondirect constructions into a global functionbuild_TD_from_smaller_ones
orgeneralized_Wilson_construction
.
Whyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy ?
Right now I am building all the constructions of OA in such a way that they all take the same parameters :
function_that_builds_OA(k,n,availability)
and it does what you expect, i.e. try if it is able to build this OA and answers accordingly. If we can make all functions that return OA behave this way, and the constructor can look like this :
for f in [f1,f2,f3,f4,....]: # try if f can be the OA we want, otherwise try the next.
So if we have recursive functions behaving this way, we can just add them to the list !
Nathann
comment:6 Changed 7 years ago by
(scuse me, replace "availability" with "existence")
comment:7 Changed 7 years ago by
 Commit changed from 054d2a2ffa441f675594a09b95cf943f41121b4c to a512ab154b21caaf74d6ccef2cf32bf67179eee9
comment:8 in reply to: ↑ 5 ; followup: ↓ 9 Changed 7 years ago by
Replying to ncohen:
Yo !
1) As I mentioned in #15310, I would prefer to have
TD_product
to be something called with argumentsk,n1,n2
as it is for Wilson construction. Specificationsdef TD_product(k,n1,n2,TD1=None,TD2=None)
might be better. But then, if you provide TD1 and TD2, the arguments k,n1,n2 are redundant.What is the point of having a function
TD_product
which only takes integer as input ? What can it do thatdesigns.transversal_design(...)
does not already do ?What we could do is implement a second function TD_product_from_parameters which calls the other ?
Sometimes you want only functions with the same prototype and sometimes you claim it is better otherwise...
3) As Brett mentioned in #15310, it would make sense to have a more involved
find_wilson_decomposition
which also contains product. There are tons of variants of Wilson decomposition and according to ColbourneDinitz this is how most of the current records are obtained. We might concentrate all the nondirect constructions into a global functionbuild_TD_from_smaller_ones
orgeneralized_Wilson_construction
.Whyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy ?
Right now I am building all the constructions of OA in such a way that they all take the same parameters :
function_that_builds_OA(k,n,availability)
and it does what you expect, i.e. try if it is able to build this OA and answers accordingly. If we can make all functions that return OA behave this way, and the constructor can look like this :
All right. What I meant is that it makes sense to try Wilson and product in the same function that builds OA. But on the other hands, calling divisors is relatively cheap on the kind of entries you will have. In a near future (and according to the TODO) the Wilson construction might be much more involved... will see.
There was doctest error that I solved on u/vdelecroix/16227. I also added curiosity doctests (the current maximum k that Sage knows from n between 10 and 20).
See the changes in u/vdelecroix/16227, if you are happy with them this is good to go.
comment:9 in reply to: ↑ 8 Changed 7 years ago by
Sometimes you want only functions with the same prototype and sometimes you claim it is better otherwise...
1) I think that having a TD product functions that accepts TD as input and not only parameters is useful
2) I think that at the moment Wilson's construction with TD as input is not really useful, as it is a complex thing and nobody knows it exists
3) I think that all constructors should have the same prototype to give us a clean orthogonal_array
function
4) Thus creating a second function that calls the current TD and has the same prototype as the others makes sense to me.
All right. What I meant is that it makes sense to try Wilson and product in the same function that builds OA. But on the other hands, calling divisors is relatively cheap on the kind of entries you will have. In a near future (and according to the TODO) the Wilson construction might be much more involved... will see.
Calling divisors is 100% free compared to the kind of constructions we deal with. We create fields, products, long lists, temporary matrices of thousands of entries. Calling divisors *is* free.
There was doctest error that I solved on u/vdelecroix/16227. I also added curiosity doctests (the current maximum k that Sage knows from n between 10 and 20).
See the changes in u/vdelecroix/16227, if you are happy with them this is good to go.
I will look at this immediately.
Nathann
comment:10 Changed 7 years ago by
Looks cool. Do you mind if I change your "curiosity tests" by using availability=True
, so that we have boolean answers instead of exceptions ? And this will become "Unknown" return values in a later patch.
Nathann
comment:11 Changed 7 years ago by
 Commit changed from a512ab154b21caaf74d6ccef2cf32bf67179eee9 to 4d6e964775e4d6734e677a9f281f56aee11bb696
comment:12 Changed 7 years ago by
Well... Actually they were "Unknown" answers already.. So if you don't mind here is the branch, otherwise we can go back to your latest commit, it is not very important. Just easier to read (for me), and it advertises the "Unknown" truth values for those who haven't met them.
Nathann
comment:13 Changed 7 years ago by
 Status changed from needs_review to positive_review
Ok. Then it is good for me.
Vincent
comment:14 Changed 7 years ago by
 Commit changed from 4d6e964775e4d6734e677a9f281f56aee11bb696 to 5cfee91760bd3b73d19ebc1318a94861d62b226f
 Status changed from positive_review to needs_review
comment:15 Changed 7 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
(same trivial conflict with the new release)
comment:16 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:17 Changed 7 years ago by
 Branch changed from u/ncohen/16227 to 5cfee91760bd3b73d19ebc1318a94861d62b226f
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #15310: Wilson's construction of Transversal Designs
trac #15310: Rebase on updated #15431
trac #15310: Merged into 6.2.rc0
trac #16227: Product construction of Transversal Designs