{"id":"2e1dbc42-4fae-4358-afbf-df325cb253cc","arxiv_id":"2606.22851","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"New prime enumeration algorithms achieve N (log log N)^{1+o(1)} bit operations in the multitape Turing model, improving prior work by nearly log N via fast polynomial arithmetic over finite fields and error-correcting code ideas.","lead":"This paper presents new algorithms for listing all primes up to a bound N, claiming the first asymptotic improvement over the sieve of Eratosthenes by a positive power of log N. A smart generalist might read it for advances in using fast polynomial arithmetic to speed up fundamental computations in number theory.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Fastest claimed bound rests on explicitly non-rigorous algorithm whose reduction to fast polynomial arithmetic may hide log factors","rationale":"The reader's weakest assumption (hidden logarithmic factors in the polynomial-arithmetic reduction) is precisely the point rendered insecure by the authors' own statement that the fastest version is non-rigorous. No other internal inconsistency is visible from the given material; the concern is therefore the same one already flagged.","tokens_in":1677,"tokens_out":360,"duration_ms":11209,"concrete_test":"Re-derive the bit-complexity recurrence for the non-rigorous sieving step (the reduction to fast multiplication in F_q[x] with q ~ log N) entirely within the multitape Turing model, counting every tape movement and field operation; if the resulting bound is strictly worse than N (log log N)^{1+o(1)} by more than a (log log N)^{o(1)} factor, the headline improvement does not hold.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract states that the N (log log N)^{1+o(1)} algorithm 'is not fully rigorous'. The rigorous Las Vegas variant is slower by an extra (log log N)^{1+o(1)} factor and the deterministic variant by (log N)^{1/2+o(1)}. The central claim of a positive-power log N improvement therefore depends on an incomplete analysis of the sieving-to-polynomial-arithmetic reduction in the multitape Turing model. If that reduction introduces even a single extra log log N factor (e.g., from field arithmetic overheads, tape management, or error-correcting-code constructions), the claimed asymptotic gain disappears and the result collapses to the already-known rigorous bounds.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript presents new algorithms for enumerating primes up to N that rely on fast polynomial arithmetic over finite fields together with techniques from error-correcting codes. The fastest variant is stated to run in N (log log N)^{1+o(1)} bit operations in the multitape Turing model and to improve on Pritchard (1981), Atkin–Bernstein (2004) and Sergeev (2016) by a factor of almost log N; this variant is explicitly described as not fully rigorous. Rigorous Las Vegas and deterministic versions incur extra factors of (log log N)^{1+o(1)} and (log N)^{1/2+o(1)} respectively.","tokens_in":1806,"tokens_out":496,"duration_ms":16581,"significance":"A fully rigorous proof of the stated complexity would constitute a notable advance, being the first improvement by a positive power of log N over the classical sieve of Eratosthenes and its subsequent refinements. The algebraic approach via polynomial arithmetic is a clear methodological strength.","major_comments":[{"comment":"Abstract: the primary claim of a positive-power log N speedup is carried exclusively by the non-rigorous variant whose complexity is N (log log N)^{1+o(1)}. The abstract itself states that this version 'is not fully rigorous', while the rigorous variants are slower by additional (log log N)^{1+o(1)} or (log N)^{1/2+o(1)} factors; therefore the claimed improvement over prior work is not yet supported by a complete analysis.","section":"Abstract"},{"comment":"Abstract (paragraph on polynomial arithmetic): the reduction of the sieving problem to fast polynomial arithmetic over finite fields is asserted to incur no hidden logarithmic factors that would cancel the (log log N)^{1+o(1)} gain. No explicit accounting of all multitape Turing-machine operations (field arithmetic overhead, tape management, or error-correcting-code constructions) is supplied, leaving open the possibility that a single extra log log N factor appears and eliminates the asymptotic improvement.","section":"Abstract"}],"minor_comments":[{"comment":"The abstract would be clearer if it briefly indicated which specific ideas from error-correcting codes are invoked and in which algorithmic step.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and constructive comments. We respond to each major comment below.","responses":[{"response":"We agree that the strongest claimed improvement appears in the non-rigorous variant. The abstract already qualifies the status of this variant. To address the concern about clarity, we will revise the abstract to state the complexities of the rigorous variants more explicitly and to note that the full improvement over prior work is shown only for the non-rigorous case pending further analysis.","revision_made":"yes","referee_comment":"[Abstract] Abstract: the primary claim of a positive-power log N speedup is carried exclusively by the non-rigorous variant whose complexity is N (log log N)^{1+o(1)}. The abstract itself states that this version 'is not fully rigorous', while the rigorous variants are slower by additional (log log N)^{1+o(1)} or (log N)^{1/2+o(1)} factors; therefore the claimed improvement over prior work is not yet supported by a complete analysis."},{"response":"We acknowledge that the current manuscript does not provide an exhaustive enumeration of every multitape Turing-machine operation in the reduction. The analysis relies on standard complexity bounds for the underlying primitives. We will add an expanded discussion or appendix that explicitly bounds the overheads from field arithmetic, tape management, and code constructions to confirm that no additional (log log N) factor arises.","revision_made":"yes","referee_comment":"[Abstract] Abstract (paragraph on polynomial arithmetic): the reduction of the sieving problem to fast polynomial arithmetic over finite fields is asserted to incur no hidden logarithmic factors that would cancel the (log log N)^{1+o(1)} gain. No explicit accounting of all multitape Turing-machine operations (field arithmetic overhead, tape management, or error-correcting-code constructions) is supplied, leaving open the possibility that a single extra log log N factor appears and eliminates the asymptotic improvement."}],"tokens_in":1402,"tokens_out":428,"duration_ms":25795,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"Harvey claims the first speedup by a positive power of log N for enumerating primes up to N. The fastest algorithm runs in N (log log N)^{1+o(1)} bit operations but is not fully rigorous. The rigorous randomized version is slower by another (log log N)^{1+o(1)} factor, and the deterministic one by (log N)^{1/2+o(1)}.\n\nThe new approach uses fast polynomial arithmetic over finite fields together with ideas from error-correcting codes. This marks a shift from the combinatorial optimizations in Pritchard, Atkin-Bernstein, and Sergeev's work. The paper presents these variants clearly in the abstract.\n\nThe methods appear to be a solid attempt to bring modern algebraic tools to an old problem. If the analysis holds, the improvement is meaningful within algorithmic number theory.\n\nThe main concern is whether the reduction from the sieving task to polynomial arithmetic introduces hidden logarithmic factors that would erase the claimed gain. The multitape Turing model analysis needs to be tight, and the non-rigorous status of the best bound makes it necessary to check the details carefully. The abstract is honest about this limitation.\n\nThis paper is for specialists in computational number theory who track improvements in sieve algorithms. A reader working on related complexity questions would get value from seeing how the polynomial methods are applied here.\n\nIt deserves serious peer review. The claim is important enough in its area that referees should examine whether the reduction works without extra factors and whether the rigorous versions are correctly bounded.","headline":"Harvey claims the first log-power speedup for prime enumeration using polynomial arithmetic over finite fields, but the strongest bound is non-rigorous and the reduction may hide extra factors.","tokens_in":2301,"tokens_out":390,"would_cite":false,"duration_ms":21718,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"New algorithms enumerate all primes up to N in N (log log N)^{1+o(1)} bit operations.","keywords":["prime enumeration","sieve of Eratosthenes","fast polynomial arithmetic","finite fields","error-correcting codes","bit complexity","multitape Turing machine"],"falsifier":"A concrete multitape Turing machine analysis or implementation for N around 10^12 that shows the observed bit operations exceed N (log log N)^{1.5} or fail to beat prior sieves by a factor approaching log N.","tokens_in":2556,"feed_emoji":"","tokens_out":641,"duration_ms":31287,"temperature":0.7,"pith_summary":"The paper presents new algorithms for finding every prime up to a bound N. These achieve the first improvement by a positive power of log N over the classic sieve of Eratosthenes. The fastest version runs in N (log log N)^{1+o(1)} bit operations under the multitape Turing model. The method reduces the sieving task to fast polynomial arithmetic over finite fields and incorporates ideas from error-correcting codes. Rigorous randomized and deterministic variants are given at the cost of additional logarithmic factors.","feed_headline":"New method lists primes to N in N (log log N) time","feed_subtitle":"First speedup by a positive power of log N over the Eratosthenes sieve via fast polynomial arithmetic over finite fields.","key_machinery":"Fast polynomial arithmetic over finite fields, used to compute convolutions or products that mark composite numbers during sieving.","core_discovery":"By reducing the problem of sieving for primes up to N to fast polynomial arithmetic over finite fields, the bit complexity of prime enumeration drops to N (log log N)^{1+o(1)}, which improves on the N log log N time of the sieve of Eratosthenes by a positive power of log N.","pith_inferences":["The same polynomial reduction technique might apply to other sieving tasks such as finding smooth numbers or twin primes.","Practical code could test whether the asymptotic gains appear in real-world runtimes for N near 10^15.","Connections between finite-field polynomials and combinatorial sieves may extend to related problems in analytic number theory."],"forward_implications":["The fastest algorithm improves on Pritchard (1981), Atkin-Bernstein (2004) and Sergeev (2016) by almost a factor of log N.","A rigorous randomized Las Vegas variant runs slower by an extra (log log N)^{1+o(1)} factor.","A rigorous deterministic variant runs slower by an extra (log N)^{1/2+o(1)} factor.","The approach draws on error-correcting codes to support the polynomial arithmetic reductions."],"fun_headline_variants":["Faster prime enumeration in N (log log N) time","Primes to N via fast polynomial arithmetic","Improved sieve beats Eratosthenes by log N","Prime enumeration at N (log log N)^{1+o(1)}","Finite field polynomials speed prime listing"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The reduction of sieving to polynomial arithmetic over finite fields introduces no hidden logarithmic factors that cancel the claimed improvement.","fun_headline_variants_meta":{"raw":{"variants":["Faster prime enumeration in N (log log N) time","Primes to N via fast polynomial arithmetic","Improved sieve beats Eratosthenes by log N","Prime enumeration at N (log log N)^{1+o(1)}","Finite field polynomials speed prime listing"]},"model":"grok-4.3","cost_usd":0.005512,"raw_usage":{"total_tokens":2617,"prompt_tokens":609,"num_sources_used":0,"completion_tokens":74,"cost_in_usd_ticks":55124500,"prompt_tokens_details":{"text_tokens":609,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1934,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":609,"tokens_out":74,"duration_ms":11443,"temperature":1.0,"reasoning_tokens":1934,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T07:34:40.941350+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete multitape Turing machine analysis or implementation for N around 10^12 that shows the observed bit operations exceed N (log log N)^{1.5} or fail to beat prior sieves by a factor approaching log N.","supporting_citations":[],"review_version":1}