Skip to main content
Top
Published in: Foundations of Computational Mathematics 5/2022

02-08-2021

Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-algebraic Sets

Authors: Saugata Basu, Cordian Riener

Published in: Foundations of Computational Mathematics | Issue 5/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Let \(\mathrm {R}\) be a real closed field. We prove that for each fixed \(\ell , d \ge 0\), there exists an algorithm that takes as input a quantifier-free first-order formula \(\Phi \) with atoms \(P=0, P > 0, P < 0 \text { with } P \in \mathcal {P} \subset \mathrm{D}[X_1,\ldots ,X_k]^{\mathfrak {S}_k}_{\le d}\), where \(\mathrm{D}\) is an ordered domain contained in \(\mathrm {R}\), and computes the ranks of the first \(\ell +1\) cohomology groups, of the symmetric semi-algebraic set defined by \(\Phi \). The complexity of this algorithm (measured by the number of arithmetic operations in \(\mathrm{D}\)) is bounded by a polynomial in k and \(\mathrm {card}(\mathcal {P})\) (for fixed d and \(\ell \)). This result contrasts with the \(\mathbf {PSPACE}\)-hardness of the problem of computing just the zeroth Betti number (i.e., the number of semi-algebraically connected components) in the general case for \(d \ge 2\) (taking the ordered domain \(\mathrm{D}\) to be equal to \(\mathbb {Z}\)). The above algorithmic result is built on new representation theoretic results on the cohomology of symmetric semi-algebraic sets. We prove that the Specht modules corresponding to partitions having long lengths cannot occur in the isotypic decompositions of low-dimensional cohomology modules of closed semi-algebraic sets defined by symmetric polynomials having small degrees. This result generalizes prior results obtained by the authors giving restrictions on such partitions in terms of their ranks and is the key technical tool in the design of the algorithm mentioned in the previous paragraph.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Appendix
Available only for authorised users
Footnotes
1
The theorem in [29] is not stated using the language of non-Archimedean extensions and Puiseux series but it is easy to translate it into the form stated here.
 
