Integrality and arithmeticity of solvable linear groups

Contents lists available atScienceDirect

Journal

of

Symbolic

Computation

www.elsevier.com/locate/jsc

Integrality

and

arithmeticity

of

solvable

linear

groups

✩

A.S. Detinko

a

,

D.L. Flannery

a

,

W.A. de

Graaf

b

a_{DepartmentofMathematics,NationalUniversityofIreland,Galway,Ireland} b_{DepartmentofMathematics,UniversityofTrento,Italy}

a

r

t

i

c

l

e

i

n

f

o

a

b

s

t

r

a

c

t

Articlehistory:

Received25October2013 Accepted10March2014 Availableonline11August2014

Keywords:

Arithmeticgroup Algorithm Algebraicgroup Lattice

We develop a practical algorithm to decide whether a finitely generated subgroupofasolvable algebraicgroupG isarithmetic. This incorporates a procedure to compute a generating set of an arithmetic subgroup of G. We also provide a simple new algorithmfor integralitytesting offinitelygenerated solvable-by-finite lineargroups over the rational field. The algorithms have beenimplementedin Magma.

©2014ElsevierLtd.All rights reserved.

1. Introduction

For K

≤

GL

(

n

,

C)

anda subringR of

C

,denote K

∩

GL

(

n

,

R

)

by KR.LetG be analgebraic group

definedover

Q

.Thispaperisconcernedwiththequestion:

Given a finitely generated subgroup H of G_Q, is H an arithmetic subgroup of G? (

∗

) Recallthat

H

≤

G_Qisanarithmeticsubgroupof

G if

itiscommensurablewith

G

Z,i.e.,

H

∩

G_Z

=

H_Z

has finiteindexinboth H and G_Z. (More generally,amatrix group issaid tobe arithmetic ifitis an arithmetic subgroupofsome algebraic

Q

-group (Segal,1983, p. 119).)The significanceof (

∗

) is evidenced by,e.g., Sarnak (2012). Decidability of(

∗

) hasnot beensettled. However, itseems to be undecidable,evenfor

G

=

SL

(

n

,

C)

(Miller,2013).Weprovethat

(

∗

)isdecidable

when G is solvable,

by givingapracticalalgorithmtoanswerthisquestion.

✩ _{TheauthorsweresupportedbyScienceFoundationIrelandgrant11/RFP.1/MTH3212.}

E-mailaddresses:alla.detinko@nuigalway.ie(A.S. Detinko),

dane.flannery@nuigalway.ie

(D.L. Flannery),

degraaf@science.unitn.it(W.A. deGraaf).

http://dx.doi.org/10.1016/j.jsc.2014.08.011

Asfurthermotivationforarithmeticitytestingweobservethatapositiveanswerenablestheuse ofarithmetic group theoryto investigatethegroup athand.Forexample,theautomorphism group ofafinitelygeneratednilpotentgroupisisomorphictoanarithmeticgroup(Segal,1983,Corollary 9, p. 122). There are polycyclic groupsthat are not isomorphic to any arithmetic group (Segal,1983, Proposition3,p. 259).Althoughwecantestwhetherapolycyclicsubgroupof

G

Qisarithmetic,testing arithmeticityofpolycyclicgroupsinthisbroadercontextisstillopen.

Our approach draws on recent progress (de Graaf and Pavan, 2009; Faccin et al., 2013) in the constructionofgeneratingsetsof

G

_Zwhen

G is

unipotentoratorus.Wecombinethosetoconstruct afiniteindexsubgroupof

G

_Zforasolvablealgebraicgroup

G—a

resultofinterestinitsownright.

WeadaptmethodsforcomputingwithSF (solvable-by-finite)lineargroups(Detinko et al.,2011, 2013a, 2013b).TodecidewhetherH is commensurablewith

G

Z,we usean algorithmfrom

Detinko

et al. (2013b) to compute the rankof an SF linear group. We alsodesign a simple newalgorithm totestwhetherafinitelygeneratedSF subgroupofGL

(

n

,

Q)

isconjugatetoa subgroupofGL

(

n

,

Z)

