Pith. sign in

REVIEW 1 major objections 4 minor 28 references

Algorithms for the Multiplication Table Problem

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper presents an algorithm that tabulates $M(n)$, the number of distinct entries in the $n\times n$ multiplication table, for all $k\le n$ in time $O(n^2/L^{1/\sqrt{2}+o(1)})$, where $L=\exp(\sqrt{\log n\,\log\log n})$, the first…

desk verdict The incremental algorithm and data are solid, but the proof of the claimed subquadratic tabulation bound (Theorem 2.9) has a real gap and needs repair. read the letter →

arxiv 1908.04251 v2 pith:DLOPHZKP submitted 2019-08-12 math.NT

Richard Brent , Carl Pomerance , David Purdum , Jonathan Webster This is my paper · ORCID
classification math.NT MSC 11A2511N3711Y1611Y7065C0568Q25
keywords multiplicationtabledistinctproductsM(n)subquadraticalgorithmsmoothnumbersdivisorintervalsMonteCarloestimationrandomfactoredintegers
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's central claim is that the exact count $M(n)$ of distinct products in an $n\times n$ multiplication table can be tabulated for every $k\le n$ in time $O(n^2/L^{1/\sqrt{2}+o(1)})$, where $L=\exp(\sqrt{\log n\,\log\log n})$; since $L^{1/\sqrt{2}}$ grows faster than any fixed power of $\log n$, this is a genuinely subquadratic bound. This matters because the asymptotic size of $M(n)$ is known only up to a slowly varying factor, not as a limit, so exact values for large $n$ are the main empirical route to guessing the true behavior. The paper also gives two Monte Carlo estimators for $M(n)$ at much larger $n$, proves that the \u201cproduct\u201d estimator has variance no larger than the \u201cBernoulli\u201d one, and reports exact computations through $n=2^{30}$ and approximate ones through $n=2^{100,000,000}$. If the main theorem is correct, exact tabulation of the multiplication table is no longer a quadratic-time problem.

What carries the argument

The central object is the divisor-pair shape of an integer $k$: $\delta(k)$ is computed by marking products in rectangles $[0,g]\times[0,k/g]$ for each divisor $g\le\sqrt{k}$, so the running time of the basic step is the area of the union of these rectangles. The key mechanism is Algorithm 4, which reuses the bit vector produced for $\delta(mp)$ to compute $\delta(mq)$ for primes $p<q$ with $m<p$, adding only the products in the shifted part of the shape; the added work is $O(m(q-p)\log n)$. Around this mechanism, the paper wraps a split of integers into $L^\gamma$-smooth and non-smooth classes: smooth $k$ are handled by the direct shape algorithm, and non-smooth $k=mq$ are recovered from a single computation of $\delta(mQ)$ for the largest prime $Q$ with $mQ\le n$. The parameter $\gamma$ is chosen to equalize the two costs, giving the exponent $1/\sqrt{2}$ in the final bound.

What would settle it

Take $\gamma=1/\sqrt{2}$ and count the integers $k\le n$ whose largest prime factor $q$ satisfies $q\le k/q$, restricting to those not $L^\gamma$-smooth; if this count multiplied by $n\log n$ is not $o(n^2/L^{1/\sqrt{2}+o(1)})$, the decomposition used in the proof of Theorem 2.9 cannot yield the stated time bound.

Watch

Extended reading notes

Core claim

Let $M(k)$ be the number of distinct entries in the $k\times k$ multiplication table and let $\delta(k)=M(k)-M(k-1)$ be the number of new products created when the table grows from $k-1$ to $k$. The paper's discovery is that $\delta(k)$ can be computed by looking only at products $ij$ with $i<g$ and $j<k/g$ for divisors $g$ of $k$, and that these computations can be batched: for integers of the form $mp$ with $m<p$ a prime, the bit vector built for $\delta(mp)$ can be reused to compute $\delta(mq)$ for a later prime $q>p$, with work proportional to the gap $q-p$. Splitting all $k\le n$ into $L^\gamma$-smooth and non-smooth classes, and balancing the two sides at $\gamma=1/\sqrt{2}$, yields a tabulation of all $M(k)$ in time $O(n^2/L^{1/\sqrt{2}+o(1)})$ and space $O(n)$. This is the first subquadratic bound for the tabulation problem, and it is achieved with a direct, sieving-style method rather than a reduction to another problem.

