Opened 5 years ago

Closed 4 years ago

#16604 closed enhancement (fixed)

new OA for n=112,160,176,208,224,352,416,514,544,640,796,896

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.4
Component: combinatorial designs Keywords:
Cc: vdelecroix Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 24c4f7f (Commits) Commit: 24c4f7fc4cf619fca8cceb5707b74b935de880c2
Dependencies: #16582,#16797 Stopgaps:

Description

As the title says.

Because this method also needs to shorten a matrix in the middle of OA_from_Vmt, it is split into QDM_from_Vmt and OA_from_quasi_difference_matrix (which was already called).

Nathann

Change History (59)

comment:1 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16604
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 00654fb8dbffe2134dc0b55ead5cea52dadf1654

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

01689fdtrac #16582: MOLS: Table with n<600 and updated syntax
0c08a79trac #16582: Merged with beta5
00654fbtrac #16604: new OA for n=112,160,224,514,796

comment:3 follow-up: Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Hey Nathann,

In OA_14_124, it is not safe to ask for a finite field of size 25 and hope that, by chance, its generator satisfies w^5 + w^2 + 1 = 0. You would rather give the constructor an explicit polynomial:

sage: R = PolynomialRing(GF(2),'x')
sage: x = R.gen()
sage: GF(2**5, 'w', modulus=x**5+x**2+1)
Finite Field in w of size 2^5

and I got a docbuild error

OSError: [combinat ] None:5: WARNING: citation not found: BvR514

Vincent

comment:4 in reply to: ↑ 3 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review
  • Summary changed from new OA for n=112,160,224,514,796 to new OA for n=112,160,224,514,640,796

Yo !

In OA_14_124, it is not safe to ask for a finite field of size 25 and hope that, by chance, its generator satisfies w^5 + w^2 + 1 = 0.

Yeah... And "by chance" it always works ?

Given that you are the one to complain about this, I will use the first's trick against you : conway=True :-P

and I got a docbuild error

OSError: [combinat ] None:5: WARNING: citation not found: BvR514

Ahahahah. I must have replaced 82 with 514 at some point :-D

I had also "made a small mistake" in the implementation. I had forgotten to set some flag from "False" to "True", which means that the new OA have a longer width. I didn't like to notice that I had implemented so many new OA and that they did not even reach the Handbook's bound.... Now all is good :-P

I also added an OA for 640, freshly debugged.

Nathann

comment:5 Changed 5 years ago by git

  • Commit changed from 00654fb8dbffe2134dc0b55ead5cea52dadf1654 to ee7ac60c2dbd59374d95bb86b66587c6a6e47321

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

ee7ac60trac #16604: OA for n=640, reviewer's remarks and silly mistake

comment:6 Changed 5 years ago by git

  • Commit changed from ee7ac60c2dbd59374d95bb86b66587c6a6e47321 to ba6609df5508dd25035203e9e53ce9e4d1ca1ee7

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

ba6609dtrac #16604: OA for n=640, reviewer's remarks and silly mistake

comment:7 Changed 5 years ago by ncohen

(I had forgotten a "Found by Julian R. Abel" line)

Nathann

comment:8 Changed 5 years ago by ncohen

  • Summary changed from new OA for n=112,160,224,514,640,796 to new OA for n=112,160,224,514,640,796,896

added a OA(15,896).

comment:9 Changed 5 years ago by git

  • Commit changed from ba6609df5508dd25035203e9e53ce9e4d1ca1ee7 to c218148c1f076c08ad5a448754421e82c78b5509

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

c218148trac #16604: OA(15,896)

comment:10 Changed 5 years ago by git

  • Commit changed from c218148c1f076c08ad5a448754421e82c78b5509 to 03c2ca3a0668b773ecf79c4c222fc802040053dd

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

03c2ca3trac #16604: OA(16,208)

comment:11 Changed 5 years ago by ncohen

  • Summary changed from new OA for n=112,160,224,514,640,796,896 to new OA for n=112,160,208,224,514,640,796,896

comment:12 Changed 5 years ago by git

  • Commit changed from 03c2ca3a0668b773ecf79c4c222fc802040053dd to 6074f4b7fcfcbb18b60726954adfa78e68716384

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

6074f4btrac #16604: OA(16,208)

comment:13 Changed 5 years ago by ncohen

  • Summary changed from new OA for n=112,160,208,224,514,640,796,896 to new OA for n=112,160,176,208,224,514,640,796,896

