Opened 5 years ago
Closed 5 years ago
#19184 closed enhancement (fixed)
HigmanSims design and graph related to it and to Witt designs
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  graph theory  Keywords:  
Cc:  dimpase  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  a380d6d (Commits)  Commit:  a380d6d88a032e941468a26200b62cb19555176a 
Dependencies:  #19133  Stopgaps: 
Description (last modified by )
This ticket implements a construction of the HigmanSims design (from a Witt design), from which we obtain an (176,49,12,14)SRG. As well, it implements an (105, 32, 4, 12)SRG related to PG(2,4); which is a Witt design, too.
Change History (46)
comment:1 Changed 5 years ago by
 Branch set to public/19184
 Commit set to 4bef48511f3612777591089530dbcb274886321b
comment:2 followup: ↓ 7 Changed 5 years ago by
A polarity of a symmetric design is simply an automorphism p of order 2 of the incidence graph, which maps points to blocks. A point P is called absolute if P lies in the block p(P). Once you know p with all points absolute, you can reorder points and blocks in the way that the incidence matrix has all 1s on the diagonal, and this is essentially the adj.mat. of the graph you are after.
Now, how does one go about finding polarites? Construct the incidence graph, compute its automorphism group a, find representatives of the conjugacy classes of a, select these which have representatives of order 2, mapping points to blocks. In this case there will be just two such class representatives, so you need to pick one, p, with all points absolute.
Let me know if you get stuck...
comment:3 Changed 5 years ago by
by the way:
File "src/sage/combinat/designs/database.py", line 4454, in sage.combinat.designs.database.HigmanSimsDesign Failed example: H = designs.HigmanSimsDesign(); H Expected nothing Got: Incidence structure with 176 points and 176 blocks **********************************************************************
comment:4 Changed 5 years ago by
 Commit changed from 4bef48511f3612777591089530dbcb274886321b to 3a6f2a39c29bd6cb2b0b1248d12f05929b199566
Branch pushed to git repo; I updated commit sha1. New commits:
3a6f2a3  trac #19184: Bugfix and PermutationGroup.relative_action

comment:5 Changed 5 years ago by
 Commit changed from 3a6f2a39c29bd6cb2b0b1248d12f05929b199566 to 0622a47fe46ba2e46117788f79850f997b8f5bd9
Branch pushed to git repo; I updated commit sha1. New commits:
0622a47  trac #19184: Labelled incidence graph

comment:6 Changed 5 years ago by
 Commit changed from 0622a47fe46ba2e46117788f79850f997b8f5bd9 to 848a9724b6565639b2dd182f8468782150105bdf
comment:7 in reply to: ↑ 2 Changed 5 years ago by
 Status changed from new to needs_review
