Pith. sign in

REVIEW 2 major objections 4 minor 117 references

Symbolic Computation with Symmetric Polynomials in Real Algebraic Geometry

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This chapter argues that permutation symmetry turns several hard computational problems in real algebraic geometry—emptiness, sampling, connectivity, and topological invariants—into problems that are polynomial in the ambient dimension…

desk verdict Useful survey of symmetric real algebraic geometry, but the Decide algorithm as presented is internally inconsistent and the Section 1.5.3 emptiness test is unreliable as written. read the letter →

arxiv 2507.23728 v1 pith:LCQ452UW submitted 2025-07-31 math.AG

Cordian Riener , Thi Xuan Vu This is my paper · ORCID
classification math.AG MSC 14P1014P2568W3013A50
keywords symmetricpolynomialsrealalgebraicgeometryhalf-degreeprinciplecriticalpointmethodorbitspacemirrorspacesBettinumbersconnectivityqueries
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 survey chapter makes the case that permutation symmetry is not merely a structural nicety but a computational lever: for polynomial systems invariant under relabeling of variables, the core tasks of real algebraic geometry—deciding emptiness, sampling real points, testing connectivity, and computing topological invariants—can be solved much faster than for general systems. The central payoff is that, when the degree is held fixed, the ambient dimension $n$ stops being the dominant cost parameter: several problems become polynomial in $n$, and sums-of-squares certificates can be built with matrices whose size no longer grows with $n$. The chapter also reports progress beyond fixed degree, including a randomized algorithm for testing whether a symmetric real algebraic set is empty. A sympathetic reader should take away that exploiting symmetry is now a systematic methodology, not a collection of ad hoc tricks.

What carries the argument

The load-bearing identity is the Fundamental Theorem of Symmetric Polynomials, which rewrites any symmetric polynomial $f$ of degree $d$ as $F(e_1,\ldots,e_d)$ in the elementary symmetric polynomials, automatically making the number of relevant variables depend on $d$ rather than $n$. Around this sit three mechanisms: the half-degree principle, which states that nonnegativity or feasibility of degree-$2d$ symmetric systems can be tested on vectors with at most $d$ (or $2d-1$) distinct coordinate values; the orbit-compression map $E_\lambda$ sending each orbit to its elementary symmetric functions, with Vandermonde maps providing homeomorphisms from Weyl chambers to their images; and the mirror-space basic construction, which reconstructs the full space's topology from its intersection with the Weyl chamber by gluing copies along reflection walls. These mechanisms are combined with the critical point method adapted to invariant systems, computing critical points orbit by orbit.

What would settle it

Run Algorithm 3 on the single symmetric equation $x_1^2 + \cdots + x_n^2 = 0$ for $n \ge 2$: the only real solution is the origin, where the Jacobian has rank $0$ instead of the required full rank, so the algorithm's assumption is violated and any incorrect "empty" answer would expose the assumption as load-bearing. A complementary check is to implement the connectivity algorithm of Theorem 20 on random symmetric quartics at $n = 10, 20, 40, 80$; if the observed growth is not polynomial in $n$, the claimed complexity bound is wrong.

Watch

Extended reading notes

Core claim

The chapter establishes that invariant-theoretic structure can be converted into complexity reductions for symbolic computation over the reals. The central claim is that for systems defined by polynomials invariant under the full symmetric group, the deciding factor is the degree rather than the number of variables: nonnegativity and feasibility can be certified on points with few distinct coordinate values (the half-degree principle), orbits can be compressed by the elementary symmetric map, and the orbit space can be coordinatized by finitely many power sums or Vandermonde images. From this, emptiness testing, connectivity queries, Betti number computations, and the Euler–Poincaré characteristic of symmetric semi-algebraic sets admit algorithms with complexity polynomial in $n$ for fixed degree, and the chapter presents a randomized emptiness algorithm that extends the gain beyond the fixed-degree regime under a full-rank Jacobian assumption. The mirror-space construction then transfers the topological information obtained in the Weyl chamber back to the full ambient space.

Load-bearing premise

The emptiness algorithm assumes the defining polynomials' Jacobian matrix has full rank at every solution; if the real solution set contains a singular point, the critical-point construction and the lemmas that transfer rank to the compressed system no longer apply.

Editorial extensions

If this is right

  • For fixed degree $d$, emptiness, connectivity, and Euler–Poincaré characteristic computations on $S_n$-invariant semi-algebraic sets run in time polynomial in the dimension $n$, with exponent depending only on $d$.
  • For $n \ge 2d$, the Gram matrix needed to decide whether a symmetric form is a sum of squares has size depending only on $d$, so symmetric SOS relaxations remain low-dimensional as $n$ grows.
  • The Betti numbers of the orbit space $S/S_n$ vanish in degrees at least $\min(n,d)$, and for fixed $d$ the equivariant Betti numbers are bounded polynomially in $n$.
  • Connectivity between two points in a symmetric set can be decided by sorting into the Weyl chamber, testing connectivity there, and checking finitely many wall conditions indexed by adjacent transpositions.
  • For systems satisfying the full-rank Jacobian condition, the randomized Real Emptiness algorithm handles degrees that grow with $n$, with complexity polynomial in $n$ and singly exponential in the degree.

