Difference families... and more BIBD

[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,...

[vdelecroix]

New commits:

​fa45dd3

trac #16461: difference families

[ncohen]

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

[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

[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

[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

[git]

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

​491d669

trac #16461: reviewer comment 1 ++

[vdelecroix]

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

[git]

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

​5d91e5f

trac #16461: more doc

[vdelecroix]

waiting for #16464 now.

[git]

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

[ncohen]

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

Nathann

[git]

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

​d3d6a31

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

[git]

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

​2638697

trac #16461: always check the difference family

[ncohen]

Hello !!

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

Nathann

[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

[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

[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

[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.

[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

[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

[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

[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

[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 ;-)

[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!!

[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

[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

[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.

[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.

[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

[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.

[ncohen]

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

[git]

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

​8b1e6ce

trac #16461: get rid of _nonzero_and_have_distinct_images

[ncohen]

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

Nathann

[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.

[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

[vdelecroix]

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

[ncohen]

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

[ncohen]

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

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​0380ead

trac #16461: fix documentation