difference family database

videlec commented 10 years ago

Import the database from the Handbook of combinatorial design inside Sage.

Depends on #16763

CC: @nathanncohen

Component: combinatorial designs

Author: Vincent Delecroix

Branch/Commit: 4434d61

Reviewer: Nathann Cohen

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

videlec commented 10 years ago

Last 10 new commits:

`0232b73`	`trac #16604: OA(20,544)`
`e5f428d`	`trac #16604: Merged with 6.3.beta6`
`355ac2a`	`trac #16662: OA for n=1046,1059,2164,3992,3994`
`15b449c`	`trac #16665: New OA for n=408,600,792,856,1368,2328,...`
`a515dee`	`trac #16673: Three factors construction of MOLS`
`845de7a`	`trac #16716: OA for n=262,950`
`a9608c5`	`trac #16722: OA(17,560)`
`e5fc881`	`trac #16722: Merged with 6.3.beta8`
`698b704`	`trac #16757: Organize the V(m,t) vectors into a dictionary`
`3ce65b8`	`trac #16802: database of difference family`

videlec commented 10 years ago

Branch: u/vdelecroix/16802

videlec commented 10 years ago

Commit: 3ce65b8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

`9cbc23c`	`trac #16673: Three factors construction of MOLS`
`3fb8806`	`trac #16673: review (one line simplicaction + doc)`
`3458d22`	`trac #16673: Merged with 6.4.beta1`
`e48c1d3`	`trac #16716: OA for n=262,950`
`b9aa228`	`trac #16722: OA(17,560)`
`9a57f13`	`trac #16757: Organize the V(m,t) vectors into a dictionary`
`57c00f0`	`trac #16757: doctest simplication`
`e898462`	`trac #16802: merge update #16757`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 3ce65b8 to e898462

videlec commented 10 years ago

comment:3

Rebased above the positively reviewed #16757...

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:4

Yooooooooooooooooooooooooooooo !!!!

First review of this patch (it will be clearer after those points have been solved):

The DF in the database: why add a 'S' in the blocks of short groups ? it is not like it is hard to check that a block has an non-empty stabilizer. We can get this info easily. Plus those 'S' have nothing to do in the blocks of a design ...
The database looks a bit messy as it is. Could you align some stuff, like the ':' or the ',' so that one can actually read it in the code ?
The database should be indexed with (v,k,l) instead of ((v1,v2,v3),k,l). You can have something like that:
```
DF_database = {
 (v,k,l) : {
    (v1,v2,v3): [DF1,DF2,DF3,....]
 }
}
```
This way you can easily check whether there exists a BIBD that can be obtained from a difference family. And you can also find (v1,v2,v3) easily.

With a database indexed with (v,k,l) you can undo those modifications

-if (v,k,l) in DF_constructions:
+G_df = DF_from_database(v,k,l,short_blocks=short_blocks)
+if G_df:

Block stabilizer: instead of computing the stabilizer of blocks, you could just develop a block with respect to the group and remove duplicated, you know ? All it takes is a simple call to set(...). Much easier to understand, no questions about where all those group-specific functions should be implemented...

If you do that you save around 100 lines of code+doc with the three functions block_stabilizer, orbit_representatives, partial_differences. Really I would have nothing if those functions were group methods, but having to implement all that just for difference families, and just to avoid a call to set(), really ?....