Reading between the lines

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

  • Beyond the paper: if these reductions hold as stated, any polynomial system with visible permutation symmetry—say from sensor networks, voting theory, or symmetric optimization—should first be attacked through orbit-space reduction before general-purpose methods are used.
  • Beyond the paper: the half-degree principle suggests a practical probabilistic filter for large symmetric feasibility problems: sample random points with few distinct coordinates as a quick rejection test before committing to full-dimensional symbolic algorithms.
  • Beyond the paper: the mirror-space strategy is promised to extend to other reflection groups; a natural testbed would be hyperoctahedral symmetry, where the same wall-gluing construction should yield analogous connectivity algorithms.
  • Beyond the paper: the full-rank Jacobian assumption in Real Emptiness is the main gap to generality; a preprocessing step that detects and removes singular strata would make the algorithm applicable to arbitrary symmetric systems.
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

2 major / 4 minor

Summary. This manuscript is a survey chapter on symbolic computation with symmetric polynomials in real algebraic geometry. The authors review classical background (symmetric polynomials, orbit spaces, critical point methods), the degree principle, sums-of-squares stabilization, and more recent results on fixed-degree complexity bounds, emptiness testing, Betti numbers, mirror spaces, and connectivity algorithms for Sn-invariant semi-algebraic sets. The central assertion is that permutation symmetry can reduce the complexity of core real-algebraic tasks, often making them polynomial in the ambient dimension for fixed degree. The chapter is largely a synthesis of the authors' own prior work and related literature, with complexity statements reproduced from cited papers.

Significance. If the survey is accurate, it serves a useful role as a unified reference for a body of results on symmetric real algebraic geometry, including the half-degree principle, equivariant Betti number bounds, and connectivity algorithms. The chapter is clearly organized and provides concrete complexity bounds for many procedures. However, the self-contained decision procedure in Section 1.3.4 contains a logical inconsistency that is load-bearing for the emptiness-testing algorithm of Section 1.5.3, and Theorem 14 states a stronger claim than the algorithm's explicit hypotheses support. These issues need to be corrected before the chapter can be relied upon as a reference for the methods it presents.

major comments (2)
  1. [1.3.4, Algorithm 2 and Theorem 4] The semantics of Algorithm 2 contradict Theorem 4. Algorithm 2's Ensure line states that it returns 'true if all fibers of Wλ by the map Eλ contain real points, false otherwise', and its control flow returns false as soon as one real root ϑ of q yields a Vieta polynomial with fewer than ℓ_i real roots. Theorem 4, however, claims the output is 'yes if E^{-1}(Wλ) has a real point and no otherwise'. These two characterizations are not equivalent. For a concrete instance in the one-block case ℓ=2, take q(T)=T(T-1), v_{1,1}=T, v_{1,2}=T-1; this is a valid zero-dimensional parametrization. For T=1, ρ(u,1)=u^2-1 has two real roots, so the fiber over (1,0) contains real preimages; for T=0, ρ(u,0)=-(u^2+1) has no real roots, so Algorithm 2 returns false at T=0 even though E^{-1}(Wλ) is nonempty. The algorithm should return true as soon as a fully real-splitting fiber is found, and false only if no such fiber exists. As written, Algorithm 3's use of Decide as an emptiness test is unsound, since 'false' can be returned both when the preimage is empty and when it is nonempty.
  2. [1.5.3, Theorem 14] Theorem 14 states that the Real Emptiness algorithm takes a sequence of symmetric polynomials f and returns true if and only if V(f)∩R^n is empty, with no rank hypothesis. This is stronger than the algorithm actually presented. Algorithm 3 explicitly assumes 'the Jacobian matrix of f has rank s at any point in V(f)', and Section 1.5.3 begins with 'Assume further that the Jacobian matrix of f ... has rank s at any point in V(f)'. This rank hypothesis is load-bearing: it is needed to apply Lemmas 4 and 5 to transfer full rank from f to f[λ] and from g to G, and to invoke Proposition 2 and Lemma 8 guaranteeing that the critical locus is finite and that the Critical Points procedure applies. The statement of Theorem 14 should either include the rank assumption explicitly or explain how the singular case is handled; as stated, it is misleading.
minor comments (4)
  1. [1.3.4, Theorem 4] The word 'zero-dimensitional' should be 'zero-dimensional'.
  2. [1.6.2, Theorem 17] The theorem statement says 'decides whether u and u are orbit-connected'; this should presumably be 'u and v'.
  3. [1.6.5, Final Discussions] There are several typographical errors in this paragraph, including 'Computationaly', 'have have provided', 'approachess', and 'taken symmetry into account'.
  4. [1.3.3, Example 16] In the display after Example 16, 'U strict (13)' appears twice; the second occurrence should likely be 'U strict (11 21)', based on the surrounding partition notation.

Circularity Check

0 steps flagged · score 2.0 of 10

No circularity found: survey statements are cited prior work, and self-citations are normal survey sourcing rather than load-bearing reductions.

full rationale

This is a survey chapter, so its assertions are citations to prior work rather than derivations within the paper; that is not circularity. Theorems 6 and 12–20 are sourced to peer-reviewed papers, several by the present authors (e.g., [91,93], [11,12], [95,96], [77]), but this is normal survey sourcing, the cited results have independent content and stated assumptions, and no fitted parameter is renamed as a prediction and no ansatz is smuggled in via citation. Two non-circular concerns are worth recording. First, in Section 1.3.4, Algorithm 2's stated semantics ('true if all fibers of Wλ by Eλ contain real points, false otherwise') do not match Theorem 4's claimed output ('yes if E−1λ(Wλ) has a real point'): the union is nonempty as soon as one fiber is nonempty, while 'false' is triggered by the first fiber with fewer than ℓi real roots; the proof of Theorem 4 gives only complexity, not correctness. Second, Algorithm 3 in Section 1.5.3 is stated under the rank assumption on Jac(f), but Theorem 14 drops that assumption. These are correctness gaps, not circular reductions. The circularity score is therefore low.

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

