(2, 1).

107

Q— with conjugation as described in Item 8 (resp.,

¯ ¯

• (1, ∞) (resp., (∞, 1)): Return Q2

Item 9) of Lemma 4.5.2.

Q— with conjugation as described in Item 4 (resp.,

¯ ¯

• (2, ∞) (resp., (∞, 2)): Return Q

Item 3) of Lemma 4.5.2.

¯

• (2, 2) : Compute r1 , r2 ∈ Q(x) such that (4.24) holds. Apply Lemma 4.6.9 to compute

Q— — Q— , then return GL (Q— — Q— ) with

¯ ¯ ¯ ¯ ¯

Q

the maximal torus T of GL . If T

conjugation as described in Item 1 of Lemma 4.5.4. Otherwise, apply Lemma 4.6.9 to

compute m1 , m2 such that [T ]F(r1 ,r2 ) = T(m1 ,m2 ) ⊆ D3 © SL3 . Compute n1 (resp., n2 ),

the number of ¬rst-order right factors of (D ’ r2 ) —¦ (D ’ r1 ) (resp., of (D + r1 + r2 ) —¦

(D ’ r2 )).

Q— with (Int t)(u) = tm1 ’m2 u.

¯ ¯

Q

“ If n1 = 1, n2 = 2 : Return GL

Q— with (Int t)(u) = tm1 +2m2 u.

¯ ¯

Q

“ If n1 = 2, n2 = 1 : Return GL

Q— with (Int t)(u) = t2m1 +m2 u.

¯ ¯

Q

“ If n1 = 2, n2 = 2 : Return GL

• (3, 3) : Apply Lemma 4.6.9 to compute the maximal torus T ; return GL = T.

¯ ¯

• (∞, ∞) : Find the dimension of the Q-vector space of Q(x)-rational solutions of L(y) =

Q— .

¯

{1} ; otherwise, return GL

0. If this dimension is 3, then return GL

• (1, 1) : Let Ld be the unique monic dth-order right factor of L for d = 1, 2.

1. If L1 fails to right-divide L2 : Then GL = GL2 is isomorphic to either SL2 or GL2 .

Decide using method given in “(0, 1) or (1, 0)” case.

¯

2. If L1 right-divides L2 : Compute r1 , r2 ∈ Q(x) such that (4.24) holds. Apply

Lemma 4.6.9 to compute the maximal torus T of GL .

Q— — Q— : Return GL

¯ ¯ T3 © SL3 .

(a) If T

Q— : Apply Lemma 4.6.9 to compute the appropriate subgroup

¯

(b) If T

U3 Q— , with con-

¯

T(m1 ,m2 ) ⊆ D3 ©SL3 . If T(m1 ,m2 ) = T(1,0) , then return GL

jugation as described in Item 1 or 2 of Lemma 4.5.6. In case T(m1 ,m2 ) = T(1,0) ,

¯

compute g ∈ Q(x) such that g /g = r2 . Test whether the equation

(D —¦ (D ’ r1 ’ 2r2 ))(y) = r2 g 3

108

¯

admits a Q(x)-rational solution. If no such solution exists, then return GL

U3 T(1,0) . Otherwise, test whether the equation

(D —¦ (D ’ r1 ’ 2r2 ) —¦ (D ’ 2r1 ’ r2 ))(y) = r2 g 3

¯

admits a Q(x)-rational solution. If no such solution exists, then return GL

2 1

U(1,1) T(1,0) . Otherwise, return GL U(1,1) T(1,0) .

Proof of correctness of algorithm: Corollary 4.1.3 implies that we may apply Theorem 4.1.5.

Proposition 3.1.3 and its proof provide a correspondence between right factors of L and

GL -invariant subspaces of VL . Let R1 , R2 , y2 , ξ, y3 , T, Lred and F(r1 ,r2 ) be as de¬ned in

Lemma 4.6.2 and let Ru be the unipotent radical of GL . We consider the various cases

according to Table 4.1 as follows.

• (0, 0) : Correctness in this case follows from Lemma 4.6.1.

• (0, 1) or (1, 0) : Correctness follows from Lemma 4.1.2.

Q— — Q— , correctness follows from the fact that there is only

¯ ¯

• (1, 2) : In case T

Q— —

¯

one subgroup listed in Theorem 4.1.5 for which n1 = 1, n2 = 2 and T

Q— . Suppose now that T Q— . Note that VD’r1 is the unique 1-dimensional GL -

¯ ¯

invariant subspace of VL . Furthermore, by Theorem 4.1.5, we have that [GL ]F(r1 ,r2 )

’1

is conjugate to U(1,0) · Pσ T(d1 ,d2 ) Pσ for some d1 , d2 , σ. From this fact, we see that

2

