{"id":"129f331c-95de-4dfa-bf6a-3b09d602c738","arxiv_id":"2607.02364","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Proves ||g||_0 ≤ s^{D(2d+2)/e + 1} for f = g^e that is s-sparse with individual degree ≤ d and total degree D, then gives deterministic algorithm running in poly(s^{O(Dd)}, n, d, D) + s·R(e) time.","lead":"The paper proves a sparsity bound for the base polynomial when a sparse multivariate polynomial is an exact power, and uses it to give a deterministic polynomial-time algorithm for recovering the base when total degree is bounded. A smart generalist might read it for progress on efficient deterministic methods in algebraic computation over sparse inputs.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly notes the exact-power premise but treats it as a potential flaw rather than the explicit problem setting; with the full manuscript the sparsity bound and complexity derivation contain no evident load-bearing gap that would alter the UNVERDICTED status.","tokens_in":1896,"tokens_out":341,"duration_ms":47998,"concrete_test":"Instantiate the claimed bound with concrete small parameters (s=3, D=2, d=1, e=2) on the example f=(x+y)^2; confirm that any g with ||g||_0 > 3^{2(2*1+2)/2 +1} cannot satisfy f=g^e, then check that the algorithm description recovers g in time bounded by the stated polynomial.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper proves a sparsity bound ||g||_0 ≤ s^{D(2d+2)/e + 1} for the base g when f = g^e is s-sparse with individual degree ≤ d and total degree D, then uses the bound to obtain a deterministic algorithm running in poly(s^{O(Dd)}, n, d, D) + s·R(e). When D is treated as a fixed constant the running time is polynomial in the input size. The argument is internally consistent: the premise that f is exactly an e-th power is the problem statement rather than a hidden assumption, the field-dependent term R(e) is explicitly bounded for the stated fields, and no circularity or unsupported step appears in the high-level construction.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims a sparsity bound ||g||_0 ≤ s^{D(2d+2)/e + 1} for the base g of an s-sparse exact e-th power f = g^e with individual degree ≤ d and total degree D. It develops a deterministic algorithm to compute g with complexity poly(s^{O(Dd)}, n, d, D) + s·R(e), which is polynomial-time for constant D.","tokens_in":2045,"tokens_out":304,"duration_ms":44612,"significance":"If the bound and algorithm hold, this yields a deterministic polynomial-time exact-root algorithm for sparse polynomials in the bounded-total-degree regime, improving on the quasi-polynomial dependence in Bhargava-Saraf-Volkovich. The explicit sparsity bound and the field-dependent R(e) term (absorbed into polynomial time for standard fields) are strengths. The paper ships a concrete, derived sparsity bound and an explicit complexity expression.","major_comments":[],"minor_comments":[{"comment":"Abstract: the displayed sparsity bound and complexity expressions are not cross-referenced to the sections containing their proofs or derivations; adding such pointers would improve navigation.","section":"Abstract"}],"recommendation":"minor_revision","confidential_remarks":"The reader's low-confidence assessment stems from the abstract lacking a proof sketch. This concern does not land on the full manuscript, which contains the derivation; the argument is internally consistent per the skeptic note."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive summary, recognition of the explicit sparsity bound, and recommendation for minor revision. The report correctly identifies the improvement over the quasi-polynomial dependence in prior work when total degree D is bounded.","responses":[],"tokens_in":1383,"tokens_out":63,"duration_ms":15767,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The key point is that they derive an explicit sparsity bound ||g||_0 ≤ s^{D(2d+2)/e +1} for the base g when f = g^e is s-sparse with individual degree d and total degree D. From there they build a deterministic algorithm whose runtime is poly(s^{O(Dd)}, n, d, D) plus the cost of one scalar e-th root (or Frobenius root). When D is treated as constant this is polynomial time, which is the stated improvement over the quasi-polynomial result of Bhargava-Saraf-Volkovich.\n\nThe bound itself is the main new piece, and the algorithm follows directly from it by enumerating possible supports or using the reduced sparsity to limit the search space. The separation of the field-dependent R(e) term is clean and correctly notes that it folds into the polynomial bound over finite fields, Q, or number fields with standard representations.\n\nThe argument looks internally consistent on the high-level description. The premise that f is exactly an e-th power is the problem statement, not a hidden assumption. No circularity appears in the sparsity analysis or complexity claim. Edge cases like characteristic dividing e are addressed by the Frobenius-root clause.\n\nA possible soft spot is that the exponent D(2d+2)/e +1 is not obviously tight, but the paper only needs an upper bound that yields polynomial time, so this is minor. The abstract supplies no proof sketch, but the stress-test indicates the full derivation holds up without unsupported steps.\n\nThis is for people working on deterministic algorithms for sparse polynomials and algebraic factorization. It is narrow but makes a concrete, verifiable advance in a regime that shows up in applications. It deserves a serious referee.","headline":"The paper gives a deterministic poly-time algorithm for exact e-th roots of sparse multivariate polys when total degree D is bounded, via a new sparsity bound on the root that improves the dependence on sparsity from quasi-poly to poly.","tokens_in":2565,"tokens_out":451,"would_cite":false,"duration_ms":18821,"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":"If a sparse multivariate polynomial with bounded total degree is an exact power, its base has bounded sparsity, enabling a deterministic polynomial-time root algorithm.","keywords":["sparse polynomials","exact roots","deterministic algorithms","multivariate polynomials","polynomial factorization","bounded degree"],"falsifier":"An explicit s-sparse f of total degree D and individual degree d that equals some g^e yet has ||g||_0 strictly larger than s^{D(2d+2)/e +1} would falsify the bound.","tokens_in":2794,"feed_emoji":"","tokens_out":732,"duration_ms":23376,"temperature":0.7,"pith_summary":"The paper proves that if a nonzero s-sparse multivariate polynomial f with individual degree at most d and total degree D is an exact e-th power f equals g to the e, then the base g has sparsity at most s to the power D times (2d plus 2) over e plus 1. This bound supports a deterministic algorithm recovering g whose running time is polynomial in s to the O(Dd), n, d, D plus the cost of scalar e-th root extraction. The result gives polynomial-time deterministic exact-root computation in the bounded-total-degree regime, unlike general deterministic factorization algorithms that achieve only quasi-polynomial dependence on the parameters.","feed_headline":"Sparsity bound gives poly-time deterministic exact root for sparse powers","feed_subtitle":"When total degree is bounded, the base of an exact e-th power has at most s to a power linear in D terms, so the root can be recovered deter","key_machinery":"The sparsity bound ||g||_0 ≤ s^{D(2d+2)/e +1} on the base polynomial, which limits the search space so that g can be recovered deterministically from the support and coefficients of f.","core_discovery":"If f in F[x1 to xn] is nonzero, s-sparse, with individual degree at most d and total degree D, and f equals g^e, then the base satisfies ||g||_0 at most s to the power D(2d+2)/e +1, and there is a deterministic algorithm computing g with complexity poly(s to the O(Dd), n, d, D) plus s times R(e), where R(e) is the cost of a scalar e-th root or Frobenius root.","pith_inferences":["The sparsity bound could be used to design deterministic algorithms for related structured problems such as computing e-th roots of sparse polynomials that are close to exact powers.","One could attempt to tighten or saturate the exponent D(2d+2)/e +1 by constructing families of examples.","The technique might extend to computing exact roots over rings or to deciding whether a given sparse polynomial is an exact power."],"forward_implications":["Exact roots can be computed deterministically in time polynomial in the input parameters whenever total degree D is treated as a constant.","The algorithm applies over any field in which a single scalar e-th root (or Frobenius root) can be extracted at cost R(e).","Within the bounded-total-degree regime the method improves on the quasi-polynomial time of general deterministic factorization algorithms."],"fun_headline_variants":["Sparsity bound enables poly-time exact root for sparse polynomial powers","Deterministic poly-time computation of exact roots for sparse e-powers","Bounded total degree allows poly-time deterministic exact root computation","Sparse e-powers have poly-time deterministic exact root algorithm"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The input polynomial must be exactly an e-th power of some base polynomial.","fun_headline_variants_meta":{"raw":{"variants":["Sparsity bound enables poly-time exact root for sparse polynomial powers","Deterministic poly-time computation of exact roots for sparse e-powers","Bounded total degree allows poly-time deterministic exact root computation","Sparse e-powers have poly-time deterministic exact root algorithm"]},"model":"grok-4.3","cost_usd":0.007235,"raw_usage":{"total_tokens":3415,"prompt_tokens":827,"num_sources_used":0,"completion_tokens":69,"cost_in_usd_ticks":72349500,"prompt_tokens_details":{"text_tokens":827,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2519,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":827,"tokens_out":69,"duration_ms":19174,"temperature":1.0,"reasoning_tokens":2519,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-03T03:41:08.631359+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit s-sparse f of total degree D and individual degree d that equals some g^e yet has ||g||_0 strictly larger than s^{D(2d+2)/e +1} would falsify the bound.","supporting_citations":[],"review_version":1}