. Sinceintegralityisanimportantlineargroupproperty(Dixon,1971,Theorem 3.5,pp. 54–55),thisis anotherusefulresultofthepaper.Integralitytestingappearsasacomponentofearlieralgorithmsto testfiniteness(Babaiet al.,1993) andpolycyclicity(AssmannandEick,2007).

Thepaperisorganized asfollows.Section 2givesaprocedure toconstructageneratingset ofa finiteindexsubgroupof

G

Z,where

G is

solvablealgebraic.InSection3weconsidertestingfiniteness of

|

K

:

K_Z

|

for

K

≤

GL

(

n

,

Q)

.Ifthisindexisfinite,weexplainhowtofind K_Zand g

∈

GL

(

n

,

Q)

such that Kg

≤

GL

(

n

,

Z)

.Section 4 thendescribesa newalgorithmto test integralityofSF subgroups of GL

(

n

,

Q)

.OurmainalgorithmispresentedinSection5.Adiscussion ofexperimentalresultsderived froma Magma (Bosmaet al.,1997) implementationofthealgorithmsconcludesthepaper.

2. Computinganarithmeticsubgroupofasolvablealgebraicgroup

Let

G be

asolvablealgebraic

Q

-group.Inthissectionwecombineresultsfrom

de Graaf

andPavan (2009)and

Faccin

et al. (2013)toconstructageneratingsetofafiniteindexsubgroupof

G

_Z.

Thefirstresultis

Vinberg

et al. (2000,Proposition 7.2(3)).

Proposition2.1.

Suppose that G

=

A



N, where both A and N are algebraic subgroups of G, defined over

Q

. Let

ΓA

,

ΓN

be arithmetic subgroups of A and N respectively. Then

ΓA

 Γ

Nis an arithmetic subgroup of G.

From

Chevalley (1955,

Ch. 5,§3,No. 5,Propositions 20and 21)wegetthefollowing.

Proposition2.2.

Let G be connected and solvable, with Lie algebra

g

⊂ gl(

n

,

C)

. Let

n

be the ideal of

g

con-sisting of all nilpotent elements of

g

. Then there is a subalgebra

d

of

g

, consisting of commuting semisimple elements, such that

g

= d

⊕ n

. Moreover, both

n

,

d

are algebraic, and if we let N, D be the corresponding connected subgroups of G, then G

=

D



N.

Let G,

g

be asin Proposition 2.2. We suppose that

g

is givenby a basis consisting ofmatrices havingentriesin

Q

.In

de Graaf (2009)

,an algorithmthat computesbasesofsubalgebras

d

,

n

with thepropertiesof

Proposition 2.2

is given.Here we donotgo intothedetails butonly brieflyrecall thebasicsteps.

1. ComputeaCartansubalgebra

h

of

g

.

2. Let

a

1

,

. . . ,

ar beabasisof

h

,andlet

a

i

=

si

+

ni betheJordandecompositionof

a

i.

3. Let

d

be the space spanned by s1

,

. . . ,

sr and let

n

be the space spanned by n1

,

. . . ,

nr

along withthe Fitting1-component

g

1

(h)

.(The latteris the space



i≥1

[h

i

,

g]

, where

[h

i

,

g]

=

[h,

[h,

. . . ,

[h,

g

]

. . .

]]

(i factors

h

).)

Starting fromthegiven basisof

g

,we compute generators ofan arithmetic group in G_Z by the following.

GeneratingArithmetic

(

G

)

Input:abasisoftheLiealgebra

g

ofthesolvablealgebraicgroup

G.

Output:ageneratingsetforafiniteindexsubgroupof

G

_Z.

1. Computebasesof

d

and

n

asabove.Denoteby

D, N the

connectedsubgroupsof

G with

respective Liealgebras

d

,

n

.

2. Computegenerators of

N

_Z usingthealgorithmfrom

de Graaf

andPavan (2009),andgenerators of D_Zusingthe algorithmfromFaccinet al. (2013).(These algorithmstake asinputbasesof

d

and

n

respectively.)

