Opened 6 years ago

Closed 6 years ago

#19226 closed enhancement (fixed)

some (collinearity graphs of) GQ(q-1,q+1)

Reported by: dimpase Owned by:
Priority: major Milestone: sage-6.9
Component: graph theory Keywords:
Cc: ncohen Merged in:
Authors: Dima Pasechnik Reviewers: Nathann Cohen
Report Upstream: N/A Work issues:
Branch: 894330e (Commits, GitHub, GitLab) Commit: 894330e1787253600523bea93f34ce793f25e05c
Dependencies: #19136, #19224 Stopgaps:

Status badges

Description

For SRG database, we need these. This ticket implements AS(q) (q odd prime power) and T_2*(O) constructions of GQ(q-1,q+1).

Change History (46)

comment:1 Changed 6 years ago by dimpase

  • Branch set to u/dimpase/GQ
  • Cc ncohen added
  • Commit set to 1de29de8ab7afe7805a4a3d8bb62c77dc1e3b76f

the GQs basically done (few things to check still, but it's basically there)


Last 10 new commits:

26db5ecMerge branch 'develop' of git://trac.sagemath.org/sage into NONU
d70bf50implemented recognition of NU; a bug in recongition of NO^+(2n+1,3) to fix...
2bd5f54fix for a silly bug in is_NOodd, moar doctests
a0a3320added SymplecticGraph to graphs.* and fixed a typo there, and a doctest
3bd8437else if -> elif, other things in NonisotropicOrthogonalPolarGraph
79ce567speedups by calling vector() once
dbc50b1remove forgotten prints
8078675coordinates enabled for PG designs
8d7562fGQ(q+1,q-1) and GQ(q-1,q+1) implemented and recognised in DB
1de29deremoved explicit graphs that we can now build (thanks to this ticket and NONU)

comment:2 Changed 6 years ago by dimpase

  • Dependencies set to #19136

comment:3 Changed 6 years ago by git

  • Commit changed from 1de29de8ab7afe7805a4a3d8bb62c77dc1e3b76f to 28752a80c4c1778228c4aa7a06a3e5f372b6c951

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

28752a8Merge branch 'develop' of git://trac.sagemath.org/sage into GQ

comment:4 Changed 6 years ago by git

  • Commit changed from 28752a80c4c1778228c4aa7a06a3e5f372b6c951 to 4076a47f7b7ec9c4a6d7e161429e25b0bc5231a1

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

4076a47added examples and tests for user-supplied hyperoval in T_2*(O), and small bug fixed

comment:5 Changed 6 years ago by dimpase

  • Status changed from new to needs_review

should't be hard to review, given the new beta.

comment:6 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

Hello Dima,

Here is a first-pass review.

  • coordinates: why not a boolean? Its default value is None, and you did not mention its type in the documentation.
  • Docstrings of the two new classes: we usually describe what exactly the function builds before the input section.
  • Could you add a link toward the wikipedia page on generalized quadrangles? I do not believe that we have a definition of that in Sage yet.
  • The value of check arguments is usually True.
  • As we usually disable checks when calling those functions internally (we only check whatever is returned to the user), you may be a bit less careful when you check that the hyperoval is indeed an hyperoval, e.g.: Pi.trace(O).is_uniform(2) or something (I did not check exactly yet).
  • checkhyperoval -> check_hyperoval
  • why do you name O the hyperoval, given that you have a hyperoval variable? Use that second name instead?!

Nathann

comment:7 Changed 6 years ago by git

  • Commit changed from 4076a47f7b7ec9c4a6d7e161429e25b0bc5231a1 to d4cc95be16dcf1b402bea40ae73f83833487b8ce

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

d4cc95baddressing referee's remarks

comment:8 in reply to: ↑ 6 Changed 6 years ago by dimpase

Replying to ncohen:

Here is a first-pass review.

  • coordinates: why not a boolean? Its default value is None, and you did not mention its type in the documentation.

done (see last commit)

  • Docstrings of the two new classes: we usually describe what exactly the function builds before the input section.

done

  • Could you add a link toward the wikipedia page on generalized quadrangles? I do not believe that we have a definition of that in Sage yet.

done

  • The value of check arguments is usually True.

done

  • As we usually disable checks when calling those functions internally (we only check whatever is returned to the user), you may be a bit less careful when you check that the hyperoval is indeed an hyperoval, e.g.: Pi.trace(O).is_uniform(2) or something (I did not check exactly yet).

I added a condition so that the check is only done on user's input.

  • checkhyperoval -> check_hyperoval

done.

  • why do you name O the hyperoval, given that you have a hyperoval variable? Use that second name instead?!

I don't like to mess around with values of parameters, and then O is shorter too; well, if you insist I can change this...

comment:9 follow-up: Changed 6 years ago by ncohen

Just wondered about something troublesome. Why are these graph constructors? You say explicitly that you build an incidence structure then its colinearity graph. Shouldn't they be hypergraph constructors instead?

Nathann

comment:10 follow-up: Changed 6 years ago by ncohen

  • Reviewers set to Nathann Cohen

Dima,

  • Documentation of AhrensSzekeresGQ -- the first line seems to miss backticks. Also, please write complete sentence in english and not 'of GQ AS(q)'.
  • Same function: you "define" q in the second line of the paragraph while you use it in the first.
  • Could you rewrite the lines in "set notation", i.e. {{{* `(\sigma, a, b), \sigma\in F_q}}} -> {{{* \{(\sigma, a, b): \sigma\in F_q\}`}}}?. It would be easier to understand.
  • Documentation of T2starGQ -- also needs some backticks.
  • Same function: q should also be defined at the beginning of the paragraph.
  • All graph constructors end in 'Graph'. Except the the ones you added recently, I missed that :-/
  • Please do not use GQ anywhere which is not a mathematical notation, e.g. neither in paragraphs of documentation nor in the constructor's name. As far as I know it is a global Sage convention to write everything expanded as much as possible.
  • What is the point of the hyperoval argument that lets the user specify one? It makes the code more complicated, and you do not seem to use it yourself. If you remove it, I guess that check_hyperoval can be removed too.
  • In is_GQqmqp: instead of having a 'if' inside of the 'if', could you compute q *before* the first if (using // instead of /) so that you can call is_prime directly?
  • Same function: you don't need to filter which function you should import. Import both, there is no time to save there, only added code complexity.
  • in ProjectiveGeometryDesign: could you change the default of point_coordinates?

01:00 am. Good night T_T

Nathann

P.S.: the most troublesome is probably the question above about hypergraph constructors. Note that there is a (pretty empty) hypergraphs.<tab> thing if you don't consider them to be designs.

comment:11 in reply to: ↑ 9 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

Just wondered about something troublesome. Why are these graph constructors? You say explicitly that you build an incidence structure then its colinearity graph. Shouldn't they be hypergraph constructors instead?

this equally applies to most graphs in generators/classical_geometries. (they are polar spaces, as I told you long ago: cf http://trac.sagemath.org/ticket/14532#comment:17 and later comments there; GQs are polar spaces too, and projective spaces are polar spaces, by the way)

(and probably to more "sporadic" graphs...)

so this is a massive rewrite, and not much fun...

Last edited 6 years ago by dimpase (previous) (diff)

comment:12 in reply to: ↑ 11 Changed 6 years ago by ncohen

so this is a massive rewrite, and not much fun...

Okay. Let's forget about it for the moment.

comment:13 Changed 6 years ago by git

  • Commit changed from d4cc95be16dcf1b402bea40ae73f83833487b8ce to 2a62ef16861fb421358f3d5f636cc9fc97e59011

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

2a62ef1further doc fixes

comment:14 in reply to: ↑ 10 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

Dima,

  • Documentation of AhrensSzekeresGQ -- the first line seems to miss backticks. Also, please write complete sentence in english and not 'of GQ AS(q)'.
  • Same function: you "define" q in the second line of the paragraph while you use it in the first.
  • Could you rewrite the lines in "set notation", i.e. {{{* `(\sigma, a, b), \sigma\in F_q}}} -> {{{* \{(\sigma, a, b): \sigma\in F_q\}`}}}?. It would be easier to understand.
  • Documentation of T2starGQ -- also needs some backticks.
  • Same function: q should also be defined at the beginning of the paragraph.

right, all the above is fixed in the last commit.

  • All graph constructors end in 'Graph'. Except the the ones you added recently, I missed that :-/lah

well, isn't it high time to realise that graphs.BlahBLahGraph is an abomination, for stuff in graphs.* is meant to be a graph after all...

  • Please do not use GQ anywhere which is not a mathematical notation, e.g. neither in paragraphs of documentation nor in the constructor's name. As far as I know it is a global Sage convention to write everything expanded as much as possible.
  • What is the point of the hyperoval argument that lets the user specify one? It makes the code more complicated, and you do not seem to use it yourself. If you remove it, I guess that check_hyperoval can be removed too.g

well, T_2^*(q) is in fact T_2^*(O), so I'm following the standard definition. And there is a sizable cottage industry of hyperoval production out there, so it's good to have things ready for them.

  • In is_GQqmqp: instead of having a 'if' inside of the 'if', could you compute q *before* the first if (using // instead of /) so that you can call is_prime directly?

Why? I think it's clean the way it is written. In 99% of the cases we don't even reach the 2nd if.

  • Same function: you don't need to filter which function you should import. Import both, there is no time to save there, only added code complexity.

I do not just import, I set up a function F to be called. This is why I do it this way...

  • in ProjectiveGeometryDesign: could you change the default of point_coordinates?

would it make things less efficient?

comment:15 in reply to: ↑ 14 ; follow-up: Changed 6 years ago by ncohen

Hello,

well, isn't it high time to realise that graphs.BlahBLahGraph is an abomination, for stuff in graphs.* is meant to be a graph after all...

It is an abomination, but that's the current standard in graphs.<tab>. It is still more sensible to have everything end in Graph than a different standard for each function. And, indeed, this standard is awful.

well, T_2^*(q) is in fact T_2^*(O), so I'm following the standard definition.

I do not understand this sentence, and I do not understand to what you answer.

And there is a sizable cottage industry of hyperoval production out there, so it's good to have things ready for them.

Okay.. I'll trust you for that.

Why? I think it's clean the way it is written. In 99% of the cases we don't even reach the 2nd if.

All you lose is a division per 2. You won't feel it, and the code will be ligther.

  • in ProjectiveGeometryDesign: could you change the default of point_coordinates?

would it make things less efficient?

If you can measure the difference I owe you a beer.

Nathann

comment:16 Changed 6 years ago by git

  • Commit changed from 2a62ef16861fb421358f3d5f636cc9fc97e59011 to 2b7736294074261e90e184ddd454b928833e160e

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

2b77362changed the default of point_coordinates, added a doctest

comment:17 Changed 6 years ago by git

  • Commit changed from 2b7736294074261e90e184ddd454b928833e160e to 5e0a6d77628c9637daf180a2e9b0dbdf0a869b4e

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

5e0a6d7updated is_GQqmqp to make reviewer happier

comment:18 in reply to: ↑ 15 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

well, isn't it high time to realise that graphs.BlahBLahGraph is an abomination, for stuff in graphs.* is meant to be a graph after all...

It is an abomination, but that's the current standard in graphs.<tab>. It is still more sensible to have everything end in Graph than a different standard for each function. And, indeed, this standard is awful.

Is this mere a lament? Or a request to change names of functions on this ticket? Or a proposal to change the standard?

well, T_2^*(q) is in fact T_2^*(O), so I'm following the standard definition.

I do not understand this sentence, and I do not understand to what you answer.

in the literature people write about T_2^*(O), with O a hyperoval in a plane in PG(3,q).

And there is a sizable cottage industry of hyperoval production out there, so it's good to have things ready for them.

Okay.. I'll trust you for that.

Why? I think it's clean the way it is written. In 99% of the cases we don't even reach the 2nd if.

All you lose is a division per 2. You won't feel it, and the code will be ligther.

OK, done

  • in ProjectiveGeometryDesign: could you change the default of point_coordinates?

would it make things less efficient?

OK, changed.


New commits:

5e0a6d7updated is_GQqmqp to make reviewer happier

comment:19 in reply to: ↑ 18 ; follow-up: Changed 6 years ago by ncohen

Is this mere a lament? Or a request to change names of functions on this ticket? Or a proposal to change the standard?

All of it. Please update your functions.

in the literature people write about T_2^*(O), with O a hyperoval in a plane in PG(3,q).

Oh, I see. I was reading 0 instead of O.

Nathann

comment:20 Changed 6 years ago by git

  • Commit changed from 5e0a6d77628c9637daf180a2e9b0dbdf0a869b4e to b5a2fcd90050e59021aef77f1a803aaeb65f4c55

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

b5a2fcdGraph Graph Graph...

comment:21 in reply to: ↑ 19 Changed 6 years ago by dimpase

  • Authors set to Dima Pasechnik
  • Status changed from needs_work to needs_review

Replying to ncohen:

Is this mere a lament? Or a request to change names of functions on this ticket? Or a proposal to change the standard?

All of it. Please update your functions.

done.

comment:22 follow-up: Changed 6 years ago by ncohen

In 10:

Please do not use GQ anywhere which is not a mathematical notation, e.g. neither in paragraphs of documentation nor in the constructor's name.

Also,

+    if hyperoval is None:
+        O = filter(lambda x: x[1]+x[2]*x[3]==0 or (x[1]==1 and x[2]==0 and x[3]==0), Pi)
+        O = set(O)
+    else:
+        map(lambda x: x.set_immutable(), hyperoval)
+        O = set(hyperoval)
+
+    if check_hyperoval and (not hyperoval is None):

I read:

if A:
   ...
else:
   ...
if (not A):
   ...

Could you change it into:

if hyperoval is None:
   ...
else:
   ...
   if check_hyperoval:
      ...

Then it should be good to go,

Nathann

comment:23 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:24 Changed 6 years ago by git

  • Commit changed from b5a2fcd90050e59021aef77f1a803aaeb65f4c55 to b73b175cbcc8aa8a28a84cfb3466d058406e48c4

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

b73b175replace GQ by more appropriate things, and remove extra condition in if

comment:25 Changed 6 years ago by ncohen

Despite what the commit message says, it does not replace GQ by more appropriate things.

Nathann

comment:26 in reply to: ↑ 22 ; follow-up: Changed 6 years ago by dimpase

  • Status changed from needs_work to needs_review

Replying to ncohen:

In 10:

Please do not use GQ anywhere which is not a mathematical notation, e.g. neither in paragraphs of documentation nor in the constructor's name.

While GQ is as acceptable abbreviation as LP, and LP is used a lot in Sage code and docs, I realise that I should have been more careful there, sorry...

Also,

+    if hyperoval is None:
+        O = filter(lambda x: x[1]+x[2]*x[3]==0 or (x[1]==1 and x[2]==0 and x[3]==0), Pi)
+        O = set(O)
+    else:
+        map(lambda x: x.set_immutable(), hyperoval)
+        O = set(hyperoval)
+
+    if check_hyperoval and (not hyperoval is None):

I read:

if A:
   ...
else:
   ...
if (not A):
   ...

Could you change it into:

done


New commits:

b73b175replace GQ by more appropriate things, and remove extra condition in if

comment:27 in reply to: ↑ 26 ; follow-up: Changed 6 years ago by ncohen

While GQ is as acceptable abbreviation as LP, and LP is used a lot in Sage code and docs, I realise that I should have been more careful there, sorry...

Update the LP doc to replace it by Linear Programming if you think that it is necessary. I've been studying graph theory for the last 7 years or so and I wouldn't recognize GQ if I was told that "This graph is a GQ".

Can't say the same for "This problem has a LP formulation".

Update those functions. It costs you nothing, and it will help people who look for those graphs.

Nathann

comment:28 Changed 6 years ago by ncohen

*Especially* when the name of your constructor is the pretty obscure T2starGQGraph.

comment:29 Changed 6 years ago by ncohen

I don't mind doing it if you are tired by this ticket.

comment:30 in reply to: ↑ 27 ; follow-up: Changed 6 years ago by dimpase

Replying to ncohen:

While GQ is as acceptable abbreviation as LP, and LP is used a lot in Sage code and docs, I realise that I should have been more careful there, sorry...

Update the LP doc to replace it by Linear Programming if you think that it is necessary.

Why? I am totally happy with LP, and GQ, as well.

I've been studying graph theory for the last 7 years or so and I wouldn't recognize GQ if I was told that "This graph is a GQ".

If a user did not hear about generelised quadrangles then having is spelled out fully in the function name makes no difference for the user. If the user did hear about them then it's very likely that the abbreviated form was also used, and is thus meaningful.

No, sorry, I'm not going to name anything BlahBlahCollinearityGraphOfGeneralisedQuadrangleGraph.

comment:31 in reply to: ↑ 30 Changed 6 years ago by ncohen

I just posted to sage-devel to ask for the general policy. We'll do what they say.

Let us pray that they have some consistent opinion.

And please don't join the thread to explain why it makes no sense in this specific ticket.

Nathann

comment:32 Changed 6 years ago by git

  • Commit changed from b73b175cbcc8aa8a28a84cfb3466d058406e48c4 to 605b2dfc685a8eb0e3caf1163a0adad5c47b9f9a

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

605b2dftypo in a graph docstring

comment:33 Changed 6 years ago by dimpase

I can add a function graphs.GeneralizedQuadrangleGraph(s,t) which will produce an example for each set (s,t) of parameters for which existence is known, if it would help you with naming issue...

comment:34 follow-up: Changed 6 years ago by ncohen

Having this function is a good idea, but to me it's orthogonal to the naming issue. It seems that 90% of those who commented the sage-devel thread stand for the full name.

Nathann

Last edited 6 years ago by ncohen (previous) (diff)

comment:35 in reply to: ↑ 34 Changed 6 years ago by dimpase

Replying to ncohen:

Having this function is a good idea, but to me it's orthogonal to the naming issue. It seems that 90% of those who commented the sage-devel thread stand for the full name.

As I write this, these brave abbreviation fighters must be busily working on a large number of tickets removing all the abbreviations from Sage function names... Perhaps you should join them, it's by far more important than this ticket. Death to all abbreviation in Sage, Victory or Death!

comment:36 Changed 6 years ago by dimpase

  • Dependencies changed from #19136 to #19136, #19224

comment:37 Changed 6 years ago by git

  • Commit changed from 605b2dfc685a8eb0e3caf1163a0adad5c47b9f9a to 0780530a7a7457e13f0cdd1f6ff006782466f0cf

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

92a2a6ftrac #19224: swtich OA(k,n)+* strongly regular graphs
930647cMerge remote-tracking branch 'trac/u/ncohen/19224' into GQ
580e422trac #19224: Merged with 6.9.beta7
9fc78a4trac #19224: Review
5a0384ctrac #19224: Rework the doctests
9433564trac #19224: Additional doctests
07b8da2Merge remote-tracking branch 'trac/u/ncohen/19224' into GQ
a14435bMerge branch 'develop' of git://trac.sagemath.org/sage into GQ
0780530TL;DR: abbrvs now dead

comment:38 follow-up: Changed 6 years ago by dimpase

it's all now named according to what majority wants...

comment:39 in reply to: ↑ 38 Changed 6 years ago by ncohen

  • Status changed from needs_review to positive_review

it's all now named according to what majority wants...

Thank you. I hope that will help others as it would have helped me.

Nathann

comment:40 Changed 6 years ago by ncohen

And thank you for the graphs too, of course. We are below 100 SRGs left ;-)

comment:41 follow-up: Changed 6 years ago by vbraun

Doctest fails. Guys, which part of the failing patchbot report was unclear to you?

comment:42 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:43 in reply to: ↑ 41 Changed 6 years ago by ncohen

Doctest fails. Guys, which part of the failing patchbot report was unclear to you?

I don't have a clue how what is done here could have the slightest effect in simplicial_complex.pyx. And as you know, sometimes, patchbot output nonsense.

Nathann

comment:44 Changed 6 years ago by ncohen

Err.. Okay, it's related :-D

comment:45 Changed 6 years ago by ncohen

  • Branch changed from u/dimpase/GQ to public/19226
  • Commit changed from 0780530a7a7457e13f0cdd1f6ff006782466f0cf to 894330e1787253600523bea93f34ce793f25e05c
  • Status changed from needs_work to positive_review

New commits:

1c09853trac #19226: Merged with 6.9
894330etrac #19226: Broken doctest

comment:46 Changed 6 years ago by vbraun

  • Branch changed from public/19226 to 894330e1787253600523bea93f34ce793f25e05c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.