This survey introduces no new axioms, free parameters, or entities. It depends on classical background: the fundamental theorem of symmetric polynomials, Tarski-Seidenberg, the critical point method, the representation theory of S_n, and the mirror space reconstruction theorem. The only explicit computational assumption is the full-rank Jacobian condition in Algorithm 3, which is not guaranteed for arbitrary symmetric systems and is a genuine limitation of the surveyed algorithms.

assumptions (6)
  • standard math Fundamental Theorem of Symmetric Polynomials (every symmetric polynomial is a unique polynomial in e1,...,en)
    Invoked in Section 1.3.1 (Theorem 2) and throughout to reduce dimension by replacing x1,...,xn with elementary symmetric polynomials.
  • standard math Tarski-Seidenberg theorem and the existence of quantifier elimination over real closed fields
    Background for the decision problems in Section 1.1.3 and the baseline algorithms in Table 2.
  • domain assumption Availability of critical point and roadmap algorithms for general semi-algebraic sets
    Sections 1.1.4-1.1.5 and the complexity table assume these as building blocks, citing [7] and [22].
  • domain assumption Full-rank Jacobian condition on input systems (rank s at every point of V(f))
    Explicit assumption in Algorithm 3 (Real Emptiness); Lemmas 4 and 5 depend on it to transfer rank from f to f[lambda] and from g to G.
  • standard math Generic random choices avoid Zariski closed subsets (Schwartz-Zippel lemma)
    Section 1.2.4; the probabilistic steps in Algorithm 3 and Lemma 8 rely on this.
  • standard math Representation theory of the symmetric group (isotypic decomposition, Schur's Lemma)
    Used in Section 1.4.1 to justify the fixed-size Gram matrix in Theorem 6.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Symbolic Computation with Symmetric Polynomials in Real Algebraic Geometry." pith.science (2026). https://pith.science/paper/LCQ452UW

@misc{pith2026250723728,
  author       = {Pith},
  title        = {Pith review of: Symbolic Computation with Symmetric Polynomials in Real Algebraic Geometry},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LCQ452UW}},
  note         = {Machine review of arXiv:2507.23728}
}
read the original abstract

Symmetry plays a central role in accelerating symbolic computation involving polynomials. This chapter surveys recent developments and foundational methods that leverage the inherent symmetries of polynomial systems to reduce complexity, improve algorithmic efficiency, and reveal deeper structural insights. The main focus is on symmetry by the permutation of variables.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

117 extracted references · 79 canonical work pages

  1. [1]

    Acevedo, M

    J.G. Acevedo, M. Velasco: Test sets for nonnegativity of polynomials invariant under a finite reflection group, Journal of Pure and Applied Algebra, 220 (2016)

    2016

  2. [2]

    Foundations of Computational Mathematics , (to appear)

    Acevedo, J., Blekherman, G., Debus, S., Riener, C.: The wonderful geometry of the Vandermonde map. Foundations of Computational Mathematics , (to appear)

  3. [3]

    In: Algorithms in Algebraic Geometry and Applications, pp

    Alonso, M.-E., Becker, E., Roy, M.-F., W¨ ormann, T.: Zeros, multiplicities, and idem- potents for zero-dimensional systems. In: Algorithms in Algebraic Geometry and Applications, pp. 1–15. Springer (1996)

    1996

  4. [4]

    I.: Hyperbolic polynomials and Vandermonde mappings

    Arnold, V. I.: Hyperbolic polynomials and Vandermonde mappings. Funktsional’nyi Analiz i ego Prilozheniya , 20(2):52–53 (1986)

    1986

  5. [5]

    Journal of the ACM, 43(6), 1002–1045 (1996)

    Basu, S., Pollack, R., Roy, M.-F.: On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM, 43(6), 1002–1045 (1996)

    1996

  6. [6]

    Journal of the American Mathematical Society, 13(1), 55–82 (2000)

    Basu, S., Pollack, R., Roy, M.-F.: Computing roadmaps of semi-algebraic sets on a variety. Journal of the American Mathematical Society, 13(1), 55–82 (2000)

    2000

  7. [7]

    Algo- rithms and Computation in Mathematics, vol

    Basu, S., Pollack, R., Roy, M.-F.: Algorithms in Real Algebraic Geometry. Algo- rithms and Computation in Mathematics, vol. 10. Springer (2006)

    2006

  8. [8]

    Discrete & Computational Geometry, 52:278–343 (2014) 55

    Basu, S., Roy, M.-F.: Divide and conquer roadmap for algebraic sets. Discrete & Computational Geometry, 52:278–343 (2014) 55

    2014

