q-x construction of Orthogonal Arrays

[nathanncohen]

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

Depends on #16500

CC: @videlec

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 8da2c73

Reviewer: Vincent Delecroix

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

[nathanncohen]

Branch: u/ncohen/16503

[nathanncohen]

Dependencies: #16500

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

[sagetrac-git]

Commit: 9128bad

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

[sagetrac-git]

Changed commit from 9128bad to 6087843

[nathanncohen]

comment:4

Updated on top of #16500 !

Nathann

[sagetrac-git]

Changed commit from 6087843 to 71dad5d

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

[videlec]

comment:6

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

[nathanncohen]

comment:7

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

[sagetrac-git]

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

91eb3d2

trac #16503: Review

[sagetrac-git]

Changed commit from 71dad5d to 91eb3d2

[videlec]

comment:9

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

[nathanncohen]

comment:11

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

Nathann

[videlec]

comment:12

Replying to @nathanncohen:

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

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:13

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

-    REFERENCES::
+    REFERENCES:

[sagetrac-git]

Changed commit from 91eb3d2 to 8da2c73

[sagetrac-git]

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

8da2c73

trac #16503: Broken doc

[videlec]

comment:16

... building the doc...

[vbraun]

Changed branch from u/ncohen/16503 to 8da2c73