{"id":"de99a432-dece-4287-9701-3bce21608bac","arxiv_id":"2507.23728","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":0.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A survey of algorithms that exploit permutation symmetry to speed up computations in real algebraic geometry.","lead":"This paper surveys how permutation symmetry in polynomials can accelerate symbolic computation in real algebraic geometry. It organizes known algorithms for emptiness testing, topological invariants, and connectivity that run in polynomial time in the number of variables when the degree is fixed.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's 'false' return is not equivalent to absence of real points in E^{-1}(Wλ), so Algorithm 3 can report nonemptiness for empty sets; Theorem 14 also drops the rank assumption.","rationale":"The reader's verdict is CONDITIONAL, and the main stated reason is the inconsistency between Algorithm 2 and Theorem 4 and the resulting unsound use in Algorithm 3. I agree that this is the most load-bearing defect: it directly undermines the survey's headline emptiness algorithm in Section 1.5.3, not merely a missing proof or an overly strong complexity bound. The reader's formal 'weakest_assumption' field points instead to the Jacobian rank hypothesis, which is real but secondary: even if the rank assumption is granted, the Decide/Real Emptiness interface is still logically unsound, as the two explicit parametrizations in the attack show. Theorem 14 also states the emptiness result without the rank assumption that Algorithm 3 requires, so the theorem overclaims relative to the presented procedure. Since the underlying results are published (the chapter cites [77] and related work), the chapter can be repaired by replacing Decide with a procedure that tests existence of at least one real root of q for which every block's Vieta polynomial has ℓ_i real roots, or by citing the correct decision routine and stating the rank hypothesis in Theorem 14. This is a major revision but not a rejection of the survey's broader organizational value, so CONDITIONAL remains the right verdict. Hence I recommend UNCHANGED relative to the reader's verdict, with agreement partial because the reader's headline weakest assumption differs from the more decisive algorithmic defect.","tokens_in":44147,"tokens_out":7356,"duration_ms":80555,"concrete_test":"Run Algorithm 2 exactly as specified on the zero-dimensional parametrization Rλ with q(T)=T(T-1), v1(T)=0, v2(T)=-1 and a single block of size ℓ=2. The algorithm returns false because the root T=0 yields the univariate polynomial -u^2-1 with no real roots. Yet E^{-1}(Wλ) contains the real point (1,-1) (and (-1,1)) coming from the root T=1, whose polynomial is u^2-1. This directly refutes Theorem 4's claimed 'yes iff E^{-1}(Wλ) has a real point'. As a second check, run Algorithm 3 on the symmetric empty variety f=x1^2+...+xn^2+1 with this Decide; the false branch of Decide causes a false 'nonempty' answer.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central emptiness algorithm beyond the fixed-degree regime is Algorithm 3, which repeatedly calls Decide(Rλ) and returns false (nonempty) whenever Decide returns false. But Algorithm 2's stated semantics are 'true if all fibers of Wλ by Eλ contain real points, false otherwise', while Theorem 4 claims the output is 'yes if and only if E^{-1}(Wλ) has a real point'. These are not equivalent: 'false' is triggered as soon as one real root of q gives a Vieta polynomial with fewer than ℓ_i real roots, regardless of whether another root's fiber has real points. A concrete demonstration: take ℓ=2, q(T)=T(T-1), v1(T)=0, v2(T)=-1. For T=1, the fiber is (e1,e2)=(0,-1), which has real preimages (1,-1) and (-1,1); for T=0, the fiber is (0,1), whose preimage satisfies u^2+1=0 and has no real points. Algorithm 2 first accepts T=1, then returns false at T=0. Thus it returns false although E^{-1}(Wλ) contains a real point. Conversely, q(T)=T, v1=0, v2=1 returns false while E^{-1}(Wλ) is empty. So false is not a reliable signal of nonemptiness. Algorithm 3's use of Decide therefore can produce false-positive nonemptiness answers. See Section 1.5.3 and Theorem 14. A secondary but related issue: Algorithm 3 is explicitly stated only under the assumption that Jac(f) has rank s on V(f), while Theorem 14 drops this hypothesis. The rank condition is load-bearing for Proposition 2 and Lemmas 4–5, and singular symmetric systems are not covered as presented.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":44488,"tokens_out":11985,"duration_ms":112070,"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":[{"comment":"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.","section":"1.3.4, Algorithm 2 and Theorem 4"},{"comment":"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.","section":"1.5.3, Theorem 14"}],"minor_comments":[{"comment":"The word 'zero-dimensitional' should be 'zero-dimensional'.","section":"1.3.4, Theorem 4"},{"comment":"The theorem statement says 'decides whether u and u are orbit-connected'; this should presumably be 'u and v'.","section":"1.6.2, Theorem 17"},{"comment":"There are several typographical errors in this paragraph, including 'Computationaly', 'have have provided', 'approachess', and 'taken symmetry into account'.","section":"1.6.5, Final Discussions"},{"comment":"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.","section":"1.3.3, Example 16"}],"recommendation":"major_revision","confidential_remarks":"The chapter is heavily based on the authors' own prior work, which is appropriate for a survey of their research line. The main concern is the correctness of the Decide procedure as presented; if this is meant to be a survey of an existing published algorithm, the authors should align the pseudocode with the published version and with the theorem statement. The editor may also wish to check that the statement of Theorem 14 matches the hypotheses in the underlying paper [77]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick read: this is a survey chapter, not a research paper. It gives a well-organized tour of how permutation symmetry reduces complexity in real algebraic geometry: the half-degree principle, symmetric SOS, orbit-space methods, critical point algorithms, mirror spaces, and connectivity. For someone entering the area it is a genuinely useful map, and the complexity tables are handy. The self-citations are heavy but expected in a survey of the authors' own line, and the cited results are generally reproduced faithfully.\n\nThe soft spot is real and load-bearing. The Decide algorithm (Algorithm 2, Section 1.3.4) is stated to return 'true if all fibers of Wλ by Eλ contain real points, false otherwise.' Theorem 4 then claims the output is 'yes if and only if E^{-1}(Wλ) has a real point.' Those are not equivalent. The algorithm returns false as soon as one real root of q gives a Vieta polynomial with fewer than ℓ_i real roots, even when another root's fiber has real points. Concretely, with ℓ=2, q(T)=T(T-1), v1=0, v2=-1, the fiber over T=1 is (e1,e2)=(0,-1), which has real preimages, while T=0 gives a fiber with no real preimages; the algorithm returns false anyway. Since Algorithm 3 in Section 1.5.3 uses false as a signal of nonemptiness, the emptiness test as written can report 'nonempty' for an empty set. Also, Theorem 14 states Real Emptiness without the rank assumption that Algorithm 3 explicitly imposes (Jac(f) full rank on V(f)); the proof of Theorem 4 gives complexity but skips correctness entirely.\n\nThese are fixable — the underlying published algorithms are probably correct with the right semantics — but a survey that mis-states a central algorithm is not ready as is. Minor typos (e.g., 'u and u' in Theorem 17) are worth catching too.\n\nWho this is for: graduate students and practitioners who want the landscape of symmetric real algebraic geometry and pointers to the original papers. It deserves a serious referee, but the referee should insist on correcting the Decide/Theorem 4 mismatch and the rank-assumption gap before publication.","headline":"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.","tokens_in":44962,"tokens_out":5066,"would_cite":true,"duration_ms":47696,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["14P10","14P25","68W30","13A50"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["symmetric polynomials","real algebraic geometry","half-degree principle","critical point method","orbit space","mirror spaces","Betti numbers","connectivity queries"],"falsifier":"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.","tokens_in":43915,"feed_emoji":"🔁","tokens_out":9823,"duration_ms":101502,"temperature":0.7,"pith_summary":"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.","feed_headline":"Permutation symmetry tames hard real polynomial problems","feed_subtitle":"Fixed-degree emptiness, connectivity, and topological problems become polynomial in dimension","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"States the half-degree principle: nonnegativity of degree-$2d$ symmetric polynomials reduces to points with at most $d$ distinct coordinates.","marker":"[107]"},{"why":"Extends the degree principle to equivariant systems, supplying the dimension reduction behind the emptiness and quantifier-elimination results.","marker":"[94]"},{"why":"Is the source of the randomized Real Emptiness algorithm and its complexity bound for symmetric polynomials.","marker":"[77]"},{"why":"Proves that symmetric SOS Gram matrices have size independent of $n$ for $n \\ge 2d$.","marker":"[91, 93]"},{"why":"Bounds equivariant Betti numbers of symmetric semi-algebraic sets and yields the fixed-degree topological algorithms.","marker":"[13]"},{"why":"Gives the orbit-connectivity algorithm inside the Weyl chamber.","marker":"[95]"},{"why":"Gives the full connectivity algorithm using mirror spaces and adjacent-transposition wall tests.","marker":"[96]"},{"why":"Supplies the mirror-space basic construction used to lift homology from the chamber to the whole symmetric set.","marker":"[35]"},{"why":"Establish the Vandermonde-map homeomorphisms and contractible fibers that coordinate the orbit space by $d$ parameters.","marker":"[4, 55, 73]"}],"fun_headline_variants":["Symmetry shrinks real polynomial complexity","Degree, not dimension, rules symmetric real systems","Permutation symmetry unlocks real algebraic shortcuts","Fixed-degree symmetric problems solved in polynomial time","Half-degree principle cuts real-solving to few points"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Symmetry shrinks real polynomial complexity","Degree, not dimension, rules symmetric real systems","Permutation symmetry unlocks real algebraic shortcuts","Fixed-degree symmetric problems solved in polynomial time","Half-degree principle cuts real-solving to few points"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000449,"raw_usage":{"total_tokens":2164,"prompt_tokens":748,"completion_tokens":1416,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":364,"completion_tokens_details":{"reasoning_tokens":1350}},"tokens_in":364,"tokens_out":1416,"duration_ms":11192,"temperature":1.0,"reasoning_tokens":1350,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T10:26:34.742538+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"The Rand Corporation, Santa Monica, Calif","cited_arxiv_id":null,"evidence_quote":"States the half-degree principle: nonnegativity of degree-$2d$ symmetric polynomials reduces to points with at most $d$ distinct coordinates."},{"cited_title":"In: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, pp","cited_arxiv_id":null,"evidence_quote":"Extends the degree principle to equivariant systems, supplying the dimension reduction behind the emptiness and quantifier-elimination results."},{"cited_title":"X.: Faster real root decision algorithm for symmetric polynomials","cited_arxiv_id":null,"evidence_quote":"Is the source of the randomized Real Emptiness algorithm and its complexity bound for symmetric polynomials."},{"cited_title":"X.: Connectivity in symmetric semi-algebraic sets","cited_arxiv_id":null,"evidence_quote":"Gives the orbit-connectivity algorithm inside the Weyl chamber."}],"review_version":1}