The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ \Theta\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.
The quadratic inverse large sieve problem predicts that the examples sharp at the square-root threshold are essentially quadratic. Hanson proved the first unconditional result in this direction: if $A\subseteq[N]$, $|A|\gg\sqrt N$, and $|A_p|\le p/2+O(1)$ for every prime $p$, then $A$ contains $\gg\log N$ elements in t...
For $m\geq 2$, let $c_p(m)$ be the all-dimensional best constant in $$ \left\|\sum_{k=1}^m A_k\right\|_p \leq c_p(m)\left\|\sum_{k=1}^m |A_k|\right\|_p. $$ Tang and Zhang conjectured an explicit formula for every finite $p>1$. We disprove the conjecture with two explicit real $2\times 2$ rank-one matrices at $p=3/2$. T...
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...
Let $k_{1,\varepsilon}(n)$ be the smallest number of real linear measurements needed by a randomized oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pm\varepsilon$, with probability at least $2/3$. For every fixed $0<\varepsilon<1$, we prove \[ \frac{n^2}{(\log...
The uniform Littlewood conjecture (ULC), introduced by Bandi, Fregoli and Kleinbock, asserts in the two-number case that $$ \lim_{Q\to\infty} Q\min_{1\le n\le Q}\|n\xi\|\,\|n\zeta\|=0 $$ for all real $\xi,\zeta$. It is proven to hold for almost every pair $(\xi,\zeta)$. Schleischitz, however, has recently disproved the...
We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degre...
A. Adıbelli, István Tomon· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
