Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

We study Gaussian regression under squared population L2 loss in a known m-dimensional subspace of degree-at-most-k functions on the d-dimensional Boolean cube. Random inputs can undersample regions essential for prediction, delaying the parametric rate even when the model is known. For fixed q0<1/2, 1≤ k≤ q0d, and sufficiently large fixed A, the worst-subspace sample threshold for minimax error Aσ2(m+t)/n with confidence 1-e-t, t≥log4, is [ N=(m+t)expEd,k+O(k1/3), quad Ed,k=dPsi(k/d), ] where Psi(q)=log2-mathsf H(tfrac12-√q(1-q)) and mathsf H is binary entropy with natural logarithms. The upper bound holds for every feasible m; the matching lower bound holds when m≤binom dlfloor k1/3rfloor or t≥ m. We sharpen the Polyanskiy--Samorodnitsky uncertainty principle in two respects. First, for fixed leakage ρ∈(0,1), the smallest set carrying a fraction 1-ρ of a nonzero degree-at-most-k polynomial's energy has probability exp-Ed,k+Oρ,q0(k1/3). An Airy-kernel construction proves that the remainder cannot be o(k1/3) in general. Second, we construct a subspace of dimension binom dlfloor k1/3rfloor such that every function in the subspace has at least a fraction 1-ρ of its energy on the same set, whose probability is at most exp-Ed,k+Cρ,q0k1/3. For sufficiently large k, this set is a Hamming ball. A striking consequence is an exponential cost of noise: the parametric rate can require (m+t)4kexp-O(k1/3) samples, whereas O((m+t)2k) suffice for noiseless identification. As k→∞ with k/d→0, the noisy threshold is (m+t)exp2k+o(k).