More SRGs using Regular Symmetric Hadamard matric with Constant Diagonal

[ncohen]

With this branch, we have some constructions of Regular Symmetric Hadamard matric with Constant Diagonal (RSHCD), as well as new SRG constructor (often picked from the RSHCD litterature).

[git]

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

​a414c36

trac #19018: More SRGs using Regular Symmetric Hadamard matric with Constant Diagonal

[dimpase]

+`\delta\in\{-1,+1\}` and row values all equal to `\delta \epsilon
+    \sqrt(n)`. For more information, ....
+    [BrouwerSpectra11]_.

you probably mean

+`\delta\in\{-1,+1\}` and row sums all equal to `\delta = \epsilon
+    \sqrt(n)`. For more information, ....
+    [BrouwerSpectra11]_.

Also, [BrouwerSpectra11] has two authors, it's not good to have only one name in the label. And the year is wrong. In #18972 I refer to this as [BH12]

.. [BH12] A. E. Brouwer, W. H. Haemers, 
+  Spectra of Graphs,
+  Springer, 2012
+  http://dx.doi.org/10.1007/978-1-4614-1939-6

Let's put it here in this way, [BH12], OK? Less hassle for me on #18972 then.

[git]

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

​c430b4b	trac #19018: Link the new constructions with graphs.strongly_regular_graph
​0e533bb	trac #19018: Bibliography

[ncohen]

you probably mean

No. I meant what is written. Look at the other reference (not Brouwer) that I cite after this paragraph. I added it there because it has been rather difficult to figure out what was meant by (n,epsilon)-RSHCD. That reference defines it clearly. By the way both \delta and \epsilon belong to -1,1, so the equation you wrote is never satisfied.

Let's put it here in this way, [BH12], OK? Less hassle for me on #18972 then.

Fixed.

I also added a commit I had forgotten: otherwise the new constructions are not used in graphs.strongly_regular_graph.

Nathann

[chapoton]

doc does not build

[ncohen]

doc does not build

Could you please double-check that the "failed build" is caused by this ticket?

See ​https://groups.google.com/forum/#!topic/sage-devel/tQFsu-LWto0

Nathann

[chapoton]

Yes it is. Look just a little be before in the shortlog:

OSError: [combinat ] None:6: WARNING: citation not found: BH11

[git]

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

​6893ad1

trac #19018: Typo

[chapoton]

you must also declare utf8 encoding in the file "src/sage/graphs/strongly_regular_db.pyx"

because of Jørgensen

[ncohen]

you must also declare utf8 encoding in the file "src/sage/graphs/strongly_regular_db.pyx"

because of Jørgensen

I compile the code and the doc without a problem. Why is this required?

[chapoton]

I am not so sure. I have spend some time to do a better "ascii_plugin". I made it so that it now complains only in presence of UTF8 characters in .py or .pyx files without utf8 declaration in the preamble. Which is the case here.

There is ​https://www.python.org/dev/peps/pep-0263/

But is seems to be useful only if you want unicode in the source. Maybe encoding declaration in presence of uft8 can be considered good practice anyway ?

[ncohen]

Maybe encoding declaration in presence of uft8 can be considered good practice anyway ?

Maybe it can. I personally do not care much. If it is important to you, please add a commit.

Nathann

P.S.: detecting whether a file contains utf8 characters can be done automatically. So we should not have to add it manually. Maybe this is the reason why this is apparently managed automatically.

[dimpase]

I do not like how (100, 44, 18, 20)-srg and (100, 45, 20, 20) are specified. Why don't you present them as Cayley graphs? Further, the paper you cite constructs several nonisomorphic examples of these graphs, and you don't say which ones you give.

[ncohen]

I do not like how (100, 44, 18, 20)-srg and (100, 45, 20, 20) are specified. Why don't you present them as Cayley graphs?