Show all 117 references
  1. [9]

    Foundations of Computational Mathematics , 14:1117–1172 (2014)

    Basu, S., Roy, M.-F., Safey El Din, M., Schost, ´E.: A baby step–giant step roadmap algorithm for general algebraic sets. Foundations of Computational Mathematics , 14:1117–1172 (2014)

    2014

  2. [10]

    arXiv preprint arXiv:1409.1534 (2014)

    Basu, S.: Algorithms in real algebraic geometry: a survey. arXiv preprint arXiv:1409.1534 (2014)

    2014 arXiv

  3. [11]

    Advances in Mathematics , 305:803–855 (2017)

    Basu, S., Riener, C.: Bounding the equivariant Betti numbers of symmetric semi- algebraic sets. Advances in Mathematics , 305:803–855 (2017)

    2017

  4. [12]

    Basu, S., Riener, C.: Efficient algorithms for computing the Euler–Poincar´ e char- acteristic of symmetric semi-algebraic sets. In Ordered Algebraic Structures and Re- lated Topics: International Conference on Ordered Algebraic Structures and Related Topics, October 12–16, 20...

    2017

  5. [13]

    Selecta Mathematica, 24:3241–3281 (2018)

    Basu, S., Riener, C.: On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms. Selecta Mathematica, 24:3241–3281 (2018)

    2018

  6. [14]

    Foundations of Computational Mathematics, 22(5), 1395–1462 (2022)

    Basu, S., Riener, C.: Vandermonde varieties, mirrored spaces, and the cohomol- ogy of symmetric semi-algebraic sets. Foundations of Computational Mathematics, 22(5), 1395–1462 (2022)

    2022

  7. [15]

    In 10th In- novations in Theoretical Computer Science Conference (ITCS 2019) (Leibniz In- ternational Proceedings in Informatics (LIPIcs), Vol

    Bl¨ aser, M., Jindal, G.: On the complexity of symmetric polynomials. In 10th In- novations in Theoretical Computer Science Conference (ITCS 2019) (Leibniz In- ternational Proceedings in Informatics (LIPIcs), Vol. 124), A. Blum (Ed.). Schloss Dagstuhl–Leibniz-Zentrum fuer Info...

    2019

  8. [16]

    Israel Journal of Mathematics , 153:355–380 (2006)

    Blekherman, G.: There are significantly more nonnegative polynomials than sums of squares. Israel Journal of Mathematics , 153:355–380 (2006)

    2006

  9. [17]

    and Riener, C

    Blekherman, G. and Riener, C. Symmetric nonnegative forms and sums of squares. Discrete and Computational Geometry , 57(4):854–886 (2017)

    2017

  10. [18]

    and Riener, C.: Symmetric non-negative forms and sums of squares

    Blekherman, G. and Riener, C.: Symmetric non-negative forms and sums of squares. Discrete & Computational Geometry , 65:764–799 (2021)

    2021

  11. [19]

    Springer Science & Business Media (2012)

    Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer Science & Business Media (2012)

    2012

  12. [20]

    Banach Center Publications, 44(1):37–50 (1998)

    Br¨ ocker, L.: On symmetric semialgebraic sets and orbit spaces. Banach Center Publications, 44(1):37–50 (1998)

    1998

  13. [21]

    W., Davenport, J

    Brown, C. W., Davenport, J. H.: The complexity of quantifier elimination and cylindrical algebraic decomposition. In: Proceedings of the 2007 International Sym- posium on Symbolic and Algebraic Computation, pp. 54–60 (2007)

    2007

  14. [22]

    MIT Press, Cambridge, MA (1987)

    Canny, J.: The Complexity of Robot Motion Planning. MIT Press, Cambridge, MA (1987)

    1987

  15. [23]

    The Computer Journal, 36(5), 504–514 (1993)

    Canny, J.: Computing roadmaps of general semi-algebraic sets. The Computer Journal, 36(5), 504–514 (1993)

    1993

  16. [24]

    N.: Finding connected components of a semialgebraic set in subexponential time

    Canny, J., Grigor’ev, Yu, D., Vorobjov, N. N.: Finding connected components of a semialgebraic set in subexponential time. Applicable Algebra in Engineering, Communication and Computing , 2(4), 217–238 (1992)

    1992

  17. [25]

    In: Proceedings of the 45th International Symposium on Sym- bolic and Algebraic Computation (ISSAC 2020) , pp

    Capco, M., Safey El Din, M., Schicho, J.: Robots, computer algebra and eight con- nected components. In: Proceedings of the 45th International Symposium on Sym- bolic and Algebraic Computation (ISSAC 2020) , pp. 62–69. ACM (2020)

    2020

  18. [26]

    Journal of Symbolic Computation, 115, 320–345 (2023)

    Capco, M., Safey El Din, M., Schicho, J.: Positive dimensional parametric polyno- mial systems, connectivity queries and applications in robotics. Journal of Symbolic Computation, 115, 320–345 (2023)

    2023

  19. [27]

    Cox, D., Little, J., O’shea, D., Sweedler, M.: Ideals, varieties, and algorithms, vol

  20. [28]

    E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition

    Collins, G. E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Lecture notes in computer science, 33:515–532 (1975)

    1975

  21. [29]

    K., She, A., Srinivasan, S.: Schur polynomials do not have small formulas if the determinant does not

    Chaugule, P., Kumar, M., Limaye, N., Mohapatra, C. K., She, A., Srinivasan, S.: Schur polynomials do not have small formulas if the determinant does not. Compu- tational Complexity 32, 1 (2023)

    2023

  22. [30]

    H., May, J

    Chen, C., Davenport, J. H., May, J. P., Moreno Maza, M., Xia, B., Xiao, R.: Triangular Decomposition of Semi-Algebraic Systems. In: Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, pp. 187–194. Springer (2010)

    2010

  23. [31]

    In: Proceedings of the 2009 Interna- tional Symposium on Symbolic and Algebraic Computation, pp

    Chen, C., Moreno Maza, M., Xia, B., Yang, L.: Computing Cylindrical Algebraic Decomposition via Triangular Decomposition. In: Proceedings of the 2009 Interna- tional Symposium on Symbolic and Algebraic Computation, pp. 95–102. Springer (2009)

    2009

  24. [32]

    Y., Reznick, B.: Sums of squares of real polynomials

    Choi, M.-D., Lam, T. Y., Reznick, B.: Sums of squares of real polynomials. In Proceedings of Symposia in Pure Mathematics, volume 58, pages 103–126. American Mathematical Society (1995)

    1995

  25. [33]

    H., Heintz, J.: Real quantifier elimination is doubly exponential

    Davenport, J. H., Heintz, J.: Real quantifier elimination is doubly exponential. Journal of Symbolic Computation, 5(1-2), 29–35 (1988)

    1988

  26. [34]

    W.: Groups generated by reflections and aspherical manifolds not covered by Euclidean space

    Davis, M. W.: Groups generated by reflections and aspherical manifolds not covered by Euclidean space. Ann. of Math. (2), 117(2):293–324 (1983)

    1983

  27. [35]

    W.: The Geometry and Topology of Coxeter Groups

    Davis, M. W.: The Geometry and Topology of Coxeter Groups . London Mathe- matical Society Lecture Note Series, vol. 32, Princeton University Press, Princeton (2008)

    2008

  28. [36]

    Journal of Symbolic Computation, 119:112–144 (2023)

    Debus, S., Riener, C.: Reflection groups and cones of sums of squares. Journal of Symbolic Computation, 119:112–144 (2023)

    2023

  29. [37]

    Verdure, H

    Debus, S, Moustrou, P, Riener, C. Verdure, H. The poset of Specht ideals for hyperoctahedral groups. Algebraic Combinatorics, Volume 6 no. 6, pp. 1593-1619 (2023)

    2023

  30. [38]

    Debus, S., Gottwald, K. K. Posets for Specht ideals of essential real reflection groups. arXiv preprint arXiv:2506.15335 (2025)

    2025 arXiv

  31. [39]

    Springer (2015)

    Derksen, H., Gregor, K.: Computational Invariant Theory. Springer (2015)

    2015

  32. [40]

    L.: Systems of linear inequalities

    Dines, L. L.: Systems of linear inequalities. Annals of Mathematics, pages 191–199 (1919)

    1919

  33. [41]

    248, Cambridge University Press, Cambridge (1998)

    van den Dries, L.: Tame topology and o-minimal structures, London Mathematical Society Lecture Note Series, vol. 248, Cambridge University Press, Cambridge (1998)

    1998

  34. [42]

    Graduate Texts in Mathematics, vol

    Eisenbud, D.: Commutative Algebra: with a View Toward Algebraic Geometry. Graduate Texts in Mathematics, vol. 150. Springer, New York (2013)

    2013

  35. [43]

    In: Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2020), pp

    Elliott, J., Giesbrecht, M., Schost, ´E.: On the bit complexity of finding points in connected components of a smooth real hypersurface. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2020), pp. 170–177. ACM, New York (2020)

    2020

  36. [44]

    H.: Cylindrical Algebraic Decomposition with Equational Constraints

    England, M., Bradford, R., Davenport, J. H.: Cylindrical Algebraic Decomposition with Equational Constraints. J. Symb. Comput. 100, 38–71 (2020)

    2020

  37. [45]

    X.: Computing critical points for invariant algebraic systems

    Faug` ere, J.-C., Labahn, G., Safey El Din, M., Schost, ´E., Vu, T. X.: Computing critical points for invariant algebraic systems. Journal of Symbolic Computation, 116, 365–399 (2023)

    2023

  38. [46]

    Sanyal, R.: Reflection groups, reflection arrangements, and invariant real varieties.Proceedings of the American Mathematical Society, 146(3) (2018)

    Friedl, T., Riener, C. Sanyal, R.: Reflection groups, reflection arrangements, and invariant real varieties.Proceedings of the American Mathematical Society, 146(3) (2018)

    2018

  39. [47]

    Fourier, J. B. J.: Solution d’une question particuliere du calcul des in´ egalit´ es. Nou- veau Bulletin des Sciences par la Soci´ et´ e philomatique de Paris, 99:100 (1826) 57

  40. [48]

    A.: Symmetry groups, semidefinite programs, and sums of squares

    Gatermann, K., Parrilo, P. A.: Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra , 192(1–3):95–128 (2004)

    2004

  41. [49]

    Applicable Algebra in Engineering, Communication and Computing 14, 1, 11–3 (2003)

    von zur Gathen, J., Gutierrez, J., Rubio, R.: Multivariate polynomial decompo- sition. Applicable Algebra in Engineering, Communication and Computing 14, 1, 11–3 (2003)

    2003

  42. [50]

    von zur Gathen, J., Gerhard, J.: Modern Computer Algebra. 2nd edn. Cambridge University Press (2003)

    2003

  43. [51]

    M: Evaluation properties of symmetric polyno- mials

    Gaudry, P., Schost, ´E., Thi´ ery, N. M: Evaluation properties of symmetric polyno- mials. International Journal of Algebra and Compu- tation 16, 03, 505–523 (2006)

    2006

  44. [52]

    In: AAECC, vol

    Gianni, P., Mora, T.: Algebraic solution of systems of polynomial equations using Gr¨ obner bases. In: AAECC, vol. 356, pp. 247–257. Springer (1989)

    1989

  45. [53]

    Linear Algebra and its Applications , 496:114–120 (2016)

    Goel, C., Kuhlmann, S., Reznick, B.: On the Choi–Lam analogue of Hilbert’s 1888 theorem for symmetric forms. Linear Algebra and its Applications , 496:114–120 (2016)

    2016

  46. [54]

    Journal of Symbolic Computation, 74, 603-616 (2016)

    G¨ orlach, P., Riener, C., Weißer, T.: Deciding positivity of multisymmetric poly- nomials. Journal of Symbolic Computation, 74, 603-616 (2016)

    2016

  47. [55]

    B.: Moments of random variables and the equivariant Morse lemma

    Givental, A. B.: Moments of random variables and the equivariant Morse lemma. Russian Mathematical Surveys , 42(2):275–276 (1987)

    1987

  48. [56]

    In: AAECC-11, pp

    Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M.: When polynomial equation sys- tems can be “solved” fast?. In: AAECC-11, pp. 205–231. Springer (1995)

    1995

  49. [57]

    Giusti, M., Heintz, J., Morais, J.-E., Pardo, L.-M.: When polynomial equation systems can be solved fast? In: AAECC-11, vol. 948, pp. 205–231. Springer (1995)

    1995

  50. [58]

    Giusti, M., Heintz, J., H¨ agele, K., Morais, J.E., Pardo, L.M., Montana, J.L.: Lower bounds for Diophantine approximations. J. Pure Appl. Algebra 117, 277–317 (1997)

    1997

  51. [59]

    Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M.: Straight-line programs in geometric elimination theory. J. Pure Appl. Algebra 124(1–3), 101–146 (1998)

    1998

  52. [60]

    Giusti, M., Lecerf, G., Salvy, B.: A Gr¨ obner-free alternative for polynomial system solving. J. Complexity 17(1), 154–211 (2001)

    2001

  53. [61]

    Journal of Symbolic Computation, 5, 37–64 (1988)

    Grigoriev, D., Vorobjov, N.: Solving systems of polynomial inequalities in subex- ponential time. Journal of Symbolic Computation, 5, 37–64 (1988)

    1988

  54. [62]

    Yu., Vorobjov, N.: Counting connected components of a semialgebraic set in subexponential time

    Grigor’ev, D. Yu., Vorobjov, N.: Counting connected components of a semialgebraic set in subexponential time. Computational Complexity , 2, 133–186 (1992)

    1992

  55. [63]

    Appli- cable Algebra in Engineering, Communication and Computing, 4(4):239–252 (1993)

    Gournay, L., Risler, J.-J.: Construction of roadmaps in semi-algebraic sets. Appli- cable Algebra in Engineering, Communication and Computing, 4(4):239–252 (1993)

    1993

  56. [64]

    The Computer Journal, 36(5), 427–431 (1993)

    Heintz, J., Roy, M.-F., Solern` o, P.: On the theoretical and practical complexity of the existential theory of the reals. The Computer Journal, 36(5), 427–431 (1993)

    1993

  57. [65]

    Springer Science & Business Me- dia (2013)

    Hartshorne, R.: Algebraic Geometry, volume 52. Springer Science & Business Me- dia (2013)

    2013

  58. [66]

    In: ICALP, pp

    Heintz, J., Sieveking, M.: Absolute primality of polynomials is decidable in random polynomial time in the number of variables. In: ICALP, pp. 16–28. Springer (1981)

    1981

  59. [67]

    In: Algebraic Geometry and its Applications: Col- lections of Papers from Shreeram S

    Heintz, J., Roy, M.-F., Solern´ o, P.: Single exponential path finding in semi-algebraic sets, part II: The general case. In: Algebraic Geometry and its Applications: Col- lections of Papers from Shreeram S. Abhyankar’s 60th Birthday Conference, pp. 449–465. Springer (1994)

    1994

  60. [68]

    In: Proceedings of Artificial Intelligence and Symbolic Mathematical Computing, Lec- ture Notes in Computer Science, vol

    Hong, H.: Heuristic search strategies for cylindrical algebraic decomposition. In: Proceedings of Artificial Intelligence and Symbolic Mathematical Computing, Lec- ture Notes in Computer Science, vol. 737, pp. 152–165. Springer (1992)

    1992

  61. [69]

    In: Proceedings of the 53rd IEEE Conference on Decision and Control , pp

    Iraji, R., Chitsaz, H.: Nuroa: A numerical roadmap algorithm. In: Proceedings of the 53rd IEEE Conference on Decision and Control , pp. 5359–5366. IEEE (2014) 58

    2014

  62. [70]

    Springer (2005)

    Jungnickel, D.: Graphs, Networks and Algorithms , Volume 3. Springer (2005)

    2005

  63. [71]

    Kaltofen, E.: Greatest common divisors of polynomials given by straight-line pro- grams. J. ACM 35(1), 231–264 (1988)

    1988

  64. [72]

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

    1989

  65. [73]

    P.: On the geometric properties of Vandermonde’s mapping and on the problem of moments

    Kostov, V. P.: On the geometric properties of Vandermonde’s mapping and on the problem of moments. Proceedings of the Royal Society of Edinburgh Section A: Mathematics, 112(3–4):203–211 (1989)

    1989

  66. [74]

    Notes by R

    Koszul, J.-L.: Lectures on Groups of Transformations . Notes by R. R. Simha and R. Sridharan, Tata Institute of Fundamental Research Lectures on Mathematics, No. 32, Tata Institute of Fundamental Research, Bombay (1965)

    1965

  67. [75]

    Kronecker, L.: Grundz¨ uge einer arithmetischen Theorie der algebraischen Gr¨ ossen. J. Reine Angew. Math. 92, 1–122 (1882)

  68. [76]

    X.: Homotopy techniques for solving sparse column support determinantal polynomial systems

    Labahn, G., Safey El Din, M., Schost, ´E., Vu, T. X.: Homotopy techniques for solving sparse column support determinantal polynomial systems. Journal of Com- plexity, 66, 101557 (2021)

    2021

  69. [77]

    X.: Faster real root decision algorithm for symmetric polynomials

    Labahn, G., Riener, C., Safey El Din, M., Schost, ´E., Vu, T. X.: Faster real root decision algorithm for symmetric polynomials. In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation , pages 452–460 (2023)

    2023

  70. [78]

    B.: Global optimization with polynomials and the problem of moments

    Lasserre, J. B.: Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization , 11(3):796–817 (2001)

    2001

  71. [79]

    Cambridge University Press (1916)

    Macaulay, F.S.: The Algebraic Theory of Modular Systems. Cambridge University Press (1916)

    1916

  72. [80]

    G.: Symmetric Functions and Hall Polynomials, 2nd Edition

    Macdonald, I. G.: Symmetric Functions and Hall Polynomials, 2nd Edition. Oxford University Press (1995)

    1995

  73. [81]

    PhD thesis, University of Wisconsin-Madison (1984)

    McCallum, S.: An improved projection operator for Cylindrical Algebraic Decom- position. PhD thesis, University of Wisconsin-Madison (1984)

    1984

  74. [82]

    In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (ISSAC), pp

    McCallum, S.: On projection in CAD-based quantifier elimination with equational constraint. In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (ISSAC), pp. 145–149. ACM (1999)

    1999

  75. [83]

    Mathematische Zeitschrift , 211:449–460 (1992)

    Meguerditchian, I.: A theorem on the escape from the space of hyperbolic polyno- mials. Mathematische Zeitschrift , 211:449–460 (1992)

    1992

  76. [84]

    Journal of Symbolic Computation , 107:106–121 (2021)

    Moustrou, P., Riener, C., Verdure, H.: Symmetric ideals, Specht polynomials and solutions to symmetric systems of equations. Journal of Symbolic Computation , 107:106–121 (2021)

    2021

  77. [85]

    A.: Structured semidefinite programs and semialgebraic geometry meth- ods in robustness and optimization

    Parrilo, P. A.: Structured semidefinite programs and semialgebraic geometry meth- ods in robustness and optimization. PhD thesis, California Institute of Technology (2000)

    2000

  78. [86]

    Journal of Symbolic Computation , 120:102234 (2024)

    Pr´ ebet, R., Safey El Din, M., Schost, ´E.: Computing roadmaps in unbounded smooth real algebraic sets I: connectivity results. Journal of Symbolic Computation , 120:102234 (2024)

    2024

  79. [87]

    arXiv preprint arXiv:2402.03111 (2024)

    Pr´ ebet, R., Safey El Din, M., Schost, ´E.: Computing roadmaps in un- bounded smooth real algebraic sets II: algorithm and complexity. arXiv preprint arXiv:2402.03111 (2024)

    2024

  80. [88]

    A, Delzell, C

    Prestel. A, Delzell, C. N.: Positive Polynomials: From Hilbert’s 17th Problem to Real Algebra. Springer (2001)

    2001

  81. [89]

    Journal of Symbolic Computation, 13(3), 255–352 (1992)

    Renegar, J.: On the computational complexity and geometry of the first order theory of the reals. Journal of Symbolic Computation, 13(3), 255–352 (1992)

    1992

  82. [90]

    Journal of Pure and Applied Algebra, 216(4), 850-856 (2012) 59

    Riener, C.: On the degree and half-degree principle for symmetric polynomials. Journal of Pure and Applied Algebra, 216(4), 850-856 (2012) 59

    2012

  83. [91]

    J., Lasserre, J

    Riener, C., Theobald, T., Andr´ en, L. J., Lasserre, J. B.: Exploiting symmetries in SDP-relaxations for polynomial optimization. Mathematics of Operations Research, 38(1):122–141 (2013)

    2013

  84. [92]

    Rouillier, F.: Solving zero-dimensional systems through the Rational Univariate Representation. Appl. Algebra Eng. Commun. Comput. 9(5), 433–461 (1999)

    1999

  85. [93]

    Symmetries in semidefinite and polynomial optimization: relaxations, combinatorics, and the degree principle

    Riener, C. Symmetries in semidefinite and polynomial optimization: relaxations, combinatorics, and the degree principle. Dissertation Goethe University Frankfurt (2011)

    2011

  86. [94]

    In: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, pp

    Riener, C., Safey El Din, M.: Real root finding for equivariant semi-algebraic sys- tems. In: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, pp. 335–342 (2018)

    2018

  87. [95]

    X.: Connectivity in symmetric semi-algebraic sets

    Riener, C., Schabert, R., Vu, T. X.: Connectivity in symmetric semi-algebraic sets. In Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, pages 162–169 (2024)

    2024

  88. [96]

    X.: Deciding connectivity in symmetric semi- algebraic sets

    Riener, C., Schabert, R., and Vu, T. X.: Deciding connectivity in symmetric semi- algebraic sets. arXiv preprint arXiv:2503.12275 (2025)

    2025 arXiv

  89. [97]

    Schabert, R.: Linear slices of hyperbolic polynomials and positivity of symmetric polynomial functions, Journal of Pure and Applied Algebra, 228 (5), 107552 (2025)

    Riener, C. Schabert, R.: Linear slices of hyperbolic polynomials and positivity of symmetric polynomial functions, Journal of Pure and Applied Algebra, 228 (5), 107552 (2025)

    2025

  90. [98]

    Applicable Algebra in Engineering, Communication and Computing , 9(5):433–461 (1999)

    Rouillier, F.: Solving zero-dimensional systems through the rational univariate representation. Applicable Algebra in Engineering, Communication and Computing , 9(5):433–461 (1999)

    1999

  91. [99]

    Discrete & Computa- tional Geometry, 45(1):181–220 (2011)

    Safey El Din, M., Schost, ´E.: A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface. Discrete & Computa- tional Geometry, 45(1):181–220 (2011)

    2011

  92. [100]

    and Schost, ´E.: A nearly optimal algorithm for deciding con- nectivity queries in smooth and bounded real algebraic sets

    Safey El Din, M. and Schost, ´E.: A nearly optimal algorithm for deciding con- nectivity queries in smooth and bounded real algebraic sets. Journal of the ACM (JACM), 63(6):1–37 (2017)

    2017

  93. [101]

    Communications in Algebra , 33(9), 3359–3365 (2005)

    Sakkalis, T.: A note on proper polynomial maps. Communications in Algebra , 33(9), 3359–3365 (2005)

    2005

  94. [102]

    Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial iden- tities. J. ACM 27(4), 701–717 (1980)

    1980

  95. [103]

    piano movers

    Schwartz, J.T., Sharir, M.: On the “piano movers” problem. II. General tech- niques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4(3):298–351 (1983)

    1983

  96. [104]

    Mathematische Annalen, 207:87–97 (1974)

    Stengle, G.: A Nullstellensatz and a Positivstellensatz in semialgebraic geometry. Mathematische Annalen, 207:87–97 (1974)

    1974

  97. [105]

    Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 10th International Symposium, AAECC-10 San Juan de Puerto Rico, Puerto Rico, May 10–14, 1993 Proceedings

    Sweedler, M.: Using Gr¨ oebner bases to determine the algebraic and transcenden- tal nature of field extensions: return of the killer tag variables. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: 10th International Symposium, AAECC-10 San Juan de Puerto Rico...

    1993

  98. [106]

    Springer, Berlin, Heidelberg, 66–75 (1993)

    1993

  99. [107]

    The Rand Corporation, Santa Monica, Calif

    Tarski, A.: A Decision Method for Elementary Algebra and Geometry. The Rand Corporation, Santa Monica, Calif. (1948)

    1948

  100. [108]

    Journal of Mathematical Analysis and Applications, 284(1), 174-190 (2003)

    Timofte, V.: On the positivity of symmetric polynomial functions.: Part I: General results. Journal of Mathematical Analysis and Applications, 284(1), 174-190 (2003)

    2003

  101. [109]

    R., Reid, M.: Basic Algebraic Geometry, Volume 2: Schemes and Complex Manifolds

    Shafarevich, I. R., Reid, M.: Basic Algebraic Geometry, Volume 2: Schemes and Complex Manifolds. Springer, Berlin (1994)

    1994

  102. [110]

    Journal of Algebra , 9:220–239 (1968) 60

    Solomon, L.: A decomposition of the group algebra of a finite Coxeter group. Journal of Algebra , 9:220–239 (1968) 60

    1968

  103. [111]

    W.: Cylindrical algebraic decomposition using validated numerics

    Strzebo´ nski, A. W.: Cylindrical algebraic decomposition using validated numerics. Journal of Symbolic Computation, 41(9), 1021–1038 (2006)

    2006

  104. [112]

    W.: Cylindrical algebraic decomposition using local projections

    Strzebo´ nski, A. W.: Cylindrical algebraic decomposition using local projections. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 389–396 (2014)

    2014

  105. [113]

    In: Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974), Vol

    Tits, J.: On buildings and their applications. In: Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974), Vol. 1, pp. 209–220 (1975)

    1975

  106. [114]

    SIAM Review, 38(1):49– 95 (1996)

    Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Review, 38(1):49– 95 (1996)

    1996

  107. [115]

    B.: Discrete linear groups that are generated by reflections

    Vinberg, E. B.: Discrete linear groups that are generated by reflections. Izv. Akad. Nauk SSSR Ser. Mat., 35:1072–1112 (1971)

    1971

  108. [116]

    X.: Computing critical points for algebraic systems defined by hyperocta- hedral invariant polynomials

    Vu, T. X.: Computing critical points for algebraic systems defined by hyperocta- hedral invariant polynomials. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation , pages 167–175 (2022)

    2022

  109. [117]

    X.: Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings

    Vu, T. X.: Computing Polynomial Representation in Subrings of Multivariate Polynomial Rings. arXiv preprint arXiv:2504.21708 (2025)

    2025 arXiv

Pith tools

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