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: | 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: |
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 follow-up: 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 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 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 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]
overGF(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 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 follow-up: 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 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 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 follow-up: 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 == (k-1):
equivalent to if (v-1)%k == 0
?
Nathann
comment:16 follow-up: 17 Changed 9 years ago by
No. None of the one implies the other.
Assume l(v-1) % (k(k-1)) == 0
. Then:
- if
l = k-1
thenv-1
is can be any multiple ofk
- if
v-1 = k(k-1)
thenl
is arbitrary
Vincent
comment:17 follow-up: 19 Changed 9 years ago by
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)
thenv
is arbitrary- if
v-1 = k(k-1)
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 "(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 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 follow-up: 21 Changed 9 years ago by
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)
thenv
is arbitrary- if
v-1 = k(k-1)
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 "(v-1)%k == 0 and l%(k-1) == 0
" ? In which case we could return "several times the same difference family" ifl
is equal to2(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.
comment:20 follow-up: 25 Changed 9 years ago by
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 follow-up: 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 follow-up: 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 follow-up: 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 follow-up: 27 Changed 9 years ago by
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 follow-up: 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 follow-up: 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 follow-up: 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 follow-up: 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 follow-up: 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((v-1)//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 follow-up: 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