Erdős multiplication problem revisited

Question

This is a well-known problem and is about counting the number of distinct numbers in the $n \times n$ multiplication table.

The very problem has been discussed in-depth and, as such, I require no further input on it by itself. There has been, however, a significant amount of debate about it on StackOverflow, namely this question:

https://stackoverflow.com/questions/24614798/find-the-number-of-distinct-numbers-in-multiplication-table

As far as I understand, the problem has currently only $O(n^2)$ computational solutions (strictly speaking, $kn^2$ iterations, with $k=0.5$), while the asymptotic size of the set is equal to $$\left|\lbrace a\cdot b:\ a,b\leq N\rbrace\right|\asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}}$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}.$$ (Ford, 2008).

As far as my knowledge goes, there is no explicit way to generate a set of size $A(n)$ and to calculate its cardinality without at least $A(n)$ operations. Also, there currently exists no solution to determine the exact value of $A(n)$ without generating the set and counting its unique elements.

There has been significant amount of dispute about it by certain individuals, convinced there is an $O(n)$ solution to the problem [calculating $A(n)$], and that they have found it. Although such solutions are usually disproven, I'm interested if it's at all possible for this problem to be solved strictly below $O(n^2)$, either with explicitly generating the set or using some functional relationship between $n$ and $A(n)$. Currently, both the reference solutions and the one sent by David are $O(n^2)$.

Edit. For clarity, let us split this into two questions:

a) Can exact $A(n)$ for a specific $n$ be actually calculated without generating the set itself (i.e. without any need to know and possibly without any method to tell if a number is in the set, or not) and if so, how? If not, possible reasons for practical/theoretical possibility/impossibility of creating such solution would be perfect.

b) Can $A(n)$ be computed by generating the set in strictly below $O(n^2)$ complexity (e.g. $O(n^2/\log \log n)$ or similar)? If so, how would that be possible?

Distinct numbers in multiplication table

Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$

I don’t quite understand what you mean by “at all possible”. Either there is a subquadratic algorithm for the problem, or there isn’t. As far as I can see, the only a priori lower bound on the time complexity of the problem is $\Omega(\log n)$ (which is the number of bits in the output). — Emil Jeřábek, Jul 20 '14 at 19:41
@EmilJeřábek I agree that the verified existence of subquadratic algorithm would make the answer obvious; yet, because nobody has created such an algorithm so far (and I've seen many attempts that has failed), I'm asking is it possible for such an algorithm to exist - and if so, how would it have to work? ; still, I've added a clarification to the question. — , Jul 20 '14 at 19:45
When the input is given in binary, the problem is in the counting hierarchy. Thus, if #P = FP, it can be solved in time polynomial in the input size, i.e., $O((\log n)^c)$ for some $c$. So, we cannot disprove the existence of an $O((\log n)^c)$ (let alone $O(n)$) algorithm without earth-shaking advances in complexity theory. — Emil Jeřábek, Jul 20 '14 at 19:55
@EmilJeřábek while what you write is strictly true, I don't strictly follow how that relates to the (edited) question; I see the problem twofold (correct me if I'm wrong) - a) if the problem can only be solved by generating the set itself, the lowest time complexity is the time needed to generate the set itself, and it's computationally impossible to generate size n set below O(n) - in that case, how could we reduce the number of operations needed to generate this specific set below O(n^2)? b) if the problem can be solved without generating the set - then how? — , Jul 20 '14 at 20:10
Number-theoretic counting functions can be quite often computed faster than by enumerating the relevant set. For example, the prime-counting function $\pi(n)$ can be computed in time $n^{1/2+o(1)}$. I don’t know whether one can do something of that sort for the Erdős problem, but it is certainly possible in principle. — Emil Jeřábek, Jul 20 '14 at 20:18
My previous comment specifically addressed the part of your question which says “If not, a proof of impossibility of creating such solution would be perfect”. The answer is that a proof of such impossibility (or even of of the much weaker impossibility of the existence of an $O((\log n)^c)$-time algorithm) would be a breakthrough result waaaaay beyond our present knowledge and available techniques. — Emil Jeřábek, Jul 20 '14 at 20:50
The cosmetic rewording does not change the basic fact that the answer to either question a) or b) can only be “yes” or “maybe”, it cannot be “no”. — Emil Jeřábek, Jul 20 '14 at 21:05
One unsuccessful approach I tried was to group primes over $\sqrt{n}$. Any two primes between $n/2$ and $n$ are essentially equivalent, as are any between $n/3$ and $n/2$. This gives us only $(1+o(1))\sqrt{n}$ essentially different primes, and you can save some time by counting factorizations of essentially different products. However, a positive proportion of numbers up to $n$ have no prime factor over $\sqrt{n}$ since the density of numbers with no prime factor greater than their square root is $1-\log 2$, so there isn't an obvious improvement better than a constant factor. — Douglas Zare, Jul 21 '14 at 12:17
The number of distinct entries in the $n\times n$ multiplication table is tabulated at https://oeis.org/A027424 and many references to the literature are given. Some of those references appear to be concerned with the efficient calculation of the number. — Gerry Myerson, Feb 02 '21 at 09:25

score 8 · Answer 1 · answered Jul 29 '21 at 10:23

The answer to both your questions are (essentially) yes, and are given in a recent paper of Brent, Pomerance, Purdum, and Webster.

Regarding (b), they show that $A(n)$ can be computed in subquadratic time. Their algorithm also tabulates the set of products.

Regarding (a), they note that for large values of $n$, exact algorithms are too slow, so they also present two Monte Carlo algorithms for approximating $A(n)$. These Monte Carlo algorithms do not tabulate the set of products (doing so would be too expensive). This answers (a) in the positive (if you don't mind Monte Carlo algorithms).

They have implemented their algorithms and give exact values of $A(n)$ for all $n \leq 2^{30}$, and Monte Carlo computations for all $n \leq 2^{100000000}$.

Erdős multiplication problem revisited

1 Answers1