Quelle  SnAnUnknownDegree.gi   Sprache: unbekannt

#############################################################################
##
##  This file is part of recog, a package for the GAP computer algebra system
##  which provides a collection of methods for the constructive recognition
##  of groups.
##
##  This files's authors include Friedrich Rober and Sergio Siccha.
##
##  Copyright of recog belongs to its developers whose names are too numerous
##  to list here. Please refer to the COPYRIGHT file for details.
##
##  SPDX-License-Identifier: GPL-3.0-or-later
##
##
##  This file provides code for recognising whether a permutation group
##  is isomorphic to an alternating or symmetric group. It implements
##  <Cite Key="JLNP13"/>.
##
#############################################################################
#
# eps : real number, the error bound
# N : integer, upper bound for the degree of G
#
# Returns a record of constants used in ThreeCyclesCanditatesIterator.
RECOG.ThreeCycleCandidatesConstants := function(eps, N)
    local M, p;
    # Constants
    M := 1;
    RECOG.CachePrimesUpTo(N);
    for p in RECOG.PrimesCache do
        if p = 2 then continue; fi;
        if p > N then break; fi;
        M := M * p ^ LogInt(N, p);
    od;
    return rec(
        M := M,
        B := Int(Ceil(13 * Log(Float(N)) * Log(3 / Float(eps)))),
        T := Int(Ceil(3 * Log(3 / Float(eps)))),
        C := Int(Ceil(Float(3 * N * ~.T / 5))),
        logInt2N := LogInt(N, 2)
    );
end;

# ri : recognition node with group G
# constants : a record with components M, B, T, C, and logInt2N
#
# The following algorithm constructs a set of possible 3-cycles. It is based
# on the simple observation that the product of two involutions t1, t2, which
# only move one common point, squares to a 3-cycle.
#
# Creates and returns a function, here called oneThreeCycleCandidate. The
# function oneThreeCycleCandidate returns one of the following:
# - a three cycle candidate, i.e. an element of G
# - TemporaryFailure, if we exhausted all attempts
# - NeverApplicable, if we found out that G can't be an Sn or An
#
# Lower Bounds need n >= 9.
RECOG.ThreeCycleCandidatesIterator := function(ri, constants)
    local
        # involution
        t,
        # integers, controlling the number of iterations
        M, B, T, C, logInt2N,
        # counters
        nrInvolutions, nrTriedConjugates, nrThreeCycleCandidates,
        # helper functions
        tryThreeCycleCandidate, oneThreeCycleCandidate;
    # Step 1: Initialization
    # The current involution t_i
    t := fail;

    M := constants.M;
    B := constants.B;
    T := constants.T;
    C := constants.C;
    logInt2N := constants.logInt2N;

    # Counters
    # Counts the constructed involutions t_i in steps 2 & 3.
    nrInvolutions := 0;
    # Counts the elements c in step 4 that we use to conjugate the current
    # involution t_i.  We initialize nrTriedConjugates to C such that "steps 2
    # & 3" in tryThreeCycleCandidate immediately construct an involution.
    nrTriedConjugates := C;
    # counts the size of the set Gamma_i in step 4 for the current involution
    # t_i
    nrThreeCycleCandidates := 0;

    # Helper functions
    # tryThreeCycleCandidate returns one of the following:
    # - a three cycle candidate, i.e. an element of G
    # - fail, if the random conjugate c from step 4 and t commute. Then we have
    #   to call tryThreeCycleCandidate again
    # - NeverApplicable, if G can not be an Sn or An
    tryThreeCycleCandidate := function()
        local
            # integer, loop variable
            a,
            # elements, in G
            r, tPower, tPowerOld, c;
        # Steps 2 & 3: New involution
        # Check if we either tried enough conjugates or constructed enough
        # three cycle candidates for the current involution t.
        # If this is the case, we need to construct the next involution
        if nrTriedConjugates >= C or nrThreeCycleCandidates >= T then
            r := RandomElm(ri, "SnAnUnknownDegree", true)!.el;
            tPower := r ^ M;
            # Invariant: tPower = (r ^ M) ^ (2 ^ a)
            # We make a small improvement to the version described in
            # <Cite Key="JLNP13"/>. The order of r ^ M is a 2-power.
            # It can be at most 2 ^ logInt2N. Thus, if we find an r such that
            # (r ^ M) ^ (2 ^ logInt2N) is non-trivial, then we can return
            # NeverApplicable.
            for a in [1 .. logInt2N] do
                tPowerOld := tPower;
                tPower := tPower ^ 2;
                if isone(ri)(tPower) then break; fi;
            od;
            if not isone(ri)(tPower) then
                return NeverApplicable;
            fi;
            t := tPowerOld;
            nrInvolutions := nrInvolutions + 1;
            nrTriedConjugates := 0;
            nrThreeCycleCandidates := 0;
        fi;
        # Steps 4 & 5: new three cycle candidate
        # Try to construct a three cycle candidate via a conjugate of t. See
        # the comment above this function.
        nrTriedConjugates := nrTriedConjugates + 1;
        c := t ^ RandomElm(ri, "SnAnUnknownDegree", true)!.el;
        if not isequal(ri)(t * c, c * t) then
            nrThreeCycleCandidates := nrThreeCycleCandidates + 1;
            return (t * c) ^ 2;
        else
            # we have to call tryThreeCycleCandidate again
            return fail;
        fi;
    end;
    # construct the iterator
    oneThreeCycleCandidate := function()
        local candidate;
        repeat
            if nrInvolutions >= B
                and (nrTriedConjugates >= C or nrThreeCycleCandidates >= T)
            then
                # With probability at least 1 - eps we constructed at least one
                # three cycle with this iterator.
                return fail;
            fi;
            candidate := tryThreeCycleCandidate();
            if candidate = NeverApplicable then
                return NeverApplicable;
            fi;
        until candidate <> fail;
        return candidate;
    end;
    return oneThreeCycleCandidate;