Because it takes several minutes to build it, and that you need to work around a bug I reported that people are still discussing (and I won't take part in it anymore)

​https://groups.google.com/d/topic/sage-devel/6rXKkF87Gtc/discussion

Further, the paper you cite constructs several nonisomorphic examples of these graphs, and you don't say which ones you give.

I do not think that it matters. I just want one.

Nathann

[ncohen]

By the way, Volker was suggesting that '==' in groups would not be group equality but representation equality. If you enjoy that kind of fun join them. But I don't have that kind of patience.

[dimpase]

Replying to ncohen:

I do not like how (100, 44, 18, 20)-srg and (100, 45, 20, 20) are specified. Why don't you present them as Cayley graphs?

Because it takes several minutes to build it,

huh? Here is an experiment with GAP, which is almost instant to run:

gap> g:=CyclicGroup(100);
<pc group of size 100 with 4 generators>
gap> l:=List([1..45], x->Random(g));
[ f2*f3, f2*f3^4*f4^2, f1*f3^4*f4^2, f1*f4^4, f2*f3^3*f4^4, f2*f3^3*f4^3, f2*f4^2, f4, f2*f3^3*f4^3, 
  f1*f4, f1*f4^3, f2*f3^4, f1*f2*f4^4, f1*f3^4*f4^4, f3^3, f1*f3^3*f4^4, f1*f3^3*f4, f2*f3^4*f4^4, 
  f1*f3^2, f3^3*f4^4, f2*f3^2*f4, f1*f3^2*f4^3, f2*f3^4, f2*f3^3*f4^2, f2*f3^3*f4, f1*f3^3*f4, f3*f4, 
  f2*f3^3*f4^4, f3^2*f4, f1*f2*f3^4*f4^4, f3^4*f4^4, f1*f3^3*f4, f1*f3^4*f4^2, f1*f3^2*f4^2, 
  f2*f3^4*f4^3, f1*f2*f3, f3, f1*f3^4, f2*f4^4, f1*f3^2, f2*f3^3, f3^2*f4, f3*f4^4, f2*f3^3*f4^2, f4^3 ]
gap> LoadPackage("grape");
true
gap> G:=CayleyGraph(g,l);
rec( 
  adjacencies := 
    [ [ 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 20, 21, 22, 23, 25, 28, 32, 33, 34, 35, 37, 41, 
          43, 46, 47, 48, 50, 51, 52, 54, 55, 59, 60, 62, 63, 64, 67, 70, 71, 72, 74, 75, 76, 80, 83, 
          84, 86, 87, 90, 92, 93, 94, 95, 96, 98, 99, 100 ] ], 
  group := <permutation group of size 100 with 4 generators>, isGraph := true, isSimple := true, 
  names := [ <identity> of ..., f1, f2, f3, f4, f1*f2, f1*f3, f1*f4, f2*f3, f2*f4, f3^2, f3*f4, f4^2, 
      f1*f2*f3, f1*f2*f4, f1*f3^2, f1*f3*f4, f1*f4^2, f2*f3^2, f2*f3*f4, f2*f4^2, f3^3, f3^2*f4, 
      f3*f4^2, f4^3, f1*f2*f3^2, f1*f2*f3*f4, f1*f2*f4^2, f1*f3^3, f1*f3^2*f4, f1*f3*f4^2, f1*f4^3, 
      f2*f3^3, f2*f3^2*f4, f2*f3*f4^2, f2*f4^3, f3^4, f3^3*f4, f3^2*f4^2, f3*f4^3, f4^4, f1*f2*f3^3, 
      f1*f2*f3^2*f4, f1*f2*f3*f4^2, f1*f2*f4^3, f1*f3^4, f1*f3^3*f4, f1*f3^2*f4^2, f1*f3*f4^3, f1*f4^4, 
      f2*f3^4, f2*f3^3*f4, f2*f3^2*f4^2, f2*f3*f4^3, f2*f4^4, f3^4*f4, f3^3*f4^2, f3^2*f4^3, f3*f4^4, 
      f1*f2*f3^4, f1*f2*f3^3*f4, f1*f2*f3^2*f4^2, f1*f2*f3*f4^3, f1*f2*f4^4, f1*f3^4*f4, f1*f3^3*f4^2, 
      f1*f3^2*f4^3, f1*f3*f4^4, f2*f3^4*f4, f2*f3^3*f4^2, f2*f3^2*f4^3, f2*f3*f4^4, f3^4*f4^2, 
      f3^3*f4^3, f3^2*f4^4, f1*f2*f3^4*f4, f1*f2*f3^3*f4^2, f1*f2*f3^2*f4^3, f1*f2*f3*f4^4, 
      f1*f3^4*f4^2, f1*f3^3*f4^3, f1*f3^2*f4^4, f2*f3^4*f4^2, f2*f3^3*f4^3, f2*f3^2*f4^4, f3^4*f4^3, 
      f3^3*f4^4, f1*f2*f3^4*f4^2, f1*f2*f3^3*f4^3, f1*f2*f3^2*f4^4, f1*f3^4*f4^3, f1*f3^3*f4^4, 
      f2*f3^4*f4^3, f2*f3^3*f4^4, f3^4*f4^4, f1*f2*f3^4*f4^3, f1*f2*f3^3*f4^4, f1*f3^4*f4^4, 
      f2*f3^4*f4^4, f1*f2*f3^4*f4^4 ], order := 100, representatives := [ 1 ], 
  schreierVector := [ -1, 1, 2, 3, 4, 2, 3, 4, 3, 4, 3, 4, 4, 3, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4, 4, 3, 4, 
      4, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 
      3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 
      4, 4, 4, 4, 4, 4, 4, 4, 4 ] )

in your case the group will be given by 3 permutation generators, but this will only make it even faster.

Further, the paper you cite constructs several nonisomorphic examples of these graphs, and you don't say which ones you give.

I do not think that it matters. I just want one.

How hard is to say that in a comment that you used pds such-and-such for group such-and-such?

[ncohen]

huh? Here is an experiment with GAP, which is almost instant to run:

Oh. Good news. Well, the best would be to rely on GAP for these computations then, for Sage does it *very* slowly.

in your case the group will be given by 3 permutation generators, but this will only make it even faster.

If you can make it work fast in Sage, I have no objection. Here is the code I used to generate it:

from sage.groups.finitely_presented import FinitelyPresentedGroup
G = FreeGroup('x,y,z')
x,y,z = G.gens()
rels = (x**5,y**5,z**4,x*y*x**(-1)*y**(-1),z*x*z**(-1)*x**(-2),z*y*z**(-1)*y**(-2))
G = FinitelyPresentedGroup(G,rels)
x,y,z = G.gens()
H = G.as_permutation_group()

L=["120","140","200","210","201","401","411","321","002","012","022","042","303","403","013","413","240","031","102","323","300","231","132","133","310","141","142","233","340","241","202","333","410","341","222","433","430","441","242","302","312","322","332","442","143"]
L = map(lambda x:map(int,x),L)
L = [G(x**xx*y**yy*z**zz) for xx,yy,zz in L]
GG = Graph()
for v in G:
    for u in L:
        uv = u*v
        GG.add_edge([v]+[x for x in G if x==uv])
        print GG.size()

How hard is to say that in a comment that you used pds such-and-such for group such-and-such?

I just do not care at all. That's why I did not. Can you acknowledge that others can have a different view on this?

I will add a commit, just to end the discussion.

Nathann

[git]

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

​d66f0b6

trac #19018: Specify which graph is built

[dimpase]

Replying to ncohen:

huh? Here is an experiment with GAP, which is almost instant to run:

Oh. Good news. Well, the best would be to rely on GAP for these computations then, for Sage does it *very* slowly.

in your case the group will be given by 3 permutation generators, but this will only make it even faster.

If you can make it work fast in Sage, I have no objection. Here is the code I used to generate it:

how about you add this code as an optional method to construct this graph (and analogous code for the other graph), and # long time tests showing that these are the graphs you claim they are.

How hard is to say that in a comment that you used pds such-and-such for group such-and-such?

I just do not care at all. That's why I did not. Can you acknowledge that others can have a different view on this?

I can contact an author of the paper in question I know, and ask his opinion. You will be in for a shock then ;-) To many people a reference of the form "this is one I fished out from [Blah]" is too vague, not only to me.

