Sage: Ticket #16597: Singer difference set and fix OA_9_135
https://trac.sagemath.org/ticket/16597
<p>
Add a function to build Singer difference set (cyclic difference set using finite projective planes).
</p>
<p>
At the same time we fix a bug in OA_9_135...
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16597
Trac 1.1.6vdelecroixTue, 01 Jul 2014 08:37:03 GMTstatus changed; cc, branch set
https://trac.sagemath.org/ticket/16597#comment:1
https://trac.sagemath.org/ticket/16597#comment:1
<ul>
<li><strong>cc</strong>
<em>ncohen</em> added
</li>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>u/vdelecroix/16597</em>
</li>
</ul>
TicketgitTue, 01 Jul 2014 08:39:54 GMTcommit set
https://trac.sagemath.org/ticket/16597#comment:2
https://trac.sagemath.org/ticket/16597#comment:2
<ul>
<li><strong>commit</strong>
set to <em>ec6df26f4d72c5eb939a9b02cd3ad809feacb105</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ec6df26f4d72c5eb939a9b02cd3ad809feacb105"><span class="icon"></span>ec6df26</a></td><td><code>trac #16597: Singer difference set</code>
</td></tr></table>
TicketncohenTue, 01 Jul 2014 10:06:42 GMT
https://trac.sagemath.org/ticket/16597#comment:3
https://trac.sagemath.org/ticket/16597#comment:3
<p>
I don't get your function <code>is_projective_plane_cardinality</code>. The doc of <code>sqrtrem</code> seems to say that <code>q</code> is the largest integer such that <code>q^2<=n</code>. Why do you increase <code>q</code> in a while loop ?
</p>
<p>
Nathann
</p>
TicketncohenTue, 01 Jul 2014 11:22:52 GMTstatus changed
https://trac.sagemath.org/ticket/16597#comment:4
https://trac.sagemath.org/ticket/16597#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<ul><li>In <code>OA_9_135</code> you remove the definition of <code>PG2 = set([x*39 for x in range(7)])</code> 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.
</li></ul><blockquote>
<p>
And you repeat this %39 everywhere right now.
</p>
</blockquote>
<ul><li><code>The set of `GF(q)` lines in `V` is a projective plane</code>. The set of <code>(q^3-1)/(q-1)=q^2+q+1</code> lines ? Either way <code>GF(q)</code> is not an integer.
</li></ul><ul><li><code>+ spaces/.</code>
</li></ul><ul><li><code> Kq (i.e the (q-1)-th root of unity</code>
</li></ul><ul><li>About the second part of function <code>singer_difference_set</code> : 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 <code>BIBD.is_cyclic</code> function.
</li></ul><p>
Which we can write easily now that BIBD are a class <code>:-D</code>
</p>
<pre class="wiki">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)
</pre><p>
Nathann
</p>
TicketvdelecroixTue, 01 Jul 2014 11:49:08 GMT
https://trac.sagemath.org/ticket/16597#comment:5
https://trac.sagemath.org/ticket/16597#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16597#comment:4" title="Comment 4">ncohen</a>:
</p>
<blockquote class="citation">
<ul><li>In <code>OA_9_135</code> you remove the definition of <code>PG2 = set([x*39 for x in range(7)])</code> 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.
</li></ul><blockquote>
<p>
And you repeat this %39 everywhere right now.
</p>
</blockquote>
</blockquote>
<p>
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.
</p>
<p>
But note that it is faster to test "x%39 == 0" rather than building PG2 and then test "x in PG2".
</p>
<blockquote class="citation">
<ul><li><code>The set of `GF(q)` lines in `V` is a projective plane</code>. The set of <code>(q^3-1)/(q-1)=q^2+q+1</code> lines ? Either way <code>GF(q)</code> is not an integer.
</li></ul></blockquote>
<p>
No, <code>GF(q)</code> is not a number but a field. It refers to line as line in a vector space over <code>GF(q)</code>. The very same way you would speak about <code>RR</code> lines in <code>CC</code>. Isn't that clear enough?
</p>
<blockquote class="citation">
<ul><li><code>+ spaces/.</code>
</li><li><code> Kq (i.e the (q-1)-th root of unity</code>
</li></ul><ul><li>About the second part of function <code>singer_difference_set</code> : 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 <code>BIBD.is_cyclic</code> function.
</li></ul></blockquote>
<p>
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.
</p>
<p>
Vincent
</p>
TicketncohenTue, 01 Jul 2014 11:56:53 GMT
https://trac.sagemath.org/ticket/16597#comment:6
https://trac.sagemath.org/ticket/16597#comment:6
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Your commit does not seem to remove any comment <code>O_o</code>
</p>
<blockquote class="citation">
<p>
But note that it is faster to test "x%39 == 0" rather than building PG2 and then test "x in PG2".
</p>
</blockquote>
<p>
I know I know, but for such functions I gladly exchange a clear code against a speedup. Which I expect is not so bad...
</p>
<p>
You can remove this PG2 if you want but then you must change the explanation accordingly !
</p>
<blockquote class="citation">
<p>
No, <code>GF(q)</code> is not a number but a field. It refers to line as line in a vector space over <code>GF(q)</code>. The very same way you would speak about <code>RR</code> lines in <code>CC</code>. Isn't that clear enough?
</p>
</blockquote>
<p>
Oh. I never said "RR lines in CC", but I get it know. I expected to see the number of lines there.
</p>
<p>
Given that the base field is <code>GF(q)</code> 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.
</p>
<blockquote class="citation">
<p>
It is stupid.
</p>
</blockquote>
<p>
Now try to think : you don't have to USE <code>is_cyclic</code> in your function. You have the base block, i.e. <code>GF(q)-0</code> in <code>GF(q^3)-0</code>, and you can define the automorphism on <code>GF(q^3)-0</code> 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.
</p>
<p>
Nathann
</p>
TicketncohenTue, 01 Jul 2014 12:01:14 GMT
https://trac.sagemath.org/ticket/16597#comment:7
https://trac.sagemath.org/ticket/16597#comment:7
<p>
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.
</p>
<p>
Nathann
</p>
TicketvdelecroixTue, 01 Jul 2014 12:37:33 GMT
https://trac.sagemath.org/ticket/16597#comment:8
https://trac.sagemath.org/ticket/16597#comment:8
<p>
Moreover, the set of points is not the vector space but the quotient of <code>V \ {0}</code> by scalar multiplication. So the strategy of theorem 3.16 does not apply directly.
</p>
<p>
Nevertheless, it would be nice to have 3.16 done somewhere! But I am not sure that this ticket is the right place.
</p>
<p>
Vincent
</p>
TicketncohenTue, 01 Jul 2014 12:44:17 GMT
https://trac.sagemath.org/ticket/16597#comment:9
https://trac.sagemath.org/ticket/16597#comment:9
<blockquote class="citation">
<p>
Moreover, the set of points is not the vector space but the quotient of <code>V \ {0}</code> by scalar multiplication. So the strategy of theorem 3.16 does not apply directly.
</p>
</blockquote>
<p>
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).
</p>
<blockquote class="citation">
<p>
Nevertheless, it would be nice to have 3.16 done somewhere! But I am not sure that this ticket is the right place.
</p>
</blockquote>
<p>
Given that you already implemented a specific case of it, I just thought I would bring it up ...
</p>
<p>
Nathann
</p>
TicketgitThu, 03 Jul 2014 06:01:46 GMTcommit changed
https://trac.sagemath.org/ticket/16597#comment:10
https://trac.sagemath.org/ticket/16597#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>ec6df26f4d72c5eb939a9b02cd3ad809feacb105</em> to <em>449939b4c19f235f1fd628e337d5ec3b50f92523</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=449939b4c19f235f1fd628e337d5ec3b50f92523"><span class="icon"></span>449939b</a></td><td><code>trac #16597: more generic, more general way + doc</code>
</td></tr></table>
TicketvdelecroixThu, 03 Jul 2014 06:02:50 GMTstatus changed
https://trac.sagemath.org/ticket/16597#comment:11
https://trac.sagemath.org/ticket/16597#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Hi Nathann,
</p>
<p>
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!
</p>
<p>
Vincent
</p>
TicketncohenThu, 03 Jul 2014 11:54:50 GMT
https://trac.sagemath.org/ticket/16597#comment:12
https://trac.sagemath.org/ticket/16597#comment:12
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I did what you think was better, but I just find it ugly.
</p>
</blockquote>
<p>
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 <code>Incidence Structure</code> relabelling function.. We can go back to your previous commit if you prefer, no problem.
</p>
<p>
Nathann
</p>
TicketgitFri, 04 Jul 2014 06:08:07 GMTcommit changed
https://trac.sagemath.org/ticket/16597#comment:13
https://trac.sagemath.org/ticket/16597#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>449939b4c19f235f1fd628e337d5ec3b50f92523</em> to <em>f725726fa68094215f1d4e19fac2378c0c29d3e8</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f725726fa68094215f1d4e19fac2378c0c29d3e8"><span class="icon"></span>f725726</a></td><td><code>trac #16597: add implementation for any d + doc</code>
</td></tr></table>
TicketvdelecroixFri, 04 Jul 2014 06:08:55 GMT
https://trac.sagemath.org/ticket/16597#comment:14
https://trac.sagemath.org/ticket/16597#comment:14
<p>
All right. Go back to the previous implementation and keep it working in any dimension.
</p>
<p>
Needs review.
</p>
<p>
Vincent
</p>
TicketncohenFri, 04 Jul 2014 08:39:10 GMT
https://trac.sagemath.org/ticket/16597#comment:15
https://trac.sagemath.org/ticket/16597#comment:15
<p>
Hello again !
</p>
<p>
Sorry but it still is a bit hard for me to read those explanations and I go slowly, it isn't really my world <code>^^;</code>
</p>
<ul><li>In the doc of <code>are_projective_space_parameters</code> you give the equations that <code>v,k,lmbda</code> 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 ?"
</li></ul><ul><li>I had begun to write a commit linking this function with <code>ProjectiveGeometryDesign</code> but I did not know enough to finish the review <code>^^;</code>
</li></ul><div class="wiki-code"><div xmlns="http://www.w3.org/1999/xhtml" class="diff">
<ul class="entries">
<li class="entry">
<h2>
<a>src/sage/combinat/designs/block_design.py</a>
</h2>
<pre>diff --git a/src/sage/combinat/designs/block_design.py b/src/sage/combinat/designs/block_design.py</pre>
<table class="trac-diff inline" summary="Differences" cellspacing="0">
<colgroup><col class="lineno" /><col class="lineno" /><col class="content" /></colgroup>
<thead>
<tr>
<th title="File a/src/sage/combinat/designs/block_design.py">
a
</th>
<th title="File b/src/sage/combinat/designs/block_design.py">
b
</th>
<td><em> def ProjectiveGeometryDesign(n, d, F, algorithm=None):</em> </td>
</tr>
</thead>
<tbody class="unmod">
<tr>
<th>117</th><th>117</th><td class="l"><span> GAP's "design" package must be available in this case, and that it can be</span></td>
</tr><tr>
<th>118</th><th>118</th><td class="l"><span> installed with the ``gap_packages`` spkg.</span></td>
</tr><tr>
<th>119</th><th>119</th><td class="l"><span></span></td>
</tr>
</tbody><tbody class="add">
<tr class="first">
<th> </th><th>120</th><td class="r"><ins> .. SEEALSO::</ins></td>
</tr><tr>
<th> </th><th>121</th><td class="r"><ins></ins></td>
</tr><tr>
<th> </th><th>122</th><td class="r"><ins> :func:`sage.combinat.designs.difference_family.are_projective_space_parameters`</ins></td>
</tr><tr class="last">
<th> </th><th>123</th><td class="r"><ins></ins></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>120</th><th>124</th><td class="l"><span> EXAMPLES:</span></td>
</tr><tr>
<th>121</th><th>125</th><td class="l"><span></span></td>
</tr><tr>
<th>122</th><th>126</th><td class="l"><span> The points of the following design are the `\\frac {2^{2+1}-1} {2-1}=7`</span></td>
</tr>
</tbody>
</table>
</li>
<li class="entry">
<h2>
<a>src/sage/combinat/designs/difference_family.py</a>
</h2>
<pre>diff --git a/src/sage/combinat/designs/difference_family.py b/src/sage/combinat/designs/difference_family.py</pre>
<table class="trac-diff inline" summary="Differences" cellspacing="0">
<colgroup><col class="lineno" /><col class="lineno" /><col class="content" /></colgroup>
<thead>
<tr>
<th title="File a/src/sage/combinat/designs/difference_family.py">
a
</th>
<th title="File b/src/sage/combinat/designs/difference_family.py">
b
</th>
<td><em> def are_projective_space_parameters(v, k, lmbda, return_parameters=False):</em> </td>
</tr>
</thead>
<tbody class="unmod">
<tr>
<th>184</th><th>184</th><td class="l"><span> - a boolean or, if ``return_parameters`` is set to ``True`` a pair</span></td>
</tr><tr>
<th>185</th><th>185</th><td class="l"><span> ``(True, (q,d))`` or ``(False, (None,None))``.</span></td>
</tr><tr>
<th>186</th><th>186</th><td class="l"><span></span></td>
</tr>
</tbody><tbody class="add">
<tr class="first">
<th> </th><th>187</th><td class="r"><ins> .. SEEALSO::</ins></td>
</tr><tr>
<th> </th><th>188</th><td class="r"><ins></ins></td>
</tr><tr>
<th> </th><th>189</th><td class="r"><ins> :func:`sage.combinat.designs.block_design.ProjectiveGeometryDesign`</ins></td>
</tr><tr class="last">
<th> </th><th>190</th><td class="r"><ins></ins></td>
</tr>
</tbody><tbody class="unmod">
<tr>
<th>187</th><th>191</th><td class="l"><span> EXAMPLES::</span></td>
</tr><tr>
<th>188</th><th>192</th><td class="l"><span></span></td>
</tr><tr>
<th>189</th><th>193</th><td class="l"><span> sage: from sage.combinat.designs.difference_family import are_projective_space_parameters</span></td>
</tr>
</tbody>
</table>
</li>
</ul>
</div></div><ul><li>I do not understand the code yet, but don't you want to use the 'conway=True<code> trick in </code>singer_difference_set` ?
</li></ul><p>
Nathann
</p>
TicketvdelecroixFri, 04 Jul 2014 09:00:06 GMT
https://trac.sagemath.org/ticket/16597#comment:16
https://trac.sagemath.org/ticket/16597#comment:16
<p>
Hi,
</p>
<blockquote class="citation">
<ul><li>In the doc of <code>are_projective_space_parameters</code> you give the equations that <code>v,k,lmbda</code> 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 ?"
</li></ul></blockquote>
<p>
will do: these are the parameters of a projective space design (assuming that they only exists for prime powers ;-)
</p>
<blockquote class="citation">
<ul><li>I had begun to write a commit linking this function with <code>ProjectiveGeometryDesign</code> but I did not know enough to finish the review <code>^^;</code>
</li></ul></blockquote>
<p>
Yeah it would be cool to check the t-design parameters of projective geometry designs fit what <code>are_projective_space_parameters</code> check for. Actually, it would make sense to move <code>are_projective_space_parameters</code> to <code>block_design.py</code>. What do you think?
</p>
<blockquote class="citation">
<ul><li>I do not understand the code yet, but don't you want to use the 'conway=True<code> trick in </code>singer_difference_set` ?
</li></ul></blockquote>
<p>
Nope. I need relative extensions <code>GF(q) -> GF(q^(d+1))</code>. The trick would only "work" for prime fields. Moreover, testing if an element of an extension belongs to the span over <code>GF(q)</code> of <code>(1,z,...,z^(d-1))</code> is a mess (and trivial if you deal directly with polyonials).
</p>
<p>
I agree that I mimic an extension of <code>GF(q)</code> by dealing with polynomials mod <code>c</code> (the relative Conway polynomial), but it seems the easiest way to go.
</p>
<p>
Vincent
</p>
TicketncohenFri, 04 Jul 2014 09:05:12 GMT
https://trac.sagemath.org/ticket/16597#comment:17
https://trac.sagemath.org/ticket/16597#comment:17
<p>
Yo !
</p>
<blockquote class="citation">
<p>
will do: these are the parameters of a projective space design (assuming that they only exists for prime powers ;-)
</p>
</blockquote>
<p>
Also : don't we use at the same time "projective space design" and "projective geometry design" ?
</p>
<blockquote class="citation">
<p>
Yeah it would be cool to check the t-design parameters of projective geometry designs fit what <code>are_projective_space_parameters</code> check for. Actually, it would make sense to move <code>are_projective_space_parameters</code> to <code>block_design.py</code>. What do you think?
</p>
</blockquote>
<p>
+1
</p>
<blockquote class="citation">
<p>
Nope. I need relative extensions <code>GF(q) -> GF(q^(d+1))</code>. The trick would only "work" for prime fields. Moreover, testing if an element of an extension belongs to the span over <code>GF(q)</code> of <code>(1,z,...,z^(d-1))</code> is a mess (and trivial if you deal directly with polyonials).
</p>
<p>
I agree that I mimic an extension of <code>GF(q)</code> by dealing with polynomials mod <code>c</code> (the relative Conway polynomial), but it seems the easiest way to go.
</p>
</blockquote>
<p>
<code>T_T</code>
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 04 Jul 2014 09:09:19 GMT
https://trac.sagemath.org/ticket/16597#comment:18
https://trac.sagemath.org/ticket/16597#comment:18
<p>
All right, I will change <code>*projective_space*</code> to `*projective_geometry*".
</p>
<p>
Haaarg... but currently the <code>ProjectiveGeometryDesign</code> is so stupdly implemented that it takes hours to generate anything interesting!! And I remember that I already rewrote that in <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/16552" title="enhancement: oval in finite projective plane (needs_work)">#16552</a>. Do you agree that I rewrite <code>ProjectiveGeometryDesign</code> to just work here (but I will not change the behavior of anything right now)?
</p>
<p>
Vincent
</p>
TicketncohenFri, 04 Jul 2014 09:11:36 GMT
https://trac.sagemath.org/ticket/16597#comment:19
https://trac.sagemath.org/ticket/16597#comment:19
<blockquote class="citation">
<p>
Haaarg... but currently the <code>ProjectiveGeometryDesign</code> is so stupdly implemented that it takes hours to generate anything interesting!! And I remember that I already rewrote that in <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/16552" title="enhancement: oval in finite projective plane (needs_work)">#16552</a>. Do you agree that I rewrite <code>ProjectiveGeometryDesign</code> to just work here (but I will not change the behavior of anything right now)?
</p>
</blockquote>
<p>
Yeahyeah good idea !
</p>
<p>
Nathann
</p>
TicketvdelecroixFri, 04 Jul 2014 21:18:27 GMTstatus changed; dependencies set
https://trac.sagemath.org/ticket/16597#comment:20
https://trac.sagemath.org/ticket/16597#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>dependencies</strong>
set to <em>#16553,#16617</em>
</li>
</ul>
TicketgitFri, 04 Jul 2014 21:37:05 GMTcommit changed
https://trac.sagemath.org/ticket/16597#comment:21
https://trac.sagemath.org/ticket/16597#comment:21
<ul>
<li><strong>commit</strong>
changed from <em>f725726fa68094215f1d4e19fac2378c0c29d3e8</em> to <em>46cd4622a9777284fb6e3bf7d21ebf90680e7954</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=bd609fcef6ba2923a6659e7c2dd35edf828467cf"><span class="icon"></span>bd609fc</a></td><td><code>trac #16553: is_t_design</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=11994efa18b15a9a0330a0816c7aea24fb2bc498"><span class="icon"></span>11994ef</a></td><td><code>trac #16553: Review</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e7a97ea3ca390627aed24693e5314568234dfdf3"><span class="icon"></span>e7a97ea</a></td><td><code>trac #16553: doc fix + deprecation is_block_design</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3c0dd71a1ecaf61af062ff7ddedf4e95f38d5b22"><span class="icon"></span>3c0dd71</a></td><td><code>trac #16553v3: change .points() -> .ground_set()</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=52b71777445b45770ad8ebceeb73da791c7145ac"><span class="icon"></span>52b7177</a></td><td><code>trac #16553: merge sage 6.3.beta5</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=0698433258c4f863cc1585ece2065b5e4e1b41eb"><span class="icon"></span>0698433</a></td><td><code>trac #16553: deprecated alias .points() + fix</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7faff0802d45ca5e6608da17002f1f6c5fc418db"><span class="icon"></span>7faff08</a></td><td><code>trac #16597: merge #16553</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=aff5e443d6cdf25e9c16b107b50b7bf200c9e37d"><span class="icon"></span>aff5e44</a></td><td><code>trac #16617: echelon matrix iterator</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4e190d5f03a7d6fa0eb117e1e9dcf6c52615391c"><span class="icon"></span>4e190d5</a></td><td><code>trac #16597: merge #16617</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=46cd4622a9777284fb6e3bf7d21ebf90680e7954"><span class="icon"></span>46cd462</a></td><td><code>trac #16597: move parameter check in block_design.py</code>
</td></tr></table>
TicketvdelecroixFri, 04 Jul 2014 21:37:19 GMTstatus changed
https://trac.sagemath.org/ticket/16597#comment:22
https://trac.sagemath.org/ticket/16597#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketgitSat, 19 Jul 2014 14:46:30 GMTcommit changed
https://trac.sagemath.org/ticket/16597#comment:23
https://trac.sagemath.org/ticket/16597#comment:23
<ul>
<li><strong>commit</strong>
changed from <em>46cd4622a9777284fb6e3bf7d21ebf90680e7954</em> to <em>10c9beb0a672b3b5c628d7b206b6dbc49aae5848</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f3cc9b7a9979e164565df53fa11dd6f8647a6ee9"><span class="icon"></span>f3cc9b7</a></td><td><code>trac #16617: cythonisation</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1d5ca5308d23fe938f0ca32b73c6f675a78948e8"><span class="icon"></span>1d5ca53</a></td><td><code>trac #16617: doctest + remove part of the cache</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6908f39941ec6a4b79373400beb20c03824957cb"><span class="icon"></span>6908f39</a></td><td><code>trac #16617: change the name + doctest</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a2c71c369ed15f065ff0679c48d2acd8ff32dfcc"><span class="icon"></span>a2c71c3</a></td><td><code>trac #16597: merge updated #16617</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=10c9beb0a672b3b5c628d7b206b6dbc49aae5848"><span class="icon"></span>10c9beb</a></td><td><code>trac #16597: take care of the update #16617</code>
</td></tr></table>
TicketvdelecroixSat, 19 Jul 2014 14:47:27 GMT
https://trac.sagemath.org/ticket/16597#comment:24
https://trac.sagemath.org/ticket/16597#comment:24
<p>
Rebased on the updated <a class="closed ticket" href="https://trac.sagemath.org/ticket/16617" title="enhancement: simple echelon matrix iterator (closed: fixed)">#16617</a>... needs review again.
</p>
TicketncohenMon, 21 Jul 2014 10:24:01 GMT
https://trac.sagemath.org/ticket/16597#comment:25
https://trac.sagemath.org/ticket/16597#comment:25
<p>
Hello !
</p>
<p>
I added a commit <code>public/16597</code> 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.
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 21 Jul 2014 10:32:22 GMT
https://trac.sagemath.org/ticket/16597#comment:26
https://trac.sagemath.org/ticket/16597#comment:26
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16597#comment:25" title="Comment 25">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Hello !
</p>
<p>
I added a commit <code>public/16597</code> 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.
</p>
</blockquote>
<p>
I can try to explain (in these comments and inside the code), could you be more precise?
</p>
<p>
Vincent
</p>
TicketncohenMon, 21 Jul 2014 10:33:35 GMT
https://trac.sagemath.org/ticket/16597#comment:27
https://trac.sagemath.org/ticket/16597#comment:27
<p>
Basically, I don't get why doint this does the job
</p>
<pre class="wiki">+ # 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)
</pre><p>
And it isn't exactly the way it is explained in Stinson's book either I believe..
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 21 Jul 2014 10:42:27 GMT
https://trac.sagemath.org/ticket/16597#comment:28
https://trac.sagemath.org/ticket/16597#comment:28
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16597#comment:27" title="Comment 27">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Basically, I don't get why doint this does the job
</p>
<pre class="wiki">+ # 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)
</pre><p>
And it isn't exactly the way it is explained in Stinson's book either I believe..
</p>
</blockquote>
<p>
It follows Stinson but the loop is stopped sooner.
</p>
<p>
The field <code>Kbig</code> with q<sup>e+1</sup> elements is a vector space over <code>Ksmall</code> the one with q elements. We chose a generator z of the multiplicative group of <code>Kbig</code> (that way we have a cyclic action on lines). We also choose a concrete subspace of dimension <code>d</code> in <code>Kbig</code> to be the span (over <code>Ksmall</code>) of 1,z,...z<sup>d-1</sup>. Let call it <code>V</code> this subspace.
</p>
<p>
The difference set is by definition the set of integers <code>i</code> such that <code>z^i</code> belong to <code>V</code> (recall that any element of <code>Kbig</code> different from <code>0</code> can be written as <code>z^i</code> with <code>i < q^e</code>).
</p>
<p>
This is what Stinson does and this is what I am doing.
</p>
<p>
Vincent
</p>
TicketncohenMon, 21 Jul 2014 10:47:50 GMT
https://trac.sagemath.org/ticket/16597#comment:29
https://trac.sagemath.org/ticket/16597#comment:29
<blockquote class="citation">
<p>
This is what Stinson does and this is what I am doing.
</p>
</blockquote>
<p>
Oh I see it now, very cool ! Plus you really generate very few objects. Coud you add those explanations in the doc/code ?
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 21 Jul 2014 10:49:04 GMT
https://trac.sagemath.org/ticket/16597#comment:30
https://trac.sagemath.org/ticket/16597#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16597#comment:29" title="Comment 29">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
This is what Stinson does and this is what I am doing.
</p>
</blockquote>
<p>
Oh I see it now, very cool ! Plus you really generate very few objects. Coud you add those explanations in the doc/code ?
</p>
</blockquote>
<p>
Of course, I will.
</p>
<p>
Vincent
</p>
TicketncohenMon, 21 Jul 2014 10:49:46 GMT
https://trac.sagemath.org/ticket/16597#comment:31
https://trac.sagemath.org/ticket/16597#comment:31
<p>
(don't forget my small commit on <code>public/16597</code>)
</p>
TicketvdelecroixMon, 21 Jul 2014 10:55:37 GMT
https://trac.sagemath.org/ticket/16597#comment:32
https://trac.sagemath.org/ticket/16597#comment:32
<p>
There is just a subtlety that I did not tell you. If you follow my words you have "too much" integers <code>i</code> (if you have <code>z^i</code> you also have <code>z^(i + n*(q^(e+1)-1)/(q^d-1))</code> or in other words the element <code>z^i x</code> with <code>x</code> in <code>Ksmall</code>). If you only store the smallest <code>i</code> as I did, everything is fine since you start to see two points on the same <code>Ksmall</code>-line only after you see all the lines in <code>Kbig</code> at least once...
</p>
<p>
Vincent
</p>
TicketncohenMon, 21 Jul 2014 10:58:24 GMT
https://trac.sagemath.org/ticket/16597#comment:33
https://trac.sagemath.org/ticket/16597#comment:33
<blockquote class="citation">
<p>
There is just a subtlety that I did not tell you. If you follow my words you have "too much" integers <code>i</code> (if you have <code>z^i</code> you also have <code>z^(i + n*(q^(e+1)-1)/(q^d-1))</code> or in other words the element <code>z^i x</code> with <code>x</code> in <code>Ksmall</code>). If you only store the smallest <code>i</code> as I did, everything is fine since you start to see two points on the same <code>Ksmall</code>-line only after you see all the lines least once...
</p>
</blockquote>
<p>
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 <code>z</code> ? Something that would be more efficient than enumeration ?
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 21 Jul 2014 10:59:25 GMT
https://trac.sagemath.org/ticket/16597#comment:34
https://trac.sagemath.org/ticket/16597#comment:34
<p>
It is a very hard thing to compute the logarithm: <a class="ext-link" href="http://en.wikipedia.org/wiki/Discrete_logarithm"><span class="icon"></span>http://en.wikipedia.org/wiki/Discrete_logarithm</a> (it is used for cryptography).
</p>
<p>
Vincent
</p>
TicketvdelecroixMon, 21 Jul 2014 11:00:32 GMT
https://trac.sagemath.org/ticket/16597#comment:35
https://trac.sagemath.org/ticket/16597#comment:35
<p>
Hopefully: "There exists an efficient quantum algorithm due to Peter Shor!" (from wikipedia)
</p>
TicketncohenMon, 21 Jul 2014 11:02:32 GMT
https://trac.sagemath.org/ticket/16597#comment:36
https://trac.sagemath.org/ticket/16597#comment:36
<blockquote class="citation">
<p>
It is a very hard thing to compute the logarithm: <a class="ext-link" href="http://en.wikipedia.org/wiki/Discrete_logarithm"><span class="icon"></span>http://en.wikipedia.org/wiki/Discrete_logarithm</a> (it is used for cryptography).
</p>
</blockquote>
<p>
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 <code>log(n)</code>
</p>
<p>
2) It is "hard" to factor stuff, yet there is something "more efficient" that trying all integers smaller than <code>n</code> (stop at <code>sqrt(n)</code>)
</p>
<p>
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 ?... <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketncohenMon, 21 Jul 2014 11:03:52 GMT
https://trac.sagemath.org/ticket/16597#comment:37
https://trac.sagemath.org/ticket/16597#comment:37
<blockquote class="citation">
<p>
Hopefully: "There exists an efficient quantum algorithm due to Peter Shor!" (from wikipedia)
</p>
</blockquote>
<p>
Allahuuuuu Akbar !
</p>
<p>
Nathann
</p>
TicketvdelecroixMon, 21 Jul 2014 11:04:28 GMT
https://trac.sagemath.org/ticket/16597#comment:38
https://trac.sagemath.org/ticket/16597#comment:38
<p>
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.
</p>
<p>
Vincent
</p>
TicketncohenMon, 21 Jul 2014 11:08:35 GMT
https://trac.sagemath.org/ticket/16597#comment:39
https://trac.sagemath.org/ticket/16597#comment:39
<p>
I am pretty sure I studied this at the University
</p>
<pre class="wiki">sage: sage.groups.generic.bsgs
</pre><p>
I forgot all of it, though... But I guess it shouldn't be a standalone function like that.
</p>
<p>
Nathann
</p>
TicketncohenWed, 23 Jul 2014 12:03:03 GMTstatus changed
https://trac.sagemath.org/ticket/16597#comment:40
https://trac.sagemath.org/ticket/16597#comment:40
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
(awaiting doc update)
</p>
TicketgitMon, 28 Jul 2014 13:19:46 GMTcommit changed
https://trac.sagemath.org/ticket/16597#comment:41
https://trac.sagemath.org/ticket/16597#comment:41
<ul>
<li><strong>commit</strong>
changed from <em>10c9beb0a672b3b5c628d7b206b6dbc49aae5848</em> to <em>ac4abab21cecffc01ff91dff40e8442fda10a9d1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=cc3e1dfd6cf2e119c40b57c81fb83322f40e1789"><span class="icon"></span>cc3e1df</a></td><td><code>trac #16597: merge 6.3.beta6</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ac4abab21cecffc01ff91dff40e8442fda10a9d1"><span class="icon"></span>ac4abab</a></td><td><code>trac #16597: more doc</code>
</td></tr></table>
TicketvdelecroixMon, 28 Jul 2014 13:25:36 GMTstatus changed
https://trac.sagemath.org/ticket/16597#comment:42
https://trac.sagemath.org/ticket/16597#comment:42
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketncohenMon, 28 Jul 2014 13:54:29 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/16597#comment:43
https://trac.sagemath.org/ticket/16597#comment:43
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
<p>
OKayyyyyyyyyyyyyyyyyyyyyyyyyyy.... !
</p>
<p>
Nathann
</p>
TicketvbraunMon, 28 Jul 2014 16:27:03 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/16597#comment:44
https://trac.sagemath.org/ticket/16597#comment:44
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/vdelecroix/16597</em> to <em>ac4abab21cecffc01ff91dff40e8442fda10a9d1</em>
</li>
</ul>
Ticket