#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 ncohen):
Yo !
> 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.
Ahahaha. Well you must have more background that I have then, I am jealous
`:-P`
> 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?
I would say open a new ticket because this ticket does not only implement
Wilson's construction, it also adds some "availability" flags to
constructors and thus this ticket is a dependency for several others.
Hence if we implement it in another ticket the other ones can be reviewed
in the meantime.
I also got word from Julian Abel that the Wilson Decomposition I
implemented was not the best one, and that some variants may be useful. I
copy/paste what he told me here (he probably will not mind)
{{{
I note from your list of known MOLS that you've used Wilson's theorem
with 1 truncated group, but not more. The next most important variants
are
where there are (1) 2 truncated groups (2) 1 spike block or 1 truncated
group and a spike. These variants are as follows:
Theorem 1: If there are k+2 MOLS(t), and k MOLS(s) for s=g, g+1, g+2,
u_1, u_2, where 0 \leq u_1, u_2 \leq t, then there are k MOLS(gt + u_1 +
u_2).
Theorem 2: If there are k+x MOLS(t), and k MOLS(s) for s=g, g+1, g+x,
g+x, where 0 \leq u_1, u_2 \leq t, x> 0 then there are k MOLS(gt +
x).
Theorem 3: If there are k+x+1 MOLS(t), and k MOLS(s) for s=g, g+1, g+2,
g+x, u_1, where 0 \ leq u_1 \leq t, x > 0, then there are k MOLS(gt + x
+ u_1).
For instance, Th. 1 gives 6 MOLS for v=106 = 7. 13 + 7 + 8. Theorem 2
gives 7 MOLS(v) for v=155 = 8.19 + 3. And Theorem 3 gives 6 MOLS(v) for
v=148= 7.19 + 6 + 9.
}}}
He also pointed me toward references where I can read those constructions,
but I have not begun this step yet and he told me it would be hard to
read. Still, it has to be done.
> 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
How is that a result of TD calling OA ?
> 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).
Well. No problem if "if Unknown" is equivalent to "if False".
> And then, you might change the name `availability` to `existence`.
Could we do that on top of #12267 ? I would prefer those patches to be
merged like that, and then we can update stuff. Otherwise it means fixing
many conflicts with the stuff above, but I agree that it is a good idea.
> 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`.
Well, I usually set `#long ` even for 2 seconds. Most tests are faster
than that, andyou can have many "2 seconds" tests. I don't mind
adding/removing flags like that, but you can also add a commit if you
like.
> 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.
okayokay, good idea ! I will add a commit in a second.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15310#comment:25>
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.
