Singer difference set and fix OA_9_135

[vdelecroix]

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

[git]

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

​ec6df26

trac #16597: Singer difference set

[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

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

• 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

[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

[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

[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

[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

[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

[git]

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

​449939b

trac #16597: more generic, more general way + doc

[vdelecroix]

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

[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

[git]

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

​f725726

trac #16597: add implementation for any d + doc

[vdelecroix]

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

Needs review.

Vincent

[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

@@ -117 +117 @@
       GAP's "design" package must be available in this case, and that it can be
       installed with the ``gap_packages`` spkg.
 
+    .. SEEALSO::
+
+        :func:`sage.combinat.designs.difference_family.are_projective_space_parameters`
+
     EXAMPLES:
 
     The points of the following design are the `\\frac {2^{2+1}-1} {2-1}=7`

src/sage/combinat/designs/difference_family.py

@@ -184 +184 @@
     - a boolean or, if ``return_parameters`` is set to ``True`` a pair
       ``(True, (q,d))`` or ``(False, (None,None))``.
 
+    .. SEEALSO::
+
+        :func:`sage.combinat.designs.block_design.ProjectiveGeometryDesign`
+
     EXAMPLES::
 
         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

[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

[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

[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

[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

[git]

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

​bd609fc	trac #16553: is_t_design
​11994ef	trac #16553: Review
​e7a97ea	trac #16553: doc fix + deprecation is_block_design
​3c0dd71	trac #16553v3: change .points() -> .ground_set()
​52b7177	trac #16553: merge sage 6.3.beta5
​0698433	trac #16553: deprecated alias .points() + fix
​7faff08	trac #16597: merge #16553
​aff5e44	trac #16617: echelon matrix iterator
​4e190d5	trac #16597: merge #16617
​46cd462	trac #16597: move parameter check in block_design.py

[git]

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

​f3cc9b7	trac #16617: cythonisation
​1d5ca53	trac #16617: doctest + remove part of the cache
​6908f39	trac #16617: change the name + doctest
​a2c71c3	trac #16597: merge updated #16617
​10c9beb	trac #16597: take care of the update #16617

[vdelecroix]

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

[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

[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

[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

[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 q^e+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,...z^d-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

[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

[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

[ncohen]

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

[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

[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

[vdelecroix]

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

Vincent

[vdelecroix]

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

[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

[ncohen]

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

Allahuuuuu Akbar !

Nathann

[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

[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

[ncohen]

(awaiting doc update)

[git]

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

​cc3e1df	trac #16597: merge 6.3.beta6
​ac4abab	trac #16597: more doc

[ncohen]

OKayyyyyyyyyyyyyyyyyyyyyyyyyyy.... !

Nathann