3. Returntheunionofthetwogeneratingsetsobtainedinthepreviousstep.

We notethat

GeneratingArithmetic

iscorrect.Indeed,let H be thegroup generatedbyits output.Then

H

≤

G_Z.Ontheother hand,H is anarithmetic subgroupof

G by Proposition 2.1

.So H

hasfiniteindexin

G

Z.

GeneratingArithmetic

(

G

)

formsavitalpartofourmainalgorithm.Noticethat

G need

not be connected.Indeed, let G◦ be theconnected component ofthe identity of G. Since

|

G_Z

:

G◦_Z

|

is finite,

GeneratingArithmetic

(

G◦

)

returnsageneratingsetofanarithmeticsubgroupof

G.

3. IntegralityandGL

(

n

,

ZZZ)

-intercepts

Thissectionandthenextdependonsomeideasfrom

Babai

et al. (1993).

An element or subgroup ofGL

(

n

,

Q)

that has a conjugatein GL

(

n

,

Z)

issaid to be

integral.

Let

H

≤

GL

(

n

,

Q)

.

Lemma3.1.

(See

Babai et al., 1993, Proposition 2.3.) H is integral if and only if there exists a positive integer d such that dh

∈

Mat

(

n

,

Z)

for all h

∈

H .

Proof. Suppose that Hg

_≤

_GL

₍

_n

_,

_Z)

_{for some g}

_∈

_GL

₍

_n

_,

_Q)

_{. Then}

_m

2_H

_⊆

_Mat

₍

_n

_,

_Z)

_{wherem is any} commonmultipleofthedenominatorsoftheentriesin g and g−1_.

Supposethat

dH

⊆

Mat

(

n

,

Z)

.Let

g be

anymatrixwhosecolumnscomprisea

Z

-basis ofthelattice generatedby

dH

Z

n_{.Then g}

_∈

_GL

₍

_n

_,

_Q)

_andHg

_≤

_GL

₍

_n

_,

_Z)

_.

Call d

=

d

(

H

)

asin Lemma 3.1 a common denominator for H . As the above proof demonstrates, knowing

d

(

H

)

isequivalenttoknowing g

∈

GL

(

n

,

Q)

suchthat

H

g

_≤

_GL

₍

_n

_,

_Z)

_{.Amethodtoconstruct} d may beextractedfrom

Babai

et al. (1993,Section 2);wegiveanalgorithmthatisamodificationof thisforourpurposesinSection4.IfH is finitelygeneratedthenwecalculate g from d by meansof thefollowing(cf.

Babai

et al.,1993,Section 3).

BasisLattice

(

S

,

d

)

Input:afiniteset S

⊆

GL

(

n

,

Q)

and

d

=

d

(

H

)

,H

= 

S



. Output:abasisforthelatticegeneratedby

dH

Z

n_in

_Z

n_.

1.

L

:=

d

Z

n.

2. While

∃

h

∈

S

∪

S−1 suchthat

h

L



L

do

L

:=

the lattice generated by

L

∪

h

L

.

3. Returnabasisof

L

.

Wewrite L

≤

f H to indicatethatthesubgroup

L has

finiteindexin

H .

Proof. Suppose that H1 is integral. By Lemma 3.1, d1H1

⊆

Mat

(

n

,

Z)

for some d1

∈ Z

. Choose a transversal

{

h1

,

. . . ,

hr

}

for the cosets of H1 in H , and let d2 be a positive integer such that

d2hi

∈

Mat

(

n

,

Z)

forall

i.

Since

d

1d2H

⊆

Mat

(

n

,

Z)

,

H is

integralby

Lemma 3.1

again.

Lemma3.3.

Suppose that d is a common denominator for H , and let

L

be the lattice generated by dH

Z

n_.

(i)

L

⊆ Z

n

_⊆

1

d

L

.

(ii) H acts

by left multiplication on the (finite) set of lattices lying between

L

and 1

d

L

.

(iii) H_Zis the stabilizer of

Z

n_{under the action in (ii).}

Proof. (i)Clear:

dH

⊆

Mat

(

n

,

Z)

and

d

Z

n

