{"id":"2459366e-0ac1-479b-a079-a40eb0861504","arxiv_id":"2509.10188","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Constant-time-with-preprocessing (CstPP) is unchanged for any polynomial preprocessing time or any primitive set containing addition, but collapses with sub-polynomial preprocessing or unary-only primitives.","lead":"This paper defines CstPP, the class of arithmetic operations computable in constant time after O(N) preprocessing on a RAM, and proves it is robust under choices of primitive operations and preprocessing time. The result gives a stable target for preprocessing-based algorithm design and lower bounds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's reduction proof relies on the false inequality N^d ≤ floor(N^{1/c})^{cd}; Lemma 4.1 fails for operands near N^d.","rationale":"The reader's weakest-assumption was the unproven Proposition 1 from the companion paper, used only in Theorem 11. I find a more immediate, internal flaw: Lemma 4 item 1 is false under the paper's explicit definition N_1 := floor(N^{1/c}). The proof of Theorem 5 asserts N^d ≤ N_1^{cd}, which is the reverse of the truth and fails for concrete values (N=15,c=2,d=1). This is load-bearing because Theorem 5 is the main result that preprocessing can be reduced to N^{1/c}, and Theorem 6 uses the same conversion. The paper's Algorithm 3 computes ceil, not floor, so the fix is straightforward; nevertheless, as written the proof of a central theorem is invalid. Thus I do not change the overall CONDITIONAL verdict, but I disagree with the reader about where the main risk lies: it is inside this paper's Lemma 4/Theorem 5, not in the external companion paper. A concrete numerical test settles the issue immediately, and the authors can repair the proof by consistently using ceil(N^{1/c}) and adjusting the inequalities in Lemma 4 and Section 5.","tokens_in":43650,"tokens_out":12719,"duration_ms":134597,"concrete_test":"Instantiate the conversion in Lemma 4.1 as used in Theorem 5 with c=2, d=1, N=15, X=10. With N_1=floor(sqrt(15))=3 and cd=2, X=10 has base-3 representation 101, requiring 3 registers; the lemma asserts 2 suffice. This directly falsifies the claimed inequality N^d ≤ floor(N^{1/c})^{cd}. A corrected version using N_1=ceil(N^{1/c})=4 would give N^d=15 ≤ 16 and the conversion works; run the same example to confirm the fix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest point is not the external Proposition 1 but the internal proof of Theorem 5 (and Theorem 6, which uses Lemma 4). Section 5.1 states: 'all operands x_1,...,x_k < N^d are less than (N_1)^{cd}' with N_1 := floor(N^{1/c}). This inequality is backwards: floor(N^{1/c})^c ≤ N, so floor(N^{1/c})^{cd} ≤ N^d. For c=2, d=1, N=15, N_1=3, we have (N_1)^{cd}=9 < 15. Lemma 4 item 1 claims every X < N^d fits in cd base-N_1 digits; taking X=10, its base-3 representation is 101, needing 3 digits while cd=2. Thus the lemma is false as stated, and the operation phase of Theorem 5 overflows for operands in [N_1^{cd}, N^d). The paper's own Algorithm 3 actually computes the ceiling (its invariant is (x-1)^c < N ≤ x^c), so the proof becomes salvageable by defining N_1 := ceil(N^{1/c}); but as written, the central preprocessing-time robustness theorem is not proven.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the complexity class CstPP of operations computable in constant time after O(N) preprocessing on a RAM whose only primitive operation is addition, and shows that the class is robust: it is invariant under enlarging the primitive operation set, under increasing preprocessing time to any fixed polynomial, and under reducing preprocessing time to N^epsilon for any fixed positive epsilon < 1 (provided +, div, mod are available). The paper also proves closure under composition, closure under inverse for fast-growing functions, reductions of constant-time procedures to single addition expressions, and two minimality results showing that the class degenerates if preprocessing is subpolynomial or if addition is replaced by unary operations. The central claimed results are Theorems 5 and 6 on preprocessing-time robustness, Theorem 8 on minimality of linear preprocessing, and Theorem 11 on inverse closure.","tokens_in":43988,"tokens_out":10447,"duration_ms":116522,"significance":"If the results hold, they give a genuinely robust and extensive theory of constant-time computation with preprocessing. The paper is careful in several places: the cardinality argument in Theorem 8 is detailed and convincing, the use of lock-step simulation in Lemma 2 is principled, and the paper identifies precise open problems. The claim that the class is unchanged when preprocessing time is increased to N^c or reduced to N^epsilon, and that it degenerates at N^{o(1)}, is interesting and would substantially strengthen the framework initiated in the companion paper [25]. The proof of Theorem 8 in particular is a strong point: it is a rare lower-bound argument that does not rely on unproved assumptions about the RAM model. However, the main robustness theorem is not proven as written because of a false inequality in Section 5, and one load-bearing lemma is false as stated. These issues appear locally repairable, but they require a revised manuscript.","major_comments":[{"comment":"The proof of Theorem 5 states that all operands x_i < N^d are less than (N_1)^{cd} with N_1 := floor(N^{1/c}). This inequality is false: floor(N^{1/c})^c <= N, so (N_1)^{cd} <= N^d. For c=2, d=1, N=15, we have N_1=3 and (N_1)^{cd}=9, while x=10 is a valid operand. Consequently Lemma 4(1), which claims that every X < N^d has a radix-N_1 representation in cd registers, is false as stated: 10 has base-3 representation 101, needing 3 digits, not cd=2. The operation phase of Theorem 5 overflows on operands in [N_1^{cd}, N^d). The proof can be repaired by taking N_1 := ceil(N^{1/c}), since then N <= N_1^c and hence N^d <= N_1^{cd}; the paper's own Algorithm 3 actually computes the ceiling, not the floor. But as written, the central preprocessing-time robustness theorem is not established.","section":"Section 5.1, Lemma 4 and Theorem 5"},{"comment":"The same floor/ceiling error appears in the proof of Theorem 6. The text sets N_1 := floor(N^{1/c}) and later asserts 'Noting that N^d <= (N_1)^{cd}', which is false for the same reason. The intended argument works with N_1 := ceil(N^{1/c}), since then (N_1)^{cd} >= N^d and, for fixed c, (N_1)^{cd} < (N^{1/c}+1)^{cd} <= N^{d+1} for N >= 2^{cd}. The proof should be corrected consistently in both directions of the robustness claim.","section":"Section 5.2, Theorem 6"},{"comment":"The proof of Lemma 4(1) is not justified within the RAM model. It says to set X_0 <- X and then repeatedly X_{i+1} <- X_i div N_1, as if X were a single integer variable. But operands X < N^d are represented in d base-N registers, and a register/variable may only contain O(N). The conversion from base N to base N_1 therefore requires a multi-register procedure, e.g. Horner's method in base N_1, and the constant-time nature of that procedure for fixed d and c is not proved. Since Theorem 5 depends on this conversion in its operation phase, this is a load-bearing gap. The intended construction is plausible, but it needs to be written out at the level of the multi-memory RAM conventions.","section":"Lemma 4, Item 1"},{"comment":"The forward direction of Theorem 11 uses floor(log_2 f(y)) to bucket the candidates for f^{-1}(x). This use is justified entirely by Proposition 1, which is stated as 'we admit here' with no proof in this manuscript. The paper claims to be readable independently, but Proposition 1 is load-bearing: if the logarithm membership result from [25] were unavailable, the inverse-closure theorem would not follow. The authors should either include a proof (or a precise pointer to the corresponding theorem of [25]) and state exactly which special case of Proposition 1 is needed. This is a dependency, not a circularity, but it is currently missing support within the manuscript.","section":"Section 8, Proposition 1"}],"minor_comments":[{"comment":"The comment in Algorithm 3 and the surrounding text say the algorithm computes x := floor(N^{1/3}). The loop invariant (x-1)^3 < N <= x^3 shows that it computes the ceiling, i.e. the least x with x^3 >= N. With the ceil correction to N_1 this is exactly what is needed, but the terminology should be fixed.","section":"Section 5.1, Algorithm 3"},{"comment":"The notation 'A_div[B^2-1]' and the description of the tables for (Br+x) div y and (Br+x) mod y are terse and ambiguous. The reader has to infer that these are one-dimensional arrays indexed by B*x+y. Please define the indexing convention explicitly, as is done for the multiplication table.","section":"Section 4, one-digit division"},{"comment":"The abstract uses the lower-case 'cstPP' while the body uses 'CstPP'. Please unify the notation.","section":"Abstract and throughout"},{"comment":"The footnote about avoiding circular dependencies in the comparison x^3 < N is unnecessarily contorted, since the theorem is stated for RAM(+,div,mod), where div and mod are primitive. Simplify or remove.","section":"Section 5.1, footnote"},{"comment":"The phrase 'there is an integer y satisfying the following inequalities' in the preprocessing part is not fully constructive as written: the completion of empty lists should specify how that y is found. The subsequent Claim 7 makes the size bound clear, but the construction of the completed lists should be made explicit.","section":"Section 8, proof of Theorem 11"}],"recommendation":"major_revision","confidential_remarks":"The main theorems are likely correct after a local repair: replace floor(N^{1/c}) with ceil(N^{1/c}) in Section 5 and provide the missing multi-register conversion details in Lemma 4. I do not see a reason to reject, but the current text contains a false lemma and an invalid inequality in the central proof, so the revision must be reviewed again. The dependence on Proposition 1 from [25] is acceptable only if the companion paper is available and the citation is precise; otherwise the self-containedness claim should be weakened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a serious theory paper, mostly self-contained, and the new results are real. But the proof of Theorem 5 (preprocessing time robustness) has a concrete error: Lemma 4.1 uses N_1 := floor(N^{1/c}) and asserts every X < N^d has cd base-N_1 digits. That's false, since floor(N^{1/c})^cd ≤ N^d, so operands near N^d overflow. The paper's own Algorithm 3 actually computes ceil(N^{1/c}), which would make the lemma true, so the fix is local. Still, as written, the central robustness claim is not proven.\n\nWhat is genuinely new and works: the Fundamental Lemma with lock-step simulation, the invariance of CstPP under primitive operations (Theorem 4), the composition closure (Theorem 3), the minimality results (Theorems 8 and 9), and the inverse closure for fast-growing functions (Theorem 11) are substantial. The cardinality argument for Theorem 8 is careful and convincing. The addition-expression normal form (Theorem 10) is a nice structural result.\n\nSoft spots: (1) the floor/ceil bug above; (2) Theorem 11 relies on Proposition 1 from the companion paper [25] (x^y and log in CstPP), admitted without proof — a real dependency, not circular, but the forward direction falls if that companion result is wrong; (3) several details in Section 4 (one-digit division, Claims 5 and 6) are deferred to the reader; those are probably routine but should be spelled out or referenced precisely.\n\nOverall: the paper deserves a serious referee. The fix for Theorem 5 is easy, but a referee must verify it doesn't cascade. If the authors replace floor with ceil consistently, the robustness theorem likely holds. For a reader in database enumeration or fine-grained complexity, this is worth engaging with. I'd send it out, with the explicit request to fix the N_1 definition.","headline":"Solid, extensive theory with one genuinely broken inequality in the main robustness proof — fixable, but as written Theorem 5 doesn't go through.","tokens_in":44408,"tokens_out":3541,"would_cite":true,"duration_ms":37403,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the class of operations computable in constant time after O(N) preprocessing is invariant under changing preprocessing to any polynomial or to N^epsilon for any epsilon>0, and degenerates at N^{o(1)}.","keywords":["CstPP","constant time","linear preprocessing","RAM model","robust complexity class","inverse functions","Fibonacci","factorial"],"falsifier":"Run Algorithm 3's computation of floor(N^{1/3}) for a large N (say 10^12) using only +, div, and mod, and check both the step count (about N^{1/3}) and the correctness of the translated loop condition; a failure there would undermine Theorem 5's claimed reduction of preprocessing time.","tokens_in":43543,"feed_emoji":"⚡","tokens_out":6023,"duration_ms":59400,"temperature":0.7,"pith_summary":"The paper studies CstPP: operations on integers that can be answered in constant time by a RAM that first builds tables in O(N) time. It argues that the class is robust: the same operations are computed if preprocessing is reduced to N^epsilon (for any fixed epsilon>0) or increased to N^c (for any fixed c>1), provided the RAM has +, div, and mod as primitive operations. It also proves closure under composition and, for fast-growing functions, closure under inverse, so the inverses of Fibonacci and factorial are constant-time computable with linear preprocessing. If correct, CstPP is a stable, machine-independent notion of instant lookup after small preprocessing, and the same invariance carries over to linear-time and constant-delay enumeration classes.","feed_headline":"Constant-time class holds up from N^epsilon to N^c preprocessing","feed_subtitle":"Even N^epsilon preprocessing suffices, and only sub-polynomial preprocessing breaks it.","key_machinery":"The Fundamental Lemma (Lemma 2) is the workhorse: if op is in CstPP(OP) and + is in OP, then any program over OP ∪ {op} can be faithfully simulated by a program over OP after a linear-time initialization. This makes every CstPP operation freely usable as a primitive. The preprocessing-time reductions rest on a radix (base) change trick: replace the reference integer N by its c-th root N_1 = floor(N^{1/c}), computed in O(N^{1/c}) time using only +, div, and mod; then operands < N^d are operands < N_1^{cd} for the original algorithm, so its O(N_1) preprocessing becomes O(N^{1/c}). The inverse-closure proof buckets candidates by floor(log_2 f(y)); for exponentially growing f each bucket has bou","core_discovery":"The central claim is that the linear preprocessing bound in the definition of CstPP is not a delicate parameter. Theorems 5 and 6 show the class is unchanged when preprocessing is relaxed to N^c for any fixed c>1 or tightened to N^epsilon for any epsilon>0, as long as the primitive operations include +, div, and mod. By contrast, Theorem 8 shows that reducing preprocessing to N^{o(1)} collapses the class: even multiplication is no longer constant-time computable with addition only. The paper also shows that a constant-time procedure can be compressed to a single addition expression (a return instruction), and that an exponentially growing function and its inverse are in CstPP together (Theor","pith_inferences":["If Proposition 1 (logarithm and exponentiation in CstPP) is verified, the inverse-closure theorem gives a general recipe: for any monotone exponentially growing f in CstPP, the inverse is also in CstPP, suggesting a broad symmetry between fast growth and fast lookup.","The degeneracy at N^{o(1)} preprocessing suggests a possible threshold effect: any positive polynomial preprocessing keeps CstPP stable, but sub-polynomial preprocessing breaks even multiplication; locating the exact threshold for other operation sets (e.g., +, div, mod) remains an open question.","The radix-change trick suggests a testable route to the open problem of whether the generalized root (x,y)->floor(x^{1/y}) is in CstPP, by iterating the same root computation with varying degrees."],"forward_implications":["CstPP can be defined with preprocessing time N^epsilon or N^c without changing the class, so the minimal preprocessing in the name is not a tight constraint.","The class is closed under composition and, for exponentially growing functions, under inverse, so complex operations like inverse factorial and inverse Fibonacci are constant-time computable after linear preprocessing.","The choice of primitive RAM operations, as long as addition is included (and for the preprocessing reductions also div and mod), does not affect the class, making it machine-independent.","The same invariance transfers to linear-time (LinTime) and constant-delay enumeration (CstDelay_lin) classes, so robustness arguments apply beyond the operation class itself.","Any constant-time computation in CstPP can be reduced to a single addition expression, meaning table lookups plus additions suffice as the on-line phase."],"fun_headline_variants":["CstPP class unchanged for N^epsilon to N^c preprocessing","Sub-polynomial preprocessing wrecks constant-time class","Constant-time ops survive N^epsilon preprocessing, not N^o(1)","Preprocessing time flexible: N^eps to N^c, but not sub-poly","Single return instruction: enough for constant-time RAM ops"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The inverse-closure theorem leans on Proposition 1, imported from the companion paper [25], that floor(log_x y) and exponentiation are themselves in CstPP; if that membership result were flawed, the bucketing argument for inverse closure would need a replacement.","fun_headline_variants_meta":{"raw":{"variants":["CstPP class unchanged for N^epsilon to N^c preprocessing","Sub-polynomial preprocessing wrecks constant-time class","Constant-time ops survive N^epsilon preprocessing, not N^o(1)","Preprocessing time flexible: N^eps to N^c, but not sub-poly","Single return instruction: enough for constant-time RAM ops"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000242,"raw_usage":{"total_tokens":1435,"prompt_tokens":891,"completion_tokens":544,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":635,"completion_tokens_details":{"reasoning_tokens":452}},"tokens_in":635,"tokens_out":544,"duration_ms":5344,"temperature":1.0,"reasoning_tokens":452,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T18:05:10.281795+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 3's computation of floor(N^{1/3}) for a large N (say 10^12) using only +, div, and mod, and check both the step count (about N^{1/3}) and the correctness of the translated loop condition; a failure there would undermine Theorem 5's claimed reduction of preprocessing time.","supporting_citations":[],"review_version":1}