Add better code for constructive recognition of `SL(3,q)` in natural representation

[fingolfin]

The constructive SL(d,q) recognition reduces almost all cases to SL(2,q) (which we have covered nicedly now), except for this one.

I think right now we just fall back to StabilizerChainProj in this case.

One option would be to implement the algorithm from https://doi.org/10.1016/j.jalgebra.2007.01.020 (Some relevant code fragments are in contrib/frank/sl2/SL3.g). That may be useful anyway, to deal with the general (black box) situation.

But for our special case, there might be a simpler and more efficient solution, sketched by @frankluebeck in an email to @Till-Eisen and myself. The idea is basically to treat $\mathrm{SL}(3)$ by a variant of the $\mathrm{SL}_n$ algorithm. Here is my translation (any mistakes are mine, of course):

For the going-down step, one just has to make a small modification (if two eigenvalues are 1, then of course the third one is as well). Namely,

q := ???;
G := SL(3, q);
t := PseudoRandom(G)^(q+1);

quite often produces an element with two equal eigenvalues. Then

u := Subgroup(G, [t, t^PseudoRandom(G)]);

is almost always (often more than one-third of the time) isomorphic to GL(2, q), and

s := DerivedSubgroup(u);  # or the subgroup generated by three random
                          # commutators from u

is even more frequently an SL(2, q). (See Lemmas 2.2–2.4 in the SL3 paper.)

[Till-Eisen]

I have benchmarked this approach. In the following you find the code and results. Note that there is an error rate in the function SL3GoingDown in the verifying procedure although this should be more than 99% accurate.

SL3GoingDown := function(q)
    local G, t, rand, u, s, list, x,y,
    bool1, bool2, ready, orderx, count, i;
    
    G := SL(3, q);

    t := PseudoRandom(G)^(q+1);
    rand := PseudoRandom(G);
    u := Subgroup(G, [t, t^rand]);
    
    list := [];
    for i in [1..10] do
        x := PseudoRandom(u);
        y := PseudoRandom(u);
        Add(list, Comm(x,y));
    od;
    #s := DerivedSubgroup(u);
    s := Group(list);
    
    #Verifying s = SL(2,q):
    ready := false;
    count := 0;
    bool1 := false;
    bool2 := false;
    repeat
        x:=PseudoRandom(s);
        orderx:=Order(x);
        if orderx = q-1 then
            bool1:=true;
        elif orderx = q+1 then
            bool2 :=true;
        fi;

        if bool1 = true and bool2 = true then
            ready:=true;
        break;
        fi;
        count:=count+1;
    until count=20;
    return ready;
end;



TestSL3GoingDown := function(q_list, iterations)
    local q, i, successes, rate;
    
    Print("-------------------------------------------\n");
    Print(String("q", 5), " | ", String("success rate", 25), " \n");
    Print("-------------------------------------------\n");
    
    for q in q_list do
        successes := 0;
        for i in [1..iterations] do
            if SL3GoingDown(q) then
               successes := successes + 1;
            fi;
        od;
        rate := Float(successes) / Float(iterations) * 100.0;
        Print(String(q, 5), " | ", String(Concatenation(String(successes), "/", String(iterations)), 25), "\n");
    od;
    Print("-------------------------------------------\n");
end;


TestSL3GoingDown([2,3,4,5,7,9,11,13, 17,23,53, 67, 101, 127], 1000);

-------------------------------------------
    q |              success rate 
-------------------------------------------
    2 |                  133/1000
    3 |                  219/1000
    4 |                  425/1000
    5 |                  339/1000
    7 |                  295/1000
    9 |                  406/1000
   11 |                  381/1000
   13 |                  363/1000
   17 |                  435/1000
   23 |                  459/1000
   53 |                  492/1000
   67 |                  452/1000
  101 |                  484/1000
  127 |                  438/1000
  163 |                  490/1000
  167 |                  472/1000

TestSL3GoingDown([2^20, 3^10, 67^6 ], 100);
-------------------------------------------
    q |              success rate 
-------------------------------------------
1048576 |                    51/100
59049 |                    45/100
90458382169 |                    44/100
-------------------------------------------

[frankluebeck]

Thanks for this check.

I guess the derived subgroup is ususally generated by 3 random commutators (may take 5 for very small q;
and GL(2,2) = SL(2,2)).

