## New York Journal of Mathematics

New York J. Math. 20(2014) 1175–1202.

## Small generators for S-unit groups of division algebras

### Ted Chinburg and Matthew Stover

To H. W. Lenstra, Jr.

Abstract. Letkbe a number field, suppose thatBis a central simple
division algebra over k, and choose any maximal order D of B. The
object of this paper is to show that the group D^{∗}S of S-units of B is
generated by elements of small height onceScontains an explicit finite
set of places of k. This generalizes a theorem of H. W. Lenstra, Jr.,
who proved such a result whenB=k. Our height bound is an explicit
function of the number field and the discriminant of a maximal order in
B used to define itsS-units.

Contents

1. Introduction 1176

2. Notation and definitions 1179

3. Absolute values and heights 1180

4. The main result 1185

5. Explicit bounds 1192

5.1. A maximal orderDand an archimedean setX 1192

5.2. The constantmX 1193

5.3. Choices forT1,T5,T3 and T_{3}^{0} 1195
5.4. Topological generators and the constantsT_{2} and T_{4} 1196

5.5. An upper bound onT6 1197

5.6. The explicit bound 1198

6. An explicit example 1199

6.1. S={∞} 1199

6.2. S={∞} ∪ {`_{i}}^{h}_{i=1} for a finite set{`_{i}}^{h}_{i=1} of odd primes 1200

Received November 7, 2014.

2010Mathematics Subject Classification. 17A35, 20H10, 22E40, 11F06, 16H10, 16U60, 20F05, 11H06.

Key words and phrases. Division algebras,S-unit groups,S-arithmetic lattices, heights on algebras, generators forS-unit groups, geometry of numbers.

Chinburg partially supported by NSF Grant DMS 1100355.

Stover partially supported by NSF RTG grant DMS 0602191 and NSF grant DMS 1361000.

ISSN 1076-9803/2014

1175

References 1201

1. Introduction

Letkbe a number field, suppose thatB is a central simple division algebra
overk, and choose any maximal order Dof B. The object of this paper is
to show that the groupD^{∗}_{S} ofS-units ofk is generated by elements of small
height once S contains an explicit finite set of places of k.

A result of this kind was shown by Lenstra in [7] when B is k itself. In
this case, G is the multiplicative group Gm and the notion of height is the
classical one. Lenstra showed that once S is sufficiently large, the group
Gm(O_{k,S}) = O_{k,S}^{∗} is generated by elements whose log heights are bounded
by

1

2log|d_{k/Q}|+ logm_{S}+r_{2}(k) log(2/π),

whered_{k} is the discriminant ofk,m_{S} is the maximal norm of a finite place
in S, and r2(k) is the number of complex places of k. One version of our
results is the following.

Theorem 1.1. Suppose B is a central simple division algebra of dimension
d^{2} over a number field k, n = [k : Q], and s is the number of real places
of k over which B ramifies. Then there is a maximal order D of B with
discriminant d_{D} and functions f1(n, d) and f2(n, d) of integer variables n
and dfor which the following is true. Define

e= 2n d(2n−s).

Suppose that S is a finite set of places of k containing all the archimedean places and that S contains all finite places v such that

Norm(v)≤f1(n, d)d^{e}_{D}.

Let mSf be the maximum norm of a finite place in S. Then e≤1 and the
group Γ_{S} of S-units in B with respect to the order D is generated by the
finite set of elements of height bounded above by

f2(n, d)mSf d^{e}_{D}.

See the remarks at the end of§5.6for explicit expressions forf1(n, d) and f2(n, d). In many cases (e.g., when B is a number field) we have

(1) f_{1}(n, d) =d^{nd}
2

π
_{n−s/2}^{ndr}^{2}

2√ 2 π

!_{2n−s}^{nds}

(2) f_{2}(n, d) =d^{nd+n+s}((d−1)!)^{n−s}2^{s}^{d}

2−2d−4 2

2 π

_{n−s/2}^{ndr}^{2}
2√

2 π

!_{2n−s}^{nds}

SMALL GENERATORS FOR 1177

wherer_{2} is the number of complex places ofkand all other notation is from
the statement of Theorem1.1. Thus, whenB is a number field this exactly
reproduces Lenstra’s bound.

WhenSis empty, even for a number fieldkone does not expect to be able
to generate the unit groupO^{∗}_{k}by elements whose log heights are bounded by
a polynomial in log|d_{k/Q}|. For example, the Brauer–Siegel Theorem implies
that ifkis real quadratic of class number 1, then the log height of a generator
of O^{∗}_{k} is greater than cd^{1/2−}_{k/}

Q for all >0, where c >0 depends only on
. However, to our knowledge there is no unconditional proof, even in the
case of real quadratic fields, that there cannot be an upper bound on the
log heights of generators forO^{∗}_{k} that is polynomial in log|d_{k/}_{Q}|.

To develop our counterpart of Lenstra’s results, we must first define an
intrinsic notion of height for elements of B^{∗}. The role of |d_{k/}_{Q}| is played
by the discriminant d_{D} of an O_{k}-order D in B that is used to define the
S-integrality of points of G over k. The height bound we produce applies
to all choices of DonceS is sufficiently large. It implies, in particular, that
there is a maximal order Din B such that when S is sufficiently large (in
an explicitly defined sense), one can generate the points of Gover Ok,S by
elements whose log heights are bounded by ^{1}_{2}log|∆_{k/Q}|+ logm_{S}+µwhere
µ depends only only the degree of B overQ. See [8], [9], [3] and references
therein for work on heights on quaternion algebras.

To show that our bounds remain quite effective outside the number field setting, in§6we apply our results to Hamilton’s quaternion algebra overQ.

The main result is the following.

Theorem 1.2. Let B be Hamilton’s quaternion algebra over Q, that is, the
rational quaternion algebra with basis {1, I, J, IJ} such that I^{2} =J^{2} =−1
and IJ=−J I. LetD be the maximal order