Hellooooo Dima,
Thank you for this explanation. I pushed a last commit that lets us build the graph (slowly). The branch contains a method that I thought I would need: PermutationGroup.relative_action
. Turns out that I do not use it, though I think it is a nice thing to have. I leave it there thinking that it does not complicate the review much, but I will move it to another ticket if you ask.
One more down!
Nathann
comment:8 Changed 5 years ago by
How about hardcoding the polarity you compute. Won't it be faster? (keep the code to compute it though...)
comment:9 Changed 5 years ago by
Hmmmmm... I don't have much control on the output of HigmanSimsDesign
which uses the output of WittDesign
. I'm afraid it could become machinedependent :/
comment:10 followup: ↓ 11 Changed 5 years ago by
more explicitly: I am not sure that HigmanSimsDesign
is *always* the same, i.e. that its labelling does not change according to the platform.
comment:11 in reply to: ↑ 10 Changed 5 years ago by
Replying to ncohen:
more explicitly: I am not sure that
HigmanSimsDesign
is *always* the same, i.e. that its labelling does not change according to the platform.
well, I think it's platformindependent: have a look at
$SAGEROOT/local/gap/latest/pkg/design/lib/blockdesign.g
you'll see in WittDesign
M24:=Group([ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23), (3,17,10,7,9)(4,13,14,19,5)(8,18,11,12,23)(15,20,22,21,16), (1,24)(2,23)(3,12)(4,16)(5,18)(6,10)(7,20)(8,14)(9,21)(11,17)(13,22) (15,19) ]); W24:=BlockDesign(24,[[1,2,3,4,5,8,11,13]],M24); W24.autGroup:=M24; Unbind(W24.autSubgroup); W24.allTDesignLambdas:=Immutable(TDesignLambdas(5,24,8,1)); W:=W24; for i in Reversed([n+1..24]) do W:=DerivedBlockDesign(W,i); od;
it hardcodes the group and a block of the "big" Witt design S(5,8,24).
comment:12 followup: ↓ 13 Changed 5 years ago by
Hmmmm... But it goes into an IncidenceStructure then, which relabels it a bit internally I believe. Honestly I don't like this much :/
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 5 years ago by
Replying to ncohen:
Hmmmm... But it goes into an IncidenceStructure then, which relabels it a bit internally I believe. Honestly I don't like this much
:/
Is IncidenceStructure platformdependent? I suppose it is not. (IMHO the Witt designs can be constructed by Sage directly just as well, but this is another story).
comment:14 in reply to: ↑ 13 Changed 5 years ago by
Is IncidenceStructure platformdependent? I suppose it is not.
It should not be at the moment, even though there is labelling going on. But enforcing that it will never be is something else.
comment:15 followup: ↓ 16 Changed 5 years ago by
How about making code to compute polarities in !SRG_176_49_12_14() generic, working for any symmetric design?
Namely, something like is_self_polar
method for symmetric IncidenceStructures
that can in addition return the representatives of possible polarities?
Some of polarities lead to new designs, e.g. any PG(2,q^2)
has a polarity with absolute points
forming a unital.
comment:16 in reply to: ↑ 15 ; followup: ↓ 17 Changed 5 years ago by
How about making code to compute polarities in !SRG_176_49_12_14() generic, working for any symmetric design? Namely, something like
is_self_polar
method for symmetric IncidenceStructures that can in addition return the representatives of possible polarities?
I do not know half of this terminology that you use ^^;
Nathann
comment:17 in reply to: ↑ 16 Changed 5 years ago by
Replying to ncohen:
How about making code to compute polarities in !SRG_176_49_12_14() generic, working for any symmetric design? Namely, something like
is_self_polar
method for symmetric IncidenceStructures that can in addition return the representatives of possible polarities?I do not know half of this terminology that you use
^^;
A 2design is called symmetric if it has as many points as blocks, and with the number of blocks on a point equals the block size (e.g. PG(2,q), and, more generally, finite projective planes, are symmetric 2designs).
The dual of a symmetric 2design is the design with points and blocks swapping the roles.
A symmetric 2design is called selfdual if it is isomorphic to its dual. A selfdual symmetric 2design is called selfpolar if it has a polarity.
OK, and for the good measure, a duality is an isomorphism between the design and its dual. Every polarity is a duality. Dualities can be computed in the same way as polarity (just drop order==2 requirement). So it would also be very natural to have is_self_dual
method, too.
comment:18 Changed 5 years ago by
 Status changed from needs_review to needs_info
Did you assumed something was installed
sage t long src/sage/combinat/designs/database.py ********************************************************************** File "src/sage/combinat/designs/database.py", line 4376, in sage.combinat.designs.database.HigmanSimsDesign Failed example: H = designs.HigmanSimsDesign(); H ... RuntimeError: Error loading Gap package design. You may want to install the gap_packages and/or database_gap SPKGs.
comment:19 Changed 5 years ago by
yes, it certainly does need gap_packages
.
comment:20 Changed 5 years ago by
actually, design
package is not needed, you can build what you need as follows directly:
sage: M24=groups.permutation.Mathieu(24) sage: o=M24.orbit((1,2,3,4,5,8,11,13),action="OnSets") sage: W=IncidenceStructure(o); W Incidence structure with 24 points and 759 blocks
comment:21 followup: ↓ 24 Changed 5 years ago by
Gniiiiiii... It is next to impossible to "guess" what comes from standard ga and what comes from another package _
comment:22 Changed 5 years ago by
 Commit changed from 848a9724b6565639b2dd182f8468782150105bdf to fbe7bb9dab658a0de26e8455c3a5d73b2a99b516