[fingolfin]

@Till-Eisen I think you numbers over estimate the success rate because the code for checking for SL(2,q) is too generous.

If I instead use this inefficient but more accurate (but not fully accurate) test:

  return SizeSL(2,q) = Size(RecognizeGroup(s));

then I see rates like these:

-------------------------------------------
    q |              success rate
-------------------------------------------
    2 |                    0/1000
    3 |                    0/1000
    4 |                    8/1000
    5 |                  129/1000
    7 |                   60/1000
    9 |                  273/1000
   11 |                  271/1000
   13 |                  198/1000

[Till-Eisen]

I think I falsely assumed that the derived subgroup is a subgroup of SL(2,q).. Thanks for pointing it out.

Here the success rate for the same list of q's as above with your correction in the code. Note that $2^{20}, 3^{10}, 67^6$ are to large to compute the size of the derived subgroup in a reasonable time.

    q |              success rate 
-------------------------------------------
    2 |                    0/1000
    3 |                    0/1000
    4 |                    7/1000
    5 |                  122/1000
    7 |                   47/1000
    9 |                  257/1000
   11 |                  289/1000
   13 |                  194/1000
   17 |                  398/1000
   23 |                  382/1000
   53 |                  449/1000
   67 |                  447/1000
  101 |                  471/1000
  127 |                  468/1000
  163 |                  482/1000
  167 |                  487/1000

[Till-Eisen]

I have another idea for an algorithm if $q>3$ is odd. However, I am not sure about its running time:

• Find an involution $i \in SL(3,q)$
• Compute the centraliser $C$ of $i$ in $SL(3,q)$ which is isomorphic to $S(GL(2,q) \times \mathbb{F}_q^{\times})$
• Then compute $\langle g^{q-1}| g \in C \rangle \cong \langle g^{q-1}| g \in GL(2,q) \rangle =SL(2,q)$, where the equality comes from the fact that $N:= \langle g^{q-1}| g \in GL(2,q) \rangle$ is normal in $SL(2,q)$, see the following.
  a) $N$ is a subgroup of SL(2,q), since $q-1= |\mathbb{F}_q^{\times}|$ therefore $\lambda^{q-1}=1$ for all $\lambda \in \mathbb{F}_q$ and
  b) for $s\in SL(2,q), g\in GL(2,q)$ we have $s^{-1}g^{q-1}s= (s^{-1}gs)^{q-1}\in N$.

To elaborate a little more why it is enough for $N$ to be normal in $SL(2,q)$:
For $q>3$, we have that $PSL(2,q)$ is simple. Since $q-1 \equiv -1$ in $\mathbb{F}_q$, taking the $q-1$th power of the unipotent matrix with $-1$ in the upper right corner one obtains a unipotent element with $1$ on the upper right corner, which shows that $N$ contains non-central elements. Thus, $N$ is larger than $Z(SL(2,q))$ and therefore the whole group.

Update
I have implemented this approach. However, even computing the centralizer with ECOG.InvolutionCentraliser takes longer than the original approach by @frankluebeck. So we can discard this idea. For $q=3$ my idea also yields a very high percentage of success. Perhaps a benchmark for the running time against the current used function StabilizerChainProj (?) would be nice to have.

The code:

SL3GoingDown_2 := function(G, q)
    local g, ord, C, i, list, s, pr;

    pr := ProductReplacer(GeneratorsOfGroup(G));
    ord := Order;

    # Find involution
    g := RECOG.InvolutionSearcher(pr, ord, 1000);

    #Compute Centraliser
    C := RECOG.InvolutionCentraliser(pr, ord, g, 50);

    #Compute N = <g^(q-1) | g \in C>
    list := [];
    for i in [1..(8*(q-1))] do
        g := PseudoRandom(C)^(q-1);
        Add(list, g);
    od;
    s := Subgroup(G, list);
    
    return Size(s) = Size(SL(2,q));
    #return s;
end;



TestSL3GoingDown := function(q_list, iterations)
    local q, i, successes, rate, G;
    
    Print("-------------------------------------------\n");
    Print(String("q", 5), " | ", String("success rate", 25), " \n");
    Print("-------------------------------------------\n");
    for q in q_list do
        successes := 0;
        G := SL(3,q);
        for i in [1..iterations] do
            if SL3GoingDown_2(G,q) then
                successes := successes + 1;
            fi;
        od;
        rate := Float(successes) / Float(iterations) * 100.0;
        Print(String(q, 5), " | ", String(Concatenation(String(successes), "/", String(iterations)), 25), "\n");
    od;
    Print("-------------------------------------------\n");
