9

1

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.

flag
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? – Joseph O'Rourke Jun 6 2011 at 20:39
@Xander: Thanks for adding the definition! – Joseph O'Rourke Jun 6 2011 at 21:22
Maybe applying BKZ to a basis of the integer ring divided by $a$, varying over $a$, will work? – Dror Speiser Jun 6 2011 at 21:47
@Dror: what is BKZ? – Xander Faber Jun 6 2011 at 21:58
Block korkine-zolotareff reduction, slightly stronger than LLL. It interpolates between LLL and HKZ (hermite). – Junkie Jun 6 2011 at 22:19
show 6 more comments

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.