comment:14 Changed 5 years ago by git

  • Commit changed from 6074f4b7fcfcbb18b60726954adfa78e68716384 to 35cbadc1fe6d60fe52b86ec19a6ad337ddb201d2

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

35cbadctrac #16604: OA(16,176)

comment:15 Changed 5 years ago by git

  • Commit changed from 35cbadc1fe6d60fe52b86ec19a6ad337ddb201d2 to bfcc6f5e263fa92bf04424dfabe825314c6b225d

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

bfcc6f5trac #16604: Now without copy and paste

comment:16 Changed 5 years ago by git

  • Commit changed from bfcc6f5e263fa92bf04424dfabe825314c6b225d to 226599fa239e84272d441e0bc29e4b9a2fbdf8f1

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

226599ftrac #16604: OA(20,352)

comment:17 Changed 5 years ago by git

  • Commit changed from 226599fa239e84272d441e0bc29e4b9a2fbdf8f1 to 326ece4053b973beef506e427f5bc29846cfa8ed

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

326ece4trac #16604: OA(20,352)

comment:18 Changed 5 years ago by ncohen

  • Summary changed from new OA for n=112,160,176,208,224,514,640,796,896 to new OA for n=112,160,176,208,224,352,514,640,796,896

comment:19 Changed 5 years ago by git

  • Commit changed from 326ece4053b973beef506e427f5bc29846cfa8ed to a6212204674050c40fca7a7c41d4f25c6c2c066c

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

a621220trac #16604: OA(20,416)

comment:20 Changed 5 years ago by ncohen

  • Summary changed from new OA for n=112,160,176,208,224,352,514,640,796,896 to new OA for n=112,160,176,208,224,352,416,514,640,796,896

comment:21 Changed 5 years ago by git

  • Commit changed from a6212204674050c40fca7a7c41d4f25c6c2c066c to 0232b73b42b1460f05622dbfc81f8d3f51b9a50b

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

0232b73trac #16604: OA(20,544)

comment:22 Changed 5 years ago by ncohen

  • Summary changed from new OA for n=112,160,176,208,224,352,416,514,640,796,896 to new OA for n=112,160,176,208,224,352,416,514,544,640,796,896

comment:23 Changed 5 years ago by vdelecroix

Is this the end of commit?

comment:24 Changed 5 years ago by ncohen

Yes it i! All MOLS from Julian R. Abel's thesis have been fixed and implemented ! :-D

Nathann

comment:25 Changed 5 years ago by git

  • Commit changed from 0232b73b42b1460f05622dbfc81f8d3f51b9a50b to e5f428d75ade25f0524abbb61c71a67039ed754a

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

e5f428dtrac #16604: Merged with 6.3.beta6

comment:26 follow-up: Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_info

Hi Nathann,

I simplified the helper function at u/vdelecroix/16604 and update the branch over 6.3.rc1.

I would be really happy if:

  • the helper function would return a quasi-difference matrix instead
  • it was a function (not a hidden one) with explanations. I was able to simplify the function reading line by line but I do not understand anything. Do you have at least references for the construction?

