Concentration conjecture for sampling the sphere by mutually orthogonal subspaces

Let ASn1A\subseteq S^{n-1} be a measurable subset with σn1(A)ecn\sigma_{n-1}(A)\geq e^{-c\sqrt{n}}. For a subspace HRnH\subseteq\mathbb{R}^n of dimension n/2\lfloor n/2\rfloor, let HH^{\perp} be its orthogonal complement, and let σH\sigma_H and σH\sigma_{H^{\perp}} denote the Haar probability measures on Sn1HS^{n-1}\cap H and Sn1HS^{n-1}\cap H^{\perp}, respectively. Let PH\mathbb{P}_H denote the orthogonally invariant Haar probability measure on the Grassmannian of such subspaces. Concentration conjecture.

PH(σH(AH)σH(AH)0.9σn1(A))1Cecn,\mathbb{P}_{H}\left(\sqrt{\sigma_H(A\cap H)\sigma_{H^{\perp}}(A\cap H^{\perp})}\geq 0.9\sigma_{n-1}(A)\right) \geq 1-Ce^{-c'\sqrt{n}},

where C,c,c>0C,c,c'>0 are universal constants. This conjecture would extend the Klartag–Regev concentration inequality to sets of measure of order ene^{-\sqrt n} and is intended to yield an Ω(n)\Omega(\sqrt n) communication lower bound for the classical vector-in-subspace problem. Its resolution status is not established in the supplied text.

Sources & referencesView supporting material

Primary source

Uri Grupel, “Sampling on the Sphere by Mutually Orthogonal Subspaces”, arXiv:1607.03714 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.