Opened 6 years ago
Closed 6 years ago
#16231 closed enhancement (fixed)
Equivalence between OA/TD/MOLS
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:  9e5e94f (Commits)  Commit:  9e5e94f648113d6b824039651bcb8d98144e01b2 
Dependencies:  #15310, #16227  Stopgaps: 
Description
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 timeconsuming 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 (#16227), and better (i.e. the best decomposition is found, not necessarily a decomposition into prime powers)
HEeeeeeeeeeeeeeeeeere it is ! :)
Nathann
Change History (34)
comment:1 Changed 6 years ago by
 Branch set to u/ncohen/16231
 Component changed from PLEASE CHANGE to combinatorics
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 6 years ago by
 Commit set to a46446f3b29690aa1245583639bb6b78b3d50dca
comment:3 followup: ↓ 4 Changed 6 years ago by
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 #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 #16241 #16236 and #16235)  family constructions (these are currently included into
orthogonal_array
andmutually_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
comment:4 in reply to: ↑ 3 Changed 6 years ago by
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 #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:
And the ones I am implementing. Indeed.
 family constructions (these are currently included into
orthogonal_array
andmutually_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
comment:5 Changed 6 years ago by
 Commit changed from a46446f3b29690aa1245583639bb6b78b3d50dca to a9dce705211f5593b926c0512a40ada05d978ff3
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

comment:6 followup: ↓ 7 Changed 6 years ago by
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
comment:7 in reply to: ↑ 6 Changed 6 years ago by
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. aTD(n+1,n)
and there is no need to check for product or Wilson construction. But right now the code intransversal_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
comment:8 followup: ↓ 9 Changed 6 years ago by
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 nonexistence 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 'nonexistence result' exactly like a construction !!
A 'nonexistence 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
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 6 years ago by
Replying to ncohen:
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 nonexistence 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
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 6 years ago by
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
comment:11 in reply to: ↑ 10 ; followup: ↓ 12 Changed 6 years ago by
Replying to ncohen:
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 nonexistence 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...
comment:12 in reply to: ↑ 11 Changed 6 years ago by
Yo !
It is if all easy checks of nonexistence 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 toTrue
that an answerFalse
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
comment:13 Changed 6 years ago by
 Branch changed from u/ncohen/16231 to public/16231
I changed the branch. You can append your commits to public/16231
when you are done :)
Nathann
comment:14 Changed 6 years ago by
(aaaaaand I just began to prepare the 1000 OA constructions I finished this morning)
comment:15 followup: ↓ 16 Changed 6 years ago by
About my check at the begining of TD, there is exactly the same code at the begining of MOLS... so what?
comment:16 in reply to: ↑ 15 Changed 6 years ago by
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
comment:17 Changed 6 years ago by
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
comment:18 Changed 6 years ago by
 Commit changed from a9dce705211f5593b926c0512a40ada05d978ff3 to 8257178acf8691b62a4092538bcaed47e73b3953
comment:19 Changed 6 years ago by
Hi Nathann,
I updated the code with what I proposed. Please check.
comment:20 Changed 6 years ago by
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
comment:21 Changed 6 years ago by
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.
comment:22 Changed 6 years ago by
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
comment:23 Changed 6 years ago by
I just tested, and all tests pass. So if it is okay for you, it can go too :)
Nathann
comment:24 Changed 6 years ago by
 Commit changed from 8257178acf8691b62a4092538bcaed47e73b3953 to d051cf4f127aa7c23c0b4a09ca12d4ecaf2caee6
Branch pushed to git repo; I updated commit sha1. New commits:
d051cf4  ValueError > EmptySetError in latin_squares

comment:25 Changed 6 years ago by
Added a trivial change for uniformization. Feel free to positive review it.
I will start #16272 now.
Vincent
comment:26 Changed 6 years ago by
Argggggggg... Nononono don't ! I already began !
Nathann
comment:27 followup: ↓ 29 Changed 6 years ago by
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 nonexistence 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
comment:28 Changed 6 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
comment:29 in reply to: ↑ 27 Changed 6 years ago by
Replying to ncohen:
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 nonexistence results ? Is that okay for you ?
Ok. I let you start. I am looking at the literature right now.
comment:30 Changed 6 years ago by
 Commit changed from d051cf4f127aa7c23c0b4a09ca12d4ecaf2caee6 to 35be2feadd00e268b36f835913ec7ec19ad86472
 Status changed from positive_review to needs_review
comment:31 Changed 6 years ago by
 Commit changed from 35be2feadd00e268b36f835913ec7ec19ad86472 to 9e5e94f648113d6b824039651bcb8d98144e01b2
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
9e5e94f  trac #16231: Merged with updated #16227

comment:32 Changed 6 years ago by
 Status changed from needs_review to positive_review
Still updating (and making mistakes in the commit messages)
comment:33 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:34 Changed 6 years ago by
 Branch changed from public/16231 to 9e5e94f648113d6b824039651bcb8d98144e01b2
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #15310: Wilson's construction of Transversal Designs
trac #15310: Rebase on updated #15431
trac #15310: Merged into 6.2.rc0
trac #15310: useless checks
trac #16231: Equivalence between OA/TD/MOLS