The divisor bound asserts that for a large (rational) integer $n \in {\bf Z}$, the number of divisors of $n$ is at most $n^{o(1)}$ as $n \to \infty$. It is not difficult to prove this bound using the fundamental theorem of arithmetic and some elementary analysis.

My question regards what happens if ${\bf Z}$ is replaced by the ring of integers in some other number field. For sake of concreteness let us work with the simple extension ${\bf Z}[\alpha]$, where $\alpha$ is some fixed algebraic integer. Of course, one may now have infinitely many units in this ring, but if we restrict the height then it appears that we have a meaningful question, namely:

Question: Let $n \in {\bf Z}[\alpha]$ be of height $O(H)$ (by which I mean that $n$ is a polynomial in $\alpha$ with rational integer coefficients of size $O(H)$ and degree $O(1)$). Is it true that the number of elements of ${\bf Z}[\alpha]$ of height $O(H)$ that divide $n$ is at most $H^{o(1)}$?

Here $o(1)$ denotes a quantity that goes to zero as $H \to \infty$, holding $\alpha$ fixed. (Actually, for my applications I would like $\alpha$ to not be fixed, but to have a minimal polynomial of bounded degree and coefficients of polynomial size in $H$, but for simplicity let me stick to the fixed $\alpha$ question first.)

It is tempting to take norms and apply the divisor bound to the norm, but then I end up needing to bound the number of elements in ${\bf Z}[\alpha]$ with a given norm and of controlled height, and I don't know how to do that except for quadratic extensions. A related problem comes up if one tries to exploit unique factorization of ideals to answer this problem. (On the other hand, it appears to me from the Dirichlet unit theorem that the number of units of height $O(H)$ is at most polylogarithmic in H, so the unit problem at least should go away.)

  • $\begingroup$ Maybe add the "heights" tag? $\endgroup$ Jun 22, 2011 at 0:10
  • $\begingroup$ I just learned from Van Vu that the result I wanted is more or less contained in this paper of Chang: math.ucr.edu/~mcc/paper/110%20Factor.pdf . Thanks, though, for the very helpful answers! $\endgroup$
    – Terry Tao
    Jun 28, 2011 at 22:25

2 Answers 2


As long as you allow a fixed number field $F = {\bf Q}(\alpha)$ you can prove $H^{o(1)}$ as you more-or-less suggest towards the end, by first showing that the number of ideals of $F$ that divide $n$ is $H^{o(1)}$ and then proving that any ideal has $O(\log^r H)$ generators of height at most $H$, where $r = r_1 + r_2 - 1$ is the rank of the unit group $U_F$ of $F$.

The first part is basically the same as the argument over $\bf Z$. If the ideal $(n)$ factors into prime powers as $\prod_i \wp_i^{e_i}$ then there are $\prod_i (e_i + 1)$ ideals that divide $n$. Given $\epsilon > 0$ there are finitely many choices of rational prime $p$ and integer $e>0$ such that $e+1 > (p^e)^\epsilon$, and therefore only finitely many choices of a prime $\wp$ of $F$ and $e>0$ such that $e+1$ exceeds the $\epsilon$ power of the norm of $\wp^e$. Therefore $\prod_i \wp_i^{e_i} \ll_\epsilon N^\epsilon$ where $N$ is the absolute value of the norm of $n$. But $N \ll H^{[F : {\bf Q}]}$, and $\epsilon$ was arbitrary, so we've proved the $H^{o(1)}$ bound.

For the second part, Dirichlet gives a logarithm map $U_F \rightarrow {\bf R}^r$ whose kernel is finite (the roots of unity in $F$) and whose image is a lattice $L$. A unit of height at most $H$ has all its conjugates of size $O(H)$, so is mapped to a ball of radius $\log(H) + O(1)$. Therefore there are $O(\log^r(H))$ units of height at most $H$. Much the same argument (involving a translate of $L$) shows that he same bound applies also to generators of any ideal $I$, since the ratio of any two generators of $I$ is a unit.

[I see that "Pitt the Elder" just gave much the same answer.]

  • $\begingroup$ Noam, the exponent on H in the end of the second paragraph should have a small o, not big O. $\endgroup$
    – KConrad
    Jun 22, 2011 at 0:45
  • $\begingroup$ Also, this answer doesn't use the assumption that the ring of integers in the number field has the form Z[alpha], which is good. $\endgroup$
    – KConrad
    Jun 22, 2011 at 0:47
  • $\begingroup$ Thanks to KConrad for the typo correction. Yes, this works equally for non-"monogenic" fields, though perhaps in Terry Tao's context it is natural to work in ${\bf Z}[\alpha]$ and define $H(n)$ in terms of the coefficients of a polynomial giving $n$ in terms of $\alpha$. $\endgroup$ Jun 22, 2011 at 0:57
  • $\begingroup$ Huh, it does indeed seem to work. At some point I thought that one needed to count all ideals of a given norm, but as your argument shows, one only needs to do this for very small norms, at which point the bound needed is obvious. $\endgroup$
    – Terry Tao
    Jun 22, 2011 at 1:13

$\newcommand{\O}{\mathcal{O}}$ $\newcommand{\C}{\mathbf{C}}$ $\newcommand{\R}{\mathbf{R}}$ $\newcommand{\Q}{\mathbf{Q}}$

I believe that your second strategy just works. Suppose that $K$ is a number field, and $\beta \in \O_K$ has height $O(H)$. The number of (ideal) divisors of the ideal $(\beta)$ is easy to estimate from above (and is $O(H^{\epsilon})$ for any $\epsilon$), since it essentially reduces to the same problem over $\Q$. So the problem becomes: given an ideal $I$ in $\O_K$, bound the number of principal generators of $I$ of height $O(H)$.

Let's consider a slight variation on the definition of height, namely, let $H(\beta)$ denote the maximum of the absolute values of $|\beta|$ for every embedding of $K$ into $\mathbf{C}$.

Let $\gamma$ and $\delta$ be two generators of an ideal $I$ whose height is $O(H)$ in your sense. Then it is easy to see that $\gamma$ and $\delta$ as well as $\gamma^{-1}$ and $\delta^{-1}$ have height $O(H)$ in the above sense. Hence the ratio $\gamma/\delta$ is a unit of height at most $O(H^2)$, and so one is reduced to proving the following: the number of units of height $O(H)$ is $O(H^{\epsilon})$ for any $\epsilon$. Actually, the number of such units is well known to be $O(\log(|H|)^r)$ for some $r$. (For example, see "Counting Algebraic Units with Bounded Height", which gives explicit bounds, and even an asymptotic formula with error bounds).

To see why this might be true, note that Dirichlet's unit theorem shows that the map $\O^{\times}_K \rightarrow \R^{r_1+r_2-1}$ (given by taking the logarithms of the absolute values of a suitable choice of embeddings) maps $\O^{\times}_K$ to a lattice, and the height of a unit $u$ is (essentially) the exponential of the $L^1$ norm in $\R^{r_1+r_2-1}$. Thus the problem becomes one of counting the elements in a lattice in $\R^r$ with small $L^1$ norm. This (roughly) only depends on the covolume of the lattice, or in other words, the regulator $R$ of $K$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .