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
1  
@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.) –  Joe Silverman Jun 7 '11 at 3:03

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.