Opened 7 years ago
Closed 7 years ago
#19226 closed enhancement (fixed)
some (collinearity graphs of) GQ(q1,q+1)
Reported by:  Dima Pasechnik  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  graph theory  Keywords:  
Cc:  Nathann Cohen  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: 
Description
For SRG database, we need these. This ticket implements AS(q) (q odd prime power) and T_2*(O) constructions of GQ(q1,q+1).
Change History (46)
comment:1 Changed 7 years ago by
Branch:  → u/dimpase/GQ 

Cc:  Nathann Cohen added 
Commit:  → 1de29de8ab7afe7805a4a3d8bb62c77dc1e3b76f 
comment:2 Changed 7 years ago by
Dependencies:  → #19136 

comment:3 Changed 7 years ago by
Commit:  1de29de8ab7afe7805a4a3d8bb62c77dc1e3b76f → 28752a80c4c1778228c4aa7a06a3e5f372b6c951 

Branch pushed to git repo; I updated commit sha1. New commits:
28752a8  Merge branch 'develop' of git://trac.sagemath.org/sage into GQ

comment:4 Changed 7 years ago by
Commit:  28752a80c4c1778228c4aa7a06a3e5f372b6c951 → 4076a47f7b7ec9c4a6d7e161429e25b0bc5231a1 

Branch pushed to git repo; I updated commit sha1. New commits:
4076a47  added examples and tests for usersupplied hyperoval in T_2*(O), and small bug fixed

comment:5 Changed 7 years ago by
Status:  new → needs_review 

should't be hard to review, given the new beta.
comment:6 followup: 8 Changed 7 years ago by
Status:  needs_review → needs_work 

Hello Dima,
Here is a firstpass review.
coordinates
: why not a boolean? Its default value isNone
, 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 usuallyTrue
.
 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 ahyperoval
variable? Use that second name instead?!
Nathann
comment:7 Changed 7 years ago by
Commit:  4076a47f7b7ec9c4a6d7e161429e25b0bc5231a1 → d4cc95be16dcf1b402bea40ae73f83833487b8ce 

Branch pushed to git repo; I updated commit sha1. New commits:
d4cc95b  addressing referee's remarks

comment:8 Changed 7 years ago by
Replying to ncohen:
Here is a firstpass review.
coordinates
: why not a boolean? Its default value isNone
, 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 usuallyTrue
.
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 ahyperoval
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 followup: 11 Changed 7 years ago by
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 followup: 14 Changed 7 years ago by
Reviewers:  → 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 thatcheck_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 callis_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 ofpoint_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 followup: 12 Changed 7 years ago by
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...
comment:12 Changed 7 years ago by
so this is a massive rewrite, and not much fun...
Okay. Let's forget about it for the moment.
comment:13 Changed 7 years ago by
Commit:  d4cc95be16dcf1b402bea40ae73f83833487b8ce → 2a62ef16861fb421358f3d5f636cc9fc97e59011 

Branch pushed to git repo; I updated commit sha1. New commits:
2a62ef1  further doc fixes

comment:14 followup: 15 Changed 7 years ago by
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 thatcheck_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 callis_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 ofpoint_coordinates
?
would it make things less efficient?
comment:15 followup: 18 Changed 7 years ago by
Hello,
well, isn't it high time to realise that
graphs.BlahBLahGraph
is an abomination, for stuff ingraphs.*
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 factT_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 ofpoint_coordinates
?would it make things less efficient?
If you can measure the difference I owe you a beer.
Nathann
comment:16 Changed 7 years ago by
Commit:  2a62ef16861fb421358f3d5f636cc9fc97e59011 → 2b7736294074261e90e184ddd454b928833e160e 

Branch pushed to git repo; I updated commit sha1. New commits:
2b77362  changed the default of point_coordinates, added a doctest

comment:17 Changed 7 years ago by
Commit:  2b7736294074261e90e184ddd454b928833e160e → 5e0a6d77628c9637daf180a2e9b0dbdf0a869b4e 

Branch pushed to git repo; I updated commit sha1. New commits:
5e0a6d7  updated is_GQqmqp to make reviewer happier

comment:18 followup: 19 Changed 7 years ago by
Replying to ncohen:
well, isn't it high time to realise that
graphs.BlahBLahGraph
is an abomination, for stuff ingraphs.*
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 inGraph
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 factT_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 ofpoint_coordinates
?would it make things less efficient?
OK, changed.
New commits:
5e0a6d7  updated is_GQqmqp to make reviewer happier

