 Award ID(s):
 1752184
 NSFPAR ID:
 10336967
 Date Published:
 Journal Name:
 International Mathematics Research Notices
 ISSN:
 10737928
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)Abstract Let $1\leq p \leq q <\infty $ and let $w \in \mathbb{C}$. Weissler conjectured that the Hermite operator $e^{w\Delta }$ is bounded as an operator from $L^{p}$ to $L^{q}$ on the Hamming cube $\{1,1\}^{n}$ with the norm bound independent of $n$ if and only if $$\begin{align*} p2e^{2w}(q2)\leq pe^{2w}q. \end{align*}$$It was proved in [ 1], [ 2], and [ 17] in all cases except $2<p\leq q <3$ and $3/2<p\leq q <2$, which stood open until now. The goal of this paper is to give a full proof of Weissler’s conjecture in the case $p=q$. Several applications will be presented.more » « less

An \ell _p oblivious subspace embedding is a distribution over r \times n matrices \Pi such that for any fixed n \times d matrix A , \[ \Pr _{\Pi }[\textrm {for all }x, \ \Vert Ax\Vert _p \le \Vert \Pi Ax\Vert _p \le \kappa \Vert Ax\Vert _p] \ge 9/10,\] where r is the dimension of the embedding, \kappa is the distortion of the embedding, and for an n dimensional vector y , \Vert y\Vert _p = (\sum _{i=1}^n y_i^p)^{1/p} is the \ell _p norm. Another important property is the sparsity of \Pi , that is, the maximum number of nonzero entries per column, as this determines the running time of computing \Pi A . While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 \le p \lt 2 , much less was known. In this article, we obtain nearly optimal tradeoffs for \ell _1 oblivious subspace embeddings, as well as new tradeoffs for 1 \lt p \lt 2 . Our main results are as follows: (1) We show for every 1 \le p \lt 2 , any oblivious subspace embedding with dimension r has distortion \[ \kappa = \Omega \left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \log ^{2 / p}r + \left(\frac{r}{n}\right)^{1 / p  1 / 2}}\right).\] When r = {\operatorname{poly}}(d) \ll n in applications, this gives a \kappa = \Omega (d^{1/p}\log ^{2/p} d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 is optimal up to {\operatorname{poly}}(\log (d)) factors. (2) We give sparse oblivious subspace embeddings for every 1 \le p \lt 2 . Importantly, for p = 1 , we achieve r = O(d \log d) , \kappa = O(d \log d) and s = O(\log d) nonzero entries per column. The best previous construction with s \le {\operatorname{poly}}(\log d) is due to Woodruff and Zhang (COLT, 2013), giving \kappa = \Omega (d^2 {\operatorname{poly}}(\log d)) or \kappa = \Omega (d^{3/2} \sqrt {\log n} \cdot {\operatorname{poly}}(\log d)) and r \ge d \cdot {\operatorname{poly}}(\log d) ; in contrast our r = O(d \log d) and \kappa = O(d \log d) are optimal up to {\operatorname{poly}}(\log (d)) factors even for dense matrices. We also give (1) \ell _p oblivious subspace embeddings with an expected 1+\varepsilon number of nonzero entries per column for arbitrarily small \varepsilon \gt 0 , and (2) the first oblivious subspace embeddings for 1 \le p \lt 2 with O(1) distortion and dimension independent of n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise \ell _p lowrank approximation. Our results give improved algorithms for these applications.more » « less

Abstract We consider vanishing properties of exponential sums of the Liouville function $\boldsymbol{\lambda }$ of the form $$ \begin{align*} & \lim_{H\to\infty}\limsup_{X\to\infty}\frac{1}{\log X}\sum_{m\leq X}\frac{1}{m}\sup_{\alpha\in C}\bigg\frac{1}{H}\sum_{h\leq H}\boldsymbol{\lambda}(m+h)e^{2\pi ih\alpha}\bigg=0, \end{align*} $$ where $C\subset{{\mathbb{T}}}$. The case $C={{\mathbb{T}}}$ corresponds to the local $1$Fourier uniformity conjecture of Tao, a central open problem in the study of multiplicative functions with farreaching numbertheoretic applications. We show that the above holds for any closed set $C\subset{{\mathbb{T}}}$ of zero Lebesgue measure. Moreover, we prove that extending this to any set $C$ with nonempty interior is equivalent to the $C={{\mathbb{T}}}$ case, which shows that our results are essentially optimal without resolving the full conjecture. We also consider higherorder variants. We prove that if the linear phase $e^{2\pi ih\alpha }$ is replaced by a polynomial phase $e^{2\pi ih^{t}\alpha }$ for $t\geq 2$ then the statement remains true for any set $C$ of upper boxcounting dimension $< 1/t$. The statement also remains true if the supremum over linear phases is replaced with a supremum over all nilsequences coming form a compact countable ergodic subsets of any $t$step nilpotent Lie group. Furthermore, we discuss the unweighted version of the local $1$Fourier uniformity problem, showing its validity for a class of “rigid” sets (of full Hausdorff dimension) and proving a density result for all closed subsets of zero Lebesgue measure.

Abstract In this paper we consider the following problem: let X k , be a Banach space with a normalised basis ( e (k, j) ) j , whose biorthogonals are denoted by ${(e_{(k,j)}^*)_j}$ , for $k\in\N$ , let $Z=\ell^\infty(X_k:k\kin\N)$ be their l ∞ sum, and let $T:Z\to Z$ be a bounded linear operator with a large diagonal, i.e. , $$\begin{align*}\inf_{k,j} \bige^*_{(k,j)}(T(e_{(k,j)})\big>0.\end{align*}$$ Under which condition does the identity on Z factor through T ? The purpose of this paper is to formulate general conditions for which the answer is positive.more » « less

Abstract Let $k_i\ (i=1,2,\ldots ,t)$ be natural numbers with $k_1>k_2>\cdots >k_t>0$, $k_1\geq 2$ and $t<k_1.$ Given real numbers $\alpha _{ji}\ (1\leq j\leq t,\ 1\leq i\leq s)$, we consider polynomials of the shape $$\begin{align*} &\varphi_i(x)=\alpha_{1i}x^{k_1}+\alpha_{2i}x^{k_2}+\cdots+\alpha_{ti}x^{k_t},\end{align*}$$and derive upper bounds for fractional parts of polynomials in the shape $$\begin{align*} &\varphi_1(x_1)+\varphi_2(x_2)+\cdots+\varphi_s(x_s),\end{align*}$$by applying novel mean value estimates related to Vinogradov’s mean value theorem. Our results improve on earlier Theorems of Baker (2017).