Z

1, I, J,1 +I +J+IJ 2

and S={∞, `_{1}, . . . , `h} be a set of places containing the archimedean place

∞ and any set {`_{i}}^{h}_{i=1} of distinct odd primes. Then the unit group D^{∗}_{S}
is generated by the finite set of elements with reduced norm contained in
{1, `_{1}, . . . , `_{h}}.

As in Lenstra’s case, Theorem 1.1leads to an algorithm for finding gen-
erators forO^{∗}_{k,S}. After embedding B into a real vector space, the algorithm
is reduced to the classical problem of enumerating lattice points of bounded
norm. That an algorithm exists to generateS-integral points of an algebraic
group over a number field, with no assumptions onS, was known by work of
Grunewald–Segal [5], [6]. Unlike their algorithm, ours is primitive recursive,
which answers a question raised in [6].

Lenstra went on to show that his algorithm, together with linear alge- bra, can be used to give a deterministic algorithm for finding generators for

the unit group O^{∗}_{k} with running-time O_{}(|d_{k/Q}|^{3/4+}). The output of the
algorithm consists of the digits of a set of generators. Answering a ques-
tion raised by Lenstra, Schoof recently announced an improvement of this
run-time to O(|d_{k/}_{Q}|^{1/2+}). By the discussion of the Brauer–Siegel theo-
rem above, one expects the length of the output may be on the order of

|d_{k/}_{Q}|^{1/2−} in some cases, but the input to the problem, namely enough in-
formation to specify k, will in general be much shorter. For instance, a real
quadratic field k can be specified by giving its discriminant d_{k/}_{Q}, and the
number of bits necessary to specify d_{k/}_{Q} is proportional to log|d_{k/}_{Q}|.

Lenstra’s algorithm for finding generators forO_{k}^{∗}makes essential use of the
fact thatO_{k,S}^{∗} is abelian, and this is not the case whenB is noncommutative
and D^{∗}_{S} is infinite. Consequently, we do not know a counterpart of this
algorithm for producing generators in the general case.

We also note that there is a spectral approach to finding small generators
for groups acting on symmetric spaces. For example, if V is a compact
quotient of a rank one symmetric space other than hyperbolic 2- or 3-space,
Burger and Schroeder [1] showed that one can bound the diameter of V
from above in terms of its volume andλ_{1}(V)diam(V) in terms of log vol(V).

One can use this to bound the length (in the Riemannian metric on V) of
a generating set. As noted in [1], these results fail for hyperbolic 2- and 3-
space, though Peter Shalen informed us that one could prove an analogous
theorem for arithmetic Fuchsian and Kleinian groups assuming Lehmer’s
conjecture. However, the problem we solve in this paper is of a different
kind, even where a result like that of [1] holds. Our methods find explicit
matrix generators with small entries, and it is not at all clear that generators
that are short in an associated Riemannian metric have representatives in
GL_{n}with small entries. It would be interesting to see if spectral methods for
S-arithmetic subgroups of reductive groups could produce generators that
have small height.

The main tool for producing small generators forO_{k,S}^{∗} onceSis sufficiently
large is Minkowski’s lattice point theorem. This determines elements of B^{∗}
which can be shown to beS-integral by careful consideration of the constants
required to apply Minkowski’s theorem. In particular, the assumption that
B is a division algebra is crucial, and it would be interesting to extend our
results to unit groups of arbitrary central simple algebras. The reason we
cannot work with a general central simple algebra is because Minkowski’s
lattice point theorem returns a nonzero element of the algebraB. We prove
that it is S-integral. However, it might not be invertible in B ifB is not a
division algebra. Given that SL_{n}(Z) is generated by elementary matrices,
which certainly have small height, we expect such a result to hold. It appears
to us that it is a deep problem to extend such height results to generators for
the S-integral points of more general linear algebraic groups over number
fields.

SMALL GENERATORS FOR 1179

2. Notation and definitions

Let k be a number field with ring of integers O_{k} and [k : Q] = n. We
denote byV∞(resp.Vf) the set of archimedean (resp. finite) places ofk. Let
B be a division algebra over kwith degreedand letD⊂B be anO_{k}-order
in B. The multiplicative group of units in a ring R will be denoted R^{∗}.
For each place v ofk and anyk-algebra or O_{k}-moduleA, let A_{v} denote the
associated completion at v.

Define a norm on B_{v}^{∗} by

(3) Normv(xv) = Norm_{k}_{v}_{/}_{Q}_{p(v)}(det(xv yBv)),

where p(v) is the place of Q under v and x_{v} y B_{v} is the k_{v}-linear endo-
morphism of Bv induced by left xv-multiplication. If detv :Bv → kv is the
reduced norm, then

(4) det(x_{v}yB_{v}) = det_{v}(x_{v})^{d}.

The idele group J(B) is the restricted direct product Q0

vB_{v}^{∗} of the B_{v}^{∗}
with respect to the groupsD^{∗}v. For x=Q

vxv∈J(B), define

(5) Norm∞(x) = Y

v∈V∞

Normv(xv)

(6) Normf(x) = Y

v∈V_{f}

Normv(xv).

We view these norms as elements of the idele groupJ(Q) ofQin the natural
way. Let | |:J(Q)→R>0 be the usual norm. By the product formula,
(7) |Norm_{∞}(x)|=|Norm_{f}(x)|^{−1}

for all x∈B^{∗}.

LetS be a finite set of places of kcontainingV∞. SetSf =SrV∞, and consider the groups

B_{R}^{∗} = Y

v∈V∞

B^{∗}_{v}

B_{S}^{∗}_{f} = Y

v∈S_{f}

B_{v}^{∗} ⊂ B_{f}^{∗}= Y

v∈V_{f}
0B_{v}^{∗}

and the product

(8) B_{S}^{∗} =Y

v∈S

B^{∗}_{v} =B_{R}^{∗} ×B^{∗}_{S}_{f} ⊂J(B) =B_{R}^{∗} ×B^{∗}_{f}.

LetG_{S} be the subgroup ofB_{S}^{∗} that satisfies the product formula, so

(9) GS=

(x, β)∈B_{S}^{∗} : |Norm_{∞}(x)|=|Norm_{f}(β)|^{−1} .

IfOk,S denotes theS-integers ofk, i.e., those elements ofkwhich lie inOk,v

for all v /∈S, then the S-order of B associated withD is

(10) DS=O_{k,S}⊗_{O}_{k}D.

The group of invertible elements ofDS will be denoted Γ_{S} and is called the
group ofS-units of D.

We define a topology onG_{S} by its natural embedding intoB_{S}^{∗}. The image
of Γ_{S} inG_{S} under the diagonal embedding is a discrete subgroup. We have
diagonal embeddings ΓS → B^{∗}_{S} and ΓS → Q

v6∈SD^{∗}v, and the product of
these embeddings is the natural diagonal embedding of ΓS intoJ(B).

For any element

α= Y

v∈V_{f}

αv ∈B_{f}^{∗},

there is a right-D-module

(11) αD=B∩

Y

v∈V_{f}

αvDv

,

where B is diagonally embedded in B_{f}. For α ∈ D, the index of αD inD
equals |Norm_{f}(α)|^{−1}. We also have the left-D-module

(12) Dα^{−1}={x∈B : x(αD)⊆D}.

3. Absolute values and heights

In this section we define absolute values on the completions Bv of B.

These will be used to define our notion of height for elements of B^{∗}. We
point the reader to [8], [9], [3] and references therein for earlier work on
heights for quaternion algebras over number fields.

For each place v of k there is a division algebra Av over kv such that
B_{v} =k_{v}⊗_{k}Bis isomorphic to a matrix algebra M_{m(v)}(A_{v}). The dimension of
Av overkvisd(v)^{2}for some integerd(v) such thatd(v)m(v) =d=√

dim_{k}B.

Note thatA_{v} and B_{v} have center isomorphic tok_{v}.

For finite v let Ov be the ring of integers of kv. We fix isomorphisms
ρ_{v} :B_{v} →M_{m(v)}(A_{v}) such that for almost all finitev,A_{v} =k_{v} andρ_{v}(Dv) =
M_{m(v)}(Ov). Let Nv :Av→kv be the reduced norm. Then Nv(r) =r^{d(v)} for
any r∈k_{v} ⊆A_{v}.

For all places v of k, let | |_{v} be the usual normalized absolute value on
kv. We extend | |_{v} to an absolute value on Av by |α|_{v} = |N_{v}(α)|^{1/d(v)}_{v} for
α ∈ A_{v}. This absolute value is clearly multiplicative and restricts to the
usual absolute value on the centerkv ofAv.

Suppose v is nonarchimedean. There is a unique maximal order U_{v} in
Av, namely the set of α ∈ Av such that |α|_{v} ≤ 1. When Av 6= kv, Uv

is a noncommutative local ring, and it is O_{v} when A_{v} = k_{v}. The unique
maximal two-sided ideal of U_{v} is the set P_{v} of α ∈ A_{v} for which |α|_{v} <1.

There is an element λv of Pv such that Pv = Uvλv = λvUv; such λv are
called prime elements by Weil in [12, Def. 3, Chap. I.4]. By [12, Prop. 5,
Chap. I.4], N_{v}(λ_{v}) is a uniformizer in k_{v}. Thus |λ_{v}|_{v} = |N_{v}(λ_{v})|^{1/d(v)}_{v} =
(#k(v))^{−1/d(v)} wherek(v) is the residue field ofvand so the range of | |_{v} on

SMALL GENERATORS FOR 1181

A^{∗}_{v} is (#k(v))^{1/d(v)})^{Z}. The set of α ∈A^{∗}_{v} such that |α|_{v} ≤(#k(v))^{−t/d(v)} is
exactlyP_{v}^{t}. This implies that|α+β|_{v} ≤max(|α|_{v},|β|_{v}) for everyα, β∈Av.

We now prove a simple lemma.

Lemma 3.1. With notation as above, suppose that v is archimedean. For
allm-element subsets{α_{i}}^{m}_{i=1}⊂Av,

(13)

m

X

i=1

αi

v

≤m^{[k}^{v}^{:}^{R}^{]−1}

m

X

i=1

|α_{i}|_{v}.

Proof. If v is complex, then Av = kv ∼= C and | |_{v} is the square of the
usual Euclidean absolute value. The result reduces to the Cauchy–Schwarz
inequality. Ifv is real andA_{v} =k_{v} ∼=R, the lemma is again clear.

The final case is when v is real and Av is Hamilton’s quaternions H =
R+RI+RJ+RIJ whereI^{2}=J^{2} =−1 andIJ =−J I. Here,

|a+bI+cJ +dIJ|_{v} = (a^{2}+b^{2}+c^{2}+d^{2})^{1/2}.

We can view this as the Euclidean length in R^{4} of the vector (a, b, c, d). It
is clear from the triangle inequality that the optimal constant in this case is

again 1. This proves the lemma.

Recall that for each placev of kwe fixed an isomorphism
ρ_{v} :B_{v} →M_{m(v)}(A_{v}).

For each v and each γ ∈ B_{v}^{∗}, let γ^{i,j}(v) denote the (i, j)-component of the
m(v)×m(v) matrix ρv(γ) ∈ GL_{m(v)}(Av). Define |γ|_{v} = maxi,j|γ^{i,j}(v)|_{v}.
EmbedB intoB_{v} =k_{v}⊗_{k}B in the natural way. Then theheight ofγ ∈B^{∗}
is defined by

(14) H(γ) = Y

v∈V

max{1,|γ|^{d(v)}_{v} },

where the product is over the set V =V∞∪V_{f} of all places of k. From the
definition of| |_{v} we see that

(15) H(γ) = Y

v∈V

max

1, max

i,j |N_{v}(γ^{i,j}(v))|_{v}

.

For anyS and any positive real numberx, the set
(16) BH_{S}(x) ={γ ∈Γ_{S} : H(γ)≤x}

of S-units of D with height bounded by x is finite. Indeed, bounding the
nonarchimedean height bounds the denominator of each matrix entry under
the image of everyρv, so the set ofγ ∈ΓS with bounded height is contained
in a lattice in B_{R}. Bounding the archimedean height immediately implies
finiteness.

We end this section by proving some inequalities we will need later con- cerning the behavior of absolute values on taking products and inverses of elements of Bv.

Lemma 3.2. Suppose v is a finite place of k and fix an isomorphism
ρv :Bv →M_{m(v)}(Av).

Let det_{v} :B_{v} →k_{v} be the reduced norm. For y, y^{0} ∈B_{v}:
1. |yy^{0}|_{v} ≤ |y|_{v}|y^{0}|_{v}.

2. If y is invertible, then |det_{v}(y)|_{v}|y^{−1}|^{d(v)}_{v} ≤ |y|d(v)(m(v)−1)

v .

Proof. Recall that

|y|_{v} = max

i,j {|y^{i,j}(v)|_{v}},
where

ρ_{v}(y) = (y^{i,j}(v))_{i,j} ∈M_{m(v)}(A_{v}).

Here|q|_{v} =|N_{v}(q)|^{1/d(v)}_{v} whenq ∈A_{v}, N_{v} :A_{v} →k_{v}is the reduced norm and
dimkv(Av) = d(v)^{2}. We noted earlier that|qq^{0}|_{v} = |q|_{v}|q^{0}|_{v} and |q+q^{0}|_{v} ≤
max{|q|_{v},|q^{0}|_{v}} for q, q ∈ A_{v}, so statement 1. of the lemma is clear by the
usual matrix multiplication formula.

Let λv be a prime element of the unique maximal Ov-order Uv in Av,
so that λ_{v}U_{v} = U_{v}λ_{v} = P_{v} is the maximal two-sided proper ideal of U_{v}.
For 0 6= q ∈ Av there is an integer ` such that qUv = λ^{`}_{v}Uv, and |q|_{v} =

|N_{v}(λ^{`}_{v})|^{1/d(v)}_{v} = (#k(v))^{−`/d(v)}. This interpretation of|q|_{v} implies that|a|=
max_{i,j}|a_{i,j}|_{v} is unchanged if we multiply a matrixa = (a_{i,j}) ∈ M_{m(v)}(A_{v})
on the left or right by a permutation matrix, by a matrix which multiplies
a single row or column by an element of U_{v}^{∗}, or by an elementary matrix
associated with some element of Uv. Thus to prove inequality (2) of Lem-
ma 3.2, we can use these operations to reduce to the case where y is a
diagonal matrix with entriesλ^{z}_{v}^{1}, . . . , λ^{z}_{v}^{m(v)} for some integers z_{1}, . . . , z_{m(v)}.

When y has this form,

|y|^{d(v)}_{v} = max{|N_{v}(λ^{z}_{v}^{i})|_{v}: 1≤i≤m(v)}= (#k(v))^{−}^{min}^{i}^{{z}^{i}^{}},

|det_{v}(y)|_{v} =|N_{v}(λ)^{z}|_{v} = (#k(v))^{−z} where z=

m(v)

X

i=1

zi,

and y^{−1} is the diagonal matrix with entriesλ^{−z}_{v} ^{1}, . . . , λ^{−z}v ^{m(v)}. Therefore,

|y^{−1}|^{d(v)}_{v} = (#k(v))^{−}^{min}^{i}^{{−z}^{i}^{}}= (#k(v))^{max}^{i}^{{z}^{i}^{}}.

The inequality in statement 2. of the lemma is therefore equivalent to
maxi {z_{i}} −z≤ −(m(v)−1) min

i {z_{i}}.

This is the same as

z−max

i {z_{i}} ≥(m(v)−1) min

i {z_{i}},

which is certainly true.

SMALL GENERATORS FOR 1183

Lemma 3.3. Suppose vis an infinite place, so that there is an isomorphism
ρv :Bv → M_{m(v)}(Av) with Av = kv if v is complex and either Av =kv or
Av =Hifv is real. Definedet^{0}_{v} :Bv →kv by det^{0}_{v}(q) =|det_{v}(q)|^{1/d(v)}_{v} where
det_{v} :B_{v} →k_{v} is the reduced norm. Then, there are minimal real constants
δ1(Av, m(v))and δ2(Av, m(v)) such that for all y, y^{0} ∈Bv:

1. |yy^{0}|_{v} ≤δ1(Av, m(v))|y|_{v}|y^{0}|_{v}.

2. |yy^{0}|_{v} =|y|_{v}|y^{0}|_{v} if eithery or y^{0} is a scalar matrix or a permutation
matrix.

3. |det^{0}_{v}(y)y^{−1}|_{v} ≤δ_{2}(A_{v}, m(v))|y|^{m(v)−1}_{v} for all y∈B_{v}^{∗}.
We also have the bounds

(17) 1≤δ_{1}(A_{v}, m(v))≤m(v)^{[k}^{v}^{:R]}

(18) 1≤δ_{2}(A_{v}, m(v))≤2^{[k}^{v}:R]m(v)(m(v)−1).
Furthermore, ifA_{v} =k_{v} then

(19) 1≤δ_{2}(A_{v}, m(v))≤((m(v)−1)!)^{[k}^{v}^{:}^{R}^{]}.
Proof. As before,

|y|_{v} = max

i,j {|y^{i,j}(v)|_{v}}
where

ρ_{v}(y) = (y^{i,j}(v))_{i,j} ∈M_{m(v)}(A_{v})

and |q|_{v} =|N_{v}(q)|^{1/d(v)}_{v} forq ∈Av, and where Nv :Av → kv is the reduced
norm and dim_{k}_{v}(Av) =d(v)^{2}. We noted earlier that |qq^{0}|_{v} =|q|_{v}|q^{0}|_{v} for all
q, q ∈A_{v}, and by Lemma 3.1,

m(v)

X

i=1

q_{i}
v

≤m(v)^{[k}^{v}^{:}^{R}^{]−1}

m(v)

X

i=1

|q_{i}|_{v} ≤m(v)^{[k}^{v}^{:}^{R}^{]}max_{i}{|q_{i}|_{v}}

for{q_{i}}_{i} ⊂Av. By writing the matrix entries of yy^{0} as sums of products of
the entries ofyandy^{0} this leads to (1) in Lemma3.3and the stated bounds
on δ_{1}(A_{v}, m(v)). The bound (2) in Lemma3.3is clear.

Now suppose that y ∈ B_{v}^{∗}. We can find permutation matrices r and r^{0}
such that the entry q of ryr^{0} for which | |_{v} is maximal lies in the upper
left corner. We then perform Gauss–Jordan elimination on the rows and
columns ofryr^{0} to produce matrices eand e^{0} in M_{m(v)}(A_{v}) such thateand
e^{0} are products of elementary matrices and the nonzero off-diagonal entry
of each elementary matrix for e or e^{0} has the form −τ /q for some entry τ
of ryr^{0}, where | −τ /q|_{v} = |τ|_{v}/|q|_{v} ≤ 1. The matrix y_{1} = eryr^{0}e^{0} has the
same entryq asy in the upper left corner, and all of the other entries in the
first row and the first column are 0. Finally, the other entries ofy_{1} have the
form α−(τ /q)β where α, β, andτ are entries of ryr^{0}. Since|τ|_{v} ≤ |q|_{v} we
see from Lemma 3.1that

|α−(τ /q)β|_{v} ≤2^{[k}^{v}^{:}^{R}^{]−1}(|α|_{v}+|β|_{v})≤2·2^{[k}^{v}^{:}^{R}^{]−1}|q|_{v} = 2^{[k}^{v}^{:}^{R}^{]}|y|_{v}.

Since q is an entry of y_{1}, we deduce that

|y|_{v} ≤ |y_{1}|_{v}≤2^{[k}^{v}^{:}^{R}^{]}|y|_{v} and det(y1) =±det(y).

We now continue withy1 and construct matricess, s^{0} ∈M_{m(v)}(Av) such that
sands^{0} are products of elementary matrices and permutation matrices, and
the off-diagonal entries of the elementary matrices involved in each product
have absolute value with respect to | |_{v} bounded above by 1. The matrix
y^{0}=sys^{0} is diagonal and

|y|_{v} ≤ |y^{0}|_{v} ≤2^{[k}^{v}^{:}^{R}^{](m(v)−1)}|y|_{v}
(20)

det(y^{0}) =±det(y).

(21)

Then (y^{0})^{−1} = (s^{0})^{−1}y^{−1}s^{−1} and s^{0}(y^{0})^{−1}s = y^{−1}, where s, s^{0},(s^{0})^{−1}, and
s^{−1} are products of elementary matrices and permutation matrices such
that the off diagonal entries in each elementary matrix has absolute value
with respect to | |_{v} bounded by 1. This leads by the above reasoning to the
bounds

|(y^{0})^{−1}|_{v} ≤2^{[k}^{v}^{:}^{R}^{](m(v)−1)}|y^{−1}|_{v}
(22)

|y^{−1}|_{v} ≤2^{[k}^{v}^{:}^{R}^{](m(v)−1)}|(y^{0})^{−1}|_{v}.
(23)

Write y^{0} = diag(c1, . . . , c_{m(v)}) for some ci ∈ Av. Define ri = |c_{i}|_{v} =

|N_{v}(c_{i})|^{1/d(v)}_{v} . Then

|y^{0}|_{v} = max_{i}{r_{i}},
det^{0}(y^{0}) =Y

i

r_{i} =r,

det^{0}(y^{0})(y^{0})^{−1} = diag(rc^{−1}_{1} , . . . , rc^{−1}_{m(v)}).

We deduce from this that

|det^{0}(y^{0})(y^{0})^{−1})|_{v} = max

i {|rc^{−1}_{i} |_{v}}

= rmax

i {|c^{−1}_{i} |_{v}}

= rmax

i {r_{i}^{−1}}
(24)

≤ (max

i {r_{i}})^{m(v)−1}
(25)

= |y^{0}|^{m(v)−1}_{v} .
(26)

SMALL GENERATORS FOR 1185

Combining this with (20) and (22) gives

|det^{0}(y)(y)^{−1})|_{v} = |det^{0}(y)|_{v}|y^{−1}|_{v}

= |det^{0}(y^{0})|_{v}|y^{−1}|_{v}

≤ 2^{[k}^{v}^{:}^{R}^{](m(v)−1)}|det^{0}(y^{0})|_{v}|(y^{0})^{−1}|_{v}

≤ 2^{[k}^{v}^{:}^{R}^{](m(v)−1)}|det^{0}(y^{0})(y^{0})^{−1}|_{v}

≤ 2^{[k}^{v}^{:}^{R}^{](m(v)−1)}|y^{0}|^{m(v)−1}_{v}

≤ 2^{[k}^{v}^{:}^{R}^{](m(v)−1)}

2^{[k}^{v}^{:}^{R}^{](m(v)−1)}|y|_{v}m(v)−1

= 2^{[k}^{v}:R]m(v)(m(v)−1)|y|^{m(v)−1}_{v} .
(27)

This gives (2) in Lemma3.3 and the bound (18) onδ_{2}(A_{v}, m(v)).

Now, suppose that Av = kv. We can improve the above bound on
δ_{2}(A_{v}, m(v)) using the fact that det(y)y^{−1} is the transpose of the cofactor
matrix ofy. Using the formula for the determinant as a sum over permuta-
tions, every entry det(y)y^{−1}is the sum of (m(v)−1)! terms, each of which is

±1 times a product ofm(v)−1 entries of the matrixy. The absolute value
with respect to| |_{v} of each entry of yis bounded by|y|_{v}, which implies that

|det(y)y^{−1}|_{v} ≤((m(v)−1)!)^{[k}^{v}^{:}^{R}^{]−1}(m(v)−1)!|y|^{m(v)−1}_{v} =
((m(v)−1)!)^{[k}^{v}^{:R]}|y|^{m(v)−1}_{v} .

This is the bound in (19).

4. The main result

We retain all notation and definitions from§§2-3. Let{ω_{i}}^{nd}_{i=1}^{2} be aZ-basis
forD. The discriminantd_{D} of Dis defined to be

d_{D}= det(M),

whereM is the matrix (T(ω_{i}ω_{j}))_{1≤i,j≤nd}2 and T :B_{R}→R is the trace. As
a real vector space, B_{R}∼=R^{nd}

2. The additive Tamagawa measure Vol onB described in [2,§X.3] is defined in such a way that

(28) d_{D}= Vol(B_{R}/D) =|d_{D}|^{1/2}.

Consider a compact convex symmetric subset X of B_{R}. By Minkowski’s
lattice point theorem, if

(29) Vol(X)≥2^{dim}^{Q}^{B} d_{D},

then X contains a nonzero element of D. Since X is bounded, there is
a constant mX such that |Norm_{v}(y)|_{v} is bounded by m^{[k}_{X}^{v}^{:}^{R}^{]/n} for every
y∈B_{v}∩X and v∈V∞. Then the set

(30) F_{X} ={(x, β)∈G_{S} : x∈X, βD⊆D, [D:βD]≤m_{X}}
is a compact subset ofG_{S}.

Proposition 4.1. With notation as above, suppose thatS contains all finite
placesv ofk such that|Norm_{k/}_{Q}(v)|^{d}≤mX. ThenFX is a fundamental set
for the action of Γ_{S} onG_{S} in the sense that Γ_{S}F_{X} =G_{S}.

Proof. Given (x, β)∈G_{S}, we must show that there existsc∈Γ_{S} such that
(cx, cβ)∈FX. This happens if and only if

cβD ⊆ D (31)

[D:cβD] ≤ mX, and (32)

cx ∈ X.

(33)

By definition, (31) means thatc∈Dβ^{−1}. Ifcx∈X, then
[D:cβD] = |Norm_{f}(cβ)|^{−1}

= |Norm_{f}(c)|^{−1}|Norm_{f}(β)|^{−1}

= |Norm_{∞}(c)| |Norm_{∞}(x)|

(34)

= |Norm∞(cx)|

≤ Y

v∈V∞

m^{[k}_{X}^{v}^{:}^{Q}^{]/n}=mX

by (9) and the definitions of GS and mX. Therefore (33) implies (32).

Combining these facts, it suffices to show that Dβ^{−1} ∩Xx^{−1} contains an
element of ΓS.

Since Xx^{−1} is convex and symmetric with volume Vol(X)|Norm_{∞}(x)|^{−1}
and the latticeDβ^{−1} inR^{nd}

2 has covolume

Covol(Dβ^{−1}) =d_{D}|Norm_{f}(β^{−1})|^{−1}=d_{D}|Norm_{∞}(x)|^{−1},
this implies that

Vol(Xx^{−1})≥2^{dim}^{Q}^{B}Covol(Dβ^{−1})

if and only if Vol(X) ≥ 2^{dim}^{Q}^{B}d_{D}. Since this holds by definition of X,
it follows that Xx^{−1}∩Dβ^{−1} contains a nonzero element c of Dβ^{−1}. By
construction,c is an element ofB^{∗} such that (cx, cβ)∈F_{X}. We claim that
c∈ΓS.

Since cβ ∈D, it follows from (4) that |Norm_{v}((cβ)_{v})|^{−1} is a nonnegative
integral power of Norm_{k/}_{Q}(v)^{d} for each v∈V_{f}. We know that

Y

v6∈V∞

|Norm_{v}((cβ)_{v})|^{−1} =|Norm_{f}(cβ)|^{−1} =|Norm_{∞}(cx)| ≤m_{X}
by (34). Hence if |Norm_{v}((cβ)_{v})| 6= 1 for some finite place v, then

|Norm_{k/}

Q(v)|^{d}≤m_{X},
which implies that v∈S_{f}. It follows that

|Norm_{v}((cβ)v)|= 1

SMALL GENERATORS FOR 1187

for allv∈V_{f}rS_{f}. Thus (cβ)_{v}Dv =Dv for thesev, since cβ∈D. However,
βv = 1 if v /∈S, so

cDv =c_{v}Dv = (cβ)_{v}Dv =Dv

for allv∈V_{f} rS_{f}. This implies that c∈D^{∗}v for allv /∈S_{f}, so c∈ΓS. This

proves the proposition.

We now describe howFX determines generators for ΓS. A subsetP ofGS

will be called a set oftopological generators forG_{S} if for any open subsetO
of GS, the group generated byO and P is all of GS. The following lemma
should be compared with [7, Lemma 6.3].

Lemma 4.2. Let P be a set of topological generators for G_{S} that contains
the identity, and let FX be as in Proposition 4.1. Then ΓS is generated by
its intersection withF_{X}P F_{X}^{−1}.

Proof. We have an equality of sets

FX(P ∪P^{−1})F_{X}^{−1} = (FXP F_{X}^{−1})∪(FXP F_{X}^{−1})^{−1}.

Therefore we can replace P by P∪P^{−1} for the remainder of the proof and
assume that P is symmetric, i.e., that P = P^{−1}. We emphasize that this
does not mean we must assume P is symmetric in the statement of the
lemma.

Consider the subset

O = (GSrΓS)∪(ΓS∩FXF_{X}^{−1})

of GS. This is an open neighborhood of FXF_{X}^{−1} in GS because ΓS is a
discrete subgroup ofG_{S}. SinceF_{X} is a fundamental set for the action of Γ_{S}
on GS, we can find a subsetF ⊂FX such that ΓS×F →GS is a bijection.

We claim that there is a small open neighborhood U of the identity in G_{S}
such thatF U F^{−1}⊂O.

It will be enough to find a U such that Γ_{S}∩(F U F^{−1}) ⊂ F_{X}F_{X}^{−1}. Let
T be the set of γ ∈ Γ_{S} such that γF ∩F U 6=∅. We want to show that if
γ ∈T, then γFX ∩FX 6=∅. SinceF is a bounded fundamental domain for
the action of Γ_{S} on G_{S} and Γ_{S} is discrete inG_{S}, the setT is finite when U
is bounded. We can then shrink U further and assume that if γ ∈T, then
γF^{0}∩F^{0} 6=∅ for each open neighborhoodF^{0} of the closure of F inG_{S}. If
γFX ∩FX = ∅ for some γ ∈ T, then since FX is compact there will be an
open neighborhoodF^{0} ofF_{X} for whichγF^{0}∩F^{0} =∅. This is a contradiction,
since the closure of F is contained inF_{X}, which proves the claim.

LetP^{0} =P∪U, sohP^{0}i=GS, and let ∆<ΓS be the subgroup generated
by Γ_{S}∩F P^{0}F^{−1}. We claim that ∆ = Γ_{S}. Indeed, if xp∈F P^{0}, there exist
y∈F and γ ∈ΓS such thatxp=γy. Then

γ =xpy^{−1} ∈F P^{0}F^{−1},

soγ ∈∆. This implies thatF P^{0}⊆∆F, so ∆F P^{0}⊆∆F. Therefore, ∆F is
right P^{0}-invariant, but hP^{0}i =GS, so ∆F =GS. Since ΓS×F → GS is a
bijection, it follows that ∆ = Γ_{S}.

This proves that Γ_{S} is generated by

ΓS∩F P^{0}F^{−1} ⊆(ΓS∩F P F^{−1})∪(ΓS∩F U F^{−1}).

However, F U F^{−1} ⊂O, and Γ_{S}∩O ⊂F_{X}F_{X}^{−1} by definition, so
(35) ΓS∩F P^{0}F^{−1} ⊆(ΓS∩FXP F_{X}^{−1})∪(ΓS∩FXF_{X}^{−1}).

Since P contains the identity, the right side of (35) equals Γ_{S}∩F_{X}P F_{X}^{−1}.

This proves the lemma.

We now define several constants that we need to state our main result.

(1) For X,FX, and `as above, let T1 be the supremum of 1 and n

|x_{v}|^{d(v)/[k}_{v} ^{v}^{:R])}o
over all

x= Y

v∈V∞

xv ∈B_{R}

for which (x, β)∈FX for someβ.

(2) Let P be a finite set of topological generators for G_{S} which contains
the identity element (see §5.4 for an example of such a set). We as-
sume that every element ofP has the form (z, ζ) withz=Q

v∈S∞zv ∈
B^{∗}

Randζ =Q

v∈S_{f}ζv ∈B_{S}^{∗}

f, wherezv is a real scalar and eachζv lies
in the local maximal order M_{m(v)}(U_{v}) ofB_{v} = M_{m(v)}(A_{v}) (cf. §5.4).

Let T2 be the supremum of 1 and n

|z_{v}|^{d(v)/[k}_{v} ^{v}^{:}^{R}^{]}o
over all z=Q

vz_{v} ∈P and all v∈V∞.
(3) Let T3 be

Y

v∈Sf

maxn

1,|α_{v}|^{d(v)}_{v} o
where as (x, α) ranges overF_{X} and α=Q

v∈Sf α_{v} ∈B_{S}^{∗}

f. Note that
for suchαandαv we have thatαvDv ⊆Dv. Suchαv are contained in
Dv, so this constant is finite. Similarly, define T_{3}^{0} to be the maximum
of

Y

v∈S_{f}

max n

1,|α_{v}|d(v)(m(v)−1)
v

o ,

where α and theαv range as above.

(4) Let T_{4} be the smallest number such that
Y

v∈S_{f}

max n

1,|g_{v}|^{d(v)}_{v} o

≤T4

for all g=Q

vgv ∈P.

SMALL GENERATORS FOR 1189

(5) Let T_{5} be the supremum of 1 and

n|det_{v}(a_{v})|^{1/[k}_{v} ^{v}^{:}^{R}^{]} : a∈F_{X} and v∈V∞

o .

where we write a ∈ F_{X} as a = (a_{v})_{v} with a_{v} ∈ B_{v}. (Recall that
detv :Bv →kv is the reduced norm.)

(6) Let T_{6} be the maximum over all subsetsW of V∞ of
T_{1}^{a(W}^{)}T_{2}^{b(W}^{)}T_{5}^{b(V}^{∞}^{r}^{W)}

where

(36) a(W) = X

v∈W

[kv :R]m(v) and b(W) = X

v∈W

[kv :R].

Now we are ready to state and prove our main result.

Theorem 4.3. Let k be an algebraic number field of degree n over Q and
B a central simple k-division algebra of degree d. Let S be a finite set of
places of k containing all the archimedean places V∞ and let D⊂B be an
O_{k}-order. We suppose that the k_{v} isomorphisms ρ_{v} :B_{v} → M_{m(v)}(A_{v}) are
chosen such that ρ_{v}(Dv) ⊆ M_{m(v)}(U_{v}) for v 6∈ S, where U_{v} is the unique
maximal Ov-order in the kv-division algebra Av. Suppose s is the number
of (real) places v at which A_{v} is isomorphic to H. Let G_{S} be the topological
group defined in (9), P be a topological generating set for GS satisfying the
above conditions, and let Γ_{S} be the group ofS-units associated with D.

Suppose thatX is a convex symmetric subset of B_{R} such that (29) holds,
and let m_{X} be the smallest real number such that|Norm_{v}(y)|_{v} is bounded by
m^{[k}_{X}^{v}^{:R]/n} for everyy ∈B_{v}∩X and v∈V∞. Suppose that S contains every
finite place v of k such that Norm(v) ≤m^{1/d}_{X} . Finally, let T_{1}, . . . , T_{6} be the
constants defined immediately above.

Then the set Γ_{S}∩F_{X}P F_{X}^{−1} from Lemma 4.2is contained in
(37) G_{S,X} = BHS ((d−1)!d)^{n} 2^{(d/2)(d−2)}d

4(d−1)!

!s

T6T3T_{3}^{0}T4

! .

Consequently, G_{S,X} is a finite generating set for ΓS.

Proof. Suppose thatγ ∈ΓS∩FXP F_{X}^{−1}. Then, there exist elements (z, ζ)∈
P and

(x, α),(y, β)∈F_{X}, x, y∈X, α= Y

v∈S_{f}

α_{v}, β= Y

v∈S_{f}

β_{v}

so that (γ, γ) = (x, α)(z, ζ)(y^{−1}, β^{−1}). That is,x_{v}z_{v}y_{v}^{−1} =γ for eachv ∈V∞

and αvζvβ_{v}^{−1} =γ for each v∈Sf.

LetW(γ) =W∞(γ)∪W_{f}(γ) be the set of placesv ofkat which|γ|_{v} >1.

By assumption, if v 6∈ S, then v is finite and ρ_{v}(Dv) ⊆ M_{m(v)}(U_{v}). Thus
γ ∈ΓS implies that |γ|_{v} ≤ 1 ifv 6∈S. Thus W(γ) ⊆S,W∞(γ) ⊂V∞ and
W_{f}(γ)⊆S_{f}.

By definition ofH(γ) we have H(γ) = Y

v∈W∞(γ)

|x_{v}z_{v}y_{v}^{−1}|^{d(v)}_{v} × Y

v∈W_{f}(γ)

|α_{v}ζ_{v}β^{−1}_{v} |^{d(v)}_{v} ,

Recall that det_{v} : B_{v} → k_{v} is the reduced norm and that d(v)^{2} is the
dimension ofAv overkv. Ifv is archimedean, we defined det^{0}_{v} :Bv→kv by
det^{0}_{v}(q) =|det_{v}(q)|^{1/d(v)}_{v} forq ∈Bv.

We have |cα|_{v} = |c|_{v}|α|_{v} for c∈ k_{v} and α ∈B_{v}, where |c|_{v} here denotes
the absolute value ofc∈kv with respect to| |_{v} :kv →R. Therefore we can
rewrite the above expression as

H(γ) = Y

v∈W∞(γ)

|det^{0}_{v}(y_{v})x_{v}z_{v}y^{−1}_{v} |^{d(v)}_{v}
(38)

× Y

v∈W_{f}(γ)

|det_{v}(βv)|_{v}|α_{v}ζvβ_{v}^{−1}|^{d(v)}_{v}
(39)

× Y

v∈W∞( γ)

|det_{v}(yv)|^{−1}_{v}
(40)

× Y

v∈W_{f}(γ)

|det_{v}(β_{v})|^{−1}_{v} ,
(41)

where the last two products are computed using the absolute values on the
completionsk_{v}. We now proceed to bound each of these terms.

Sublemma 1. One has that

(42) Y

v∈W∞(γ)

|det^{0}_{v}(y_{v})(x_{v}z_{v}y_{v}^{−1})|^{d(v)}_{v} ≤µ_{1} T_{1}^{a(W}^{∞}^{(γ))} T_{2}^{b(W}^{∞}^{(γ))}
where a(W∞(γ))and b(W∞(γ)) are as in (36) and

(43) µ_{1} = Y

v∈W∞(γ)

δ_{1}(A_{v}, m(v))^{d(v)}δ_{2}(A_{v}, m(v))^{d(v)}.
Furthermore,

(44) µ1 ≤((d−1)!d)^{[k:}^{Q}^{]} 2^{(d/2)(d−2)}d
4(d−1)!

!s

.

if Av =H at exactly s real places of k.

Proof. By assumption each zv is a real scalar. Therefore, Lemma3.3gives

|det^{0}_{v}(yv)(xvzvy_{v}^{−1})|^{d(v)}_{v}

≤δ_{1}(A_{v}, m(v))^{d(v)}|x_{v}|^{d(v)}_{v} |z_{v}|^{d(v)}_{v} |det^{0}_{v}(y_{v})y_{v}^{−1}|^{d(v)}_{v}
(45)

≤δ1(Av, m(v))^{d(v)}|x_{v}|^{d(v)}_{v} |z_{v}|^{d(v)}_{v} δ2(Av, m(v))^{d(v)}|y_{v}|d(v)(m(v)−1)
v

≤δ_{1}(A_{v}, m(v))^{d(v)}δ_{2}(A_{v}, m(v))^{d(v)}T_{1}^{[k}^{v}^{:}^{R}^{]}T_{2}^{[k}^{v}^{:}^{R}^{]}T_{1}^{[k}^{v}^{:}^{R}^{](m(v)−1)}