comment:19 followup: 21 Changed 7 years ago by
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 7 years ago by
Commit:  5e0a6d77628c9637daf180a2e9b0dbdf0a869b4e → b5a2fcd90050e59021aef77f1a803aaeb65f4c55 

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

comment:21 Changed 7 years ago by
Authors:  → Dima Pasechnik 

Status:  needs_work → 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 followup: 26 Changed 7 years ago by
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 7 years ago by
Status:  needs_review → needs_work 

comment:24 Changed 7 years ago by
Commit:  b5a2fcd90050e59021aef77f1a803aaeb65f4c55 → b73b175cbcc8aa8a28a84cfb3466d058406e48c4 

Branch pushed to git repo; I updated commit sha1. New commits:
b73b175  replace GQ by more appropriate things, and remove extra condition in if

comment:25 Changed 7 years ago by
Despite what the commit message says, it does not replace GQ by more appropriate things.
Nathann
comment:26 followup: 27 Changed 7 years ago by
Status:  needs_work → 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:
b73b175  replace GQ by more appropriate things, and remove extra condition in if

comment:27 followup: 30 Changed 7 years ago by
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 7 years ago by
*Especially* when the name of your constructor is the pretty obscure T2starGQGraph
.
comment:30 followup: 31 Changed 7 years ago by
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 Changed 7 years ago by
I just posted to sagedevel 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 7 years ago by
Commit:  b73b175cbcc8aa8a28a84cfb3466d058406e48c4 → 605b2dfc685a8eb0e3caf1163a0adad5c47b9f9a 

Branch pushed to git repo; I updated commit sha1. New commits:
605b2df  typo in a graph docstring

comment:33 Changed 7 years ago by
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 followup: 35 Changed 7 years ago by
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 sagedevel thread stand for the full name.
Nathann
comment:35 Changed 7 years ago by
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 sagedevel 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 7 years ago by
Dependencies:  #19136 → #19136, #19224 

comment:37 Changed 7 years ago by
Commit:  605b2dfc685a8eb0e3caf1163a0adad5c47b9f9a → 0780530a7a7457e13f0cdd1f6ff006782466f0cf 

Branch pushed to git repo; I updated commit sha1. New commits:
92a2a6f  trac #19224: swtich OA(k,n)+* strongly regular graphs

930647c  Merge remotetracking branch 'trac/u/ncohen/19224' into GQ

580e422  trac #19224: Merged with 6.9.beta7

9fc78a4  trac #19224: Review

5a0384c  trac #19224: Rework the doctests

9433564  trac #19224: Additional doctests

07b8da2  Merge remotetracking branch 'trac/u/ncohen/19224' into GQ

a14435b  Merge branch 'develop' of git://trac.sagemath.org/sage into GQ

0780530  TL;DR: abbrvs now dead

comment:38 followup: 39 Changed 7 years ago by
it's all now named according to what majority wants...
comment:39 Changed 7 years ago by
Status:  needs_review → 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 7 years ago by
And thank you for the graphs too, of course. We are below 100 SRGs left ;)
comment:41 followup: 43 Changed 7 years ago by
Doctest fails. Guys, which part of the failing patchbot report was unclear to you?
comment:42 Changed 7 years ago by
Status:  positive_review → needs_work 

comment:43 Changed 7 years ago by
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:45 Changed 7 years ago by
Branch:  u/dimpase/GQ → public/19226 

Commit:  0780530a7a7457e13f0cdd1f6ff006782466f0cf → 894330e1787253600523bea93f34ce793f25e05c 
Status:  needs_work → positive_review 
comment:46 Changed 7 years ago by
Branch:  public/19226 → 894330e1787253600523bea93f34ce793f25e05c 

Resolution:  → fixed 
Status:  positive_review → closed 
the GQs basically done (few things to check still, but it's basically there)
Last 10 new commits:
Merge branch 'develop' of git://trac.sagemath.org/sage into NONU
implemented recognition of NU; a bug in recongition of NO^+(2n+1,3) to fix...
fix for a silly bug in is_NOodd, moar doctests
added SymplecticGraph to graphs.* and fixed a typo there, and a doctest
else if > elif, other things in NonisotropicOrthogonalPolarGraph
speedups by calling vector() once
remove forgotten prints
coordinates enabled for PG designs
GQ(q+1,q1) and GQ(q1,q+1) implemented and recognised in DB
removed explicit graphs that we can now build (thanks to this ticket and NONU)