Opened 5 years ago

Closed 5 years ago

#16227 closed enhancement (fixed)

Product construction of Transversal Designs

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.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 5 years ago by ncohen

  • Branch set to u/ncohen/16227
  • Commit set to d0e33a6442be6048db925335fd006ab20fc5ffc3
  • Status changed from new to needs_review

New commits:

03f896ctrac #15310: Wilson's construction of Transversal Designs
6357236trac #15310: Rebase on updated #15431
25f5959trac #15310: Merged into 6.2.rc0
d0e33a6trac #16227: Product construction of Transversal Designs

comment:2 Changed 5 years ago by git

  • Commit changed from d0e33a6442be6048db925335fd006ab20fc5ffc3 to 054d2a2ffa441f675594a09b95cf943f41121b4c

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

054d2a2trac #16227: Product construction of Transversal Designs

comment:3 Changed 5 years ago by vdelecroix

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 and TD_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 function def 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 follow-up: Changed 5 years ago by vdelecroix

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 Colbourne-Dinitz this is how most of the current records are obtained. We might concentrate all the non-direct constructions into a global function build_TD_from_smaller_ones or generalized_Wilson_construction.

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

Yo !

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.

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 Colbourne-Dinitz this is how most of the current records are obtained. We might concentrate all the non-direct constructions into a global function build_TD_from_smaller_ones or generalized_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 5 years ago by ncohen

(scuse me, replace "availability" with "existence")

comment:7 Changed 5 years ago by git

  • Commit changed from 054d2a2ffa441f675594a09b95cf943f41121b4c to a512ab154b21caaf74d6ccef2cf32bf67179eee9

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

f23fa88trac #15310: useless checks
62f0158trac #15310: cutting some branches of the exploration
d743414trac #15310: reviewer's remarks
3fc79batrac #15310: Merged into 6.2.rc1
a512ab1trac #16227: Merged with updated #15310

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

Replying to ncohen:

Yo !

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.

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 ?

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 Colbourne-Dinitz this is how most of the current records are obtained. We might concentrate all the non-direct constructions into a global function build_TD_from_smaller_ones or generalized_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 5 years ago by ncohen

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 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from a512ab154b21caaf74d6ccef2cf32bf67179eee9 to 4d6e964775e4d6734e677a9f281f56aee11bb696

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

e62fae8corrected doctests + new doctests
4d6e964trac #16227: Replace exception with booleans in the doctests

comment:12 Changed 5 years ago by ncohen

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 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Ok. Then it is good for me.

Vincent

comment:14 Changed 5 years ago by git

  • Commit changed from 4d6e964775e4d6734e677a9f281f56aee11bb696 to 5cfee91760bd3b73d19ebc1318a94861d62b226f
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

e86d26ctrac #15310: Merged with 6.2.rc2
5cfee91trac #16227: Merged with updated #15310

comment:15 Changed 5 years ago by ncohen

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

(same trivial conflict with the new release)

comment:16 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:17 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/16227 to 5cfee91760bd3b73d19ebc1318a94861d62b226f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.