redesign transversal designs

[videlec]

The tickets #15310 and #16227 introduce a nice availability keywords to the function transversal_design. With availability=True the return value is the answer to the question "Does Sage know how to build a TD(k,n)"? Using Unknown from sage.misc.unknown we can turn the question into "Do we know mathematically that a TD(k,n) exist?" whose answer would be:

• True if Sage knows how to do it
• Unknwon if neither Sage nor mathematics can help
• False if we know mathematically that such construction does not exist

As the semantic changes, we will also turn the keyword availability into existence (or maybe have both).

In the same ticket, we will include some of the known non existence of transversal designs:

• The Bruck Ryser Chowla Theorm gives the non-existence of many TD(n+1,n)
• C. Lam in Lam, "The Search for a Finite Projective Plane of Order 10" (1991) proved that TD(11,10) cannot exist

And we might see later

• there is some work (?) that shows that if $k$ is large enough then the existence of TD(k,n) implies the existence of TD(n+1,n) and so the non-existence results can percolate downwards in k

Depends on #16231

CC: @nathanncohen @brettpim

Component: combinatorics

Keywords: designs, orthogona arrays

Author: Nathann Cohen, Vincent Delecroix

Branch/Commit: e2749b3

Reviewer: Nathann Cohen, Vincent Delecroix

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

[videlec]

Dependencies: #15310, #16227

[brettpim]

comment:4

In case "Unkown" did you mean that Sage does not know how to do it (as currently implemented) but possibly Mathematics knows the answer? "Unknown" should ideally mean that mathematics does not know the answer but Sage development is likely to lag behind mathematics and I don't want users to think that if Sage does not know the answer that this implies that mathematics does not know the answer. I think this is all what you meant but the word "nor" confused me.

The Bruck-Ryser-Chowla Theorem (from Theorem 2.13 in Stinson's Book) shows that if $n \equiv 1,2 \bmod 4$
and there exists a prime $p \equiv 3 \bmod 4$ such that the largest power of $p$ that divides $n$ is odd. Then a TD$(n+1,n)$ does not exist.

A reference for the non existence of TD$(11,10)$ is

@article {MR1018454,
    AUTHOR = {Lam, C. W. H. and Thiel, L. and Swiercz, S.},
     TITLE = {The nonexistence of finite projective planes of order {$10$}},
   JOURNAL = {Canad. J. Math.},
  FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de Math\'ematiques},
    VOLUME = {41},
      YEAR = {1989},
    NUMBER = {6},
     PAGES = {1117--1123},
      ISSN = {0008-414X},
     CODEN = {CJMAAB},
   MRCLASS = {51E15 (51-04)},
  MRNUMBER = {1018454 (90j:51008)},
MRREVIEWER = {J. C. Fisher},
       DOI = {10.4153/CJM-1989-049-4},
}

For the results I mentioned about sufficiently high $k$ implying TD$(n+1,n)$ exists, I will have to dig up the papers by Metz and review them to remember exactly how this works.

[brettpim]

comment:5

Why did that BibTeX reference format so badly?

[nathanncohen]

comment:6

Yo !

In case "Unkown" did you mean that Sage does not know how to do it (as currently implemented) but possibly Mathematics knows the answer?

The parameter will be called "existence". When you type designs.transversal_design(k,n,existence=True)

it will answer

1. True meaning "Sage can build it"
2. Unknown meaning "Sage can't build it, but it may exist"
3. False meaning "it does not exist"

Thus there is nothing there to mean "Mathematics knows it exists but Sage does not know how to build it". THouuuuuuugh if you know of something like that, the only responsible way to solve the problem is to implement the mathematical result :-P

"Unknown" should ideally mean that mathematics does not know the answer but Sage development is likely to lag behind mathematics and I don't want users to think that if Sage does not know the answer that this implies that mathematics does not know the answer. I think this is all what you meant but the word "nor" confused me.

Well, the word "unknown" means "Sage has no idea" ^^;

For the results I mentioned about sufficiently high $k$ implying TD$(n+1,n)$ exists, I will have to dig up the papers by Metz and review them to remember exactly how this works.

Okayyyyyyyyy !

Why did that BibTeX reference format so badly?

Because some characters that you used are interpreted as typographic instructions. Wrap what you want to say with {{{ and }}} to avoid that. I edited your comment above, so it looks fine now ;-)

