#15310: Wilson's construction of Transversal Designs/Orthogonal Arrays/MOLS
-------------------------+-------------------------------------------------
Reporter: | Owner:
ncohen | Status: needs_review
Type: | Milestone: sage-6.2
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
combinatorics | Work issues:
Keywords: | Commit:
Authors: | 62f0158c281c55523a532d5ef21c666ba9c7dc3d
Nathann Cohen | Stopgaps:
Report Upstream: N/A |
Branch: |
u/ncohen/15310 |
Dependencies: |
#15287, #15431 |
-------------------------+-------------------------------------------------
Comment (by vdelecroix):
Hi Nathann,
Brett Stevens is in sabatical in Bordeaux and explains me in full details
the Wilson construction. Good news: I have enough background to starts
seriously the review.
1) There is a much simpler construction than the Wilson one, often called
the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a
TD(k,nt) (this is basically the case u=0 in Wilson construction). We found
that Wilson construction does not apply to a TD(3,6) but the Kronecker
product does! Do you prefer opening a new ticket or including it in this
one?
2) The programming design with TD calling OA is very bad. In OA there is a
nice `EmptySetError` which has an important mathematical meaning. But if
you ask for a transversal design you get instead a `NotImplementedError`
which is much less informative
{{{
sage: designs.orthogonal_array(6,3) # this is great
Traceback (most recent call last)
...
EmptySetError: No Orthogonal Array exists when k>=n+t
sage: designs.transversal_design(6,3) # this is bad
Traceback (most recent call last)
...
NotImplementedError: I don't know how to build this Transversal Design!
}}}
In the ideal world, Sage would only return a design or raise an
`EmptySetError` with a meaningful message mentionning a theorem. And I
learned from Brett that there exist several situations where we know
mathematically that a TD(k,n) does not exist. When `availability=True` it
would be nice to get a troolean: True (means yes), False (means no),
Unknown in `sage.misc.unknown` (means I do not know). And then, you might
change the name `availability` to `existence`.
3) The loop where you test the Wilson construction is 2.86 seconds on my
(dual core) computer. I am not sure it deserves a `# long time`.
4) Could you mention the following reference as a todo
- AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
- TITLE = Making the MOLS table
- BOOKTITLE = Computational and constructive design theory
- SERIES = Math. Appl.
- VOLUME = 368
- PAGES = 67--134
- PUBLISHER = Kluwer Acad. Publ., Dordrecht
- YEAR = 1996
They have a slightly improved Wilson construction for u=1, 2 that requires
less material (ie not four full smaller TDs)... and hence gives more cases
where the construction applies.
Cheers,
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/15310#comment:24>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