Load-bearing premise

For the subquadratic bound, the proof needs every non-smooth $k\le n$ to split as $k=mq$ with $q$ its largest prime factor and $m<q$, so that the reuse step of Algorithm 4 applies; the paper does not address integers such as $p^3$ where $q\le m$, so the bound is not established for that class.

Editorial extensions

If this is right

  • The tabulation problem for $M(n)$ is asymptotically separated from the direct quadratic construction: Theorem 2.9 supplies an algorithm whose running time is $o(n^2)$, so the limiting obstruction to exact computation is no longer the area of the table.
  • The incremental Algorithm 3 runs in time $O(n^2\log n/\Phi(n))$, where $\Phi(n)$ is the slowly varying factor from the known order-of-magnitude result, and Remark 2.7 observes this can be written as $O(M(n)\log n)$, tying the cost to the number of distinct products rather than to the table area.
  • Working modulo $w$ (with $w$ up to 120 in the implementation) reduces both time and space for a $\delta(n)$ computation by counting consecutive products instead of constructing them; the reported runtime for computing a batch of $\delta(n)$ values near $n=10^8$ drops as $w$ increases from 1 to 60.
  • Lemma 3.2 shows that, for the same number of trials, the product estimator's variance is no larger than that of the Bernoulli estimator; in the implementation the product method is preferred for smaller $n$ and the Bernoulli method for larger $n$, mainly because of space.
  • The numerical data, exact through $n=2^{30}$ and Monte Carlo through $n=2^{100,000,000}$, show the normalized ratio $N^2/(M(N)\Phi(N))$ trending toward roughly 0.12; extrapolating this to a limit is non-rigorous, and the paper notes the true asymptotic region may only begin at far larger $n$.
  • We infer that the bit-vector reuse in Algorithm 4 should transfer to other counting problems defined by divisor-list shapes, such as distinct products in rectangular or asymmetric tables, where the same \u201clearn $\delta(mp)$ while computing $\delta(mq)$\u201d mechanism applies whenever two integers have similar divisor structures.
  • We infer that, in practice, the split parameter $\gamma$ would be tuned rather than fixed at $1/\sqrt{2}$, and that measuring the crossover between Algorithm 3 and Algorithm 5 would give a concrete test of where the subquadratic bound starts to bite.
  • The exceptional case identified above suggests a concrete check: count non-smooth $k$ with $q\le k/q$ and see whether a shifted $\gamma$ absorbs them into the smooth class; if it does not, a modified treatment would be needed to keep the theorem intact.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The manuscript studies the computation of M(n), the number of distinct entries in the n × n multiplication table. It presents exact algorithms, including a direct quadratic algorithm, an incremental algorithm that tabulates M(k) for k ≤ n in O(n^2 log n / Φ(n)) time with O(n) space, and a claimed subquadratic algorithm with running time O(n^2/L^{1/√2+o(1)}) and O(n) space. It also gives two Monte Carlo estimators and proves that the 'product' estimator has variance no larger than the 'Bernoulli' estimator. Numerical results are reported for exact computations up to n = 2^30 and Monte Carlo estimates up to n = 2^{100,000,000}, and the data are compared with Ford's order-of-magnitude result.

Significance. If the subquadratic bound were established, it would be a notable improvement over the previous O(n^2 log n / Φ(n)) incremental method, making the exact tabulation claim of clear interest. The incremental algorithm and its Ford-based time bound (Theorem 2.6) are sound and useful, the variance comparison in Lemma 3.2 is correct, and the computational results are extensive. The paper also appears to be the first to implement Bach's algorithm for generating random factored integers. The main caveat is the gap in the proof of Theorem 2.9, which is discussed below and prevents the central subquadratic claim from being accepted as proven.