Nathann

[brettpim]

comment:7

Replying to @nathanncohen:

Yo !

In case "Unkown" did you mean that Sage does not know how to do it (as currently implemented) but possibly Mathematics knows the answer?

The parameter will be called "existence". When you type designs.transversal_design(k,n,existence=True)

it will answer

1. True meaning "Sage can build it"
2. Unknown meaning "Sage can't build it, but it may exist"
3. False meaning "it does not exist"

Perfect, this is what I thought, but "nor" threw me off

Why did that BibTeX reference format so badly?

Because some characters that you used are interpreted as typographic instructions. Wrap what you want to say with {{{ and }}} to avoid that. I edited your comment above, so it looks fine now ;-)

thanks

You put it in some kind of box, a "code block"?

[nathanncohen]

comment:8

You put it in some kind of box, a "code block"?

Yep !

[nathanncohen]

Branch: public/16272

[nathanncohen]

comment:9

Here it is ! I implemented the same thing so many times that even I am trying to see that unifying it all may help... :-P

Nathann

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

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
a46446f	trac #16231: Equivalence between OA/TD/MOLS
a9dce70	trac #16231: Merged with updated #16227
8d8b928	more documentation to orthogonal_arrays.py
8257178	remove MOLS construction for prime powers + doc
d678326	trac #16272: Replacing availability by existence and forwarding the results between design constructors

[sagetrac-git]

Commit: d678326

[videlec]

comment:12

Hi,

I would like to have a verbose or message option:

sage: designs.transversal_design(7,6,existence=True)
False
sage: designs.transversal_design(7,6,existence=True,message=True)
(False, "By the Bruck-Ryser-Chowla theorem, no projective plane of order 6 exists")

But it looks like we are implementing ourself the propagation of errors... What do you think?

Vincent

[nathanncohen]

comment:13

Yo !

But it looks like we are implementing ourself the propagation of errors... What do you think?

HMmm... Well, to me this is similar to the "construction path" feature. You know, the feature to tell you how to prove formally that a design exists with theorems ? There you want a "formal proof" that it cannot be done.

The thing is that right now we have no recursive proof of non-existence... But I still believe that it is too early to implement stuff like that.

Nathann

[videlec]

comment:15

Hello,

Here it comes!

Ok. I mainly did two things

• implement my own projective_space_as_OA inside orthogonal_arrays.py. This might sound weird but the current implementation of ProjectiveSpaceDesign is slow and scarry me (I plan to clean it soon in a ticket).
• implement a beautiful TD_existence (I do not like the name, so I aks for suggestions here):

sage: from sage.combinat.designs.orthogonal_arrays import TD_existence
sage: TD_existence(6)
TD(k,6)
 exist            for k in [ 2, 3]
 unknown to exist for k in [ 4, 6]
 not exist        for k in [ 7,+infini]

I also correct some of the errors raised to get mainly EmptySetError and NotImplementedError.

Vincent

[sagetrac-git]

Changed commit from d678326 to ba058dd

[sagetrac-git]

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

8403829	16272: more functionalities
ba058dd	more doctests

[videlec]

comment:17

As I do not have the reference for the third point mentioned in the ticket, I did not do it...

Vincent

[nathanncohen]

comment:19

Yo !

• implement my own projective_space_as_OA inside orthogonal_arrays.py. This might sound weird but the current implementation of ProjectiveSpaceDesign is slow and scarry me (I plan to clean it soon in a ticket).