Branch pushed to git repo; I updated commit sha1. New commits:
fbe7bb9  trac #19184: Broken doctest

comment:23 Changed 5 years ago by
 Status changed from needs_info to needs_review
comment:24 in reply to: ↑ 21 Changed 5 years ago by
Replying to ncohen:
Gniiiiiii... It is next to impossible to "guess" what comes from standard ga and what comes from another package
_
no need to guess, just go read GAP source code...
comment:25 Changed 5 years ago by
the construction of the design is from
M. Smith, A combinatorial configuration associated with the Higman–Sims simple group, J. Algebra 41(1976),175–195 http://dx.doi.org/10.1016/00218693(76)901757
(free download, in fact) It's a better reference than the one you give.
comment:26 followup: ↓ 27 Changed 5 years ago by
Right, but do you know *where* it appears in this paper?
comment:27 in reply to: ↑ 26 Changed 5 years ago by
Replying to ncohen:
Right, but do you know *where* it appears in this paper?
oh, right. Here is a good reference that does have it:
page 80 in [Atlas] J.H. Conway et al. Atlas of finite groups : maximal subgroups and ordinary characters for simple groups. Oxford University Press, 1985 https://en.wikipedia.org/wiki/ATLAS_of_Finite_Groups
(the reference you provide at the moment is an explicit link to an obscure publication, it can vanish tomorrow...)
comment:28 Changed 5 years ago by
 Commit changed from fbe7bb9dab658a0de26e8455c3a5d73b2a99b516 to b01eb12e55f47412c3d0b9d28d7f6b01c80da0a3
Branch pushed to git repo; I updated commit sha1. New commits:
7cbfa8b  trac #19180: A (220,84,38,28)strongly regular graph

6ce1899  trac #19180: Speedup

f90d1ce  Merge remotetracking branch 'trac/public/19180' into hs

2ceb7ee  Merge branch 'public/19184' of git://trac.sagemath.org/sage into hs

b01eb12  cite [BvL84]

comment:29 Changed 5 years ago by
 Commit changed from b01eb12e55f47412c3d0b9d28d7f6b01c80da0a3 to a0eabd4de0bd036b28cc08cfdb472bbc6668108d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a0eabd4  cite [BvL84]

comment:30 Changed 5 years ago by
 Commit changed from a0eabd4de0bd036b28cc08cfdb472bbc6668108d to 590b3ca2f0af42ce82bb8fa65564a0f76b457acf
Branch pushed to git repo; I updated commit sha1. New commits:
590b3ca  no need to take complement

comment:31 Changed 5 years ago by
 Commit changed from 590b3ca2f0af42ce82bb8fa65564a0f76b457acf to c07f2bcf3fa044a586eff5c7c66b80d104f18b3a
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c07f2bc  no need to take complement

comment:32 Changed 5 years ago by
 Description modified (diff)
comment:33 Changed 5 years ago by
 Commit changed from c07f2bcf3fa044a586eff5c7c66b80d104f18b3a to 994aa337c2b831a4e38be970f4829f37a839dd87
Branch pushed to git repo; I updated commit sha1. New commits:
994aa33  SRG on 105 vertices for L(3,4)

comment:34 Changed 5 years ago by
 Description modified (diff)
 Summary changed from HigmanSims design to HigmanSims design and graph related to it and to Witt designs
