{"id":"8edcef36-a74d-44c4-80e2-d2afee6ca438","arxiv_id":"1908.03486","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A new projection-based algorithm computes zero-dimensional tropical varieties from a Gröbner basis in polynomial time in the degree and ambient dimension.","lead":"This paper gives a faster way to compute zero-dimensional tropical varieties, geometric objects that encode how solutions to polynomial equations behave. The method runs in polynomial time when a Gröbner basis is given, and the authors provide a working implementation in the Singular computer algebra system.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Complexity proved for sequential strategy only; overlap strategy used in benchmarks lacks the bound, so the advertised polynomial guarantee is not established for the implemented algorithm.","rationale":"The reader's weakest assumption (ν(K*)⊆Q) is explicit in Convention 7.1 and does not affect correctness; it only restricts the stated complexity count. The more consequential gap is the one between the proven sequential strategy and the implemented overlap strategy, which is exactly where the paper's practical claims live. Since the reader already issued CONDITIONAL, my read supports that verdict; I recommend UNCHANGED rather than a movement. The theorem itself appears sound.","tokens_in":15797,"tokens_out":28978,"duration_ms":282146,"concrete_test":"Formalize the overlap gluing as a relation R = {(u, v) ∈ p_{1..i}(Trop(I)) × p_{1..i-1,j}(Trop(I)) : u|_{1..i-1} = v|_{1..i-1}} and prove the analogue of Lemma 7.4 for R: find m ≤ C(|R|,2) such that w ↦ π_v(w_{1..i}) - m w_j is injective on R, with the search costing O(|R|^2) Q-operations. If such a proof can be written, extend Theorem 7.6 to overlap; if a counterexample with |R|=d^2 but no separating m below d^4 is constructed, the practical algorithm lacks the claimed polynomial bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 7.6 gives O(n d^2 log d log log d) K-operations and O(n d^4) Q-operations for Algorithm 4.2 specifically with the sequential strategy. Section 5.4 states that the overlap strategy is what the implementation uses for the timings in Section 6. The proof of Proposition 7.5 depends on the sequential product structure p_{1..k-1} × p_k: Lemma 7.4 is applied to the two sets X and Y and yields an injective scalar projection a - m b. For overlap, the candidate set T in Algorithm 4.1 is not a Cartesian product but a relation R ⊆ p_{1..i} × p_{1..i-1,j} with equality constraints on the common prefix; the paper gives no analogue of Lemma 7.4 or Proposition 7.5 for this relation. Although |R|≤d^2 follows from |p_{1..i}|≤d and |p_{1..i-1,j}|≤d, no bound is proved on the size of the smallest separating integer m nor on the cost of finding it. Consequently, the complexity statement that a reader naturally attaches to the implemented algorithm is unsupported. Remark 7.7's average-polynomial claim for positive-dimensional tropical links is likewise heuristic and not a theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an algorithm for computing the tropical variety of a zero-dimensional ideal from a lexicographical Gröbner basis in shape position. The method rests on 'slim' unimodular transformations, which map the given Gröbner basis to one for the transformed ideal, and then reduce the computation to univariate minimal polynomials and Newton polygons. Projections of the tropical variety onto coordinate subspaces are computed separately and then glued via Algorithm 4.1, with Algorithm 4.2 assembling the full tropical variety. The authors prove correctness of these algorithms, give a complexity analysis for the sequential gluing strategy, describe a Singular implementation, compare timings with a p-adic root-approximation approach in Magma, and discuss implications for computing positive-dimensional tropical links.","tokens_in":16040,"tokens_out":19154,"duration_ms":191071,"significance":"If the proof is completed, this is a valuable contribution: it gives a polynomial bound in the degree and ambient dimension for computing zero-dimensional tropical varieties from a Gröbner basis, avoiding both elimination and root approximation to unknown precision. The paper ships an implementation and reproducible benchmark data, and the honeycomb-cubic example is a meaningful stress test. The explicit complexity theorem for the sequential strategy, the exact minimal-polynomial/Newton-polygon steps, and the preservation of shape position and saturation are all concrete strengths that make the central idea credible and potentially useful for subsequent work on tropical links.","major_comments":[{"comment":"The proof of Proposition 7.5 states that ϕ_w(I) = ϕ_u(ϕ_v(I)) for u := m e_k − e_ℓ. This equality does not hold: for two slim transformations v and u concentrated at the same coordinate ℓ, one computes (ϕ_u∘ϕ_v)(x_ℓ) = x_ℓ · ∏_{i≠ℓ} x_i^{v_i-u_i}, whereas ϕ_w(x_ℓ) = x_ℓ^{-1} · ∏_{i≠ℓ} x_i^{w_i}. In particular, the exponents of x_ℓ differ by sign. Thus Algorithm 3.4 applied to u and a Gröbner basis of ϕ_v(I) produces a Gröbner basis of the composite ideal, not of ϕ_w(I). The intended invariant should be formulated on the level of elimination ideals: applying Algorithm 3.4 to u and the known basis of ϕ_v(I) yields an ideal whose elimination ideal in x_ℓ has tropical variety π_{v+m e_k}(Trop(I)), which is exactly what the gluing step requires. This repair is localized and does not change the stated operation counts, but Theorem 7.6 relies on this proposition, so the proof as written is incomplete. Additionally, for k=2 the induction assumption 'known from a previous call of Algorithm 4.1' is not satisfied; an initial slim transformation and its Gröbner basis must be supplied or computed, adding an O(d^2) cost that is within the claimed bound.","section":"Section 7, Proposition 7.5"},{"comment":"The complexity guarantee is proved only for the sequential gluing strategy, whereas the implementation and the timings in Section 6 use the overlap strategy. For overlap, the candidate set T in Algorithm 4.1 is a relation with equality constraints on a common prefix, not a Cartesian product, so Lemma 7.4 does not directly apply; no analogue is proved bounding the size of the separating integer or the cost of finding it. Consequently, the abstract's claim that 'our algorithm requires only a polynomial number of arithmetic operations' is not supported for the strategy actually used in the benchmarks. The authors should either prove a complexity bound for the overlap strategy or explicitly restrict the polynomial-complexity claim to the sequential strategy and state that the implemented default strategy is not covered.","section":"Sections 5.4, 6, and Theorem 7.6"}],"minor_comments":[{"comment":"The proof uses the equality p_ℓ(Trop(J)) = Trop(J ∩ K[x_ℓ^±]) for zero-dimensional ideals without comment; since this equality is not valid for arbitrary ideals, a short justification in this setting would improve readability.","section":"Lemma 3.2"},{"comment":"The notation ϕ_{(−1,3)}(I) omits the third coordinate of the transformation; writing ϕ_{(−1,3,0)}(I) would avoid confusion.","section":"Example 4.3"},{"comment":"The assumption ν(K*) ⊆ Q is explicit in Section 7 but should be restated in the abstract or in the statement of Theorem 7.6 so that the polynomial bound is not over-read to arbitrary valued fields.","section":"Convention 7.1 / Theorem 7.6"},{"comment":"The extrapolation to positive-dimensional tropical links relies on the heuristic claim that zero-dimensional Gröbner bases can be computed in average polynomial time; please label this as experimental/heuristic and distinguish it from the proved Theorem 7.6.","section":"Remark 7.7"},{"comment":"The text contains residual LaTeX markup artifacts such as '/lessnotequal' and 'bracehtipupleft' in the rendering; these should be cleaned in the journal version.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main algorithm and implementation are valuable, and the correctness proofs of Algorithms 3.4, 4.1, and 4.2 are convincing apart from the local gap in Proposition 7.5. I recommend major revision rather than rejection because the gap appears repairable and the sequential complexity result is likely correct. The overlap-strategy mismatch should be addressed as a matter of accurate claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper's main algorithm is real, the main theorem is proved for the sequential strategy, and the implementation's default overlap strategy is not covered by that theorem. The positive-dimensional remark is a heuristic extrapolation. None of this sinks the paper, but the abstract should be read with that caveat.\n\nWhat's actually new: the slim unimodular transformations of lex Gröbner bases, and the gluing algorithm that reconstructs a zero-dimensional tropical variety from coordinate projections. Given a reduced lex Gröbner basis in shape position, the algorithm runs in polynomial arithmetic operations in the degree and dimension — O(n d^2 log d log log d) over K, O(n d^4) over Q — assuming rational valuations. That's a genuine improvement over Chan's elimination and Hofmann-Ren's root approximation. The correctness proofs (Lemmas 3.2, 3.3 and the algorithm correctness) look clean. The timings against Magma are believable and show the method scales better at higher degree.\n\nSoft spots, in proportion: (1) Theorem 7.6 only covers the sequential gluing strategy. Section 5.4 says the implementation used for the timings uses the overlap strategy, for which no complexity bound is proved. The paper is not hiding this, but the abstract's 'polynomial number of arithmetic operations' without qualification is likely to be read as covering the implemented algorithm. It would help to either extend the analysis to overlap or qualify the abstract. (2) Remark 7.7, that tropical link computation is dominated by the Gröbner walk, is an argument based on average-case bounds for zero-dimensional Gröbner bases. It is clearly labeled as an argument, so I wouldn't call it a fatal flaw, but it's not a theorem. (3) The algorithm assumes shape position and a lex Gröbner basis input; the complexity of getting to that state is not part of the analysis. That's standard for this kind of paper.\n\nThe citation pattern looks reasonable — Chan, Hofmann-Ren, and the standard tropical geometry references are cited appropriately. Code and data are announced but not independently verifiable from the preprint.\n\nFor whom: computational tropical geometers and people using Singular to compute tropical varieties. It deserves a serious referee; I'd send it to a journal like JSC or MCOM. The referee should push for a clear statement of which strategy the complexity theorem covers and whether the implementation's strategy can be brought under the same proof.","headline":"Solid algorithmic contribution with a proved polynomial bound for the sequential strategy; the implementation's overlap strategy and the positive-dimensional remark sit outside the proof, so the abstract overreaches slightly.","tokens_in":16544,"tokens_out":6008,"would_cite":true,"duration_ms":61753,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["14T05","13P10","13P15","68W30"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a zero-dimensional tropical variety can be computed exactly from coordinate projections, in polynomial time, by gluing the projections with slim unimodular transformations.","keywords":["tropical geometry","tropical varieties","zero-dimensional ideals","Gröbner bases","unimodular transformations","coordinate projections","computer algebra","complexity bounds"],"falsifier":"Compute Trop(I) for a zero-dimensional ideal in shape position over the 2-adic numbers by Algorithm 4.2 and independently by p-adic root approximation, comparing point sets with multiplicities; any mismatch would refute the correctness claim. A sharper test is to search for an ideal whose smallest injective slope $m$ exceeds $\\binom{d^2}{2}$, which would contradict Lemma 7.4.","tokens_in":15592,"feed_emoji":"🌴","tokens_out":11576,"duration_ms":110058,"temperature":0.7,"pith_summary":"This paper claims that the tropical variety of a zero-dimensional ideal can be computed in polynomial time once a reduced lexicographic Gröbner basis in shape position is known. The strategy is to project the tropical variety onto coordinate axes and then reconstruct it by gluing the coordinate projections together, using slim unimodular transformations to make each gluing step injective. The authors prove that the sequential version of the algorithm uses $O(n d^2 \\log d \\log \\log d)$ arithmetic operations in the coefficient field and $O(n d^4)$ arithmetic operations over the rationals, with $d$ the degree of the ideal and $n$ the number of variables. If true, this removes the worst-case exponential behaviour of earlier elimination and root-approximation approaches for zero-dimensional tropical computations, and shifts the bottleneck in computing positive-dimensional tropical varieties to the Gröbner walk.","feed_headline":"Zero-dimensional tropical varieties computed in polynomial time","feed_subtitle":"Given a lex Gröbner basis, projection and gluing need only $O(n d^2 \\log d \\log \\log d)$ field operations.","key_machinery":"The load-bearing object is the slim unimodular transformation: a torus automorphism that replaces one variable $x_\\ell$ by $x_\\ell$ times a Laurent monomial in the remaining variables, with exponent vector having one $-1$ and all other entries nonnegative. Its associated linear functional $\\pi_u$ projects $\\mathbb{R}^n$ onto one coordinate in a direction that can separate finitely many points. The key identity (Lemma 3.2) is $\\pi_u(\\operatorname{Trop}(I)) = \\operatorname{Trop}(\\phi_u(I) \\cap K[x_\\ell^{\\pm}])$, which turns a projection of the tropical variety into a univariate tropical variety computable from the Newton polygon of a minimal polynomial. A companion algorithm updates a lex Gröbner basis in shape position to the transformed basis in $O(d^2 \\sum (1+\\log u_i))$ field operations, by inverting and multiplying univariate polynomials modulo $f_n$. The gluing step then filters the candidate set $w \\in \\mathbb{R}^A$ whose coordinate projections are already known by testing whether $\\pi_u(w)$ lies in the univariate tropical variety.","core_discovery":"The central claim is that Trop(I) for a zero-dimensional ideal $I \\subseteq K[x^{\\pm}]$ is completely determined by a small collection of univariate tropical varieties, and that these data can be assembled exactly. The paper shows that for a slim unimodular transformation $\\phi_u$, the image of Trop(I) under the linear functional $\\pi_u$ equals the tropical variety of the elimination ideal $\\phi_u(I) \\cap K[x_\\ell^{\\pm}]$, a univariate object read off from a Newton polygon. Using this identity, Algorithm 4.1 merges any two known projections into a larger projection by picking $u$ so that $\\pi_u$ separates the finite candidate set, and Algorithm 4.2 repeatedly applies this merge until the full set is obtained. Theorem 7.6 states that the sequential strategy uses $O(n d^2 \\log d \\log \\log d)$ coefficient-field operations and $O(n d^4)$ rational operations, given a reduced lex Gröbner basis of shape position and a valuation $\\nu(K^*) \\subseteq \\mathbb{Q}$. The authors also argue that plugging this algorithm into tropical-link computations makes link computation polynomial-time on average, so that the Gröbner walk dominates in positive dimension.","pith_inferences":["The projection-and-gluing paradigm suggests that zero-dimensional tropical computation is essentially univariate: the multivariate structure enters only through the choice of finitely many injective linear functionals, so randomized or heuristic choices of $u$ could reduce the exact rational-operation cost.","If link computation really becomes polynomial-time, further progress on positive-dimensional tropical varieties will depend mainly on Gröbner basis computation and the Gröbner walk, not on tropical-specific elimination.","The same gluing scheme might extend to positive-dimensional ideals if the finite candidate set is replaced by a polyhedral candidate, offering a route to positive-dimensional tropical varieties without traversing the full Gröbner complex."],"forward_implications":["A zero-dimensional tropical variety can be computed exactly from the coordinate-axis tropical projections, with no need to solve polynomial systems or approximate roots in the valuation topology.","For an ideal of degree $d$ presented by a shape-position lex Gröbner basis, the sequential gluing strategy keeps every candidate set at size at most $d^2$, so both work and memory stay polynomial in $d$ and $n$.","The complexity bound makes the computation of tropical links, the local step that guides the Gröbner walk in existing tropical-variety software, a polynomial-time subtask on average for zero-dimensional links.","In practice, the projection method scales with degree rather than with the size of the splitting field, which is what slows down p-adic root-approximation baselines."],"supporting_citations":[{"why":"Introduces the Gröbner complex traversal framework into which the paper's positive-dimensional discussion fits.","marker":"[BJSST07]"},{"why":"Supplies coordinate projections as the conceptual approach to tropical computation that this paper sharpens.","marker":"[Cha13]"},{"why":"Provides the root-approximation algorithm for tropical links that the new zero-dimensional algorithm is intended to replace.","marker":"[HR18]"},{"why":"Supplies the univariate arithmetic complexity bounds used in Proposition 7.2 and in the proof of Proposition 7.3.","marker":"[GG13]"},{"why":"Gives the shape-position characterization of lexicographic Gröbner bases stated in Lemma 2.4.","marker":"[CLO05]"},{"why":"Provides the change-of-ordering method used for one minimal-polynomial computation strategy in Section 5.3.","marker":"[FGLM93]"},{"why":"Provides the modular techniques used in the implementation to control rational coefficient growth.","marker":"[Ste19]"},{"why":"Supports the average polynomial-time claim for zero-dimensional Gröbner bases used in the positive-dimensional remark.","marker":"[Lak91]"},{"why":"Also supports the average polynomial-time claim for zero-dimensional Gröbner bases in the positive-dimensional remark.","marker":"[LL91]"}],"fun_headline_variants":["Projection algorithm computes zero-dimensional tropical varieties fast","Zero-dimensional tropical varieties via projections: polynomial time","New projection method speeds up tropical variety computation","Polynomial-time tropical variety computation via projections","Efficient zero-dimensional tropical varieties using projections"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The polynomial-time guarantee assumes the field's valuation takes only rational values and that a reduced lex Gröbner basis in shape position is supplied; if either fails, the stated complexity bound is not established.","fun_headline_variants_meta":{"raw":{"variants":["Projection algorithm computes zero-dimensional tropical varieties fast","Zero-dimensional tropical varieties via projections: polynomial time","New projection method speeds up tropical variety computation","Polynomial-time tropical variety computation via projections","Efficient zero-dimensional tropical varieties using projections"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000198,"raw_usage":{"total_tokens":1332,"prompt_tokens":874,"completion_tokens":458,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":390}},"tokens_in":490,"tokens_out":458,"duration_ms":5308,"temperature":1.0,"reasoning_tokens":390,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:11:37.921970+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute Trop(I) for a zero-dimensional ideal in shape position over the 2-adic numbers by Algorithm 4.2 and independently by p-adic root approximation, comparing point sets with multiplicities; any mismatch would refute the correctness claim. A sharper test is to search for an ideal whose smallest injective slope $m$ exceeds $\\binom{d^2}{2}$, which would contradict Lemma 7.4.","supporting_citations":[],"review_version":1}