Sage: Ticket #12418: adding Delsarte bound for codes
https://trac.sagemath.org/ticket/12418
<p>
Delsarte bound for codes, aka Linear Programming bound, is easy to implement in Sage.
</p>
<p>
To work well in big dimensions, one needs an arbitrary precision LP solver. We use an LP backend to PPL, which is available in Sage since <a class="closed ticket" href="https://trac.sagemath.org/ticket/12533" title="enhancement: arbitrary precision LP solver backend (closed: fixed)">#12533</a>.
</p>
<p>
Apply
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12418/12418_delsart_bounds.patch" title="Attachment '12418_delsart_bounds.patch' in Ticket #12418">12418_delsart_bounds.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12418/12418_delsart_bounds.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12418/12418_update.patch" title="Attachment '12418_update.patch' in Ticket #12418">12418_update.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12418/12418_update.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12418
Trac 1.1.6dimpaseFri, 03 Feb 2012 08:08:56 GMT
https://trac.sagemath.org/ticket/12418#comment:1
https://trac.sagemath.org/ticket/12418#comment:1TicketdimpaseFri, 03 Feb 2012 09:10:37 GMTcc changed
https://trac.sagemath.org/ticket/12418#comment:2
https://trac.sagemath.org/ticket/12418#comment:2
<ul>
<li><strong>cc</strong>
<em>kini</em> added
</li>
</ul>
TicketdimpaseSun, 05 Feb 2012 13:51:46 GMTcc changed
https://trac.sagemath.org/ticket/12418#comment:3
https://trac.sagemath.org/ticket/12418#comment:3
<ul>
<li><strong>cc</strong>
<em>wdj</em> added
</li>
</ul>
TicketdimpaseMon, 06 Feb 2012 12:09:54 GMTcc, description changed
https://trac.sagemath.org/ticket/12418#comment:4
https://trac.sagemath.org/ticket/12418#comment:4
<ul>
<li><strong>cc</strong>
<em>ncohen</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12418?action=diff&version=4">diff</a>)
</li>
</ul>
TicketncohenMon, 06 Feb 2012 12:12:10 GMT
https://trac.sagemath.org/ticket/12418#comment:5
https://trac.sagemath.org/ticket/12418#comment:5
<p>
(GLPK can solve non-integer rational LP. It is not exposed, but may not be too hard either)
</p>
TicketdimpaseTue, 07 Feb 2012 14:12:30 GMTcc changed
https://trac.sagemath.org/ticket/12418#comment:6
https://trac.sagemath.org/ticket/12418#comment:6
<ul>
<li><strong>cc</strong>
<em>ppurka</em> added
</li>
</ul>
TicketppurkaTue, 07 Feb 2012 14:22:47 GMT
https://trac.sagemath.org/ticket/12418#comment:7
https://trac.sagemath.org/ticket/12418#comment:7
<p>
The function named <code>delsarte_bound</code> should be renamed to something like <code>delsarte_bound_hamming_space</code>. This is so that in future other functions like <code>delsarte_bound_johnson_space</code>, <code>delsarte_bound_permutation_space</code>, etc can be added easily, without having inconsistencies in naming.
</p>
TicketdimpaseSat, 18 Feb 2012 15:23:42 GMTcc changed
https://trac.sagemath.org/ticket/12418#comment:8
https://trac.sagemath.org/ticket/12418#comment:8
<ul>
<li><strong>cc</strong>
<em>ptrrsn_1</em> added
</li>
</ul>
TicketdimpaseTue, 05 Jun 2012 15:40:03 GMTdescription changed
https://trac.sagemath.org/ticket/12418#comment:9
https://trac.sagemath.org/ticket/12418#comment:9
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12418?action=diff&version=9">diff</a>)
</li>
</ul>
TicketdimpaseFri, 08 Jun 2012 14:44:48 GMTdescription changed; dependencies set
https://trac.sagemath.org/ticket/12418#comment:10
https://trac.sagemath.org/ticket/12418#comment:10
<ul>
<li><strong>dependencies</strong>
set to <em>#12533</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12418?action=diff&version=10">diff</a>)
</li>
</ul>
TicketdimpaseFri, 08 Jun 2012 14:47:15 GMTattachment set
https://trac.sagemath.org/ticket/12418
https://trac.sagemath.org/ticket/12418
<ul>
<li><strong>attachment</strong>
set to <em>delsarte_bound.py</em>
</li>
</ul>
<p>
a prototype implementation
</p>
TicketdimpaseSun, 28 Oct 2012 16:39:58 GMTstatus, description changed
https://trac.sagemath.org/ticket/12418#comment:11
https://trac.sagemath.org/ticket/12418#comment:11
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12418?action=diff&version=11">diff</a>)
</li>
</ul>
TicketppurkaWed, 07 Nov 2012 10:26:04 GMT
https://trac.sagemath.org/ticket/12418#comment:12
https://trac.sagemath.org/ticket/12418#comment:12
<p>
I think the <code>Krawtchouk</code> polynomial could be computed explicitly by not making repeated calls to <code>binomial</code>. This should speed it up. I have something like this in mind:
</p>
<pre class="wiki">def Krawtchouk2(n,q,l,i):
# Use the expression in equation (55) of MacWilliams & Sloane, pg 151
# We write jth term = some_factor * (j-1)th term
kraw = jth_term = (q-1)**l * binomial(n, l) # j=0
for j in range(1,l+1):
jth_term *= -q*(l-j+1)*(i-j+1)/((q-1)*j*(n-j+1))
kraw += jth_term
return kraw
n,q,l,i = 10,8,7,5
timeit('Krawtchouk2(n,q,l,i)')
timeit('Krawtchouk (n,q,l,i)')
print Krawtchouk2(n,q,l,i) == Krawtchouk(n,q,l,i)
625 loops, best of 3: 53.3 µs per loop
625 loops, best of 3: 205 µs per loop
True
</pre><p>
I noticed that sage handles nonintegral components in the binomial, so the expression for the <code>Krawtchouk</code> already works with nonintegral <code>n</code> and <code>x</code>.
</p>
<pre class="wiki">n,q,l,i = 10.6,8,7,5.4
#timeit('Krawtchouk3(n,q,l,i)')
timeit('Krawtchouk2(n,q,l,i)')
timeit('Krawtchouk (n,q,l,i)')
print Krawtchouk2(n,q,l,i) == Krawtchouk(n,q,l,i)
print Krawtchouk2(n,q,l,i), Krawtchouk(n,q,l,i)
625 loops, best of 3: 382 µs per loop
125 loops, best of 3: 4.74 ms per loop
False
93582.0160001147 93582.0159999999
</pre>
TicketppurkaWed, 07 Nov 2012 10:40:40 GMT
https://trac.sagemath.org/ticket/12418#comment:13
https://trac.sagemath.org/ticket/12418#comment:13
<p>
Can you mention when it guarantees a weight spectrum? Would doing an <code>ILP</code> make it a proper weight spectrum?
</p>
<pre class="wiki"> - ``return_data`` -- if ``True``, return a weights vector, which actually need not
be a proper weight enumerator, or even have integer entries, and the LP.
</pre><p>
Also, I think the term <code>weight enumerator</code> refers to the <code>weight enumerator polynomial</code>. Perhaps using <code>weight distribution</code> or <code>distance distribution</code> is more appropriate here.
</p>
TicketdimpaseWed, 07 Nov 2012 14:26:36 GMT
https://trac.sagemath.org/ticket/12418#comment:14
https://trac.sagemath.org/ticket/12418#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:12" title="Comment 12">ppurka</a>:
</p>
<blockquote class="citation">
<p>
I think the <code>Krawtchouk</code> polynomial could be computed explicitly by not making repeated calls to <code>binomial</code>. This should speed it up.
</p>
</blockquote>
<p>
It's probably even faster to compute by using recurrence relations, but I don't think it's important here: LP solving timing clearly dominates the rest.
</p>
<p>
By the way, would it be interesting to include an option to compute bounds on codes with a prescribed forbidden
set of distances, rather than just [1..d] ? It's a trivial add-on.
I did this in a prototype code for Johnson schemes, <a class="ext-link" href="http://mathoverflow.net/questions/111603/intersecting-4-sets/111647#111647"><span class="icon"></span>here</a>.
</p>
<p>
Any other interesting schemes to include? (Johnson scheme takes care of constant weight binary codes, as you know.)
</p>
TicketdimpaseWed, 07 Nov 2012 14:57:35 GMTdependencies, description, milestone changed
https://trac.sagemath.org/ticket/12418#comment:15
https://trac.sagemath.org/ticket/12418#comment:15
<ul>
<li><strong>dependencies</strong>
changed from <em>#12533</em> to <em>#12533, #13650</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12418?action=diff&version=15">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-5.4</em> to <em>sage-5.5</em>
</li>
</ul>
TicketppurkaWed, 07 Nov 2012 14:59:39 GMT
https://trac.sagemath.org/ticket/12418#comment:16
https://trac.sagemath.org/ticket/12418#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:14" title="Comment 14">dimpase</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:12" title="Comment 12">ppurka</a>:
</p>
<blockquote class="citation">
<p>
I think the <code>Krawtchouk</code> polynomial could be computed explicitly by not making repeated calls to <code>binomial</code>. This should speed it up.
</p>
</blockquote>
<p>
It's probably even faster to compute by using recurrence relations, but I don't think it's important here: LP solving timing clearly dominates the rest.
</p>
</blockquote>
<p>
The point is that someone might try to use these polynomials more generally in a separate context. They are not defined anywhere else in Sage, so anyone who tries to use them will use this one.
</p>
<blockquote class="citation">
<p>
By the way, would it be interesting to include an option to compute bounds on codes with a prescribed forbidden
set of distances, rather than just [1..d] ? It's a trivial add-on.
I did this in a prototype code for Johnson schemes, <a class="ext-link" href="http://mathoverflow.net/questions/111603/intersecting-4-sets/111647#111647"><span class="icon"></span>here</a>.
</p>
</blockquote>
<p>
Wow! You have the Johnson scheme too?! Sure, add them all in!! Do you use the polynomials used by Aaltonen?
</p>
<blockquote class="citation">
<p>
Any other interesting schemes to include? (Johnson scheme takes care of constant weight binary codes, as you know.)
</p>
</blockquote>
<p>
LP for permutation codes would be interesting. There are not too many good results known there. IIRC, it uses Charlier polynomials.
</p>
<p>
EDIT: FWIW, it is Charlier polynomials.
</p>
TicketppurkaWed, 07 Nov 2012 15:10:11 GMT
https://trac.sagemath.org/ticket/12418#comment:17
https://trac.sagemath.org/ticket/12418#comment:17
<p>
Oh, I forgot to add. Forbidden distances will be nice as well. I think only some special cases achieve the closed form solutions. In general, still not much is known. It looks like you only need to drop distances <code>d_1,...,d_m</code> instead of <code>1,...,d</code>, right?
</p>
<p>
How about introducing an extra keyword called <code>forbidden_distances</code> or <code>exclude_distances</code>, which defaults to <code>1,...,d</code>?
</p>
TicketdimpaseWed, 07 Nov 2012 15:18:37 GMT
https://trac.sagemath.org/ticket/12418#comment:18
https://trac.sagemath.org/ticket/12418#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:16" title="Comment 16">ppurka</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:14" title="Comment 14">dimpase</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:12" title="Comment 12">ppurka</a>:
</p>
<blockquote class="citation">
<p>
I think the <code>Krawtchouk</code> polynomial could be computed explicitly by not making repeated calls to <code>binomial</code>. This should speed it up.
</p>
</blockquote>
<p>
It's probably even faster to compute by using recurrence relations, but I don't think it's important here: LP solving timing clearly dominates the rest.
</p>
</blockquote>
<p>
The point is that someone might try to use these polynomials more generally in a separate context. They are not defined anywhere else in Sage, so anyone who tries to use them will use this one.
</p>
</blockquote>
<p>
Actually, I have most discrete orthogonal polynomials arising in the classical P- and Q- polynomial schemes
<a class="ext-link" href="https://bitbucket.org/dimpase/qcode/src/9e3b79dc71992aa2a8ea170dbd13f9f373772411/aw.sage?at=default"><span class="icon"></span>implemented</a>, although it's neither polished nor optimized.
</p>
<p>
[
</p>
<blockquote class="citation">
<p>
</p>
<blockquote class="citation">
<p>
By the way, would it be interesting to include an option to compute bounds on codes with a prescribed forbidden
set of distances, rather than just [1..d] ? It's a trivial add-on.
I did this in a prototype code for Johnson schemes, <a class="ext-link" href="http://mathoverflow.net/questions/111603/intersecting-4-sets/111647#111647"><span class="icon"></span>here</a>.
</p>
</blockquote>
<p>
Wow! You have the Johnson scheme too?! Sure, add them all in!! Do you use the polynomials used by Aaltonen?
</p>
</blockquote>
<p>
I <a class="ext-link" href="https://bitbucket.org/dimpase/qcode/src/9e3b79dc71992aa2a8ea170dbd13f9f373772411/aw.sage?at=default"><span class="icon"></span>use</a> the descriptions in the book "Algebraic Combinatorics I" by E.Bannai and T.Ito.
Something known as <a class="ext-link" href="http://mathworld.wolfram.com/EberleinPolynomial.html"><span class="icon"></span>Eberlein polynomials</a>.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Any other interesting schemes to include? (Johnson scheme takes care of constant weight binary codes, as you know.)
</p>
</blockquote>
<p>
LP for permutation codes would be interesting. There are not too many good results known there. IIRC, it uses Chebychev polynomials(?).
</p>
</blockquote>
<p>
yes, this should be perfectly doable.
</p>
TicketppurkaWed, 07 Nov 2012 15:23:58 GMT
https://trac.sagemath.org/ticket/12418#comment:19
https://trac.sagemath.org/ticket/12418#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:18" title="Comment 18">dimpase</a>:
</p>
<blockquote class="citation">
<p>
I <a class="ext-link" href="https://bitbucket.org/dimpase/qcode/src/9e3b79dc71992aa2a8ea170dbd13f9f373772411/aw.sage?at=default"><span class="icon"></span>use</a> the descriptions in the book "Algebraic Combinatorics I" by E.Bannai and T.Ito.
Something known as <a class="ext-link" href="http://mathworld.wolfram.com/EberleinPolynomial.html"><span class="icon"></span>Eberlein polynomials</a>.
</p>
</blockquote>
<p>
That's for the binary case. For the q-ary case it is a product of Krawtchouk and Hahn, if I recall properly. Let me fish out the paper; I will send it to you.
</p>
TicketdimpaseMon, 07 Jan 2013 06:44:48 GMT
https://trac.sagemath.org/ticket/12418#comment:20
https://trac.sagemath.org/ticket/12418#comment:20
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:12" title="Comment 12">ppurka</a>:
</p>
<blockquote class="citation">
<p>
I think the <code>Krawtchouk</code> polynomial could be computed explicitly by not making repeated calls to <code>binomial</code>. This should speed it up. I have something like this in mind:
</p>
</blockquote>
<p>
This can be further optimized by using Horner's rule. I'll do this, and leave the rest (other schemes) for another ticket, OK?
</p>
TicketppurkaMon, 07 Jan 2013 07:01:41 GMT
https://trac.sagemath.org/ticket/12418#comment:21
https://trac.sagemath.org/ticket/12418#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:20" title="Comment 20">dimpase</a>:
</p>
<blockquote class="citation">
<p>
This can be further optimized by using Horner's rule. I'll do this, and leave the rest (other schemes) for another ticket, OK?
</p>
</blockquote>
<p>
Yes, yes. One space/polynomial at a time. Just Hamming space in this ticket is OK.
</p>
TicketdimpaseTue, 08 Jan 2013 03:32:53 GMTattachment set
https://trac.sagemath.org/ticket/12418
https://trac.sagemath.org/ticket/12418
<ul>
<li><strong>attachment</strong>
set to <em>update.diff</em>
</li>
</ul>
<p>
update of the patch - for reviewing only
</p>
TicketdimpaseTue, 08 Jan 2013 03:37:14 GMTdescription changed
https://trac.sagemath.org/ticket/12418#comment:22
https://trac.sagemath.org/ticket/12418#comment:22
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12418?action=diff&version=22">diff</a>)
</li>
</ul>
<p>
Please review. I added a Kravchouck speedup, and cleaned up docstrings as requested.
</p>
TicketdimpaseTue, 08 Jan 2013 05:29:35 GMT
https://trac.sagemath.org/ticket/12418#comment:23
https://trac.sagemath.org/ticket/12418#comment:23
<p>
improved docstrings for <code>return_data</code>
</p>
TicketppurkaTue, 08 Jan 2013 09:28:25 GMT
https://trac.sagemath.org/ticket/12418#comment:24
https://trac.sagemath.org/ticket/12418#comment:24
<p>
Thanks for the update. I have some general comments. Will look into this patch in more detail too.
</p>
<ol><li>There are lot of trailing whitespaces. The patchbot will complain. :)
</li><li>What is the point of this portion of the code? Can't it be replaced by <code>kk = ZZ(log(q, q_base))</code>?
<div class="wiki-code"><div class="code"><pre> kk <span class="o">=</span> <span class="mi">0</span>
<span class="k">while</span> q_base<span class="o">**</span>kk <span class="o"><</span> q<span class="p">:</span>
kk <span class="o">+=</span> <span class="mi">1</span>
</pre></div></div></li><li>There is another bit further down:
<div class="wiki-code"><div class="code"><pre> m <span class="o">=</span> <span class="o">-</span><span class="mi">1</span>
<span class="k">while</span> q_base<span class="o">**</span><span class="p">(</span>m<span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o"><</span> bd<span class="p">:</span>
m <span class="o">+=</span> <span class="mi">1</span>
<span class="k">if</span> q_base<span class="o">**</span><span class="p">(</span>m<span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o">==</span> bd<span class="p">:</span>
m <span class="o">+=</span> <span class="mi">1</span>
</pre></div></div></li><li>Also, I don't think this deprecation is necessary any more. The ticket you cited is over 2 years old.
<div class="wiki-code"><div class="code"><pre><span class="gd">-def dimension_upper_bound(n,d,q):
</span><span class="gi">+@rename_keyword(deprecation=6094, method="algorithm")
+def dimension_upper_bound(n,d,q,algorithm=None):
</span></pre></div></div></li></ol><p>
<strong>Edit:</strong> Sorry. It seems <code>ZZ</code> doesn't work but <code>int(log(..))</code> does work.
</p>
TicketdimpaseTue, 08 Jan 2013 13:25:52 GMT
https://trac.sagemath.org/ticket/12418#comment:25
https://trac.sagemath.org/ticket/12418#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:24" title="Comment 24">ppurka</a>:
</p>
<blockquote class="citation">
<p>
Thanks for the update. I have some general comments. Will look into this patch in more detail too.
</p>
<ol><li>There are lot of trailing whitespaces. The patchbot will complain. :)
</li></ol></blockquote>
<p>
I've just uploaded an update with all the trailing spaces removed.
</p>
<blockquote class="citation">
<ol start="2"><li>What is the point of this portion of the code? Can't it be replaced by <code>kk = ZZ(log(q, q_base))</code>?
<div class="wiki-code"><div class="code"><pre> kk <span class="o">=</span> <span class="mi">0</span>
<span class="k">while</span> q_base<span class="o">**</span>kk <span class="o"><</span> q<span class="p">:</span>
kk <span class="o">+=</span> <span class="mi">1</span>
</pre></div></div></li><li>There is another bit further down:
<div class="wiki-code"><div class="code"><pre> m <span class="o">=</span> <span class="o">-</span><span class="mi">1</span>
<span class="k">while</span> q_base<span class="o">**</span><span class="p">(</span>m<span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o"><</span> bd<span class="p">:</span>
m <span class="o">+=</span> <span class="mi">1</span>
<span class="k">if</span> q_base<span class="o">**</span><span class="p">(</span>m<span class="o">+</span><span class="mi">1</span><span class="p">)</span> <span class="o">==</span> bd<span class="p">:</span>
m <span class="o">+=</span> <span class="mi">1</span>
</pre></div></div></li></ol></blockquote>
<p>
this came from an older piece of plain Python. Then I struggled with log() quite a bit, and finally gave up on it and rolled my own.
</p>
<blockquote class="citation">
<ol start="4"><li>Also, I don't think this deprecation is necessary any more. The ticket you cited is over 2 years old.
<div class="wiki-code"><div class="code"><pre><span class="gd">-def dimension_upper_bound(n,d,q):
</span><span class="gi">+@rename_keyword(deprecation=6094, method="algorithm")
+def dimension_upper_bound(n,d,q,algorithm=None):
</span></pre></div></div></li></ol></blockquote>
<p>
I blindly copied from <code>sage/coding/code_bounds.py</code>
Should the whole file be cleaned out of these?
By the way, plural <code>methods</code> slipped through this decorator...
</p>
<blockquote class="citation">
<p>
<strong>Edit:</strong> Sorry. It seems <code>ZZ</code> doesn't work but <code>int(log(..))</code> does work.
</p>
</blockquote>
TicketdimpaseThu, 10 Jan 2013 12:40:51 GMT
https://trac.sagemath.org/ticket/12418#comment:26
https://trac.sagemath.org/ticket/12418#comment:26
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:24" title="Comment 24">ppurka</a>:
</p>
<blockquote class="citation">
<p>
Thanks for the update. I have some general comments. Will look into this patch in more detail too.
</p>
</blockquote>
<blockquote class="citation">
<ol start="2"><li>What is the point of this portion of the code? Can't it be replaced by <code>kk = ZZ(log(q, q_base))</code>?
</li></ol></blockquote>
<p>
yes, it is basically what it does; this is also needed to do a Gomory-style cut which might be available due to the corresponding rounding.
</p>
TicketppurkaThu, 24 Jan 2013 11:37:11 GMT
https://trac.sagemath.org/ticket/12418#comment:27
https://trac.sagemath.org/ticket/12418#comment:27
<p>
Ok. I am finally getting some time to look into this again. Here are some comments.
</p>
<ol><li><code>Krawtchouk</code> is missing a doctest.
</li><li>There is no need of <code>\</code> in <code>def delsarte_bound_...</code>
</li><li>There are still many trailing whitespaces. If you use vim then you can try this command <code>:%s/[ ]\+$//</code>
</li><li><code> - ``q`` -- the length of the alphabet</code> -- this should be "the <em>size</em> of the alphabet"
</li></ol><blockquote>
<p>
Also I think the the options <code>q</code> and <code>d</code> can be swapped to be in the order in which they appear
in the function definition.
</p>
</blockquote>
<ol start="5"><li><code>- ``solver`` -- the LP/ILP solved </code> --- this should be <em>solver</em>.
What other solvers are present? They should be listed as options in this
variable.
</li><li><code>The bound on the size of the F_2-codes</code> --- this should be <em><code>`F_2`</code></em>
</li><li> <code> - ``return_data`` </code> --- As it is currently written in the description, it is unclear what this is returning. It looks like the first component is an MIP variable (and not a vector), and the second component is the MILP itself. At a first glance in your doctests, it looks like we need to understand how the MILP works in order to get the values of the weight distribution. Should we just return the weight distribution itself? A weight distribution vector can be returned by doing <code>p.get_values(a).values()</code>.
</li><li>The backend should automatically handle "isinteger=True" at least so that it is functional. Currently I get a very generic Exception (why is this only "Exception"?). Maybe it is automatically handled in a later version of sage? I will have to check against 5.6.beta1 and higher:
<pre class="wiki">Exception: This backend does not handle integer variables ! Read the doc !
</pre></li><li>Why do we need the second function? We already discussed this off-ticket - I will wait for your generic function.
</li><li><code>(**this option is currenly disabled, cf. trac #13667**). </code> --- it should be <em><code>:trac:`13667`</code></em> since it will be in the documentation.
</li><li><code> Parameter "algorithm" has the same meaning as in codesize_upper_bound() </code> --- This should be <em><code>:func:`codesize_upper_bound`</code></em>.
</li><li><code> print "Wrong q_base=", q_base, " for q=", q, kk</code> --- This can be formatted python3 style as
<pre class="wiki"> print "Wrong q_base={} for q={} {}".format(q_base, q, kk)
</pre></li><li>According to the patchbot this needs rebasing against some higher version of 5.6. I have only beta0 here; I will check it against rc1 after I have compiled that.
</li><li>EDIT: I forgot.. the deprecation notice should go. It has been two years. If code_bounds needs to be cleaned then I can do that.
</li></ol><p>
EDIT: Update backticks in 6., 10., 11.
</p>
TicketknsamWed, 20 Feb 2013 16:45:16 GMTstatus changed
https://trac.sagemath.org/ticket/12418#comment:28
https://trac.sagemath.org/ticket/12418#comment:28
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
This patch needs to address referee's comments. I am changing this to <code>needs_work</code> in the meanwhile.
</p>
TicketdimpaseSat, 15 Jun 2013 13:46:39 GMTattachment set
https://trac.sagemath.org/ticket/12418
https://trac.sagemath.org/ticket/12418
<ul>
<li><strong>attachment</strong>
set to <em>12418_delsart_bounds.2.patch</em>
</li>
</ul>
<p>
rebased for Sage 5.10 and fixed some outstanding issues
</p>
TicketdimpaseSat, 15 Jun 2013 13:53:03 GMT
https://trac.sagemath.org/ticket/12418#comment:29
https://trac.sagemath.org/ticket/12418#comment:29
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:27" title="Comment 27">ppurka</a>:
</p>
<p>
rebased to Sage 5.10 and fixed the following:
</p>
<blockquote class="citation">
<ol><li><code>Krawtchouk</code> is missing a doctest.
</li><li>There is no need of <code>\</code> in <code>def delsarte_bound_...</code>
</li><li>There are still many trailing whitespaces. If you use vim then you can try this command <code>:%s/[ ]\+$//</code>
</li><li><code> - ``q`` -- the length of the alphabet</code> -- this should be "the <em>size</em> of the alphabet"
</li></ol><blockquote>
<p>
Also I think the the options <code>q</code> and <code>d</code> can be swapped to be in the order in which they appear
in the function definition.
</p>
</blockquote>
</blockquote>
<p>
I swapped the docstrings instead.
</p>
<blockquote class="citation">
<ol start="5"><li><code>- ``solver`` -- the LP/ILP solved </code> --- this should be <em>solver</em>.
What other solvers are present? They should be listed as options in this
variable.
</li><li><code>The bound on the size of the F_2-codes</code> --- this should be <em><code>`F_2`</code></em>
</li></ol></blockquote>
<p>
(and other <code>F_</code>)
</p>
<blockquote class="citation">
<ol start="8"><li>The backend should automatically handle "isinteger=True" at least so that it is functional. Currently I get a very generic Exception (why is this only "Exception"?). Maybe it is automatically handled in a later version of sage? I will have to check against 5.6.beta1 and higher:
</li></ol></blockquote>
<p>
The PPL backend does not handle ILP. One might want to improve the way it reports this error, but not on this ticket.
</p>
<blockquote class="citation">
<pre class="wiki">Exception: This backend does not handle integer variables ! Read the doc !
</pre></blockquote>
<blockquote class="citation">
<ol start="11"><li><code> Parameter "algorithm" has the same meaning as in codesize_upper_bound() </code> --- This should be <em><code>:func:`codesize_upper_bound`</code></em>.
</li><li>According to the patchbot this needs rebasing against some higher version of 5.6. I have only beta0 here; I will check it against rc1 after I have compiled that.
</li></ol></blockquote>
<p>
Rebased.
</p>
TicketdimpaseSat, 22 Jun 2013 07:39:24 GMTwork_issues set
https://trac.sagemath.org/ticket/12418#comment:30
https://trac.sagemath.org/ticket/12418#comment:30
<ul>
<li><strong>work_issues</strong>
set to <em>code refactoring</em>
</li>
</ul>
TicketppurkaSat, 22 Jun 2013 08:27:48 GMT
https://trac.sagemath.org/ticket/12418#comment:31
https://trac.sagemath.org/ticket/12418#comment:31
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:30" title="Comment 30">dimpase</a>:
</p>
<blockquote class="citation">
<p>
Work issues set to code refactoring
</p>
</blockquote>
<p>
Oh good. I was wondering if you didn't want to do that in this patch.
</p>
TicketdimpaseMon, 01 Jul 2013 14:30:55 GMTattachment set
https://trac.sagemath.org/ticket/12418
https://trac.sagemath.org/ticket/12418
<ul>
<li><strong>attachment</strong>
set to <em>12418_delsart_bounds.patch</em>
</li>
</ul>
<p>
rebased for Sage 5.10 and fixed some outstanding issues
</p>
TicketdimpaseMon, 01 Jul 2013 14:31:57 GMTattachment set
https://trac.sagemath.org/ticket/12418
https://trac.sagemath.org/ticket/12418
<ul>
<li><strong>attachment</strong>
set to <em>12418_refactored.diff</em>
</li>
</ul>
<p>
code refactoring - for review only
</p>
TicketdimpaseMon, 01 Jul 2013 14:33:49 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/12418#comment:32
https://trac.sagemath.org/ticket/12418#comment:32
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>code refactoring</em> deleted
</li>
</ul>
TicketchapotonFri, 05 Jul 2013 15:21:01 GMT
https://trac.sagemath.org/ticket/12418#comment:33
https://trac.sagemath.org/ticket/12418#comment:33
<p>
instructions for the bot:
</p>
<p>
apply 12418_delsart_bounds.patch
</p>
TicketchapotonFri, 05 Jul 2013 18:12:06 GMTstatus changed
https://trac.sagemath.org/ticket/12418#comment:34
https://trac.sagemath.org/ticket/12418#comment:34
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<ul><li>doctest covering is not 100%
</li></ul><ul><li>you can use the wikipedia role for example <code>:wikipedia:`Togo`</code>
</li></ul><ul><li>it would be better to lazy_import the new functions, maybe ?
</li></ul>
TicketdimpaseFri, 05 Jul 2013 19:06:29 GMT
https://trac.sagemath.org/ticket/12418#comment:35
https://trac.sagemath.org/ticket/12418#comment:35
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12418#comment:34" title="Comment 34">chapoton</a>:
</p>
<blockquote class="citation">
<ul><li>doctest covering is not 100%
</li></ul></blockquote>
<p>
hmm, what function do you mean? there is an internal function which is not exported; I don't think it needs a doctest, does it?
</p>
<blockquote class="citation">
<ul><li>you can use the wikipedia role for example <code>:wikipedia:`Togo`</code>
</li></ul></blockquote>
<p>
where?
</p>
<blockquote class="citation">
<ul><li>it would be better to lazy_import the new functions, maybe ?
</li></ul></blockquote>
<p>
I have no idea. Is there a stated policy on this?
Having said this, perhaps it's better to re-lazy_import the whole <code>sage/coding</code>, something for another ticket?
</p>
TicketchapotonFri, 05 Jul 2013 19:33:31 GMT
https://trac.sagemath.org/ticket/12418#comment:36
https://trac.sagemath.org/ticket/12418#comment:36
<ul><li>well, the bot complains about the missing doctest, so I guess that the internal function needs one indeed
</li></ul><ul><li>instead of <code>`en.wikipedia.org/wiki/Kravchuk_polynomials <http://en.wikipedia.org/wiki/Kravchuk_polynomials>`_</code>
</li></ul><p>
you can write <code>:wikipedia:`Kravchuk_polynomials`</code>
</p>
<ul><li>the bot is not happy either on adding something new in the global namespace. It is better for the startup time of sage to try and make the bot happy on this point, imho.
</li></ul>
TicketdimpaseSat, 06 Jul 2013 22:00:18 GMTattachment set
https://trac.sagemath.org/ticket/12418
https://trac.sagemath.org/ticket/12418
<ul>
<li><strong>attachment</strong>
set to <em>12418_update.patch</em>
</li>
</ul>
<p>
update to fix the remaining issues
</p>
TicketdimpaseSat, 06 Jul 2013 22:01:52 GMTstatus, description changed
https://trac.sagemath.org/ticket/12418#comment:37
https://trac.sagemath.org/ticket/12418#comment:37
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12418?action=diff&version=37">diff</a>)
</li>
</ul>
TicketppurkaThu, 18 Jul 2013 07:45:03 GMTstatus changed
https://trac.sagemath.org/ticket/12418#comment:38
https://trac.sagemath.org/ticket/12418#comment:38
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
The patch looks OK to me now. Though I would have really liked the Q-matrix to be passed to the linear program (for instance to the delsarte LP building function), this can be done in a future patch when LP for other spaces are introduced.
</p>
TicketppurkaThu, 18 Jul 2013 07:52:37 GMTreviewer, author set
https://trac.sagemath.org/ticket/12418#comment:39
https://trac.sagemath.org/ticket/12418#comment:39
<ul>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton, Punarbasu Purkayastha</em>
</li>
<li><strong>author</strong>
set to <em>Dmitrii Pasechnik</em>
</li>
</ul>
TicketjdemeyerSun, 21 Jul 2013 21:42:07 GMTmilestone changed
https://trac.sagemath.org/ticket/12418#comment:40
https://trac.sagemath.org/ticket/12418#comment:40
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketjdemeyerFri, 16 Aug 2013 21:10:45 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/12418#comment:41
https://trac.sagemath.org/ticket/12418#comment:41
<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>merged</strong>
set to <em>sage-5.12.beta1</em>
</li>
</ul>
Ticket