For fixed A > 0, a one-pass learner with Ad^2 persistent bits needs \Omega_A(d\log(1/\epsilon)) noiseless Gaussian samples to recover a unit vector to angular error 0\lt \epsilon\le1/10 with probability 2/3, uniformly in accuracy for large d. Computation and randomized updates are unrestricted, but output uses only the terminal state, stopping index and fresh randomness. (Lean)
Manuscripts (6)
Memory and precision in noiseless Gaussian regression
September 27, 2026 · source · Lean formalization available · cite as \cite{OAI:Memory-and-precision-in-noiseless-Gaussian-regression-September-27-2026}
For every fixed A > 0, a learner that retains at most Ad^2 bits between fresh exact Gaussian linear measurements needs \Omega_A(d\log(1/\epsilon)) measurements to estimate a uniformly random unit vector to angular error at most ϵ, for any 0\lt \epsilon\le 1/10, with probability at least 2/3. The constant is absolute for o(d^2) memory.
Posterior replicas and conditional information in Gaussian regression
September 27, 2026 · source · Lean formalization available · cite as \cite{OAI:Posterior-replicas-and-conditional-information-in-Gaussian-regression-September-27-2026}
For a signal with density bounded by L relative to uniform probability on S^{d-1}, we bound the information in a finite message W formed from exact Gaussian measurements, conditional on an independent projection revealed only to the analyst. For explicit row counts proportional to d, the bound is O(H(W)/d+d+\log(2+\log L)). Consequently, a finite-state learner with o(d^2) persistent bits and a deterministic sample horizon needs \Omega(d\log(1/\epsilon)) fresh noiseless Gaussian measurements for constant-probability angular accuracy 0\lt \epsilon\le1/10 under the uniform spherical prior.
Localization costs and information growth for exact Gaussian observations
September 27, 2026 · source · cite as \cite{OAI:Localization-costs-and-information-growth-for-exact-Gaussian-observations-September-27-2026}
For the image of a uniform cube under a spherical coordinate map, we prove that finite messages from t blocks of \Theta(d) exact Gaussian measurements reveal only O_A(dt) information when each message has at most \exp(Ad^2) values, for fixed A. The same bound holds when each message is supplemented with a nested cell that restores the required geometric spread.
Projection moments, positive cap domination, and Riesz estimates on the sphere
September 27, 2026 · source · Lean formalization available · cite as \cite{OAI:Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere-September-27-2026}
We prove moment estimates for exact random projections of finite measures whose mass is controlled on Euclidean balls, and derive positive domination by countable sums of spherical cap measures. For learners with M=o(d^2) bits of memory, these estimates give three proofs that uniform-sphere average success at least 2/3 at angular accuracy 0\lt \epsilon\le1/10 requires \Omega(d\log(1/\epsilon)) noiseless Gaussian observations. The three proofs keep their different stopping and accuracy costs explicit.
Replacing Gaussian observations in memory-constrained inference
September 27, 2026 · source · Lean formalization available · cite as \cite{OAI:Replacing-Gaussian-observations-in-memory-constrained-inference-September-27-2026}
Replacing the Gaussian rows used to select a finite message by independent rows increases the remaining conditional information by at most Cd, for a uniform spherical signal, message entropy at most d2, and the specified row dimensions proportional to d. As an application, we prove that learners with M=o(d^2) persistent bits need T=\Omega(d\log(1/\epsilon)) exact observations to attain uniform-sphere angular success at least 3/5, for 0\lt \epsilon\le1/10 and a deterministic finite horizon.
Subsphere methods for memory-sample lower bounds in noiseless Gaussian regression
September 27, 2026 · source · Lean formalization available · cite as \cite{OAI:Subsphere-methods-for-memory-sample-lower-bounds-in-noiseless-Gaussian-regression-September-27-2026}
Let a finite-state streaming learner estimate a uniformly random unit vector from independent exact Gaussian linear measurements. We prove that o(d^2) bits of persistent memory and angular success probability at least 2/3 require at least 2^{-16}d\log_2(1/\epsilon) samples for all sufficiently large d, uniformly for 0\lt \epsilon\le1/10. The proof conditions each batch on its observed projection and controls the resulting random residual subsphere.
Result 140 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md