end;

# ri : recognition node with group G
# c : element of G,
#     should be a 3-cycle
# eps : real number, the error bound
# N : integer, upper bound for the degree of G
#
# Returns a list of elements of G.
#
# If the input is as assumed, then this function returns a list of bolstering
# elements with respect to c.
#
# Lower Bounds need n >= 9.
# Bolstering Elements are only defined for n >= 7.
RECOG.BolsteringElements := function(ri, cWithMem, eps, N)
    local result, R, S, nrPrebolsteringElms, i, c, rWithMem, r, cr, cr2;
    result := [];
    c := StripMemory(cWithMem);
    R := Int(Ceil(7 / 4 * Log(Float(eps ^ -1))));
    S := 7 * N * R;
    # find pre-bolstering elements
    for i in [0 .. S] do
        rWithMem := RandomElm(ri, "SnAnUnknownDegree", true)!.el;
        r := StripMemory(rWithMem);
        # test whether r is pre-bolstering
        cr := c ^ r;
        cr2 := cr ^ r;
        if not docommute(ri)(cr, c)
                and not isequal(ri)(cr2, c)
                and not isequal(ri)(cr2, c ^ 2)
                and docommute(ri)(cr2, c)
        then
            if isone(ri)((cr ^ (c * r)
                      * cr ^ (cr2 * c)) ^ 3)
            then
                Add(result, cWithMem ^ 2 * rWithMem);
            else
                Add(result, cWithMem * rWithMem);
            fi;
        fi;
        if Length(result) > R then break; fi;
    od;
    return result;
end;

# ri : recognition node with group G
# g : element of G,
#     should be a cycle matching c
# c : element of G,
#     should be a 3-cycle
# r : element of G
#
# Returns a boolean.
#
# If the input is as assumed, that is in particular the supports of c and
# c^(g^2) have exactly one point, say alpha, in common, then this function
# returns whether alpha is a fixed point of r.
RECOG.IsFixedPoint := function(ri, g, c, r)
    local
        # respectively c ^ (g ^ i)
        cg, cg2, cg3, cg4,
        # temporary holder of H1, H2
        temp,
        # (sets of) elements of G
        H1, H2, x1, x2, x3,
        # helper function
        commutesWithAtMostOne;
    # Helper function
    commutesWithAtMostOne := function(ri, x, H)
        local nrTrivialComm, h;
        nrTrivialComm := 0;
        for h in H do
            if docommute(ri)(x, h) then
                nrTrivialComm := nrTrivialComm + 1;
            fi;
            if nrTrivialComm >= 2 then
                return false;
            fi;
        od;
        return true;
    end;
    cg := c ^ g;
    cg2 := cg ^ g;
    cg3 := cg2 ^ g;
    cg4 := cg3 ^ g;
    H1 := [ c ^ 2, c ^ cg, ~[2] ^ cg3, ~[3] ^ cg3, ~[4] ^ cg4 ];
    # Test whether an element of the set X commutes with at least
    # two elements of H1.
    x1 := c ^ r;
    if not commutesWithAtMostOne(ri, x1, H1) then return false; fi;
    x2 := cg2 ^ r;
    if not commutesWithAtMostOne(ri, x2, H1) then return false; fi;
    x3 := ((cg2 ^ cg3) ^ cg4) ^ r;
    if not commutesWithAtMostOne(ri, x3, H1) then return false; fi;
    # Test whether an elm of the set X commutes with at least
    # two elements of H2.
    H2 := [c, cg, ~[2] ^ cg3, ~[3] ^ cg3, ~[4] ^ cg4];
    if not commutesWithAtMostOne(ri, x1, H2) then return false; fi;
    if not commutesWithAtMostOne(ri, x2, H2) then return false; fi;
    if not commutesWithAtMostOne(ri, x3, H2) then return false; fi;
    return true;
end;

# ri : recognition node with group G
# g : element of G,
#     should be a k-cycle matching c
# c : element of G,
#     should be a 3-cycle
# r : element of G,
#     should have at least one moved point in common with g and should fix at
#     least two moved points of g
# k : integer,
#     should be length of cycle g
#
# Returns fail or a conjugate of r.
#
# W.l.o.g. let g = (1, ..., k) and c = (1, 2, 3).
# If the input is as assumed, then the algorithm returns a conjugate r ^ x such
# that r ^ x fixes the points 1, 2 but not the point 3.
RECOG.AdjustCycle := function(ri, g, c, r, k)
    local
        # list of 4 booleans, is point j fixed point
        F4,
        # smallest fixed point
        f1,
        # second smallest fixed point
        f2,
        # smallest non-fixed point
        m,
        # bool, false if |F| < 2 or |F| = k
        success,
        # integer, loop variable over [1 .. k]
        j,
        # element of G, loop variable
        t,
        # conjugating element
        x;
    # According to the paper we have:
    # F := { 1 <= j <= k | RECOG.IsFixedPoint(g, c ^ (g ^ (j - 3)), r) = true }
    # f1 := smallest number in F
    # f2 := second smallest number in F
    # m := smallest number *not* in F
    # We do not store F explicitely. Instead we store the intersection of F and
    # {1, 2, 3, 4} in the variable F4.
    F4 := [false, false, false, false];
    f1 := fail;
    f2 := fail;
    m := fail;
    t := c ^ (g ^ -3);
    for j in [1 .. k] do
        # invariant: t = c ^ (g ^ (j - 3))
        t := t ^ g;
        if RECOG.IsFixedPoint(ri, g, t, r) then
            if j <= 4 then
                F4[j] := true;
            fi;
            if f1 = fail then
                f1 := j;
            elif f2 = fail then
                f2 := j;
            fi;
        elif m = fail then
            m := j;
        fi;
        # f1 and f2 not being fail is equivalent to |F| >= 2
        # m not being fail is equivalent to |F| < k
        success := f1 <> fail and f2 <> fail and m <> fail;
        if success then
            if j >= 4 then
                break;
            # case 2, we do not need to compute F4[4]
            elif f1 = 1 and f2 = 2 and m = 3 then
                return r;
            fi;
        fi;
    od;
    if not success then
        return fail;
    fi;
    # case distinction on F as in the table of Algorithm 4.20
    # via a decision tree
    if F4[1] then
        if F4[2] then
            # We are in case 1, since case 2 is handled during the
            # computation of F4 above.
            x := c ^ ((g * c ^ 2) ^ (m - 3) * c) * c;
        else
            if F4[3] then
                if F4[4] then
                    # case 3
                    x := c ^ g;
                else
                    # case 4
                    x := (c ^ 2) ^ g;
                fi;
            else
                # case 5
                x := c ^ ((g * c ^ 2) ^ (f2 - 3) * c);
            fi;
        fi;
    else
        if F4[2] then
            if F4[4] then
                # case 6
                x := c ^ (c ^ g);
            else
                if F4[3] then
                    # case 7
                    x := (c ^ 2) ^ (c ^ g);
                else
                    # case 8
                    x := c ^ ((g * c ^ 2) ^ (f2 - 3) * c ^ g);
                fi;
            fi;
        else
            if F4[3] then
                # case 9
                x := (c ^ 2) ^ ((g * c ^ 2) ^ (f2 - 3)) * c ^ 2;
            else
                # case 10
                x := c ^ ((g * c ^ 2) ^ (f2 - 3)) * c ^ ((g * c ^ 2) ^ (f1 - 3));
            fi;
        fi;
    fi;
    return r^x;
end;

# ri : recognition node with group G
# g : element of G,
#     should be a k-cycle matching c
# c : element of G,
#     should be a 3-cycle
# r : element of G,
#     should be a cycle as in the return value of RECOG.AdjustCycle. If e.g.
#     g = (1, 2, ..., k), then r would be a cycle fixing 1 and 2 and moving 3.
# s : element of group G,
#     should be a storage cycle
# k : integer,
#     should be length of cycle g
# k0 : integer,
#      should be length of cycle r
#
# Returns a list consisting of:
# - gTilde: element of G,
#           should be a cycle matching g
# - sTilde: element of G,
#           should be current storage cycle, since we may call RECOG.AppendPoints
#           several times and may not have used the last sTilde.
# - kTilde: integer,
#           should be the length of gTilde
#
# The algorithm appends new points to the cycle g. Since g will always be a
# cycle of odd length, new points can only be appended in pairs. We identify
# the point j in {1, ..., k} with the 3-cycle c ^ (g ^ (j - 3)). We store new
# points in the storage cycle sTilde until we have found two different points.
# Then we append these to g.
RECOG.AppendPoints := function(ri, g, c, r, s, k, k0)
    local gTilde, sTilde, kTilde, gc2, x, j;
    gTilde := g;
    sTilde := s;
    kTilde := k;
    x := c;
    for j in [1 .. k0 - 1] do
        # invariant: x = c ^ (r ^ j)
        x := x ^ r;
        if docommute(ri)(x, gTilde * c ^ 2) then
            # If sTilde doesn't already store a point, then store x.
            if isone(ri)(sTilde) then
                sTilde := x;
            fi;
            # Do we now have two different points? If so, append them.
            if not isone(ri)(sTilde) and not isequal(ri)(sTilde, x) then
                kTilde := kTilde + 2;
                gTilde := gTilde * sTilde ^ (x ^ 2);
                sTilde := One(gTilde);
            fi;
        fi;
    od;
    return [gTilde, sTilde, kTilde];
end;

# ri : recognition node with group G
# g : element of G
# p : prime
# Returns whether g is an element of order p.
RECOG.IsElmOfPrimeOrder := function(ri, g, p)
    if not isone(ri)(g) and isone(ri)(g ^ p) then
        return true;
    else
        return false;
    fi;
end;

