Opened 7 years ago

Closed 7 years ago

#16461 closed enhancement (fixed)

Difference families... and more BIBD

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorial designs Keywords:
Cc: ncohen Merged in:
Authors: Vincent Delecroix Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 0380ead (Commits, GitHub, GitLab) Commit: 0380ead2db09b903f25ef9204ed8b2f1f66cfd20
Dependencies: #16464, #16391 Stopgaps:

Status badges

Description (last modified by vdelecroix)

A file for difference families and the associated BIBD constructions.

Also

  • some simplifications for BIBD with k=4,5
  • some new BIBD with k=6,7,...

Change History (47)

comment:1 Changed 7 years ago by vdelecroix

  • Branch set to u/vdelecroix/16461
  • Commit set to fa45dd3df9317893e1fc0a2a4c4cbe1e0314c000
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

fa45dd3trac #16461: difference families

comment:2 follow-up: Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_work

Wow. Coool to see something happend there ! Thanks for the work ! :-)

Here is a first-pass-review.

  • The new file should be added to the doc
  • "Associates to n is a dictionnary"
  • Could you add references for the DF ? (even if it is always "from the handbook")
  • Unless you add a definition of what a DF is at the head of difference_family.py I would say that your "todo" belongs to the constructor, after the def.
  • All functions need a docstring.
  • zmod_or_finite_field : why not always use a GF ? By the way the name of this function is not sufficiently descriptive. Same for group_law
  • About group_law : I was telling Nicolas the other day how it would be more proper to have a category Groups() which would be "any kind of group" and also have a "MultiplicativeGroups?()` category for ... well, multiplicative groups.
  • quadratic_residues, quartic_residues and cyclotomic_cosets belong to the Fields code (and probably to another patch, so that the Fields guys see that it is being added)
  • Could you add a SEEALSO link from is_difference_family to difference_family, as the latter contains the actual definition of a DF ?
  • I expect that _have_distinct_images would be faster if you added all elements to the set directly (i.e. set(map(f,elts)) then checked that it has the right size. This way you do not 1) check that the element is in the set 2) add it, i.e. two log(n) computations.
  • difference_family needs an INPUT section (and could be linked toward http://en.wikipedia.org/wiki/Difference_set).
  • have_distinct_images too
  • Shouldn't Return a `(k,l)`-difference family use "lambda" instead ? You use both l and lambda in the docstring. I think I saw lambd or lam used once.
  • You don't need to check that the value of 'l' is correct when you computed it yourself. It belongs to the "else" group above.
  • such that the set of differences seen as a multi-set contains : it does not say what the "set of differences" actually is, i.e. the union of the sets of differences corresponding to every set of the family... This sentence isn't very clear either, it may deserve another sentence.
  • is_difference_family -- looks like the case when one of the "sets" of the DF contains the same element twice is handled correctly, but maybe it should deserves an explicit error ? Especially for things like the set [0,5,10,15] over GF(5**4) which may not be obvious.
  • Languages should have built-in functions so that "{} times" becomes "{} time" when {} == 1 :-P
  • why DF_constructions[v][k,l] instead of DF_constructions[v,k,l] ?
  • I still have not read/checked the main function, i.e. difference_family.

Nathann

comment:3 Changed 7 years ago by ncohen

Another remark : you removed difference families from the code for (37,4),(21,5),(41,5),(61,5),(281,5). Those difference families are needed for the BIBD constructions, so could you add a doctests somewhere to make sure they are always generated by your functions ? Thanks !

Nathann

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

Replying to ncohen comment 2:

Wow. Coool to see something happend there ! Thanks for the work ! :-)

Here is a first-pass-review.

Thanks. I just answer to the remarks for which it is not clear to me what to do.

  • About group_law : I was telling Nicolas the other day how it would be more proper to have a category Groups() which would be "any kind of group" and also have a "MultiplicativeGroups?()` category for ... well, multiplicative groups.

But then how do you get the group law? I would be happy to see my group_law method as a method of any group. Tell Nicolas, that the power set of a set with the operation of symmetric difference is also a group... which is neither additive nor multiplicative ;-)

  • quadratic_residues, quartic_residues and cyclotomic_cosets belong to the Fields code (and probably to another patch, so that the Fields guys see that it is being added)

Problem1: quadratic_residues is already a function that takes an integer n as input and return the squares modulo n. The ouptut are sage Integer. So it does not fit very well as I need finite field which are not necessarily primes. Idem for cyclotomic_cosets.

  • I expect that _have_distinct_images would be faster if you added all elements to the set directly (i.e. set(map(f,elts)) then checked that it has the right size. This way you do not 1) check that the element is in the set 2) add it, i.e. two log(n) computations.