THis thing has NOTHING to do here. Use the current ProjectivePlaneDesigns, and write another ticket to change the code if you don't like it. I agree that it is slow, but implementing the function TWICE (one that is slow, one that is hidden in an unrelated module) is not a way to solve it.

• implement a beautiful TD_existence (I do not like the name, so I aks for suggestions here):

Beautiful ? Is that a joke ? A function that PRINTS text ?

Get this thing out of here until a proper interface design is found. A function like that should RETURN values, not print stuff. Plus we have almost no negative result to advertise for the moment. Plus how the hell is an user going to find that ? We write Sage code here, not our own scripts !!!

If such a function is to ever be implemented, it will return a pair "lower bound, upper bound". The only interesting data in your three lines are TWO NUMBERS, and wrapping them in intervals for nothing, adding a 2 there and an infinity there looks fancy, but once more we work on a library here, not on your own code.

I also correct some of the errors raised to get mainly EmptySetError and NotImplementedError.

I will look at that when the problems above are solved....

Nathann

[nathanncohen]

comment:20

By the way... When we will have merged all constructions, there is a doctest that I would like to include in the doc, and it may partly do what you built this "TD_existence" thing for.

This is the table that I am trying to copy :
http://books.google.fr/books?id=S9FA9rq1BgoC&lpg=PA175&ots=Do3xYTkMox&dq=%22mols%22%20of%20side%20%3C%2010000&pg=PA176#v=onepage&q=%22mols%22%20of%20side%20%3C%2010000&f=false

It is somehow "the reference". It gives you the maximum number of MOLS that are known to exist for a given order.

aaaaaaaand I have had the following code for a while to see where I was going:

print "      ",
for i in range(20):
    print str(i)+" "*(4-len(str(i))),
print ""
print " "*4+"_"*20*5+"__"

for i in range(20*10):
    if i%20==0:
        print ""
        print str(i)+" "*(4-len(str(i)))+"| ",
    if i < 2:
        k = 1
    else:
        for k in range(i+1):
            if not designs.mutually_orthogonal_latin_squares(i,k,availability=True):
                break
    k = str(k-1)
    print k+" "*(4-len(k)),

This function is not meant to be called by users of course, I thought I would just make it a private function and call it just once, in a "# long" doctest. Here is what it produces, with #16241 (and all its dependencies) applied.

       0    1    2    3    4    5    6    7    8    9    10   11   12   13   14   15   16   17   18   19   
    ______________________________________________________________________________________________________

0   |  0    0    1    2    3    4    1    6    7    8    2    10   4    12   4    4    15   16   3    18   
20  |  4    5    3    22   7    24   4    26   5    28   4    30   31   5    4    5    8    36   4    5    
40  |  7    40   5    42   5    6    4    46   8    48   6    5    5    52   5    6    7    3    2    58   
60  |  5    60   5    6    63   4    2    66   4    4    6    70   7    72   3    7    3    6    3    78   
80  |  9    80   8    82   6    6    6    3    7    88   3    6    3    4    3    6    7    96   6    8    
100 |  8    100  6    102  7    4    4    106  4    108  4    6    7    112  3    7    4    8    3    6  

It will be a nice way to advertise what Sage can do for TD/OA/MOLS :-P

Nathann

[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
d34b012	trac #16272: Merged with updated #16227

[sagetrac-git]

Changed commit from 47798d2 to d34b012

[nathanncohen]

comment:58

Still merging ...

Nathann

[vbraun]

comment:60

Merge conflict

[sagetrac-git]

Changed commit from d34b012 to c127a6d

[sagetrac-git]

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

d051cf4	ValueError -> EmptySetError in latin_squares
9e5e94f	trac #16231: Merged with updated #16227
c127a6d	trac #16272: Merged with updated #16231

[nathanncohen]

Changed dependencies from #15310, #16227, #16281 to #16231

[sagetrac-git]

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

e2749b3

trac #16272: Merged with 6.3.beta0

[sagetrac-git]

Changed commit from c127a6d to e2749b3

[vbraun]

Changed branch from public/16272 to e2749b3