###### tags: `recog`, `GAP`
# AnSn recog unknown degree

## Overview
[paper unknown degree](https://arxiv.org/abs/1306.0767)

[paper known degree](https://www.researchgate.net/publication/228930940_A_black-box_group_algorithm_for_recognizing_finite_symmetric_and_alternating_groups_I)

[how to write recog methods](https://hackmd.io/UQHK8XZgSJyZrUMEzb_6eQ?view)

[Finding involutions with small support](https://www.researchgate.net/publication/281895853_Finding_involutions_with_small_support)

[Renaming Table](https://hackmd.io/TJflWtgcSFmSd2WHwneMtA)

## Current Profiling

gapdev -c 'ReadPackage("recog", "_dev/MatC3_2.g");'

So we try to find threeCycleCandidates very hard, namely 564 times, but never find one. We try out 94 involutions in this process. We try all K = 5 random conjugates per involution.

### Master

testing: /
/combined/ClassicalNaturalNaming.tst
    2703 ms (58 ms GC) and 174MB allocated for ClassicalNaturalNaming.tst
testing: //quick/GenericSnAnUnknownDegree.tst
      48 ms (3 ms GC) and 8.42MB allocated for GenericSnAnUnknownDegree.tst
testing: /quick/MatDiagonal.tst
    3054 ms (602 ms GC) and 479MB allocated for MatDiagonal.tst
testing: /quick/MatReducible.tst
     154 ms (3 ms GC) and 13.7MB allocated for MatReducible.tst
testing: /quick/MatSn.tst
     363 ms (28 ms GC) and 66.3MB allocated for MatSn.tst
testing: /quick/MatTrivial.tst
       5 ms (0 ms GC) and 473KB allocated for MatTrivial.tst
testing: /quick/Methods.tst
       0 ms (0 ms GC) and 30.3KB allocated for Methods.tst
testing: /quick/PermAllSubgroups.tst
     530 ms (98 ms GC) and 48.0MB allocated for PermAllSubgroups.tst
testing: /quick/PermCycle.tst
       3 ms (0 ms GC) and 214KB allocated for PermCycle.tst
testing: /quick/PermDirProd.tst
      17 ms (0 ms GC) and 2.40MB allocated for PermDirProd.tst
testing: /quick/PermThrowAwayFixedPoints.tst
       4 ms (0 ms GC) and 641KB allocated for PermThrowAwayFixedPoints.tst
testing: /quick/PermTrivial.tst
       2 ms (0 ms GC) and 175KB allocated for PermTrivial.tst
testing: /quick/ProjLowIndex.tst
     428 ms (20 ms GC) and 41.5MB allocated for ProjLowIndex.tst
testing: /quick/ProjLowIndex2.tst
    5970 ms (400 ms GC) and 516MB allocated for ProjLowIndex2.tst
testing: /quick/ProjNotAbsIrred.tst
     256 ms (13 ms GC) and 26.8MB allocated for ProjNotAbsIrred.tst
testing: /quick/ProjReducible.tst
     270 ms (16 ms GC) and 30.7MB allocated for ProjReducible.tst
testing: /quick/ProjStabChain.tst
    1513 ms (139 ms GC) and 103MB allocated for ProjStabChain.tst
testing: /quick/ProjSubfield.tst
     334 ms (22 ms GC) and 38.1MB allocated for ProjSubfield.tst
testing: /quick/ProjSubfield2.tst
     507 ms (108 ms GC) and 37.3MB allocated for ProjSubfield2.tst
testing: /quick/ProjSubfield3.tst
      71 ms (0 ms GC) and 4.83MB allocated for ProjSubfield3.tst
testing: /quick/ProjTensor.tst
     979 ms (35 ms GC) and 90.3MB allocated for ProjTensor.tst
testing: /quick/ProjTensorInduced.tst
     952 ms (33 ms GC) and 80.9MB allocated for ProjTensorInduced.tst
testing: /quick/ProjThreeLargeElOrders.tst
     850 ms (28 ms GC) and 46.8MB allocated for ProjThreeLargeElOrders.tst
testing: /quick/ProjTrivial.tst
       5 ms (0 ms GC) and 539KB allocated for ProjTrivial.tst
testing: /quick/RecogMethod.tst
       0 ms (0 ms GC) and 62.4KB allocated for RecogMethod.tst
testing: /combined/Sporadic.tst
     605 ms (306 ms GC) and 76.2MB allocated for Sporadic.tst
testing: /quick/bugfix.tst
     825 ms (133 ms GC) and 70.0MB allocated for bugfix.tst
testing: /quick/cgo1.tst
    1155 ms (19 ms GC) and 52.7MB allocated for cgo1.tst
testing: /quick/classical.tst
     980 ms (22 ms GC) and 56.8MB allocated for classical.tst
testing: /quick/mixed.tst
       1 ms (0 ms GC) and 59.4KB allocated for mixed.tst
testing: /quick/sl3.tst
      65 ms (5 ms GC) and 10.9MB allocated for sl3.tst
-----------------------------------
total     22649 ms (2091 ms GC) and 2.03GB allocated
              0 failures in 31 files

#I  No errors detected while testing

testing: /slow/C3C5.tst
    7272 ms (237 ms GC) and 396MB allocated for C3C5.tst
testing: /combined/ClassicalNaturalNaming.tst
   61434 ms (1304 ms GC) and 3.57GB allocated for ClassicalNaturalNaming.tst
testing: /slow/GenericSnAnUnknownDegree.tst
   82345 ms (12115 ms GC) and 7.27GB allocated for GenericSnAnUnknownDegree.tst
testing: /slow/MatAn.tst
   11404 ms (195 ms GC) and 704MB allocated for MatAn.tst
testing: /slow/MatC3.tst
     243 ms (10 ms GC) and 33.8MB allocated for MatC3.tst
testing: /slow/MatC3_2.tst
    8327 ms (818 ms GC) and 625MB allocated for MatC3_2.tst
testing: /slow/MatHSmax5.tst
    2761 ms (146 ms GC) and 416MB allocated for MatHSmax5.tst
testing: /slow/NonDeletedPermModuleRepOfSn.tst
    2956 ms (799 ms GC) and 119MB allocated for NonDeletedPermModuleRepOfSn.tst
testing: /slow/PermLargeBasePrimitive.tst
    3966 ms (1433 ms GC) and 2.50GB allocated for PermLargeBasePrimitive.tst
testing: /slow/ProjC6.tst
    6839 ms (267 ms GC) and 449MB allocated for ProjC6.tst
testing: /slow/ProjDet.tst
   15564 ms (322 ms GC) and 553MB allocated for ProjDet.tst
testing: /combined/Sporadic.tst
    5906 ms (2714 ms GC) and 1006MB allocated for Sporadic.tst
testing: /slow/basic.tst
    6840 ms (1859 ms GC) and 1.04GB allocated for basic.tst
testing: /slow/bugfix.tst
   63549 ms (7819 ms GC) and 7.38GB allocated for bugfix.tst
-----------------------------------
total    279406 ms (30038 ms GC) and 25.9GB allocated
              0 failures in 14 files

### SnAn

testing: /combined/ClassicalNaturalNaming.tst
    2575 ms (55 ms GC) and 174MB allocated for ClassicalNaturalNaming.tst
testing: /quick/GenericSnAnUnknownDegree.tst
    2335 ms (250 ms GC) and 436MB allocated for GenericSnAnUnknownDegree.tst
testing: /quick/GenericSnAnUnknownDegreeHelpers.tst
       3 ms (0 ms GC) and 410KB allocated for GenericSnAnUnknownDegreeHelpers.tst
testing: /quick/MatDiagonal.tst
    2517 ms (399 ms GC) and 438MB allocated for MatDiagonal.tst
testing: /quick/MatReducible.tst
     237 ms (11 ms GC) and 22.2MB allocated for MatReducible.tst
testing: /quick/MatSn.tst
     492 ms (31 ms GC) and 93.8MB allocated for MatSn.tst
testing: /quick/MatTrivial.tst
       7 ms (2 ms GC) and 481KB allocated for MatTrivial.tst
testing: /quick/Methods.tst
       0 ms (0 ms GC) and 30.3KB allocated for Methods.tst
testing: /quick/PermAllSubgroups.tst
     517 ms (99 ms GC) and 48.0MB allocated for PermAllSubgroups.tst
testing: /quick/PermCycle.tst
       3 ms (0 ms GC) and 216KB allocated for PermCycle.tst
testing: /quick/PermDirProd.tst
      16 ms (0 ms GC) and 2.34MB allocated for PermDirProd.tst
testing: /quick/PermThrowAwayFixedPoints.tst
       4 ms (0 ms GC) and 644KB allocated for PermThrowAwayFixedPoints.tst
testing: /quick/PermTrivial.tst
       2 ms (0 ms GC) and 174KB allocated for PermTrivial.tst
testing: /quick/ProjLowIndex.tst
     434 ms (18 ms GC) and 42.1MB allocated for ProjLowIndex.tst
testing: /quick/ProjLowIndex2.tst
    4114 ms (335 ms GC) and 336MB allocated for ProjLowIndex2.tst
testing: /quick/ProjNotAbsIrred.tst
     260 ms (14 ms GC) and 26.9MB allocated for ProjNotAbsIrred.tst
testing: /quick/ProjReducible.tst
     215 ms (8 ms GC) and 20.8MB allocated for ProjReducible.tst
testing: /quick/ProjStabChain.tst
    1634 ms (155 ms GC) and 111MB allocated for ProjStabChain.tst
testing: /quick/ProjSubfield.tst
     350 ms (13 ms GC) and 32.1MB allocated for ProjSubfield.tst
testing: /quick/ProjSubfield2.tst
     391 ms (12 ms GC) and 34.5MB allocated for ProjSubfield2.tst
testing: /quick/ProjSubfield3.tst
     106 ms (3 ms GC) and 6.52MB allocated for ProjSubfield3.tst
testing: /quick/ProjTensor.tst
    1334 ms (41 ms GC) and 104MB allocated for ProjTensor.tst
testing: /quick/ProjTensorInduced.tst
    1181 ms (131 ms GC) and 95.6MB allocated for ProjTensorInduced.tst
testing: /quick/ProjThreeLargeElOrders.tst
     786 ms (16 ms GC) and 46.5MB allocated for ProjThreeLargeElOrders.tst
testing: /quick/ProjTrivial.tst
       6 ms (0 ms GC) and 536KB allocated for ProjTrivial.tst
testing: /quick/RecogMethod.tst
       0 ms (0 ms GC) and 62.4KB allocated for RecogMethod.tst
testing: /combined/Sporadic.tst
     443 ms (209 ms GC) and 74.7MB allocated for Sporadic.tst
testing: /quick/bugfix.tst
     792 ms (122 ms GC) and 77.9MB allocated for bugfix.tst
testing: /quick/cgo1.tst
    1025 ms (23 ms GC) and 54.2MB allocated for cgo1.tst
testing: /quick/classical.tst
     824 ms (22 ms GC) and 56.8MB allocated for classical.tst
testing: /quick/mixed.tst
       1 ms (0 ms GC) and 59.4KB allocated for mixed.tst
testing: /quick/sl3.tst
     100 ms (4 ms GC) and 12.7MB allocated for sl3.tst
-----------------------------------
total     22704 ms (1973 ms GC) and 2.29GB allocated
              0 failures in 32 files

#I  No errors detected while testing

testing: /slow/C3C5.tst
    6003 ms (217 ms GC) and 403MB allocated for C3C5.tst
testing: /combined/ClassicalNaturalNaming.tst
   60118 ms (1366 ms GC) and 3.50GB allocated for ClassicalNaturalNaming.tst
testing: /slow/MatAn.tst
   18595 ms (401 ms GC) and 1.07GB allocated for MatAn.tst
testing: /slow/MatC3.tst
     281 ms (13 ms GC) and 28.2MB allocated for MatC3.tst
testing: /slow/MatC3_2.tst
   18392 ms (727 ms GC) and 1.30GB allocated for MatC3_2.tst
testing: /slow/MatHSmax5.tst
  187077 ms (31103 ms GC) and 172GB allocated for MatHSmax5.tst
testing: /slow/NonDeletedPermModuleRepOfSn.tst
     760 ms (54 ms GC) and 235MB allocated for NonDeletedPermModuleRepOfSn.tst
testing: /slow/PermLargeBasePrimitive.tst
    4574 ms (1827 ms GC) and 2.47GB allocated for PermLargeBasePrimitive.tst
testing: /slow/ProjC6.tst
    9205 ms (279 ms GC) and 502MB allocated for ProjC6.tst
testing: /slow/ProjDet.tst
   17284 ms (325 ms GC) and 556MB allocated for ProjDet.tst
testing: /combined/Sporadic.tst
    6173 ms (2632 ms GC) and 1018MB allocated for Sporadic.tst
testing: /slow/basic.tst
    7436 ms (1983 ms GC) and 1.05GB allocated for basic.tst
testing: /slow/bugfix.tst
   74818 ms (7629 ms GC) and 7.68GB allocated for bugfix.tst
-----------------------------------
total    410716 ms (48556 ms GC) and 191GB allocated
              0 failures in 13 files

#I  No errors detected while testing

## Current Strategy
We have to be careful what we do for small degrees. If we pass an A5, S5, A6, S6 into the "unknown degree" algorithm, then it will not recognize it. If the input acts on a space with a large dimension, then this can take forever.
On the other hand, if we would always first compute the permutation representation of the action on the natural module, this would also become expensive for large groups.

- We assume that our input group G is a projective irreducible matrix group.
- Deduce an upper bound N for the degree of An,Sn.
- Look at some orders and deduce a lower bound for the degree.
- If lower bound > upper bound, then we excluded An,Sn.
- If lower bound < 7, then terminate, since SnAnUnknownDegree cannot recognize A5,S5,A6,S6,Aut(A6).
- Otherwise, we continue.
- Monte-Carlo: Try to compute standard generators and degree n of largest An < G via SnAnUnknownDegree by Jambor et al.
- Try to compute an isomorphism from G to An or Sn.
- If n < 11, then use methods from Conder
- Otherwise, we have n >= 11 and use methods from SnAnKnownDegree

Modifications to Jambor et al:
- For each ThreeCycleCandidate `c` we check if `c^3 = 1` and we check for some random elements `r` if `c * c^r` has order 1, 2, 3 or 5.
- Use Conder's Thesis to compute images for degree `<= 10`

## TODO: misc
- If we do not detect a three-cycle candidate at all, we run in the loop for a loooong time. We should return `TemporaryFailure` if we do find three-cycle candidates for a long time.
- `ConstructSnAnIsomorphism`: after the detection/construction of standard generators of Sn we verify all elements again, instead of proceeding with the leftover elements. Is this necessary or can we just verify the remaining elements?
- Documentation
- RecogniseSnAn performs verification! How do we tell recog we verified the recognition?

## TODO: Non-constructive recognition

- Permgroups: Conder, Algorithm 1 IsAlternatingOrSymmetric(G, ε)

## TODO: Make a new Leaf Node in Natural Representation

Currently, we mark the $G \cong \{S_n,A_n\}$ node in arbitrary representation as a leaf node. The following structure would be nicer:

G
/phi\
/ \
/ \
- -
1 H

where $G$ is marked as an inner node, $\phi$ is the found isomorphism and H is the $\{S_n,A_n\}$ in natural representation marked as a leaf node.

## TODO: Improvement for Bolstering Elements

- Compare our implementation with Magma's version and [Martin Leuner's Version](https://github.com/gap-packages/recog/pull/42)
- First, assume it is Sn/An and try to find only a **few** bolstering elements in the beginning.
- We use Chernoff's Bound in the proof of the proportion to show that among $S$ random elements we can construct at least $C$ bolstering elements in our procedure. It seems, that we can terminate more quickly, if one considers that these elements should be found (more or less) evenly distributed. Hence if one does not find any element after say $3 \cdot \frac{S}{C}$ iterations, we should be able to say that it is unlikely that we will find $C$ bolstering elements in the remaining iterations.
(**Idea:** update the probability of success with Chernoff's Bound every $N$-th iteration.)
- Profile how many iterations are needed to find these bolstering elements if we have an actual three-cycle c. (**Tightness** of bound $S$)

gap> SetInfoLevel(InfoRecog, 0);;
gap> gens := GeneratorsOfGroup;;
gap> l := gens(SymmetricGroup(11));;
gap> ll := List(l,x->PermutationMat(x,11)) * Z(5)^0;;
gap> m := GModuleByMats(ll,GF(5));;
gap> s5 := List(ll,x->KroneckerProduct(x,x));;
gap> m := GModuleByMats(s5,GF(5));;
gap> c := MTX.CompositionFactors(m);;
gap> i := Position(List(c,a->a.dimension), 43);;
gap> g := Group(c[i].generators);;
gap> ri := RecognizeGroup(g);; time;

gap> AddMethod(FindHomDbPerm, FindHomMethodsGeneric.SnAnUnknownDegree, 58);;
gap> AddMethod(FindHomDbMatrix, FindHomMethodsGeneric.SnAnUnknownDegree, 1070);;
gap> AddMethod(FindHomDbProjective, FindHomMethodsGeneric.SnAnUnknownDegree, 1220);;

gap> ri := RecognizeGroup(g);; time;

## TODO: Performance
Comparisons:
- Compare unknown degree implementation with known degree implementation, if the latter is a lot faster, maybe use try that first?
- Compare with Magma implementation. Are there any tricks we can use to improve performance?

Write down what we understood about the performance of the algorithm
- be careful with small classical groups!
- use it when we are in the case "quasisimple or classical"
- if our dimension and field are not too small we almost always get NeverApplicable (because our bound N will be dim+2 or so)
- TODO: is the field F_2 a problem? Maybe we get too small orders to rule out An and Sn
- `N` has a huge impact on the performance. How many `ThreeCycleCandidates` we compute depends on `N` by `O(N Log(N)^2)` (which is almost as big as `N^2` for `N` <= 100)
- `G := Sp(4,2); ri := EmptyRecognitionInfoRecord(rec(), G, false); RECOG.RecogniseSnAn(ri, 1/2, 8);` takes 30 _seconds_ on my machine. The reasons might be, that `G` only has small orders and that `N = 8` is way too big. The SLP code takes about 50% of the time. So with efficient SLPs this would still be way too slow
- eps seems to have almost no impact on the performance
- setting it smaller than 1/100 actually makes recognition slower
- it only influences how long we try until we return TemporaryFailure, which in our use case almost never happens anyways

Test how slow exiting via TemporaryFailure is by setting the bound N to a huge value

- what is faster: LargeBasePrimitive or SnAnUnknownDegree
- verify that Giant is quicker than us
- verify that we don't take too long

Do Profiling!

## Errors
- veryslow/ClassicalNatural.tst

    # Expected output:
    Stamp: ClassicalNatural
    # But found:
    Stamp: SnAnUnknownDegree

- slow/MatC3_2.tst

    Error, reached the pre-set memory limit)

## Comparison with master

Test that take longer than on master (all times in ms):
|folder|test|master|SnAnBranch|
|:--:|:--:|---:|---:|
|quick|ProjLowIndex2.tst|4 238|14 628|
|slow|C3C5.tst|5 931|11 602|
|slow|MatC3_2.tst|7 085|175 936|
|slow|MatHSmax5.tst|2 540|5 582|
|slow|NonDeletedPermModuleRepOfSn.tst|2 093|12 075|
|slow|ProjC6.tst|5 489|13 581|
|slow|ProjDet.tst|13 317|44 214|
|veryslow|MatC6.tst|23 934|1 447 542|
|veryslow|MatrixFiniteDeletedPermutationModule.tst|142 975|282 337|

Measurements in GAP:

Test("tst/working/quick/ProjLowIndex2.tst");
time;
Test("tst/working/slow/C3C5.tst");
time;
Test("tst/working/slow/MatC3_2.tst");
time;
Test("tst/working/slow/MatHSmax5.tst");
time;
Test("tst/working/slow/NonDeletedPermModuleRepOfSn.tst");
time;
Test("tst/working/slow/ProjC6.tst");
time;
Test("tst/working/slow/ProjDet.tst");
time;
Test("tst/working/veryslow/MatC6.tst");
time;
Test("tst/working/veryslow/MatrixFiniteDeletedPermutationModule.tst");
time;

## TODO: Known Degree
- issue & broken tests: RecogniseSnAnKnownDegree does not work for n <= 10 for A_n, S_n
- working tests for RecogniseSnAnKnownDegree via RECOG.TestGroup
- Add wrapper around RecogniseSnAn, so it could be used as a leaf method in recog at a later point.
- The input would be `(ri, G)`, where `ri` is a recognition record and `G` a group.
- The record `ri` should contain an entry `degree` or something similar, otherwise the method would return `NotEnoughInformation`. Suggestion:
- create recog record with `ri := EmptyRecognitionInfoRecord(rec(degree := 10),G,projective);`,
- test the entry with `IsBound(ri!.degree);`
- get entry with `ri!.degree`

## TODO: paper
- paper about implementation
e.g.
[https://msp.org/jsag/about/journal/about.html](Journal of Software for Algebra and Geometry)

## TODO: general recog work
- issue: prime sieve gap library function
max: I guess there really should be a GAP function like Primes(min,max) which gives you all primes in that range... or perhaps just AllPrimes(maxN) or so is enough. And that could check if N is small and then just return a subset of Primes, or else run a sieve. Or so
code: see `gap/sieve.g`
- Recog: isone(ri) and ri!.isone are both used
- UnderlyingElement does not work on pc group elements with memory.

    DihedralGroup(IsPcGroup, 10);
    ri := EmptyRecognitionInfoRecord(rec(), G, false);
    a := RandomElm( ri, "simplesocle", true )!.el;
    b := RandomElm( ri, "simplesocle", true )!.el;

- discuss with Max if `Success`, `NeverApplicable` and `TemporaryFailure` should be turned internally into a something else for example a string like `NotEnoughInformation`
- RECOG.RecognizeAlternating is broken? assuming the group is iso to an alternating, RECOG.RecognizeAlternating uses `ordersseen` to determine the degree. if the degree is wrong though, `RecogniseSnAn` will never succeed.
- add a general issue to detect performance regressions

## Proofs: Derek's GuessAltsymDegree

Proportions:
- proportion of `k`-cycles in `S_n` is $\frac{1}{k \cdot (n-k)!}$
- proportion of product of disjoint `k`-cycles and `n-k`-cycles in `S_n` is $\frac{1}{n-k} \cdot \frac{1}{k}$

**Claim 1**: `G = A_n`.
If `n` odd, then we should arrive at `mindege + 2 <= mindego`.
If `n` even, then we should arrive at `mindege + 1 <= mindego`.

**Proof, sketch:**

`n` even: find `n-1`-cycle. Thus maybe `mindego = n-1`.

`n` odd: `n`-cycles yield `mindego = n`. Thus maybe `mindego = n`.

Let `g in G` with even order. Then `g` has at least two cycles of even length. When computing `mindegforg` all cycles of even length except for the longest one are ignored. Thus `mindege <= n-2`.

**Claim 2:** `G = S_n`. Then we should arrive at `mindege = mindego`.

**Proof, sketch:**

If `n` even: find `n`-cycle. Thus maybe `mindege = n`. For some odd $3<=k<=n-3, k \neq n/2$, find disjoint product of `n-k`-cycle and `k`-cycle. Thus maybe `mindego = n`.

If `n` odd: find `n`-cycle. Thus maybe `mindego = n`. For some even `2<=k<=n-2`, find disjoint product of `n-k`-cycle and `k`-cycle. Thus maybe `mindege = n`.

## Proofs : Bolstering Elements

**Chernoff's Bound.**
Let $\mathfrak{X}_1, \mathfrak{X}_2, \dots$ be a sequence of not necessarily independent $\{0,1\}$-valued random variables
such that for all $0 < i \in \mathbb{N}$ and for all $(x_1, \dots, x_{i-1}) \in \{0,1\}^{i-1}$
we have $$\operatorname{Prob}\left(\mathfrak{X}_i = 1 \mid \mathfrak{X}_1 = x_1, \dots, \mathfrak{X}_{i-1} = x_{i-1}\right) \geq p.$$
Then, for all integers $S$ and $0 < \delta < 1$,
$$ \operatorname{Prob}\left(\sum_{i = 1}^S\mathfrak{X}_i \leq (1 - \delta) p \ell\right) \leq e^{-\delta^2 p S / 2}.$$

**Lemma 5.11.**
Let $7 \leq n \in \mathbb{N}$, $G \in \{S_n, A_n\}$, $c \in G$ be a $3$-cycle
and $p(n)$ be the proportion of pre-bolstering elements in $G$. Then we have
$$p(n) \geq \frac{2}{5n}.$$

**Proposition 5.12.**
Let $7 \leq n \in \mathbb{N}$, $G \in \{S_n, A_n\}$, $c \in G$ be a $3$-cycle, $0 < \varepsilon < 1$ and $\frac{1}{2} <\alpha \leq \frac{4}{5}$. Let $S = \left\lceil 5 n \operatorname{max}\left(\frac{25}{18}\left\lceil\frac{1}{2}\log_{\alpha}\varepsilon\right\rceil, \left(\frac{5}{4}\right)^4 \log \varepsilon^{-1}\right)\right\rceil$.
The probability that among $S$ random elements of $G$ at least $\left\lceil\frac{1}{2}\log_{\alpha}\varepsilon\right\rceil$ are pre-bolstering with respect to $c$ is at least $1 - \varepsilon$.

**Proof**
We use Chernoff's Bound for $\delta = \frac{16}{25}$. Let $r_1, \dots, r_S \in G$ be uniformly distributed independent random elements.
For $1 \leq i \leq S$ denote by $\mathfrak{X}_i$ a $\{0, 1\}$-valued random variable such that $\mathfrak{X}_i = 1$ if and only if $r_i$ is pre-bolstering. We need to show
$$\operatorname{Prob}\left(\sum_{i = 1}^S \mathfrak{X}_i < \left\lceil\frac{1}{2}\log_{\alpha}\varepsilon\right\rceil\right) \overset{!}{\leq} \varepsilon.$$
We have
$$
(1 - \delta) \cdot p(n) \cdot S
\geq \left(1 - \frac{16}{25}\right) \cdot \frac{2}{5n} \cdot 5n\frac{25}{18}\left\lceil\frac{1}{2}\log_{\alpha}\varepsilon\right\rceil
= \left\lceil\frac{1}{2}\log_{\alpha}\varepsilon\right\rceil
$$
and
$$
e^{-\delta^2 \cdot p \cdot S / 2}
\leq e^{-\left(\frac{16}{25}\right)^2 \cdot \frac{2}{5n} \cdot 5n\left(\frac{5}{4}\right)^4 \log \varepsilon^{-1} / 2}
= e^{-\log \varepsilon^{-1}} = \varepsilon
$$
Hence Chernoff's Bound yields the result.
(**TODO**: Why are the bounds for $\alpha$ important?)

**Lemma 4.7.**
`BolsteringElements` finds at least $R$ bolstering elements in $S$ random element selections, where
$S = 7N\left\lceil\frac{7}{4}\log\varepsilon^{-1}\right\rceil$ and
$R = \left\lceil\frac{7}{4}\log\varepsilon^{-1}\right\rceil$

**Proof**
We can use Propostion 5.12. with $\alpha = \frac{3}{4}$,
since
$$
\left\lceil\frac{1}{2}\log_{\alpha}\varepsilon\right\rceil
= \left\lceil- \frac{1}{\log(\frac{16}{9})} \cdot \log\varepsilon\right\rceil
\leq \left\lceil\frac{7}{4}\log\varepsilon^{-1}\right\rceil
= R,
$$
(**TODO**: Isn't this the wrong direction, since we need to find more than $R$ elements, but can only say something about finding at least $\left\lceil\frac{1}{2}\log_{\alpha}\varepsilon\right\rceil$ elements?)
$$
S
\geq 7N\frac{7}{4}\log\varepsilon^{-1}
\geq 5N\left(\frac{5}{4}\right)^4\log\varepsilon^{-1}
$$
and
$$
S = 7N \cdot R \geq 5N \frac{25}{18} \left\lceil\frac{1}{2}\log_{\alpha}\varepsilon\right\rceil.
$$

## Conder's Thesis (Implementation is finished)
We want to make this publicly available. Should we upload this to some professor's website, e.g. Max's?

How to adjust `ConstructSnAnIsomorphism` to integrate Conder's Thesis. The following is taken from Conder's Thesis p.66. We restructured it a bit and for each algorithm added in parantheses first the name used by Conder and then the name(s) of the corresponding gap function(s):

How to extend Algorithm 15 (ConstructiveRecognition / ConstructSnAnIsomorphism + as first step compute standard generators) such that it works for degrees between 5 and 10:
- only compute the initial 3 elements of <s, t> (that is E[1..3] = PreImages of [(1,2,3), (1,2,4), (1,2,5)]).
- remove the call to Algorithm 6 (DomainCover / ConstructXiAn, ConstructXiSn)
- replace calls to Algorithm 9 (ElementToPermutation / FindImageAn and FindImageSn) with calls to Algorithm 10 (ElementToSmallDegreePermutation / FindImageSnSmallDegree).
- Algorithm 10 uses Algorithm 7 (ConjugateMap / FindAnElementMappingIToJ)

What we need to put this into recog:
- Group/GrpFin/SimpleRecog/isaltorsym.m:
- ElementToSmallDegreePermutation
- local variables:
- E, a list of elements,
computed on line 650
- ConjugateMap
- local variables:
- t, s

# The Power is the same as in Conder's Thesis,
# since taking a three cycle Ei to the power of 2 is 
# the same as taking its inverse.
E1 := t;
E2 := (E1^s)^(2*(n mod 2) - 1);
E3 := (E2^s)^(2*(n mod 2) - 1);

## Old Profiling

- compare our implementation with jambor's implementation in magma

n := 20;;
eps := 1/100;;
nrSamples := 100;;

G := SymmetricGroup(n);;
nrSuccess := 0;;
for i in [1..nrSamples] do
    ri:= EmptyRecognitionInfoRecord(rec(), G, false);
    if not RECOG.RecogniseSnAn(ri, eps, n) in [TemporaryFailure, NeverApplicable] then
        nrSuccess := nrSuccess + 1;
    fi;
    Print(i,"\n");
od;
time;
nrSuccess;

**Results: Friedrich's Laptop, each test with new GAP session**
- `eps = 1/100, n = 100, nrSamples=50 -> time = 129123, nrSuccess = 50`
- `eps = 1/100, n = 20, nrSamples=100 -> time = 37629, nrSuccess = 100`
- `eps = 1/100, n = 11, nrSamples=100 -> time = 14305, nrSuccess = 100`
- `eps = 1/10, n = 100, nrSamples=50 -> time = 126833, nrSuccess = 50`
- `eps = 1/10, n = 20, nrSamples=100 -> time = 44283, nrSuccess = 100`
- `eps = 1/10, n = 11, nrSamples=100 -> time = 14569, nrSuccess = 100`

n := 5;;
eps := 1/100;;
q := 5;;
nrSamples := 10;;

G := SU(n, q);;
nrNeverApplicable := 0;;
for i in [1..nrSamples] do
    ri:= EmptyRecognitionInfoRecord(rec(), G, true);
    if RECOG.RecogniseSnAn(ri, eps, 1000) = NeverApplicable then
        nrNeverApplicable := nrNeverApplicable + 1;
    fi;
    Print(i,"\n");
od;
time;
nrNeverApplicable;

- For classical groups, it seems that we terminate quickly with `NeverApplicable`.

## Old Code Snippets

gapdev -c 'Test("tst/working/quick/GenericSnAnUnknownDegree.tst");'

# Expand a permutation group G to a diagonal group with m+1 components
G := SymmetricGroup(10);
d := NrMovedPoints(G);
m := 5;
T := List([1..m], j -> Product([1..d], i -> CycleFromList([i, i + d * j])));
T := Concatenation([()], T);
H := Group(List(GeneratorsOfGroup(G), g -> Product([1..m+1], j-> g ^ T[j])));
RECOG.TestGroup(H, false, Size(G), rec());

gap> ri:= EmptyRecognitionInfoRecord(rec(), SymmetricGroup(11), false);;
gap> FindHomMethodsGeneric.SnAnUnknownDegree(ri);;
gap> x := PseudoRandom(Grp(ri));;
gap> slp := SLPforElement(ri, x);;
gap> x = ResultOfStraightLineProgram(slp, NiceGens(ri));

gap> LoadPackage("profiling");;
gap> MyProfileFunctionCall := function(func, args)
        local filename, result, profile;
        filename := UserHomeExpand("~/.gap/profiles/profile.gz");
        ProfileLineByLine(filename);
        result := CallFuncList(func, args);
        UnprofileLineByLine();
        profile := ReadLineByLineProfile(filename);
        OutputAnnotatedCodeCoverageFiles(
            profile,
            UserHomeExpand("~/.gap/profiles/")
        );
    end;;
gap> n := 11;;
gap> sets := Combinations([1 .. n], 2);;
gap> G := Action(SymmetricGroup(n), sets, OnSets);;
gap> ri := EmptyRecognitionInfoRecord(rec(), G, false);;
gap> MyProfileFunctionCall(FindHomMethodsGeneric.SnAnUnknownDegree, [ri, ri!.Grp]);

This computation is extremely slow:

gap> LoadPackage("recog");;
gap> LoadPackage("profiling");;
gap> MyProfileFunctionCall := function(func, args)
        local filename, result, profile;
        filename := UserHomeExpand("~/.gap/profiles/profile.gz");
        ProfileLineByLine(filename);
        result := CallFuncList(func, args);
        UnprofileLineByLine();
        profile := ReadLineByLineProfile(filename);
        OutputAnnotatedCodeCoverageFiles(
            profile,
            UserHomeExpand("~/.gap/profiles/")
        );
    end;;
gap> G := SL(3,2);;
gap> ri := RecogNode(G, true);;
gap> MyProfileFunctionCall(FindHomMethodsGeneric.SnAnUnknownDegree, [ri, ri!.Grp]);