bug in difference_family(9,3)

[videlec]

Reported by N. Cohen

sage: designs.difference_family(9,3)
Traceback (most recent call last):
...
RuntimeError: 

CC: @nathanncohen

Component: combinatorial designs

Author: Vincent Delecroix

Branch/Commit: 09ea45b

Reviewer: Nathann Cohen

Issue created by migration from https://trac.sagemath.org/ticket/17528

[videlec]

Branch: u/vdelecroix/17528

[videlec]

Commit: e867d7c

[videlec]

New commits:

e867d7c

trac #17528: incoherences in difference families

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:2

Yop !

Hmmmm... To be honest I would sleep better if this constructor was turned into many functions, each of them checking that their input corresponds to the proved construction.... :-/

By the way why did you add a triple loop ? Why wouldn't you change the big doctest which begins with Other constructions for `\lambda > 1`:: with lambda>=1 instead ?

Nathann

[videlec]

comment:3

Replying to @nathanncohen:

Yop !

Hmmmm... To be honest I would sleep better if this constructor was turned into many functions, each of them checking that their input corresponds to the proved construction.... :-/

done

By the way why did you add a triple loop ? Why wouldn't you change the big doctest which begins with Other constructions for `\lambda > 1`:: with lambda>=1 instead ?

true

Vincent

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e867d7c to 1addcb8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1addcb8

trac #17528: modularization of difference_family

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:5

Hello !

I added a small commit at public/17528. Also, you did not change the big doctest to handle l=1, is there a reason ?

Nathann

[videlec]

Changed commit from 1addcb8 to 2846ea4

[videlec]

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

[videlec]

comment:6

Replying to @nathanncohen:

Hello !

I added a small commit at public/17528. Also, you did not change the big doctest to handle l=1, is there a reason ?

Just forgot... here it is (and with a clearer construction of the Wilson 1972 paper).

Vincent

---

New commits:

2b43b43	trac #17528: Merged with 6.5.beta4
8fd86c2	trac #17528: reviewer's commit
ff16c63	trac #17528: externalize Wilson construction of DF
2846ea4	trac #17528: list also lambda=1 constructions in DF

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:7

Hello !

Can you add your new function to the index, as well as some documentation for its existence/check parameters ?

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:8

Also: instead of checking that the cosets are disjoint like you do, wouldn't it be simpler/faster to:

1) Take all elements of A 2) Multiply it in any way possible (except by 1) and check that the result is not in A ?

It removes already_in and nb_seen.

Nathann

[videlec]

comment:9

Replying to @nathanncohen:

Also: instead of checking that the cosets are disjoint like you do, wouldn't it be simpler/faster to:

1) Take all elements of A 2) Multiply it in any way possible (except by 1) and check that the result is not in A ?

It removes already_in and nb_seen.

I do not think it works. What you need is to write all elements a_i of A as x^m i_k + j_k^ with j_k < m. Then you need to check that the j_k are different. A possible way to do it along your lines is the following:

AA = set(~x*y for x in A for y in A if x != y)
for i in range((v-1)//m):
    if x**(m*i) in AA:
        # bad case
# good case

You reduce the iteration over the whole K to iteration over Hm which is a bit smaller (it has size 2v/k). I will do that.

By the way, nb_seen was not needed. It was just to stop the loop as soon as all elements of A are decomposed (instead of enumerating the whole K). The same "trick" is actually used in singer_difference_set... the thing is that you know exactly what you are looking for but there is no better way to do it rather then iterating through the whole K.

Vincent

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

09ea45b

trac #17528: doc + optimization for cosets check

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2846ea4 to 09ea45b

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

Reviewer: Nathann Cohen

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:12

Okayyyyyyyyyyy !

Thanks for the fix+reorganisation !

Nathann

[videlec]

comment:13

Indeed. It was needed!

I hope I will have time for #16866 now.

Could you have a look at the almost combinatorial design ticket #17452?

Vincent

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:14

Could you have a look at the almost combinatorial design ticket #17452?

I don't know that class, but I can give it a try. Can you look at #17149 ? :-P

Nathann

[6bdad4c1-1e26-4f2f-a442-a01a2292c181]

comment:15

By the way there is one guy who was hired by Inria to work full-time on coding theory stuff... Where is he ? O_o

[vbraun]

Changed branch from public/17528 to 09ea45b