Opened 5 years ago

Closed 5 years ago

# HigmanSims design and graph related to it and to Witt designs

Reported by: Owned by: ncohen major sage-6.9 graph theory dimpase Nathann Cohen Dima Pasechnik N/A a380d6d (Commits) a380d6d88a032e941468a26200b62cb19555176a #19133

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.

### comment:1 Changed 5 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

New commits:

 ​302e6bc `trac #19133: Three Witt-based strongly regular graphs` ​6c0c890 `trac #19133: Merged with 6.9.beta5` ​3bc31a1 `trac #19133: Broken doctests` ​4bef485 `trac #19184: HigmanSims design`

### comment:2 follow-up: ↓ 7 Changed 5 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 5 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 5 years ago by git

• 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 git

• 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 git

• Commit changed from 0622a47fe46ba2e46117788f79850f997b8f5bd9 to 848a9724b6565639b2dd182f8468782150105bdf

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

 ​735afae `trac #19184: Merged with 6.9.beta6` ​848a972 `trac #19184: the SRG at last !`

### comment:7 in reply to: ↑ 2 Changed 5 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 5 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 5 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: ↓ 11 Changed 5 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 5 years ago by dimpase

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: ↓ 13 Changed 5 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: ↓ 14 Changed 5 years ago by dimpase

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 5 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: ↓ 16 Changed 5 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,q2) has a polarity with absolute points forming a unital.

Version 0, edited 5 years ago by dimpase (next)

### comment:16 in reply to: ↑ 15 ; follow-up: ↓ 17 Changed 5 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 5 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?

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 5 years ago by dimpase (previous) (diff)

### comment:18 Changed 5 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 5 years ago by dimpase

yes, it certainly does need `gap_packages`.

### comment:20 Changed 5 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: ↓ 24 Changed 5 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 5 years ago by git

• 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 ncohen

• Status changed from needs_info to needs_review

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

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 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: ↓ 27 Changed 5 years ago by ncohen

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

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

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 git

• 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 remote-tracking 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 git

• 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 git

• 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 git

• 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 dimpase

• Description modified (diff)

### comment:33 Changed 5 years ago by git

• 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 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 5 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:

 ​006fa91 `trac #19184: HigmanSims design` ​031346e `trac #19184: SRG on 105 vertices for L(3,4)`

### comment:36 Changed 5 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 5 years ago by ncohen (previous) (diff)

### comment:37 Changed 5 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:

 ​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 follow-up: ↓ 39 Changed 5 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: ↓ 41 Changed 5 years ago by 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 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 5 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 5 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:

 ​006fa91 `trac #19184: HigmanSims design` ​a380d6d `trac #19184: SRG on 105 vertices for L(3,4)`

### comment:43 Changed 5 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 5 years ago by ncohen

• Status changed from needs_review to positive_review

### comment:45 Changed 5 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 5 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.