Equivalence between OA/TD/MOLS

[nathanncohen]

This branch implements the following equivalence result : there exists a TD(k,n) iif there exists a OA(k,n) iif there exists k+2 MOLS.

With this branch, the three constructors communicate with each other, and a construction of any of these objects can be used to create objects of the other kinds.

Because the constructor of OA calls the constructor of TD,and because the constructor of TD calls the constructor of OA, there is a new who_asked parameters in these constructors which can be used to remember who asked the question first.

On the down side : the constructor of MOLS used to be able to return "the maximum number of MOLS of size nxn that Sage can build". With this patch, the feature is removed.

Explanation: I created this feature because we only had two simple constructions of MOLS, and because it was easy to guess this number k from those constructions. With the new equivalences, this is not as easy anymore, thus I removed it for the moment.

I think that it is not that bad, considering that it appeared very recently, and that not many people may even know that Sage can build MOLS yet.

This feature, however, can be interesting, and can be reimplemented. While with the two former constructions it was easy to guess in one line, we now have to try all possible parameters to find the largest integer k we are looking for. This is not necessarily very time-consuming given that all these objects now have an "availability" flag.
Hence it will be implemented again, this time for all constructions at the same time.

Two important points:

1. The fact that the constructions communicate with each other means that Sage returns better results than before (and in particular the "maximum" number formerly returned by the constructor of MOLS is in many cases smaller than what Sage can now do
2. The McNeish theorem from the constructors of MOLS has now been removed, as the same constructions has been implemented for TD since (Product construction of Transversal Designs #16227), and better (i.e. the best decomposition is found, not necessarily a decomposition into prime powers)

HEeeeeeeeeeeeeeeeeere it is ! :-)

Nathann

Depends on #15310
Depends on #16227

CC: @videlec @KPanComputes @dimpase

Component: combinatorics

Author: Nathann Cohen

Branch/Commit: 9e5e94f

Reviewer: Vincent Delecroix

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

[nathanncohen]

Branch: u/ncohen/16231

[sagetrac-git]

Commit: a46446f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. 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
f23fa88	trac #15310: useless checks
a46446f	trac #16231: Equivalence between OA/TD/MOLS

[videlec]

comment:3

Hello,

Remainder: the content of this ticket has been partially discussed in #15310 and #16227.

I assume that the big goal of this ticket is also to find more constructions.

The operation which consists in removing groups is trivial. So instead of given a couple (k,n) look for a TD(k,n) it is just more meaningful for a given n to have functions which:

• return the largest k such that Sage knows how to build a TD(k,n) and provide it
• the smallest k such that Sage knows that there does not exist a TD(k,n) and provide the Theorem that says so (see also redesign transversal designs #16272 for that)

Removing this feature from the MOLS in is very bad. I would rather try to make it available in the other functions. Doing it by "trying all k before it says no" does not look like a good strategy to me.

In order to find new TD(k,n), we have different strategies:

• individual constructions (currently there is TD_6_12 and also the ones introduced in New MOLS shared by Ian Wanless #16241 Five mutually orthogonal latin squares of order 12 #16236 and A pair of orthogonal latin squares of order 10 #16235)
• family constructions (these are currently included into orthogonal_array and mutually_orthogonal_latin_squares). It is hard for me to tell if those constructions overlap.
• generalized Wilson constructions which build TD(k,n) from "smaller" ones
• translations, which is basically what this ticket is about

Is that all? I would like this to be clear before thinking about what you did.

Vincent

[nathanncohen]

comment:4

Yo !

I assume that the big goal of this ticket is also to find more constructions.

Indeed.

The operation which consists in removing groups is trivial. So instead of given a couple (k,n) look for a TD(k,n) it is just more meaningful for a given n to have functions which:

• return the largest k such that Sage knows how to build a TD(k,n) and provide it
• the smallest k such that Sage knows that there does not exist a TD(k,n) and provide the Theorem that says so (see also redesign transversal designs #16272 for that)

Removing this feature from the MOLS in is very bad.

Vincent, you need to stop screaming every ten seconds when something trivial is changed. This thing will appear again, as I am telling you that I want to reproduce the big MOLS table in the Handbook. Finding the largest k in the very purpose of my not sleeping and forgetting to eat for days.

I removed this parameter right now because it can not be guessed at no cost, as it was the case. In order to find the largest k, you must explore many branches and recursive constructions, and implementing this will be done in another ticket, as those are sufficiently complicated and long to review already.

Again, stop screaming every minute. There was NOTHING about MOLS in Sage very recently, and we implement a lot of stuff at once. Here I remove stuff because it makes my patch easier to implement, and I will add it again later. Nobody even knew that this feature existed except me.

I would rather try to make it available in the other functions. Doing it by "trying all k before it says no" does not look like a good strategy to me.

Vincent, be serious. Have you thought about it ?... There is no other way to do that.

In order to find new TD(k,n), we have different strategies:

• individual constructions (currently there is TD_6_12 and also the ones introduced in New MOLS shared by Ian Wanless #16241 Five mutually orthogonal latin squares of order 12 #16236 and A pair of orthogonal latin squares of order 10 #16235)

And the ones I am implementing. Indeed.

• family constructions (these are currently included into orthogonal_array and mutually_orthogonal_latin_squares). It is hard for me to tell if those constructions overlap.

They must overlap on some values, and not on others.

• generalized Wilson constructions which build TD(k,n) from "smaller" ones

Yep.

• translations, which is basically what this ticket is about

Yep.

Is that all? I would like this to be clear before thinking about what you did.

Well, I think that it is all.

The point is that before this ticket, the MOLS constructor has only two cases :

1. A family construction for prime powers

2. A product decomposition applied stupidly : factor the input into prime power, and do the best you can with that.

When the first is applied, the "best k" is easy to find.

When the second is applied, the "best k" is easy to find.

Thus I had added this feature or returning the "best k", because it came at absolutely no cost.

Now we can build much better MOLS than that, because we have a LOT of constructions in OA/TD that MOLS can use, and so we can return MOLS that we would not have had with the previous constructions. On the other hand, if the "best k" we can now build is higher than what we could do before, it is not as easy to deduce because you have to explore stuff, in particular in the recursive constructions of OA/TD.

Thus I removed this guessing, because it is not how this feature is to be implemented. The only way I see to implement it is to try all values and return the largest one found, and I have no idea what you can think about when you say that it "does not look like a good strategy". It is the only one we can implement.

And we will implement this "best k" for all constructions at the same time. Or perhaps only for OA, and all others will ask it. Once, and for all constructors. But first, let them communicate.

Nathann

[sagetrac-git]

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

62f0158	trac #15310: cutting some branches of the exploration
d743414	trac #15310: reviewer's remarks
3fc79ba	trac #15310: Merged into 6.2.rc1
054d2a2	trac #16227: Product construction of Transversal Designs
a512ab1	trac #16227: Merged with updated #15310
e62fae8	corrected doctests + new doctests
4d6e964	trac #16227: Replace exception with booleans in the doctests
a9dce70	trac #16231: Merged with updated #16227

[sagetrac-git]

Changed commit from a46446f to a9dce70

[videlec]

comment:6

Hi Nathann,

I added some documentation, please start editing from u/vdelecroix/16231

If n is a prime power, there is an optimal construction, i.e. a TD(n+1,n) and there is no need to check for product or Wilson construction. But right now the code in transversal_design does. For prime powers there are two places where some code is implemented:

• in orthogonal_array (you refer to theorem 6.39 and 6.40 of Stinson)
• in mutually_orthogonal_latin_squares (you refer to section 6.4.1 of Stinson)
  Are the outputs equivalent? Note that there is no way to test it with the current code, unless I use the forbidden who_asked parameter. Would it be possible to isolate the two constructions in two functions? Why do we need two constructions for the case of n being a prime power?

Vincent

[nathanncohen]

comment:7

Yo !

I added some documentation, please start editing from u/vdelecroix/16231

Okay, I'll look at that right now.

If n is a prime power, there is an optimal construction, i.e. a TD(n+1,n) and there is no need to check for product or Wilson construction. But right now the code in transversal_design does. For prime powers there are two places where some code is implemented:

• in orthogonal_array (you refer to theorem 6.39 and 6.40 of Stinson)
• in mutually_orthogonal_latin_squares (you refer to section 6.4.1 of Stinson)
  Are the outputs equivalent?

No idea. They return valid answers, but I have no idea if they are the same. I would say "no", but really who cares ? Let's keep only one.

Note that there is no way to test it with the current code, unless I use the forbidden who_asked parameter.

Am I guilty for that ?... :-P

Would it be possible to isolate the two constructions in two functions? Why do we need two constructions for the case of n being a prime power?

I don't think we need two constructions of the same designs... I mean. AFTER this patch is merged, I don't think we need two, given that they all communicate with each other. BEFORE this patch, we actually need three different implementations ;-)

Nathann

[nathanncohen]

comment:8

Okay, I agree with your modifications except one :

+        if availability:
+            return False
+        from sage.categories.sets_cat import EmptySetError
+        raise EmptySetError("No Transversal Design exists when k>=n+2")

We shouldn't duplicate non-existence results but rather forward them, in this case forward it from OA to TD.

The nice thing is that later we will be able to implement a 'non-existence result' exactly like a construction !!

A 'non-existence result' will be a function taking a "k,n,existence=" as parameter, which can sometimes return "False" as an answer instead of "Unknown" ;-)

Thiiiiiiiiiis code will become COOL.

Nathann

[videlec]

comment:9

Replying to @nathanncohen:

Okay, I agree with your modifications except one :

+        if availability:
+            return False
+        from sage.categories.sets_cat import EmptySetError
+        raise EmptySetError("No Transversal Design exists when k>=n+2")

We shouldn't duplicate non-existence results but rather forward them, in this case forward it from OA to TD.

For the simple reason that in transversal_design you first start to check if there exists a product and a Wilson decomposition before discovering that for trivial reasons your parameters are not valid...

Vincent

[nathanncohen]

comment:10

For the simple reason that in transversal_design you first start to check if there exists a product and a Wilson decomposition before discovering that for trivial reasons your parameters are not valid...

Isn't the problem solved if we call orthogonal_array before trying the decomposition ?

Nathann

[videlec]

comment:11

Replying to @nathanncohen:

For the simple reason that in transversal_design you first start to check if there exists a product and a Wilson decomposition before discovering that for trivial reasons your parameters are not valid...

Isn't the problem solved if we call orthogonal_array before trying the decomposition ?

It is if all easy checks of non-existence are done inside orthogonal_array. Moreover, it is not specified right now that when availability is set to True that an answer False means that the object does not exist...

[nathanncohen]

comment:12

Yo !

It is if all easy checks of non-existence are done inside orthogonal_array.

Why ? It would work anyway. The order changes the performances, not the existence of a result.

Moreover, it is not specified right now that when availability is set to True that an answer False means that the object does not exist...

True. So you can either add something which we will remove in a patch today or tomorrow, or wait until we change "availability" to "existence" so that we can do this properly.

Nathann

[nathanncohen]

Changed branch from u/ncohen/16231 to public/16231

[nathanncohen]

comment:13

I changed the branch. You can append your commits to public/16231 when you are done :-)

Nathann

[nathanncohen]

comment:14

(aaaaaand I just began to prepare the 1000 OA constructions I finished this morning)

[videlec]

comment:15

About my check at the begining of TD, there is exactly the same code at the begining of MOLS... so what?

[nathanncohen]

comment:16

About my check at the begining of TD, there is exactly the same code at the begining of MOLS... so what?

As I say, we can either include it now and remove it later or not do it, really it is up to you. I still consider this code as "being worked on" and everything in there is pretty new. For as long as it does not return wrong results, I do not mind if it is not "finished" given that I am working on it and that I know it will be patched soon :-)

Nathann

[nathanncohen]

comment:17

Gosh... The branch on #16277 will be awful. I have three dependencies which all have dependencies. There will be one thousand commit on the branch and actually only ONE which is just about that branch :-P

This would have been complicated with Mercurial I guess ^^;

Nathann

[sagetrac-git]

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

8d8b928	more documentation to orthogonal_arrays.py
8257178	remove MOLS construction for prime powers + doc

[sagetrac-git]

Changed commit from a9dce70 to 8257178

[videlec]

comment:19

Hi Nathann,

I updated the code with what I proposed. Please check.

[nathanncohen]

comment:20

Yooooooooooo !

I agree with everything. Well.

Except : Vincent, you are one of the guys who cannot stand to see

if ___ :
    return
else:
    return

I am the kind of guy who cannot stand to see

if ___:
    return
return

Sooooooo could we coexist in the way that you don't change my writing unless you need to, and I don't change yours unless I need to ? :-P

Thaaaaaaanks. Good to go for me. And the constructions patch will be ready soon :-)