_⊆

_dH

_Z

n

_⊆

_L

_.

(ii)Wehave

H

L

=

L

.Thus

H acts

onthesetoflattices

L

suchthat

L

⊆

L



⊆

1_d

L

.

(iii)Let

h

∈

H . Ifh

∈

H_Z then

Z

n

₌

_h

₍

_h−1

_Z

n

₎

_⊆

_h

_Z

n_{, so h}

_Z

n

_{= Z}

n_{. Conversely, ifh}

_Z

n

_{= Z}

n _then

everyentryin

h is

aninteger.

Proposition3.4.

H is integral if and only if H

_Z

≤

f H .

Proof. Thisisaconsequenceof

Lemmas 3.2 and

3.3.

Thefollowingprocedureconstructs H_Z ifH is finitelygeneratedand

d

(

H

)

isknown.

IntegralIntercept

(

S

,

d

)

Input:afiniteset

S

⊆

GL

(

n

,

Q)

and

d

=

d

(

H

)

,

H

= 

S



. Output:ageneratingsetofH_Z.

1.

L

:=

the lattice generated by

BasisLattice

(

S

,

d

)

. 2.

Λ

:=

the set of all lattices

L

suchthat

L

⊆

L



⊆

1_d

L

.

3. Returnageneratingsetforthestabilizerof

Z

n undertheactionof

H on

Λ

.

Remark3.5. Step(3)maybecarriedout usingstandardalgorithms forfinitepermutation groupsto obtainatransversalfor H_Z in H , thenwritingdownSchreiergenerators.More practicalapproaches are possiblein specialsituations; say forpolycyclic H (e.g., arithmetic H

≤

G_Q andsolvable G). In thatcaseanalgorithmcanbebasedonanorbit-stabilizer approach.Thisissimilartothealgorithm describedin

Laue

et al. (1984).Such analgorithmenumeratestheorbitof

Z

n underactionby

H ,

in theprocessobtaininggeneratorsofthestabilizer.Theefficiencyofthisapproachdependsheavilyon orbitsize.

4. Integralityofsolvable-by-finitesubgroupsofGL

(

n

,

Q

Q

Q)

We next describe how to test integrality of a finitely generated SF subgroup of GL

(

n

,

Q)

, and computeacommondenominatorifthegroupisintegral.

Let H

= 

h1

,

. . . ,

hr



≤

GL

(

n

,

Q)

.We have H

≤

GL

(

n

,

R

)

where R

=

1_b

Z

= {

a

/

bi

|

a

∈ Z,

i

≥

0

}

for

some positive integer

b determined

by theentries inthe hi andh−i1.Forany prime p

∈ Z

not

di-viding

b,

reductionmodulo p of matrixentriesdefinesacongruencehomomorphism

ϕ

p

:

GL

(

n

,

R

)

→

GL

(

n

,

p

)

. If H is SF and p

=

2 then Hp

=

ker

ϕ

p

∩

H is torsion-free andunipotent-by-abelian (see Dixon, 1985, Lemma 9, or Detinko et al., 2011, Section 2.2.1). Assume that p has been so chosen whenever

H is

SF.

Denotetheunipotent radicalof K

≤

GL

(

n

,

Q)

by

U

(

K

)

.Replace K if necessarybya conjugatein block triangularformwithcompletelyreduciblediagonal blocks.If

π

denotes projection of K onto

Lemma4.1.

The following are equivalent.

(i) H is

integral.

(ii)

π

(

H

)

is integral.

(iii)

π

(

Hp

)

is integral.

Proof. By

Babai

et al. (1993,Theorem 2.4),afinitelygeneratedsubgroup K of GL

(

n

,

Q)

isintegral if andonlyif

{

tr

(

x

)

|

x

∈

K

}

⊆ Z

.Thus(i)

⇔

(ii).Since

|

π

(

H

)

:

π

(

Hp)

|

= |

H

:

HpU

(

H

)

|

<

∞

,

Lemma 3.2

gives(ii)

⇔

(iii).

Denotethecharacteristicpolynomialof

h

∈

GL

