Product construction of Transversal Designs

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

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

Depends on #15310

CC: @videlec @KPanComputes @dimpase

Component: combinatorics

Author: Nathann Cohen

Branch/Commit: 5cfee91

Reviewer: Vincent Delecroix

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Commit: d0e33a6

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Branch: u/ncohen/16227

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

New commits:

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

054d2a2

trac #16227: Product construction of Transversal Designs

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d0e33a6 to 054d2a2

[videlec]

comment:3

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.

[videlec]

comment:4

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.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:6

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 054d2a2 to a512ab1

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f23fa88	trac #15310: useless checks
62f0158	trac #15310: cutting some branches of the exploration
d743414	trac #15310: reviewer's remarks
3fc79ba	trac #15310: Merged into 6.2.rc1
a512ab1	trac #16227: Merged with updated #15310

[videlec]

comment:8

Replying to @nathanncohen:

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.

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:9

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

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:10

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e62fae8	corrected doctests + new doctests
4d6e964	trac #16227: Replace exception with booleans in the doctests

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a512ab1 to 4d6e964

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:12

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

[videlec]

comment:13

Ok. Then it is good for me.

Vincent

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e86d26c	trac #15310: Merged with 6.2.rc2
5cfee91	trac #16227: Merged with updated #15310

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4d6e964 to 5cfee91

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Reviewer: Vincent Delecroix

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:15

(same trivial conflict with the new release)

[vbraun]

Changed branch from u/ncohen/16227 to 5cfee91