# ri : recognition node with group G
# c : a 3-cycle of a group G
# x : bolstering element with respect to c
# N : integer, upper bound for the degree of G
#
# returns either fail or a list consisting of:
# - g, cycle matching c
# - k, length of cycle g.
#
# We return fail if one of the following holds:
# - N is not an upper bound for the degree of G
# - c is not a 3-cycle
RECOG.BuildCycle := function(ri, c, x, N)
    local
        # integers
        m, mDash,
        # group elements
        d, y, dx, e, z, f, g, x2;
    # Compute m.
    # m is the least natural number such that with
    # d = c ^ (x ^ (m + 1))
    # we have Order(d * c) <> 5. Note that m >= 1.
    # We also compute
    # y = c * (c ^ x) * (c ^ (x ^ 2)) * ... * (c ^ (x ^ m)).
    # The next three lines correspond to m = 1
    # We use x ^ 2 several times.
    x2 := x ^ 2;
    m := 1;
    y := c * (c ^ x);
    d := c ^ x2;
    while true do
        if m >= N / 2 then
            return fail;
        elif RECOG.IsElmOfPrimeOrder(ri, d * c, 5) then
            m := m + 1;
        else
            break;
        fi;
        y := y * d;
        d := d ^ x;
    od;
    if m = 1 then
        return fail;
    fi;
    # case |alpha - beta| = 0
    if isequal(ri)(d, c) or isequal(ri)(d, c ^ 2) then
        return [y, 2 * m + 3];
    fi;
    # case |alpha - beta| = 1
    dx := d ^ x;
    if not RECOG.IsElmOfPrimeOrder(ri, dx * c, 5) then
        return [y, 2 * m + 3];
    fi;
    # case |alpha - beta| >= 2
    # case distinction on element e
    # w in v ^ <x>
    if not RECOG.IsElmOfPrimeOrder(ri, d * c, 2) then
        # case 1, alpha > beta
        if docommute(ri)(dx, d ^ c) then
            e := dx ^ c;
        # case 2, alpha < beta
        else
            e := (dx ^ (c ^ 2)) ^ 2;
        fi;
    # w not in v ^ <x>
    else
        # case 3, alpha > beta
        if not docommute(ri)(dx, d ^ c) then
            e := dx ^ (c ^ 2);
        # case 4, alpha < beta
        else
            e := (dx ^ c) ^ 2;
        fi;
    fi;
    z := d ^ e;
    # Compute m' (here mDash).
    # mDash is the least natural number such that with
    # f := z ^ (x ^ (2 * mDash))
    # we have Order(f * c) <> 5. Note that mDash >= 1.
    # We also compute
    # g = y * z * (z ^ (x ^ 2)) * ... * (z ^ (x ^ (2 * (mDash - 1)))).
    # The next three lines correspond to mDash = 1
    mDash := 1;
    g := y * z;
    f := z ^ x2;
    while true do
        if mDash >= N / 2 then
            return fail;
        elif RECOG.IsElmOfPrimeOrder(ri, f * c, 5) then
            mDash := mDash + 1;
        else
            break;
        fi;
        g := g * f;
        f := f ^ x2;
    od;
    return [g, 2 * mDash + 2 * m + 3];
end;

# ri : recognition node with group G
# c : element of G,
#     should be a 3-cycle
# eps : real number, the error bound
# N : integer, upper bound for the degree of G
#
# Returns fail or a list [g, k] consisting of:
# - g: element of G,
#      should be a k-cycle matching c
# - k: integer,
#      should be length of cycle g.
#
# Note that the order of the returned list is reversed with respect to the
# paper to be consistent with the return values of the other functions.
#
# We return fail if one of the following holds:
# - the list of bolstering elements is too small
# - N is not an upper bound for the degree of G
# - c is not a 3-cycle
RECOG.ConstructLongCycle := function(ri, c, eps, N)
    local g, k, tmp, B, x;
    B := RECOG.BolsteringElements(ri, c, Float(eps) / 2., N);
    if Length(B) < Int(Ceil(7. / 4. * Log(2. / Float(eps)))) then
        return fail;
    fi;
    k := 0;
    for x in B do
        tmp := RECOG.BuildCycle(ri, c, x, N);
        if tmp = fail then
            return fail;
        elif tmp[2] > k then
            g := tmp[1];
            k := tmp[2];
        fi;
    od;
    return [g, k];
end;

# ri : recognition node with group G
# g : element of G,
#     should be a k-cycle matching c
# c : element of G,
#     should be a 3-cycle
# k : integer,
#     should be length of cycle g
# eps : real number, the error bound
# N : integer, upper bound for the degree of G
#
# Returns fail or a list consisting of:
# - gTilde : element of G,
#            long cycle, a standard generator of An < G
# - cTilde : element of G,
#            3-cycle, a standard generator of An < G
# - kTilde : integer,
#            degree of group An < G, that is generated by gTilde and cTilde
RECOG.StandardGenerators := function(ri, g, c, k, eps, N)
    local s, k0, c2, r, kTilde, gTilde, i, x, m, tmp, cTilde;
    s := One(g);
    k0 := k - 2;
    c2 := c ^ 2;
    r := g * c2;
    kTilde := k;
    gTilde := g;
    for i in [1 .. Int(Ceil(Log(10. / 3.) ^ (-1)
            * (Log(Float(N)) + Log(1 / Float(eps)))))] do
        x := r ^ RandomElm(ri, "SnAnUnknownDegree", true)!.el;
        m := RECOG.AdjustCycle(ri, gTilde, c, x, kTilde);
        if m = fail then return fail; fi;
        tmp := RECOG.AppendPoints(ri, gTilde, c, m, s, kTilde, k0);
        gTilde := tmp[1];
        s := tmp[2];
        kTilde := tmp[3];
        if kTilde > N then return fail; fi;
    od;
    if isone(ri)(s) then
        gTilde := c2 * gTilde;
        cTilde := c;
    else
        kTilde := kTilde + 1;
        gTilde := gTilde * s;
        cTilde := s;
    fi;
    if RECOG.SatisfiesAnPresentation(ri,
                                     StripMemory(gTilde),
                                     StripMemory(cTilde),
                                     kTilde) then
        return [gTilde, cTilde, kTilde];
    else
        return fail;
    fi;
end;

# This function is an excerpt of the function RECOG.RecogniseSnAn in gap/SnAnBB.gi
# ri : recognition node with group G,
# n : degree
# stdGensAnWithMemory : standard generators of An < G
#
# Returns either fail or a record with components:
# [s, stdGens, xis, n], where:
# - type: the isomorphism type, that is either the string "Sn" or "An".
# - isoData: a list [stdGens, xis, n] where
#   - stdGens are the standard generators of G. They do not have memory.
#   - xis implicitly defines the isomorphism. It is used by RECOG.FindImageSn
#     and RECOG.FindImageAn to compute the isomorphism.
#   - n is the degree of the group.
# - slpToStdGens: an SLP to stdGens.
#
# TODO: Image Computation requires n >= 11.
RECOG.ConstructSnAnIsomorphism := function(ri, n, stdGensAnWithMemory)
    local stdGensAn, xis, gImage, foundOddPermutation, slp, eval,
        hWithMemory, bWithMemory, stdGensSnWithMemory, b, h, g;
    stdGensAn := StripMemory(stdGensAnWithMemory);
    xis := RECOG.ConstructXiAn(n, stdGensAn[1], stdGensAn[2]);
    foundOddPermutation := false;
    for g in ri!.gensHmem do
        gImage := RECOG.FindImageAn(ri, n, StripMemory(g),
                                    stdGensAn[1], stdGensAn[2],
                                    xis[1], xis[2]);
        if gImage = fail then return fail; fi;
        if SignPerm(gImage) = -1 then
            # we found an odd permutation,
            # so the group cannot be An
            foundOddPermutation := true;
            break;
        fi;
        slp := RECOG.SLPforAn(n, gImage);
        eval := ResultOfStraightLineProgram(slp,
                                            [stdGensAn[2], stdGensAn[1]]);
        if not isequal(ri)(eval, StripMemory(g)) then return fail; fi;
    od;
    if not foundOddPermutation then
        return rec(type := "An",
                   isoData := [[stdGensAn[1], stdGensAn[2]], xis, n],
                   slpToStdGens := SLPOfElms(stdGensAnWithMemory));
    fi;
    # Construct standard generators for Sn: [bWithMemory, hWithMemory].
    slp := RECOG.SLPforAn(n, (1,2) * gImage);
    eval := ResultOfStraightLineProgram(
        slp, [stdGensAnWithMemory[2], stdGensAnWithMemory[1]]
    );
    hWithMemory := eval * g ^ -1;
    bWithMemory := stdGensAnWithMemory[1] * stdGensAnWithMemory[2];
    if n mod 2 = 0 then
        bWithMemory := hWithMemory * bWithMemory;
    fi;
    stdGensSnWithMemory := [bWithMemory, hWithMemory];
    b := StripMemory(bWithMemory);
    h := StripMemory(hWithMemory);
    if not RECOG.SatisfiesSnPresentation(ri, n, b, h) then
        return fail;
    fi;
    xis := RECOG.ConstructXiSn(n, b, h);
    for g in ri!.gensHmem do
        gImage := RECOG.FindImageSn(ri, n, StripMemory(g),
                                    b, h,
                                    xis[1], xis[2]);
        if gImage = fail then return fail; fi;
        slp := RECOG.SLPforSn(n, gImage);
        eval := ResultOfStraightLineProgram(slp, [h, b]);
        if not isequal(ri)(eval, StripMemory(g)) then return fail; fi;
    od;
    return rec(type := "Sn",
               isoData := [[b, h], xis, n],
               slpToStdGens := SLPOfElms(stdGensSnWithMemory));