I will add a commit, just to end the discussion.

Could you change in [JK03]_. to in Tab.8.1 from [JK03]_. there? Otherwise you force the person interested to browse through most of the paper, and it is 30+ pages long.

[ncohen]

Hello,

how about you add this code as an optional method to construct this graph (and analogous code for the other graph), and # long time tests showing that these are the graphs you claim they are.

I do not want to, especially when the code is badly written in order to avoid a bug. If you care, you can add a commit. But really, it would be better to wait for the bug to be solved before writing that.

I can contact an author of the paper in question I know, and ask his opinion. You will be in for a shock then ;-)

It would change nothing even if the author has the same opinion. The status is simple: *I* do not care, which is why I did not do it. That ends your means to force me to do it. If you want to do it, there is no problem, as usual.

As for the authors, I sent them an email this morning to tell them what I did, and to thank them for the instructions.

Could you change in [JK03]_. to in Tab.8.1 from [JK03]_. there? Otherwise you force the person interested to browse through most of the paper, and it is 30+ pages long.

Will do.

Nathann

[git]

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

​1cae2dc

trac #19028: Table 8.1

[ncohen]

P.S.: If you add such tests, please mark them as "not tested", and not as "long time". I already mark as such the tests that go above 2seconds. When you have too many of them, running long tests on that file takes minutes off everybody's time. Perhaps we should have a --very-long flag.... :-/

