Opened 9 years ago
Closed 9 years ago
#16461 closed enhancement (fixed)
Difference families... and more BIBD
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.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: 
Description (last modified by )
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 9 years ago by
Branch:  → u/vdelecroix/16461 

Commit:  → fa45dd3df9317893e1fc0a2a4c4cbe1e0314c000 
Description:  modified (diff) 
Status:  new → needs_review 
comment:2 followup: 4 Changed 9 years ago by
Status:  needs_review → needs_work 

Wow. Coool to see something happend there ! Thanks for the work ! :)
Here is a firstpassreview.
 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 forgroup_law
 About
group_law
: I was telling Nicolas the other day how it would be more proper to have a categoryGroups()
which would be "any kind of group" and also have a "MultiplicativeGroups?()` category for ... well, multiplicative groups.
quadratic_residues
,quartic_residues
andcyclotomic_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. twolog(n)
computations.
difference_family
needs an INPUT section (and could be linked towardhttp://en.wikipedia.org/wiki/Difference_set
).
have_distinct_images
too
 Shouldn't
Return a `(k,l)`difference family
use "lambda" instead ? You use bothl
andlambda
in the docstring. I think I sawlambd
orlam
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 multiset 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]
overGF(5**4)
which may not be obvious.
 Languages should have builtin functions so that "{} times" becomes "{} time" when
{} == 1
:P
 why
DF_constructions[v][k,l]
instead ofDF_constructions[v,k,l]
?
 I still have not read/checked the main function, i.e.