Literature
1.
go back to reference V. I. Arnold, Hyperbolic polynomials and Vandermonde mappings, Funktsional. Anal. i Prilozhen. 20 (1986), no. 2, 52–53.MathSciNet V. I. Arnold, Hyperbolic polynomials and Vandermonde mappings, Funktsional. Anal. i Prilozhen. 20 (1986), no. 2, 52–53.MathSciNet
2.
go back to reference S. Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, Discret. Comput. Geom. 22 (1999), no. 1, 1–18.MathSciNetCrossRef S. Basu, On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets, Discret. Comput. Geom. 22 (1999), no. 1, 1–18.MathSciNetCrossRef
3.
go back to reference S. Basu, Computing the first few Betti numbers of semi-algebraic sets in single exponential time, J. Symb. Comput. 41 (2006), no. 10, 1125–1154.MathSciNetCrossRef S. Basu, Computing the first few Betti numbers of semi-algebraic sets in single exponential time, J. Symb. Comput. 41 (2006), no. 10, 1125–1154.MathSciNetCrossRef
4.
go back to reference S. Basu, Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time, Found. Comput. Math. 8 (2008), no. 1, 45–80.MathSciNetCrossRef S. Basu, Computing the top Betti numbers of semialgebraic sets defined by quadratic inequalities in polynomial time, Found. Comput. Math. 8 (2008), no. 1, 45–80.MathSciNetCrossRef
5.
go back to reference S. Basu, Algorithms in real algebraic geometry: a survey, Real algebraic geometry, Panor. Synthèses, vol. 51, Soc. Math. France, Paris, 2017, pp. 107–153. S. Basu, Algorithms in real algebraic geometry: a survey, Real algebraic geometry, Panor. Synthèses, vol. 51, Soc. Math. France, Paris, 2017, pp. 107–153.
6.
go back to reference S. Basu, A. Gabrielov, and N. Vorobjov, Monotone functions and maps, Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM 107 (2013), no. 1, 5–33.MathSciNetCrossRef S. Basu, A. Gabrielov, and N. Vorobjov, Monotone functions and maps, Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM 107 (2013), no. 1, 5–33.MathSciNetCrossRef
7.
go back to reference S. Basu, R. Pollack, and M.-F. Roy, Computing roadmaps of semi-algebraic sets on a variety, J. Am. Math. Soc. 13 (2000), no. 1, 55–82.MathSciNetCrossRef S. Basu, R. Pollack, and M.-F. Roy, Computing roadmaps of semi-algebraic sets on a variety, J. Am. Math. Soc. 13 (2000), no. 1, 55–82.MathSciNetCrossRef
8.
go back to reference S. Basu, R. Pollack, and M.-F. Roy, Computing the Euler–Poincaré characteristics of sign conditions, Comput. Complex. 14 (2005), no. 1, 53–71.CrossRef S. Basu, R. Pollack, and M.-F. Roy, Computing the Euler–Poincaré characteristics of sign conditions, Comput. Complex. 14 (2005), no. 1, 53–71.CrossRef
9.
go back to reference S. Basu, R. Pollack, and M.-F. Roy, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006 (second edition). S. Basu, R. Pollack, and M.-F. Roy, Algorithms in real algebraic geometry, Algorithms and Computation in Mathematics, vol. 10, Springer-Verlag, Berlin, 2006 (second edition).
10.
go back to reference S. Basu, R. Pollack, and M.-F. Roy, Computing the first Betti number of a semi-algebraic set, Found. Comput. Math. 8 (2008), no. 1, 97–136.MathSciNetCrossRef S. Basu, R. Pollack, and M.-F. Roy, Computing the first Betti number of a semi-algebraic set, Found. Comput. Math. 8 (2008), no. 1, 97–136.MathSciNetCrossRef
11.
go back to reference S. Basu and C. Riener, Efficient algorithms for computing the Euler–Poincaré characteristic of symmetric semi-algebraic sets, Ordered algebraic structures and related topics, Contemp. Math., vol. 697, Am. Math. Soc., Providence, RI, 2017, pp. 51–79. S. Basu and C. Riener, Efficient algorithms for computing the Euler–Poincaré characteristic of symmetric semi-algebraic sets, Ordered algebraic structures and related topics, Contemp. Math., vol. 697, Am. Math. Soc., Providence, RI, 2017, pp. 51–79.
12.
go back to reference S. Basu and C. Riener, On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms, Selecta Math. (N.S.) 24 (2018), no. 4, 3241–3281.MathSciNetCrossRef S. Basu and C. Riener, On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms, Selecta Math. (N.S.) 24 (2018), no. 4, 3241–3281.MathSciNetCrossRef
13.
go back to reference S. Basu and C. Riener, On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities, International Mathematics Research Notices (2018), rny062. S. Basu and C. Riener, On the isotypic decomposition of cohomology modules of symmetric semi-algebraic sets: polynomial bounds on multiplicities, International Mathematics Research Notices (2018), rny062.
14.
go back to reference S. Basu and M.-F. Roy, Divide and conquer roadmap for algebraic sets, Discret. Comput. Geom. 52 (2014), no. 2, 278–343.MathSciNetCrossRef S. Basu and M.-F. Roy, Divide and conquer roadmap for algebraic sets, Discret. Comput. Geom. 52 (2014), no. 2, 278–343.MathSciNetCrossRef
15.
go back to reference S. Basu and T. Zell, Polynomial hierarchy, Betti numbers, and a real analogue of Toda’s theorem, Found. Comput. Math. 10 (2010), no. 4, 429–454.MathSciNetCrossRef S. Basu and T. Zell, Polynomial hierarchy, Betti numbers, and a real analogue of Toda’s theorem, Found. Comput. Math. 10 (2010), no. 4, 429–454.MathSciNetCrossRef
16.
go back to reference L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer-Verlag, New York, 1998, With a foreword by Richard M. Karp. L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity and real computation, Springer-Verlag, New York, 1998, With a foreword by Richard M. Karp.
17.
go back to reference J. Bochnak, M. Coste, and M.-F. Roy, Géométrie algébrique réelle (second edition in english: Real algebraic geometry), Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas ], vol. 12 (36), Springer-Verlag, Berlin, 1987 (1998). J. Bochnak, M. Coste, and M.-F. Roy, Géométrie algébrique réelle (second edition in english: Real algebraic geometry), Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas ], vol. 12 (36), Springer-Verlag, Berlin, 1987 (1998).
18.
go back to reference L. Bröcker, On symmetric semialgebraic sets and orbit spaces, Banach Center Publ. 44 (1998), no. 1, 37–50.MathSciNetCrossRef L. Bröcker, On symmetric semialgebraic sets and orbit spaces, Banach Center Publ. 44 (1998), no. 1, 37–50.MathSciNetCrossRef
19.
go back to reference P. Bürgisser and F. Cucker, Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré, Complexity of computations and proofs, Quad. Mat., vol. 13, Dept. Math., Seconda Univ. Napoli, Caserta, 2004, pp. 73–151. P. Bürgisser and F. Cucker, Variations by complexity theorists on three themes of Euler, Bézout, Betti, and Poincaré, Complexity of computations and proofs, Quad. Mat., vol. 13, Dept. Math., Seconda Univ. Napoli, Caserta, 2004, pp. 73–151.
20.
go back to reference P. Bürgisser, F. Cucker, and P. Lairez, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM 66 (2018), no. 1, 5:1–5:30. P. Bürgisser, F. Cucker, and P. Lairez, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM 66 (2018), no. 1, 5:1–5:30.
21.
go back to reference P. Bürgisser, F. Cucker, and P. Lairez, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM 66 (2019), no. 1, Art. 5, 30, [Publication date initially given as 2018]. P. Bürgisser, F. Cucker, and P. Lairez, Computing the homology of basic semialgebraic sets in weak exponential time, J. ACM 66 (2019), no. 1, Art. 5, 30, [Publication date initially given as 2018].
22.
go back to reference P. Bürgisser, F. Cucker, and J. Tonelli-Cueto, Computing the Homology of Semialgebraic Sets. II: General formulas, arXiv e-prints (2019), arXiv:1903.10710. P. Bürgisser, F. Cucker, and J. Tonelli-Cueto, Computing the Homology of Semialgebraic Sets. II: General formulas, arXiv e-prints (2019), arXiv:​1903.​10710.
23.
go back to reference P. Bürgisser, F. Cucker, and J. Tonelli-Cueto, Computing the homology of semialgebraic sets. I: Lax formulas, Found. Comput. Math. 20 (2020), no. 1, 71–118.MathSciNetCrossRef P. Bürgisser, F. Cucker, and J. Tonelli-Cueto, Computing the homology of semialgebraic sets. I: Lax formulas, Found. Comput. Math. 20 (2020), no. 1, 71–118.MathSciNetCrossRef
24.
go back to reference J. Canny, The complexity of robot motion planning, MIT Press, Cambridge, 1987. J. Canny, The complexity of robot motion planning, MIT Press, Cambridge, 1987.
25.
go back to reference T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Representation theory of the symmetric groups, Cambridge Studies in Advanced Mathematics, vol. 121, Cambridge University Press, Cambridge, 2010, The Okounkov–Vershik approach, character formulas, and partition algebras. T. Ceccherini-Silberstein, F. Scarabotti, and F. Tolli, Representation theory of the symmetric groups, Cambridge Studies in Advanced Mathematics, vol. 121, Cambridge University Press, Cambridge, 2010, The Okounkov–Vershik approach, character formulas, and partition algebras.
26.
go back to reference M. W. Davis, Groups generated by reflections and aspherical manifolds not covered by Euclidean space, Ann. Math. 117 (1983), no. 2, 293–324.MathSciNetCrossRef M. W. Davis, Groups generated by reflections and aspherical manifolds not covered by Euclidean space, Ann. Math. 117 (1983), no. 2, 293–324.MathSciNetCrossRef
27.
go back to reference M. W. Davis, The geometry and topology of Coxeter groups, London Mathematical Society Monographs Series, vol. 32, Princeton University Press, Princeton, 2008. M. W. Davis, The geometry and topology of Coxeter groups, London Mathematical Society Monographs Series, vol. 32, Princeton University Press, Princeton, 2008.
28.
go back to reference P. Erdős and J. Lehner, The distribution of the number of summands in the partitions of a positive integer, Duke Math. J. 8 (1941), 335–345.MathSciNetCrossRef P. Erdős and J. Lehner, The distribution of the number of summands in the partitions of a positive integer, Duke Math. J. 8 (1941), 335–345.MathSciNetCrossRef
29.
go back to reference A. Gabrielov and N. Vorobjov, Approximation of definable sets by compact families, and upper bounds on homotopy and homology, J. Lond. Math. Soc. 80 (2009), no. 1, 35–54.MathSciNetCrossRef A. Gabrielov and N. Vorobjov, Approximation of definable sets by compact families, and upper bounds on homotopy and homology, J. Lond. Math. Soc. 80 (2009), no. 1, 35–54.MathSciNetCrossRef
30.
go back to reference A. Givental, Moments of random variables and the equivariant Morse lemma, Rus. Math. Surv. 42 (1987), no. 2, 275–276.MathSciNetCrossRef A. Givental, Moments of random variables and the equivariant Morse lemma, Rus. Math. Surv. 42 (1987), no. 2, 275–276.MathSciNetCrossRef
31.
go back to reference B. Iversen, Cohomology of sheaves, Universitext, Springer-Verlag, Berlin, 1986.CrossRef B. Iversen, Cohomology of sheaves, Universitext, Springer-Verlag, Berlin, 1986.CrossRef
32.
go back to reference V.P. Kostov, On the geometric properties of Vandermonde’s mapping and on the problem of moments, Proc. Royal Soc. Edinb.: Sect. A Math. 112 (1989), no. 3-4, 203–211.MathSciNetCrossRef V.P. Kostov, On the geometric properties of Vandermonde’s mapping and on the problem of moments, Proc. Royal Soc. Edinb.: Sect. A Math. 112 (1989), no. 3-4, 203–211.MathSciNetCrossRef
33.
go back to reference J.-L. Koszul, 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. J.-L. Koszul, 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.
34.
go back to reference P. A. MacMahon, Combinatory analysis, two volumes (bound as one), Chelsea Publishing Co., New York, 1960. P. A. MacMahon, Combinatory analysis, two volumes (bound as one), Chelsea Publishing Co., New York, 1960.
35.
go back to reference L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS Texts and Monographs, vol. 6, American Mathematical Society, Providence, RI; Société Mathématique de France, Paris, 2001, Translated from the 1998 French original by John R. Swallow, Cours Spécialisés [Specialized Courses], 3. L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS Texts and Monographs, vol. 6, American Mathematical Society, Providence, RI; Société Mathématique de France, Paris, 2001, Translated from the 1998 French original by John R. Swallow, Cours Spécialisés [Specialized Courses], 3.
36.
go back to reference I. Meguerditchian, A theorem on the escape from the space of hyperbolic polynomials, Math. Z. 211 (1992), no. 3, 449–460.MathSciNetCrossRef I. Meguerditchian, A theorem on the escape from the space of hyperbolic polynomials, Math. Z. 211 (1992), no. 3, 449–460.MathSciNetCrossRef
37.
go back to reference C. Procesi, Lie groups, Universitext, Springer, New York, 2007, An approach through invariants and representations. C. Procesi, Lie groups, Universitext, Springer, New York, 2007, An approach through invariants and representations.
38.
39.
go back to reference J. H. Reif, Complexity of the mover’s problem and generalizations, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (Washington, DC, USA), SFCS ’79, IEEE Computer Society, 1979, pp. 421–427. J. H. Reif, Complexity of the mover’s problem and generalizations, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (Washington, DC, USA), SFCS ’79, IEEE Computer Society, 1979, pp. 421–427.
40.
go back to reference C. Riener, On the degree and half-degree principle for symmetric polynomials, J. Pure Appl. Algebra 216 (2012), no. 4, 850–856.MathSciNetCrossRef C. Riener, On the degree and half-degree principle for symmetric polynomials, J. Pure Appl. Algebra 216 (2012), no. 4, 850–856.MathSciNetCrossRef
41.
go back to reference J. Schwartz and M. Sharir, On the piano movers’ problem ii. General techniques for computing topological properties of real algebraic manifolds, Adv. Appl. Math. 4 (1983), 298–351.MathSciNetCrossRef J. Schwartz and M. Sharir, On the piano movers’ problem ii. General techniques for computing topological properties of real algebraic manifolds, Adv. Appl. Math. 4 (1983), 298–351.MathSciNetCrossRef
42.
go back to reference J.-P. Serre, Linear representations of finite groups, Springer-Verlag, New York-Heidelberg, 1977, Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42. J.-P. Serre, Linear representations of finite groups, Springer-Verlag, New York-Heidelberg, 1977, Translated from the second French edition by Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42.
43.
44.
go back to reference E. H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York, 1966.MATH E. H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York, 1966.MATH
45.
go back to reference V. Timofte, On the positivity of symmetric polynomial functions. I. General results, J. Math. Anal. Appl. 284 (2003), no. 1, 174–190.MathSciNetCrossRef V. Timofte, On the positivity of symmetric polynomial functions. I. General results, J. Math. Anal. Appl. 284 (2003), no. 1, 174–190.MathSciNetCrossRef
46.
go back to reference J. Tits, On buildings and their applications, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 1 (1975), 209–220. J. Tits, On buildings and their applications, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974), Vol. 1 (1975), 209–220.
47.
go back to reference L. van den Dries, Tame topology and o-minimal structures, London Mathematical Society Lecture Note Series, vol. 248, Cambridge University Press, Cambridge, 1998.CrossRef L. van den Dries, Tame topology and o-minimal structures, London Mathematical Society Lecture Note Series, vol. 248, Cambridge University Press, Cambridge, 1998.CrossRef
48.
go back to reference È. B. Vinberg, Discrete linear groups that are generated by reflections, Izv. Akad. Nauk SSSR Ser. Mat. 35 (1971), 1072–1112.MathSciNet È. B. Vinberg, Discrete linear groups that are generated by reflections, Izv. Akad. Nauk SSSR Ser. Mat. 35 (1971), 1072–1112.MathSciNet
Metadata
Title
Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-algebraic Sets
Authors
Saugata Basu
Cordian Riener
Publication date
02-08-2021
Publisher
Springer US
Published in
Foundations of Computational Mathematics / Issue 5/2022
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-021-09519-7

Other articles of this Issue 5/2022

Foundations of Computational Mathematics 5/2022 Go to the issue

Premium Partner