Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2504.21708 v1 pith:STC6IR4O submitted 2025-04-30 cs.SC cs.CCmath.AG

Thi Xuan Vu This is my paper · ORCID
classification cs.SCcs.CCmath.AG MSC 68W3013A5012Y0513P10
keywords polynomialrepresentationsubringmembershipNewton-Henselliftingstraight-lineprogramsalgebraicindependenceinvariantpolynomialscomplexityanalysispowerseries
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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))$.

Load-bearing premise

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).

Editorial extensions

If this is right

  • 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))$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 2, Proposition 2.1, Algorithm 1, Lemma 2.3(b)] 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.
  2. [Algorithm 2, Step 5; Section 3.2] 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).
  3. [Lemma 3.1] 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.
minor comments (4)
  1. [Keywords] The keyword 'invriant polynomials' contains a typo; it should read 'invariant polynomials'.
  2. [Theorem 3.4] 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.
  3. [Section 3.2] The phrase 'non-zempty' should be 'non-empty'.
  4. [Proof of Theorem 3.4, Step 5 complexity] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the algorithm composes h with the Hensel inverse of g; all load-bearing ingredients are classical external results, and no parameter is fitted to the target f.

full rationale

The derivation chain is self-contained. The main algorithm (Algorithm 2, Theorem 3.4/1.1) computes a power-series inverse y(u) of the polynomial map g near a generic point a, so that g(y(u)) = u + g(a), then evaluates h at this inverse series. Because the input assumption is h = f(g), the paper obtains h(y(u)) = f(u + g(a)) and recovers f by a translation. This is a direct function-composition derivation, not an assumption of the conclusion: the unknown f is never used in the computation, and correctness is meant to be checked by substituting the recovered f into the generators. No parameter is fitted to h or to a subset of data; Delta is an intrinsic degree bound on the unknown output, and the random generic point a is not fitted. The citations that carry mathematical weight are external and classical: Shephard–Todd/Chevalley–Serre for invariant rings (Theorem 4.4, Refs. [9,51,52]), the Jacobian criterion for algebraic independence (Refs. [32,2]), Baur–Strassen for derivative complexity, and Thom transversality (Ref. [46]) for Lemma 3.1. The author's own works cited in the paper are contextual applications of invariant-system solving, not load-bearing justifications of the central claim. Separate technical concerns — the off-by-one lifting precision in Proposition 2.1 (ceil(log2(delta)) iterations only guarantee order 2^k, which is insufficient when delta is a power of two), the missing dominance hypothesis in Lemma 3.1 as stated, and the sign inconsistency in Step 5 versus the appendix — are correctness defects in the exposition, not circularity: none of them makes the output equal to an input by construction. The algorithm is a direct constructive derivation against the input polynomials, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted parameters or invented entities. The algorithm depends on standard algebraic facts plus the problem assumptions. The main load-bearing point is the use of a generic point with full-rank Jacobian, which relies on algebraic independence of the g_i; this hypothesis is omitted from the statement of Lemma 3.1.

assumptions (5)
  • standard math The Jacobian matrix of algebraically independent g_1,...,g_n has nonzero determinant, so the set of points where it has full rank is a nonempty Zariski open set.
    Invoked in Lemma 3.1 and Section 3.1 to justify choosing a generic point a for the lifting initialization. Requires characteristic zero, or sufficiently large, per the cited references [32, 2].
  • standard math Newton-Hensel lifting guarantees a unique power series solution y(u) of g(y)=u+g(a) when the Jacobian at a is invertible.
    Proposition 2.1 and Section 2 restate the classical formal inverse function theorem for power series.
  • standard math Chevalley-Shephard-Todd theorem: K[x]^G is generated by n algebraically independent homogeneous polynomials iff G is generated by pseudo-reflections.
    Used in Theorem 4.4 and Lemma 4.5 to obtain the degree bound deg(f) <= deg(h) for invariant h.
  • domain assumption K has characteristic zero, or sufficiently large characteristic, so integer divisions in matrix inversion and the Jacobian criterion are valid.
    Stated in Theorem 1.1 and used in Section 2.2 for Berkowitz or Leverrier matrix inversion and in the Jacobian criterion for algebraic independence.
  • domain assumption h is an element of the subring S = K[g_1,...,g_n], so a unique f exists.
    This is the membership assumption of the problem, stated in Section 1; without it the representation may not exist or may not be unique.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings." pith.science (2026). https://pith.science/paper/STC6IR4O