end;

# This method is an implementation of <Cite Key="JLNP13"/>. It is the main
# function of SnAnUnknownDegree.
# Note that it currently only works for 11 <= <A>n</A>. TODO: make it work with
# smaller <A>n</A>, that is include fixes from Jonathan Conder's B.Sc.
# Thesis "Algorithms for Permutation Groups", see PR #265.
#
# From <Cite Key="JLNP13" Where="Theorem 1.1"/>:
# RECOG.RecogniseSnAn is a one-sided Monte-Carlo algorithm with the following
# properties. It takes as input a black-box group <A>G</A>, a natural number
# <A>N</A> and a real number <A>eps</A> with 0 < <A>eps</A> < 1. If <A>G</A> is
# isomorphic to An or Sn for some 9 <= <A>n</A> <= <A>N</A>, it returns with
# probability at least 1 - <A>eps</A> the degree <A>n</A> and an
# isomorphism from <A>G</A> to An or Sn.
RECOG.RecogniseSnAn := function(ri, eps, N)
    local T, foundPreImagesOfStdGens, constants, iterator, c, tmp, recogData, i;
    T := Int(Ceil(Log2(1 / Float(eps))));
    foundPreImagesOfStdGens := false;
    constants := RECOG.ThreeCycleCandidatesConstants(1. / 4., N);
    for i in [1 .. T] do
        iterator := RECOG.ThreeCycleCandidatesIterator(ri, constants);
        c := iterator();
        while c <> fail do
            if c = NeverApplicable then return NeverApplicable; fi;
            # This is a very cheap test to determine
            # if our candidate c could be a three cycle.
            if not isone(ri)(StripMemory(c) ^ 3) then
                c := iterator();
                continue;
            fi;
            tmp := RECOG.ConstructLongCycle(ri, c, 1. / 8., N);
            if tmp = fail then
                c := iterator();
                continue;
            fi;
            # Now tmp contains [g, k] where
            #   g corresponds to a long cycle
            #   k is its length
            tmp := RECOG.StandardGenerators(ri, tmp[1], c, tmp[2], 1. / 8., N);
            if tmp = fail then
                c := iterator();
                continue;
            fi;
            # Now tmp contains [g, c, n] where
            #   g, c correspond to standard generators of An
            recogData := RECOG.ConstructSnAnIsomorphism(ri, tmp[3], tmp{[1,2]});
            if recogData = fail then continue; fi;
            return recogData;
        od;
    od;
    return TemporaryFailure;
end;

