q-x construction of Orthogonal Arrays

[ncohen]

Another construction of orthogonal arrays. New OA for n=158, 329, 334, 355, 517, 574, 745, 979, 1926.

Thanks to Julian R. Abel's pointers, as usual :-)

Nathann

[git]

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

​004833a	trac #16347: Wilson's construction with two truncated groups
​f5069f0	trac #16347: Merged with 6.3.beta4
​f182d36	trac #16499: Cheap speedup in the OA recursive constructions
​70f7046	trac #16500: New recursive constructions of Orthogonal Arrays
​9128bad	trac #16503: q-x construction of Orthogonal Arrays

[git]

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

​828ff22	trac #16437: cut the branches in W. dec. with two trunc. blocks
​8ebd21b	trac #16347: use is_sum_of_squares_pyx instead of two_squares
​0175134	trac #16347: doc + simplifications
​9ff5062	trac #16423: Table of MOLS from the handbook and comparison with Sage
​e64be98	trac #16423: tiny code improvement and alignment
​e948cf6	trac #16423: Aligning the alignment
​0a7d853	trac #16423: Broken doctests
​b329351	trac #16499: Cheap speedup in the OA recursive constructions
​a67c04f	trac #16500: New recursive constructions of Orthogonal Arrays
​6087843	trac #16503: q-x construction of Orthogonal Arrays

[ncohen]

Updated on top of #16500 !

Nathann

[git]

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

​41c50d5	trac #16500: Simplified find_recursive_construction
​e1992ce	trac #16500: doc + speedup
​697dd0c	trac #16500: Typoes in the doc
​71dad5d	trac #16503: q-x construction of Orthogonal Arrays

[vdelecroix]

Hi Nathann,

1) One lines 656-659 you have an import followed by a commented check!!

from sage.combinat.designs.bibd import _check_pbd
PBD = [[relabel[xx] for xx in B if not xx in points_to_delete] for B in TD]

# _check_pbd(PBD,n,[q,q-x-1,q-x+1,x+2])

why is that?

2) This is wrong (lines 730-731)

# The next is always True, because q is a prime power
# orthogonal_array(k+1,q,existence=True) and

if k+1 > q... instead we can start the loop at k+1 instead of 3.

3) I bounced into something bad: I wanted to change in find_recursive_construction the

assert k >= 3

into a

assert k > 3, "you do not need recursion for k<4"

since it is trivial to build one latin square. But it appears that the recursive constructions is called with k=3 many times! so bad! This has to be corrected... but hopefully, not here. I guess that #16535 would be the good place.

Vincent

[ncohen]

Hello !

1) One lines 656-659 you have an import followed by a commented check!!

from sage.combinat.designs.bibd import _check_pbd
PBD = [[relabel[xx] for xx in B if not xx in points_to_delete] for B in TD]

# _check_pbd(PBD,n,[q,q-x-1,q-x+1,x+2])

why is that?

It is something I used while implementing the construction and as it said something about the PBD I left it. I updated that comment as that troubled you.

2) This is wrong (lines 730-731)

# The next is always True, because q is a prime power
# orthogonal_array(k+1,q,existence=True) and

The line before that one is

            orthogonal_array(k+1,q-x+1,existence=True) and

3) I bounced into something bad: I wanted to change in find_recursive_construction the

assert k >= 3

into a

assert k > 3, "you do not need recursion for k<4"

since it is trivial to build one latin square. But it appears that the recursive constructions is called with k=3 many times! so bad! This has to be corrected... but hopefully, not here. I guess that #16535 would be the good place.

Why in #16535 ? What we need to do is add a case for k=3 in the orthogonal_array constructor.

I fixed the things above, plus an apparently incorrect 1<x.

Nathann

[git]

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

​91eb3d2

trac #16503: Review

[vdelecroix]

Hi Nathann,

You can actually cut the loop if x >= q as x is increasing along the loop. It is done at public/16503 (it does not matter too much right now, but it will if you want to compute a big MOLS table).

Beyond that, you can set to positive review.

Vincent

[ncohen]

HMmmmm... I don't like much to differentiate over integer divisions.. Do you mind if we keep it like that ?

Nathann

[vdelecroix]

Replying to ncohen:

HMmmmm... I don't like much to differentiate over integer divisions.. Do you mind if we keep it like that ?

Me neither, but the floor function is increasing... so it is fine (as the composition of increasing functions is increasing)! But we can keep it as it is, since we cut very little with that: (q^2-n)/(q-2) ~ q + cte for large q.

Vincent

[vdelecroix]

As reported in #16524 there is a problem building the doc. Solution (line 622)

-    REFERENCES::
+    REFERENCES:

[git]

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

​8da2c73

trac #16503: Broken doc

[vdelecroix]

... building the doc...