Nathann

[dimpase]

Replying to ncohen:

P.S.: If you add such tests, please mark them as "not tested", and not as "long time". I already mark as such the tests that go above 2seconds. When you have too many of them, running long tests on that file takes minutes off everybody's time. Perhaps we should have a --very-long flag.... :-/

well, it's your Sage code that does something very slow. Here is a slight modification that is very fast:

def g1():
    from sage.groups.finitely_presented import FinitelyPresentedGroup
    G = FreeGroup('x,y,z')
    x,y,z = G.gens()
    rels = (x**5,y**5,z**4,x*y*x**(-1)*y**(-1),z*x*z**(-1)*x**(-2),z*y*z**(-1)*y**(-2))
    G = FinitelyPresentedGroup(G,rels)
    x,y,z = G.gens()
    H = G.as_permutation_group()
    L=["120","140","200","210","201","401","411","321","002","012","022","042","303","403","013","413","240","031","102","323","300","231","132","133","310","141","142","233","340","241","202","333","410","341","222","433","430","441","242","302","312","322","332","442","143"]
    L = map(lambda x:map(int,x),L)
    x,y,z=(H.0,H.1,H.2)  # from now on we work in H
    L = [H(x**xx*y**yy*z**zz) for xx,yy,zz in L]
    GG = Graph()
    for v in H:
        GG.add_edges(map(lambda u: (v,u*v), L)) # and we add edges in bunches
    return GG

gives

sage: timeit('G=g1()')
25 loops, best of 3: 13.7 ms per loop
sage: G.is_strongly_regular(parameters=True)
(100, 45, 20, 20)

Would you like to change the code to use this way to build these graphs, or prefer me doing it? In the latter case I'd appreciate having strings in L for the other graph...

[dimpase]

Replying to dimpase:

Here is a slight modification that is very fast:

def g1():
    from sage.groups.finitely_presented import FinitelyPresentedGroup
    G = FreeGroup('x,y,z')
    x,y,z = G.gens()
    rels = (x**5,y**5,z**4,x*y*x**(-1)*y**(-1),z*x*z**(-1)*x**(-2),z*y*z**(-1)*y**(-2))
    G = FinitelyPresentedGroup(G,rels)
    x,y,z = G.gens()
    H = G.as_permutation_group()
    L=["120","140","200","210","201","401","411","321","002","012","022","042","303","403","013","413","240","031","102","323","300","231","132","133","310","141","142","233","340","241","202","333","410","341","222","433","430","441","242","302","312","322","332","442","143"]
    L = map(lambda x:map(int,x),L)
    x,y,z=(H.0,H.1,H.2)  # from now on we work in H
    L = [H(x**xx*y**yy*z**zz) for xx,yy,zz in L]
    GG = Graph()
    for v in H:
        GG.add_edges(map(lambda u: (v,u*v), L)) # and we add edges in bunches
    return GG

in fact the lines

    GG = Graph()
    for v in H:
        GG.add_edges(map(lambda u: (v,u*v), L)) # and we add edges in bunches

can be replaced by

    GG = Graph(H.cayley_graph(generators=L, simple=True))

[ncohen]

well, it's your Sage code that does something very slow.

You really have your way to phrase things, Dima... Clearly there is no slowness in Sage, and I was doing it very badly.

At some point I wanted to try the permutation group version, but I did not know how to get the generators back in this version of the group. Despite the fact that it indeed works, how can you be sure that you will get the same generators, in the same order?

Would you like to change the code to use this way to build these graphs, or prefer me doing it?

You want that feature, and you apparently know more than I on the matter.

In the latter case I'd appreciate having strings in L for the other graph...

I don't have it anymore. I overwrote it with this second list.

Nathann

[git]

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

​7045124

trac #19018: Merged with 6.9.beta2

[ncohen]

(there was a conflict with the latest beta)

[dimpase]

Replying to ncohen:

At some point I wanted to try the permutation group version, but I did not know how to get the generators back in this version of the group. Despite the fact that it indeed works, how can you be sure that you will get the same generators, in the same order?

Signature:      G.as_permutation_group(limit=4096000)
Docstring:
   Return an isomorphic permutation group.

   The generators of the resulting group correspond to the images by
   the isomorphism of the generators of the given group.
...

is not clear enough?

[ncohen]

It is.

Nathann

[dimpase]

Oh, I can use _helper_payley_matrix you have written :-)

[ncohen]

What for ? O_o

[dimpase]

Replying to ncohen:

What for ? O_o

skew-symmetric Hadamard matrices I need for my srgs...

[dimpase]

if you are happy with my added commit, feel free to set it to positive review.

[ncohen]

Come on Dima... This function is only a 'cdef' function because you do not want to write doctests... It is not so bad to copy/paste code (twice) here.

Nathann

[dimpase]

Replying to ncohen:

Come on Dima... This function is only a 'cdef' function because you do not want to write doctests... It is not so bad to copy/paste code (twice) here.

No, no, no, creation of the same group twice is a deadly sin in my Book! (besides, SRG_100_44_18_20 and SRG_100_45_20_20 doctest it good enough)

And it's cdef because it is a helper function.

[ncohen]

No, no, no, creation of the same group twice is a deadly sin in my Book! (besides, SRG_100_44_18_20 and SRG_100_45_20_20 doctest it good enough)

This is ridiculous. But if you insist:

1) Make it a Python function 2) Doctest it properly 3) Rename it with a _ before its name, so that it is clearly a private function

I also find all this to be a waste of time. This is why I believe that copy/paste is better.

Nathann

[ncohen]

In "my" book, functions must be doctested unless you can't. Here, you can.

[dimpase]

Replying to ncohen:

In "my" book, functions must be doctested unless you can't. Here, you can.,

you have a number of such cdef'd functions in this file, e.g. eigenvalues. It is clear it can be doctested too...

In H_3_cayley_graph() case, it's clear it's basically a macro used in two different places, for this fine language forgot to have macros implemented... Would you like me to convert it into a decorator?!

[ncohen]

you have a number of such cdef'd functions in this file, e.g. eigenvalues. It is clear it can be doctested too...

