Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 '11 at 20:39
    
@Xander: Thanks for adding the definition! –  Joseph O'Rourke Jun 6 '11 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 '11 at 21:47
    
@Dror: what is BKZ? –  Xander Faber Jun 6 '11 at 21:58
    
Block korkine-zolotareff reduction, slightly stronger than LLL. It interpolates between LLL and HKZ (hermite). –  Junkie Jun 6 '11 at 22:19
show 6 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.