#! @BeginChunk SnAnUnknownDegree
#! This method tries to determine whether the input group given by <A>ri</A> is
#! isomorphic to a symmetric group Sn or alternating group An with
#! <M>11 \leq n</M>.
#! It is an implementation of <Cite Key="JLNP13"/>.
#!
#! If <A>Grp(ri)</A> is a permutation group, we assume that it is primitive and
#! not a giant (a giant is Sn or An in natural action).
#!
#! @EndChunk
BindRecogMethod(FindHomMethodsGeneric, "SnAnUnknownDegree",
"method groups isomorphic to Sn or An with n >= 11",
function(ri, G)
    local eps, N, p, d, recogData, isoData, degree, swapSLP;
    #G := Grp(ri);
    # TODO find value for eps
    eps := 1 / 10^2;
    # Check magma
    if IsPermGroup(G) then
        # We assume that G is primitive and not a giant.
        # The smallest non-natural primitive action of Sn or An induces
        # a large base group. Thus by [L84] its degree is smallest, when the
        # action is on 2-subsets. Thus its degree is at least n * (n-1) / 2.
        # Thus for a given degree k, we have
        # n >= 1/2 + Sqrt(1/4 + 2*k).
        N := Int(Ceil(1/2 + Sqrt(Float(1/4 + 2 * NrMovedPoints(G)))));
    elif IsMatrixGroup(G) then
        p := Characteristic(DefaultFieldOfMatrixGroup(G));
        d := DimensionOfMatrixGroup(G);
        # Let N be the largest integer such that A_N has a representation of
        # dimension d.
        if ri!.projective then
            # If n >= 9, then the smallest irreducible projective An-module has
            # dimension n-2, see [KL90], Proposition 5.3.7.
            # Assume N >= 9 and use the comment above to compute N. If we
            # arrive at a value < 9 for N, then we must have been in the case N
            # < 9.
            # TODO: The table in [KL90], Proposition 5.3.7. has more detailed
            # values for 5 <= n < 9. Do we want to use that?
            N := Maximum(8, d + 2);
        else
            # If n >= 10, then the smallest irreducible An-module is the
            # fully deleted permutation module, see [KL90], Proposition 5.3.5.
            # It has dimension n-2 if p|n and dimension n-1 otherwise.
            # Assume N >= 10 and use the comment above to compute N. If we
            # arrive at a value < 10 for N, then we must have been in the case
            # N < 10.
            if (d + 2) mod p = 0 then
                N := d + 2;
            else
                N := d + 1;
            fi;
            N := Maximum(9, N);
        fi;
    else
        N := ErrorNoReturn("SnAnUnknownDegree: no method to compute bound",
                           " <N>, Grp(<ri>) must be an IsPermGroup or an",
                           " IsMatrixGroup");
    fi;
    # Try to find an isomorphism
    recogData := RECOG.RecogniseSnAn(ri, eps, N);
    # RECOG.RecogniseSnAn returned NeverApplicable or TemporaryFailure
    if not IsRecord(recogData) then
        return recogData;
    fi;
    isoData := recogData.isoData;
    ri!.SnAnUnknownDegreeIsoData := isoData;
    SetFilterObj(ri, IsLeaf);
    degree := isoData[3];
    if recogData.type = "Sn" then
        SetSize(ri, Factorial(degree));
        SetIsRecogInfoForAlmostSimpleGroup(ri, true);
    else
        SetSize(ri, Factorial(degree) / 2);
        SetIsRecogInfoForSimpleGroup(ri, true);
    fi;
    # Note that when setting the nice generators we reverse their order, such
    # that it fits to the SLPforSn/SLPforAn function!
    SetNiceGens(ri, Reversed(isoData[1]));
    swapSLP := StraightLineProgram([[[2, 1], [1, 1]]], 2);
    Setslptonice(ri,
                 CompositionOfStraightLinePrograms(swapSLP,
                                                   recogData.slpToStdGens));
    if recogData.type = "Sn" then
        Setslpforelement(ri, SLPforElementFuncsGeneric.SnUnknownDegree);
    else
        Setslpforelement(ri, SLPforElementFuncsGeneric.AnUnknownDegree);
    fi;
    return Success;
end);

# The SLP function if G is isomorphic to Sn.
SLPforElementFuncsGeneric.SnUnknownDegree := function(ri, g)
    local isoData, degree, image;
    isoData := ri!.SnAnUnknownDegreeIsoData;
    degree := isoData[3];
    image := RECOG.FindImageSn(ri, degree, g, isoData[1][1], isoData[1][2],
                       isoData[2][1], isoData[2][2]);
    return RECOG.SLPforSn(degree, image);
end;

# The SLP function if G is isomorphic to An.
SLPforElementFuncsGeneric.AnUnknownDegree := function(ri, g)
    local isoData, degree, image;
    isoData := ri!.SnAnUnknownDegreeIsoData;
    degree := isoData[3];
    image := RECOG.FindImageAn(ri, degree, g, isoData[1][1], isoData[1][2],
                       isoData[2][1], isoData[2][2]);
    return RECOG.SLPforAn(degree, image);
end;