difference family database #16802

videlec · 2014-08-12T10:43:55Z

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

The text was updated successfully, but these errors were encountered:

videlec · 2014-08-12T10:44:34Z

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 · 2014-08-12T10:44:34Z

Branch: u/vdelecroix/16802

videlec · 2014-08-12T10:44:34Z

Commit: 3ce65b8

sagetrac-git · 2014-08-20T13:38:57Z

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`

sagetrac-git · 2014-08-20T13:38:57Z

Changed commit from 3ce65b8 to e898462

videlec · 2014-08-20T13:39:19Z

comment:3

Rebased above the positively reviewed #16757...

nathanncohen · 2014-08-20T14:33:39Z

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 · 2014-08-20T16:37:43Z

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 · 2014-08-20T16:37:43Z

Changed commit from e898462 to d8f8fef

videlec · 2014-08-20T16:37:43Z

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

sagetrac-git · 2014-08-20T18:02:14Z

Changed commit from d8f8fef to c66bc2f

sagetrac-git · 2014-08-20T18:02:14Z

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

`c66bc2f`	`trac #16802: review 2`

videlec · 2014-08-20T18:03:23Z

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

sagetrac-git · 2014-08-20T18:07:16Z

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

`c415a98`	`trac #16802: database of difference family`

sagetrac-git · 2014-08-20T18:07:16Z

Changed commit from c66bc2f to c415a98

nathanncohen · 2014-08-21T10:52:52Z

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

sagetrac-git · 2014-08-21T10:53:16Z

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

`7c91847`	`trac #16802: Review`

sagetrac-git · 2014-08-21T10:53:16Z

Changed commit from c415a98 to 7c91847

sagetrac-git · 2014-08-21T11:09:52Z

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`

sagetrac-git · 2014-08-21T11:09:52Z

Changed commit from 7c91847 to 4bd8d69

nathanncohen · 2014-08-21T11:10:19Z

comment:12

(rebased on top of #16763)

nathanncohen · 2014-08-21T11:10:19Z

Changed dependencies from #16757 to #16763

sagetrac-git · 2014-08-21T11:56:01Z

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

`3c0fa72`	`trac #16802: review the review`

sagetrac-git · 2014-08-21T11:56:01Z

Changed commit from 4bd8d69 to 3c0fa72

videlec · 2014-08-21T11:56:38Z

comment:14

Hello,

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

Vincent

sagetrac-git · 2014-08-21T12:01:53Z

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

`2b555e4`	`trac #16802: review the review`

sagetrac-git · 2014-08-21T12:01:53Z

Changed commit from 3c0fa72 to 2b555e4

sagetrac-git · 2014-08-21T12:32:17Z

Changed commit from 2b555e4 to 4434d61

sagetrac-git · 2014-08-21T12:32:17Z

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

`4434d61`	`trac #16802: review the review`

nathanncohen · 2014-08-21T13:33:24Z

comment:17

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

Nathann

nathanncohen · 2014-08-21T13:35:20Z

comment:18

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

Nathann

nathanncohen · 2014-08-21T13:35:20Z

Reviewer: Nathann Cohen

videlec · 2014-08-21T13:40:33Z

comment:19

Thanks!!

Vincent

vbraun · 2014-08-22T11:47:53Z

comment:20

Milestone? duplicate/wontfix?

vbraun · 2014-08-23T13:24:24Z

Changed branch from public/16802 to 4434d61

videlec added c: combinatorial designs labels Aug 12, 2014

videlec added the s: needs review label Aug 12, 2014

nathanncohen mannequin added s: needs work and removed s: needs review labels Aug 20, 2014

videlec added s: needs review and removed s: needs work labels Aug 20, 2014

nathanncohen mannequin added s: positive review and removed s: needs review labels Aug 21, 2014

vbraun added s: needs info and removed s: positive review labels Aug 22, 2014

videlec added this to the sage-6.4 milestone Aug 22, 2014

videlec added s: positive review and removed s: needs info labels Aug 22, 2014

vbraun removed the s: positive review label Aug 23, 2014

vbraun closed this as completed in ea6afcd Aug 23, 2014

videlec mentioned this issue Aug 23, 2014

twin prime difference sets #16863

Closed

difference family database #16802

difference family database #16802

Comments

videlec commented Aug 12, 2014

videlec commented Aug 12, 2014

videlec commented Aug 12, 2014

videlec commented Aug 12, 2014

sagetrac-git mannequin commented Aug 20, 2014

sagetrac-git mannequin commented Aug 20, 2014

videlec commented Aug 20, 2014

nathanncohen mannequin commented Aug 20, 2014

videlec commented Aug 20, 2014

videlec commented Aug 20, 2014

videlec commented Aug 20, 2014

sagetrac-git mannequin commented Aug 20, 2014

sagetrac-git mannequin commented Aug 20, 2014

videlec commented Aug 20, 2014

sagetrac-git mannequin commented Aug 20, 2014

sagetrac-git mannequin commented Aug 20, 2014

nathanncohen mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

nathanncohen mannequin commented Aug 21, 2014

nathanncohen mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

videlec commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

sagetrac-git mannequin commented Aug 21, 2014

nathanncohen mannequin commented Aug 21, 2014

nathanncohen mannequin commented Aug 21, 2014

nathanncohen mannequin commented Aug 21, 2014

videlec commented Aug 21, 2014

vbraun commented Aug 22, 2014

vbraun commented Aug 23, 2014