{"id":"e32a23d6-a5ce-4d2c-87c1-b2d8c2a4988f","arxiv_id":"2502.04581","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"k-SUM is complete for the existential fragment of linear integer arithmetic sentences, and 3-SUM is complete for sentences using at most three linear inequalities, unifying many fine-grained reductions.","lead":"The paper proves that k-SUM is complete for deciding a broad logically defined family of linear-integer-arithmetic statements over finite sets, and that 3-SUM is complete for a low-inequality-dimension fragment of that family. It also identifies a pair of geometric problems that together capture the complexity of the whole family, unifying many conditional time lower bounds.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 27's deferred exterior-disjoint cube decomposition is the load-bearing unverified step: if it needs ω(n) boxes, Theorem 28's counting reduction and Theorem 5 fail.","rationale":"I traced the dependencies of the main claims and agree with the reader that Lemma 27 is the most load-bearing unverified ingredient. The proof of Theorem 28 explicitly invokes Lemma 27 to turn orthant membership into a disjoint-box covering; without an O(n)-box partition, the reduction to counting 3-SUM witnesses (Corollary 3 / Corollary 19) no longer works, so Theorem 5 falls. I also checked whether this concern reaches Theorem 4: it does not directly, since Theorem 4 is a consequence of Lemmas 11 and 12, whose proofs are likewise deferred but rest on the syntactic reductions of Section 5 rather than on cube decomposition. I considered Lemma 18's heavy-light proof as an alternative concern: it appears to double-count witnesses when several coordinates have high multiplicity, but this gap is localized and plausibly repairable by a canonical first-heavy-coordinate argument, whereas a false Lemma 27 would require a fundamentally different geometric mechanism. Thus the reader's CONDITIONAL verdict remains appropriate, subject to the full version making Lemma 27's proof available and the proposed check settling the box-count question.","tokens_in":25842,"tokens_out":38289,"duration_ms":430827,"concrete_test":"Resolve Lemma 27 by one of two checks: (a) supply the full proof of the exterior-disjoint extension of [23] and verify it preserves O(n) boxes and O(n log^2 n) time, including explicit handling of shared boundaries (e.g., half-open boxes); or (b) determine the worst-case boundary complexity of the union of n translates of a unit cube in R^3. If that complexity is Ω(n^2), then no disjoint decomposition into O(n) boxes exists, Lemma 27 is false, and the counting argument in Theorem 28 cannot be repaired by a minor convention change.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 27 is the geometric pivot of Theorem 28 and hence of Theorem 5. The reduction replaces each orthant S(V_i,c') by a congruent cube and then partitions the union of O(n) such cubes into O(n) pairwise-disjoint boxes. The counting step requires that every sum a'+b' falls in at most one box; if the decomposition produces ω(n) boxes, or only interior-disjoint boxes with shared boundaries and no half-open convention, the witness count no longer equals the number of covered pairs. The proof is deferred to the full version, and the exterior-disjoint strengthening of the Chew et al. result [23] is not demonstrated in this preprint. This concern directly affects the paper's second headline completeness result (3-SUM complete for FOPZ formulas of inequality dimension at most 3). Theorem 4's problem-pair completeness rests on the separate, also deferred Lemmas 11 and 12, so the reader's pinpointed assumption is load-bearing for a major advertised result even if it is not the main dependency of Theorem 4.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a descriptive-complexity class FOP_Z of model-checking problems for prenex linear integer arithmetic formulas over finite integer sets, and proves fine-grained completeness results for k-SUM and two geometric problems. It claims that k-SUM is complete for the k-existential fragment (Theorem 1), that counting witnesses of existential FOP_Z formulas reduces to #k-SUM for odd k (Theorem 2, Corollary 3), that 3-SUM is complete for all k-quantifier FOP_Z formulas of inequality dimension at most 3 (Theorems 5 and 28), and that the pair consisting of Pareto Sum Verification and Hausdorff Distance under n Translations is complete for the entire class FOP^k_Z (Theorem 4). The paper also derives conditional lower bounds for Pareto sum computation. The proof strategy combines a bit-level reduction of inequalities to equalities, a heavy-light argument for multiset counting, reductions among quantifier structures via sumset approximation, and a geometric decomposition of the union of congruent cubes into disjoint boxes.","tokens_in":26077,"tokens_out":5416,"duration_ms":56498,"significance":"If the claims are correct, the paper gives a rare kind of fine-grained completeness: natural problems capturing a logically defined class over arithmetic. The existential-fragment completeness of k-SUM and the low-inequality-dimension completeness of 3-SUM would unify many existing reductions and provide a clean framework for conditional lower bounds. The problem-pair completeness of Pareto Sum Verification and Hausdorff Distance under n Translations is an ambitious and plausible generalization of 3-SUM. The paper is also careful to build on prior equivalences, such as the 3-SUM/#3-SUM equivalence of Chan et al. and Patrascu's convolutional 3-SUM equivalence, and I saw no circularity in the reduction structure. However, the manuscript as submitted is not self-contained: many load-bearing proofs, including the geometric Lemma 27 and the component lemmas of Theorem 4, are deferred to a full version, so the contribution is currently conditional on material the referee cannot check.","major_comments":[{"comment":"Lemma 27 states that the union of n congruent axis-aligned cubes in R^3 can be decomposed into O(n) boxes with pairwise disjoint interiors and exteriors in O(n log^2 n) time, but the proof is deferred. This lemma is the counting mechanism in Theorem 28 and hence in Theorem 5: without exterior-disjointness, a point a'+b' could lie on the boundary of more than one box, and the witness count would no longer equal |A'|·|B'| (or, in the existential case, the number of b' witnessed by a given a'). A journal version must include the proof, or a precise citation establishing exactly this strengthening of the Chew et al. result [23].","section":"§6, Lemma 27"},{"comment":"Theorem 4, the problem-pair completeness result for all of FOP^k_Z, rests on Lemmas 11 and 12, whose proofs are deferred, and on Theorem 10, whose proof is also deferred. These are not local technicalities: they are the only bridge from the syntactic normal forms of Lemma 22 to arbitrary quantifier prefixes of length k. As the manuscript stands, the paper's headline completeness claim cannot be verified from the text. The full proofs of Theorem 10, Lemma 11, and Lemma 12 must appear.","section":"§5.2–5.3, Theorem 10 and Lemmas 11–12"},{"comment":"The foundational reduction showing that k-SUM is complete for FOP_Z(∃k) is only sketched. Lemma 13, which converts a conjunction of m linear inequalities into a unique disjunct of equality checks, is stated without proof, and the Vector k-SUM to k-SUM step is cited to [5] rather than proved. Since Theorem 1 underpins Theorem 2, Corollary 3, and the later quantifier-prefix arguments, the full reduction should be included.","section":"§3, Theorem 1 and Lemma 13"},{"comment":"Theorem 5 extends Theorem 28 from FOP^3_Z to FOP^k_Z with k≥3, but no proof of this extension is given; the text only says 'We can extend Theorem 28 to k-quantifiers by the following theorem.' The k-quantifier extension is a separate load-bearing claim, since it supplies the n^{k-1-ε} bounds advertised in the abstract and used in Theorem 7. A proof is needed to show how the counting/decomposition approach composes with arbitrary quantifier prefixes.","section":"§6, Theorem 5"}],"minor_comments":[{"comment":"The phrase 'faster-than-n^{⌈k/2⌉±o(1)}' is imprecise; the formal statements use O(n^{⌈k/2⌉−ε}) for some ε>0. Please rephrase for accuracy.","section":"Abstract"},{"comment":"Definition 33 has a typo: the output of Pareto Sum should be a set C⊆Z^d, not C⊆Z.","section":"§7, Definition 33"},{"comment":"The reference list contains formatting errors, e.g., reference [46] spells the author as 'Puatracscu' instead of 'Patrascu'.","section":"References"},{"comment":"Several standard objects are used without definitions in the text, including All-ints 3-SUM, the Strong 3-SUM hypothesis, and the exact half-open boundary conventions in the boxes of Lemma 27; a journal version should make these precise.","section":"§5–§6"}],"recommendation":"major_revision","confidential_remarks":"The manuscript reads like a conference extended abstract: numerous core proofs, including the geometric Lemma 27 and the component lemmas of Theorem 4, are deferred to a full version. For a journal submission, I would require that the full proofs be included or made available as a clearly labeled appendix before the results can be evaluated. The novelty and the overall reduction architecture appear suitable for a fine-grained complexity venue, but the current document is not independently verifiable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I agree with the conditional verdict: the framework is significant if true, but this preprint doesn't yet prove it. The big new thing is a descriptive-complexity view of k-SUM. They define FOP_Z, the class of Presburger/linear-integer-arithmetic sentences over finite sets, show k-SUM is fine-grained complete for the k-existential fragment (Theorem 1), and that 3-SUM is complete for all 3-quantifier formulas of inequality dimension at most 3 (Theorem 5). They also produce a problem pair—Pareto Sum Verification plus Hausdorff distance under n Translations—complete for the whole class FOP_Z^k (Theorem 4). If correct, this unifies a lot of scattered reductions and gives a clean answer to what these fine-grained hypotheses actually capture. The reductions are sketched well enough to see the shape: the bit-level trick to turn inequalities into equalities, the vector k-SUM reduction, and the use of Chan et al.'s #3-SUM equivalence for counting. The heavy-light multiset counting lemma is a nice piece on its own.\n\nNow the soft spots, and they are the same ones the stress-test flagged. The preprint is not self-contained: Theorem 1, Theorem 2, Theorem 4, Theorem 10, and Theorem 5 all defer central parts to a full version. The most load-bearing is Lemma 27, the claim that the union of n axis-aligned unit cubes in R^3 can be decomposed into O(n) interior- and exterior-disjoint boxes in O(n log^2 n) time. Theorem 5's counting argument depends on that decomposition being exactly O(n) and on disjointness strong enough that each sum a'+b' lands in at most one box. The stress-test note is right: if the exterior-disjoint strengthening fails, or the box count is superlinear, the low-inequality-dimension completeness result collapses. The paper says the proof is in a full version, but I don't have it, so I can't verify the claim.\n\nI don't see circularity. The reductions go from FOP_Z problems to k-SUM or to the geometric pair, and they rely on external equivalences like Patrascu's convolutional 3-SUM and Chan et al.'s #3-SUM. The self-citations are appropriate. The barrier discussion—why spanning the whole class would imply hyperclique lower bounds—is honest and helpful.\n\nBottom line: this paper is for fine-grained complexity and descriptive complexity people. It deserves a serious referee, not a desk reject. But the review must demand the deferred proofs or a full version; I'd want to see Lemma 27 in full before betting on Theorem 5. My recommendation: send it to referees with a request for the missing material—conditional accept rather than outright reject.","headline":"Genuinely new completeness framework for k-SUM over a logical class, but too many deferred proofs—especially Lemma 27—make acceptance conditional on the full version.","tokens_in":26566,"tokens_out":4058,"would_cite":true,"duration_ms":41335,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","03B25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that $k$-SUM is complete for the existential fragment of a logical class $\\mathsf{FOP}_{\\mathbb{Z}}$ of Presburger arithmetic sentences, and that Pareto Sum Verification together with Hausdorff distance under $n$…","keywords":["fine-grained complexity","k-SUM hypothesis","Presburger arithmetic","integer linear arithmetic","descriptive complexity","Pareto sum verification","Hausdorff distance under translation","completeness theorems"],"falsifier":"Exhibit a concrete set of $n$ axis-aligned unit cubes in $\\mathbb{R}^3$ whose union provably cannot be decomposed into $O(n)$ axis-aligned boxes with pairwise disjoint interiors and exteriors (for example, a construction requiring $\\Omega(n \\log n)$ boxes). Such a construction would refute Lemma 27 and invalidate Theorems 28 and 5 as stated; a simpler test is to compute the decomposition on large random cube sets and check whether the number of output boxes and the running time stay within $O(n)$ and $O(n \\log^2 n)$, respectively.","tokens_in":25637,"feed_emoji":"🧮","tokens_out":10480,"duration_ms":85323,"temperature":0.7,"pith_summary":"This paper asks, in effect, how much of the difficulty of linear integer arithmetic is captured by the $k$-SUM problem. It defines a class $\\mathsf{FOP}_{\\mathbb{Z}}$ of model-checking problems: deciding prenex sentences in Presburger arithmetic over finite sets of integer points, with $k$ quantified variables ranging over the input sets. The main claims are that $k$-SUM is fine-grained complete for the $k$-existential-quantifier fragment, that $3$-SUM is complete for all $k$-quantifier sentences of inequality dimension at most $3$, and that the pair consisting of Pareto Sum Verification and Hausdorff distance under $n$ translations is complete for the whole class. If these claims hold, a subquadratic speed-up for $3$-SUM (or for either geometric problem) would translate into polynomial speed-ups for every sentence in the corresponding logical fragment, turning isolated algorithmic barriers into a single completeness story.","feed_headline":"One problem pair decides all k-quantifier integer arithmetic","feed_subtitle":"Faster Pareto-sum and Hausdorff translation checks would speed up every sentence in the class FOP_Z.","key_machinery":"The load-bearing mechanism is a collection of fine-grained reductions. The bit-level trick of Vassilevska Williams and Williams turns a conjunction of linear inequalities into a small number of conjunctions of linear equalities by guessing the most significant differing bit of each inequality; the vector $k$-SUM to $k$-SUM reduction of Abboud, Lewi, and Williams then collapses a conjunction of equalities into a single $k$-SUM instance. For counting versions, a heavy-light argument shows that multiset $\\#k$-SUM is equivalent to $\\#k$-SUM for odd $k$, and the recent equivalence between $3$-SUM and $\\#3$-SUM supplies the counting hardness needed for quantifier changes. For the general-quantifier results, the paper proves a normal form (Lemma 22) reducing every $\\mathsf{FOP}_{\\mathbb{Z}}(Q_1 Q_2 \\exists)$ formula to the syntactic form $Q_1 a_1 Q_2 a_2 \\exists a_3 : a_1 + a_2 \\le a_3$, uses the Additive Sumset Approximation problem to move between quantifier structures, and uses a decomposition of the union of $O(n)$ congruent cubes in $\\mathbb{R}^3$ into $O(n)$ interior- and exterior-disjoint boxes (Lemma 27) to turn satisfiability of $\\forall\\exists$-formulas into a witness-counting condition against disjoint boxes.","core_discovery":"The paper's central discovery is a set of fine-grained completeness theorems that locate $k$-SUM and two geometric problems inside a logical class. Theorem 1 states that any problem of deciding an $\\mathsf{FOP}_{\\mathbb{Z}}$ formula with $k$ existential quantifiers reduces to $k$-SUM with only polylogarithmic overhead; Theorem 5 states that $3$-SUM is complete for all $\\mathsf{FOP}_{\\mathbb{Z}}$ formulas with $k$ quantifiers and inequality dimension at most $3$; Theorem 4 states that the pair (Pareto Sum Verification, Hausdorff distance under $n$ translations) is complete for all of $\\mathsf{FOP}_{\\mathbb{Z}}$, in the sense that a time $O(n^{2-\\epsilon(d)})$ algorithm for both problems exists if and only if every $k$-quantifier sentence in $\\mathsf{FOP}_{\\mathbb{Z}}$ with $k \\ge 3$ can be decided in time $O(n^{k-1-\\epsilon_P})$. The paper also proves a counting version (Theorem 2 and Corollary 3), showing that counting witnesses for existential $\\mathsf{FOP}_{\\mathbb{Z}}$ formulas is no harder than counting $k$-SUM witnesses, and transfers the resulting hardness to the computation of Pareto sums (Theorem 7).","pith_inferences":["The paper's invitation to treat Pareto Sum Verification as a high-dimensional generalization of $3$-SUM suggests that future hardness results could be organized around the dominance query 'does every sum $a+b$ lie below some $c$', making the verification problem a canonical representative of the whole class.","An immediate consequence of Theorem 4 that the authors leave implicit is that any exact algorithm for approximating Hausdorff distance under translation that improves on the $\\tilde{O}(mn)$ baseline is constrained by every $\\mathsf{FOP}_{\\mathbb{Z}}$ lower bound, so future lower bounds for logic fragments can be read directly as lower bounds for geometric approximation.","Because the cube-decomposition lemma (Lemma 27) is deferred to the full version, the printed proof of Theorem 5 depends on an unverified geometric claim; a reader who distrusts the exterior-disjointness extension of the earlier interior-disjoint decomposition will want to check that step before relying on the result.","The barrier analysis suggests that proving $3$-SUM complete for all of $\\mathsf{FOP}_{\\mathbb{Z}}$ is equivalent to a tight reduction from the $3$-uniform hyperclique problem to $3$-SUM, so closing the remaining gap is plausibly as hard as relating two central fine-grained hypotheses."],"forward_implications":["A faster-than-$n^{\\lceil k/2 \\rceil}$ algorithm for $k$-SUM would speed up every problem in $\\mathsf{FOP}_{\\mathbb{Z}}(\\exists^k)$ by a polynomial factor.","A faster-than-$n^2$ algorithm for $3$-SUM would imply polynomial speed-ups for all $\\mathsf{FOP}_{\\mathbb{Z}}$ formulas with $k$ quantifiers and inequality dimension at most $3$, regardless of quantifier structure.","A faster-than-$n^2$ algorithm for both Pareto Sum Verification and Hausdorff distance under $n$ translations would imply polynomial speed-ups for every $k$-quantifier sentence in $\\mathsf{FOP}_{\\mathbb{Z}}$.","A faster-than-$n^2$ algorithm for computing Pareto sums of sets with $\\Theta(n)$ output size would refute the $3$-SUM hypothesis, and in dimension at least $2$ the same speed-up would speed up all $\\mathsf{FOP}_{\\mathbb{Z}}$ formulas not ending in $\\exists\\forall\\exists$ or $\\forall\\exists\\forall$.","A subquadratic algorithm for counting $3$-SUM witnesses would let us count witnesses of every existential $3$-quantifier $\\mathsf{FOP}_{\\mathbb{Z}}$ formula in subquadratic time."],"supporting_citations":[{"why":"introduces the 3-SUM hypothesis as the central hardness assumption for quadratic-time geometry problems that this paper generalizes.","marker":"[35]"},{"why":"supplies the bit-level trick that converts linear inequalities into equalities, the core of the reduction in Theorem 1.","marker":"[52]"},{"why":"provides the reduction from vector k-SUM to k-SUM that collapses conjunctions of equalities into a single k-SUM instance.","marker":"[5]"},{"why":"establishes the subquadratic equivalence between 3-SUM and counting 3-SUM witnesses used to lift existential completeness to counting and to quantifier-change arguments.","marker":"[22]"},{"why":"gives the interior-disjoint box decomposition of cubes in R^3 that Lemma 27 extends to exterior-disjointness for the low-inequality-dimension completeness theorem.","marker":"[23]"},{"why":"defines the PTO class and proves barriers showing 3-SUM cannot easily be complete for all FOP_Z formulas under standard hypotheses.","marker":"[7]"},{"why":"provides the convolutional version of 3-SUM used to prove the Additive Sumset Approximation upper and lower bounds in Theorem 10.","marker":"[46]"},{"why":"offers the All-ints 3-SUM equivalence used to handle the forall-exists-exists quantifier structure and to determinize the quantifier-change reductions.","marker":"[51]"}],"fun_headline_variants":["k-SUM captures every k-quantifier integer arithmetic sentence","3-SUM complete for all 3-inequality integer arithmetic","Pareto-sum and Hausdorff distance complete for FOP_Z","Pareto-sum and Hausdorff translation checks decide FOP_Z","k-SUM completeness for k-quantifier arithmetic logic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is Lemma 27, whose proof is deferred: the union of $n$ axis-aligned congruent cubes in $\\mathbb{R}^3$ can be decomposed into $O(n)$ axis-aligned boxes with disjoint interiors and exteriors in $O(n \\log^2 n)$ time; if that decomposition needs more boxes or more time, the counting mechanism behind $3$-SUM completeness for low-inequality-dimension formulas breaks down.","fun_headline_variants_meta":{"raw":{"variants":["k-SUM captures every k-quantifier integer arithmetic sentence","3-SUM complete for all 3-inequality integer arithmetic","Pareto-sum and Hausdorff distance complete for FOP_Z","Pareto-sum and Hausdorff translation checks decide FOP_Z","k-SUM completeness for k-quantifier arithmetic logic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000391,"raw_usage":{"total_tokens":2186,"prompt_tokens":1203,"completion_tokens":983,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":819,"completion_tokens_details":{"reasoning_tokens":893}},"tokens_in":819,"tokens_out":983,"duration_ms":9763,"temperature":1.0,"reasoning_tokens":893,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T22:14:14.047484+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a concrete set of $n$ axis-aligned unit cubes in $\\mathbb{R}^3$ whose union provably cannot be decomposed into $O(n)$ axis-aligned boxes with pairwise disjoint interiors and exteriors (for example, a construction requiring $\\Omega(n \\log n)$ boxes). Such a construction would refute Lemma 27 and invalidate Theorems 28 and 5 as stated; a simpler test is to compute the decomposition on large random cube sets and check whether the number of output boxes and the running time stay within $O(n)$ and $O(n \\log^2 n)$, respectively.","supporting_citations":[{"cited_title":"Chan, Virginia Vassilevska Williams, and Yinzhan Xu","cited_arxiv_id":null,"evidence_quote":"establishes the subquadratic equivalence between 3-SUM and counting 3-SUM witnesses used to lift existential completeness to counting and to quantifier-change arguments."},{"cited_title":"Paul Chew, Dorit Dor, Alon Efrat, and Klara Kedem","cited_arxiv_id":null,"evidence_quote":"gives the interior-disjoint box decomposition of cubes in R^3 that Lemma 27 extends to exterior-disjointness for the low-inequality-dimension completeness theorem."},{"cited_title":"The fine-grained complexity of multi-dimensional ordering properties","cited_arxiv_id":null,"evidence_quote":"defines the PTO class and proves barriers showing 3-SUM cannot easily be complete for all FOP_Z formulas under standard hypotheses."},{"cited_title":"Towards polynomial lower bounds for dynamic problems","cited_arxiv_id":null,"evidence_quote":"provides the convolutional version of 3-SUM used to prove the Additive Sumset Approximation upper and lower bounds in Theorem 10."},{"cited_title":"Subcubic equivalences between path, matrix and triangle problems","cited_arxiv_id":null,"evidence_quote":"offers the All-ints 3-SUM equivalence used to handle the forall-exists-exists quantifier structure and to determinize the quantifier-change reductions."}],"review_version":1}