(I can handle the merge with your documentation ticket #16766)

Vincent

comment:27 in reply to: ↑ 26 ; follow-up: Changed 4 years ago by ncohen

  • Status changed from needs_info to needs_review

Yo !

I would be really happy if:

  • the helper function would return a quasi-difference matrix instead
  • it was a function (not a hidden one) with explanations. I was able to simplify the function reading line by line but I do not understand anything. Do you have at least references for the construction?

I made it a private function exactly because I have no idea how to write a proper documentation for it. It is just a kind of construction that Julian R. Abel uses for many OA, and as I found I had been doing copy/pastes for it many many times I figured out that it would be better to simplify the code by making it one function. What it does exactly was not more documented before than it is now.

You can find examples of this construction in the Handbook, like on page 171 about theorem 3.76 for n=80.

(I can handle the merge with your documentation ticket #16766)

Hmmmm... I know that we will have to pay for this patch :-/

Nathann

comment:28 follow-up: Changed 4 years ago by vdelecroix

(I am using a live usb key and I completely messed up the author name in my commits. I tried "git rebase -i HEAD~2" but I obtain a list of 200+ commits because of the merge... do you know how to fix it?)

comment:29 in reply to: ↑ 27 ; follow-up: Changed 4 years ago by vdelecroix

Replying to ncohen:

Yo !

I would be really happy if:

  • the helper function would return a quasi-difference matrix instead
  • it was a function (not a hidden one) with explanations. I was able to simplify the function reading line by line but I do not understand anything. Do you have at least references for the construction?

I made it a private function exactly because I have no idea how to write a proper documentation for it. It is just a kind of construction that Julian R. Abel uses for many OA, and as I found I had been doing copy/pastes for it many many times I figured out that it would be better to simplify the code by making it one function. What it does exactly was not more documented before than it is now.

You can find examples of this construction in the Handbook, like on page 171 about theorem 3.76 for n=80.

It is not an explanation... I would like something like "If A and Y are matrices of size XX and properties YY then applying construction ZZ you obtain a quasi-difference matrix".

comment:30 in reply to: ↑ 29 Changed 4 years ago by ncohen

It is not an explanation... I would like something like "If A and Y are matrices of size XX and properties YY then applying construction ZZ you obtain a quasi-difference matrix".

I understand what you want, I am just telling you that this is all I have.

Nathann

comment:31 in reply to: ↑ 28 ; follow-up: Changed 4 years ago by ncohen

(I am using a live usb key and I completely messed up the author name in my commits. I tried "git rebase -i HEAD~2" but I obtain a list of 200+ commits because of the merge... do you know how to fix it?)

to change your last two commits I would do that :

1) git reset HEAD~1 # this "cancels" your last commit, and its code will become "staged differences". As if you had not typed "git commit"

2) git commit --amend --author <whatever you want> # change the author of the merge commit

3) git commit -a --author <whatever you want> # do your last commit again

Nathann

comment:32 in reply to: ↑ 31 Changed 4 years ago by vdelecroix

Replying to ncohen:

(I am using a live usb key and I completely messed up the author name in my commits. I tried "git rebase -i HEAD~2" but I obtain a list of 200+ commits because of the merge... do you know how to fix it?)

to change your last two commits I would do that :

1) git reset HEAD~1 # this "cancels" your last commit, and its code will become "staged differences". As if you had not typed "git commit"

2) git commit --amend --author <whatever you want> # change the author of the merge commit

3) git commit -a --author <whatever you want> # do your last commit again

Great. It worked... but this method works only if there is at most one commit after the merge. If you have a look at the branch u/vdelecroix/16604 the helper function is much simpler (and the code run a bit faster).

Vincent

comment:33 Changed 4 years ago by ncohen

  • Branch changed from u/ncohen/16604 to u/vdelecroix/16604
  • Commit changed from e5f428d75ade25f0524abbb61c71a67039ed754a to de1dafd330dcf9b07899f677b26bcab6d0ba7297

New commits:

e54b3bbtrac #16604: merge 6.3.rc1
de1dafdtrac #16604: simplification of the helper + more doc

comment:34 Changed 4 years ago by ncohen

Yooooooooo !

I just read your new version of the code. Thanks, it's much better than this ! I will add a small commit for a sentence I had some trouble understanding at first.

And if you do not mind I will also reverse your 2**n-->1<<n. That's zero improvement on speed for less redability.

Nathann

comment:35 Changed 4 years ago by ncohen

  • Branch changed from u/vdelecroix/16604 to public/16604
  • Commit changed from de1dafd330dcf9b07899f677b26bcab6d0ba7297 to 976013cf69d2bdfab7772c047fdee6094292dc9c

Here it is ! And I agree with your commits of course, thank you again !

By the way : the improvement at #16720 is made by not using addition on the group/field objects from Sage, because it is too slow. So we have to keep that in mind if we ever meet speed problems again with these operations.

Nathann


New commits:

976013ctrac #16604: review of the reviewer's patch

comment:36 Changed 4 years ago by git

  • Commit changed from 976013cf69d2bdfab7772c047fdee6094292dc9c to 3d1482926f8621b2fc509aec9e6e4281244524af

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

3d14829trac #16604: the helper as a standalone function

comment:37 follow-up: Changed 4 years ago by vdelecroix

Hi again,

