We study the simultaneous approximation of constant-degree polynomials over convex sets. For any family of $m$ degree-$d$ polynomials and any convex set ${H} \subseteq \mathbb{R}_{\ge0}^n$, we construct an $\epsilon$-Cover of the joint value set $\{(f_1(x), \dots, f_m(x)) : x \in {H}\}$ in the $\ell_\infty$-norm. This cover is of size $n^{O(\log(mn)/\epsilon^2)}$, provided the polynomials have constant range over the smallest $\ell_1$-ball inscribing ${H}$. Our approach extends classical net-based sparsifications for linear functions (e.g., Lipton, Markakis, and Mehta [2003]) to arbitrary families of constant-degree polynomials over general convex sets. We use a two-step scheme: first, we construct a quasi-polynomial pre-cover of the family on the smallest $\ell_1$-ball containing ${H}$ by using a concentration argument and leveraging a connection between Bernstein approximation and multinomial distributions; we then compress the pre-cover to ${H}$ by using a recursive degree reduction and feasibility programs anchored at points of the pre-cover. The existence of these covers immediately yields a unified framework for Quasi-Polynomial Time Approximation Schemes (QPTAS) across a wide range of a problems, including fixed-degree polynomial minimization over polyhedral sets, Constraint Satisfaction Problems (CSPs), Free Games, variational inequalities with polynomial operators (which implies guarantees for local Nash equilibria in polynomial games), and additive approximation for normalized densest $k$-subhypergraph on $O(1)$-uniform hypergraphs.
Let $\mu$ be a log-concave probability measure on $\mathbb R^n$ and let $f\colon\mathbb R^n\to\mathbb R^k$ be a polynomial mapping of degree at most $d$. We show that \[ \mu(f\in A) \le C\bigl(\lambda_k(A)\bigr)^{\frac{1}{k(d-1)+1}} \] for every Borel set $A\subset\mathbb R^k$ whenever the image measure $\mu\circ f^{-1}$ is absolutely continuous. The constant $C$ is independent of the dimension $n$, and the exponent $\frac{1}{k(d-1)+1}$ is sharp. This extends the scalar Carbery--Wright inequality and answers, in the log-concave setting, a question raised by Avni, Glazer, and Larsen. In addition, we show that the density of $\mu\circ f^{-1}$, whenever it exists, belongs to the Nikolskii--Besov space $B^{\frac{1}{k(d-1)+1}}_{1,\infty}(\mathbb R^k)$, with a dimension-free bound for the corresponding norm. A central difficulty in passing from scalar polynomials to vector-valued polynomial mappings is the lack of a suitable nondegeneracy parameter quantifying absolute continuity of $\mu\circ f^{-1}$, as the variance does in the scalar case. Natural candidates such as the covariance matrix or the Jacobian matrix either fail to characterize this property or do not lead to dimension-free estimates. We identify such a parameter and define it to be the covariance matrix of the vector formed by the monomials of degree up to $d^{k-1}$ in the normalized components of $f$. The dimension-free nature of our results allows us to extend Kusuoka's absolute continuity criterion for Gaussian polynomial random vectors to the log-concave setting. Moreover, in this setting, we obtain estimates relating convergence in distribution to convergence in total variation for polynomial random vectors.
We study the cone $\mathcal{M}_{n,2d}$ of nonnegative mean polynomials---real $n$-variate forms of degree $2d$ that can be expressed as weighted power means $M_{q,p}(Y,w)$ with $q>p$. This cone simultaneously generalises the cone of sums of squares $\Sigma_{n,2d}$ and the cone of sums of nonnegative circuit polynomials $\mathcal{C}_{n,2d}$. We prove that every square of an arbitrary polynomial belongs to the mean polynomial preprime $T_{\mathrm{mean}}$, that $T_{\mathrm{mean}}$ is strongly generating, and consequently that every polynomial strictly positive on a compact semialgebraic set admits a representation with mean polynomial certificates. We exhibit the Robinson form $\hat{R}$ as a separating example that lies in $\mathcal{M}_{4,4}$ but outside $\mathrm{SOSONC}_{4,4}$. Finally, we outline a convergent hierarchy of lower bounds for polynomial optimization based on the mean polynomial cone and discuss tractable depth-truncated approximations via signomial programming.
We give a $\text{poly}(d, p, \log(1/\epsilon))$-time algorithm that computes an $\epsilon$-approximate fixed point of any $\ell_p$-nonexpansive map $f : \mathcal{X} \to \mathcal{X}$, where $\mathcal{X} \subset \mathbb R^d$ is a convex compact set and $p$ is an even integer. This is the first algorithm with $\text{poly}(d, \log(1/\epsilon))$ runtime for any fixed $p \ne 2$. Our techniques are based on a computationally efficient version of Sion's theorem for non-compact minmax problems, and extend to more general total search problems that admit low-degree polynomial potentials.
Constantinos Daskalakis, Gabriele Farina, B. Zhang· 0 citations
Let $\mu$ be an $n$-AD-regular measure in $\mathbb{R}^d$. Chousionis, Garnett, Le and Tolsa [CGLT] proved that $\mu$ is uniformly $n$-rectifiable if and only if the square function built from the density differences $\Delta_\mu(x,r)=\mu(B(x,r))/r^n-\mu(B(x,2r))/(2r)^n$ satisfies a Carleson condition. In this paper we show that the same characterization holds if the density is first composed with a function $F$ which is bi-Lipschitz on the interval $[c_0^{-1},c_0]$ determined by the AD-regularity constant $c_0$. The main example is $F=\log$, introduced in [Le], for which the square function takes the scale-invariant form $\Delta_\mu^{\log}(x,r) = \log\bigl(\mu(B(x,r))/\mu(B(x,2r))\bigr)+n\log 2$. We give a complete proof, extend the statement to the smooth square functions of [CGLT], where the density is replaced by the convolution of $\mu$ with a Gaussian or a more general radial kernel, discuss what happens when $F$ is not bi-Lipschitz, and treat the case $\mu(\mathbb{R}^d)<\infty$, where the behavior of $F$ near zero enters in only one of the two implications. We also show that the qualitative characterization of $n$-rectifiable measures by Tolsa and Toro [TT], in terms of the same square function at $\mu$-almost every point, holds after composition with any locally bi-Lipschitz $F$. This requires neither AD-regularity nor doubling, and for $F=\log$ the condition $\lim_{r\to0}\Delta_\mu(x,r)=0$ becomes $\lim_{r\to0}\mu(B(x,r))/\mu(B(x,2r))=2^{-n}$.
Let $P (Y_1, ..., Y_d)$ be a certain fixed homogeneous polynomial of integral coefficients. In this paper, we establish a quantitative equidistribution criterion for the ergodic averages along $\Omega (|P (n_1, ..., n_d)|)$. Consequently, by an estimate of Lachand, we prove the following variant of a theorem of Bergelson and Richter: if $P$ is an irreducible binary cubic form and $ (X, T)$ is a uniquely ergodic system with unique invariant measure $\mu$, then for any $x \in X$ and $f \in C(X)$, \begin{equation*} \lim_{N \rightarrow \infty} \frac 1 {N^2} {\mathop{\sum\sum}_{n_1, n_2 \leqslant N}} f \big( T^{ \Omega (|P (n_1, n_2)| ) } x \big) = \int_{X} f \ \mathrm{d} \mu . \end{equation*} Moreover, we prove in the appendix a related conjecture of C\'espedes and Donoso over number fields.
Let $X=\{X_j\}_{j=1}^\infty$ be a sequence of independent random variables whose densities and moments of order $2d$ are uniformly bounded. For a random vector $f(X)=(f_1(X),f_2(X))$ whose components are polynomial functionals of degree at most $d$, we prove that \[ [[f]]_{\mu,\infty}^{\frac1{2d-1}}\mu(f\in A) \le C\bigl(\lambda_2(A)\bigr)^{\frac1{2d-1}} \] for every Borel set $A\subset\mathbb R^2$, where $C$ depends only on $d$ and the uniform density and moment bounds, and $\lambda_2$ denotes the Lebesgue measure on $\mathbb R^2$. Here $[[f]]_{\mu,\infty}$ measures the failure of proportionality of the highest-order orthogonal-chaos components of $f_1$ and $f_2$ with respect to the law $\mu$ of $X$. Consequently, whenever these components are not proportional, the law of $f$ admits a density in the weak Lorentz space $L^{\frac{2d-1}{2d-2},\infty}(\mathbb R^2)$. This recovers the dichotomy established by Nualart and Tudor for two-dimensional Wiener chaos vectors and extends it beyond the Gaussian setting. We also obtain the lower bound \[ \int_{\mathbb R^\infty}\Delta_f\,d\mu \ge C[[f]]_{\mu,\infty}^2, \] where $\Delta_f$ is the determinant of the Gram matrix of $\nabla f_1$ and $\nabla f_2$. In the special case of Gaussian measures, this gives a relaxed version of the estimate conjectured by Nourdin, Nualart, and Poly.
Egor D. Kosov· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
