Opened 3 years ago

Closed 3 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: sage-6.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 dimpase)

This ticket implements a construction of the Higman-Sims 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 3 years ago by ncohen

  • Branch set to public/19184
  • Commit set to 4bef48511f3612777591089530dbcb274886321b

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:

302e6bctrac #19133: Three Witt-based strongly regular graphs
6c0c890trac #19133: Merged with 6.9.beta5
3bc31a1trac #19133: Broken doctests
4bef485trac #19184: HigmanSims design

comment:2 follow-up: Changed 3 years ago by dimpase

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 3 years ago by dimpase

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 3 years ago by git

  • Commit changed from 4bef48511f3612777591089530dbcb274886321b to 3a6f2a39c29bd6cb2b0b1248d12f05929b199566

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

3a6f2a3trac #19184: Bugfix and PermutationGroup.relative_action

comment:5 Changed 3 years ago by git

  • Commit changed from 3a6f2a39c29bd6cb2b0b1248d12f05929b199566 to 0622a47fe46ba2e46117788f79850f997b8f5bd9

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

0622a47trac #19184: Labelled incidence graph

comment:6 Changed 3 years ago by git

  • Commit changed from 0622a47fe46ba2e46117788f79850f997b8f5bd9 to 848a9724b6565639b2dd182f8468782150105bdf

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

735afaetrac #19184: Merged with 6.9.beta6
848a972trac #19184: the SRG at last !

comment:7 in reply to: ↑ 2 Changed 3 years ago by ncohen

  • 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 3 years ago by dimpase

How about hardcoding the polarity you compute. Won't it be faster? (keep the code to compute it though...)

comment:9 Changed 3 years ago by ncohen

Hmmmmm... I don't have much control on the output of HigmanSimsDesign which uses the output of WittDesign. I'm afraid it could become machine-dependent :-/

comment:10 follow-up: Changed 3 years ago by 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.

comment:11 in reply to: ↑ 10 Changed 3 years ago by dimpase

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 platform-independent: 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 follow-up: Changed 3 years ago by ncohen

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 ; follow-up: Changed 3 years ago by dimpase

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 platform-dependent? 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 3 years ago by ncohen

Is IncidenceStructure platform-dependent? 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 follow-up: Changed 3 years ago by dimpase

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.

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

comment:16 in reply to: ↑ 15 ; follow-up: Changed 3 years ago by 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 ^^;

Nathann

comment:17 in reply to: ↑ 16 Changed 3 years ago by dimpase

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 2-design 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 2-designs).

The dual of a symmetric 2-design is the design with points and blocks swapping the roles.

A symmetric 2-design is called self-dual if it is isomorphic to its dual. A self-dual symmetric 2-design is called self-polar 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.

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

comment:18 Changed 3 years ago by vdelecroix

  • 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 3 years ago by dimpase

yes, it certainly does need gap_packages.

comment:20 Changed 3 years ago by dimpase

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 follow-up: Changed 3 years ago by ncohen

Gniiiiiii... It is next to impossible to "guess" what comes from standard ga and what comes from another package -_-

comment:22 Changed 3 years ago by git

  • Commit changed from 848a9724b6565639b2dd182f8468782150105bdf to fbe7bb9dab658a0de26e8455c3a5d73b2a99b516

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

fbe7bb9trac #19184: Broken doctest

comment:23 Changed 3 years ago by ncohen

  • Status changed from needs_info to needs_review

comment:24 in reply to: ↑ 21 Changed 3 years ago by dimpase

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 3 years ago by dimpase

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/0021-8693(76)90175-7

(free download, in fact) It's a better reference than the one you give.

comment:26 follow-up: Changed 3 years ago by ncohen

Right, but do you know *where* it appears in this paper?

comment:27 in reply to: ↑ 26 Changed 3 years ago by dimpase

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 3 years ago by git

  • Commit changed from fbe7bb9dab658a0de26e8455c3a5d73b2a99b516 to b01eb12e55f47412c3d0b9d28d7f6b01c80da0a3

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

7cbfa8btrac #19180: A (220,84,38,28)-strongly regular graph
6ce1899trac #19180: Speedup
f90d1ceMerge remote-tracking branch 'trac/public/19180' into hs
2ceb7eeMerge branch 'public/19184' of git://trac.sagemath.org/sage into hs
b01eb12cite [BvL84]

comment:29 Changed 3 years ago by git

  • Commit changed from b01eb12e55f47412c3d0b9d28d7f6b01c80da0a3 to a0eabd4de0bd036b28cc08cfdb472bbc6668108d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

a0eabd4cite [BvL84]

comment:30 Changed 3 years ago by git

  • Commit changed from a0eabd4de0bd036b28cc08cfdb472bbc6668108d to 590b3ca2f0af42ce82bb8fa65564a0f76b457acf

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

590b3cano need to take complement

comment:31 Changed 3 years ago by git

  • Commit changed from 590b3ca2f0af42ce82bb8fa65564a0f76b457acf to c07f2bcf3fa044a586eff5c7c66b80d104f18b3a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c07f2bcno need to take complement

comment:32 Changed 3 years ago by dimpase

  • Description modified (diff)

comment:33 Changed 3 years ago by git

  • Commit changed from c07f2bcf3fa044a586eff5c7c66b80d104f18b3a to 994aa337c2b831a4e38be970f4829f37a839dd87

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

994aa33SRG on 105 vertices for L(3,4)

comment:34 Changed 3 years ago by dimpase

  • 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 3 years ago by git

  • Commit changed from 994aa337c2b831a4e38be970f4829f37a839dd87 to 031346ed2a8fe0cfddf4280887b36cd18cd38589

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

006fa91trac #19184: HigmanSims design
031346etrac #19184: SRG on 105 vertices for L(3,4)

comment:36 Changed 3 years ago by ncohen

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

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

comment:37 Changed 3 years ago by git

  • Commit changed from 031346ed2a8fe0cfddf4280887b36cd18cd38589 to 8d615c25881eb21595d31fbf77b3d63f3fba8fd9

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

3a6f2a3trac #19184: Bugfix and PermutationGroup.relative_action
0622a47trac #19184: Labelled incidence graph
735afaetrac #19184: Merged with 6.9.beta6
848a972trac #19184: the SRG at last !
fbe7bb9trac #19184: Broken doctest
2ceb7eeMerge branch 'public/19184' of git://trac.sagemath.org/sage into hs
a0eabd4cite [BvL84]
c07f2bcno need to take complement
994aa33SRG on 105 vertices for L(3,4)
8d615c2less crude code in SRG_176_49_12_14

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

oops, sorry, I messed up stuff again. I'll try to clean up.

comment:39 in reply to: ↑ 38 ; follow-up: Changed 3 years ago by dimpase

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 3 years ago by dimpase

  • 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 3 years ago by ncohen

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 3 years ago by git

  • Commit changed from 8d615c25881eb21595d31fbf77b3d63f3fba8fd9 to a380d6d88a032e941468a26200b62cb19555176a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

006fa91trac #19184: HigmanSims design
a380d6dtrac #19184: SRG on 105 vertices for L(3,4)

comment:43 Changed 3 years ago by ncohen

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 command-line 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 3 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:45 Changed 3 years ago by dimpase

Nathann, my apologies. I should not play with git -f late at night. Thanks for all the work you did here.

comment:46 Changed 3 years ago by vbraun

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