Plus there is the "short+non-abelian exception" in is_difference_family, that wouldn't be needed anymore in this case ....
If you insist on having all those functions to avoid calling "set" to simplify the orbits of a block, and if you want to keep the warning above, you may also have to handle the case where the group is a multiplicative+commutative group.
(That's going very far just to avoid a set(...) :-P
difference_family : new short_blocks argument. Really, WHY do you care so much about short blocks ? They are just blocks whose orbit is smaller, what's all the fuss about ? If we give the users access to the database, can't we just give them a function that tests if a block is short and let them do what they want with it ?
What's the point of filtering difference families with short blocks anyway ?
The checks in DF_from_database: if you want to check anything about the database, it would be better to do it in the doctests than at runtime ?...
DF_from_database: if you actually need it, should be in difference_family.py not in database.py
isn't "too few" better than "too less" ?

Nathann

videlec commented 10 years ago

comment:5

Thanks for the rebase.

Replying to @nathanncohen:

Yooooooooooooooooooooooooooooo !!!!

First review of this patch (it will be clearer after those points have been solved):

The DF in the database: why add a 'S' in the blocks of short groups ?

removed

The database looks a bit messy as it is. Could you align some stuff, like the ':' or the ',' so that one can actually read it in the code ?

The database should be indexed with (v,k,l) instead of ((v1,v2,v3),k,l).
With a database indexed with (v,k,l) you can undo those modifications
-if (v,k,l) in DF_constructions:
+G_df = DF_from_database(v,k,l,short_blocks=short_blocks)
+if G_df:

done, done, done.

For the rest, some people defines difference families with short blocks (as in the Handbook) and some people do not allow them (like in Stinson for example). So you have to care about the two definitions.

About the functions block_stabilizer, orbit_representatives, partial_differences it is used in basically two places: is_difference_family and BIBID_from_difference_family. You can not avoid them in the former. Nevertheless:

I removed partial_differences as it was used in only one place and is a two lines function
I rewrote some of the doc

As you can see, the is_difference_family is very detailed and it was very useful to debug the database from the Handbook.

I do not see the need of multiplicative Abelian group in difference families...

Vincent

New commits:

`6518229`	`trac #16802: database of difference family`
`d8f8fef`	`trac #16802: review 1`

videlec commented 10 years ago

Changed commit from e898462 to d8f8fef

videlec commented 10 years ago

Changed branch from u/vdelecroix/16802 to public/16802

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from d8f8fef to c66bc2f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

c66bc2f trac #16802: review 2

videlec commented 10 years ago

comment:7

In the last commit:

remove DF_from_database and include the code in difference_family
remove the function orbit_representatives (remains only block_stabilizer)
remove the argument short_blocks from everywhere

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

c415a98 trac #16802: database of difference family

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from c66bc2f to c415a98

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:9

Helloooooooooooo !!!

Very good code, efficient and all. I added a commit but I still have a couple of remarks :

What does that mean ?

+An example with a short block (i.e. considering restricted difference when a
+block has a non trivial stabilizer)::

I do not find the two messages about the checks over l very clear for a user:
```
sum(1/s_i) k*(k-1) = {} is not a multiple of (v-1) = {} (stabilizer sizes {})
```
The si are not defined (and it is hard to define them in an error message)... What would you think of formulating that with BIBD terminology ? A bit like my comment about nb_diff in the code ?
What do we do about non-commutative groups ? If we don't handle them it would be nice to have an error message sayng "the group is not commutative". And if we handle them we have to be more verbose about left/right actions and everything (I personally think that it is going too far, but well)..

I did several things in my commit:

move a DF that was not properly ordered
expand the doc a bit in some places
Removed the "abelian/additive" in is_difference_family, but that's also part of the more general question above.
rename c_counter to tmp_counter
Replace the ValueError in difference_family with an AssertionError.

Tell me if you agree with those changes, and what you think of my questions above. Before we set this ticket to positive_review I will rebase it somehow, so that all design patches are linearly ordered.

Thanks !

Nathann

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

7c91847 trac #16802: Review

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from c415a98 to 7c91847

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

`424e229`	`trac #16763: New OA for n=189, plus some others through Vmt vectors`
`5ba165e`	`trac #16763: Complete bibliographical references`
`f3f644d`	`trac #16763: code simplification`
`04936aa`	`trac #16802: database of difference family`
`4bd8d69`	`trac #16802: Review`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 7c91847 to 4bd8d69

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:12

(rebased on top of #16763)

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Changed dependencies from #16757 to #16763

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

3c0fa72 trac #16802: review the review

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 4bd8d69 to 3c0fa72

videlec commented 10 years ago

comment:14

Hello,

I tried to address the issue you mentioned in comment:9...

Vincent

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

2b555e4 trac #16802: review the review

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 3c0fa72 to 2b555e4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 2b555e4 to 4434d61

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

4434d61 trac #16802: review the review

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:17

Thanks ! Positive review to this branch ! I will rebase it on top of #16763 and switch it to positive_review

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:18

Oh. Looks like I did it already. Let's go then ! :-P

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

Reviewer: Nathann Cohen

videlec commented 10 years ago

comment:19

Thanks!!

Vincent

vbraun commented 10 years ago

comment:20

Milestone? duplicate/wontfix?

vbraun commented 10 years ago

Changed branch from public/16802 to 4434d61

sagemath / sage

difference family database #16802