(

n

,

C)

by

χ

h

(

X

)

.

Proposition4.2.

(Cf. Lemma 8 and Theorem 9 of

Assmann and Eick, 2007.) Suppose that each element of H is equal to hm1

1

· · ·

h

mr

r for some mi

∈ Z

. Then H is integral if and only if each hiis integral, i.e., χhi

(

X

)

∈ Z[

X

]

and det

(

hi)

= ±

1 for1

≤

i

≤

r.

Proof. If

χ

hi

(

X

)

∈ Z[

X

]

has constant term

±

1 for all i then



hi



⊆ {



n−1

j=0ajhij

|

aj

∈ Z}

. So there

exist positive integers di, 1

≤

i

≤

r, such that di



hi



⊆

Mat

(

n

,

Z)

. Hence d

=

d1

· · ·

dr is a common

denominatorfor

H .

If H is polycyclicwithpolycyclicsequence

(

h1

,

. . . ,

hr),then H satisfies thehypothesisof

Proposi-tion 4.2.Anygeneratingsetof H is similarlysuitablewhen

H is

abelian.

Lemma4.3.

Suppose that H

≤

K

≤

GL

(

n

,

Q)

and the normal closure HK_{is finitely generated abelian. Then} HK_{is integral if and only if each h}

iis integral.

Proof. If the hi are integral then Proposition 4.2 guaranteesthat H is integral. Since HK isfinitely

generated, there are x1

,

. . . ,

xt

∈

H and y1

,

. . . ,

y

t

∈

K such that HK

= 

xiyi

:

1

≤

i

≤

t



. By

Proposi-tion 4.2again,

H

K _isintegral.

Lemma4.4.

Suppose that H is SF and Y is a normal generating

set for Hp(p

=

2),

i.e., H

p

= 

Y



H. Then H is integral if and only if each element of Y is integral.

Proof. If each element of

Y is

integral then thesameholds for

π

(

Y

)

. Hence thefinitelygenerated abeliangroup

π

(

Hp)

= 

π

(

Y

)



π(H)isintegralby

Lemma 4.3

.Theclaimnowfollowsfrom

Lemma 4.1

. We compute

Y from

apresentation

P

of

ϕ

p(H

)

≤

GL

(

n

,

p

)

on

ϕ

p(h1

),

. . . ,

ϕ

p(hr)usingthe func-tion

NormalGenerators

asin

Detinko

et al. (2011, Section 3.2): thisevaluates therelatorsof

P

, replacing

ϕ

p(hi) everywhere by hi, 1

≤

i

≤

r. Proposition 4.2and Lemma 4.4consequently provide

ourstraightforwardproceduretotestintegralityof

H .

IsIntegralSF

(

S

)

Input:afinitesubset

S of

GL

(

n

,

Q)

suchthat

H

= 

S



isSF. Output:

true

ifH is integral;

false

otherwise.

1. Y

:= NormalGenerators(

S

)

.

2. Ifeveryelementof

Y is

integralthenreturn

true

; elsereturn

false

.

Remark4.5.When H is finitewe have Hp

=

1,so

IsIntegralSF

always returns

true

forsuch

A major class of SF groups is PF (polycyclic-by-finite) groups. According to Assmann and Eick (2007, Corollary 10), one may test integrality of a PF subgroup H of GL

(

n

,

Q)

after computing a polycyclicsequence andtransversalfora finiteindexpolycyclic normalsubgroupof H . Bycontrast,

IsIntegralSF

doesnotrequireH to bePFandjusttestsintegralityofseveralmatricesinHp.

ToconjugateanintegralSFgroup

H into

GL

(

n

,

Z)

,ortocomputegeneratorsofitsfiniteindex sub-group H_Zvia

IntegralIntercept

,wemustknow

d

(

H

)

.Themethodbelowtofindthiscommon denominatorisasimplificationof

Babai

et al. (1993,p. 120)forSFinput.

Firstdetermineablockuppertriangularconjugateof

H with

completelyreduciblediagonalblocks; this maybe done as in Detinko et al. (2013b,Section 4.2). Let