@misc{pith2026250421708,
  author       = {Pith},
  title        = {Pith review of: Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/STC6IR4O}},
  note         = {Machine review of arXiv:2504.21708}
}
abstract

Let $\mathcal{R} = \mathbb{K}[x_1, \dots, x_n]$ be a multivariate polynomial ring over a field $\mathbb{K}$ of characteristic 0. Consider $n$ algebraically independent elements $g_1, \dots, g_n$ in $\mathcal{R}$. Let $\mathcal{S}$ denote the subring of $\mathcal{R}$ generated by $g_1, \dots, g_n$, and let $h$ be an element of $\mathcal{S}$. Then, there exists a unique element ${f} \in \mathbb{K}[u_1, \dots, u_n]$ such that $h = f(g_1, \dots, g_n)$. In this paper, we provide an algorithm for computing ${f}$, given $h$ and $g_1, \dots, g_n$. The complexity of our algorithm is linear in the size of the input, $h$ and $g_1, \dots, g_n$, and polynomial in $n$ when the degree of $f$ is fixed. Previous works are mostly known when $f$ is a symmetric polynomial and $g_1, \dots, g_n$ are elementary symmetric, homogeneous symmetric, or power symmetric polynomials.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Symbolic Computation with Symmetric Polynomials in Real Algebraic Geometry

    math.AG 2025-07 conditional

    A survey of algorithms that exploit permutation symmetry to speed up computations in real algebraic geometry.

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages · cited by 1 Pith paper

  1. [1]

    Baur and V

    W. Baur and V. Strassen. 1983. The complexity of partial d erivatives. Theoretical Computer Science 22, 3 (1983), 317–330

    work page 1983

  2. [2]

    Beecken, J

    M. Beecken, J. Mittmann, and N. Saxena. 2013. Algebraic i ndependence and blackbox identity testing. Information and Computation 222 (2013), 2–19

    work page 2013

  3. [3]

    S. J. Berkowitz. 1984. On computing the determinant in sm all parallel time using a small number of processors. Information processing letters 18, 3 (1984), 147– 150

    work page 1984

  4. [4]

    Bläser and G

    M. Bläser and G. Jindal. 2018. On the complexity of symmet ric polynomials. In 10th Innovations in Theoretical Computer Science Conferen ce (ITCS 2019) (Leib- niz International Proceedings in Informatics (LIPIcs)) , A. Blum (Ed.), Vol. 124. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagst uhl, Germany, 47:1– 47:14. https://doi.org/10.4230/LIPIcs.IT...

    work page doi:10.4230/lipics.itcs.2019.47 2018

  5. [5]

    D. G. Cantor and E. Kaltofen. 1991. On fast multiplicatio n of polynomials over arbitrary algebras. Acta Informatica 28, 7 (1991), 693–701

    work page 1991

  6. [6]

    Cardelli, M

    L. Cardelli, M. Tribastone, M. Tschaikowski, and A. Vand in. 2017. ERODE: a tool for the evaluation and reduction of ordinary differential eq uations. In Tools and Algorithms for the Construction and Analysis of Systems: 23 rd International Con- ference, TACAS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 20...

    work page 2017

  7. [7]

    Cardelli, M

    L. Cardelli, M. Tribastone, M. Tschaikowski, and A. Vandin. 2017. Maximal aggre- gation of polynomial dynamical systems. Proceedings of the National Academy of Sciences 114, 38 (2017), 10029–10034

    work page 2017

  8. [8]

    Chaugule, M

    P. Chaugule, M. Kumar, N. Limaye, C. K. Mohapatra, A. She, and S. Srinivasan

    work page

