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:  sage6.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
 Branch set to u/vdelecroix/16597
 Cc ncohen added
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
 Commit set to ec6df26f4d72c5eb939a9b02cd3ad809feacb105
comment:3 Changed 7 years ago by
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 followup: ↓ 5 Changed 7 years ago by
 Status changed from needs_review to needs_work
 In
OA_9_135
you remove the definition ofPG2 = 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^31)/(q1)=q^2+q+1
lines ? Either wayGF(q)
is not an integer.
+ spaces/.
Kq (i.e the (q1)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 aBIBD.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 ; followup: ↓ 6 Changed 7 years ago by
Replying to ncohen:
 In
OA_9_135
you remove the definition ofPG2 = 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^31)/(q1)=q^2+q+1
lines ? Either wayGF(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 (q1)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 aBIBD.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
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 overGF(q)
. The very same way you would speak aboutRR
lines inCC
. 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
Sorry, my last comment above is incorrect : what you need is a 2plane defined by the set of 1space it contains, and the group action which sends a 1space on another 1space by multiplication.
Nathann
comment:8 followup: ↓ 9 Changed 7 years ago by
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
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 2plane is defined by the 1lines it contains, and the action is an action on 1lines (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
 Commit changed from ec6df26f4d72c5eb939a9b02cd3ad809feacb105 to 449939b4c19f235f1fd628e337d5ec3b50f92523
Branch pushed to git repo; I updated commit sha1. New commits:
449939b  trac #16597: more generic, more general way + doc

comment:11 followup: ↓ 12 Changed 7 years ago by
 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
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
 Commit changed from 449939b4c19f235f1fd628e337d5ec3b50f92523 to f725726fa68094215f1d4e19fac2378c0c29d3e8
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

comment:14 Changed 7 years ago by
All right. Go back to the previous implementation and keep it working in any dimension.
Needs review.
Vincent
comment:15 followup: ↓ 16 Changed 7 years ago by
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 thatv,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): 117 117 GAP's "design" package must be available in this case, and that it can be 118 118 installed with the ``gap_packages`` spkg. 119 119 120 .. SEEALSO:: 121 122 :func:`sage.combinat.designs.difference_family.are_projective_space_parameters` 123 120 124 EXAMPLES: 121 125 122 126 The points of the following design are the `\\frac {2^{2+1}1} {21}=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): 184 184  a boolean or, if ``return_parameters`` is set to ``True`` a pair 185 185 ``(True, (q,d))`` or ``(False, (None,None))``. 186 186 187 .. SEEALSO:: 188 189 :func:`sage.combinat.designs.block_design.ProjectiveGeometryDesign` 190 187 191 EXAMPLES:: 188 192 189 193 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 ; followup: ↓ 17 Changed 7 years ago by
Hi,
 In the doc of
are_projective_space_parameters
you give the equations thatv,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 tdesign 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^(d1))
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
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 tdesign parameters of projective geometry designs fit what
are_projective_space_parameters
check for. Actually, it would make sense to moveare_projective_space_parameters
toblock_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 overGF(q)
of(1,z,...,z^(d1))
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 modc
(the relative Conway polynomial), but it seems the easiest way to go.
T_T
Nathann
comment:18 followup: ↓ 19 Changed 7 years ago by
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
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 rewriteProjectiveGeometryDesign
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
 Dependencies set to #16553,#16617
 Status changed from needs_review to needs_work
comment:21 Changed 7 years ago by
 Commit changed from f725726fa68094215f1d4e19fac2378c0c29d3e8 to 46cd4622a9777284fb6e3bf7d21ebf90680e7954
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

comment:22 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:23 Changed 7 years ago by
 Commit changed from 46cd4622a9777284fb6e3bf7d21ebf90680e7954 to 10c9beb0a672b3b5c628d7b206b6dbc49aae5848
comment:24 Changed 7 years ago by
Rebased on the updated #16617... needs review again.
comment:25 followup: ↓ 26 Changed 6 years ago by
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
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 followup: ↓ 28 Changed 6 years ago by
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^(d1)) 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 ; followup: ↓ 29 Changed 6 years ago by
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^(d1)) 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^{d1}. 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 ; followup: ↓ 30 Changed 6 years ago by
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
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
(don't forget my small commit on public/16597
)
comment:32 followup: ↓ 33 Changed 6 years ago by
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^d1))
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
comment:33 in reply to: ↑ 32 Changed 6 years ago by
There is just a subtlety that I did not tell you. If you follow my words you have "too much" integers
i
(if you havez^i
you also havez^(i + n*(q^(e+1)1)/(q^d1))
or in other words the elementz^i x
withx
inKsmall
). If you only store the smallesti
as I did, everything is fine since you start to see two points on the sameKsmall
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 followup: ↓ 36 Changed 6 years ago by
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 followup: ↓ 37 Changed 6 years ago by
Hopefully: "There exists an efficient quantum algorithm due to Peter Shor!" (from wikipedia)
comment:36 in reply to: ↑ 34 Changed 6 years ago by
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
Hopefully: "There exists an efficient quantum algorithm due to Peter Shor!" (from wikipedia)
Allahuuuuu Akbar !
Nathann
comment:38 Changed 6 years ago by
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
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
 Status changed from needs_review to needs_work
(awaiting doc update)
comment:41 Changed 6 years ago by
 Commit changed from 10c9beb0a672b3b5c628d7b206b6dbc49aae5848 to ac4abab21cecffc01ff91dff40e8442fda10a9d1
comment:42 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:43 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
OKayyyyyyyyyyyyyyyyyyyyyyyyyyy.... !
Nathann
comment:44 Changed 6 years ago by
 Branch changed from u/vdelecroix/16597 to ac4abab21cecffc01ff91dff40e8442fda10a9d1
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #16597: Singer difference set