major comments (1)
  1. [§2.5, Theorem 2.9] The proof of Theorem 2.9 does not cover non-L^γ-smooth k whose largest prime factor q satisfies q ≤ m, where k = m q. The proof writes such k as m q and claims that computing δ(mQ) for the largest prime Q with mQ ≤ n via Algorithm 4 learns δ(mq) for all primes q ≤ Q. However, Algorithm 4 and Lemma 2.8 require an initial prime p with m < p < q; when q ≤ m (e.g., k = p^3 with p > L^γ) no such p exists, and when m > sqrt(n) the largest prime Q with mQ ≤ n may itself satisfy Q ≤ m. The proof gives no alternative treatment or run-time estimate for these k, so the claimed O(n^2/L^{1/√2+o(1)}) total bound is not established for all k ≤ n.
minor comments (4)
  1. [§2.3, Lemma 2.8] The proof of Lemma 2.8 is a single sentence; please expand the area calculation to justify the O(m log n) bound per unit shift, since this estimate is used in the proof of Theorem 2.9.
  2. [§4, Table 3] The header of Table 3 is garbled: the last column should be labeled (N^2/M(N))/Φ(N), and the units of the 'trials' column should be stated. In particular, the value 100 for n = 30 appears inconsistent with the T = 10^6 mentioned earlier in §4.
  3. [§2.5, Algorithm 5] Algorithm 5 is defined only by the proof of Theorem 2.9; a pseudocode listing or a more explicit algorithmic description would improve reproducibility and reader confidence.
  4. [Global] There are minor typographical issues in the arXiv source, including spurious spaces in the title in the header; please check the source file before final submission.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new algorithm's time bounds are derived from external standard results and an analytically balanced parameter, not from fitted data or self-referential definitions.

full rationale

The paper's central claim, Theorem 2.9, is derived by splitting k ≤ n into L^γ-smooth numbers and non-smooth numbers k = mq with q the largest prime factor. The count of smooth numbers uses the external Canfield–Erdős–Pomerance bound, and the δ(n) analysis uses Ford's Corollary 5 through Lemma 2.4. The parameter γ is chosen analytically as γ = 1/√2 to balance two runtime terms; no parameter is fitted to data and then renamed as a prediction. The Monte Carlo extrapolation near 0.12 is explicitly labelled non-rigorous in the paper, so it is not presented as a derivation from the algorithm's own outputs. The authors' self-citations, such as Brent–Kung [8] and Brent's slides [6,7], are historical or implementation-related and are not load-bearing for the asymptotic tabulation claim. The reviewer's concern about non-smooth k = mq with q ≤ m, such as k = p^3, is a potential correctness gap in the proof of Theorem 2.9, not a circularity: it does not reduce the claimed runtime to an input by construction. Applying the required quote-and-reduction standard, no circular step can be exhibited.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The theoretical analysis imports Ford's divisor-interval theorems and smooth-number counting from the literature; these are external results. The new algorithm introduces no new constants fitted to data; the parameter gamma is chosen analytically to balance two run-time terms.

assumptions (4)
  • standard math Ford's theorem: M(n) = Theta(n^2 / Phi(n)) with Phi(n) = (log n)^c (log log n)^{3/2}
    Used for context and in Remark 2.7 to express time bounds; cited from Ford [15,16].
  • standard math Lemma 2.4 (Ford, Corollary 5): (1/n) sum_{k <= n} tau^+(k) = Theta(log n / Phi(n))
    Used in Theorem 2.6 to bound the time of Algorithm 3; cited from Ford [15].
  • standard math Smooth number count: the number of L^gamma-smooth integers <= n is n / L^{1/(2gamma)+o(1)}
    Used in Theorem 2.9 to bound the first class; cited from Canfield, Erdos and Pomerance [10].
  • standard math Bach's algorithm generates random integers in [1,N] together with their prime factorization in expected time (log N)^{O(1)}
    Used in Section 3.3 to avoid factoring; cited from Bach [2].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algorithms for the Multiplication Table Problem." pith.science (2026). https://pith.science/paper/DLOPHZKP

@misc{pith2026190804251,
  author       = {Pith},
  title        = {Pith review of: Algorithms for the Multiplication Table Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DLOPHZKP}},
  note         = {Machine review of arXiv:1908.04251}
}
abstract

Let $M(n)$ denote the number of distinct entries in the $n \times n$ multiplication table. The function $M(n)$ has been studied by Erd\H{o}s, Tenenbaum, Ford, and others, but the asymptotic behaviour of $M(n)$ as $n \to \infty$ is not known precisely. Thus, there is some interest in algorithms for computing $M(n)$ either exactly or approximately. We compare several algorithms for computing $M(n)$ exactly, and give a new algorithm that has a subquadratic running time. We also present two Monte Carlo algorithms for approximate computation of $M(n)$. We give the results of exact computations for values of $n$ up to $2^{30}$, and of Monte Carlo computations for $n$ up to $2^{100,000,000}$, and compare our experimental results with Ford's order-of-magnitude result.

Figures

Figures reproduced from arXiv: 1908.04251 by the authors.

Figure 1
Figure 1. The shape for computing δ(42) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 68 72 76 80 84 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 108 114 120 126 1 2 3 4 5 6 × 1 2 3 4 5 … view at source ↗
Figure 2
Figure 2. The shape for computing δ(42) working modulo 1. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 68 72 76 80 84 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 6 12 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 108 114 120 126 1 2 3 … view at source ↗
Figure 3
Figure 3. shows the area that is considered in computing δ(75) modulo 2. The products in light gray are accounted for by a counting argument and the products in dark gray are constructed. That is, the bit vector storing even numbers starts at 50, and then the even products 52 and 56 in dark gray are constructed. Thus, there are 24+ 2 = 26 unique even products. The bit vector storing odd numbers starts at 25, and constructs th… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The shape for computing δ(377) working modulo 6. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P , Ann. of Math. (2) 160 (2004), 781–793. 12Table 3 is extended to n = 5 × 108 (but with lower accuracy) in [6, 7]. ALGORITHMS FOR THE MULTIPLICATION TABLE PROBLEM 15

    work page 2004

  2. [2]

    Eric Bach, How to generate factored random numbers , SIAM J. Comput. 17 (1988), 179–193

    work page 1988

  3. [3]

    Balazard, J

    M. Balazard, J. L. Nicolas, C. Pomerance, and G. Tenenbau m, Grandes d´ eviations pour certaines fonctions arithm´ etiques, J. Number Theory 40 (1992), 146–164 (in French)

    work page 1992

  4. [4]

    Bernstein, Detecting perfect powers in essentially linear time , Math

    Daniel J. Bernstein, Detecting perfect powers in essentially linear time , Math. Comp. 67 (1998), 1253–1283

    work page 1998

  5. [5]

    Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language , J. Symbolic Comput. 24 (1997), 235–265

    work page 1997

  6. [6]

    Brent, The multiplication table, and random factored integers , slides from a semi- nar given at Hong Kong Baptist University, Hong Kong, Feb

    Richard P. Brent, The multiplication table, and random factored integers , slides from a semi- nar given at Hong Kong Baptist University, Hong Kong, Feb. 6, 2015. https://maths-people. anu.edu.au/~brent/pd/multiplication-HK.pdf

    work page 2015

  7. [7]

    Brent, Algorithms for the multiplication table , slides from a seminar given at CARMA, Newcastle, NSW, May 29, 2018

    Richard P. Brent, Algorithms for the multiplication table , slides from a seminar given at CARMA, Newcastle, NSW, May 29, 2018. https://maths-people.anu.edu.au/~brent/pd/ multiplication-CARMA.pdf

    work page 2018

  8. [8]

    Brent and H

    Richard P. Brent and H. T. Kung, The area-time complexity of binary multiplication , J. Assoc. Comput. Mach. 28 (1981), 521–534. Corrigendum: ibid 29 (1982), 904

    work page 1981