Nathann

[videlec]

comment:21

Hi Nathann,

I like both, but have a preference for the second one. Anyway I started doing it because both kinds were present. I will revert to the way you like.

[nathanncohen]

comment:22

Well it really doesn't matter, let's keep it as it is ! I just had many reviews on "you should not write it the way you like, write it the way I like instead" :-P

It's cool like that, we have more interesting wars to fight :-D

Nathann

[nathanncohen]

comment:23

I just tested, and all tests pass. So if it is okay for you, it can go too :-)

Nathann

[sagetrac-git]

Changed commit from 8257178 to d051cf4

[sagetrac-git]

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

d051cf4

ValueError -> EmptySetError in latin_squares

[videlec]

comment:25

Added a trivial change for uniformization. Feel free to positive review it.

I will start #16272 now.

Vincent

[nathanncohen]

comment:26

Argggggggg...
Nononono don't ! I already began !

Nathann

[nathanncohen]

comment:27

Okay with your test. So I set this to positive_review. About #16272 : I am writing the part of the patch that changes !True/False into !True/False/Unknown. I already did it for BIBD. I can see this to the end then you can take the branch and add the non-existence results ? Is that okay for you ?

If you want to work on designs you can look at #16277 in the meantime. The two tasks do not conflict.

Nathann

[nathanncohen]

Reviewer: Vincent Delecroix

[videlec]

comment:29

Replying to @nathanncohen:

Okay with your test. So I set this to positive_review. About #16272 : I am writing the part of the patch that changes !True/False into !True/False/Unknown. I already did it for BIBD. I can see this to the end then you can take the branch and add the non-existence results ? Is that okay for you ?

Ok. I let you start. I am looking at the literature right now.

[sagetrac-git]

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
35be2fe	trac #16231: Merged with updated #16277

[sagetrac-git]

Changed commit from d051cf4 to 35be2fe

[sagetrac-git]

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

9e5e94f

trac #16231: Merged with updated #16227

[sagetrac-git]

Changed commit from 35be2fe to 9e5e94f

[nathanncohen]

comment:32

Still updating (and making mistakes in the commit messages)

[vbraun]

Changed branch from public/16231 to 9e5e94f