This function is a cdef function because it needs to be fast. So it can't.

In H_3_cayley_graph() case, it's clear it's basically a macro used in two different places, for this fine language forgot to have macros implemented... Would you like me to convert it into a decorator?!

I want you to do the job properly: either you copy paste it, or you document what you write. You don't turn a function into a 'cdef' function just because you don't want to write documentation.

Besides, you don't give a positive review to your own changes. Period.

Nathann

[dimpase]

Replying to ncohen:

you have a number of such cdef'd functions in this file, e.g. eigenvalues. It is clear it can be doctested too...

This function is a cdef function because it needs to be fast. So it can't.

And we want H_3_cayley_graph() to be slow, and turn it into a pure Python function due to this? Are you kidding me?

In H_3_cayley_graph() case, it's clear it's basically a macro used in two different places, for this fine language forgot to have macros implemented... Would you like me to convert it into a decorator?!

I want you to do the job properly: either you copy paste it, or you document what you write. You don't turn a function into a 'cdef' function just because you don't want to write documentation.

Copy-pasting 10 lines of code is clearly a very bad idea. I do not understand why you even propose this.

[ncohen]

And we want H_3_cayley_graph() to be slow, and turn it into a pure Python function due to this? Are you kidding me?

Make me laugh, tell me that you declared a function that builds a graph from a group into a C function because of a speed issue.

Copy-pasting 10 lines of code is clearly a very bad idea. I do not understand why you even propose this.

Because it does not require a new function, documentation, and doctests.

Nathann

[ncohen]

Oh. Perhaps you missed something: changing the def/cdef only means that the *function call* occurs in C. What is being done inside is the same, and does not depend on how you declare the function.

[dimpase]

Replying to ncohen:

Copy-pasting 10 lines of code is clearly a very bad idea. I do not understand why you even propose this.

Because it does not require a new function, documentation, and doctests.

And it makes the code stink. Why do you ask me to make code stink?

[ncohen]

And it makes the code stink. Why do you ask me to make code stink?

Grow up. No God above forbids you to copy paste 10 lines of code. If you don't want to do that, then write the function according to Sage's standard. If you find this painful, then think again of the advantages of copy paste.

Nathann

[dimpase]

Replying to ncohen:

And it makes the code stink. Why do you ask me to make code stink?

Grow up. No God above forbids you to copy paste 10 lines of code. If you don't want to do that, then write the function according to Sage's standard. If you find this painful, then think again of the advantages of copy paste.

Gods forbid us to waste time and space. This discussion is a waste of time, and copy/pasting code is waste of space, and of time, for someone who will have to read these chunks of brainlessly duplicated code. And it is clear that copy/pasted code has no place in a quality codebase.

Nathann

[ncohen]

Write this doctest, and let's move on.

[dimpase]

Replying to ncohen:

Write this doctest, and let's move on.

One cannot directly doctest cdef'd functions, right?

[ncohen]

One cannot directly doctest cdef'd functions, right?

Dima, this function has no reason to be a cdef. So write its docstring correctly or remove your commit: my branch is correct and respects the standards.

Nathann

[ncohen]

Just in case it might convince you that copy/paste is better: note that the paper indicates that H3 is the 11th group in GAP's catalogue of groups of order 100. So you don't even need to build it by yourself.

Nathann

[dimpase]

Replying to ncohen:

Just in case it might convince you that copy/paste is better: note that the paper indicates that H3 is the 11th group in GAP's catalogue of groups of order 100. So you don't even need to build it by yourself.

I know, but this means that one would need database_gap optional package installed. If this is OK with you then I can change the code to use instead, and this would allow to get rid of the code of H_3_cayley_graph.

[ncohen]

HMmmm.... No sorry, I'd like this function to be available in pure Sage (without optional packages). If you don't mind, then could you make both available? The 'graph6' version and the group one? This way it can be built directly in Sage, but we can still check that it is valid (and optional tests are automatically run now).

Nathann

[git]

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

​6ed716d

added a doctest