Sage: Ticket #19777: Three new SRGs and db update
https://trac.sagemath.org/ticket/19777
<p>
Andries Brouwer's database has been updated, and this ticket forwards the changes to Sage's copy of it.
</p>
<p>
4 graphs have been added to it, 3 of which are built from 2-intersection codes. The last one comes from a reference I haven't been able to find yet.
</p>
<p>
Nathann
</p>
<p>
<a class="ext-link" href="http://www.steinertriples.fr/ncohen/tmp/graphs-20151224.tar.bz2"><span class="icon"></span>http://www.steinertriples.fr/ncohen/tmp/graphs-20151224.tar.bz2</a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/19777
Trac 1.1.6ncohenThu, 24 Dec 2015 12:43:42 GMTstatus changed; branch set
https://trac.sagemath.org/ticket/19777#comment:1
https://trac.sagemath.org/ticket/19777#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>branch</strong>
set to <em>public/19777</em>
</li>
</ul>
TicketgitThu, 24 Dec 2015 12:43:45 GMTcommit set
https://trac.sagemath.org/ticket/19777#comment:2
https://trac.sagemath.org/ticket/19777#comment:2
<ul>
<li><strong>commit</strong>
set to <em>bb930ca4c4e9314670f4b64aab956c6e4eeb6e05</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=bb930ca4c4e9314670f4b64aab956c6e4eeb6e05"><span class="icon"></span>bb930ca</a></td><td><code>trac #19777: Three new SRGs and db update</code>
</td></tr></table>
TicketdimpaseThu, 24 Dec 2015 14:34:14 GMT
https://trac.sagemath.org/ticket/19777#comment:3
https://trac.sagemath.org/ticket/19777#comment:3
<p>
I think I already mentioned on another ticket that 2-intersection codes and 2-distance codes are (almost) the same thing. Why don't you add these 2-intersection codes to the corr. db, instead of hardcoding them into strongly_regular_graphs_db?
</p>
TicketdimpaseThu, 24 Dec 2015 15:15:01 GMT
https://trac.sagemath.org/ticket/19777#comment:4
https://trac.sagemath.org/ticket/19777#comment:4
<p>
a 2-intersection code is a projective 2-weight code:
e.g. take L from <code>SRG_1024_363_122_132()</code> and do
</p>
<pre class="wiki">sage: K = GF(2**2,'x')
sage: x = K.gens()[0]
sage: L = [map({'0':0,'1':1,'a':x,'b':x**2}.get,xx) for xx in L]
sage: L = Matrix(K,map(list,L)).transpose()
sage: c = LinearCode(L); c
Linear code of length 121, dimension 5 over Finite Field in x of size 2^2
sage: [w for w,f in enumerate(c.weight_distribution()) if w and f]
[88, 96]
sage: c.weight_enumerator()
x^121 + 660*x^33*y^88 + 363*x^25*y^96
</pre><p>
so you have 0 word, 660 words of weight 88, and 363 of weight 96.
</p>
TicketncohenThu, 24 Dec 2015 16:06:42 GMT
https://trac.sagemath.org/ticket/19777#comment:5
https://trac.sagemath.org/ticket/19777#comment:5
<p>
Hmmmm.. I used your code and generated the graph from the two weights code. For some reason it takes infinitely more time.
</p>
<pre class="wiki">sage: %time strongly_regular_from_two_weight_code(c)
CPU times: user 19 s, sys: 104 ms, total: 19.1 s
Wall time: 18.5 s
Graph on 1024 vertices
</pre>
TicketdimpaseThu, 24 Dec 2015 16:09:57 GMT
https://trac.sagemath.org/ticket/19777#comment:6
https://trac.sagemath.org/ticket/19777#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:5" title="Comment 5">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Hmmmm.. I used your code and generated the graph from the two weights code. For some reason it takes infinitely more time.
</p>
</blockquote>
<p>
well, all I am saying is that these matrices etc should go into the database; it's another story how to use them - nothing prevents you from calling the faster function on them...
</p>
TicketncohenThu, 24 Dec 2015 16:11:35 GMT
https://trac.sagemath.org/ticket/19777#comment:7
https://trac.sagemath.org/ticket/19777#comment:7
<blockquote class="citation">
<p>
well, all I am saying is that these matrices etc should go into the database; it's another story how to use them - nothing prevents you from calling the faster function on them...
</p>
</blockquote>
<p>
I understand, yet what you ask represents a big amount of work if you insist to make me do all of it.
</p>
TicketdimpaseThu, 24 Dec 2015 16:17:11 GMT
https://trac.sagemath.org/ticket/19777#comment:8
https://trac.sagemath.org/ticket/19777#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:7" title="Comment 7">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
well, all I am saying is that these matrices etc should go into the database; it's another story how to use them - nothing prevents you from calling the faster function on them...
</p>
</blockquote>
<p>
I understand, yet what you ask represents a big amount of work if you insist to make me do all of it.
</p>
</blockquote>
<p>
I can do the work, it's not a problem (although I currently have keyboard/mouse elbow, and should not do much typing for a while), but do you agree that by right this data must be in the <code>coding/</code> ?
</p>
TicketncohenThu, 24 Dec 2015 16:19:16 GMT
https://trac.sagemath.org/ticket/19777#comment:9
https://trac.sagemath.org/ticket/19777#comment:9
<blockquote class="citation">
<p>
I can do the work, it's not a problem (although I currently have keyboard/mouse elbow, and should not do much typing for a while), but do you agree that by right this data must be in the <code>coding/</code> ?
</p>
</blockquote>
<p>
Yeah yeah that's where it should be. At the moment I am trying to figure out what exactly needs to be done, and how. Turns out that the difference between a two-weight code and a two intersection set is merely a matrix transposition, is it?
</p>
<p>
Nathann
</p>
TicketncohenThu, 24 Dec 2015 16:20:05 GMT
https://trac.sagemath.org/ticket/19777#comment:10
https://trac.sagemath.org/ticket/19777#comment:10
<pre class="wiki">sage: from sage.coding.two_weight_db import data
sage: %time strongly_regular_from_two_intersection_set(data[-1]['M'].transpose())
CPU times: user 452 ms, sys: 24 ms, total: 476 ms
Wall time: 436 ms
Graph on 625 vertices
sage: %time strongly_regular_from_two_weight_code(data[-1]['M'])
CPU times: user 1.68 s, sys: 16 ms, total: 1.7 s
Wall time: 1.67 s
Graph on 625 vertices
</pre>
TicketncohenThu, 24 Dec 2015 16:22:23 GMT
https://trac.sagemath.org/ticket/19777#comment:11
https://trac.sagemath.org/ticket/19777#comment:11
<p>
Okay, everything looks fairly straightforward. The only problem is with the SRG parameter 'guessing' from the two_weight codes. If we do the operation through the matrix's transpose I have no idea what parameters we end up with.
</p>
<p>
Nathann
</p>
TicketdimpaseThu, 24 Dec 2015 16:33:36 GMT
https://trac.sagemath.org/ticket/19777#comment:12
https://trac.sagemath.org/ticket/19777#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:11" title="Comment 11">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Okay, everything looks fairly straightforward. The only problem is with the SRG parameter 'guessing' from the two_weight codes. If we do the operation through the matrix's transpose I have no idea what parameters we end up with.
</p>
</blockquote>
<p>
It seems that k will be one of eigenvalue multiplicities of the "usual" graph. I.e. often the same, e.g. for data on this ticket they are the same, but not always --- that's where formulae on Chen's page go wrong. One of these f, g:
</p>
<pre class="wiki"> # multiplicity of eigenvalues 'r,s' (f=lambda_r, g=lambda_s)
#
# They are integers (checked by the 'integrality condition').
f = -k*(s+1)*(k-s)/((k+r*s)*(r-s))
g = k*(r+1)*(k-r)/((k+r*s)*(r-s))
</pre><p>
Details are in <a class="ext-link" href="http://pages.uoregon.edu/kantor/PAPERS/2-WeightCodes.pdf"><span class="icon"></span>http://pages.uoregon.edu/kantor/PAPERS/2-WeightCodes.pdf</a>.
</p>
TicketncohenThu, 24 Dec 2015 17:45:40 GMT
https://trac.sagemath.org/ticket/19777#comment:13
https://trac.sagemath.org/ticket/19777#comment:13
<p>
I still don't see a way to do the job cleanly.
</p>
TicketdimpaseThu, 24 Dec 2015 18:21:53 GMT
https://trac.sagemath.org/ticket/19777#comment:14
https://trac.sagemath.org/ticket/19777#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:13" title="Comment 13">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I still don't see a way to do the job cleanly.
</p>
</blockquote>
<p>
Do you mean a procedure to give possible parameters of a projective 2-weight code from (v,k,l,mu)?
Anyway, a part of the job is to move these L's and the related info into the two-weight code database.
</p>
TicketncohenThu, 24 Dec 2015 18:43:14 GMT
https://trac.sagemath.org/ticket/19777#comment:15
https://trac.sagemath.org/ticket/19777#comment:15
<blockquote class="citation">
<p>
Do you mean a procedure to give possible parameters of a projective 2-weight code from (v,k,l,mu)?
</p>
</blockquote>
<p>
I mean a way to use the "SRG from 2 intersection" routine on the two-weight code instead of the current function we use. It's much faster, but if we do that we don't know how to predict which parameters we will end up with.
</p>
<blockquote class="citation">
<p>
Anyway, a part of the job is to move these L's and the related info into the two-weight code database.
</p>
</blockquote>
<p>
True but that leaves an unpleasant feeling of just not doing what needs to be done.
</p>
<p>
Nathann
</p>
TicketdimpaseThu, 24 Dec 2015 19:41:01 GMT
https://trac.sagemath.org/ticket/19777#comment:16
https://trac.sagemath.org/ticket/19777#comment:16
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:15" title="Comment 15">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Do you mean a procedure to give possible parameters of a projective 2-weight code from (v,k,l,mu)?
</p>
</blockquote>
<p>
I mean a way to use the "SRG from 2 intersection" routine on the two-weight code instead of the current function we use. It's much faster, but if we do that we don't know how to predict which parameters we will end up with.
</p>
</blockquote>
<p>
I thought we don't have this implemented for the two-weight code graph on its words, do we?
</p>
<p>
Here we are in a better shape: there are formulas from Cor.3.7 of Calderbank-Kantor, written also on on Eric Chen's pages.
My understanding is that they give the parameters of "SRG from 2 intersection".
(or perhaps its complement - this is easy to figure out).
This will answer the question
</p>
<p>
"is there a 2-intersection proj. set giving (v,k,l,mu)-SRG". <strong>(A)</strong>
</p>
<hr />
<p>
To get the parameters of the graph of codewords of the corresponding 2-weight code, one needs the duality of assoc. schemes (Thm 5.7 and the discussion after it in Calderbank-Kantor).
It is easy to compute them directly from graph parameters (via eigenvalues etc).
I'd be happy to provide an implementation of it.
Thus, to answer the question
</p>
<p>
"is there a 2-weight code giving (v,k,l,mu)-SRG" <strong>(B)</strong>,
</p>
<p>
one will compute the parameters (v,k',l',mu') of the dual (note that A==dual(dual(A)), and answer <strong>(A)</strong> for (v,k',l',mu'). Then use Thm 3.1 (p.100, same text), which tells one how to switch between (n,k,h_1,h_2) and parameters of the corresponding 2-weight code.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Anyway, a part of the job is to move these L's and the related info into the two-weight code database.
</p>
</blockquote>
<p>
True but that leaves an unpleasant feeling of just not doing what needs to be done.
</p>
</blockquote>
<p>
above is the plan, what do you think about it?
</p>
<p>
Dima
</p>
TicketgitThu, 24 Dec 2015 22:44:37 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:17
https://trac.sagemath.org/ticket/19777#comment:17
<ul>
<li><strong>commit</strong>
changed from <em>bb930ca4c4e9314670f4b64aab956c6e4eeb6e05</em> to <em>4d2c2f4496c95fa6b6cf2187747d62e3609677d3</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=4d2c2f4496c95fa6b6cf2187747d62e3609677d3"><span class="icon"></span>4d2c2f4</a></td><td><code>trac #19777: Three new SRGs and db update</code>
</td></tr></table>
TicketncohenThu, 24 Dec 2015 22:46:13 GMT
https://trac.sagemath.org/ticket/19777#comment:18
https://trac.sagemath.org/ticket/19777#comment:18
<blockquote class="citation">
<p>
above is the plan, what do you think about it?
</p>
</blockquote>
<p>
Here is my answer, as an admittedly cleaner commit.
</p>
<p>
If you know how to find your way in order to make <code>strongly_regular_from_two_weight_code(L)</code> as fast as <code>strongly_regular_from_two_intersection_set(L.transpose())</code>, we will definitely have gained something <code>O_o</code>
</p>
<p>
Nathann
</p>
TicketgitFri, 25 Dec 2015 13:58:23 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:19
https://trac.sagemath.org/ticket/19777#comment:19
<ul>
<li><strong>commit</strong>
changed from <em>4d2c2f4496c95fa6b6cf2187747d62e3609677d3</em> to <em>93bd35710e758924c7015a1b417eba94eb2d8bd5</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=93bd35710e758924c7015a1b417eba94eb2d8bd5"><span class="icon"></span>93bd357</a></td><td><code>trac #19777: Convert the other 2-intersection set</code>
</td></tr></table>
TicketncohenFri, 25 Dec 2015 14:01:38 GMT
https://trac.sagemath.org/ticket/19777#comment:20
https://trac.sagemath.org/ticket/19777#comment:20
<p>
I converted the old SRG from Disset into a code too. Cleaner. Slower, but cleaner.
</p>
TicketdimpaseFri, 25 Dec 2015 16:40:08 GMT
https://trac.sagemath.org/ticket/19777#comment:21
https://trac.sagemath.org/ticket/19777#comment:21
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:20" title="Comment 20">ncohen</a>:
</p>
<blockquote class="citation">
<p>
I converted the old SRG from Disset into a code too. Cleaner. Slower, but cleaner.
</p>
</blockquote>
<p>
Why has it got slower? I don't follow you here, sorry.
</p>
TicketncohenFri, 25 Dec 2015 16:46:33 GMT
https://trac.sagemath.org/ticket/19777#comment:22
https://trac.sagemath.org/ticket/19777#comment:22
<blockquote class="citation">
<p>
Why has it got slower? I don't follow you here, sorry.
</p>
</blockquote>
<p>
Because building a graph using the matrix takes a different time if you go through a two-weigth code of through the equivalent 2-intersection set. That's what I was saying in <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:18" title="Comment 18">18</a> and in <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:10" title="Comment 10">10</a>.
</p>
<p>
That's the thing that disturbs me. If we can make one function as fast as the other, then everything is fine.
</p>
<p>
Nathann
</p>
TicketncohenFri, 25 Dec 2015 16:47:09 GMT
https://trac.sagemath.org/ticket/19777#comment:23
https://trac.sagemath.org/ticket/19777#comment:23
<p>
(and the time differences increases quickly with the size of the graph you build)
</p>
TicketdimpaseFri, 25 Dec 2015 16:53:18 GMT
https://trac.sagemath.org/ticket/19777#comment:24
https://trac.sagemath.org/ticket/19777#comment:24
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:22" title="Comment 22">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Why has it got slower? I don't follow you here, sorry.
</p>
</blockquote>
<p>
Because building a graph using the matrix takes a different time if you go through a two-weigth code of through the equivalent 2-intersection set. That's what I was saying in <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:18" title="Comment 18">18</a> and in <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:10" title="Comment 10">10</a>.
</p>
<p>
That's the thing that disturbs me. If we can make one function as fast as the other, then everything is fine.
</p>
</blockquote>
<p>
but why do you build it via a slower function, despite a faster function being available?
</p>
TicketncohenFri, 25 Dec 2015 17:18:15 GMT
https://trac.sagemath.org/ticket/19777#comment:25
https://trac.sagemath.org/ticket/19777#comment:25
<p>
............. because you made me do it ?..
</p>
TicketncohenFri, 25 Dec 2015 17:20:48 GMT
https://trac.sagemath.org/ticket/19777#comment:26
https://trac.sagemath.org/ticket/19777#comment:26
<p>
What the hell man, I had those four functions in the strongly_regular_db file and you asked me to add them inside of the two-weight database. Now they are in he two-weight database and the SRG that correspond are built as they always were, through the "SRG from 2-weight code" function.
</p>
<p>
I thought that you said you knew how to guess the parameters of the SRG that would be obtained when using the "SRG from 2-intersection code". Because that's the problem, in case it needs be said again: I cannot replace the first function by the other, for I don't know what exactly the parameters of the SRG will be. Will I get what I expect or its complement?
</p>
<p>
If you can guess that then you can use the faster of the two functions.
</p>
<p>
Nathann
</p>
TicketdimpaseFri, 25 Dec 2015 18:10:47 GMT
https://trac.sagemath.org/ticket/19777#comment:27
https://trac.sagemath.org/ticket/19777#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:26" title="Comment 26">ncohen</a>:
</p>
<blockquote class="citation">
<p>
What the hell man, I had those four functions in the strongly_regular_db file and you asked me to add them inside of the two-weight database. Now they are in he two-weight database and the SRG that correspond are built as they always were, through the "SRG from 2-weight code" function.
</p>
</blockquote>
<p>
Sorry, I forgot that that DB gets processed a _build_small_srg_database() in its entirety.
Now I looked at the code ans see that this is the case.
</p>
<p>
OK, I will speed it up. Where is the main slowness - is it in <code>strongly_regular_from_two_weight_code</code>, or in the main body of <code>_build_small_srg_database()</code> ?
</p>
<p>
The computations in the latter can be replaced by what I explained in comment 16.
I don't know how to speed up <code>strongly_regular_from_two_weight_code</code>, but in most
cases (in particular for v=1024) it can be replaced by <code>strongly_regular_from_two_intersection_set</code>.
</p>
<p>
Dima
</p>
TicketncohenFri, 25 Dec 2015 18:14:27 GMT
https://trac.sagemath.org/ticket/19777#comment:28
https://trac.sagemath.org/ticket/19777#comment:28
<blockquote class="citation">
<p>
OK, I will speed it up. Where is the main slowness - is it in <code>strongly_regular_from_two_weight_code</code>, or in the main body of <code>_build_small_srg_database()</code> ?
</p>
</blockquote>
<p>
In <code>strongly_regular_from_two_weight_code</code>, for it performs a compuation on every pair of points in the code. It is not the case for <code>strongly_regular_from_two_intersection_set</code>, as you can see from its code.
</p>
<blockquote class="citation">
<p>
The computations in the latter can be replaced by what I explained in comment 16.
I don't know how to speed up <code>strongly_regular_from_two_weight_code</code>, but in most
cases (in particular for v=1024) it can be replaced by <code>strongly_regular_from_two_intersection_set</code>.
</p>
</blockquote>
<p>
I do not mind if all that is being done is replacing the first function by the other. Actually I wouldn't mind if that were the case, the only problem is with the graph's parameters.
</p>
<p>
Or perhaps we can build one, and if it does not match return its complement. Dirty, but operationnal.
</p>
<p>
Nathann
</p>
TicketdimpaseFri, 25 Dec 2015 22:59:49 GMT
https://trac.sagemath.org/ticket/19777#comment:29
https://trac.sagemath.org/ticket/19777#comment:29
<p>
I did checks, and out of 22 entries in the 2-weight codes db, 18 are self-dual, that is
one can use <code>strongly_regular_from_two_intersection_set</code> on the transpose of their matrices
(more precisely, <code>strongly_regular_from_two_intersection_set</code> builds the complement of the graph,
but this is fine (we'd adjust doctests).
</p>
<p>
For the remaining 4 cases, I checked what one gets by using <code>strongly_regular_from_two_intersection_set</code> on the transpose of their matrices.
</p>
<p>
2-wt code of (512, 315, 202, 180) gives the graph of GQ(7,9).
</p>
<p>
2-wt code of (512, 219, 106, 84) gives (512, 73, 10, 12)
and correspondingly
2-wt code of (512, 73, 12, 10) gives (512, 219, 106, 84)
(that is, it suffices to use just one of these 2-wt codes to get graphs)
</p>
<p>
2-wt code of (243, 220, 199, 200) gives (243, 110, 37, 60)
(that is, <code>SRG_243_110_37_60()</code> can be removed, or not just used...)
</p>
TicketgitSat, 26 Dec 2015 00:16:11 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:30
https://trac.sagemath.org/ticket/19777#comment:30
<ul>
<li><strong>commit</strong>
changed from <em>93bd35710e758924c7015a1b417eba94eb2d8bd5</em> to <em>1f08db56c47170d996c21e9ae720a717160b2093</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=e28f719bafa0e3260d4e4dc93349e991f59dd192"><span class="icon"></span>e28f719</a></td><td><code>Merge branch 'develop' of git://trac.sagemath.org/sage into develop</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=1f08db56c47170d996c21e9ae720a717160b2093"><span class="icon"></span>1f08db5</a></td><td><code>make 2-wt codes stuff more efficient</code>
</td></tr></table>
TicketdimpaseSat, 26 Dec 2015 08:06:52 GMT
https://trac.sagemath.org/ticket/19777#comment:31
https://trac.sagemath.org/ticket/19777#comment:31
<p>
this will need a bit more work --- not 100% ready for review yet. One part of it works more by an accident than due to theory.
</p>
TicketncohenSat, 26 Dec 2015 08:32:52 GMT
https://trac.sagemath.org/ticket/19777#comment:32
https://trac.sagemath.org/ticket/19777#comment:32
<p>
Yooooooo !
</p>
<p>
Do you mind if we move your last commit -- and the optimization issue -- to another ticket ? It would be cool to have those new srg, and the update of the db as well, in Sage asap.
</p>
<p>
I can split it myself if you prefer.
</p>
<p>
Thanks,
</p>
<p>
Nathann
</p>
TicketdimpaseSat, 26 Dec 2015 12:31:29 GMT
https://trac.sagemath.org/ticket/19777#comment:33
https://trac.sagemath.org/ticket/19777#comment:33
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:32" title="Comment 32">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Do you mind if we move your last commit -- and the optimization issue -- to another ticket ? It would be cool to have those new srg, and the update of the db as well, in Sage asap.
</p>
</blockquote>
<p>
we are travelling today back to Oxford, and I know what I want to change.
I think it should be ready tomorrow morning or earlier.
</p>
TicketncohenSat, 26 Dec 2015 12:36:28 GMT
https://trac.sagemath.org/ticket/19777#comment:34
https://trac.sagemath.org/ticket/19777#comment:34
<p>
Okay then,
</p>
<p>
Nathann
</p>
TicketgitSat, 26 Dec 2015 22:51:35 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:35
https://trac.sagemath.org/ticket/19777#comment:35
<ul>
<li><strong>commit</strong>
changed from <em>1f08db56c47170d996c21e9ae720a717160b2093</em> to <em>205bdd5b2639d6e0f6d55d2a85c8ee23087ab718</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=205bdd5b2639d6e0f6d55d2a85c8ee23087ab718"><span class="icon"></span>205bdd5</a></td><td><code>guard against runtime errors, remove useless check</code>
</td></tr></table>
TicketdimpaseSat, 26 Dec 2015 22:53:15 GMT
https://trac.sagemath.org/ticket/19777#comment:36
https://trac.sagemath.org/ticket/19777#comment:36
<p>
OK, ready now :-)
</p>
TicketdimpaseSun, 27 Dec 2015 09:33:51 GMT
https://trac.sagemath.org/ticket/19777#comment:37
https://trac.sagemath.org/ticket/19777#comment:37
<p>
PS. (for a follow-up ticket?) I don't see why the 2-wt codes database does not store the complete weight enumerator, but
computes it all the time from scratch. As well, one should be aware of the corr. function:
</p>
<pre class="wiki">sage: L=LinearCode(M); L
Linear code of length 65, dimension 4 over Finite Field of size 5
sage: e=L.weight_enumerator(); e
x^65 + 364*x^15*y^50 + 260*x^10*y^55
</pre><p>
allows one to get all the needed info without going through the code explicitly:
</p>
<pre class="wiki">sage: e.substitute(x=1)
260*y^55 + 364*y^50 + 1
sage: e.substitute(x=1).coefficients()
[260, 364, 1]
sage: map(lambda x:x[1], e.substitute(x=1).exponents())
[55, 50, 0]
</pre>
TicketncohenSun, 27 Dec 2015 10:39:00 GMT
https://trac.sagemath.org/ticket/19777#comment:38
https://trac.sagemath.org/ticket/19777#comment:38
<blockquote class="citation">
<p>
OK, ready now :-)
</p>
</blockquote>
<p>
Could you:
</p>
<p>
1) Define what the '1s eigenmatrix' is, or point toward somewhere which defines it?
</p>
<p>
2) This function has no reason to be a 'cdef' function, given that it calls high-level functions like 'matrix'. You don't save anything with the 'cdef', and removing it will enable you to add doctests.
</p>
<p>
3) Why should we keep <code>SRG_243_110_37_60</code> if you say that we don't use it, and that we obtain the same graph by another way?
</p>
<p>
4) Could you add in the code an indication/reference for this new filter:
</p>
<pre class="wiki">if 1+f+g != v: # the only other eigenvalue, k, has multiplicity 1'
</pre><p>
All other filters should already have such a reference
</p>
<p>
5) I'm a bit worried about this new filter: does it discard any new entry? I thought that the filters we had already matched Andries Brouwer's database.
</p>
<p>
6) Instead of <code>[function, M.transpose()]</code> could you use <code>[lambda x:function(x.transpose()), M]</code> ? The difference is that the first computes the transpose when it is run, while the other only does it when it is called.
</p>
<p>
Thanks,
</p>
<p>
Nathann
</p>
<p>
P.S.: I rebased the branch atop of the latest release, and merged your two commits
</p>
TicketncohenSun, 27 Dec 2015 10:39:17 GMTstatus changed
https://trac.sagemath.org/ticket/19777#comment:39
https://trac.sagemath.org/ticket/19777#comment:39
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketncohenSun, 27 Dec 2015 10:53:19 GMT
https://trac.sagemath.org/ticket/19777#comment:40
https://trac.sagemath.org/ticket/19777#comment:40
<p>
It seems that those two codes generate the very same two graphs
</p>
<pre class="wiki">{'q': 2, 'n': 73, 'source': 'Shared by Eric Chen [ChenDB]_.', 'w2': 40, 'w1': 32, 'k': 9}
{'q': 2, 'n': 219, 'source': 'Shared by Eric Chen [ChenDB]_.', 'w2': 112, 'w1': 96, 'k': 9}
</pre>
TicketdimpaseSun, 27 Dec 2015 14:48:08 GMT
https://trac.sagemath.org/ticket/19777#comment:41
https://trac.sagemath.org/ticket/19777#comment:41
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:40" title="Comment 40">ncohen</a>:
</p>
<blockquote class="citation">
<p>
It seems that those two codes generate the very same two graphs
</p>
<pre class="wiki">{'q': 2, 'n': 73, 'source': 'Shared by Eric Chen [ChenDB]_.', 'w2': 40, 'w1': 32, 'k': 9}
{'q': 2, 'n': 219, 'source': 'Shared by Eric Chen [ChenDB]_.', 'w2': 112, 'w1': 96, 'k': 9}
</pre></blockquote>
<p>
I suppose these are ones I mentioned in comment 29:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
2-wt code of (512, 219, 106, 84) gives (512, 73, 10, 12)
and correspondingly
2-wt code of (512, 73, 12, 10) gives (512, 219, 106, 84)
(that is, it suffices to use just one of these 2-wt codes to get graphs)
</p>
</blockquote>
</blockquote>
TicketdimpaseSun, 27 Dec 2015 15:23:57 GMT
https://trac.sagemath.org/ticket/19777#comment:42
https://trac.sagemath.org/ticket/19777#comment:42
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:38" title="Comment 38">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
OK, ready now :-)
</p>
</blockquote>
<p>
Could you:
</p>
</blockquote>
<blockquote class="citation">
<p>
3) Why should we keep <code>SRG_243_110_37_60</code> if you say that we don't use it, and that we obtain the same graph by another way?
</p>
</blockquote>
<p>
well, it's a seemingly different construction; should we move it into <code>smallgraphs</code>?
</p>
<blockquote class="citation">
<p>
4) Could you add in the code an indication/reference for this new filter:
</p>
<pre class="wiki">if 1+f+g != v: # the only other eigenvalue, k, has multiplicity 1'
</pre><p>
All other filters should already have such a reference
</p>
</blockquote>
<p>
well, it is just common sense; the adjacency matrix has 3 different eigenvalues, one of which is
k, of multiplicity 1 (and this is a classical fact about eigenvalues of nonnegative matrices),
and the other two are r and s, with multiplicities f and g. Naturally, one must have 1+f+g=v.
</p>
<p>
By the way, the reference for 'Integrality condition' (integrality of f) is very vague - I don't know whether it is meant to be [BCN89]_, and if yes, then where this is mentioned.
And why only f is checked, but not g?
</p>
<blockquote class="citation">
<p>
5) I'm a bit worried about this new filter: does it discard any new entry? I thought that the filters we had already matched Andries Brouwer's database.
</p>
</blockquote>
<p>
perhaps it does not, but it is certainly correct, and takes care of integrality of g.
</p>
<blockquote class="citation">
<p>
P.S.: I rebased the branch atop of the latest release, and merged your two commits
</p>
</blockquote>
<p>
do you want me to keep working on the branch currently on the ticket?
</p>
TicketgitSun, 27 Dec 2015 15:36:57 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:43
https://trac.sagemath.org/ticket/19777#comment:43
<ul>
<li><strong>commit</strong>
changed from <em>205bdd5b2639d6e0f6d55d2a85c8ee23087ab718</em> to <em>5b8a3fd5cb08cdfff21ca3dce73d8e5091af6b24</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=221a31f289e3d5479eee08796ce2e30a86066d76"><span class="icon"></span>221a31f</a></td><td><code>trac #19777: Three new SRGs and db update</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=cb220e8ae9ed6bb35e5f6d9924aeb68726f6381a"><span class="icon"></span>cb220e8</a></td><td><code>trac #19777: Convert the other 2-intersection set</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=5b8a3fd5cb08cdfff21ca3dce73d8e5091af6b24"><span class="icon"></span>5b8a3fd</a></td><td><code>trac #19777: make 2-wt codes stuff more efficient</code>
</td></tr></table>
TicketncohenSun, 27 Dec 2015 15:44:52 GMT
https://trac.sagemath.org/ticket/19777#comment:44
https://trac.sagemath.org/ticket/19777#comment:44
<blockquote class="citation">
<p>
well, it's a seemingly different construction; should we move it into <code>smallgraphs</code>?
</p>
</blockquote>
<p>
Argggggg, no please not in smallgraphs.. Let's keep it where the others are.
</p>
<p>
I guess it's fine to keep it if you want: I keep forgetting that you have this idea in your head of having "several instances per set of parameters", while I'm just trying to 'save' Andries Brouwer's database.
</p>
<blockquote class="citation">
<p>
well, it is just common sense; the adjacency matrix has 3 different eigenvalues, one of which is
k, of multiplicity 1 (and this is a classical fact about eigenvalues of nonnegative matrices),
and the other two are r and s, with multiplicities f and g. Naturally, one must have 1+f+g=v.
</p>
</blockquote>
<p>
Could you add a '# multiplicities of eigenvalues' somewhere ? <code>:-P</code>
</p>
<p>
Only because I am an illiterate idiot <code>:-P</code>
</p>
<blockquote class="citation">
<p>
By the way, the reference for 'Integrality condition' (integrality of f) is very vague - I don't know whether it is meant to be [BCN89]_, and if yes, then where this is mentioned.
And why only f is checked, but not g?
</p>
</blockquote>
<p>
If that bothers you, then surely you understand why I prefer to have clear references for those filters <code>:-P</code>
</p>
<blockquote class="citation">
<p>
perhaps it does not, but it is certainly correct, and takes care of integrality of g.
</p>
</blockquote>
<p>
Okay okay. For the sake of symmetry.
</p>
<blockquote class="citation">
<p>
do you want me to keep working on the branch currently on the ticket?
</p>
</blockquote>
<p>
I am a dangerous and forgetful idiot, and I forgot to push the branch. It is done, sorry for the delay and if you have anything tricky to rebase because of it please give me the branch's name and I will do it for you.
</p>
<p>
Nathann
</p>
TicketgitSun, 27 Dec 2015 19:27:34 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:45
https://trac.sagemath.org/ticket/19777#comment:45
<ul>
<li><strong>commit</strong>
changed from <em>5b8a3fd5cb08cdfff21ca3dce73d8e5091af6b24</em> to <em>9b0c141e745a8155e6d2b030116167e3f39a5ab0</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=9b0c141e745a8155e6d2b030116167e3f39a5ab0"><span class="icon"></span>9b0c141</a></td><td><code>from cdef to def with docs added, etc</code>
</td></tr></table>
TicketdimpaseSun, 27 Dec 2015 19:28:45 GMTstatus, author changed; reviewer set
https://trac.sagemath.org/ticket/19777#comment:46
https://trac.sagemath.org/ticket/19777#comment:46
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen, Dima Pasechnik</em>
</li>
<li><strong>author</strong>
changed from <em>Nathann Cohen</em> to <em>Nathann Cohen, Dima Pasechnik</em>
</li>
</ul>
TicketgitMon, 28 Dec 2015 14:37:16 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:47
https://trac.sagemath.org/ticket/19777#comment:47
<ul>
<li><strong>commit</strong>
changed from <em>9b0c141e745a8155e6d2b030116167e3f39a5ab0</em> to <em>ab7dce9d05ea183f546a251f071f3ff933af855a</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=14bdcab2ac7044d8554f37f084cf8c398dde02d6"><span class="icon"></span>14bdcab</a></td><td><code>Trac 19778: McFarland 1973 difference set construction</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=8bd17be0e663eb02be619bf9e8feba5067e288f5"><span class="icon"></span>8bd17be</a></td><td><code>Trac 19778: input blocks</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=b3dd88ae6ff747f6c67ca20948b58269dcac73cd"><span class="icon"></span>b3dd88a</a></td><td><code>Trac 19778: code reorganization in difference_family</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f01133f13bcc51cbe02aecd3e26f961038984947"><span class="icon"></span>f01133f</a></td><td><code>trac #19778: Merged with 7.0.beta1</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=67bcb95712bd5746bfc979638863bd41092fad55"><span class="icon"></span>67bcb95</a></td><td><code>trac #19777: Merged with 7.0.beta1</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ab7dce9d05ea183f546a251f071f3ff933af855a"><span class="icon"></span>ab7dce9</a></td><td><code>trac #19777: Review</code>
</td></tr></table>
TicketgitMon, 28 Dec 2015 14:42:11 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:48
https://trac.sagemath.org/ticket/19777#comment:48
<ul>
<li><strong>commit</strong>
changed from <em>ab7dce9d05ea183f546a251f071f3ff933af855a</em> to <em>7194f38c78dd4e1c463433175427a1e71929c4bb</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=8f854d087c7120cedf7c0b99740821c37b156e3c"><span class="icon"></span>8f854d0</a></td><td><code>trac #19777: make 2-wt codes stuff more efficient</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7194f38c78dd4e1c463433175427a1e71929c4bb"><span class="icon"></span>7194f38</a></td><td><code>trac #19777: Review</code>
</td></tr></table>
TicketncohenMon, 28 Dec 2015 14:42:49 GMT
https://trac.sagemath.org/ticket/19777#comment:49
https://trac.sagemath.org/ticket/19777#comment:49
<p>
Seems that I am growing more incompetent with git every day. Sorry for the mess. I cleaned it and rebased the branch again <code>:-/</code>
</p>
<p>
Nathann
</p>
TicketncohenMon, 28 Dec 2015 14:50:14 GMT
https://trac.sagemath.org/ticket/19777#comment:50
https://trac.sagemath.org/ticket/19777#comment:50
<p>
Some remarks about your commit:
</p>
<p>
1) Thank you for the added info in the docstring of 'eigenmatrix'. I won't lie and say that I get all of it, but I know that the fault lies in my restricted knowledge and not in the doc. I really should hit those books <code>:-/</code>
</p>
<p>
2) replacement <code>k+r*s==mu</code> -- is that true in general? Is it checked anywhere in the code, and should we check it?
</p>
<p>
3) I am not sure that I understand how exactly this second eigenmatrix works. If <code>em==cinv*emi*cinv</code>, are you sure that there exists a strongly regular graph whose eigenmatrix is <code>vP^(-1)</code>? Or is it only because we are obtaining this SRG from a 2-intersection set? In general, when are you sure that the other strongly regular graph exists from only looking at the value of <code>vP^(-1)</code>? I wonder how general this thing is, and if it is specific to two-weight codes or if it belongs somewhere else.
</p>
<p>
Thanks,
</p>
<p>
Nathann
</p>
TicketncohenMon, 28 Dec 2015 14:51:43 GMT
https://trac.sagemath.org/ticket/19777#comment:51
https://trac.sagemath.org/ticket/19777#comment:51
<p>
4) What would you think of leaving the <code>SRG_</code> function in the index, even if that construction is overwritten by the 2-weight code one? I don't think that it hurt, and at least from the point of view of the code this list is still an index of all <code>SRG_*</code> functions.
</p>
TicketdimpaseMon, 28 Dec 2015 15:39:09 GMT
https://trac.sagemath.org/ticket/19777#comment:52
https://trac.sagemath.org/ticket/19777#comment:52
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:50" title="Comment 50">ncohen</a>:
</p>
<blockquote class="citation">
<p>
2) replacement <code>k+r*s==mu</code> -- is that true in general? Is it checked anywhere in the code, and should we check it?
</p>
</blockquote>
<p>
Thm 9.1.3(ii) in [BH12]_ tells you how to get mu and l from r and s. In particular indeed <code>k+r*s==mu</code>. It is basically a consequence of the fact that r and s are roots of a quadratic equation, with coefficients being linear functions of l and m (and then the coefficients are symmetric -- see, swapping s and r doesn't change things here -- functions of the roots, as every algebraist since Galois knows...)
</p>
<blockquote class="citation">
<p>
3) I am not sure that I understand how exactly this second eigenmatrix works. If <code>em==cinv*emi*cinv</code>, are you sure that there exists a strongly regular graph whose eigenmatrix is <code>vP^(-1)</code>?
</p>
</blockquote>
<p>
in this case <code>vP^(-1)</code> corresponds to the complement of the original graph.
As the original graph exists, its complement exists, too...
</p>
<blockquote class="citation">
<p>
Or is it only because we are obtaining this SRG from a 2-intersection set? In general, when are you sure that the other strongly regular graph exists from only looking at the value of <code>vP^(-1)</code>?
</p>
</blockquote>
<p>
It does exist if the graph has a regular group of automorphisms (in particular for graphs from
2-wt codes/projective 2-intersection sets this is the case). Then the dual graph comes from taking elements of this group as vertices, and some nontrivial way to define adjacency among them...
</p>
<blockquote class="citation">
<p>
I wonder how general this thing is, and if it is specific to two-weight codes or if it belongs somewhere else.
</p>
</blockquote>
<p>
well, yes, it is more general, but not by too much...
</p>
TicketdimpaseMon, 28 Dec 2015 15:39:31 GMT
https://trac.sagemath.org/ticket/19777#comment:53
https://trac.sagemath.org/ticket/19777#comment:53
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19777#comment:51" title="Comment 51">ncohen</a>:
</p>
<blockquote class="citation">
<p>
4) What would you think of leaving the <code>SRG_</code> function in the index, even if that construction is overwritten by the 2-weight code one? I don't think that it hurt, and at least from the point of view of the code this list is still an index of all <code>SRG_*</code> functions.
</p>
</blockquote>
<p>
as you like...
</p>
TicketgitTue, 29 Dec 2015 16:42:04 GMTcommit changed
https://trac.sagemath.org/ticket/19777#comment:54
https://trac.sagemath.org/ticket/19777#comment:54
<ul>
<li><strong>commit</strong>
changed from <em>7194f38c78dd4e1c463433175427a1e71929c4bb</em> to <em>29f123c10658cce8b05306738fcf720d5d869828</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=29f123c10658cce8b05306738fcf720d5d869828"><span class="icon"></span>29f123c</a></td><td><code>trac #19777: Keep the useless SRG_ function in the index</code>
</td></tr></table>
TicketncohenTue, 29 Dec 2015 17:23:08 GMT
https://trac.sagemath.org/ticket/19777#comment:55
https://trac.sagemath.org/ticket/19777#comment:55
<p>
Okayyyyyyyy... Good to go? <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketdimpaseWed, 30 Dec 2015 21:27:26 GMTstatus changed
https://trac.sagemath.org/ticket/19777#comment:56
https://trac.sagemath.org/ticket/19777#comment:56
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
good :-)
</p>
TicketvbraunThu, 31 Dec 2015 14:08:32 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/19777#comment:57
https://trac.sagemath.org/ticket/19777#comment:57
<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>public/19777</em> to <em>29f123c10658cce8b05306738fcf720d5d869828</em>
</li>
</ul>
Ticket