Friedgut conjectured that an increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have bounded size, with a bound independent of the dimension and the bias (J. Amer. Math. Soc. 12 (1999)). We prove this conjecture by showing that, for $0<p\leq 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $\mu_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$. A separate high-bias argument completes the proof for all $p\in(0,1)$. Our proof builds on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)). Tracking Hatami's construction isolates an adaptive representation with increasing local activations and dimension-free arity and multiplicity-counted load bounds. Our main new ingredient is a bias-matched randomized shifting procedure that converts the pseudo-junta approximator into an increasing function while retaining exact measurability with respect to a controlled forced refinement of its adaptive representation. From the resulting monotone adaptive representation, we extract positive certificates and truncate them to obtain the required narrow DNF.
A long-standing question posed by Fukuda (1995) and Ziegler (2000) inquires about the asymptotic behavior of $g(n)$, the maximum number of facets that an $n$-dimensional $0/1$-polytope can have. A remarkable result by B\'ar\'any and P\'or (2001) via probabilistic methods established that $g(n)$ is at least superexponen...
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 parameter...
We prove Breiman's conjecture under the first-moment assumption. Let $Y_1,Y_2,\ldots$ be iid nonnegative random variables with $\mathbb P\{Y_1>0\}>0$, normalized by their sum. If the resulting randomly weighted sum converges to a nondegenerate law for one fixed integrable, nonconstant mark distribution, then the tail o...
Let $Q\geq 1$ be large, and $\delta \in(0,1)$ be small. Denote by $\mathcal C \subset \mathbb R^3$ a sufficiently smooth curve with non-vanishing curvature and torsion. How many rational points $\mathbf{a}/q$ of height $q\in[1, Q]$ are $\delta/q$-near $\mathcal C$? This manuscript provides an essentially optimal answer...
Ming-Feng Chen, A. Seeger, Rajula Srivastava et al.· 2 citations
For every finite family of Euclidean balls in $\mathbb{R}^n$, $n\ge2$, and every $0<\delta<1/2$, we select a subfamily whose $(1+\delta)$-dilations cover the original union and whose undilated balls have multiplicity at most $C_n\delta^{-(n-1)/2}$. This proves the covering estimate conjectured by Han and Lu \cite{HL}....
We give an affirmative answer to the planar local smoothing problem in Question~1.7 of D.~Ntalampekos and positive and negative answers to the basic approximation and level-set parts of his higher-dimensional Question~1.8. In every dimension $n\ge2$, each continuous Lebesgue monotone function in $W^{1,p}$ on a bounded...
De-Guang Zhong· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