Just thought it's a good ticket for this graph :)
comment:35 Changed 5 years ago by
 Commit changed from 994aa337c2b831a4e38be970f4829f37a839dd87 to 031346ed2a8fe0cfddf4280887b36cd18cd38589
comment:36 Changed 5 years ago by
Err... Dima, if you must change my branches without asking first then there is something you should know: as far as I am concerned, your branches as very unclean. And I try to keep mine at a certain level of hygiene.
Sooooooo unless it's because the reviewer asks you to change thing (after you pushed it), please only push *clean* stuff with a *clean* history. That means: the commits are properly labelled, and their name starts with the number of the ticket. That also means that no commit 'fixes' a bug that was introduced in the previous commit (if that happens while you develop, *squash* the two commits before pushing them).
I fixed it and pushed it.
Nathann
comment:37 Changed 5 years ago by
 Commit changed from 031346ed2a8fe0cfddf4280887b36cd18cd38589 to 8d615c25881eb21595d31fbf77b3d63f3fba8fd9
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
3a6f2a3  trac #19184: Bugfix and PermutationGroup.relative_action

0622a47  trac #19184: Labelled incidence graph

735afae  trac #19184: Merged with 6.9.beta6

848a972  trac #19184: the SRG at last !

fbe7bb9  trac #19184: Broken doctest

2ceb7ee  Merge branch 'public/19184' of git://trac.sagemath.org/sage into hs

a0eabd4  cite [BvL84]

c07f2bc  no need to take complement

994aa33  SRG on 105 vertices for L(3,4)

8d615c2  less crude code in SRG_176_49_12_14

comment:38 followup: ↓ 39 Changed 5 years ago by
oops, sorry, I messed up stuff again. I'll try to clean up.
comment:39 in reply to: ↑ 38 ; followup: ↓ 41 Changed 5 years ago by
Replying to dimpase:
oops, sorry, I messed up stuff again. I'll try to clean up.
hmm, did I really mess it up, or it's just a side effect of a forced push?
comment:40 Changed 5 years ago by
 Reviewers set to Dima Pasechnik
anyhow, I am happy with the content now; please review my changes, and feel free to set it to positive review then.
comment:41 in reply to: ↑ 39 Changed 5 years ago by
hmm, did I really mess it up, or it's just a side effect of a forced push?
You overwrote my modifications, and pushed your branch back. Incidentally, you also waste *my* time.
comment:42 Changed 5 years ago by
 Commit changed from 8d615c25881eb21595d31fbf77b3d63f3fba8fd9 to a380d6d88a032e941468a26200b62cb19555176a
comment:43 Changed 5 years ago by
Okay, good. Thank you for these changes, and the modifications you brought to the functions I wrote.
Now, Dima, it is time for you to learn how to use git, because you cannot continue using tools that you do not understand. You need to use 'tig', which is a commandline tool that displays the branch of a git tree: it is *very* helpful to learn git, and *very* helpful to work with Sage.
Then, you should learn how to use 'git rebase i', which lets you rename/merge commits before pushing them. That will make your branches much cleaner. Also, please remember to give a proper commit message <anytime>, but in particular for the 'merge' commits.
Good to go.
Nathann
comment:44 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:45 Changed 5 years ago by
Nathann, my apologies. I should not play with git f
late at night. Thanks for all the work you did here.
comment:46 Changed 5 years ago by
 Branch changed from public/19184 to a380d6d88a032e941468a26200b62cb19555176a
 Resolution set to fixed
 Status changed from positive_review to closed
Helloooo Dima !
I can build this design but I do not know how to build the graph from it. It is explained there [1] but I am afraid that I do not understand what those polarities are, and how to use them. Would it happen to make more sense for you ?
^^;
Nathann
[1] http://oai.cwi.nl/oai/asset/2586/2586A.pdf
New commits:
trac #19133: Three Wittbased strongly regular graphs
trac #19133: Merged with 6.9.beta5
trac #19133: Broken doctests
trac #19184: HigmanSims design