{

a1

,

. . . ,

am

}

⊆

π

(

H

)

be a basis of

the envelopingalgebra



π

(

H

)



Q. Ifc is a common multiple ofthe denominators of entries inthe

ai then d1

:=

c det

(

[

tr

(

aiaj)

]

1≤i,j≤n)

=

d

(

π

(

H

))

. Define ui

=

hi

−

π

(

hi) and vi

=

h−_i1

−

π

(

h−_i1

)

. Let d2

=

en−1 where

e is

acommonmultipleofdenominatorsofentriesinthe

u

i and vi.Eachelement

of H is asumofterms x

=

π

(

g1

)

w1

· · ·

π

(

gk)wkwhere gj

∈

H and wj

=

1 orsome

u

i or vi.Since

π

(

h

)

uj and

π

(

h

)

vj arenilpotent,ifthereareatleast

n occurrences

of

u

jsand vjs inx then x

=

0.

Thus

dH

⊆

Mat

(

n

,

Z)

where

d

=

dn₁d2.Notethatforcompletelyreducible H (e.g., H is finite),

d

(

H

)

=

d

(

π

(

H

))

=

d1.

5. Arithmeticitytestinginsolvablealgebraicgroups

Inthissectionweapplyresultsof

Detinko

et al. (2013b)andtheprevioussectionstotestwhether afinitelygeneratedsubgroup

H

≤

G_Qofasolvablealgebraicgroup

G is

arithmetic.

DenotetheHirschnumberofa group K with finitetorsion-freerankby h

(

K

)

.Finitelygenerated SFsubgroupsofGL

(

n

,

Q)

havefinitetorsion-freerank(Detinkoet al.,2013b,Proposition 2.6). Lemma5.1.

Let L be a finitely generated SF subgroup of

GL

(

n

,

Q)

, and let K

≤

L. Then K

≤

f L if and only if

h

(

K

)

=

h

(

L

)

.

Proof. ThisfollowsfromProposition 2.3andCorollary 3.3of

Detinko

et al. (2013b).

Corollary5.2.

H is an arithmetic subgroup of G if and only if H is integral and

h

(

H

)

=

h

(

G_Z

)

. In particular, H

≤

G_Zis arithmetic if and only if h

(

H

)

=

h

(

G_Z

)

.

Proof. This is immediate from Proposition 3.4 and Lemma 5.1, using that h

(

H

)

=

h

(

H_Z

)

when

H_Z

≤

f H .

Remark5.3. If G is a unipotent

Q

-group then we have a more general statement (Detinko et al., 2013b, Lemma 3.7): H

≤

G_Q is arithmetic in G if andonly if h

(

H

)

=

h

(

G_Q

)

, i.e., h

(

H

)

equals the dimensionof

G.

Fornon-unipotentsolvable(evenabelian)

G this

isnottrue;

G

Qneednotevenhave finiterank.

Wenowstateourarithmeticitytestingalgorithm.Thisusestheprocedure

HirschNumber

from

Detinko et al. (2013b, Section 4.4), which returns h

(

K

)

fora finitely generated SF subgroup K of

GL

(

n

,

Q)

.

IsArithmeticSolvable

(

S

,

G

)

Input:afinitesubset S of GQ,

G a

solvablealgebraicgroup. Output:

true

ifH

= 

S



isarithmetic;

false

otherwise. 1. If

IsIntegralSF

(

S

)

= false

thenreturn

false

. 2. T

:= GeneratingArithmetic(

G

)

.

3. If

HirschNumber

(

S

)

= HirschNumber(

T

)

thenreturn

false

; elsereturn

true

.

Table 1

Runningtimes(inseconds)ofthestepsinIsArithmeticSolvable.

n dimg(n) h(G(n)Z) IsInt(S) T:= GA(G(n)) h(S) h(T)

2 6 5 0.12 0.05 0.51 0.68

3 15 14 0.29 0.19 2.10 2.28

4 28 27 0.86 1.12 11.28 12.77

Remark5.4.Steps(1)and(3)arejustifiedby

Corollary 5.2

.If

G is

