The number of distinct products in N by N multiplication table

Number theory 1 Minute

You need to know: Basic arithmetic, logarithm.

Background: For positive integer N, let M(N) denote the number of distinct integers n which can be written as n=a\cdot b, where a and b are positive integers not exceeding N.

The Theorem: On 18th January 2004, Kevin Ford submitted to arxiv a paper in which he proved, among other results, the existence of positive constants c_1 and c_2 such that inequality c_1\frac{N^2}{(\log N)^\delta(\log\log N)^{3/2}} \leq M(N) \leq c_2\frac{N^2}{(\log N)^\delta(\log\log N)^{3/2}} holds for all N, where \delta=1-\frac{1+\log\log 2}{\log 2}=0.08607....

Short context: The number M(N) of distinct products in N\times N multiplication table has been studied starting since 1955, when Erdős proved that \lim\limits_{N\to\infty}\frac{M(N)}{N^2}=0. However, exactly how fast M(N) grows was an open question, answered by the Theorem. In fact, this result is only one out of many corollaries of a deep theory developed by Ford for estimating the number H(x,y,z) of positive integers n \leq x having a divisor in (y,z] and the number H_r(x,y,z) of positive integers n \leq x having exactly r such divisors.

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 8.10 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment