{"id":"1fb17387-8de6-40f9-8cb0-b6fc5dd8d6bd","arxiv_id":"1908.04251","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A claimed subquadratic tabulation algorithm for M(n) with time O(n^2 / L^{1/sqrt(2)+o(1)}), plus exact tables to 2^30 and Monte Carlo tables to 2^100,000,000, with an incomplete proof of the main complexity bound.","lead":"This paper finds faster ways to count how many different numbers appear in an n by n multiplication table, exactly for n up to 2^30 and approximately for table sizes up to 2^100,000,000. A new subquadratic algorithm is claimed, but its proof has a gap for numbers whose largest prime factor is not bigger than the remaining factor.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 2.9 omits non-smooth k = m q with q ≤ m, e.g. k = p^3, where Algorithm 4's precondition m < p < q fails and no alternative bound is given.","rationale":"The reader's weakest_assumption identifies exactly the same gap in Theorem 2.9: the proof assumes every non-smooth k = m q satisfies m < q, which is false for k = p^3. Algorithm 4 requires m < p < q because its correctness relies on the divisor lists of mp and mq having the same structure as q varies, and on the shapes being nested; when q ≤ m, the divisor lists include q (or p) as small divisors and the nested-rectangle re-use argument collapses. The proof does not quantify these cases, so the subquadratic bound is not proven for all k ≤ n. This is load-bearing because Theorem 2.9 is the paper's advertised headline contribution, and the gap appears in the main proof rather than in a peripheral remark. At the same time, the rest of the paper is well supported: Algorithm 3 and Ford's lemma give a sound though non-subquadratic tabulation method, and the exact numerical results and Monte Carlo variance comparison are independent of the gap. The concern is a genuine proof incompleteness, not an observed falsehood, so the appropriate outcome is to require the authors to repair or clarify the proof, matching the reader's CONDITIONAL verdict. No change to that verdict is needed.","tokens_in":15220,"tokens_out":5358,"duration_ms":54426,"concrete_test":"For n = 2^20, 2^25, 2^30 and γ = 1/√2, enumerate the exceptional set E(n) = {k ≤ n : P(k) > L^γ and P(k)^2 ≤ k}, where P(k) is the largest prime factor, and compute the total cost Σ_{k∈E(n)} k τ^+(k) using the paper's Algorithm 2 cost model. If this sum is not o(n^2/L^{1/√2+o(1)}), then the exceptional cases are not negligible; alternatively, derive an analytic upper bound for this sum and verify that it is absorbed by the claimed exponent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central subquadratic tabulation claim, Theorem 2.9, splits integers k ≤ n into L^γ-smooth and non-smooth classes. For each non-smooth k, the proof writes k = m q with q the largest prime factor and then applies Algorithm 4, whose input specification explicitly requires m < p < q for the previously computed prime p. But when q ≤ m, as in k = p^3 with p > L^γ, this precondition fails. In such cases the largest prime Q with mQ ≤ n may itself be at most m, so no valid starting prime p exists and the nested-rectangle argument of Algorithm 4 cannot be used. The proof gives no alternative treatment for these k, and it does not estimate their contribution to the runtime. Since the number of such k is not shown to be negligible, the claimed O(n^2/L^{1/√2+o(1)}) bound is not established for all k ≤ n.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15316,"tokens_out":12146,"duration_ms":116162,"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":[{"comment":"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.","section":"§2.5, Theorem 2.9"}],"minor_comments":[{"comment":"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.","section":"§2.3, Lemma 2.8"},{"comment":"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.","section":"§4, Table 3"},{"comment":"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.","section":"§2.5, Algorithm 5"},{"comment":"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.","section":"Global"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the incomplete proof of Theorem 2.9. The gap appears fixable, for example by adding a separate argument for the q ≤ m case or by showing that such k can be handled directly with Algorithm 2 at a cost absorbed by the claimed bound. If the authors supply a correct proof, the paper would be a solid contribution. The computational and Monte Carlo sections are strong and should be preserved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading, but the headline subquadratic tabulation theorem has a genuine proof gap. The incremental δ(n) computation (Algorithms 2 and 3) and the resulting O(n^2 log n / Φ(n)) tabulation bound via Ford's corollary are solid, useful contributions. The exact values through n = 2^30, independently verified, and the Monte Carlo variance comparison (Lemma 3.2) are also fine. The first real implementation of Bach/Kalai random factored integers for this problem is a nice touch.\n\nThe problem is Theorem 2.9. In the proof, every non-L^γ-smooth k is written as m q with q the largest prime factor, and Algorithm 4 is invoked, whose precondition is m < p < q. That fails whenever q ≤ m, e.g. k = p^3. More broadly, for any m > sqrt(n), the largest prime Q with m Q ≤ n is < m, so no valid starting prime exists at all. The proof gives no alternative treatment and no runtime bound for these cases. This is not a corner case; it covers a substantial set of non-smooth k. As written, the O(n^2/L^{1/√2+o(1)}) claim is not established.\n\nI agree with the stress-test note. The theorem may be salvageable—perhaps by handling q ≤ m separately and showing those k contribute negligibly—but that is real work, not a typo. The numerical and Monte Carlo sections do not depend on Theorem 2.9; they use Algorithm 3 and look reliable. One minor concern is that the large-n Monte Carlo estimates rely on approximations described only in unpublished slides, so the largest table entries are not as independently checkable as the rest.\n\nThe citation pattern looks fine. The use of Ford's results is appropriate, and the reliance on unpublished slides is the only reproducibility soft spot.\n\nRecommendation: send to peer review, not desk reject. The paper has enough solid content that a serious referee should engage with it, but the proof of Theorem 2.9 needs to be repaired or explicitly downgraded to conditional before publication.","headline":"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.","tokens_in":15959,"tokens_out":6880,"would_cite":true,"duration_ms":74525,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11A25","11N37","11Y16","11Y70","65C05","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["multiplication table","distinct products","M(n)","subquadratic algorithm","smooth numbers","divisor intervals","Monte Carlo estimation","random factored integers"],"falsifier":"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.","tokens_in":14919,"feed_emoji":"🔢","tokens_out":15102,"duration_ms":144027,"temperature":0.7,"pith_summary":"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.","feed_headline":"First subquadratic algorithm tabulates the multiplication table","feed_subtitle":"The distinct-product count for every table size up to n now has a provably subquadratic algorithm.","key_machinery":"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 $pp$, 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.","pith_inferences":[],"forward_implications":["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."],"supporting_citations":[{"why":"Describes the direct quadratic algorithm and the earlier exact computations that the new incremental and subquadratic methods generalize and extend.","marker":"[8]"},{"why":"Gives the asymptotic count of integers up to $n$ with all prime factors at most $L^\\gamma$, which fixes the cost of the smooth half of the split in Theorem 2.9.","marker":"[10]"},{"why":"Contains the mean-value result for the divisor-interval function $\\tau^+(k)$ that Lemma 2.4 uses to bound the running time of the basic shape algorithm.","marker":"[15]"},{"why":"Supplies the procedure for generating random integers together with their prime-power factorizations, which lets both Monte Carlo estimators avoid factoring large integers.","marker":"[2]"}],"fun_headline_variants":["Subquadratic algorithm cracks multiplication table count","Exact multiplication table counts now in subquadratic time","First subquadratic exact tabulation of multiplication table","Multiplication table counts: breaking the quadratic barrier","Subquadratic sieve computes all distinct products up to n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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