Opened 7 years ago

Closed 6 years ago

#16597 closed enhancement (fixed)

Singer difference set and fix OA_9_135

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: ac4abab (Commits) Commit: ac4abab21cecffc01ff91dff40e8442fda10a9d1
Dependencies: #16553,#16617 Stopgaps:

Description

Add a function to build Singer difference set (cyclic difference set using finite projective planes).

At the same time we fix a bug in OA_9_135...

Change History (44)

comment:1 Changed 7 years ago by vdelecroix

  • Branch set to u/vdelecroix/16597
  • Cc ncohen added
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by git

  • Commit set to ec6df26f4d72c5eb939a9b02cd3ad809feacb105

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

ec6df26trac #16597: Singer difference set

comment:3 Changed 7 years ago by ncohen

I don't get your function is_projective_plane_cardinality. The doc of sqrtrem seems to say that q is the largest integer such that q^2<=n. Why do you increase q in a while loop ?

Nathann

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

  • Status changed from needs_review to needs_work
  • In OA_9_135 you remove the definition of PG2 = set([x*39 for x in range(7)]) but it still appears in the documentation. And it is nice to have an object representing that to describe more clearly what the function does.

And you repeat this %39 everywhere right now.

  • The set of `GF(q)` lines in `V` is a projective plane. The set of (q^3-1)/(q-1)=q^2+q+1 lines ? Either way GF(q) is not an integer.
  • + spaces/.
  • Kq (i.e the (q-1)-th root of unity
  • About the second part of function singer_difference_set : what would you think of implementing 3.16 instead ? It builds the cyclic difference set from a cyclic automorphism of a BIBD... And it could be useful later, like when we will have a BIBD.is_cyclic function.

Which we can write easily now that BIBD are a class :-D

sage: def is_cyclic(BIBD):
....:     repr = BIBD.automorphism_group().conjugacy_classes_representatives()
....:     repr = [x.cycles() for x in repr]
....:     for x in repr:
....:         if len(x) == 1 and len(x[0].tuple()) == BIBD.num_points():
....:             return x[0].tuple()
....:     return False
sage: is_cyclic(designs.balanced_incomplete_block_design(13,3))
(1, 9, 8, 7, 12, 10, 5, 2, 11, 3, 0, 4, 6)

Nathann

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

Replying to ncohen:

  • In OA_9_135 you remove the definition of PG2 = set([x*39 for x in range(7)]) but it still appears in the documentation. And it is nice to have an object representing that to describe more clearly what the function does.

And you repeat this %39 everywhere right now.

I will put it back if you prefer. I just remarked that I removed an important comment about PG2 being the set of points = 0 mod 39.

But note that it is faster to test "x%39 == 0" rather than building PG2 and then test "x in PG2".

  • The set of `GF(q)` lines in `V` is a projective plane. The set of (q^3-1)/(q-1)=q^2+q+1 lines ? Either way GF(q) is not an integer.

No, GF(q) is not a number but a field. It refers to line as line in a vector space over GF(q). The very same way you would speak about RR lines in CC. Isn't that clear enough?

  • + spaces/.
  • Kq (i.e the (q-1)-th root of unity
  • About the second part of function singer_difference_set : what would you think of implementing 3.16 instead ? It builds the cyclic difference set from a cyclic automorphism of a BIBD... And it could be useful later, like when we will have a BIBD.is_cyclic function.

It is stupid. You will have to first build the projective space, then compute its automorphism group that we already know and then apply a big hammer.

Vincent

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

I will put it back if you prefer. I just remarked that I removed an important comment about PG2 being the set of points = 0 mod 39.

Your commit does not seem to remove any comment O_o

But note that it is faster to test "x%39 == 0" rather than building PG2 and then test "x in PG2".

I know I know, but for such functions I gladly exchange a clear code against a speedup. Which I expect is not so bad...

You can remove this PG2 if you want but then you must change the explanation accordingly !

No, GF(q) is not a number but a field. It refers to line as line in a vector space over GF(q). The very same way you would speak about RR lines in CC. Isn't that clear enough?

Oh. I never said "RR lines in CC", but I get it know. I expected to see the number of lines there.

Given that the base field is GF(q) just talking about lines is clear enough though, isn't it ? You can leave it like that if you want, I am not used to talk of "RR lines in CC", that's all.

It is stupid.

Now try to think : you don't have to USE is_cyclic in your function. You have the base block, i.e. GF(q)-0 in GF(q^3)-0, and you can define the automorphism on GF(q^3)-0 with your generator. You don't have to build the projective plane nor to compute its group, BUT you can use theorem 3.16 exactly as it is done in the book, by providing the base block and a cyclic action on the ground set. 3.16 just does a relabelling.

Nathann

comment:7 Changed 7 years ago by ncohen

Sorry, my last comment above is incorrect : what you need is a 2-plane defined by the set of 1-space it contains, and the group action which sends a 1-space on another 1-space by multiplication.

Nathann

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

Moreover, the set of points is not the vector space but the quotient of V \ {0} by scalar multiplication. So the strategy of theorem 3.16 does not apply directly.

Nevertheless, it would be nice to have 3.16 done somewhere! But I am not sure that this ticket is the right place.

Vincent

comment:9 in reply to: ↑ 8 Changed 7 years ago by ncohen

Moreover, the set of points is not the vector space but the quotient of V \ {0} by scalar multiplication. So the strategy of theorem 3.16 does not apply directly.

That's what I said in the comment above : the 2-plane is defined by the 1-lines it contains, and the action is an action on 1-lines (which is just a multiplication).

Nevertheless, it would be nice to have 3.16 done somewhere! But I am not sure that this ticket is the right place.

Given that you already implemented a specific case of it, I just thought I would bring it up ...

Nathann

comment:10 Changed 7 years ago by git

  • Commit changed from ec6df26f4d72c5eb939a9b02cd3ad809feacb105 to 449939b4c19f235f1fd628e337d5ec3b50f92523

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

449939btrac #16597: more generic, more general way + doc

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

  • Status changed from needs_work to needs_review

Hi Nathann,

I did what you think was better, but I just find it ugly. At least, I did something good: it now work for any dimension. And it needs review!

Vincent

comment:12 in reply to: ↑ 11 Changed 7 years ago by ncohen

Yo !

I did what you think was better, but I just find it ugly.

Yeah I agree.. What the function does is not very clear indeed. Plus I am not convinced that it is really a "Difference Set" function. It could be more a BIBD function, or just a Incidence Structure relabelling function.. We can go back to your previous commit if you prefer, no problem.

Nathann

comment:13 Changed 7 years ago by git

  • Commit changed from 449939b4c19f235f1fd628e337d5ec3b50f92523 to f725726fa68094215f1d4e19fac2378c0c29d3e8

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f725726trac #16597: add implementation for any d + doc

comment:14 Changed 7 years ago by vdelecroix

All right. Go back to the previous implementation and keep it working in any dimension.

Needs review.

Vincent

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

Hello again !

Sorry but it still is a bit hard for me to read those explanations and I go slowly, it isn't really my world ^^;

  • In the doc of are_projective_space_parameters you give the equations that v,k,lmbda must satisfy, but could you say it "with words" before that ? Something like "such that the projective geometry of parameters xx,xx,xx is a xx,xx,xx design ?"
  • I had begun to write a commit linking this function with ProjectiveGeometryDesign but I did not know enough to finish the review ^^;
  • src/sage/combinat/designs/block_design.py

    diff --git a/src/sage/combinat/designs/block_design.py b/src/sage/combinat/designs/block_design.py
    a b def ProjectiveGeometryDesign(n, d, F, algorithm=None): 
    117117      GAP's "design" package must be available in this case, and that it can be
    118118      installed with the ``gap_packages`` spkg.
    119119
     120    .. SEEALSO::
     121
     122        :func:`sage.combinat.designs.difference_family.are_projective_space_parameters`
     123
    120124    EXAMPLES:
    121125
    122126    The points of the following design are the `\\frac {2^{2+1}-1} {2-1}=7`
  • src/sage/combinat/designs/difference_family.py

    diff --git a/src/sage/combinat/designs/difference_family.py b/src/sage/combinat/designs/difference_family.py
    a b def are_projective_space_parameters(v, k, lmbda, return_parameters=False): 
    184184    - a boolean or, if ``return_parameters`` is set to ``True`` a pair
    185185      ``(True, (q,d))`` or ``(False, (None,None))``.
    186186
     187    .. SEEALSO::
     188
     189        :func:`sage.combinat.designs.block_design.ProjectiveGeometryDesign`
     190
    187191    EXAMPLES::
    188192
    189193        sage: from sage.combinat.designs.difference_family import are_projective_space_parameters
  • I do not understand the code yet, but don't you want to use the 'conway=True trick in singer_difference_set` ?

Nathann

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

Hi,

  • In the doc of are_projective_space_parameters you give the equations that v,k,lmbda must satisfy, but could you say it "with words" before that ? Something like "such that the projective geometry of parameters xx,xx,xx is a xx,xx,xx design ?"

will do: these are the parameters of a projective space design (assuming that they only exists for prime powers ;-)

  • I had begun to write a commit linking this function with ProjectiveGeometryDesign but I did not know enough to finish the review ^^;

Yeah it would be cool to check the t-design parameters of projective geometry designs fit what are_projective_space_parameters check for. Actually, it would make sense to move are_projective_space_parameters to block_design.py. What do you think?

  • I do not understand the code yet, but don't you want to use the 'conway=True trick in singer_difference_set` ?

Nope. I need relative extensions GF(q) -> GF(q^(d+1)). The trick would only "work" for prime fields. Moreover, testing if an element of an extension belongs to the span over GF(q) of (1,z,...,z^(d-1)) is a mess (and trivial if you deal directly with polyonials).

I agree that I mimic an extension of GF(q) by dealing with polynomials mod c (the relative Conway polynomial), but it seems the easiest way to go.

Vincent

comment:17 in reply to: ↑ 16 Changed 7 years ago by ncohen

Yo !

will do: these are the parameters of a projective space design (assuming that they only exists for prime powers ;-)

Also : don't we use at the same time "projective space design" and "projective geometry design" ?

Yeah it would be cool to check the t-design parameters of projective geometry designs fit what are_projective_space_parameters check for. Actually, it would make sense to move are_projective_space_parameters to block_design.py. What do you think?

+1

Nope. I need relative extensions GF(q) -> GF(q^(d+1)). The trick would only "work" for prime fields. Moreover, testing if an element of an extension belongs to the span over GF(q) of (1,z,...,z^(d-1)) is a mess (and trivial if you deal directly with polyonials).

I agree that I mimic an extension of GF(q) by dealing with polynomials mod c (the relative Conway polynomial), but it seems the easiest way to go.

T_T

Nathann

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

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

All right, I will change *projective_space* to `*projective_geometry*".

Haaarg... but currently the ProjectiveGeometryDesign is so stupdly implemented that it takes hours to generate anything interesting!! And I remember that I already rewrote that in #16552. Do you agree that I rewrite ProjectiveGeometryDesign to just work here (but I will not change the behavior of anything right now)?

Vincent

comment:19 in reply to: ↑ 18 Changed 7 years ago by ncohen

Haaarg... but currently the ProjectiveGeometryDesign is so stupdly implemented that it takes hours to generate anything interesting!! And I remember that I already rewrote that in #16552. Do you agree that I rewrite ProjectiveGeometryDesign to just work here (but I will not change the behavior of anything right now)?

Yeahyeah good idea !

Nathann

comment:20 Changed 7 years ago by vdelecroix

  • Dependencies set to #16553,#16617
  • Status changed from needs_review to needs_work

comment:21 Changed 7 years ago by git

  • Commit changed from f725726fa68094215f1d4e19fac2378c0c29d3e8 to 46cd4622a9777284fb6e3bf7d21ebf90680e7954

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

bd609fctrac #16553: is_t_design
11994eftrac #16553: Review
e7a97eatrac #16553: doc fix + deprecation is_block_design
3c0dd71trac #16553v3: change .points() -> .ground_set()
52b7177trac #16553: merge sage 6.3.beta5
0698433trac #16553: deprecated alias .points() + fix
7faff08trac #16597: merge #16553
aff5e44trac #16617: echelon matrix iterator
4e190d5trac #16597: merge #16617
46cd462trac #16597: move parameter check in block_design.py

comment:22 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:23 Changed 7 years ago by git

  • Commit changed from 46cd4622a9777284fb6e3bf7d21ebf90680e7954 to 10c9beb0a672b3b5c628d7b206b6dbc49aae5848

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

f3cc9b7trac #16617: cythonisation
1d5ca53trac #16617: doctest + remove part of the cache
6908f39trac #16617: change the name + doctest
a2c71c3trac #16597: merge updated #16617
10c9bebtrac #16597: take care of the update #16617

comment:24 Changed 7 years ago by vdelecroix

Rebased on the updated #16617... needs review again.

comment:25 follow-up: Changed 6 years ago by ncohen

Hello !

I added a commit public/16597 but I do not understand the code as it is written, so I cannot much more. It seems to work indeed, but I don't get the maths behind.

Nathann

comment:26 in reply to: ↑ 25 Changed 6 years ago by vdelecroix

Replying to ncohen:

Hello !

I added a commit public/16597 but I do not understand the code as it is written, so I cannot much more. It seems to work indeed, but I don't get the maths behind.

I can try to explain (in these comments and inside the code), could you be more precise?

Vincent

comment:27 follow-up: Changed 6 years ago by ncohen

Basically, I don't get why doint this does the job

+    # now compute the set of i such that z^i belongs to the subspace spanned by
+    # (1,z,z^2,...,z^(d-1)) over GF(q) (up to the action of scalar
+    # multiplication)

And it isn't exactly the way it is explained in Stinson's book either I believe..

Nathann

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

Replying to ncohen:

Basically, I don't get why doint this does the job

+    # now compute the set of i such that z^i belongs to the subspace spanned by
+    # (1,z,z^2,...,z^(d-1)) over GF(q) (up to the action of scalar
+    # multiplication)

And it isn't exactly the way it is explained in Stinson's book either I believe..

It follows Stinson but the loop is stopped sooner.

The field Kbig with qe+1 elements is a vector space over Ksmall the one with q elements. We chose a generator z of the multiplicative group of Kbig (that way we have a cyclic action on lines). We also choose a concrete subspace of dimension d in Kbig to be the span (over Ksmall) of 1,z,...zd-1. Let call it V this subspace.

The difference set is by definition the set of integers i such that z^i belong to V (recall that any element of Kbig different from 0 can be written as z^i with i < q^e).

This is what Stinson does and this is what I am doing.

Vincent

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

This is what Stinson does and this is what I am doing.

Oh I see it now, very cool ! Plus you really generate very few objects. Coud you add those explanations in the doc/code ?

Nathann

comment:30 in reply to: ↑ 29 Changed 6 years ago by vdelecroix

Replying to ncohen:

This is what Stinson does and this is what I am doing.

Oh I see it now, very cool ! Plus you really generate very few objects. Coud you add those explanations in the doc/code ?

Of course, I will.

Vincent

comment:31 Changed 6 years ago by ncohen

(don't forget my small commit on public/16597)

comment:32 follow-up: Changed 6 years ago by vdelecroix

There is just a subtlety that I did not tell you. If you follow my words you have "too much" integers i (if you have z^i you also have z^(i + n*(q^(e+1)-1)/(q^d-1)) or in other words the element z^i x with x in Ksmall). If you only store the smallest i as I did, everything is fine since you start to see two points on the same Ksmall-line only after you see all the lines in Kbig at least once...

Vincent

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

comment:33 in reply to: ↑ 32 Changed 6 years ago by ncohen

There is just a subtlety that I did not tell you. If you follow my words you have "too much" integers i (if you have z^i you also have z^(i + n*(q^(e+1)-1)/(q^d-1)) or in other words the element z^i x with x in Ksmall). If you only store the smallest i as I did, everything is fine since you start to see two points on the same Ksmall-line only after you see all the lines least once...

I see, I see. Could you also put it in the doc ? By the way, shouldn't there be a field function somewhere that gives you the logarithm of a field element with respect to z ? Something that would be more efficient than enumeration ?

Nathann

comment:34 follow-up: Changed 6 years ago by vdelecroix

It is a very hard thing to compute the logarithm: http://en.wikipedia.org/wiki/Discrete_logarithm (it is used for cryptography).

Vincent

comment:35 follow-up: Changed 6 years ago by vdelecroix

Hopefully: "There exists an efficient quantum algorithm due to Peter Shor!" (from wikipedia)

comment:36 in reply to: ↑ 34 Changed 6 years ago by ncohen

It is a very hard thing to compute the logarithm: http://en.wikipedia.org/wiki/Discrete_logarithm (it is used for cryptography).

1) You are already computing a logarithm, so it is at most as hard as a for loop. It is only "hard" because these guys measure complexity with respect to log(n)

2) It is "hard" to factor stuff, yet there is something "more efficient" that trying all integers smaller than n (stop at sqrt(n))

3) It is exactly because it is a useful operation that we should have a function for it. Of course it's not our job to implement it but perhaps we should have a simple way to do that in Sage ?... O_o

Nathann

comment:37 in reply to: ↑ 35 Changed 6 years ago by ncohen

Hopefully: "There exists an efficient quantum algorithm due to Peter Shor!" (from wikipedia)

Allahuuuuu Akbar !

Nathann

comment:38 Changed 6 years ago by vdelecroix

If you want to compute the logarithm of a bunch of numbers I am not sure there is something better than trial multiplication... and doing it for each element of your set is definitely a bad idea.

Vincent

comment:39 Changed 6 years ago by ncohen

I am pretty sure I studied this at the University

sage: sage.groups.generic.bsgs

I forgot all of it, though... But I guess it shouldn't be a standalone function like that.

Nathann

comment:40 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

(awaiting doc update)

comment:41 Changed 6 years ago by git

  • Commit changed from 10c9beb0a672b3b5c628d7b206b6dbc49aae5848 to ac4abab21cecffc01ff91dff40e8442fda10a9d1

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

cc3e1dftrac #16597: merge 6.3.beta6
ac4ababtrac #16597: more doc

comment:42 Changed 6 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:43 Changed 6 years ago by ncohen

  • Reviewers set to Nathann Cohen
  • Status changed from needs_review to positive_review

OKayyyyyyyyyyyyyyyyyyyyyyyyyyy.... !

Nathann

comment:44 Changed 6 years ago by vbraun

  • Branch changed from u/vdelecroix/16597 to ac4abab21cecffc01ff91dff40e8442fda10a9d1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.