As my set are rather small, you are probably right.

  • is_difference_family -- looks like the case when one of the "sets" of the DF contains the same element twice is handled correctly, but maybe it should deserves an explicit error ? Especially for things like the set [0,5,10,15] over GF(5**4) which may not be obvious.

Such blocks might be valid for lambda > 1. (but note that 0=5=10=15 in your GF(5**4)).

  • I still have not read/checked the main function, i.e. difference_family.

No hurry. I have to do the changes.

Replying to ncohen comment 3

Another remark : you removed difference families from the code for (37,4),(21,5),(41,5),(61,5),(281,5). Those difference families are needed for the BIBD constructions, so could you add a doctests somewhere to make sure they are always generated by your functions ? Thanks !

It is already (partly) tested in the bibd.py file. But I will add something more explicit.

Vincent

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

Yooooooooo !

But then how do you get the group law?

It's unrelated. My remark was just that this is wrong :

sage: groups.misc.AdditiveCyclic(4) in Groups()
False

What we have now is that MultiplicativeGroups is improperly called "groups". That's just about the thing's name.

I would be happy to see my group_law method as a method of any group.

We, it could definitely be the first method of a Groups() category !

Tell Nicolas, that the power set of a set with the operation of symmetric difference is also a group... which is neither additive nor multiplicative ;-)

Well, you got the email so tell him. That's actually dead right !

Problem1: quadratic_residues is already a function that takes an integer n as input and return the squares modulo n. The ouptut are sage Integer. So it does not fit very well as I need finite field which are not necessarily primes. Idem for cyclotomic_cosets.

quadratic_residues is a function from the global namespace. What you are implementing is a method of Fields, isn't it ?

Such blocks might be valid for lambda > 1. (but note that 0=5=10=15 in your GF(5**4)).

That's exactly why I picked those values. Are you allowed to have the same element twice in a set of a difference family ?

It is already (partly) tested in the bibd.py file. But I will add something more explicit.

Yes yes, I just worried that it could only be triggered when you try to compute exhaustively all BIBD for n<500 or something.

Nathann

comment:6 Changed 7 years ago by git

  • Commit changed from fa45dd3df9317893e1fc0a2a4c4cbe1e0314c000 to 491d66957e3f92387f3db04e92914f359e2a35e2

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

491d669trac #16461: reviewer comment 1 ++

comment:7 in reply to: ↑ 5 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Problem1: quadratic_residues is already a function that takes an integer n as input and return the squares modulo n. The ouptut are sage Integer. So it does not fit very well as I need finite field which are not necessarily primes. Idem for cyclotomic_cosets.

quadratic_residues is a function from the global namespace. What you are implementing is a method of Fields, isn't it ?

I refactored quadratic_residues, quartic_residues and cyclotomic_cosets into a unique function named cyclotomic_cosets and that takes a cosets argument. It definitely belong to finite fields, but I am not sure this is standard terminology in algebra... I believe not... The multiplicative group of invertible elements of a finite field is always cyclic, so any coset is actually "cyclotomic". It might be multiplicative_cosets. Nevertheless, I am not sure it would be of much use as a method of finite field and I would rather let it where it is.

Such blocks might be valid for lambda > 1. (but note that 0=5=10=15 in your GF(5**4)).

That's exactly why I picked those values. Are you allowed to have the same element twice in a set of a difference family ?

Nope: the difference must belong to G \ {0} so you can not repeat an element.

It is already (partly) tested in the bibd.py file. But I will add something more explicit.

Yes yes, I just worried that it could only be triggered when you try to compute exhaustively all BIBD for n<500 or something.

It is now completely tested.

Vincent

comment:8 Changed 7 years ago by git

  • Commit changed from 491d66957e3f92387f3db04e92914f359e2a35e2 to 5d91e5f398d7ddad0bfb9cb6952f3af493943b0d

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

5d91e5ftrac #16461: more doc

comment:9 Changed 7 years ago by vdelecroix

  • Dependencies set to #16464
  • Status changed from needs_review to needs_work

waiting for #16461 now.

Version 0, edited 7 years ago by vdelecroix (next)

comment:10 Changed 7 years ago by git

  • Commit changed from 5d91e5f398d7ddad0bfb9cb6952f3af493943b0d to 2d12cc02dd29a47955b670df51beed44b569d2a0

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

