11
$\begingroup$

Let $K$ be a number field of absolute degree $d$, let $B$ be a positive real number, and write $S(K, B) = \{x \in K : H(x) \leq B\}$. Here $H$ is the absolute multiplicative height of an algebraic number. A result of Schanuel asserts that $|S(K, B)| \sim c B^{2d}$ for some explicit constant $c$ depending only on the number field $K$.

Does anyone know if the proof of Schanuel's result can be turned into an algorithm for computing the set $S(K,B)$?

There are other approaches to computing the set $S(K,B)$. For example, the article "Elements with bounded height in number fields" by Petho and Schmitt [Period. Math. Hungar. 43 (2001), no. 1-2, 31–41] gives an algorithm that embeds $S(K,B)$ into a computable set of size $B^{2d^2 + d}$. But sorting through this larger set to determine $S(K,B)$ is computationally infeasible for quadratic fields when $B$ is larger than about 3.

NB - The simplest definition of the absolute multiplicative height is via the Mahler measure of its minimal polynomial. Suppose $x \in K$ has minimal polynomial $f(T) \in \mathbb{Z}[T]$, and write $$f(T)= a(T-\alpha_1) \cdots (T - \alpha_r)$$ with $\alpha_i \in \mathbb{C}$. Without loss of generality, we may assume $x = \alpha_1$. Then the absolute multiplicative height $H(x)$ can be defined by the formula $$ H(x)^r = |a| \prod_{i = 1}^r \max\{1, |\alpha_i|\}. $$

P.S. To clarify, I already have an algorithm in hand that calculates the set $S(K,B)$ fairly quickly, but I am specifically interested in knowing whether or not Schanuel's technique can be reworked into an algorithm.

Improve this question
$\endgroup$
11
  • $\begingroup$ Perhaps you should define "the absolute multiplicative height of an algebraic number" just for the education of those less versed in this area. Is it $n + \sum |a_i|$ where the $a_i$ are the coefficients of the min degree polynomial of which it is a root? $\endgroup$
    – Joseph O'Rourke
    Commented Jun 6, 2011 at 20:39
  • $\begingroup$ @Xander: Thanks for adding the definition! $\endgroup$
    – Joseph O'Rourke
    Commented Jun 6, 2011 at 21:22
  • $\begingroup$ Maybe applying BKZ to a basis of the integer ring divided by $a$, varying over $a$, will work? $\endgroup$
    – Dror Speiser
    Commented Jun 6, 2011 at 21:47
  • $\begingroup$ @Dror: what is BKZ? $\endgroup$
    – Xander Faber
    Commented Jun 6, 2011 at 21:58
  • 1
    $\begingroup$ @Xander: Do you actually want the full set $S(K,B)$, or do you have some other problem such as a Diophantine equation whose solutions you know have height less than $B$, and you want to find the solutions? If the latter, there are often tricks to cut the search space. As for Schanuel's proof, my impression is that if it's done carefully with error estimates, it will yield an algorithm, but I don't imagine it would be at all efficient. (However, I haven't actually tried to do it.) $\endgroup$
    – Joe Silverman
    Commented Jun 7, 2011 at 3:03

0

Reset to default

You must log in to answer this question.