unipotentthen H is integral(Segal, 1983,Lemma 2,p. 111),andstep(1)canbeomitted.

6. Practicalperformance

We have implemented our algorithms in Magma. The implementation relies on the package

‘Infinite’ (Detinko et al.,2013c) andproceduresavailableat

de Graaf (2013)

.Althoughthemaingoal hasbeentoestablishthatarithmeticityisdecidable,inthissectionweshowthatouralgorithmscan beappliedinpracticetonontrivialexamples.

One ofthemainbottlenecks of

GeneratingArithmetic

liesinthecomputation ofthetorus

part.Let

g

= d

⊕ n

and

D be

asin

Proposition 2.2

.Thefirststepofthealgorithmgivenin

Faccin

et al. (2013)forcomputinggeneratorsof

D

Zconstructstheassociativealgebra

A with

unitygeneratedby

d

. Subsequently A is writtenasadirectsumofnumberfields

Q(

α

)

.Foreachsuch field,generators of the unit group of

Z[

α

]

arecomputed. Butthe algorithm forthistask (asimplemented in Magma) becomes extremelydifficultto applyin practiceifthedegreeof

Q(

α

)

is toolarge,say30 or more. Ontheother hand,ifall fieldsthat occurare equalto

Q

thenthecomputation ofgenerators of D_Z

istrivial.Forthesereasonsweconstructedtestexampleswherethefieldextensionshavedegree

≤

2 (andsomeextensionsofdegree2 dooccur).Thisconstructionworksasfollows.FirstwedefineaLie algebra

g(

n

)

⊂ gl(

2n

,

C)

,

n

≥

2.Forthiswedividethematricesof

gl(

2n

,

C)

into2

×

2 blocks.OurLie algebra

g(

n

)

isthedirectsum

g(

n

)

= t

⊕ n

oftwosubalgebras.Thesubalgebra

t

hasdimension

n,

and the

ith

basiselementhasonits

ith

diagonalblockthematrix



0 1 2i

−

1 0



andzeroselsewhere.

Let

e

i,jbetheelementarymatrixwith1 inposition

(

i

,

j

)

andzeroselsewhere.Then

n

isspanned

bythe

e

i,jwhere

(

i

,

j

)

appearsinablockabovethediagonal.Sodim

n

=

4



n

2



.

The Lie algebra

g(

n

)

is algebraic,and welet G

(

n

)

<

GL

(

2n

,

C)

be the connectedalgebraic group withLiealgebra

g(

n

)

.

Nowlet

m be

a2n

×

2n matrixproducedbythefollowingrandomizedconstruction.Theentriesof

m are randomlyanduniformlychosenfrom

(

0

,

0

,

1

)

(sowemakeittwiceaslikelythata0 ischosen). Wecontinuetoproducematriceslikethisuntilthedeterminantisnot0 or

±

1.

Set



G

(

n

)

=

mG

(

n

)

m−1_{.Thisisanalgebraic groupwithLiealgebra}

_m