difference_family
.
Nathann
comment:3 Changed 9 years ago by
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 followup: 5 Changed 9 years ago by
Replying to ncohen comment 2:
Wow. Coool to see something happend there ! Thanks for the work !
:)
Here is a firstpassreview.
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 categoryGroups()
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
andcyclotomic_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. twolog(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]
overGF(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 followup: 7 Changed 9 years ago by
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 integern
as input and return the squares modulon
. The ouptut are sageInteger
. So it does not fit very well as I need finite field which are not necessarily primes. Idem forcyclotomic_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 yourGF(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 9 years ago by
Commit:  fa45dd3df9317893e1fc0a2a4c4cbe1e0314c000 → 491d66957e3f92387f3db04e92914f359e2a35e2 

Branch pushed to git repo; I updated commit sha1. New commits:
491d669  trac #16461: reviewer comment 1 ++

comment:7 Changed 9 years ago by
Status:  needs_work → needs_review 

Problem1:
quadratic_residues
is already a function that takes an integern
as input and return the squares modulon
. The ouptut are sageInteger
. So it does not fit very well as I need finite field which are not necessarily primes. Idem forcyclotomic_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 yourGF(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 9 years ago by
Commit:  491d66957e3f92387f3db04e92914f359e2a35e2 → 5d91e5f398d7ddad0bfb9cb6952f3af493943b0d 

Branch pushed to git repo; I updated commit sha1. New commits:
5d91e5f  trac #16461: more doc

comment:9 Changed 9 years ago by
Dependencies:  → #16464 

Status:  needs_review → needs_work 
waiting for #16464 now.
comment:10 Changed 9 years ago by
Commit:  5d91e5f398d7ddad0bfb9cb6952f3af493943b0d → 2d12cc02dd29a47955b670df51beed44b569d2a0 

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
b903c4d  trac #16461: more doc

9b1544b  trac #16464: generic implementation

f0a2958  trac #16464: Docstring work

f0474bb  trac #16464: be more careful with errors

21cb1a8  trac #16464: handle correctly arguments for cyclotomic_cosets

b07ad01  trac #16464: Second review

136e870  trac #16464: tiny improvements for is_a_splitting

965f550  trac #16464: replace bool(S1&S2) by S1.isdisjoint(S2)

9b199c7  trac #16461: merge #16464

2d12cc0  trac #16461: adapt the implementation with #16464

comment:11 Changed 9 years ago by
Status:  needs_work → needs_review 

comment:13 Changed 9 years ago by
Commit:  2d12cc02dd29a47955b670df51beed44b569d2a0 → d3d6a31efd1ec23afa311c51a437253a4b8f1628 

Branch pushed to git repo; I updated commit sha1. New commits:
d3d6a31  trac #16461: reset finite_field_base.pyx to its previous state

comment:14 Changed 9 years ago by
Commit:  d3d6a31efd1ec23afa311c51a437253a4b8f1628 → 263869795e1c6e6af4a44045b4275b0911aef2eb 

Branch pushed to git repo; I updated commit sha1. New commits:
2638697  trac #16461: always check the difference family

comment:15 Changed 9 years ago by
Hello !!
Is if l == (k1):
equivalent to if (v1)%k == 0
?
Nathann
comment:16 followup: 17 Changed 9 years ago by
No. None of the one implies the other.
Assume l(v1) % (k(k1)) == 0
. Then:
 if
l = k1
thenv1
is can be any multiple ofk
 if
v1 = k(k1)
thenl
is arbitrary
Vincent
comment:17 followup: 19 Changed 9 years ago by
Yoooooooooooo !
No. None of the one implies the other.
Assume
l(v1) % (k(k1)) == 0
. Then, for example:
 if
l = k(k1)
thenv
is arbitrary if
v1 = k(k1)
thenl
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 "(v1)%k == 0 and l%(k1) == 0
" ? In which case we could return "several times the same difference family" if l
is equal to 2(k1)
?
Nathann
comment:18 Changed 9 years ago by
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 followup: 21 Changed 9 years ago by
Replying to ncohen:
Yoooooooooooo !
No. None of the one implies the other.
Assume
l(v1) % (k(k1)) == 0
. Then, for example:
 if
l = k(k1)
thenv
is arbitrary if
v1 = k(k1)
thenl
is arbitraryYesyesyes. 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 "(v1)%k == 0 and l%(k1) == 0
" ? In which case we could return "several times the same difference family" ifl
is equal to2(k1)
?
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 semigroup of the integers... it is more than just stable under multiplication.
comment:20 followup: 25 Changed 9 years ago by
Instead of this
_nonzero_and_have_distinct_images((r**jone for j in xrange(1,m+1)), to_coset)
Couldn't you do that ?
things = [r**jone 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 followup: 23 Changed 9 years ago by
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 9 years ago by
Status:  needs_review → needs_info 

comment:23 followup: 24 Changed 9 years ago by
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 groupdesigns.abelian_difference_family(invariants, k, lambda)
: we care
Vincent
comment:24 followup: 26 Changed 9 years ago by
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 groupdesigns.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 followup: 27 Changed 9 years ago by
Replying to ncohen:
Instead of this
_nonzero_and_have_distinct_images((r**jone for j in xrange(1,m+1)), to_coset)Couldn't you do that ?
things = [r**jone 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 followup: 28 Changed 9 years ago by
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 groupdesigns.abelian_difference_family(invariants, k, lambda)
: we careI 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 followup: 30 Changed 9 years ago by
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 theK.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 followup: 29 Changed 9 years ago by
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 followup: 31 Changed 9 years ago by
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 Changed 9 years ago by
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.
comment:31 followup: 32 Changed 9 years ago by
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 Changed 9 years ago by
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 9 years ago by
Reviewers:  → 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 9 years ago by
Commit:  263869795e1c6e6af4a44045b4275b0911aef2eb → 8b1e6cefc5d2bae89d9a23c75a78e558ef6d3826 

Branch pushed to git repo; I updated commit sha1. New commits:
8b1e6ce  trac #16461: get rid of _nonzero_and_have_distinct_images

comment:35 Changed 9 years ago by
Status:  needs_info → needs_review 

comment:36 Changed 9 years ago by
Why don't you need to test equality with 0 for the first construction ?
Nathann
comment:37 Changed 9 years ago by
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((v1)//m)]
) is automatically requested and you want that all the other differences belong to cosets distinct from it.
comment:38 Changed 9 years ago by
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 followup: 40 Changed 9 years ago by
Then bibds.py
? covering_designs.py
? block_designs.py
? When do we put an s
and when we do not?
comment:40 Changed 9 years ago by
Status:  needs_review → positive_review 

Then
bibds.py
?covering_designs.py
?block_designs.py
? When do we put ans
and when we do not?
Well, all new files have an 's'. Okay, doesn't matter.
Nathann
comment:41 Changed 9 years ago by
Dependencies:  #16464 → #16464,#16391 

comment:42 Changed 9 years ago by
Dependencies:  #16464,#16391 → #16391 

comment:43 Changed 9 years ago by
Dependencies:  #16391 → #16464 

comment:44 Changed 9 years ago by
Branch:  u/vdelecroix/16461 → public/16461 

Commit:  8b1e6cefc5d2bae89d9a23c75a78e558ef6d3826 → ee3b03584f8a60e892734193793dc1c20b6007c0 
Dependencies:  #16464 → #16464, #16391 
Last 10 new commits:
90f828f  trac #16391: use OrthogonalArrayBlockGraph instead of OrthogonalArrayGraph

6e3c685  trac #16391: reviewer's comments

52c2de8  trac #16391: Removing the holes

d0885f7  trac #16391: bugfix

c1de597  trac #16391: doc clean + remove some list construction

41a9a24  trac #16391: Typo

42239cc  trac #16391: Undoing stuff

24ac3a8  trac #16391: Broken doc

70c9805  trac #16391: Merged with #16460

ee3b035  trac #16461: Merged with #16391

comment:45 Changed 9 years ago by
Commit:  ee3b03584f8a60e892734193793dc1c20b6007c0 → 0380ead2db09b903f25ef9204ed8b2f1f66cfd20 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
0380ead  trac #16461: fix documentation

comment:46 Changed 9 years ago by
Status:  needs_review → positive_review 

comment:47 Changed 9 years ago by
Branch:  public/16461 → 0380ead2db09b903f25ef9204ed8b2f1f66cfd20 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
trac #16461: difference families