Show all 59 references
  1. [9]

    Chevalley

    C. Chevalley. 1955. Invariants of finite groups generate d by reflections. American Journal of Mathematics 77, 4 (1955), 778–782

    1955

  2. [10]

    A. Colin. 1997. Solving a system of algebraic equations with symme- tries. Journal of Pure and Applied Algebra 117-118 (1997), 195 – 215. https://doi.org/10.1016/S0022-4049(97)00011-X

    1997 doi

  3. [11]

    D. A. Cox, J. Little, and D. O’Shea. 2007. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3rd ed. Springer-Verlag New York, Inc., Secaucus, NJ, USA

    2007

  4. [12]

    Dahan, É

    X. Dahan, É. Schost, and J. Wu. 2009. Evaluation propert ies of invariant polyno- mials. Journal of Symbolic Computation 44, 11 (2009), 1592–1604

    2009

  5. [13]

    J. Damon. 1997. A global weighted version of Bézout’s th eorem. The Arnoldfest (Toronto, ON, 1997) 24 (1997), 115–129

    1997

  6. [14]

    Demin, E

    A. Demin, E. Demitraki, and G. Pogudin. 2023. Exact line ar reductions of dy- namical models. arXiv preprint arXiv:2301.11653 (2023)

    2023 arXiv

  7. [15]

    Ding-Feng, L

    Y. Ding-Feng, L. Kwok-Yan, and D. Zong-Duo. 1999. Crypt analysis of 2/u1D445 Schemes. In Advances in Cryptology—Crypto’99 . Springer, 315–325

    1999

  8. [16]

    Faugère, G

    J-C. Faugère, G. Labahn, M. Safey El Din, É. Schost, and T . X. Vu. 2023. Comput- ing critical points for invariant algebraic systems. Journal of Symbolic Compu- tation 116 (2023), 365–399

    2023

  9. [17]

    Faugère and L

    J.-C. Faugère and L. Perret. 2006. Cryptanalysis of 2/u1D445− schemes. In Advances in Cryptology-CRYPTO 2006: 26th Annual International Crypt ology Conference, Santa Barbara, California, USA, August 20-24, 2006. Proceedings 26. Springer, 357– 372

    2006

  10. [18]

    Faugère and L

    J.-C. Faugère and L. Perret. 2009. An efficient algorithm for decomposing mul- tivariate polynomials and its applications to cryptograph y. Journal of Symbolic Computation 44, 12 (2009), 1676–1689

    2009

  11. [19]

    Faugère, M

    J.-C. Faugère, M. Safey El Din, and T. Verron. 2016. On th e complexity of com- puting Gröbner bases for weighted homogeneous systems. Journal of Symbolic Computation 76 (2016), 107 – 141. https://doi.org/10.1016/j.jsc.2015 .12.001

    2016 doi

  12. [20]

    Feret, V

    J. Feret, V. Danos, J. Krivine, R. Harmer, and W. Fontana . 2009. Internal coarse- graining of molecular systems. Proceedings of the National Academy of Sciences 106, 16 (2009), 6453–6458

    2009

  13. [21]

    Feret, T

    J. Feret, T. Henzinger, H. Koeppl, and T. Petrov. 2012. L umpability abstractions of rule-based systems. Theoretical Computer Science 431 (2012), 137–164

    2012

  14. [22]

    Gatermann

    K. Gatermann. 1996. Semi-invariants, equivariants an d algorithms. Applicable Algebra in Engineering, Communication and Computing 7, 2 (1996), 105–124

    1996

  15. [23]

    Gaudry, É

    P. Gaudry, É. Schost, and N. M. Thiéry. 2006. Evaluation properties of symmetric polynomials. International Journal of Algebra and Computation 16, 03 (2006), 505–523

    2006

  16. [24]

    Giusti, M.and Heintz, J

    J. Giusti, M.and Heintz, J. E. Morais, J. Morgenstem, an d L. M. Pardo. 1998. Straight-line programs in geometric elimination theory. Journal of pure and applied algebra 124, 1-3 (1998), 101–146

    1998

  17. [25]

    Giusti, J

    M. Giusti, J. Heintz, K. Hägele, J. E. Morais, L. M. Pardo , and J. L. Montana. 1997. Lower bounds for Diophantine approximations. Journal of Pure and Applied Algebra 117 (1997), 277–317

    1997

  18. [26]

    Giusti, J

    M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. 1995. When polynomial equa- tion systems can be “solved” fast?. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 11th International Symposium, AA ECC-11 Paris, France, July 17–22, 1995 Proceedings 11 . Sp...

    1995

  19. [27]

    Giusti, G

    M. Giusti, G. Lecerf, and B. Salvy. 2001. A Gröbner free a lternative for polyno- mial system solving. Journal of complexity 17, 1 (2001), 154–211

    2001

  20. [28]

    Harvey and J

    D. Harvey and J. van der Hoeven. 2022. Polynomial multip lication over finite fields in time /u1D442(/u1D45B log /u1D45B). Journal of the ACM (JACM) 69, 2 (2022), 1–40

    2022

  21. [29]

    Heintz, T

    J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein . 2000. Deformation tech- niques for efficient polynomial equation solving. Journal of Complexity 16, 1 (2000), 70–109

    2000

  22. [30]

    Heintz and M

    J. Heintz and M. Sieveking. 1981. Absolute primality of polynomials is decidable in random polynomial time in the number of variables. In International Collo- quium on Automata, Languages, and Programming . Springer, 16–28

    1981

  23. [31]

    Hubert and G

    E. Hubert and G. Labahn. 2013. Scaling invariants and sy mmetry reduction of dynamical systems. Foundations of Computational Mathematics 13 (2013), 479– 516

    2013

  24. [32]

    J. E. Humphreys. 1992. Reflection groups and Coxeter groups . Number 29. Cam- bridge university press

    1992

  25. [33]

    Jiménez-Pastor and G

    A. Jiménez-Pastor and G. Pogudin. 2022. Computing exac t nonlinear reductions of dynamical models. ACM Communications in Computer Algebra 56, 2 (2022), 25–31

    2022

  26. [34]

    Kaltofen

    E. Kaltofen. 1988. Greatest common divisors of polynom ials given by straight- line programs. Journal of the ACM (JACM) 35, 1 (1988), 231–264

    1988

  27. [35]

    Kaltofen

    E. Kaltofen. 1989. Factorization of polynomials given by straight-line programs. Adv. Comput. Res. 5 (1989), 375–412

    1989

  28. [36]

    Krick and L

    T. Krick and L. M. Pardo. 1996. A computational method fo r diophantine approxi- mation. In Algorithms in algebraic geometry and applications. Springer, 193–253

    1996

  29. [37]

    Kronecker

    L. Kronecker. 1882. Grundzüge einer arithmetischen Th eorie der algebraischen Grössen. Journal für die Reine und Angewandte Mathematik 92 (1882), 1–122

  30. [38]

    Labahn, C

    G. Labahn, C. Riener, M. Safey El Din, É. Schost, and T. X. Vu. 2023. Faster real root decision algorithm for symmetric polynomials. In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computa tion. 452–460

    2023

  31. [39]

    Labahn, M

    G. Labahn, M. Safey El Din, É. Schost, and T. X. Vu. 2021. H omotopy techniques for solving sparse column support determinantal polynomia l systems. Journal of Complexity 66 (2021), 101557

    2021

  32. [40]

    U. J. J. Le Verrier. 1840. Sur les variations séculaires des éléments elliptiques des sept planètes principales: Mercure, Vénus, La Terre, Ma rs, Jupiter, Saturne et Uranus. J. Math. Pures Appli 4, 1840 (1840), 220–254

  33. [41]

    G. Lecerf. 2003. Computing the equidimensional decomp osition of an algebraic closed set by means of lifting fibers. Journal of Complexity 19, 4 (2003), 564–596

    2003

  34. [42]

    Lecerf and É

    G. Lecerf and É. Schost. 2003. Fast multivariate power s eries multiplication in characteristic zero. Electronic Journal of SADIO (EJS) 5 (2003), 1–10

    2003

  35. [43]

    Ovchinnikov, I

    A. Ovchinnikov, I. Pérez Verona, G. Pogudin, and M. Trib astone. 2021. CLUE: exact maximal reduction of kinetic models by constrained lumping of differential equations. Bioinformatics 37, 12 (2021), 1732–1738

    2021

  36. [44]

    Patarin and L

    J. Patarin and L. Goubin. 1997. Asymmetric cryptograph y with S-Boxes Is it eas- ier than expected to design efficient asymmetric cryptosystems?. In International Conference on Information and Communications Security . Springer, 369–380

    1997

  37. [45]

    Riener, R

    C. Riener, R. Schabert, and T. X. Vu. 2024. Connectivity in Symmetric Semi- Algebraic Sets. In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation . 162–169

    2024

  38. [46]

    Safey El Din and É

    M. Safey El Din and É. Schost. 2017. A nearly optimal algo rithm for deciding connectivity queries in smooth and bounded real algebraic s ets. Journal of the ACM (JACM) 63, 6 (2017), 1–37

    2017

  39. [47]

    Schönhage

    A. Schönhage. 1977. Schnelle Multiplikation von polyn omen über Körpern der Charakteristik 2. Acta Informatica 7, 4 (1977), 395–398

    1977

  40. [48]

    Schönhage and V

    A. Schönhage and V. Strassen. 1971. Schnelle Multiplik ation großer Zahlen. Computing 7, 3 (1971), 281–292

    1971

  41. [49]

    É. Schost. 2003. Computing parametric geometric resol utions. Applicable Alge- bra in Engineering, Communication and Computing 13, 5 (2003), 349–393

    2003

  42. [50]

    J. T. Schwartz. 1980. Fast probabilistic algorithms fo r verification of polynomial identities. Journal of the ACM (JACM) 27, 4 (1980), 701–717

    1980

  43. [51]

    J.-P. Serre. 1965. Algèbre Locale - Multiplicités, vol ume 11 of Lectures notes in mathematics

    1965

  44. [52]

    C Shephard and J

    G. C Shephard and J. A. Todd. 1954. Finite unitary reflect ion groups. Canadian Journal of Mathematics 6 (1954), 274–304

    1954

  45. [53]

    Sweedler

    M. Sweedler. 1993. Using Gröebner bases to determine th e algebraic and tran- scendental nature of field extensions: return of the killer t ag variables. In Ap- plied Algebra, Algebraic Algorithms and Error-Correcting Codes: 10th Interna- tional Symposium, AAECC-10 San Juan de ...

    1993

  46. [54]

    von zur Gathen and J

    J. von zur Gathen and J. Gerhard. 2003. Modern Computer Algebra (2 ed.). Cam- bridge University Press, New York, NY, USA

    2003

  47. [55]

    von zur Gathen, J

    J. von zur Gathen, J. Gutierrez, and R. Rubio. 2003. Mult ivariate polynomial de- composition. Applicable Algebra in Engineering, Communication and Computing 14, 1 (2003), 11–31

    2003

  48. [56]

    T. X. Vu. 2022. Computing critical points for algebraic systems defined by hype- roctahedral invariant polynomials. In Proceedings of the 2022 International Sym- posium on Symbolic and Algebraic Computation . 167–175

    2022

  49. [57]

    P. A. Worfolk. 1994. Zeros of equivariant vector fields: Algorithms for an invari- ant approach. Journal of Symbolic Computation 17, 6 (1994), 487–511. 9 , , Thi Xuan Vu

    1994

  50. [58]

    D. Ye, Z. Dai, and K.-Y. Lam. 2001. Decomposing attacks o n asymmetric cryp- tography based on mapping compositions. Journal of Cryptology 14 (2001), 137– 150. A AN EXAMPLE We illustrate the steps of our main algorithm (Algorithm 2) w ith a concrete example. Let us consider (/...

    2001

  51. [2023]

    Computational Complexity 32, 1 (2023), 3

    Schur polynomials do not have small formulas if the determinant does not. Computational Complexity 32, 1 (2023), 3

    2023

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.