More Like this

1. Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set

   https://doi.org/10.1007/s00454-024-00626-0  

   Basu, Saugata; Percival, Sarah (September 2024, Discrete & Computational Geometry)

   Let $$\R$$ be a real closed field and $$\C$$ the algebraic closure of $$\R$$. We give an algorithm for computing a semi-algebraic basis for the first homology group, $$\HH_1(S,\mathbb{F})$$, with coefficients in a field $$\FF$$, of any given semi-algebraic set $$S \subset \R^k$$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves $$s$$ polynomials whose degrees are bounded by $$d$$, the complexity of the algorithm is bounded by $$(s d)^{k^{O(1)}}$$. This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset $$\Gamma$$ of the given semi-algebraic set $$S$$, such that $$\HH_q(S,\Gamma) = 0$$ for $q=0,1$. We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety $$X$$ of dimension $$n$$, there exists Zariski closed subsets \[ Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)} \] with $$\dim_\C Z^{(i)} \leq i$, and $$\HH_q(X,Z^{(i)}) = 0$$ for $$0 \leq q \leq i$$. We conjecture a quantitative version of this result in the semi-algebraic category, with $$X$$ and $$Z^{(i)}$$ replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of $$Z^{(0)}$$ and $$Z^{(1)}$$ with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing $$Z^{(0)}$$). 

   more » « less
2. ROUGH INTEGERS WITH A DIVISOR IN A GIVEN INTERVAL

   https://doi.org/10.1017/S1446788719000442  

   FORD, KEVIN (August 2021, Journal of the Australian Mathematical Society)

   Abstract We determine, up to multiplicative constants, the number of integers $$n\leq x$$ that have a divisor in $(y,2y]$ and no prime factor $$\leq w$$ . Our estimate is uniform in $x,y,w$ . We apply this to determine the order of the number of distinct integers in the $$N\times N$$ multiplication table, which are free of prime factors $$\leq w$$ , and the number of distinct fractions of the form $$(a_{1}a_{2})/(b_{1}b_{2})$$ with $$1\leq a_{1}\leq b_{1}\leq N$$ and $$1\leq a_{2}\leq b_{2}\leq N$$ . 

   more » « less
3. Edge Expansion and Spectral Gap of Nonnegative Matrices

   https://doi.org/10.1137/1.9781611975994.73  

   Mehta, Jenish C.; Schulman, Leonard J. (January 2020, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms)

   The classic graphical Cheeger inequalities state that if $$M$$ is an $$n\times n$$ \emph{symmetric} doubly stochastic matrix, then \[ \frac{1-\lambda_{2}(M)}{2}\leq\phi(M)\leq\sqrt{2\cdot(1-\lambda_{2}(M))} \] where $$\phi(M)=\min_{S\subseteq[n],|S|\leq n/2}\left(\frac{1}{|S|}\sum_{i\in S,j\not\in S}M_{i,j}\right)$$ is the edge expansion of $$M$$, and $$\lambda_{2}(M)$$ is the second largest eigenvalue of $$M$$. We study the relationship between $$\phi(A)$$ and the spectral gap $$1-\re\lambda_{2}(A)$$ for \emph{any} doubly stochastic matrix $$A$$ (not necessarily symmetric), where $$\lambda_{2}(A)$$ is a nontrivial eigenvalue of $$A$$ with maximum real part. Fiedler showed that the upper bound on $$\phi(A)$$ is unaffected, i.e., $$\phi(A)\leq\sqrt{2\cdot(1-\re\lambda_{2}(A))}$$. With regards to the lower bound on $$\phi(A)$$, there are known constructions with \[ \phi(A)\in\Theta\left(\frac{1-\re\lambda_{2}(A)}{\log n}\right), \] indicating that at least a mild dependence on $$n$$ is necessary to lower bound $$\phi(A)$$. In our first result, we provide an \emph{exponentially} better construction of $$n\times n$$ doubly stochastic matrices $$A_{n}$$, for which \[ \phi(A_{n})\leq\frac{1-\re\lambda_{2}(A_{n})}{\sqrt{n}}. \] In fact, \emph{all} nontrivial eigenvalues of our matrices are $$0$$, even though the matrices are highly \emph{nonexpanding}. We further show that this bound is in the correct range (up to the exponent of $$n$$), by showing that for any doubly stochastic matrix $$A$$, \[ \phi(A)\geq\frac{1-\re\lambda_{2}(A)}{35\cdot n}. \] As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of $$n^{\alpha}$ for $$\frac{1}{2}\leq\alpha\leq1$$ in lower bounding $$\phi$$ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices $$R$$ with nonnegative entries, to obtain a two-sided \emph{gapped} refinement of the Perron-Frobenius theorem. Recall from the Perron-Frobenius theorem that for such $$R$$, there is a nonnegative eigenvalue $$r$$ such that all eigenvalues of $$R$$ lie within the closed disk of radius $$r$$ about $$0$$. Further, if $$R$$ is irreducible, which means $$\phi(R)>0$$ (for suitably defined $$\phi$$), then $$r$$ is positive and all other eigenvalues lie within the \textit{open} disk, so (with eigenvalues sorted by real part), $$\re\lambda_{2}(R) 

   more » « less
4. Absence of bubbling phenomena for non-convex anisotropic nearly umbilical and quasi-Einstein hypersurfaces

   https://doi.org/10.1515/crelle-2021-0038  

   De Rosa, Antonio; Gioffrè, Stefano (August 2021, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract We prove that, for every closed (not necessarily convex) hypersurface Σ in ℝ n + 1 {\mathbb{R}^{n+1}} and every p > n {p>n} , the L p {L^{p}} -norm of the trace-free part of the anisotropic second fundamental form controls from above the W 2 , p {W^{2,p}} -closeness of Σ to the Wulff shape. In the isotropic setting, we provide a simpler proof. This result is sharp since in the subcritical regime p ≤ n {p\leq n} , the lack of convexity assumptions may lead in general to bubbling phenomena.Moreover, we obtain a stability theorem for quasi-Einstein (not necessarily convex) hypersurfaces and we improve the quantitative estimates in the convex setting. 

   more » « less
5. A STABILITY VERSION OF THE GAUSS–LUCAS THEOREM AND APPLICATIONS

   https://doi.org/10.1017/S1446788719000284  

   STEINERBERGER, STEFAN (September 2019, Journal of the Australian Mathematical Society)

   Let $$p:\mathbb{C}\rightarrow \mathbb{C}$$ be a polynomial. The Gauss–Lucas theorem states that its critical points, $$p^{\prime }(z)=0$$ , are contained in the convex hull of its roots. We prove a stability version whose simplest form is as follows: suppose that $$p$$ has $n+m$ roots, where $$n$$ are inside the unit disk, $$\begin{eqnarray}\max _{1\leq i\leq n}|a_{i}|\leq 1~\text{and}~m~\text{are outside}~\min _{n+1\leq i\leq n+m}|a_{i}|\geq d>1+\frac{2m}{n};\end{eqnarray}$$ then $$p^{\prime }$$ has $n-1$ roots inside the unit disk and $$m$$ roots at distance at least $(dn-m)/(n+m)>1$ from the origin and the involved constants are sharp. We also discuss a pairing result: in the setting above, for $$n$$ sufficiently large, each of the $$m$$ roots has a critical point at distance $${\sim}n^{-1}$$ . 

   more » « less