I read the Abel-Cheng paper of 1994 (written during Julian Abel's thesis I guess) where the explanation was clear enough to write a complete documentation. The function has moved to orthogonal_array.py...

Please read three times the documentation to see whether its readable and understandable. You can also complain about the ugly name I choose, but in that case find something better.

Vincent

PS: there are two mysteries that I will ask Julian about

  • it is not clear to me why we need wc = w + 1
  • we do not care very much of the fact that the part different from 2^c is a prime number
Last edited 4 years ago by vdelecroix (previous) (diff)

comment:38 in reply to: ↑ 37 ; follow-up: Changed 4 years ago by ncohen

Yooooo !!!

I read the Abel-Cheng paper of 1994 (written during Julian Abel's thesis I guess) where the explanation was clear enough to write a complete documentation. The function has moved to orthogonal_array.py...

Great ! It is cool to have a good doc for this construction. But the function's name makes one think "Okay, this function takes c as an input and return an OA with n=2^c".

Please read three times the documentation to see whether its readable and understandable. You can also complain about the ugly name I choose, but in that case find something better.

Well. Did you read it three times yourself ? :-P

  • Most of the function's one line description defines what n is, and at this level we do not care much. What about Returns an OA(k,|G_1|2^c) from a constrained (G_1,k-1,2)-difference matrix ? It is a bit more meaningful and also indicates that the function's input is not as simple as a pair of integers...
  • Why G_1 and not G ?
  • Shouldn't we use F_p rather than GF(2) in the doc ?
  • that belong t
  • B and C : why not name them A_{G_1} and A_{GF(2)} ?
  • For any pair `i` and `j` of distinct integers in `{1,...,k-1}` and `g` an element of `G_1` --> for any i\neq j and g\in G_1 ?
  • C_{i,k_1} - C_{i,k_1} is zero :-P
  • the array whose rowS

About the function's name here's my attempt: OA_p_times_2_pow_c_from_matrix ? With your name one can believe that it is just about powers of two. And the "from matrix" indicated that "if you are looking for something standard, pass your way".

Nathann

comment:39 in reply to: ↑ 38 ; follow-up: Changed 4 years ago by vdelecroix

Hello,

Thanks for your careful reading.

Please read three times the documentation to see whether its readable and understandable. You can also complain about the ugly name I choose, but in that case find something better.

Well. Did you read it three times yourself ? :-P

No. I wrote it three times ;-?

  • Most of the function's one line description defines what n is, and at this level we do not care much. What about Returns an OA(k,|G_1|2^c) from a constrained (G_1,k-1,2)-difference matrix ? It is a bit more meaningful and also indicates that the function's input is not as simple as a pair of integers...

done

  • Why G_1 and not G ?

Because G was the cartesian product. Now changed.

  • Shouldn't we use F_p rather than GF(2) in the doc ?

You meant F_2? And then use F_{2^c} for GF(2^c). In non compiled version of the doc I found my version more readable. Moreover, it conincides with what you use in Sage to get your finite field. And it is pretty much standard (wikipedia entry for GF(2)).

  • that belong t

t -> to (done)

  • B and C : why not name them A_{G_1} and A_{GF(2)} ?

B and C is the notation from Abel-Cheng 1994. And it is much shorter when you have to write B_{i,k_1} instead of (A_{GF(2)})_{i,k_1}.

  • For any pair `i` and `j` of distinct integers in `{1,...,k-1}` and `g` an element of `G_1` --> for any i\neq j and g\in G_1 ?

done

  • C_{i,k_1} - C_{i,k_1} is zero :-P

you are right! It is now C_{i,k_1} - C_{j,k_1}.

  • the array whose rowS

done

About the function's name here's my attempt: OA_p_times_2_pow_c_from_matrix ? With your name one can believe that it is just about powers of two. And the "from matrix" indicated that "if you are looking for something standard, pass your way".

As I mentioned it is not p_times_2_pow_c but n_times_2_pow_c. G needs not be a cyclic group of prime order. Changed for OA_n_times_2_pow_c_from_matrix.

Vincent

comment:40 Changed 4 years ago by git

  • Commit changed from 3d1482926f8621b2fc509aec9e6e4281244524af to 7b392539e555ec0796a9d4b76f885920c48616ac

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

7b39253trac #16604: updated documentation + name changed

comment:41 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:42 Changed 4 years ago by git

  • Commit changed from 7b392539e555ec0796a9d4b76f885920c48616ac to 3cf39835a05cafffa1406c0ace944f9f4b7e3042

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

344b0bftrac #16598: Merged with 6.3
3cf3983trac #16604: Reviewing the review

comment:43 in reply to: ↑ 39 Changed 4 years ago by ncohen

Helloooooooooo !!

Thanks for your modifications. I added a small commit to fix a couple of things

  • add the function in the new index
  • Move the explanation on how elements of GF(2^c) should be encoded to the input section

I also tried to rephrase the last sentence of the explanation but I still don't get it. I replaced an occurrence of G_1 with G (and I think that was not a mistake), plus I changed the bound 1<=i<= |G| to 1<= i <= 2|G|, and now it seems that you indexed Y with i,j while it should be indexed on k. Especially since now that i goes to 2|G| the vector Y has the wrong length. Plus you define Y as being of length k-1. Could you check that again ?

You also defined k as ranging from 1 to k-1 which was a bit hard to read, so I "found a way around".

Tell me what you think !

Nathann

comment:44 Changed 4 years ago by vdelecroix

Hi,

I was a bit stupid: there is a k in the parameter but I used it as a variable... so it is definitely confusing. Moreover in the Abel-Cheng articles they use transposed matrix so I was confused with rows and columns. I will add a commit about that in a minute.

Vincent

comment:45 Changed 4 years ago by git

  • Commit changed from 3cf39835a05cafffa1406c0ace944f9f4b7e3042 to d612056869f25d94835570fca45572bfd2f5ccc8

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

d612056trac #16604: on the doc again

comment:46 Changed 4 years ago by vdelecroix

The matrix A has as many rows as the length of Y and has 2|G| columns...

Vincent

comment:47 Changed 4 years ago by ncohen

Cool ! This time I got it ! :-D

It really is hell with everybody using the matrix or its transpose T_T

By the wayyyyyy... As this function is now public... Would you feel like writing some code to check that all constraints are satisfied ? ^^;

You see all these things better than I, that's why I ask... ^^;

Nathann

comment:48 Changed 4 years ago by git

  • Commit changed from d612056869f25d94835570fca45572bfd2f5ccc8 to bff470ee5b4bb561cae7f01cf08ed7dfe126fa94

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

bff470etrac #16604: small check of dimensions

comment:49 follow-up: Changed 4 years ago by vdelecroix

Good idea. I did the dimension check... if we want more, we need is_difference_matrix.

I would go for a positive review at this stage... what do you think?

Vincent

comment:50 in reply to: ↑ 49 Changed 4 years ago by ncohen

Yo !

Good idea. I did the dimension check... if we want more, we need is_difference_matrix.

We don't have is_difference_matrix ? O_o

Okay then I will write this today. You may like difference families but I like difference matrices.

We need a is_difference_matrix. Then we'll finish this ticket.

Nathann

comment:51 Changed 4 years ago by ncohen

  • Dependencies changed from #16582 to #16582,#16797

Ticket for is_difference_matrix: #16797

Nathann

comment:52 Changed 4 years ago by git

  • Commit changed from bff470ee5b4bb561cae7f01cf08ed7dfe126fa94 to 579e75bd1c2a355082d5cf04b7f0ecc95d6c092a

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

8f10d94trac #16797: is_difference_matrix
aa097f6trac #16797: Fit with the current definition until we can change everything at once
5d21b8ctrac #16797: int * and ** instead of Python list
8f29bd1trac #16797: change int to int * in a malloc
811e3e9trac #16797: better malloc + better error msg
1b8c2e3trac #16797: More compact mallocs
b78c347trac #16797: Reorder the arguments to copy is_orthogonal_array
6c21904trac #16797: correct a row/column inversion
48b6902trac #16604: merge #16797
579e75btrac #16604: input check + doctest

comment:53 Changed 4 years ago by vdelecroix

Needs review.

Vincent

comment:54 Changed 4 years ago by git

  • Commit changed from 579e75bd1c2a355082d5cf04b7f0ecc95d6c092a to 05c691500eb1131cb71303ed759ddf2cbc13b46f

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

e1a83d0trac #16604: Optional check flag
05c6915trac #16604: Variable rename and list->set

comment:55 Changed 4 years ago by ncohen

Your turn !

Nathann

comment:56 Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

I am happy with the current version.

Vincent

comment:57 Changed 4 years ago by git

  • Commit changed from 05c691500eb1131cb71303ed759ddf2cbc13b46f to 24c4f7fc4cf619fca8cceb5707b74b935de880c2
  • Status changed from positive_review to needs_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

dee4275trac #16797: Merged with 6.4.beta0
24c4f7ftrac #16604: Merge with updated #16797

comment:58 Changed 4 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:59 Changed 4 years ago by vbraun

  • Branch changed from public/16604 to 24c4f7fc4cf619fca8cceb5707b74b935de880c2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.