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
Operator noncommutative functions
Abstract We establish a theory of noncommutative (NC) functions on a class of von Neumann algebras with a particular direct sum property, e.g.,$$B({\mathcal H})$$. In contrast to the theory’s origins, we do not rely on appealing to results from the matricial case. We prove that the$$k{\mathrm {th}}$$directional derivative of any NC function at a scalar point is ak-linear homogeneous polynomial in its directions. Consequences include the fact that NC functions defined on domains containing scalar points can be uniformly approximated by free polynomials as well as realization formulas for NC functions bounded on particular sets, e.g., the NC polydisk and NC row ball.
more »
« less
- Award ID(s):
- 2054199
- PAR ID:
- 10499561
- Publisher / Repository:
- Canadian Math Society
- Date Published:
- Journal Name:
- Canadian Mathematical Bulletin
- Volume:
- 66
- Issue:
- 2
- ISSN:
- 0008-4395
- Page Range / eLocation ID:
- 492 to 508
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract LetKbe an imaginary quadratic field and$$p\geq 5$$a rational prime inert inK. For a$$\mathbb {Q}$$-curveEwith complex multiplication by$$\mathcal {O}_K$$and good reduction atp, K. Rubin introduced ap-adicL-function$$\mathscr {L}_{E}$$which interpolates special values ofL-functions ofEtwisted by anticyclotomic characters ofK. In this paper, we prove a formula which links certain values of$$\mathscr {L}_{E}$$outside its defining range of interpolation with rational points onE. Arithmetic consequences includep-converse to the Gross–Zagier and Kolyvagin theorem forE. A key tool of the proof is the recent resolution of Rubin’s conjecture on the structure of local units in the anticyclotomic$${\mathbb {Z}}_p$$-extension$$\Psi _\infty $$of the unramified quadratic extension of$${\mathbb {Q}}_p$$. Along the way, we present a theory of local points over$$\Psi _\infty $$of the Lubin–Tate formal group of height$$2$$for the uniformizing parameter$$-p$$.more » « less
-
Abstract We investigate a novel geometric Iwasawa theory for$${\mathbf Z}_p$$-extensions of function fields over a perfect fieldkof characteristic$$p>0$$by replacing the usual study ofp-torsion in class groups with the study ofp-torsion class groupschemes. That is, if$$\cdots \to X_2 \to X_1 \to X_0$$is the tower of curves overkassociated with a$${\mathbf Z}_p$$-extension of function fields totally ramified over a finite nonempty set of places, we investigate the growth of thep-torsion group scheme in the Jacobian of$$X_n$$as$$n\rightarrow \infty $$. By Dieudonné theory, this amounts to studying the first de Rham cohomology groups of$$X_n$$equipped with natural actions of Frobenius and of the Cartier operatorV. We formulate and test a number of conjectures which predict striking regularity in the$$k[V]$$-module structure of the space$$M_n:=H^0(X_n, \Omega ^1_{X_n/k})$$of global regular differential forms as$$n\rightarrow \infty .$$For example, for each tower in a basic class of$${\mathbf Z}_p$$-towers, we conjecture that the dimension of the kernel of$$V^r$$on$$M_n$$is given by$$a_r p^{2n} + \lambda _r n + c_r(n)$$for allnsufficiently large, where$$a_r, \lambda _r$$are rational constants and$$c_r : {\mathbf Z}/m_r {\mathbf Z} \to {\mathbf Q}$$is a periodic function, depending onrand the tower. To provide evidence for these conjectures, we collect extensive experimental data based on new and more efficient algorithms for working with differentials on$${\mathbf Z}_p$$-towers of curves, and we prove our conjectures in the case$$p=2$$and$$r=1$$.more » « less
-
Abstract We give an explicit raising operator formula for the modified Macdonald polynomials$$\tilde {H}_{\mu }(X;q,t)$$, which follows from our recent formula for$$\nabla $$on an LLT polynomial and the Haglund-Haiman-Loehr formula expressing modified Macdonald polynomials as sums of LLT polynomials. Our method just as easily yields a formula for a family of symmetric functions$$\tilde {H}^{1,n}(X;q,t)$$that we call$$1,n$$-Macdonald polynomials, which reduce to a scalar multiple of$$\tilde {H}_{\mu }(X;q,t)$$when$$n=1$$. We conjecture that the coefficients of$$1,n$$-Macdonald polynomials in terms of Schur functions belong to$${\mathbb N}[q,t]$$, generalizing Macdonald positivity.more » « less
-
Abstract The purpose of this paper is to introduce and study the following graph-theoretic paradigm. Let$$ \begin{align*}T_Kf(x)=\int K(x,y) f(y) d\mu(y),\end{align*} $$where$$f: X \to {\Bbb R}$$,Xa set, finite or infinite, andKand$$\mu $$denote a suitable kernel and a measure, respectively. Given a connected ordered graphGonnvertices, consider the multi-linear form$$ \begin{align*}\Lambda_G(f_1,f_2, \dots, f_n)=\int_{x^1, \dots, x^n \in X} \ \prod_{(i,j) \in {\mathcal E}(G)} K(x^i,x^j) \prod_{l=1}^n f_l(x^l) d\mu(x^l),\end{align*} $$where$${\mathcal E}(G)$$is the edge set ofG. Define$$\Lambda _G(p_1, \ldots , p_n)$$as the smallest constant$$C>0$$such that the inequality(0.1)$$ \begin{align} \Lambda_G(f_1, \dots, f_n) \leq C \prod_{i=1}^n {||f_i||}_{L^{p_i}(X, \mu)} \end{align} $$holds for all nonnegative real-valued functions$$f_i$$,$$1\le i\le n$$, onX. The basic question is, how does the structure ofGand the mapping properties of the operator$$T_K$$influence the sharp exponents in (0.1). In this paper, this question is investigated mainly in the case$$X={\Bbb F}_q^d$$, thed-dimensional vector space over the field withqelements,$$K(x^i,x^j)$$is the indicator function of the sphere evaluated at$$x^i-x^j$$, and connected graphsGwith at most four vertices.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.4153/S0008439522000339
