An official website of the United States government
Abstract Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set$$S \subset \mathbb {R}^k$$by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$, is semialgebraically homeomorphic toS. In this paper, we consider a weaker version of this question. We prove that for any$$\ell \geq 0$$, there exists an algorithm which takes as input a description of a semialgebraic subset$$S \subset \mathbb {R}^k$$given by a quantifier-free first-order formula$$\phi $$in the language of the reals and produces as output a simplicial complex$$\Delta $$, whose geometric realization,$$|\Delta |$$is$$\ell $$-equivalent toS. The complexity of our algorithm is bounded by$$(sd)^{k^{O(\ell )}}$$, wheresis the number of polynomials appearing in the formula$$\phi $$, andda bound on their degrees. For fixed$$\ell $$, this bound issingly exponentialink. In particular, since$$\ell $$-equivalence implies that thehomotopy groupsup to dimension$$\ell $$of$$|\Delta |$$are isomorphic to those ofS, we obtain a reduction (having singly exponential complexity) of the problem of computing the first$$\ell $$homotopy groups ofSto the combinatorial problem of computing the first$$\ell $$homotopy groups of a finite simplicial complex of size bounded by$$(sd)^{k^{O(\ell )}}$$.
more »
« less
This content will become publicly available on February 7, 2026
Hyperbolic Metric Spaces and Stochastic Embeddings
Abstract Stochastic embeddings of finite metric spaces into graph-theoretic trees have proven to be a vital tool for constructing approximation algorithms in theoretical computer science. In the present work, we build out some of the basic theory of stochastic embeddings in the infinite setting with an aim toward applications to Lipschitz free space theory. We prove that proper metric spaces stochastically embedding into$$\mathbb {R}$$-trees have Lipschitz free spaces isomorphic to$$L^1$$-spaces. We then undergo a systematic study of stochastic embeddability of Gromov hyperbolic metric spaces into$$\mathbb {R}$$-trees by way of stochastic embeddability of their boundaries into ultrametric spaces. The following are obtained as our main results: (1) every snowflake of a compact, finite Nagata-dimensional metric space stochastically embeds into an ultrametric space and has Lipschitz free space isomorphic to$$\ell ^1$$, (2) the Lipschitz free space over hyperbolicn-space is isomorphic to the Lipschitz free space over Euclideann-space and (3) every infinite, finitely generated hyperbolic group stochastically embeds into an$$\mathbb {R}$$-tree, has Lipschitz free space isomorphic to$$\ell ^1$$, and admits a proper, uniformly Lipschitz affine action on$$\ell ^1$$.
more »
« less
- Award ID(s):
- 2342644
- PAR ID:
- 10611150
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Forum of Mathematics, Sigma
- Volume:
- 13
- ISSN:
- 2050-5094
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let$$G$$be a split semisimple group over a global function field$$K$$. Given a cuspidal automorphic representation$$\Pi$$of$$G$$satisfying a technical hypothesis, we prove that for almost all primes$$\ell$$, there is a cyclic base change lifting of$$\Pi$$along any$$\mathbb {Z}/\ell \mathbb {Z}$$-extension of$$K$$. Our proof does not rely on any trace formulas; instead it is based on using modularity lifting theorems, together with a Smith theory argument, to obtain base change for residual representations. As an application, we also prove that for any split semisimple group$$G$$over a local function field$$F$$, and almost all primes$$\ell$$, any irreducible admissible representation of$$G(F)$$admits a base change along any$$\mathbb {Z}/\ell \mathbb {Z}$$-extension of$$F$$. Finally, we characterize local base change more explicitly for a class of toral representations considered in work of Chan and Oi.more » « less
-
Abstract Letfbe an$$L^2$$-normalized holomorphic newform of weightkon$$\Gamma _0(N) \backslash \mathbb {H}$$withNsquarefree or, more generally, on any hyperbolic surface$$\Gamma \backslash \mathbb {H}$$attached to an Eichler order of squarefree level in an indefinite quaternion algebra over$$\mathbb {Q}$$. Denote byVthe hyperbolic volume of said surface. We prove the sup-norm estimate$$\begin{align*}\| \Im(\cdot)^{\frac{k}{2}} f \|_{\infty} \ll_{\varepsilon} (k V)^{\frac{1}{4}+\varepsilon} \end{align*}$$ with absolute implied constant. For a cuspidal Maaß newform$$\varphi $$of eigenvalue$$\lambda $$on such a surface, we prove that$$\begin{align*}\|\varphi \|_{\infty} \ll_{\lambda,\varepsilon} V^{\frac{1}{4}+\varepsilon}. \end{align*}$$ We establish analogous estimates in the setting of definite quaternion algebras.more » « less
-
Abstract We study the degree of an L-Lipschitz map between Riemannian manifolds, proving new upper bounds and constructing new examples. For instance, if $$X_k$$ is the connected sum of k copies of $$\mathbb CP^2$$for$$k \ge 4$$, then we prove that the maximum degree of an L-Lipschitz self-map of $$X_k$$ is between $$C_1 L^4 (\log L)^{-4}$$ and $$C_2 L^4 (\log L)^{-1/2}$$. More generally, we divide simply connected manifolds into three topological types with three different behaviors. Each type is defined by purely topological criteria. For scalable simply connected n-manifolds, the maximal degree is $$\sim L^n$$. For formal but nonscalable simply connectedn-manifolds, the maximal degree grows roughly like $$L^n (\log L)^{-\theta (1)}$$. And for nonformal simply connected n-manifolds, the maximal degree is bounded by $$L^\alpha $$ for some $$\alpha < n$$.more » « less
-
Abstract For$$E \subset \mathbb {N}$$, a subset$$R \subset \mathbb {N}$$isE-intersectiveif for every$$A \subset E$$having positive relative density,$$R \cap (A - A) \neq \varnothing $$. We say thatRischromatically E-intersectiveif for every finite partition$$E=\bigcup _{i=1}^k E_i$$, there existsisuch that$$R\cap (E_i-E_i)\neq \varnothing $$. When$$E=\mathbb {N}$$, we recover the usual notions of intersectivity and chromatic intersectivity. We investigate to what extent the known intersectivity results hold in the relative setting when$$E = \mathbb {P}$$, the set of primes, or other sparse subsets of$$\mathbb {N}$$. Among other things, we prove the following: (1) the set of shifted Chen primes$$\mathbb {P}_{\mathrm {Chen}} + 1$$is both intersective and$$\mathbb {P}$$-intersective; (2) there exists an intersective set that is not$$\mathbb {P}$$-intersective; (3) every$$\mathbb {P}$$-intersective set is intersective; (4) there exists a chromatically$$\mathbb {P}$$-intersective set which is not intersective (and therefore not$$\mathbb {P}$$-intersective).more » « less