_g(

_n

₎

_m−1_{.The Liealgebra has} basis Bn consisting of all mum−1, for u in the above constructed basis of

g(

n

)

. Let g1

,

. . . ,

gr be

generatorsofanarithmeticsubgroupof

G

(

n

)

_Z.For1

≤

i

≤

r let kibechosenrandomlyanduniformly

from

{

1

,

2

}

.Then

S

= {(

mgim−1

)

ki

|

1

≤

i

≤

r

}

generatesasubgroupof



G

(

n

)

Q(andnotethatitalways

is arithmetic).The inputon whichwe testedour implementationof

IsArithmeticSolvable

is

theset

S,

togetherwiththealgebraicgroup



G

(

n

)

givenbyitsLiealgebra,inturngivenbyitsbasis Bn.

In Table 1 we report on the running times of our algorithm with the input as above for n

=

2

,

3

,

4. Allexperiments were performed on a 3.16 GHzmachine running Magma V2.19-9. The first three columns ofTable 1list n, dim

g(

n

)

,andthe Hirschnumber of



G

(

n

)

_Z. The other columnslist running times of

IsIntegralSF

(

S

)

, T

:= GeneratingArithmetic(

G

(

n

))

,

HirschNumber

(

S

)

and

HirschNumber

(

T

)

.

From

Table 1

we seethat ouralgorithm isefficientenough tohandlequite nontrivialexamples. Moreover,thebulkoftherunningtimegoesintocomputingHirschnumbers.Ofcourse,thisdepends onourparticulartestexample.Ifwetookexampleswhereitisdifficulttocomputegeneratorsof D_Z,

thenamuchlargerproportionofthetimewouldgointocomputinganarithmeticsubgroup.However, thecurrent implementationis rathersensitive torandomness ofthe input. Occasionallyit happens that generators in T have coefficientswith many digits (up to 10, forexample). This then causes problemswhencomputingtheHirschnumber.So wehaveaveragedtimesover 50 runsinorderto dampentheeffectsofrandomnessoftheinput.

References

Assmann,B.,Eick,B.,2007.Testingpolycyclicityoffinitelygeneratedrationalmatrixgroups.Math.Comput. 76,1669–1682. Babai,L.,Beals,R.,Rockmore,D.N.,1993.Decidingfinitenessofmatrixgroupsindeterministicpolynomialtime.In:Proc.of

InternationalSymposiumonSymbolicandAlgebraicComputation.ISSAC ’93.ACMPress,pp. 117–126.

Bosma,W.,Cannon,J.,Playoust,C.,1997.TheMagmaalgebrasystem.I.Theuserlanguage.J.Symb.Comput. 24(3–4),235–265. Chevalley,C.,1955.ThéoriedesGroupesdeLie,TomeIII.ThéorèmesgénérauxsurlesalgèbresdeLie.Hermann,Paris. deGraaf,W.,2009.ConstructingalgebraicgroupsfromtheirLiealgebras.J.Symb.Comput. 44,1223–1233.

deGraaf,W.,2013.

http://www.science.unitn.it/~degraaf/arith/arithgrp.m

.

deGraaf,W.,Pavan,A.,2009.Constructingarithmeticsubgroupsofunipotentgroups.J.Algebra 322,3950–3970.

Detinko,A.S.,Flannery,D.L.,O’Brien,E.A.,2011.AlgorithmsfortheTitsalternativeandrelatedproblems.J.Algebra 344,397–406. Detinko,A.S.,Flannery,D.L.,O’Brien,E.A.,2013a.Recognizingfinitematrixgroupsoverinfinitefields.J.Symb.Comput. 50,

100–109.

Detinko,A.S.,Flannery,D.L.,O’Brien,E.A.,2013b.Algorithmsforlineargroupsoffiniterank.J.Algebra 393,187–196.

Detinko,A.S.,Flannery,D.L.,O’Brien,E.A.,2013c.

http://magma.maths.usyd.edu.au/magma/

.

Dixon,J.D.,1971.TheStructureofLinearGroups.VanNostrandReinhold,London.

Dixon,J.D.,1985.Theorbit-stabilizerproblemforlineargroups.Can.J.Math. 37(2),238–259.

Faccin,P.,deGraaf,W.,Plesken,W.,2013.Computinggeneratorsoftheunitgroupofanintegralabeliangroupring.J. Alge-bra 373,441–452.

Laue,R.,Neubüser,J.,Schoenwaelder,U.,1984.AlgorithmsforfinitesolublegroupsandtheSOGOSsystem.In:Computational GroupTheory.Durham,1982.AcademicPress,London,pp. 105–135.

MillerIII,C.F.,2013.Personalcommunication.

Sarnak,P.,2012.Notesonthinmatrixgroups.

http://arxiv.org/abs/1212.3525

.

Segal,D.,1983.PolycyclicGroups.CambridgeUniversityPress,Cambridge.

Vinberg,E.B.,Gorbatsevich,V.V.,Shvartsman,O.V.,2000.DiscretesubgroupsofLiegroups.In:LieGroupsandLieAlgebras,II. Encycl.Math.Sci.,vol. 21.Springer,Berlin,pp. 1–123,217–223.