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: 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: 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 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 (#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 ncohen

  • 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 git

  • Commit set to a46446f3b29690aa1245583639bb6b78b3d50dca

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

03f896ctrac #15310: Wilson's construction of Transversal Designs
6357236trac #15310: Rebase on updated #15431
25f5959trac #15310: Merged into 6.2.rc0
f23fa88trac #15310: useless checks
a46446ftrac #16231: Equivalence between OA/TD/MOLS

comment:3 follow-up: Changed 6 years ago by vdelecroix

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 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

comment:4 in reply to: ↑ 3 Changed 6 years ago by ncohen

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:

  • individual constructions (currently there is TD_6_12 and also the ones introduced in #16241 #16236 and #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

comment:5 Changed 6 years ago by git

  • Commit changed from a46446f3b29690aa1245583639bb6b78b3d50dca to a9dce705211f5593b926c0512a40ada05d978ff3

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

62f0158trac #15310: cutting some branches of the exploration
d743414trac #15310: reviewer's remarks
3fc79batrac #15310: Merged into 6.2.rc1
054d2a2trac #16227: Product construction of Transversal Designs
a512ab1trac #16227: Merged with updated #15310
e62fae8corrected doctests + new doctests
4d6e964trac #16227: Replace exception with booleans in the doctests
a9dce70trac #16231: Merged with updated #16227

comment:6 follow-up: Changed 6 years ago by vdelecroix

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 ncohen

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

comment:8 follow-up: Changed 6 years ago by 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 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

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

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 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

comment:10 in reply to: ↑ 9 ; follow-up: Changed 6 years ago by 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 ?

Nathann

comment:11 in reply to: ↑ 10 ; follow-up: Changed 6 years ago by vdelecroix

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 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...

comment:12 in reply to: ↑ 11 Changed 6 years ago by ncohen

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

comment:13 Changed 6 years ago by ncohen

  • 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 ncohen

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

comment:15 follow-up: Changed 6 years ago by vdelecroix

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 ncohen

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 ncohen

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 git

  • Commit changed from a9dce705211f5593b926c0512a40ada05d978ff3 to 8257178acf8691b62a4092538bcaed47e73b3953

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

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

comment:19 Changed 6 years ago by vdelecroix

Hi Nathann,

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

comment:20 Changed 6 years ago by ncohen

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 vdelecroix

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 ncohen

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 ncohen

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 git

  • Commit changed from 8257178acf8691b62a4092538bcaed47e73b3953 to d051cf4f127aa7c23c0b4a09ca12d4ecaf2caee6

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

d051cf4ValueError -> EmptySetError in latin_squares

comment:25 Changed 6 years ago by vdelecroix

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 ncohen

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

Nathann

comment:27 follow-up: Changed 6 years ago by 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 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

Last edited 6 years ago by ncohen (previous) (diff)

comment:28 Changed 6 years ago by ncohen

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

comment:29 in reply to: ↑ 27 Changed 6 years ago by vdelecroix

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 non-existence 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 git

  • Commit changed from d051cf4f127aa7c23c0b4a09ca12d4ecaf2caee6 to 35be2feadd00e268b36f835913ec7ec19ad86472
  • 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
35be2fetrac #16231: Merged with updated #16277

comment:31 Changed 6 years ago by git

  • Commit changed from 35be2feadd00e268b36f835913ec7ec19ad86472 to 9e5e94f648113d6b824039651bcb8d98144e01b2

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

9e5e94ftrac #16231: Merged with updated #16227

comment:32 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

Still updating (and making mistakes in the commit messages)

comment:33 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:34 Changed 6 years ago by vbraun

  • Branch changed from public/16231 to 9e5e94f648113d6b824039651bcb8d98144e01b2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.