next up previous
Next: Linear recurrence sequences Up: Diophantine Equations and Diophantine Previous: Introduction

Linear equations with unknowns from a multiplicative group

We introduce some terminology. Let $ {\mathbb{C}}^*$ be the multiplicative group of non-zero complex numbers. Let $ \Gamma $ be a subgroup of $ {\mathbb{C}}^*$. $ \Gamma $ is said to be a torsion group if all its elements have finite order, that is, are roots of unity. In that case we say that $ \Gamma $ has rank 0. More generally, $ \Gamma $ is said to be of finite rank if there are $ a_1,\ldots,a_r\in\Gamma $ with the following property: for every $ x\in\Gamma $ there exist integers $ z_1,\ldots,z_r$ and a positive integer $ m$ such that $ x^m=a_1^{z_1}\cdots a_r^{z_r}$. If $ \Gamma $ is not a torsion group then the smallest $ r$ for which such $ a_1,\ldots,a_r$ exist is called the rank of $ \Gamma $.
For instance, the group

$\displaystyle \Gamma$ $\displaystyle =$ $\displaystyle \{ x\in{\mathbb{C}}^*:\, \exists m\in{\mathbb{N}},\, z_1,z_2\in{\mathbb{Z}}:\, x^m=2^{z_1}\cdot 3^{z_2}\}$  
  $\displaystyle =$ $\displaystyle \{ \zeta \sqrt[m]{2^{z_1}3^{z_2}}:\, \zeta \,\,$root of unity$\displaystyle ,\,\,m\in{\mathbb{N}},\, z_1,z_2\in{\mathbb{Z}}\}$  

has rank $ 2$. More generally, any subgroup of $ \Gamma $ containing $ 2,3$ has rank $ 2$.

First let $ a,b$ be non-zero rational numbers and let $ \Gamma =\{ p_1^{z_1}\cdots p_r^{z_r}:\, z_i\in{\mathbb{Z}}\}$ be the multiplicative group generated by the prime numbers $ p_1,\ldots,p_r$. In 1933, Mahler [17] showed that the equation

$ ax+by=1$   in $ x,y\in\Gamma $ (1)

has only finitely many solutions. In 1960, Lang [13] showed that for any $ a,b\in{\mathbb{C}}^*$ and any subgroup $ \Gamma $ of $ {\mathbb{C}}^*$ of finite rank, the number of solutions of equation (1) is finite.

For subgroups $ \Gamma $ of $ {\mathbb{Q}}^*$ there are reasonably efficient algorithms to determine all solutions of (1). For instance, consider the equation

$\displaystyle x+y=1$   $\displaystyle \mbox{in $x,y\in\Gamma =\{ 2^{z_1}3^{z_2}5^{z_3}7^{z_4}11^{z_5}13^{z_6}:\, z_i\in{\mathbb{Z}}\}$ \mbox{with \mbox{$x \leqslant y$.}}}$

We give some solutions: $ (\frac{1}{2},\frac{1}{2})$, $ (\frac{3}{7},\frac{4}{7})$, $ (\frac{2}{13},\frac{11}{13})$, $ (\frac{3993}{20800},\frac{16807}{20800})$. In his thesis, [30, Section 6.5], de Weger determined all solutions of this equation, and showed that there are precisely $ 545$ of them.

Our concern is to give uniform upper bounds for the number of solutions of infinite classes of equations of the shape (1), depending on as few parameters as possible. In 1984, the author [4] showed that in Mahler's case, that is, with $ a,b\in{\mathbb{Q}}^*$ and with $ \Gamma $ the group generated by prime numbers $ p_1,\ldots,p_r$, equation (1) has at most $ 3\times 7^{2r+3}$ solutions. This bound is independent of the primes $ p_1,\ldots,p_r$ and of the coefficients $ a,b$. Building further on work of Schlickewei, in 1996 Beukers and Schlickewei [1] proved the following general result:
For any subgroup $ \Gamma $ of $ {\mathbb{C}}^*$ of finite rank $ r$, and any $ a,b\in{\mathbb{C}}^*$, equation (1) has at most $ 2^{16(r+1)}$ solutions.