Ru is two-dimensional and acts trivially on VL /VD’r1 ; we conclude that [Ru ]F(r1 ,r2 ) =

U(1,0) . Thus, we have [GL ]F(r1 ,r2 ) = U(1,0) · T(m1 ,m2 ) ; correctness now follows after a

2 2

straightforward calculation.

Q— — Q— , correctness follows from the fact that there is only

¯ ¯

• (2, 1) : In case T

Q— — Q— .

¯ ¯

one subgroup listed in Theorem 4.1.5 for which n1 = 2, n2 = 1 and T

Q— . Note that V(D’r2 )—¦(D’r1 ) is the unique 2-dimensional GL -

¯

Suppose now that T

invariant subspace of VL . Furthermore, by Theorem 4.1.5, we have that [GL ]F(r1 ,r2 ) is

’1

conjugate to U(0,1) · Pσ T(d1 ,d2 ) Pσ for some d1 , d2 , σ. From this fact, we see that Ru is

2

two-dimensional and acts trivially on V(D’r2 )—¦(D’r1 ) ; we conclude that [Ru ]F(r1 ,r2 ) =

U(0,1) . Thus, we have [GL ]F(r1 ,r2 ) = U(0,1) · T(m1 ,m2 ) ; correctness now follows after a

2 2

straightforward calculation.

Q— — Q— , correctness follows from the fact that there is only one

¯ ¯

• (2, 2) : In case T

Q— —Q— . Suppose now

¯ ¯

subgroup listed in Theorem 4.1.5 for which n1 = n2 = 2 and T

109

Q— . Then, after considering the relevant subgroups listed in Theorem 4.1.5,

¯

that T

’1

we see that [GL ]F(r1 ,r2 ) is conjugate to U(0,0) · Pσ T(d1 ,d2 ) Pσ for some d1 , d2 , σ with

1

®

1ab

d1 > d2 . This implies that [Ru ]F(r1 ,r2 ) = clos(M ) for some M = 0 1 c ∈ U3

° »

001

®

101

with M conjugate to M0 = 0 1 0 . We claim that either a = 0 or c = 0 :

° »

001

Indeed, this claim follows easily from Lemma 4.3.4. Applying Item 1 of Lemma 4.5.1

with

Q = diag(tm1 , tm2 , t’m1 ’m2 ),

t some nonroot of unity, we now see that two of a, b, c are zero. It follows that

[Ru ]F(r1 ,r2 ) is one of the following subgroups:

±® ±® ±®

1 10u 1

0

u0

0

1 1 1

U(1,0) = 0 1 0 , U(0,0) = 0 1 0 , U(0,1) = 0 u .

1

° ° °

» » »

001

0 0

1

01 0

One checks that the following are equivalent:

1

1. [Ru ]F(r1 ,r2 ) = U(1,0)

2. y2 ∈ KLred , ξ ∈ KLred

/

3. D ’ r1 is the unique right factor of (D ’ r2 ) —¦ (D ’ r1 ), and (D + r1 + r2 ) —¦ (D ’ r2 )

is completely reducible

4. n1 = 1, n2 = 2

In case any of the above equivalent conditions holds, we see that [GL ]F(r1 ,r2 ) = U(1,0) ·

1

Q Q— , and a calculation shows that the conjugation action is as described

¯¯

T(m1 ,m2 )

in the algorithm; thus, the algorithm is correct in this case. Correctness in case

1 1

[Ru ]F(r1 ,r2 ) is equal to U(0,0) or U(0,1) is proved by similar means.

• (3, 3) : Correctness is clear in this case.

• (∞, ∞) : Correctness is clear in this case.

• (1, 1) : Suppose GL is isomorphic to either SL2 or GL2 . Then L1 fails to right-divide

L2 . Correctness then follows from Lemma 4.1.2.

110

Q— — Q— , correctness

¯ ¯

Suppose that GL is solvable, i.e., L1 right-divides L2 . In case T

follows from the fact that there is only one subgroup listed in Theorem 4.1.5 for which

Q— — Q— .

¯ ¯

n1 = n2 = 1 and T

Q— . Let A be a basis of VL such that [GL ]A ⊆ SL3 is one

¯

Suppose now that T

of the relevant subgroups listed in Theorem 4.1.5. Note that each of the solvable

subgroups listed in Theorem 4.1.5 satisfying n1 = n2 = 1 has unipotent radical either

U(1,1) , U(1,1) or U3 . In particular, [Ru ]A includes U(1,1) ; thus, there exists „ ∈ Ru such

1 2 1

®

that

1

11

2

1 ∈ U3 .

[„ ]A = 0 1

° »

00 1

Let M0 = [„ ]A , and let

®

1 a b

¯

c ∈ U3 , a, b, c ∈ Q.

= 0

M = [„ ]F(r1 ,r2 ) 1