end;



TestSL3GoingDown([3,5,7,9,11], 1000);

-------------------------------------------
    q |              success rate 
-------------------------------------------
    3 |                  906/1000
    5 |                  947/1000
    7 |                  924/1000
    9 |                  970/1000
   11 |                  992/1000

[fingolfin]

@Till-Eisen isn't the derived subgroup of $S(GL(2,q) \times \mathbb{F}_q^{\times})$ also $SL(2,q)$? So you could try that approach here, too.

Looking at the involution centralizer, I think you are trying way to hard.

Also, don't use Size(s), use Size(RecognizeGroup(s)).

Here is a version based on that:

SetInfoLevel(InfoRecog,0); SetInfoLevel(InfoMethSel,0);

SL3GoingDown_2 := function(G, q)
    local g, ord, C, i, list, s, pr;

    pr := ProductReplacer(GeneratorsOfGroup(G));
    ord := Order;

    # Find involution
    g := RECOG.InvolutionSearcher(pr, ord, 20);

    #Compute Centraliser
    C := RECOG.InvolutionCentraliser(pr, ord, g, 6);

    #Compute N = <g^(q-1) | g \in C>
    list := [];
    for i in [1..10] do
        x := PseudoRandom(C);
        y := PseudoRandom(C);
        Add(list, Comm(x,y));
    od;
    s := Subgroup(G, list);
    
    return Size(RecognizeGroup(s)) = SizeSL(2,q);
    #return s;
end;

It seems to work very well, and is fastest of all the versions I tried so far:

gap> TestSL3GoingDown([3,5,7,9,11, 3^10], 100);
-------------------------------------------
    q |              success rate
-------------------------------------------
    3 |                    94/100
    5 |                    99/100
    7 |                    99/100
    9 |                    99/100
   11 |                   100/100
59049 |                   100/100
-------------------------------------------

[Till-Eisen]

I did some benchmarks to compare the running time between Frank Lübecks idea (implemented in SL3GoingDown) and my idea (implemented in SL3GoingDown_2). This implies that we need a separate code for $q=2$, perhaps use SL3GoingDown_2 for very small odd prime powers and else SL3GoingDown?

SL3GoingDown := function(G,q)
    local t, rand, u, s, list, x,y, i;

    t := PseudoRandom(G)^(q+1);
    rand := PseudoRandom(G);
    u := Subgroup(G, [t, t^rand]);
    
    list := [];
    for i in [1..10] do
        x := PseudoRandom(u);
        y := PseudoRandom(u);
        Add(list, Comm(x,y));
    od;
    #s := DerivedSubgroup(u);
    s := Subgroup(G, list);
    return s;
end;

SL3GoingDown_2 := function(G, q)
    local g, ord, C, i, list, s, pr,x,y;

    pr := ProductReplacer(GeneratorsOfGroup(G));
    ord := Order;

    # Find involution
    g := RECOG.InvolutionSearcher(pr, ord, 20);

    #Compute Centraliser
    C := RECOG.InvolutionCentraliser(pr, ord, g, 6);

    #Compute N = <g^(q-1) | g \in C>
    list := [];
    for i in [1..10] do
        x := PseudoRandom(C);
        y := PseudoRandom(C);
        Add(list, Comm(x,y));
    od;
    s := Subgroup(G, list);
    return s;
end;

gap> q := 3;;
gap> G := SL(3,q);;
gap> for i in [1..1000] do SL3GoingDown_2(G,q); od; time;
601
gap> 
gap> for i in [1..1000] do SL3GoingDown(G,q); od; time;
281

gap> q := 5^4;;
gap> G := SL(3,q);;
gap> 
gap> for i in [1..1000] do SL3GoingDown_2(G,q); od; time;
1835
gap> 
gap> for i in [1..1000] do SL3GoingDown(G,q); od; time;
652

gap> q := 5^11;;
gap> G := SL(3,q);;
gap> 
gap> for i in [1..100] do SL3GoingDown_2(G,q); od; time;
4831
gap> for i in [1..100] do SL3GoingDown(G,q); od; time;
914