We mention that in 1988, Erd\html{\H{o\/}}\kern.05ems, Stewart and Tijdeman [3] proved a result in the other direction:
Let $ a,b$ be non-zero rational numbers. Then for every $ \varepsilon >0$ and every sufficiently large $ r$, there is a subgroup $ \Gamma $ of $ {\mathbb{Q}}^*$ of rank $ r$ such that (1) has at least $ e^{(4-\varepsilon )r^{1/2}(\log r)^{-1/2}}$ solutions.

We now turn to equations in $ n\geqslant 3$ variables, namely

$ a_1x_1+\cdots+a_nx_n=1$   in $ x_1,\ldots,x_n\in\Gamma $, (2)

where $ \Gamma $ is a subgroup of $ {\mathbb{C}}^*$ of finite rank, and $ a_1,\ldots,a_n\in{\mathbb{C}}^*$. Assume that $ \Gamma $ is not finite. A solution of equation (2) is called non-degenerate, if each subsum of the left-hand side is non-zero, i.e.,

$\displaystyle a_{i_1}x_{i_1}+\cdots +a_{i_t}x_{i_t}\not= 0$   $\displaystyle \mbox{for each subset $\{ i_1,\ldots,i_t\}$\ of $\{ 1,\ldots,n\}$.}$

This non-degeneracy condition is rather natural, since each degenerate solution gives rise to an infinite family of solutions. For instance, if $ (x_1,\ldots,x_n)$ is a solution of (2) with $ a_1x_1+\cdots +a_mx_m=0$, $ a_{m+1}x_{m+1}+\cdots+a_nx_n=1$, then for every $ x\in\Gamma $, $ (xx_1,\ldots,xx_m,x_{m+1},\ldots,x_n)$ is also a solution of (2).

It follows from work of van der Poorten and Schlickewei, the author, and Laurent from the 1980's that (2) has only finitely many solutions. The major tool in the proof of this result is W.M. Schmidt's Subspace Theorem (see next section). In 1990, Schlickewei [23] was the first to give an explicit upper bound for the number of non-degenerate solutions of (2), but only in the special case that $ \Gamma $ is contained in an algebraic number field. Schlickewei's bound depended, apart from the number of variables $ n$ and the rank of $ \Gamma $, on several other parameters and when his work appeared, it was an open problem to deduce a uniform upper bound depending only on $ n$ and the rank of $ \Gamma $. After several intermediate results, Schlickewei, Schmidt and the author [8], see also the survey paper [6] succeeded in proving the following theorem:
Theorem 1. Let $ \Gamma $ be a subgroup of $ {\mathbb{C}}^*$ of finite rank $ r$, and let $ a_1,\ldots,a_n\in{\mathbb{C}}^*$. Then equation (2) has at most $ e^{(6n)^{5n}(r+1)}$ non-degenerate solutions

The basic tool was a new quantitative version of Schmidt's Subspace Theorem, obtained by Schlickewei and the author [7] or the survey paper [6]). The upper bound in Theorem 1 is probably far from best possible, but one can show that the theorem does not remain valid if the upper bound is replaced by a bound independent of $ r$ or $ n$.

We mention that recently, Moree, Stewart, Tijdeman and the author [5] and independently Granville (unpublished) proved the following generalization of the result of Erd\html{\H{o\/}}\kern.05ems, Stewart and Tijdeman mentioned above:
Theorem 2. Let $ a_1\ldots,a_n$ be non-zero rationals. Then for every $ \varepsilon >0$ and every sufficiently large $ r$ there is a subgroup $ \Gamma $ of $ {\mathbb{Q}}^*$ of rank $ r$ such that $ (2)$ has at least $ \exp\big( (1-\varepsilon )\frac{n^2}{n-1}r^{1-(1/n)}(\log r)^{-(1/n)}\big)$ non-degenerate solutions.
The proof is not based on Diophantine approximation but uses instead some analytic number theory.

next up previous
Next: Linear recurrence sequences Up: Diophantine Equations and Diophantine Previous: Introduction