OA(7,66), OA(7,68), OA(8,69), OA(7,74) and OA(8,76)

[nathanncohen]

New designs, and a new "TD from PBD" construction ! Too bad this construction cannot be called automatically (yet) :-P

Nathann

Depends on #16461
Depends on #16388

CC: @videlec @KPanComputes @dimpase @brettpim

Component: combinatorial designs

Author: Nathann Cohen

Branch/Commit: 5d4607a

Reviewer: Vincent Delecroix

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

[nathanncohen]

Branch: u/ncohen/16361

[nathanncohen]

Author: Nathann Cohen

[sagetrac-git]

Commit: 20ef216

[sagetrac-git]

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

973b926	trac #16236: Merged with #16272
37681e2	trac #16295 : Faster is_orthogonal_array
994324e	trac #16295: Doctests and review
fc6de73	trac #16295: Merged with 6.3.beta1
b9f8b03	trac #16295: bugfix in wilson's construction
f969003	trac #16356: MOLS for n=18,57,154,276,298,342
20ef216	trac #16361: OA(7,66), OA(7,68), OA(8,69), OA(7,74) and OA(8,76)

[videlec]

comment:5

Hi Nathann,

The function OA_from_PBD is sensitive to the output of orthogonal_array. More precisely, the function needs a TD(k,i) - i TD(k,1). But right now, it is just a matter of luck whether the answer of orthogonal_array(k,i) actually is... and tomorrow the answer might change. So you could not rely on that. For the current purpose of the ticket, a fix would be to feed explicitly the function OA_from_PBD with the corresponding list of TD(k,i) - i TD(k,1).

Vincent

[nathanncohen]

comment:6

Hellooooooooo !!

The function OA_from_PBD is sensitive to the output of orthogonal_array.

Indeed. And sensitive to the labelling of the design, which I guess is what bothers you.

More precisely, the function needs a TD(k,i) - i TD(k,1). But right now, it is just a matter of luck whether the answer of orthogonal_array(k,i) actually is... and tomorrow the answer might change. So you could not rely on that. For the current purpose of the ticket, a fix would be to feed explicitly the function OA_from_PBD with the corresponding list of TD(k,i) - i TD(k,1).

First, it is not true that "this can change and that I cannot rely on that" because there is a doctest. So if the constructions for which we need OA_from_PBD work now, they will continue working for as long as the doctest is there.

Secondly, you are right that the least we can do is solve this problem "up to relabelling" of the original design. This is what is being done in #16391 (it depends on #16370), which also implements another technique to find TD(k,n)-x.TD(k,1). This patch #16391 is also a dependency of #16347 (wilson's construction), and the patch on which we talk right now is also a dependency of #16347 (wilson's construction). You can see that in Wilson's construction the lines that are a problem to you have been changed and that the function OA_with_holes is called instead.

+    # Building the OA
+    OAs ={i:list(OA_with_holes(k,i,i)) for i in K}
+
+    # Turning them into IMOLS
+    for i,OA in OAs.items():
+        for ii in range(i):
+            OAs[i].remove((ii,)*k)

Sooooooooooo given that

1. the current construction will work for as long as they are doctested
2. What bothers you is already fix a bit above

ittttttt would be cool if you could consider that this problem does not matter as it is already fixed above. It just comes from the fact that I write all my code in the same file but that I try to split it into small bits that are easier to review... And in this case I probably removed the call to OA_with_PBD so that this patch could be reviewed without the "Helper functions" patch as a dependency.

Nathann

[videlec]

comment:8

EDIT: post removed

[videlec]

comment:9

Hello,

incomplete_orthogonal_array:

• Under the condition x <= 3 and n > k-1 and k >= 3 it should return orthogonal_array(k,n,existence=True) and not True.

• If k=n+1 then we have a projective planes and all blocks intersect... so there is no OA(n+1,n) - 2.OA(n+1,1). I added the appropriate test in incomplete_orthogonal_array.

OA_from_PBD:

• it makes more sense to use the function incomplete_orthogonal_array since it is here!!

