{"id":"323d9307-23fd-4620-9c37-bcb37022fa26","arxiv_id":"2504.21708","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A randomized Newton-Hensel lifting algorithm computes the unique representation f of a polynomial h in a subring generated by algebraically independent polynomials g_1,...,g_n in O~((nL_1+n^4+L_2)M(Delta,n)) field operations.","lead":"This paper presents an algorithm that rewrites a polynomial h as an expression f in terms of n algebraically independent generators g_1,...,g_n of a subring, when such an expression exists. The method uses Newton-Hensel lifting and runs in time roughly linear in the input size when the degree of the unknown expression f is fixed.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Hensel lifting in Proposition 2.1/Algorithm 1 is off by one: for Delta a power of two (e.g., Delta=1) the returned series has insufficient precision, so Algorithm 2 fails on the valid instance g=x^2, h=x^2, f=u.","rationale":"I read the central claim as asserting a correct algorithm, not merely a plausible strategy. The lifting precision bug makes the provided algorithm concretely wrong on a degree-one instance, which is within the theorem's scope. The reader's identified weakest assumption, Lemma 3.1, is less central because in Theorem 1.1 the g_i are algebraically independent, so det Jac(g) is a nonzero polynomial and a good point a exists; the overstrong lemma can be bypassed. The off-by-one cannot be bypassed: the loop count in Algorithm 1 does not deliver the precision asserted by Proposition 2.1. I agree with the reader's CONDITIONAL verdict: the core construction is sound and fixable, but the printed pseudocode and proof need correction. Hence UNCHANGED. I disagree with the reader's selection of the weakest assumption; the off-by-one in the lifting loop is more directly load-bearing.","tokens_in":27080,"tokens_out":30166,"duration_ms":327594,"concrete_test":"Run Algorithm 1 exactly as printed on n=1, F=x^2-u-1, a=1, delta=1 (the loop body is skipped) and compare the residual F(1,u)=-u modulo <u>^1: Proposition 2.1 requires this residual to vanish, but -u does not. For delta=2 the loop runs once and returns y=1+u/2, whose residual is u^2/4, again not zero modulo <u>^2. End-to-end, run Algorithm 2 on g=x^2, h=x^2, Delta=1; the expected output is u, while the printed algorithm returns a constant regardless of which sign convention is used in Step 5.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing defect is an off-by-one error in the lifting precision. The paper defines <u>^delta as the ideal of monomials of degree at least delta+1, so D mod <u>^delta keeps terms of degree at most delta. Proposition 2.1 and Algorithm 1 claim that after ceil(log2(delta)) Newton iterations, starting from y^(0)=a, the resulting series satisfies y^(ceil(log2(delta)))=y mod <u>^delta. But the Newton iteration doubles the order of the residual: for F(x,u)=g(x)-u-g(a), at x=a the residual is F(a,u)=-u, of order 1, so after k iterations the residual has order 2^k. To be zero modulo <u>^delta one needs order at least delta+1, i.e., 2^k >= delta+1, hence k >= ceil(log2(delta+1)). The stated bound ceil(log2(delta)) is one iteration short exactly when delta is a power of two, including delta=1. Concretely, take n=1, g=x^2, h=x^2, so f(u)=u and Delta=1. With a=1, P=x^2-u-1. Algorithm 1 runs zero iterations and returns y=1, but y mod <u>^1 is 1+u/2. Algorithm 2 then outputs a constant instead of u. This failure is independent of the sign error in Step 5; even after correcting the translation, the truncated lifting does not carry the linear term needed for a degree-one f. Lemma 2.3 shows the same problem: it asserts F_i(y^(0),u)=0 mod <u>^1, whereas F_i(a,u)=-u_i is not in that ideal; the correct base is mod <u>^0. The error is easily repaired by iterating to ceil(log2(delta+1)), and the complexity estimate is unaffected up to a constant, so the mathematical idea survives.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the computational problem of expressing a polynomial h in a subring K[g_1,...,g_n] of K[x] as h=f(g_1,...,g_n) with f in K[u], where g_1,...,g_n are algebraically independent polynomials over a characteristic-zero field. The main contribution is a randomized algorithm based on Newton-Hensel lifting: after a generic linear translation, the system g(x)-u-g(a)=0 is lifted to a power series y(u), then h(y(u)) is computed to precision Delta, where Delta bounds the degree of f, followed by a back-translation to obtain f. The claimed complexity is O~((nL_1+n^4+L_2)M(Delta,n)) field operations, with L_1 and L_2 the straight-line program lengths of the generators and h. The paper also discusses degree bounds for weighted-homogeneous generators and for invariant rings of pseudo-reflection groups, and includes a worked example in Appendix A.","tokens_in":27472,"tokens_out":14448,"duration_ms":137175,"significance":"If the correctness issues identified below are repaired, the result is a significant generalization of earlier symmetric-polynomial special cases (Gaudry-Schost-Thiery, Blaser-Jindal, Chaugule et al.) to arbitrary algebraically independent generators, with a complexity bound that is linear in the input SLP sizes and polynomial in n for fixed degree. The power-series lifting approach is natural, and the worked example in Appendix A demonstrates the intended mechanics. The paper is also careful to note the Monte Carlo nature of the algorithm and to discuss degree bounds via weighted degrees for pseudo-reflection groups. However, the present version contains several load-bearing errors: the lifting precision is off by one, the final translation in Algorithm 2 has a sign error, and Lemma 3.1 is false without an additional dominance hypothesis. These issues are local and repairable, but they must be corrected before the paper can be accepted.","major_comments":[{"comment":"The lifting precision is off by one. The residual F_i(a,u)=-u_i has order 1, so after k Newton iterations the residual has order 2^k; to achieve F_i(y^(k),u)=0 mod <u>^delta one needs 2^k >= delta+1, i.e., k >= ceil(log2(delta+1)). The stated ceil(log2(delta)) iterations are insufficient exactly when delta is a power of two. For example, with n=1, g=x^2, h=x^2, we have f(u)=u and Delta=1; Algorithm 1 with delta=1 performs zero iterations and returns y=a, which is not y mod <u>^1, so the linear term of f is lost and the output is a constant instead of u. Lemma 2.3(b) similarly asserts F_i(a,u)=0 mod <u>^1, but -u_i is not in that ideal; the correct base case is mod <u>^0. The fix is to iterate to ceil(log2(delta+1)) (equivalently, one extra step when delta is a power of two), and the complexity analysis is unchanged because the geometric sum is dominated by the final term.","section":"Section 2, Proposition 2.1, Algorithm 1, Lemma 2.3(b)"},{"comment":"The sign in the final translation is wrong. The lifting equations give g(y(u))=u+g(a), so ell(u)=h(y(u))=f(u+g(a)); hence the output polynomial is obtained as ell(u-g(a)), exactly as executed in Appendix A. Step 5 as written returns ell(u+g(a)), which would produce f(u+2g(a)) in general. The statement in Section 3.2 that ell equals f(u-g(a)) is also incorrect; the correct identity is ell(u)=f(u+g(a)), and the subsequent translation direction should read u_i <- u_i - g_i(a).","section":"Algorithm 2, Step 5; Section 3.2"},{"comment":"Lemma 3.1 claims that for any polynomial system F in K[x], there exists a nonempty Zariski open set U0 such that the Jacobian of F has full rank at every point of U0. This is false without assuming the Jacobian determinant of F is not identically zero (i.e., F is dominant). For instance, F(x,y)=(x, x^2) has Jacobian rank 1 everywhere, so no such point exists and the lemma's conclusion fails. The proof via Thom's weak transversality requires the morphism F to be dominant in order to obtain a nonempty Zariski-open set of regular values in the target. The main theorem is not endangered because algebraic independence of the g_i implies the Jacobian determinant is nonzero by the Jacobian criterion, which is noted in Section 3.1, so a starting point can be chosen outside its zero set; but the lemma as stated and proved is incorrect and should carry the dominance hypothesis.","section":"Lemma 3.1"}],"minor_comments":[{"comment":"The keyword 'invriant polynomials' contains a typo; it should read 'invariant polynomials'.","section":"Keywords"},{"comment":"The theorem statement contains typos: 'randomzied algoritmo' should be 'randomized algorithm', and the phrase 'a bound on the degree of /u1D454' should refer to the degree of f.","section":"Theorem 3.4"},{"comment":"The phrase 'non-zempty' should be 'non-empty'.","section":"Section 3.2"},{"comment":"The claim that evaluating the translated SLP to obtain the output polynomial f costs O(L1+n+L2) operations underestimates the cost of expanding an SLP to a dense polynomial; the correct cost is O((L1+n+L2)M(Delta,n)), which is consistent with the stated total bound but is not 'negligible compared to the preceding steps' as asserted.","section":"Proof of Theorem 3.4, Step 5 complexity"}],"recommendation":"major_revision","confidential_remarks":"The central lifting idea is sound and the worked example in Appendix A confirms the intended computation, but the off-by-one precision error and the sign error in Algorithm 2 are concrete correctness bugs that must be fixed, and Lemma 3.1 needs a corrected hypothesis. All three are local and repairable, so I recommend inviting a revision rather than rejecting. The paper's comparison with prior work appears accurate and the SLP complexity framework is appropriate for a computer algebra venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear X,\n\nThe paper deserves a serious referee, but not because it is ready as printed. The core idea is genuinely useful: rewrite h as f(g_1,...,g_n) for algebraically independent generators by Newton-Hensel lifting, with a clean quasi-linear complexity bound in straight-line program length. The related work is careful, and the worked example in Appendix A actually verifies the intended mathematics. That part is good.\n\nThe problems are concrete and several.\n\nFirst, the lifting precision is off by one. Proposition 2.1 and Algorithm 1 iterate ceil(log2 δ) times, but Newton doubling starts from a residual of order 1, so you need ceil(log2(δ+1)) iterations to get precision δ. For δ=1 the algorithm does zero iterations and fails on g=x^2, h=x^2, f=u: it returns a constant. This is a real counterexample to Theorem 1.1 as stated. The fix is trivial — iterate one more time when δ is a power of two — and the complexity bound is unchanged, but the theorem as printed is false.\n\nSecond, the translation in Algorithm 2 Step 5 has the wrong sign. The appendix correctly uses f(u)=ℓ(u−g(a)); the pseudocode and the proof text say u+g(a). The example shows the correct version. This is the kind of error a referee should catch, but it means a reader cannot implement the algorithm as written.\n\nThird, Lemma 3.1 claims a nonempty Zariski open set of full-rank Jacobian points for any polynomial system. That is false without dominance: for F=(x_1^2,x_1^2) the preimage of the regular values is empty. In the main theorem the needed instance is true because algebraic independence makes the Jacobian determinant nonzero, so this is a missing hypothesis in the lemma statement, not a flaw in the application.\n\nThe adaptive degree-bound procedure at the end of Section 3 is also under-specified: the check for whether the candidate matches the desired output needs a concrete verification, though polynomial identity testing would work.\n\nNone of these are deep. The mathematical idea is sound, and the complexity analysis is plausible. What the paper needs is a careful revision that fixes the off-by-one and sign errors, restates Lemma 3.1, and formalizes the adaptive loop. As is, I would not trust the printed algorithm, but I would send it to a competent referee with the expectation of a conditional accept. The audience is computer algebra people working on invariant systems and polynomial decomposition; they will find the approach worth building on.\n\nBest,\n[You]","headline":"A useful Newton-lifting algorithm for subring membership with two concrete bugs (off-by-one precision, sign error) and one overstated lemma; the core idea is sound and worth a careful revision.","tokens_in":27978,"tokens_out":8916,"would_cite":false,"duration_ms":83864,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W30","13A50","12Y05","13P10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives a randomized algorithm that recovers the unique polynomial f with h = f(g_1,...,g_n) in near-linear time for any algebraically independent generators.","keywords":["polynomial representation","subring membership","Newton-Hensel lifting","straight-line programs","algebraic independence","invariant polynomials","complexity analysis","power series"],"falsifier":"Compute the Jacobian determinant of a candidate generator set: if it is identically zero, the generic full-rank point promised by the lifting lemma does not exist and the algorithm cannot initialize. For the claimed theorem, a direct test is to run the main algorithm on an algebraically independent instance with a known $f$, such as $h = g_1^2 + g_2$ with $g_1=x_1+x_2$ and $g_2=x_1x_2$, and vary the random starting point; failure for a positive-density set of points would contradict the claimed Monte Carlo correctness.","tokens_in":26853,"feed_emoji":"🧮","tokens_out":11595,"duration_ms":103901,"temperature":0.7,"pith_summary":"This paper solves a basic membership-and-rewriting question for polynomial subrings: given $n$ algebraically independent polynomials $g_1,\\dots,g_n$ and any $h$ in the subring they generate, find the unique polynomial $f$ with $h = f(g_1,\\dots,g_n)$. The proposed randomized algorithm returns $f$ in $\\widetilde{O}((nL_1+n^4+L_2)M(\\Delta,n))$ field operations, where $L_1,L_2$ are straight-line-program lengths for the generators and $h$, and $\\Delta$ bounds the degree of $f$. The interest is that this holds for arbitrary algebraically independent generators, not just the symmetric and elementary-symmetric cases treated in earlier work, and that the cost is near-linear in the input size and polynomial in $n$ when $\\Delta$ is fixed. For invariants of finite pseudo-reflection groups, a degree bound $\\Delta \\le \\deg h$ makes the complexity depend only on the degree of the input polynomial.","feed_headline":"New algorithm rewrites any subring polynomial in near-linear time","feed_subtitle":"The method works for any algebraically independent generators and keeps cost near-linear in the input size.","key_machinery":"Newton-Hensel lifting with a generic shift is the engine: instead of inverting $g$ directly, the algorithm picks a generic point $a$, forms the system $g_i(x)-u_i-g_i(a)=0$, and iteratively doubles the precision of the unique power series $y(u)$ with $y(0)=a$ and $g(y(u))=u+g(a)$. Each iteration evaluates the Jacobian of $g$ using symbolic differentiation whose cost is linear in the circuit size, inverts it in the truncated power-series ring, and multiplies power series; the cost is captured by $M(\\Delta,n)$, the cost of multiplying $n$-variate series to total degree $\\Delta$. A full-rank Jacobian at a generic point is required for the lifting to start; for the main theorem, algebraic independence makes the Jacobian determinant a nonzero polynomial, so such points form a nonempty open set. A final translation $u_i \\leftarrow u_i+g_i(a)$ recovers $f$ from the lifted series.","core_discovery":"The paper's central claim is Theorem 1.1 (restated as Theorem 3.4): over a characteristic-zero field $K$, for algebraically independent $g_1,\\dots,g_n \\in K[x]$ and $h \\in K[g_1,\\dots,g_n]$, there is a randomized algorithm that returns the unique $f \\in K[u_1,\\dots,u_n]$ with $h = f(g_1,\\dots,g_n)$, using $\\widetilde{O}((nL_1+n^4+L_2)M(\\Delta,n))$ operations in $K$, where $L_1$ and $L_2$ are the lengths of straight-line programs for the generators and $h$, and $\\Delta$ is a degree bound on $f$. The proof runs a Newton-Hensel lifting that constructs the power-series solution $y(u)$ of $g(y)=u$ near a generic point, evaluates $h$ at the truncated series, and shifts variables back to recover $f$. For $h$ invariant under a finite pseudo-reflection group, the paper obtains $\\Delta \\le \\deg h$, so the complexity becomes $\\widetilde{O}((nL_1+n^4+L_2)M(\\deg h,n))$.","pith_inferences":["A practical implementation should first verify that the Jacobian determinant of the generators is a nonzero polynomial before choosing random starting points, because the generic full-rank region is only guaranteed to be nonempty under that condition.","The algorithm suggests a new pipeline for multivariate polynomial decomposition: once candidate generators are found, recovering the outer polynomial is no longer the bottleneck, so the hardness shifts to the generator-finding step.","A weighted-degree refinement of $M(\\Delta,n)$ could tighten the complexity for weighted-homogeneous generators, since the paper's weighted-degree identity already pins down the degree of the representation.","The paper does not give an explicit probability bound for success; such a bound could be obtained by bounding the degree of the bad-point set and applying the standard probabilistic identity-testing lemma."],"forward_implications":["Any subring membership instance with algebraically independent generators can be solved in near-linear time in the input size whenever a degree bound is known, extending the earlier special cases of symmetric and power-sum bases.","For invariants of finite pseudo-reflection groups, the complexity becomes $\\widetilde{O}((nL_1+n^4+L_2)M(\\deg h,n))$, independent of the degrees of the basic invariants.","The output is produced as a straight-line program, so the construction composes naturally with polynomial-system solvers that accept circuit-encoded input and use lifting techniques.","The adaptive degree-doubling variant removes the need to know the degree bound in advance, at the same asymptotic cost.","When several polynomials $h_1,\\dots,h_m$ all lie in the subring, the same lifted series is computed once and each $h_i$ is evaluated separately, so the marginal cost per extra polynomial is $\\widetilde{O}(L_{h_i}M(\\Delta,n))$."],"supporting_citations":[{"why":"Originates the straight-line-program geometric elimination setting and the lifting machinery the algorithm builds on.","marker":"[25]"},{"why":"Supplies the derivative-complexity result used to compute the Jacobian of the generators in linear circuit cost.","marker":"[1]"},{"why":"Provides the division-free matrix-inversion routine used inside each lifting step.","marker":"[3]"},{"why":"Gives the fast multivariate power-series multiplication bound used for the $M(\\Delta,n)$ factor in the complexity.","marker":"[42]"},{"why":"Provides the algebraic transversality statement used to justify the existence of generic full-rank points.","marker":"[46]"},{"why":"States the earlier general invariant-rewriting cost that this paper's degree-dependent bound is compared against.","marker":"[12]"},{"why":"Gives the specialized symmetric-polynomial algorithm whose faster cost this paper generalizes to arbitrary generators.","marker":"[4]"},{"why":"Establishes the prior evaluation-complexity result for elementary symmetric polynomials that motivates the general subring problem.","marker":"[23]"},{"why":"Supplies the probabilistic identity-testing lemma used to control the success probability of random point selection.","marker":"[50]"}],"fun_headline_variants":["Near-linear algorithm computes subring polynomial form","New method rewrites subring polynomials in near-linear time","General generators? Near-linear polynomial rewrite algorithm","Fast polynomial representation for any algebraically independent set","Break symmetric limit: near-linear subring representation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lifting step needs a starting point where the Jacobian of $g_1,\\dots,g_n$ has full rank; the argument relies on algebraic independence of the generators to guarantee that such a point exists, but the paper states a lemma claiming this for all polynomial systems without that hypothesis, which is false (e.g., $g_1=x_1,\\ g_2=x_1^2$ have identically zero Jacobian determinant, so no full-rank point exists).","fun_headline_variants_meta":{"raw":{"variants":["Near-linear algorithm computes subring polynomial form","New method rewrites subring polynomials in near-linear time","General generators? Near-linear polynomial rewrite algorithm","Fast polynomial representation for any algebraically independent set","Break symmetric limit: near-linear subring representation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000195,"raw_usage":{"total_tokens":1397,"prompt_tokens":1025,"completion_tokens":372,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":641,"completion_tokens_details":{"reasoning_tokens":301}},"tokens_in":641,"tokens_out":372,"duration_ms":4671,"temperature":1.0,"reasoning_tokens":301,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:57:39.381133+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the Jacobian determinant of a candidate generator set: if it is identically zero, the generic full-rank point promised by the lifting lemma does not exist and the algorithm cannot initialize. For the claimed theorem, a direct test is to run the main algorithm on an algebraically independent instance with a known $f$, such as $h = g_1^2 + g_2$ with $g_1=x_1+x_2$ and $g_2=x_1x_2$, and vary the random starting point; failure for a positive-density set of points would contradict the claimed Monte Carlo correctness.","supporting_citations":[{"cited_title":"Giusti, J","cited_arxiv_id":null,"evidence_quote":"Originates the straight-line-program geometric elimination setting and the lifting machinery the algorithm builds on."},{"cited_title":"Baur and V","cited_arxiv_id":null,"evidence_quote":"Supplies the derivative-complexity result used to compute the Jacobian of the generators in linear circuit cost."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the division-free matrix-inversion routine used inside each lifting step."},{"cited_title":"Lecerf and É","cited_arxiv_id":null,"evidence_quote":"Gives the fast multivariate power-series multiplication bound used for the $M(\\Delta,n)$ factor in the complexity."},{"cited_title":"Safey El Din and É","cited_arxiv_id":null,"evidence_quote":"Provides the algebraic transversality statement used to justify the existence of generic full-rank points."},{"cited_title":"Dahan, É","cited_arxiv_id":null,"evidence_quote":"States the earlier general invariant-rewriting cost that this paper's degree-dependent bound is compared against."},{"cited_title":"Bläser and G","cited_arxiv_id":null,"evidence_quote":"Gives the specialized symmetric-polynomial algorithm whose faster cost this paper generalizes to arbitrary generators."},{"cited_title":"Gaudry, É","cited_arxiv_id":null,"evidence_quote":"Establishes the prior evaluation-complexity result for elementary symmetric polynomials that motivates the general subring problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the probabilistic identity-testing lemma used to control the success probability of random point selection."}],"review_version":1}