Show all 28 references
  1. [9]

    Burthe, Jr., Further investigations with the strong probable prime test , Math

    Ronald J. Burthe, Jr., Further investigations with the strong probable prime test , Math. Comp. 65 (1996), 373–381

    1996

  2. [10]

    E. R. Canfield, P. Erd˝ os, and C. Pomerance, On a problem of Oppenheim concerning ‘Fac- torisatio Numerorum’, J. Number Theory 17 (1983), 1–28

    1983

  3. [11]

    Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective , sec- ond edition, Springer, New York 2005

    2005

  4. [12]

    Paul Erd˝ os, Some remarks on number theory , Riveon Lematematika 9 (1955), 45–48 (in Hebrew)

    1955

  5. [13]

    Paul Erd˝ os,An asymptotic inequality in the theory of numbers , Vestnik Leningrad. Univ. 15 (1960), no. 13, 41–49 (in Russian)

    1960

  6. [14]

    Tenenbaum, Sur la structure de la suite des diviseurs d’un entier , Ann

    Paul Erd˝ os and G. Tenenbaum, Sur la structure de la suite des diviseurs d’un entier , Ann. Inst. Fourier (Grenoble) 31 (1981, no. 1, ix, 17–37 (in French)

    1981

  7. [15]

    Kevin Ford, The distribution of integers with a divisor in a given interv al, Ann. of Math. (2) 168 (2008), no. 2, 367–433

    2008

  8. [16]

    Lecture Notes, vol

    Kevin Ford, Integers with a divisor in (y,2y], Anatomy of integers, CRM Proc. Lecture Notes, vol. 46, Amer. Math. Soc., Providence, RI, 2008, pp. 65–80

    2008

  9. [17]

    C. F. Gauss, Theoria combinationis observationum erro ribus minimis obnoxiae, Carl Friedrich Gauss Werke , Bd. 4, G¨ ottingen, 1873, 1–26 (in Latin)

  10. [18]

    Helfgott, An improved sieve of Eratosthenes , Math

    Harald A. Helfgott, An improved sieve of Eratosthenes , Math. Comp. 89 (2020), 333-350

    2020

  11. [19]

    Hennessy and David A

    John L. Hennessy and David A. Patterson, Computer Architecture: a Quantative Approach , fifth edition, Elsevier, 2012

    2012

  12. [20]

    Cryptology 16 (2003), 287–289

    Adam Kalai, Generating random factored numbers, easily , J. Cryptology 16 (2003), 287–289

    2003

  13. [21]

    Khinchin, ¨Uber einen Satz der Wahrscheinlichkeitsrechnung , Fundamenta Mathematicae 6 (1924), 9–20 (in German)

    Aleksandr Y. Khinchin, ¨Uber einen Satz der Wahrscheinlichkeitsrechnung , Fundamenta Mathematicae 6 (1924), 9–20 (in German)

    1924

  14. [22]

    H. W. Lenstra jr. and Carl Pomerance, Primality testing with Gaussian periods , J. European Math. Soc. 21 (2019), 1229–1269

    2019

  15. [23]

    Lichtman and Carl Pomerance, Improved error bounds for the Fermat primality test on random inputs , Math

    Jared D. Lichtman and Carl Pomerance, Improved error bounds for the Fermat primality test on random inputs , Math. Comp. 87 (2018), 2871–2890

    2018

  16. [24]

    Miller, Riemann ’s hypothesis and tests for primality, J

    Gary L. Miller, Riemann ’s hypothesis and tests for primality, J. Comp. System Sci. 13 (1976), 300–317

    1976

  17. [25]

    Norton On the number of restricted prime factors of an integer, I , Illinois J

    Karl K. Norton On the number of restricted prime factors of an integer, I , Illinois J. Math. 20 (1976), 681–705

    1976

  18. [26]

    David Purdum, Multiplication table , https://rutrum.github.io/multiplication-table/

  19. [27]

    David Purdum and Jonathan W ebster, http://blue.butler.edu/~jewebste/Mn2pow30.txt

  20. [28]

    Rabin, Probabilistic algorithm for testing primality , J

    Michael O. Rabin, Probabilistic algorithm for testing primality , J. Number Theory 12 (1980), 128–138

    1980

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.