b903c4dtrac #16461: more doc
9b1544btrac #16464: generic implementation
f0a2958trac #16464: Docstring work
f0474bbtrac #16464: be more careful with errors
21cb1a8trac #16464: handle correctly arguments for cyclotomic_cosets
b07ad01trac #16464: Second review
136e870trac #16464: tiny improvements for is_a_splitting
965f550trac #16464: replace bool(S1&S2) by S1.isdisjoint(S2)
9b199c7trac #16461: merge #16464
2d12cc0trac #16461: adapt the implementation with #16464

comment:11 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:12 Changed 7 years ago by ncohen

I hate to see the dependencies in the tickets... T_T

Nathann

comment:13 Changed 7 years ago by git

  • Commit changed from 2d12cc02dd29a47955b670df51beed44b569d2a0 to d3d6a31efd1ec23afa311c51a437253a4b8f1628

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

d3d6a31trac #16461: reset finite_field_base.pyx to its previous state

comment:14 Changed 7 years ago by git

  • Commit changed from d3d6a31efd1ec23afa311c51a437253a4b8f1628 to 263869795e1c6e6af4a44045b4275b0911aef2eb

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

2638697trac #16461: always check the difference family

comment:15 Changed 7 years ago by ncohen

Hello !!

Is if l == (k-1): equivalent to if (v-1)%k == 0 ?

Nathann

comment:16 follow-up: Changed 7 years ago by vdelecroix

No. None of the one implies the other.

Assume l(v-1) % (k(k-1)) == 0. Then:

  • if l = k-1 then v-1 is can be any multiple of k
  • if v-1 = k(k-1) then l is arbitrary

Vincent

Last edited 7 years ago by vdelecroix (previous) (diff)

comment:17 in reply to: ↑ 16 ; follow-up: Changed 7 years ago by ncohen

Yoooooooooooo !

No. None of the one implies the other.

Assume l(v-1) % (k(k-1)) == 0. Then, for example:

  • if l = k(k-1) then v is arbitrary
  • if v-1 = k(k-1) then l is arbitrary

Yesyesyes. I needed some time to find out why those cyclotomic cosets were cool difference families and I finally understood it to some extent :-)

As your function handles a lot of l>1 already, what would you mean of changing the "if" into "(v-1)%k == 0 and l%(k-1) == 0" ? In which case we could return "several times the same difference family" if l is equal to 2(k-1) ?

Nathann

comment:18 Changed 7 years ago by ncohen

By the way I think that the best way to deal with those multiple copies is to set a "multiplier" variable when D is defined. And at the end of everything, if multiplier>1, copy the whole family several times ?...

Nathann

comment:19 in reply to: ↑ 17 ; follow-up: Changed 7 years ago by vdelecroix

Replying to ncohen:

Yoooooooooooo !

No. None of the one implies the other.

Assume l(v-1) % (k(k-1)) == 0. Then, for example:

  • if l = k(k-1) then v is arbitrary
  • if v-1 = k(k-1) then l is arbitrary

Yesyesyes. I needed some time to find out why those cyclotomic cosets were cool difference families and I finally understood it to some extent :-)

As your function handles a lot of l>1 already, what would you mean of changing the "if" into "(v-1)%k == 0 and l%(k-1) == 0" ? In which case we could return "several times the same difference family" if l is equal to 2(k-1) ?

Actually, it is more than that. You can take the union of several families with the same (G,k) (the group G need to be fixed). If you have (G,k,l1), (G,k,l2), ..., (G,k,ln) difference families then you have a (G,k,l1+l2+...+ln) by taking the union. In other words, the set of l you can build for a fixed (G,k) is a semi-group of the integers... it is more than just stable under multiplication.

Last edited 7 years ago by vdelecroix (previous) (diff)

comment:20 follow-up: Changed 7 years ago by ncohen

Instead of this

_nonzero_and_have_distinct_images((r**j-one for j in xrange(1,m+1)), to_coset)

Couldn't you do that ?

things = [r**j-one for j in xrange(1,m+1)]
if 0 not in things and len(K.cyclotomic_cosets(x,things)) == m):

Or am I doing something wrong ?

Nathann

comment:21 in reply to: ↑ 19 ; follow-up: Changed 7 years ago by ncohen

Yo !

Actually, it is more than that. ... it is more than just stable under multiplication.

Oh. True, true. No idea how we will deal with this, then O_o

Nathann

comment:22 Changed 7 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:23 in reply to: ↑ 21 ; follow-up: Changed 7 years ago by vdelecroix

Replying to ncohen:

Yo !

Actually, it is more than that. ... it is more than just stable under multiplication.

Oh. True, true. No idea how we will deal with this, then O_o

For this ticket, I see two solutions:

  • make a more specialized function which take as input a fixed Abelian group (given by its invariants) and not only v. The case of cyclic families would just be the invariant being (v,) itself and power of cyclic would be (v,v,...,v).
  • write a TODO

The first solution is not that complicated. But then, it would make more sense to have:

  • designs.difference_family(v,k,lambda): do not care about the group
  • designs.abelian_difference_family(invariants, k, lambda): we care

Vincent

comment:24 in reply to: ↑ 23 ; follow-up: Changed 7 years ago by ncohen

For this ticket, I see two solutions:

Nono, a later ticket... This one is almost reviewed (still wincing a bit but I understand more and more :-P)

  • make a more specialized function which take as input a fixed Abelian group (given by its invariants) and not only v. The case of cyclic families would just be the invariant being (v,) itself and power of cyclic would be (v,v,...,v).
  • write a TODO

The first solution is not that complicated. But then, it would make more sense to have:

  • designs.difference_family(v,k,lambda): do not care about the group
  • designs.abelian_difference_family(invariants, k, lambda): we care

I don't see the relationship that you make between the group and the lambda. For me the problem is only that we need a way to detect that we can build a (v,k,l1+l2)-DF if we can build a (v,k,l1)-DF and a (v,k,l2)-DF. What does the group have to do with that ?

Nathann

comment:25 in reply to: ↑ 20 ; follow-up: Changed 7 years ago by vdelecroix

Replying to ncohen:

Instead of this

_nonzero_and_have_distinct_images((r**j-one for j in xrange(1,m+1)), to_coset)

Couldn't you do that ?

things = [r**j-one for j in xrange(1,m+1)]
if 0 not in things and len(K.cyclotomic_cosets(x,things)) == m):

Or am I doing something wrong ?

You are right. And it is true for the three constructions of Wilson, we just want to see if some elements are in distinct cosets. But on the other hand, with your solution you will build the cosets many times. It might be much longer especially in the third construction where there is an iteration over all elements of the finite field.

I can build the dictionnary to_coset from the K.cyclotomic_cosets if you like ;-)

comment:26 in reply to: ↑ 24 ; follow-up: Changed 7 years ago by vdelecroix

Replying to ncohen:

For this ticket, I see two solutions:

Nono, a later ticket... This one is almost reviewed (still wincing a bit but I understand more and more :-P)

  • make a more specialized function which take as input a fixed Abelian group (given by its invariants) and not only v. The case of cyclic families would just be the invariant being (v,) itself and power of cyclic would be (v,v,...,v).
  • write a TODO

The first solution is not that complicated. But then, it would make more sense to have:

  • designs.difference_family(v,k,lambda): do not care about the group
  • designs.abelian_difference_family(invariants, k, lambda): we care

I don't see the relationship that you make between the group and the lambda. For me the problem is only that we need a way to detect that we can build a (v,k,l1+l2)-DF if we can build a (v,k,l1)-DF and a (v,k,l2)-DF. What does the group have to do with that ?

If your two DF are on the same group you can take the union. Otherwise it just makes no sense!!

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

Yo !

You are right. And it is true for the three constructions of Wilson, we just want to see if some elements are in distinct cosets. But on the other hand, with your solution you will build the cosets many times. It might be much longer especially in the third construction where there is an iteration over all elements of the finite field.

Oh. I will look at that.

I can build the dictionnary to_coset from the K.cyclotomic_cosets if you like ;-)

What I want to do is get rid of this _nonzero_and_have_distinct_images function :-P

Nathann

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

If your two DF are on the same group you can take the union. Otherwise it just makes no sense!!

Ahahahah. True, true. I was thinking of BIBD, sorry :-D

Soooooooooooooooo we only need to implement this l1+l2 mechanism for BIBD.. And designs in general. Hmmmmmm :-P

Nathann

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

Replying to ncohen:

If your two DF are on the same group you can take the union. Otherwise it just makes no sense!!

Ahahahah. True, true. I was thinking of BIBD, sorry :-D

Soooooooooooooooo we only need to implement this l1+l2 mechanism for BIBD.. And designs in general. Hmmmmmm :-P

It can be worth it to have it at the level of the difference families to build designs with transitive symmetric groups.

comment:30 in reply to: ↑ 27 Changed 7 years ago by vdelecroix

Replying to ncohen:

What I want to do is get rid of this _nonzero_and_have_distinct_images function :-P

All right, it can be replaced by:

   len(set(to_coset[elt] for elt in XXX)) == len(XXX)

+ special care of the zero element.

Last edited 7 years ago by vdelecroix (previous) (diff)

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

It can be worth it to have it at the level of the difference families to build designs with transitive symmetric groups.

HMmmmmm... Sorry but for the moment I am only interested by DF for as long as they generate new BIBD :-P

Nathann

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

Replying to ncohen:

It can be worth it to have it at the level of the difference families to build designs with transitive symmetric groups.

HMmmmmm... Sorry but for the moment I am only interested by DF for as long as they generate new BIBD :-P

Might be. But on the other hand, it is easier to manipulate difference families rather than BIBD because they are small.

comment:33 Changed 7 years ago by ncohen

  • Reviewers set to Nathann Cohen

Ookayyyyyyyyy... It woud be cool if you could get rid of this _nonzero_and_have_distinct_images in a nice way. Aaaaaaaaaaaaaand if it not possible, well, you can set this ticket to positive_review anyway. Thanks for this patch ! :-)

Nathann

comment:34 Changed 7 years ago by git

  • Commit changed from 263869795e1c6e6af4a44045b4275b0911aef2eb to 8b1e6cefc5d2bae89d9a23c75a78e558ef6d3826

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

8b1e6cetrac #16461: get rid of _nonzero_and_have_distinct_images

comment:35 Changed 7 years ago by vdelecroix

  • Status changed from needs_info to needs_review

comment:36 Changed 7 years ago by ncohen

Why don't you need to test equality with 0 for the first construction ?

Nathann

comment:37 Changed 7 years ago by vdelecroix

Actually, there is no need to test equality to 0 (I realized that after removing the _nonzero...).

The second construction is a bit different from the other two because each block of the difference family contains 0. Somehow the coset labelled 0 (which is just [xx*j for j in xrange((v-1)//m)]) is automatically requested and you want that all the other differences belong to cosets distinct from it.

comment:38 Changed 7 years ago by ncohen

Okay, I se no reason to not set this to positive_review. Except one thing which was bothering me : difference_family.py instead of difference_families.py ? :-P

Nathann

comment:39 follow-up: Changed 7 years ago by vdelecroix

Then bibds.py? covering_designs.py? block_designs.py? When do we put an s and when we do not?

comment:40 in reply to: ↑ 39 Changed 7 years ago by ncohen

  • Status changed from needs_review to positive_review

Then bibds.py? covering_designs.py? block_designs.py? When do we put an s and when we do not?

Well, all new files have an 's'. Okay, doesn't matter.

Nathann

comment:41 Changed 7 years ago by ncohen

  • Dependencies changed from #16464 to #16464,#16391

comment:42 Changed 7 years ago by ncohen

  • Dependencies changed from #16464,#16391 to #16391

comment:43 Changed 7 years ago by ncohen

  • Dependencies changed from #16391 to #16464

comment:44 Changed 7 years ago by ncohen

  • Branch changed from u/vdelecroix/16461 to public/16461
  • Commit changed from 8b1e6cefc5d2bae89d9a23c75a78e558ef6d3826 to ee3b03584f8a60e892734193793dc1c20b6007c0
  • Dependencies changed from #16464 to #16464, #16391

Last 10 new commits:

90f828ftrac #16391: use OrthogonalArrayBlockGraph instead of OrthogonalArrayGraph
6e3c685trac #16391: reviewer's comments
52c2de8trac #16391: Removing the holes
d0885f7trac #16391: bugfix
c1de597trac #16391: doc clean + remove some list construction
41a9a24trac #16391: Typo
42239cctrac #16391: Undoing stuff
24ac3a8trac #16391: Broken doc
70c9805trac #16391: Merged with #16460
ee3b035trac #16461: Merged with #16391

comment:45 Changed 7 years ago by git

  • Commit changed from ee3b03584f8a60e892734193793dc1c20b6007c0 to 0380ead2db09b903f25ef9204ed8b2f1f66cfd20
  • 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:

0380eadtrac #16461: fix documentation

comment:46 Changed 7 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:47 Changed 7 years ago by vbraun

  • Branch changed from public/16461 to 0380ead2db09b903f25ef9204ed8b2f1f66cfd20
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.