{"id":"6f13e0bb-e7bd-4236-b848-210b9498e64f","arxiv_id":"2506.07386","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A modified Dirichlet-hyperbola algorithm computes Φ(n) in Θ(n^{2/3}(ln ln n)^{1/3}) time and Θ(n^{1/3}(ln ln n)^{2/3}) space, and produced the first computation of Φ(10^19).","lead":"This paper gives an algorithm that computes the totient summatory function Φ(n) in roughly n^(2/3) time using only about n^(1/3) memory, a large reduction from the square-root memory of earlier practical methods. It uses the algorithm to compute the first known value of Φ(10^19), a new record in this sequence.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The n^{2/3}(ln ln n)^{1/3} time bound is not proven: Lemma 4's interior-batch analysis rests on Lemma 14, whose crossover split appears reversed, so the key Θ(a ln(n^2 a^{-3})) estimate lacks a valid derivation.","rationale":"The paper makes a plausible and apparently correct algorithmic contribution: the phase structure is coherent, the OEIS checks for n = 13..18 match, the new Φ(10^19) value was run twice, and the reported memory is far below the √n storage that the older methods require. These are real supporting data. However, the asymptotic time theorem is not rigorously established. The reader's flagged Lemma 5 is not the load-bearing weakness, because the saved v-values are exactly consecutive and the contribution is only O(√n ln n), which is negligible compared with n^{2/3}. The genuinely load-bearing step is Lemma 4's interior-batch analysis via Lemma 14: the printed integral split has reversed or incompatible limits, so the claimed Θ(a ln(n^2 a^{-3})) bound is unproved as written. Since line 13.27 is the only nontrivial phase-1/2 inner loop whose estimated cost is close to the target, an error there could invalidate the headline time bound. A numerical count of exact loop executions for moderate n would quickly reveal whether the final estimate is numerically credible. The correctness proof being asserted rather than formalized is a secondary concern, especially because no implementation is shipped. The appropriate verdict remains CONDITIONAL: conditional on a corrected, verifiable proof of Lemma 14 (or an independent bound on line 13.27) and ideally on a released implementation with explicit parameters.","tokens_in":20192,"tokens_out":22873,"duration_ms":239214,"concrete_test":"Write a script that, for n = 10^9, 10^12, and 10^15, with a = ⌊(n/ln ln n)^{2/3}⌋, b = ⌊n/a⌋, and the χ, s progression of Algorithm 13, counts the exact number of executions of line 13.27 over all batches using the defined ℓmin and ℓmax. Compare the interior-batch count (excluding first and last) with Θ(a ln(n^2 a^{-3})) and the total with Θ(n^{2/3}(ln ln n)^{1/3}). If the interior count deviates by more than a small constant factor, or if the total exceeds the stated rate, Lemma 14's estimate is falsified; if it matches, the gap is a rigor issue rather than a false claim.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central upper bound in Theorem 7 depends on excluding super-Θ(n^{2/3}) work in line 13.27. Lemma 4, which does this, is the load-bearing step. Its proof splits line 13.27 into first/last batches and interior batches; the interior estimate is delegated to Lemma 14. In Lemma 14, after substituting u = bχ + 1 and setting T = n/(u-b)^2, the text says 'for lesser t, the first argument prevails' and then writes the inner integral as ∫_b^T ... dt + ∫_T^1 ... dt. For most u in [1+2b, 1+√n], T is much larger than b (near u = 2b, T ≈ a = n/b ≫ b), so the first integral has limits reversed relative to the original t ∈ [1,b], and the second integral has nonstandard reversed limits as well. Consequently the displayed Θ(a ln(n^2 a^{-3})) total is not obtained by a valid sequence of integral manipulations; it may be true, but it is not established. This matters: if the true interior-batch count were, say, Θ(a ln b), line 13.27 would contribute n^{2/3}(ln n)(ln ln n)^{-2/3}, which dominates the claimed bound. The proof of correctness is also asserted rather than demonstrated. The reader's Lemma 5 concern is not the weakest point: the saved phase-2 values are v = ⌊n/χ⌋, which are exactly consecutive s-values by the identity ⌊n/⌊n/s⌋⌋ = s for s ≤ √n, and the whole Lemma 5 contribution is only O(√n ln n), far below the claimed bound.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an algorithm (Algorithm 13) for computing the totient summatory function Φ(n) in claimed time Θ(n^{2/3}(ln ln n)^{1/3}) and space Θ(n^{1/3}(ln ln n)^{2/3}), starting from an existing Mertens-first Dirichlet-hyperbola algorithm and progressively reordering its loops to eliminate the need to store the Mertens array M′ beyond index b. The author reports a new computation Φ(10^19) = 30396355092701331435065976498046398788, alongside reproductions of known values for 10^13 through 10^18.","tokens_in":20577,"tokens_out":4974,"duration_ms":51912,"significance":"If the complexity claims and the computed value are correct, the paper makes a useful contribution: it lowers the space requirement from Θ(n^{1/2}) to soft-Θ(n^{1/3}) with essentially the same soft-O(n^{2/3}) runtime, and it provides a new, independently reproducible computational data point. The paper is honest in reporting wall-clock times and memory, and the verification against OEIS A064018 for smaller n strengthens confidence in the implementation. The algorithm is also described with enough pseudocode detail that an expert could reimplement it. However, the rigorous derivation of the central time bound is incomplete, and the correctness of the batched loop transformations is asserted rather than proved, so the significance is conditional on a repaired analysis.","major_comments":[{"comment":"The proof of Lemma 14, which provides the crucial estimate Θ(a ln(n^2 a^{-3})) for line 13.27, contains an invalid integral manipulation. After the substitution u = bχ + 1 and the definition T = n/(u−b)^2, the text states that 'for lesser t, the first argument prevails' and then splits the inner integral as ∫_b^T ... dt + ∫_T^1 ... dt. But for the relevant range u ∈ [1+2b, 1+√n], T is in fact smaller than b throughout: at u = 1+2b, T ≈ n/b^2 = a^2/n ≈ n^{1/3}(ln ln n)^{−4/3}, while b ≈ n^{1/3}(ln ln n)^{2/3}; at u = 1+√n, T ≈ 1. Hence the first integral should run from T to b, and the second from 1 to T; writing the limits in reverse order changes the sign. The subsequent equality chain treats these oriented integrals as positive quantities, so the displayed Θ(a ln(n^2 a^{-3})) is not obtained by a valid sequence of estimates. Since Lemma 14 is the load-bearing estimate that prevents line 13.27 from exceeding the target Θ(n^{2/3}(ln ln n)^{1/3}) time, Theorem 7's upper bound is currently unproved.","section":"Lemma 14 (Section 4)"},{"comment":"The proof of Theorem 7 states that 'the correctness of the algorithm is evident by its development' and provides no formal equivalence proof for the batched loop reorderings. This matters because the transformations leading from Algorithm 1 to Algorithm 13 are nontrivial: Algorithms 9, 12, and 13 replace inner loops with batched updates that change the order of accumulation and introduce conditions such as (4), and line 13.38 is not visibly equivalent to the original line 10.50. The paper should supply an invariant or a bijection between the pairs (y, t, ℓ) processed in the batched versions and the pairs (y, x) in the original loop, so that a reader can verify that each M′ entry receives exactly the same set of contributions.","section":"Theorem 7 proof (Section 4)"},{"comment":"The proof of Lemma 5 relies on the approximation that the k-th Mertens value saved during phase 2 has index x ≈ n/(√n − k), and that batches therefore have A ≈ √n − b(j−1) and B ≈ √n − bj. No rigorous error bound or justification for this approximation is given. Since the total contribution of line 13.38 is claimed to be Θ(√n ln b), which is below the target bound, a rigorous bound with a constant factor would likely suffice; nevertheless, the current proof is heuristic and does not establish the stated Θ(√n ln b) claim in the form used.","section":"Lemma 5 (Section 4)"}],"minor_comments":[{"comment":"The notation eΘ is used without a formal definition; please define it explicitly (e.g., up to polylogarithmic factors).","section":"Section 1.1 and throughout"},{"comment":"The assignment a ← ⌊eΘ(n^{2/3})⌋ is not a concrete algorithmic instruction, since eΘ hides constant and logarithmic factors. For an algorithm to be reproducible, a should be set to a specific function, for example a = ⌊c (n/ln ln n)^{2/3}⌋ with an explicit constant c, and the analysis should state how the constant affects the Θ bounds.","section":"Algorithm 1 line 1.1 and Algorithm 13 line 13.1"},{"comment":"The introductory formula writes Φ(n) = Σ_{k=1}^n φ(n); this is a typo and should be φ(k).","section":"Section 1"},{"comment":"There are several typographical inconsistencies, including 'M¨obius' (encoding artifacts), 'parmeter' in the proof of Theorem 7, and 'modifed' in Section 2. A careful proofreading pass is recommended.","section":"Throughout"},{"comment":"It would be helpful to state the exact value of a used for each run, or at least the asymptotic parameter choice, so that the reported timings can be interpreted and the run is reproducible.","section":"Section 5, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a computational number theory venue and the reported computation is interesting, but the central complexity theorem currently rests on Lemma 14, whose proof appears to contain a sign/orientation error that invalidates the derivation. This is not a matter of style or a missing reference; it is a load-bearing technical gap. The author may well be able to repair the proof, since the final bound is plausible and the computations are consistent, but the manuscript in its present form does not establish the claimed Θ(n^{2/3}(ln ln n)^{1/3}) time bound. I would support a major-revision decision with the expectation that the author either supplies a corrected integral analysis for Lemma 14 or revises the stated complexity claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the algorithmic idea is real, the new Φ(10^19) is a nice data point, but the proof of the headline time bound has a concrete error in Lemma 14, so I wouldn't take the Θ(n^{2/3}(ln ln n)^{1/3}) claim at face value yet.\n\nWhat's genuinely new: the space reduction from Θ(√n) to Θ(n^{1/3}) by batching Mertens values and swapping loop order in the Macris algorithm. That's a clever, practical trick. The paper is honest about its lineage, and the small-n values match OEIS. The 10^19 computation was run twice and the timings scale roughly as claimed.\n\nThe soft spot is in the analysis. Lemma 4's bound for line 13.27 is delegated to Lemma 14. In the proof of Lemma 14, after substituting u = bχ + 1 and setting T = n/(u-b)^2, the text splits the t-integral over [1,b] as ∫_b^T ... + ∫_T^1 ... . That is not a valid split. For most u in the range, T ≫ b, so the first integral ranges outside [1,b] and the second has reversed limits. The displayed Θ(a ln(n^2 a^{-3})) total therefore is not actually derived. Since Lemma 4 is the load-bearing step for the upper bound in Theorem 7, the headline time complexity is unproven as written. It may be true, but the argument doesn't show it.\n\nThe reader's worry about Lemma 5 is not the real issue; the saved phase-2 values are exactly the consecutive floor(n/x) values, and that contribution is only O(√n ln b). The bigger gap is the integral error and the fact that correctness is asserted 'evident by its development' rather than demonstrated. Also, no code is shipped, which makes it harder to check the finer details of the loops.\n\nWho should read this: anyone working on practical algorithms for summatory functions. The batching idea is worth borrowing, and the new value is a real data point. But the paper needs a corrected Lemma 14 (or a different proof) before I'd trust the asymptotic claim.\n\nRecommendation: send it to peer review. A referee who checks Lemma 14 carefully can tell whether the bound is repairable. This is not a desk reject; it's a paper with a promising core and a proof gap that needs real work.","headline":"Genuinely useful space-reduction trick and a new Φ(10^19), but the key time bound depends on an integral split in Lemma 14 that doesn't work as written.","tokens_in":21090,"tokens_out":3605,"would_cite":true,"duration_ms":37009,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11Y16","11-04","11A25","11Y55","11Y70"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes an algorithm that computes the totient summatory function in nearly n^{2/3} time with only cube-root memory, and reports a new value at 10^19.","keywords":["totient summatory function","Euler's totient","Mertens function","Möbius function","Dirichlet hyperbola method","segmented sieve","space-time tradeoff","A064018"],"falsifier":"Instrument a run of Algorithm 13 to count hits to line 13.38 and to record the saved Mertens indices x and batch bounds A and B; if the total hit count differs from Theta($\\sqrt$(n) ln b) by more than a constant factor, the time bound in Theorem 7 does not follow. A separate direct check is to compute Phi(n) by brute-force summation for n up to $10^{8}$ and compare with the algorithm's output; any mismatch would refute the claimed correctness.","tokens_in":19944,"feed_emoji":"🧮","tokens_out":11683,"duration_ms":110676,"temperature":0.7,"pith_summary":"This paper tries to show that the totient summatory function $\\Phi(n)=\\sum_{k\\le n}\\phi(k)$ can be computed in $\\widetilde{\\Theta}(n^{2/3})$ time while storing only $\\widetilde{\\Theta}(n^{1/3})$ integers, a cube-root memory footprint. The route is to take the known Mertens-first Dirichlet-hyperbola algorithm, which needs $\\Theta(\\sqrt n)$ storage, and reorganize its loops so that Mertens values are accumulated in blocks and flushed into a short array $M'$ of length about $n^{1/3}$ instead of being kept all at once. A reader should care because the memory reduction is what lets the computation advance from the desktop-limited value $\\Phi(10^{18})$ to the new value $\\Phi(10^{19})=30396355092701331435065976498046398788$, reported after two agreeing runs. The paper's own analysis sets the optimal balance at $a=\\Theta((n/\\ln\\ln n)^{2/3})$, giving $\\Theta(n^{2/3}(\\ln\\ln n)^{1/3})$ time and $\\Theta(n^{1/3}(\\ln\\ln n)^{2/3})$ space.","feed_headline":"Totient sums reach 10^19 using cube-root memory","feed_subtitle":"A loop-reordered Mertens-first algorithm does it in about 9 days on 7 GB, extending the known totient sum.","key_machinery":"The load-bearing object is the short accumulator array $M'$, indexed from 1 to $b$, which holds the partial contributions to the $Y$ sum in the hyperbola formula. The carrying identity is $\\Phi=\\mu*\\mathrm{id}$ decomposed by the Dirichlet hyperbola method into an $X$ sum over Möbius values, a $Y$ sum over Mertens values, and an overlap correction $Z$; the workhorse is the loop reordering that turns the phase-3 Mertens loop into phase-1 and phase-2 updates, so that no Mertens value beyond $b$ needs to be kept. When a batch of saved Mertens values fills the temporary array $M$, condition (4) determines which pairs $(y,t)$ receive each stored value, and the batch is flushed into $M'$.","core_discovery":"The central claim is Theorem 7: with $a=\\Theta((n/\\ln\\ln n)^{2/3})$, Algorithm 13 evaluates the identity $\\Phi(n)=\\sum_{x\\le a}\\mu(x)\\lfloor n/x\\rfloor(\\lfloor n/x\\rfloor+1)/2 + \\sum_{y\\le b} y\\,M(\\lfloor n/y\\rfloor) - b(b+1)M(a)/2$ in $\\Theta(n^{2/3}(\\ln\\ln n)^{1/3})$ time and $\\Theta(n^{1/3}(\\ln\\ln n)^{2/3})$ space, where $M(k)=\\sum_{i\\le k}\\mu(i)$ is the Mertens function and $b=\\lfloor n/a\\rfloor$. The discovery is that the $\\Theta(\\sqrt n)$ arrays of stored Möbius and Mertens values in the earlier algorithm can be replaced by an array $M'$ of length $b$ plus a temporary batch array $M$ of length $b$, because every contribution that the third phase needs can be precomputed into $M'$ during the first two phases by summing over $x$ first rather than over $y$. That reorganization is what makes the reported $\\Phi(10^{19})$ computation feasible in less than nine days and about 6.6 GB.","pith_inferences":["The same block-flush idea should transfer to other summatory functions evaluated by the Dirichlet hyperbola method with a Mertens-type prefix, potentially lowering their space from square-root to cube-root scale at a log-log factor cost; the paper only applies it to $\\Phi$.","The large wall-clock jump between $10^{18}$ and $10^{19}$ suggests multiword arithmetic dominates at $10^{19}$; if so, a tighter big-integer implementation should bring the runtime back toward the asymptotic ratio, which is a testable prediction.","Lemma 5's saved-index approximation $x\\approx n/(\\sqrt n-k)$ can be checked empirically by instrumenting phase 2; such a check would either confirm the $\\Theta(\\sqrt n\\ln b)$ bound or pinpoint where the proof needs repair."],"forward_implications":["With optimal parameters, Algorithm 13 achieves $\\Theta(n^{2/3}(\\ln\\ln n)^{1/3})$ time and $\\Theta(n^{1/3}(\\ln\\ln n)^{2/3})$ space, so the asymptotic time loss relative to the square-root-space version is only a $(\\ln\\ln n)^{1/3}$ factor.","The new value $\\Phi(10^{19})=30396355092701331435065976498046398788$ extends the sequence by one term and was verified by running the computation twice; the values at $10^{13},\\dots,10^{18}$ match the previously published ones.","The space reduction means the algorithm can run in a few gigabytes rather than needing the $\\Theta(\\sqrt n)$ integers that put $10^{19}$-scale compute out of reach of a desktop machine.","The phase-3 loop simplification, using the bound $n/(b+1)\\ge\\lfloor v/t\\rfloor$ to break early, makes the final Mertens sweep cost only $\\Theta(b\\ln b)$ time."],"supporting_citations":[{"why":"Supplies Algorithm 1, the Mertens-first totient-sum algorithm in nearly n^{2/3} time and square-root-n space that Algorithm 13 is built from; its four-phase loop structure is the object being reorganized.","marker":"[6]"},{"why":"Provides the elementary hyperbola-based algorithm for Phi(n) and its space-time tradeoffs, the comparison point showing why square-root-n storage is the practical bottleneck.","marker":"[4]"},{"why":"Gives one of the previously known nearly n^{2/3}-time algorithms that computed Phi up to 10^18, setting the prior record that the new computation extends.","marker":"[5]"},{"why":"Supplies the subquadratic individual-Mertens computation used in Section 2 to derive the balance point for the hyperbola formula; frames the time estimate the paper's algorithm improves upon.","marker":"[1]"},{"why":"Shows an even faster individual Mertens computation, used in the same Section 2 comparison as an alternative ingredient for evaluating the hyperbola formula.","marker":"[2]"}],"fun_headline_variants":["Totient sums reach 10^19 with cube-root memory","Mertens reordering computes totient sums in n^(2/3) time","Phi(10^19) computed with n^(1/3) memory in 9 days","Cube-root storage for totient summatory function","Loop reorder cuts totient sum storage to n^(1/3)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claimed running time depends on the unproved approximation that the k-th Mertens value saved during the middle phase has index near n/(sqrt(n)-k), and the algorithm's correctness is stated as evident from its construction rather than proved.","fun_headline_variants_meta":{"raw":{"variants":["Totient sums reach 10^19 with cube-root memory","Mertens reordering computes totient sums in n^(2/3) time","Phi(10^19) computed with n^(1/3) memory in 9 days","Cube-root storage for totient summatory function","Loop reorder cuts totient sum storage to n^(1/3)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000251,"raw_usage":{"total_tokens":1536,"prompt_tokens":906,"completion_tokens":630,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":536}},"tokens_in":522,"tokens_out":630,"duration_ms":6176,"temperature":1.0,"reasoning_tokens":536,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:36:37.512779+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument a run of Algorithm 13 to count hits to line 13.38 and to record the saved Mertens indices x and batch bounds A and B; if the total hit count differs from Theta($\\sqrt$(n) ln b) by more than a constant factor, the time bound in Theorem 7 does not follow. A separate direct check is to compute Phi(n) by brute-force summation for n up to $10^{8}$ and compare with the algorithm's output; any mismatch would refute the claimed correctness.","supporting_citations":[{"cited_title":"Summing µ(n): a faster elementary algo- rithm","cited_arxiv_id":null,"evidence_quote":"Supplies Algorithm 1, the Mertens-first totient-sum algorithm in nearly n^{2/3} time and square-root-n space that Algorithm 13 is built from; its four-phase loop structure is the object being reorganized."},{"cited_title":"and µ(x) ̸= 0","cited_arxiv_id":null,"evidence_quote":"Provides the elementary hyperbola-based algorithm for Phi(n) and its space-time tradeoffs, the comparison point showing why square-root-n storage is the practical bottleneck."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the subquadratic individual-Mertens computation used in Section 2 to derive the balance point for the hyperbola formula; frames the time estimate the paper's algorithm improves upon."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows an even faster individual Mertens computation, used in the same Section 2 comparison as an alternative ingredient for evaluating the hyperbola formula."}],"review_version":1}