• I changed the end of the if/elif to forward the non-existence (and also avoid doctest error because of Specify the values of k,n in the exceptions #16388)

• I changed the doctest (which was just a copy of the one in database.py!!) to be something non-trivial

see the changes on the branch public/16361 (where #16461 is merged). I was able to build the doc and all test pass...

Do you have further remarks? Otherwise it deserves a positive review.

Vincent

[nathanncohen]

comment:10

Hello !

incomplete_orthogonal_array:

• Under the condition x <= 3 and n > k-1 and k >= 3 it should return orthogonal_array(k,n,existence=True) and not True.

+1

• If k=n+1 then we have a projective planes and all blocks intersect... so there is no OA(n+1,n) - 2.OA(n+1,1). I added the appropriate test in incomplete_orthogonal_array.

See [1]

OA_from_PBD:

• it makes more sense to use the function incomplete_orthogonal_array since it is here!!

+1

• I changed the end of the if/elif to forward the non-existence (and also avoid doctest error because of Specify the values of k,n in the exceptions #16388)

See below

• I changed the doctest (which was just a copy of the one in database.py!!) to be something non-trivial

+1

see the changes on the branch public/16361 (where #16461 is merged). I was able to build the doc and all test pass...

Do you have further remarks? Otherwise it deserves a positive review.

Well... Actually, I think that you should not intercept all exceptions in order to return specific error messages... I believe that you should let the subfunction raise its own exception. That's going too far I think :-/

If the user requests a construction that requires other construction, let the other constructions raise an exception ! The user will see a message like "Impossible to build a OA(....)", meaning that the function needed one and it did not exist.

+    for i in K:
+        if incomplete_orthogonal_array(k,i,(1,)*i,existence=True) is False:
+            raise EmptySetError("The construction is impossible since there is no OA({},{})-{}.OA({},1)".format(k,i,i,k))
+        elif incomplete_orthogonal_array(k,i,(1,)*i,existence=True) is Unknown:
+            raise NotImplementedError("I was not able to build an OA({},{})-{}.OA({},1)".format(k,i,i,k))
+        else:
+            OAs[i] = incomplete_orthogonal_array(k,i,(1,)*i)

In the first two situations, you return manually the exception that should be raised by incomplete_orthogonal_array. Why do it again manually ? Why not just call it ?

Same here

+    elif orthogonal_array(k,n,existence=existence) is False:
+        if existence:
+            return False
+        raise EmptySetError("There is no OA({},{}) and hence no OA({},{})-{}.OA({},1)".format(k,n,k,n,k))
+
+    elif orthogonal_array(k,n,existence=existence) is Unknown:
+        if existence:
+            return Unknown
+        raise NotImplementedError("I do not know how to build this OA({},{})-{}.OA({},1)".format(k,n,k))
+
     else:
-        return orthogonal_array(k,n,existence=existence)
+        raise RuntimeError("This should not happen!")

The line you removed was doing the very same job, i.e. forwarding the non-existence results ! All you did was rewrite the exception, and the user sees :

"There is no OA(k,n) and this no OA(k,n)-xOA(k,1)"

instead of

"There is no OA(k,n)"

I believe that you should let the subfunction raise its exception. What do you think ?

Nathann

[videlec]

comment:11

Replying to @nathanncohen:

Hello !

incomplete_orthogonal_array:

• If k=n+1 then we have a projective planes and all blocks intersect... so there is no OA(n+1,n) - 2.OA(n+1,1). I added the appropriate test in incomplete_orthogonal_array.

See [1]

What is [1]?

OA_from_PBD:

• I changed the end of the if/elif to forward the non-existence (and also avoid doctest error because of Specify the values of k,n in the exceptions #16388)

See below

see the changes on the branch public/16361 (where #16461 is merged). I was able to build the doc and all test pass...

Do you have further remarks? Otherwise it deserves a positive review.

Well... Actually, I think that you should not intercept all exceptions in order to return specific error messages... I believe that you should let the subfunction raise its own exception. That's going too far I think :-/

I believe that you should let the subfunction raise its exception. What do you think ?

All right, but then you should put #16388 as a dependency and adapt the doctests...

Vincent

[sagetrac-git]

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

4007157	trac #16361: merge with #16461
191aaab	trac #16361: fix bug in IOA + better OA_from_PBD
0380ead	trac #16461: fix documentation
8704b9c	trac #16361: merge updated #16461
767e091	trac #16388: Specify the values of k,n in the exceptions
a460169	merge Sage version 6.3.beta3
c365a39	trac #16388: use format for OA + specify (k,n) for BIBD
ec26ca2	trac #16388: a missing one in BIBD_from_TD
79178b6	trac #16388: (v,k,1)-BIBD instead of BIBD(v,k,1)
02ecf51	trac #16361: Merged with #16388

[sagetrac-git]

Changed commit from 20ef216 to 02ecf51

[sagetrac-git]

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

5d4607a

trac #16361: Don't re-raise the exceptions

[sagetrac-git]

Changed commit from 02ecf51 to 5d4607a

[nathanncohen]

comment:14

Here it is !

Nathann

[videlec]

comment:15

Hi,

Looks good to me. All test pass and documentation builds!

Do you know if there is an OA(n,n) for some n which is not a prime power? (it is not in Sage).

Vincent

[nathanncohen]

comment:16

Yo !

Looks good to me. All test pass and documentation builds!

I hope that Volker will merge it soon... I had not noticed that some tickets had been closed already in an unreleased beta :-/

Do you know if there is an OA(n,n) for some n which is not a prime power? (it is not in Sage).

HMmmm.... No idea, but there is a partial answer as Theorem III.3.32 in the handbook. Looks like we will call "is_sum_of_squares" again :-P

Nathann

[nathanncohen]

Changed dependencies from #16356 to #16461, #16388

[vbraun]

comment:18

Reviewer name

Whats up with the TODO?

[nathanncohen]

comment:19

Whats up with the TODO?

Sorry, it was a "note to self". I did that when I rebased everything above.

Nathann

[nathanncohen]

Reviewer: Vincent Delecroix

[vbraun]

Changed branch from u/ncohen/16361 to 5d4607a