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 the image of a single quadratic. We significantly improve this lower bound to \[ \exp\left(c\frac{\sqrt{\log N}}{\log\log N}\right). \] We also prove density-dependent variants, including a two-set version motivated by Green--Harper's robust inverse large sieve conjectures and their connection with the inverse Goldbach problem. Combined with a theorem of Elsholtz--Harper on hypothetical decompositions of the primes, our results show that any such decomposition would force both summands to have large intersections with quadratic images. Our proof combines a weighted entropy argument with sieve estimates, inspired by the recent work of Croot--Mao--Pohoata--Sheffer--Yip.
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$. The comparison is certified by seven strict rational inequalities and, in particular, places the attained ratio above $207/200$, while the conjectured constant lies below $207/200$. On the positive side, we prove the conjectured sharp bound for every family of rank-at-most-one summands when $2\leq p<\infty$, and classify all equality cases. We also prove the corresponding endpoint statement for $p=\infty$. Finally, for arbitrary complex matrices, we establish the conjectured sharp constant in the case $m=2$, $p=4$.
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.
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 n)^{A_\varepsilon}} \le k_{1,\varepsilon}(n) \le C_\varepsilon \frac{n^2\{\log\log(e^e n)\}^2}{\log(e n)}. \] Previously, the best unrestricted bounds for general linear sketches of the Schatten--1 norm were $\Omega(n)$ and the trivial $O(n^2)$ upper bound (Li, Nguyen, Woodruff'19), leaving a polynomial gap. Our bounds close that gap up to polylogarithmic factors and give a nontrivial logarithmic saving below the $n^2$-measurement storage bound. The result extends much further. Write $k_{p,\varepsilon}(n)$ for the analogous sketch dimension for the Schatten--$p$ norm. For every fixed finite $p>0$ that is not a positive even integer, there are positive constants $A_{p,\varepsilon},C_{p,\varepsilon},c_p$ such that \[ \frac{n^2}{(\log n)^{A_{p,\varepsilon}}} \le k_{p,\varepsilon}(n) \le C_{p,\varepsilon}\frac{n^2}{(\log n)^{c_p}}, \] so $k_{p,\varepsilon}(n)=n^{2-o(1)}$ throughout the non-even regime. Together with the known tight bounds $\Theta_{p,\varepsilon}(n^{2-4/p})$ for positive even $p$ and $\Theta_\varepsilon(n^2)$ for $p=\infty$ (Li, Woodruff'16), our results close the remaining polynomial gap across the Schatten family and complete, up to polylogarithmic factors, the polynomial-order classification of general linear sketches for all Schatten-$p$ norms.
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 full statement and showed that the set of counterexamples contains a dense $G_\delta$ set. We prove that a set of counterexample pairs with the first coordinate being a badly approximable number has Hausdorff dimension at least $3/2$. We further show that the set of badly approximable numbers $\xi$ for which there exists $\zeta$ such that $(\xi,\zeta)$ is a counterexample to ULC has full Hausdorff dimension. This contrasts with the classical Littlewood conjecture, for which the set of possible counterexamples is known to have Hausdorff dimension $0$.
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 degree at most $k$ has discrepancy at most $n^{\frac12-\frac{1}{2(D+1)}-\varepsilon}$ for some $\varepsilon=\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\tilde O(n^{\frac12-\frac{1}{2(D+1)}})$. In the opposite direction, we construct $n$-point sets in $\mathbb R^d$ whose discrepancy with respect to hyperplanes is $\tilde\Omega(n^{\frac12-\frac{1}{d+1}}),$ extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.