==== TABLE OF CONTENTS ====
Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//main.tex
Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//preamble.tex
Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/geometry-model.tex
Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/introduction.tex
Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/positive-caps.tex
Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/projection.tex
Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/riesz.tex
Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//references.bib
===========================

==== BEGIN Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//main.tex ====
\documentclass[11pt]{article}
\input{preamble}
\title{Projection moments, positive cap domination,\\
and Riesz estimates on the sphere}
\author{OpenAI}
\date{September 27, 2026}
\begin{document}
\maketitle
\begin{abstract}
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<\epsilon\le1/10\) requires
\(\Omega(d\log(1/\epsilon))\) noiseless Gaussian observations. The three
proofs keep their different stopping and accuracy costs explicit.
\end{abstract}
\begingroup
\small
\tableofcontents
\endgroup
\clearpage
\input{sections/introduction}
\input{sections/geometry-model}
\input{sections/projection}
\input{sections/positive-caps}
\input{sections/riesz}
\bibliographystyle{plain}
\bibliography{references}
\end{document}
==== END Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//main.tex ====

==== BEGIN Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//preamble.tex ====
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{needspace}
\usepackage{array,enumitem,booktabs}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage[nameinlink,noabbrev]{cleveref}
\hypersetup{
  pdftitle={Projection moments, positive cap domination, and Riesz estimates on the sphere},
  pdfauthor={OpenAI},
  pdfsubject={Exact random projections and finite-state noiseless Gaussian regression},
  bookmarksopen=true,
  bookmarksnumbered=true
}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\renewcommand{\P}{\mathbb P}
\newcommand{\1}{\mathbf 1}
\newcommand{\ind}{\mathbf 1}
\newcommand{\sphere}{S^{d-1}}
\newcommand{\norm}[1]{\left\lVert #1\right\rVert}
\newcommand{\abs}[1]{\left\lvert #1\right\rvert}
\newcommand{\inner}[2]{\langle #1,#2\rangle}
\newcommand{\ip}[2]{\langle #1,#2\rangle}
\newcommand{\dist}{\operatorname{dist}}
\newcommand{\aff}{\operatorname{aff}}
\newcommand{\vol}{\operatorname{vol}}
\newcommand{\op}{\mathrm{op}}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\supp}{supp}
==== END Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//preamble.tex ====

==== BEGIN Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/geometry-model.tex ====
\section{Spherical probabilities and exact observations}
\label{p:geometry-model}

We collect the geometric facts used by all three estimates and then specify
the finite-state experiment to which they will be applied. The geometric
lemmas keep their normalizations visible: all measures on spheres below are
probability measures, whereas densities on Euclidean label spaces are
relative to Lebesgue measure unless another reference measure is stated.

\subsection{Coordinates and caps}

Write \(\sigma_d\) for uniform probability on the unit sphere
\(S^{d-1}\subset\R^d\), and write \(B(z,r)\) for the closed Euclidean ball
with center \(z\) and radius \(r\). When the ambient dimension is fixed we
abbreviate \(\sigma_d\) to \(\sigma\). The norm is Euclidean, and
\(\norm A_{\op}\) denotes the operator norm of a matrix. Constants denoted
by \(C\) are positive and absolute and may increase from one occurrence to
the next. A subscript records any permitted additional dependence.
All logarithms are natural unless a base is displayed.

\begin{lemma}[Coordinates of a uniform direction]\label{p:coordinate-density}
Let \(D\ge2\) and \(1\le k<D\) be integers. If \(U\) is uniform on
\(S^{D-1}\) and \(P\) is any \(k\)-by-\(D\) matrix satisfying
\(PP^{\mathsf T}=I_k\), then \(PU\) has Lebesgue density
\begin{equation}\label{p:coordinate-formula}
 c(D,k)(1-\norm u^2)^{(D-k-2)/2}\1_{\{\norm u<1\}},
 \qquad
 c(D,k)=\frac{\Gamma(D/2)}
 {\pi^{k/2}\Gamma((D-k)/2)}.
\end{equation}
The direction of the component of \(U\) in \(\ker P\) is uniform on its
unit sphere and is independent of the pair consisting of \(PU\) and the
length of that complementary component. In particular, its conditional
law given \(PU\) is uniform.
\end{lemma}

\begin{proof}
Rotation invariance reduces the projection to the first \(k\) coordinates.
Let \(G\in\R^k\) and \(H\in\R^{D-k}\) be independent standard Gaussian
vectors. Then \((G,H)/\sqrt{\norm G^2+\norm H^2}\) is uniform on the sphere.
The random variables \(\norm G^2/2\) and \(\norm H^2/2\) are independent
unit-scale gamma variables of shapes \(k/2\) and \((D-k)/2\). Changing
variables from these two positive numbers to their sum and their first
fraction shows that the fraction has density
\[
 \frac{\Gamma(D/2)}
 {\Gamma(k/2)\Gamma((D-k)/2)}
 t^{k/2-1}(1-t)^{(D-k)/2-1},\qquad 0<t<1.
\]
The direction of \(G\) is uniform and independent of these lengths.
Polar coordinates in \(\R^k\), with
\(\vol(S^{k-1})=2\pi^{k/2}/\Gamma(k/2)\), now give
\eqref{p:coordinate-formula}. The surface-area identity itself follows by
integrating \(e^{-\norm x^2}\) in polar coordinates. The direction of \(H\)
is uniform and independent of both lengths and of \(G\), which proves the
conditional assertion. The event \(H=0\) is null.
\end{proof}

The beta distribution in this lemma is a classical description of random
orthogonal projections; see Frankl and Maehara~\cite{FranklMaehara1990}.
We use the displayed derivation, including its conditional direction law.

Write \(v_k\) for the Lebesgue volume of the unit ball in \(\R^k\).
The following estimate will cancel the dimensional density scale in both
projection arguments.

\begin{lemma}[Unit-ball volume]\label{p:unit-ball-volume-lemma}
For every integer \(k\ge1\),
\begin{equation}\label{p:unit-ball-volume}
 v_k\le(2\pi e/k)^{k/2}.
\end{equation}
\end{lemma}

\begin{proof}
On the ball of radius \(\sqrt k\), the function
\(e^{-\norm z^2/2}\) is at least \(e^{-k/2}\). Comparing its integral
there with the full Gaussian integral gives
\[
 e^{-k/2}k^{k/2}v_k
 \le\int_{\R^k}e^{-\norm z^2/2}\,dz=(2\pi)^{k/2},
\]
which is the claimed bound.
\end{proof}

\begin{lemma}[Spherical cap mass]\label{p:cap-mass}
Put \(n=d-1\) for \(d\ge2\). There is an absolute \(a>0\) such that,
for every \(c\in S^{d-1}\) and \(0<r\le2\),
\begin{equation}\label{p:cap-mass-two-sided}
 (ar)^n\le \sigma\bigl(B(c,r)\bigr)\le\min\{1,r^n\}.
\end{equation}
For every ambient center \(z\in\R^d\) and radius \(r>0\),
\begin{equation}\label{p:ambient-cap-mass}
 \sigma\bigl(B(z,r)\bigr)\le\min\{1,(2r)^n\}.
\end{equation}
An output direction independent of the signal has probability at most
\(\epsilon^n\) of angular error at most \(\epsilon\), averaged over
\(\sigma\).
\end{lemma}

\begin{proof}
For \(r\le1\), rotate \(c\) to the north pole. A sphere point in
\(B(c,r)\) has last coordinate at least \(1-r^2/2\ge1/2\). Its surface
element as a graph over \(c^\perp\) is at most twice Lebesgue measure,
and its projection lies in the \(n\)-ball of radius \(r\). The full sphere
has area at least twice the volume of the unit \(n\)-ball, by projecting
both hemispheres. This proves the upper bound for \(r\le1\); total mass
one proves it for \(r>1\).

For the lower bound when \(r\le1\), the angular radius
\(2\arcsin(r/2)\) is at least \(r\). In polar angle the cap mass is the
integral of \(\sin^{n-1}\theta\) over this interval divided by its
integral over \([0,\pi]\). Use
\(\sin\theta\ge2\theta/\pi\) for \(0\le\theta\le r\) and bound the
denominator by \(\pi\). Since \(n\le2^{n-1}\), the result is at least
\((r/\pi)^n\). For \(1\le r\le2\), monotonicity therefore gives the
lower bound with \(a=1/(2\pi)\).

If an ambient ball meets the sphere, choose \(c\) in the intersection.
Its sphere portion is contained in \(B(c,2r)\), proving
\eqref{p:ambient-cap-mass}; an empty intersection is immediate. Finally,
angular error at most \(\epsilon\) implies chordal error at most
\(\epsilon\), because \(2\sin(\theta/2)\le\theta\). Apply the
sphere-centered upper bound to each fixed output and then integrate over
any independent output randomization.
\end{proof}

\subsection{The finite-state regression experiment}

An unknown direction \(s\in S^{d-1}\) is observed through independent
standard Gaussian features and their exact labels:
\[
 X_t\sim N(0,I_d),\qquad Y_t=\inner{X_t}{s},\qquad t=1,2,\ldots .
\]
At each sample index the learner retains a state from a set of at most
\(2^M\) values, where \(M\) is a nonnegative integer. A transition may
use the current state, the entire current pair \((X_t,Y_t)\), the sample
index, and fresh independent randomness. Computation within the transition
is unrestricted. Every piece of information depending on earlier samples
that remains available later must be encoded by the finite state. The
learner neither chooses a feature nor revisits an earlier one.

The learner stops after at most a prescribed integer \(T\ge0\) samples.
Its stopping decisions obey the same information restriction. For fixed
rules, its output is a unit vector whose law depends only on the terminal
state and stopping index, with fresh randomness allowed. In particular,
the last observed pair influences the output only through the terminal
state. The sample index is available without being stored in the state;
the proofs below account for the information in the stopping index.

A shared random seed may select the rules before sampling. The pair
consisting of this seed and the initial finite state is jointly independent
of the signal and the entire sequence of feature rows. The seed and initial
state may depend on each other. Fresh transition and output randomness is
independent of these variables and of initialization. Nonuniform rules may
also depend on \(d,\epsilon\), and the sample index. This is a bit-memory
model with a deterministic finite horizon.

We impose the following measurability convention. The original experiment
is jointly measurable in the signal, pre-generated feature rows, shared
seed, initial state, and fresh randomness, including the resulting state
path, stopping index, and output. For almost every fixed shared seed, the
finite vector of transition and stopping probabilities at each fixed
state and index is measurable in the completion of
\(\gamma_d(dx)\,dy\), where \(\gamma_d=N(0,I_d)\). A rule given instead
as a completed-measurable function of the current pair and an independent
fresh seed is also allowed; Lemma~\ref{p:borel-kernels} justifies this
presentation. Each terminal output law is a probability measure on the
Borel sphere.

For the lower bounds, let \(S\sim\sigma\) be independent of the feature
rows. We call the probability of
\(\arccos\inner{\widehat S}{S}\le\epsilon\), including all learner
randomness, the \emph{uniform-sphere average success probability}.

\begin{theorem}[Finite-memory precision bound]\label{p:regression}
Let \(M(d)=o(d^2)\) be a sequence of nonnegative integers and let
\(0<\epsilon(d)\le1/10\). There is an absolute \(c>0\) such that, for
all sufficiently large \(d\), every learner in the experiment above whose
uniform-sphere average success satisfies
\[
 \Prob\{\arccos\inner{\widehat S}{S}\le\epsilon(d)\}\ge\frac23
\]
must use
\[
 T(d)\ge c\,d\log\frac1{\epsilon(d)}.
\]
The dimension threshold may depend on the memory sequence. In particular,
the conclusion holds when the same success probability is required
separately for every \(s\in S^{d-1}\).
\end{theorem}

An every-signal guarantee implies the average guarantee by integration
against \(\sigma\). All three proofs use the average guarantee itself.
The first proof also yields a uniform dependence on the memory budget.

\begin{corollary}[Finite-dimensional memory dependence]
\label{p:finite-memory-tradeoff}
There are absolute constants \(c>0\) and \(d_0\) such that, for every
integer \(d\ge d_0\), every nonnegative integer \(M\), and every
\(0<\epsilon\le1/10\), a learner in the experiment above with
uniform-sphere average success at least \(2/3\) and deterministic finite
horizon \(T\) satisfies
\[
 T\ge \frac{c\,d\log(1/\epsilon)}{1+M/d^2}.
\]
\end{corollary}

The proof appears at the end of Section~\ref{p:projection}. In particular,
the same precision bound holds with absolute constants throughout
\(M\le d^2\) once \(d\) exceeds an absolute threshold.

\subsection{Measurable continuations and shared randomness}

The block arguments will start fresh executions from specified states,
including states the learner never reaches. The next lemma supplies Borel
rules for all such continuations while preserving the actual uniform-prior
experiment. Its proof uses the marginal law of each observation pair,
so it does not require a density conditional on a selected state.

\begin{lemma}[Borel versions and counterfactual continuations]
\label{p:borel-kernels}
Fix \(d\ge2\), finite \(T\), and finite state sets. Suppose each transition
and stopping probability, for each fixed state and index, is measurable in
the completion of the Borel sigma field of \(\R^d\times\R\) under
\(\lambda(dx,dy)=\gamma_d(dx)\,dy\), where \(\gamma_d\) is standard
Gaussian probability on \(\R^d\). The terminal output law depends only on
the terminal state and index. There are everywhere Borel probability
kernels with the same state sets and output laws that induce the same
uniform-prior joint law of signal, state path, stopping index, and output.
For the Borel learner, starting from any state and index and supplying fresh
future features defines a measurable continuation success function, whether
or not that state is reachable in the original execution.
The same conclusion holds when a rule is given before seed integration by
a finite probability vector measurable in the completion of
\(\lambda\otimes\kappa\), where \(\kappa\) is the law of an independent
fresh seed.
\end{lemma}

\begin{proof}
First suppose the rule includes a fresh seed of law \(\kappa\). Each
completed-product measurable coordinate has a product-measurable version:
approximate it by simple functions and replace the countably many level
sets by product-measurable sets modulo null sets. Replace the resulting
finite vector by a fixed point mass wherever it fails to be a probability
vector. This repair occurs on a product-measurable null set. Integrating
against \(\kappa\) now gives a Borel probability vector in the current
pair, and Fubini shows agreement with the original integrated rule for
\(\lambda\)-almost every pair. It therefore suffices to consider the
coordinate probabilities in the first statement.

For each fixed state and index, combine the possible transitions and stops
into a finite set of destinations, tagged as continuing or stopping.
Choose Borel versions of their coordinate probabilities by the same
simple-function construction. On the Borel null set where the versions
fail to be nonnegative or to sum to one, replace the vector by a fixed
point mass. Finitely many states and indices are involved, so all changes
lie in one Borel \(\lambda\)-null set \(Z\).

For every nonzero feature \(x\), Lemma~\ref{p:coordinate-density} gives
a Lebesgue density for \(\inner{x}{S}\). Since a Gaussian feature is
nonzero almost surely, every pre-generated pair
\((X_t,\inner{X_t}{S})\) has law absolutely continuous with respect to
\(\lambda\). Thus each pair avoids \(Z\) almost surely. Even if the
current state depends on previous observations, the probability of being
in a particular state and seeing a pair in \(Z\) is bounded by the
marginal probability of seeing that pair in \(Z\), which is zero.

Almost surely none of the finitely many pre-generated pairs lies in
\(Z\). Couple the original and modified finite destination kernels by
the same fresh uniform random numbers. Induction gives identical state
paths and stopping decisions; couple their unchanged terminal output laws
identically as well. This proves equality of the specified joint laws.
Finally, finite composition and integration of the Borel kernels against
independent future features and coins defines a measurable continuation
from every specified state and index, including unreachable states.
\end{proof}

\paragraph{Convention for the three applications.}
We first condition on a shared seed for which the model assumptions hold.
The joint independence of seed and initial state from signal and feature
rows ensures that the conditional initial-state law still contains no
signal or sample information. We then use the Borel learner supplied by
Lemma~\ref{p:borel-kernels}. The lemma need only preserve the
uniform-prior law; preservation at every fixed signal is unnecessary.
All bounds below are uniform in the fixed rules and are averaged over the
shared seed at the end. The original conditional success probabilities
are measurable in that seed because the original experiment is jointly
measurable. Neither the replacement kernels nor any subsequent proof
decompositions need to be selected jointly across seeds.

\subsection{A common full-data endpoint}

The three moment arguments produce bounds involving \(T+d\). The next
elementary obstruction supplies the linear lower bound on \(T\) needed
to remove that additive \(d\), without using any memory restriction.

\begin{lemma}[Antipodal full-data bound]\label{p:haar-linear}
In the experiment above, if \(\epsilon\le1/10\) and \(T\le d/8\),
even an estimator given all \(T\) features and labels has uniform-prior
success probability at most \(5/8\).
\end{lemma}

\begin{proof}
Let \(F\) be the row span of the pre-generated feature matrix and put
\(u=P_FS\). Its dimension is \(T\) almost surely, with the evident
interpretation for \(T=0\). The labels determine \(u\).
For \(T=0\), the residual is the original uniform signal. For \(T>0\),
Lemma~\ref{p:coordinate-density}, applied after fixing the feature matrix,
shows that conditional on all the data the residual is
\(\sqrt{1-\norm u^2}\,\omega\), with \(\omega\) uniform on the unit
sphere of \(F^\perp\). Before conditioning on the labels, isotropy gives
\(\E\norm u^2=T/d\). Consequently
\(\Prob\{\norm u^2\ge1/2\}\le2T/d\).

When \(\norm u^2<1/2\), opposite residual directions give two signals
at distance \(2\sqrt{1-\norm u^2}>\sqrt2>2\epsilon\). They have the same
conditional law, and at most one can be within chordal distance
\(\epsilon\) of a fixed output. Angular success implies this chordal
condition, so conditional success is at most \(1/2\), also after
averaging independent estimator randomness. Total success is at most
\[
 \frac12+\frac12\Prob\{\norm u^2\ge1/2\}
 \le\frac12+\frac Td\le\frac58.
\]
Giving the estimator all pre-generated data also covers a learner that
stops at a prefix, with its independent shared and fresh randomness.
\end{proof}
==== END Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/geometry-model.tex ====

==== BEGIN Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/introduction.tex ====
\section{Introduction}\label{p:introduction}

A linear projection can concentrate a measure even when the original
measure has no atoms. The amount of concentration depends on how much mass
can lie near the affine subspaces that a projection collapses. This paper
studies that dependence for random exact projections and uses it to analyze
what a finite memory state can retain from noiseless Gaussian equations.

We consider three questions. The first asks for an integrated moment of a
projected density. Let \(\nu\) be a finite positive measure in \(\R^d\)
whose mass on every ball of radius \(r\) is at most \(Kr^\beta\), and let
\(P\) be a random matrix with \(k\) orthonormal rows. When \(P_\#\nu\)
has density \(g_P\), an integrated estimate controls the average over
\(P\) of \(\int g_P^q\). Such an estimate measures concentration throughout
the label space. Theorem~\ref{p:frame-moment} proves a bound with explicit
dependence on the dimension, support radius, and local-mass exponent.

The second question asks for an actual positive dominating measure after a
finite routing decision. Let \(\sigma\) be uniform probability on
\(S^{d-1}\), and let \(\mu_B\) be \(\sigma\) conditioned on a spherical
cap \(B\). A routing rule observes a Gaussian matrix \(X\) and the exact
label \(Xs\), and selects an output \(w\) with probability
\(K_w(X,Xs)\). Its average likelihood \(f_w(s)=\E_XK_w(X,Xs)\)
weights the parent measure to \(f_w\mu_B\). We seek a positive sum of
normalized cap measures that dominates this measure, with a controlled
cost for small child radii. The positive-domination theorem in
Section~\ref{p:cap-section} constructs a countable such sum and bounds
its cost by a power of a reference routing probability.

The third question concerns evaluation at a specified label. For a
measurable function \(h:S^{d-1}\to[0,1]\), the ambient Riesz functional
\[
 V(h)=\sup_{z\in\R^d}\int h(s)\norm{s-z}^{-d/2}\,d\sigma(s)
\]
is the supremum of the raw Riesz potentials of \(h\sigma\) over ambient
centers, and it controls mass near every center. If \(h\sigma\) is restricted
to a ball about \(z\), Section~\ref{p:riesz-section} estimates a Gaussian projected
density at \(Xz+b\) for every fixed offset \(b\). It uses one explicitly
chosen density version for all offsets. This qualification matters:
an integrated density norm is unchanged by modifications on a
matrix-dependent graph, so it cannot by itself assign or bound the values
on that graph.

All three estimates give a precision bound for finite-state regression.
The signal is uniform on \(S^{d-1}\), and each fresh observation is a
standard Gaussian feature together with its exact inner product with the
signal. Write \(T\) for the learner's deterministic sample horizon.
In the bit-memory model of Section~\ref{p:geometry-model}, a learner
with \(M(d)=o(d^2)\) retained bits that achieves angular error at most
\(\epsilon(d)\), where \(0<\epsilon(d)\le1/10\), with average probability
at least \(2/3\)
requires
\[
 T(d)\ge c\,d\log(1/\epsilon(d))
\]
for an absolute \(c>0\) and all sufficiently large \(d\), as stated in
Theorem~\ref{p:regression}. The dimension threshold may depend on the
memory sequence. Under the same accuracy and success requirements, the
integrated projection argument also gives the explicit tradeoff
\[
 T\ge \frac{c\,d\log(1/\epsilon)}{1+M/d^2}
\]
for every nonnegative integer \(M\) and all \(d\) above an absolute
threshold (Corollary~\ref{p:finite-memory-tradeoff}). In particular, the
same precision bound holds with absolute constants throughout \(M\le d^2\).
The underlying success-probability bounds
\eqref{p:haar-success}, \eqref{p:cap-fixed-stop-explicit}, and
Proposition~\ref{p:riesz-success} retain explicit dependence on arbitrary
\(M\).

\subsection{Projection geometry and earlier methods}

The local growth condition belongs to classical potential theory.
Mattila's work on Hausdorff dimension and orthogonal projections uses
inverse-distance energy averaging and compares positive-dimensional
Hausdorff measure with the existence of a measure satisfying a ball-growth
bound~\cite[Lemma~5.1, p.~236, and Theorem~5.4, p.~237]{Mattila1975}.
Mattila describes the potential-theoretic projection method as following
Kaufman's work~\cite[Introduction, p.~227]{Mattila1975}. Here the growth
measure is supplied by a hypothesis or constructed from a cap test. The quantitative estimates require successive
distances to affine spans and moments whose order grows with \(d\).

Affine simplex volumes also have an established role in integral geometry.
Drury's affine-plane change of variables contains a simplex-volume
Jacobian~\cite[Lemma~1, pp.~497--498]{Drury1984}. In our frame calculation,
the product of successive affine heights is the volume of the associated
parallelepiped, and the \(k\) projected rows raise its inverse to the
\(k\)th power. We derive that row-Jacobian and its probability normalization
directly. The exact density of a rectangular block of a Haar orthogonal
matrix is classical; see Jiang~\cite[Lemma~2.5]{Jiang2006}.
Our derivation keeps its normalization explicit before the affine-height
change of variables. Classical beta descriptions of a uniform direction projected
onto a subspace are discussed by Frankl and
Maehara~\cite{FranklMaehara1990}; Lemma~\ref{p:coordinate-density}
gives the vector density and conditional direction law used here.

The regression application sits within a broader study of learning with
limited retained information. Shamir's finite-message protocols include a
bounded-memory online subclass~\cite[Section~2]{Shamir2014}.
Steinhardt, Valiant, and Wager related memory, communication, and statistical
queries~\cite[Section~1.1]{SVW2016}; Raz subsequently proved a qualitative
quadratic-memory versus exponential-sample separation for parity
learning~\cite[Theorem~1]{Raz2016}. For regression, Steinhardt and Duchi
established memory-dependent minimax risk bounds in a sparse noisy
model~\cite[Section~1.1]{SteinhardtDuchi2015}.

Sharan, Sidford, and Valiant developed a nonuniform finite-width
branching-program analysis for continuous regression. Their principal
theorem concerns independent isotropic Gaussian features with independent
uniform additive noise of half-width \(2^{-d/5}\). With at most \(d^2/4\)
bits of memory, success probability at least \(2/3\) for a uniformly
distributed unit signal, and Euclidean accuracy
\(d^{-r}\) in its stated range \(r\le O(d/\log d)\), it gives an
\(\Omega(d\log r)\) sample bound~\cite[Theorem~1]{SSV2019}.
Their projection argument expands high moments into independent copies
and uses successive orthogonalization~\cite[Section~7, Lemma~12]{SSV2019}.
That is a close methodological predecessor of our tuple calculations.
Their lemma treats one noisy interval under a global \(L^2\) density
condition. The estimates here treat exact multirow labels under local
ball or Riesz-potential conditions. Dagan, Kur, and Shamir obtained related
quadratic-space obstructions for approximate null vectors of Gaussian
rows and for empirical residual error in a different equation
model~\cite[Theorems~3 and~10]{DKS2019}. These comparisons concern
distinct statistical targets and observation laws.

\subsection{How the three arguments work}

For the integrated estimate, expand the \(q\)th density moment using
\(q\) points of the measure. The collision of their labels is controlled
by the projection of the \(q-1\) differences from the first point.
Successive coordinates of an orthonormal frame have ellipsoidal densities;
their determinant powers telescope, leaving one nonnegative determinant
power and an explicit \(\sqrt d\) scale. Gram--Schmidt converts the
remaining change of variables into inverse affine heights. A tube about
each preceding affine span is covered by balls, so the local mass
hypothesis integrates these heights in reverse order. This proves
Theorem~\ref{p:frame-moment}.

The first application separates a Gaussian matrix into its positive radial
factor and an independent orthonormal frame. The routing rule may use the
whole radial factor; averaging that dependence produces weights on frame
and projected label. The projected support occupies a \(k\)-ball.
Its volume cancels the dimensional scale in the density norm and returns
the same radius exponent as the incoming local-mass bound. The backward
argument therefore preserves the ambient dimension through every block.
Section~\ref{p:projection} completes this route with local stopping-index
counting and the common full-data bound of Section~\ref{p:geometry-model}.

For positive cap domination, the order is different. Bounded nonnegative
tests on a countable cap dictionary imply a local ball bound for a rescaled
test measure. The normalized instance of the integrated theorem bounds the
test of \(f_w\mu_B\). To turn all these inequalities into a positive
dominating measure, the proof uses a weighted sum of cap densities.
Finitely many caps occur at each scale and the weighted cost makes the
fine-scale \(L^1\) tail vanish. This gives norm compactness. Strict
separation of the closed downward convex set then produces exactly the
bounded tests already controlled. The resulting positive sums propagate
the unnormalized joint laws of signal and state, with a separate reference
probability for each parent cap.

The specified-label argument uses \(q\) vectors anchored at \(z\),
rather than \(q-1\) differences anchored at a sampled point. Their images
under the Gaussian rows have covariance equal to the anchored Gram matrix.
The resulting ball-average estimate is uniform in every fixed offset.
Taking a single lower-limit version and applying Fatou's lemma on each
offset graph preserves that estimate for exact densities. Operator-norm
bins and radial shells then control the Riesz potential of earlier
continuations. This route retains a factor of order
\(1+\log(1/\epsilon)\) from its shell count and a global terminal clock;
its own short-run argument controls both.

The three analytic conclusions and the costs of their regression
applications are compared below. Here \(T\) is the deterministic sample
horizon, and a stopping index is charged only where its value enters the
corresponding argument.

\begin{center}
\small
\begin{tabular}{@{}>{\raggedright\arraybackslash}p{.18\textwidth}
                  >{\raggedright\arraybackslash}p{.37\textwidth}
                  >{\raggedright\arraybackslash}p{.39\textwidth}@{}}
\toprule
Estimate & Analytic guarantee & Regression argument \\
\midrule
Integrated projection & A density moment integrated over the frame and
label space & Backward local-mass propagation; stopping indices counted
within each block \\[3pt]
Positive cap domination & An actual dominating sum of cap measures, with
weighted radius cost & Forward propagation of joint signal--state laws;
one final sum over stopping indices \\[3pt]
Fixed-offset density & One density version with a moment bound at
every fixed affine offset & Backward Riesz-potential propagation; global
terminal tags and a logarithmic shell count \\
\bottomrule
\end{tabular}
\end{center}

Section~\ref{p:geometry-model} supplies the probability normalizations,
finite-state model, Borel-kernel reduction, and common full-data endpoint.
Section~\ref{p:projection} proves the integrated estimates and their
backward application; these two sections suffice for the regression
consequence and the explicit memory tradeoff. Section~\ref{p:cap-section}
uses the normalized projection moment to construct positive dominating
measures and propagate them forward. Section~\ref{p:riesz-section} first
proves its specified-offset estimate, then develops the Riesz recurrence
and its parameter argument. The cap dual constraints test averages on
spherical caps; they are distinct from integration on affine subspheres.
==== END Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/introduction.tex ====

==== BEGIN Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/positive-caps.tex ====
\section{Positive domination by cap measures}\label{p:cap-section}

This section proves the sample bound by propagating the joint law of the
signal and each memory state forward through the stream.  We bound each
such law by a positive sum of uniform measures on spherical caps.  A term
is charged for its mass and for a power of the reciprocal of its radius.
The main step shows that a block of observations increases the total charge
by a controlled factor.  The passage from bounds on test functions to an
actual dominating measure requires compactness in the norm of $L^1$.

We prove Theorem~\ref{p:regression} by a forward argument in the
finite-state experiment of Section~\ref{p:geometry-model}. Use that
section's fixed-seed convention and Borel kernels from
Lemma~\ref{p:borel-kernels}. All bounds below are uniform in the fixed
rules; their scalar probability conclusions are averaged over the shared
seed at the end.

\subsection{The spherical experiment and the projection input}

Write $\sigma$ for uniform probability on $S^{d-1}$, and set
\begin{equation}\label{p:cap-parameters}
 n=d-1,\qquad k=p=\lfloor d/16\rfloor,\qquad
 \alpha=\lambda=\frac n2,\qquad \theta=1-\frac1p.
\end{equation}
We take $d$ sufficiently large that $p\ge2$ and $k,p\ge d/32$.
For $c\in S^{d-1}$ and $0<r\le2$, define
\[
 B(c,r)=\{s\in S^{d-1}:\norm{s-c}\le r\},\qquad
 \mu_{c,r}(ds)=\frac{\1_{B(c,r)}(s)}{\sigma(B(c,r))}\,\sigma(ds).
\]
These are spherical caps and their normalized probability measures.
For an ambient ball in $\R^d$ we use the distinct notation
$D(b,t)=\{u\in\R^d:\norm{u-b}\le t\}$.

Lemma~\ref{p:cap-mass} supplies the two-sided estimate
\begin{equation}\label{p:cap-volume-bound}
 (ar)^n\le\sigma(B(c,r))\le(A_0r)^n,
 \qquad a=(2\pi)^{-1},\quad A_0=1.
\end{equation}
In particular every $\mu_{c,r}$ is well defined.

Let $X$ be a $k\times d$ matrix with independent standard Gaussian
entries and put
\[
 H=(XX^{\mathsf T})^{1/2},\qquad P=H^{-1}X
\]
on the probability-one event that $X$ has full row rank.  Define $P$
arbitrarily on the remaining null set.  We may make this definition
measurable.  On the full-rank event $PP^{\mathsf T}=I_k$ and $X=HP$;
the law of $P$ is
invariant under right orthogonal multiplication.  Let
$v_k$ be the Lebesgue volume of the unit ball of $\R^k$ and let
$m_k(dz)=v_k^{-1}\1_{\{\norm z\le1\}}\,dz$ be uniform probability on
that ball.

The use of independent replicas for high projection moments is related
to the argument of Sharan, Sidford, and Valiant
\cite[Section~7, Lemma~12]{SSV2019}. We use the normalized moment theorem
(Theorem~\ref{p:frame-positive}) with the parameters in
\eqref{p:cap-parameters}. Its inverse-distance margin satisfies
$\lambda-(p-2)-k\ge3d/8$. Below we verify its unit support, mass,
local-growth, independence, and absolute-continuity hypotheses for each
finite positive test measure before invoking its normalized density bound.

\subsection{One block: from bounded tests to a dominating measure}

Fix a parent cap $B=B(c,r)$.  Let $\mathcal W$ be a finite set and let
$K_w(X,Y)\in[0,1]$, for $w\in\mathcal W$, be Borel functions of a
$k\times d$ matrix and a vector in $\R^k$ with $\sum_wK_w\le1$.
Define
\begin{equation}\label{p:cap-reference-probabilities}
 \begin{split}
 f_w(s)&=\E_X K_w(X,Xs),\\
 q_w&=\E_X\int K_w(X,Xc+rHz)\,dm_k(z).
 \end{split}
\end{equation}
The functions $f_w$ are measurable.  The variables $z$ in the second
line are independent of $X$ and are used only to define a reference law.
The kernel still receives the full matrix $X$ and the radial factor $H$
through the displayed label.  In particular, $\sum_wq_w\le1$.

\begin{proposition}[Positive domination after one block]
\label{p:cap-domination}
For each $w\in\mathcal W$, there are countably many caps
$B(c_i,\rho_i)$ with $0<\rho_i\le r$ and coefficients $a_i\ge0$ such
that
\begin{equation}\label{p:cap-domination-bound}
 f_w\mu_{c,r}\le\sum_i a_i\mu_{c_i,\rho_i},
 \qquad
 \sum_i a_i(r/\rho_i)^\alpha\le\exp(Cd)q_w^\theta.
\end{equation}
The first inequality is an inequality of finite positive measures on
$S^{d-1}$: it holds after evaluating both sides on every measurable set.
The constant $C$ is independent of the parent cap and of the kernels.
\end{proposition}

\begin{proof}
We prove a bound for nonnegative tests and then convert it into a
countable positive domination.

\smallskip\noindent
\emph{Cap tests and their local mass.}
Put $\rho_j=r2^{-j}$ and choose a finite $\rho_j/2$-net $N_j$ of the
sphere for every $j\ge0$. Take as a dictionary the parent cap, indexed
by $*$, together with all $B(c',\rho_j)$, $c'\in N_j$. Repetitions may
have separate indices. For this countable index set $I$, write
$B_i=B(c_i,\rho_i)$ and
\[
 \phi_i=\frac{\1_{B(c_i,\rho_i)}}{\sigma(B(c_i,\rho_i))},
 \qquad b_i=(r/\rho_i)^\alpha.
\]
Thus $\phi_*\,d\sigma=\mu_{c,r}$, every $\phi_i$ is a probability
density, $b_*=1$, and the weights at level $j$ are $2^{\alpha j}$.
If $h\in L^\infty(\sigma)$ is nonnegative and satisfies
\begin{equation}\label{p:cap-dual-constraints}
 \int h\phi_i\,d\sigma\le b_i\qquad(i\in I),
\end{equation}
then its integral against any positive dictionary sum is at most that
sum's weighted cost. We will bound $\int h f_w\,d\mu_{c,r}$ for every
such test.

Let $\nu$ be the image of $h\mu_{c,r}$ under $s\mapsto(s-c)/r$.
It has unit-ball support and mass at most one by the parent constraint.
We claim that, for an absolute $D\ge1$,
\begin{equation}\label{p:cap-test-ball-bound}
 \nu(D(b,t))\le D^d t^\lambda
 \qquad(b\in\R^d,\ t>0).
\end{equation}
For $0<t\le1/4$, suppose the ball meets the rescaled cap, and choose a
point $s_0\in B$ whose image lies in it. The corresponding sphere points
are all within $2rt$ of $s_0$. Set
\[
 j=\left\lfloor\log_2\frac1{4t}\right\rfloor,\qquad \rho=\rho_j;
 \qquad 4rt\le\rho<8rt,\quad \rho\le r.
\]
A center in $N_j$ within $\rho/2$ of $s_0$ gives a dictionary cap
containing those points, since $2rt+\rho/2\le\rho$. Its constraint and
the two-sided cap estimate imply
\begin{align*}
 \nu(D(b,t))
 &\le\frac{\sigma(B_i)}{\sigma(B)}\int h\,d\mu_{c_i,\rho_i}\\
 &\le(A_0/a)^n(\rho/r)^{n-\alpha}
 \le(A_0/a)^n(8t)^\lambda.
\end{align*}
An empty intersection has zero mass. For
$t>1/4$, use the mass bound and $1\le4^\lambda t^\lambda$.
These estimates prove \eqref{p:cap-test-ball-bound}.

\smallskip\noindent
\emph{The quantitative test estimate.}
All hypotheses of Theorem~\ref{p:frame-positive} now hold for $\nu$.
Indeed, the test, parent cap, and measure are fixed before the fresh
matrix $X$ is drawn. For every orthonormal $k$-frame $P$, the coordinate
density in Lemma~\ref{p:coordinate-density} gives $P_\#\sigma\ll dz$.
Because $h\mu_{c,r}\ll\sigma$, its projection is also absolutely
continuous, and the affine rescaling
\[
 P((s-c)/r)=(Ps-Pc)/r
\]
gives the same conclusion for $P_\#\nu$. The theorem therefore supplies
a jointly measurable density satisfying, for almost every $X$,
\[
 P_\#\nu=g_Xm_k,\qquad g_X(z)=0\text{ for }\norm z>1,
 \qquad \E_X\int g_X^p\,dm_k\le\exp(C_Ddp).
\]
The density is relative to $dm_k=dz/v_k$ on the unit ball; $D$, and
hence the new constant, is absolute. Since $s=c+ru$ gives
$Xs=Xc+rHPu$, Tonelli's theorem and H\"older's inequality on the product
law of $X$ and $z$ yield
\begin{equation}\label{p:cap-dual-test}
\begin{split}
 \int h f_w\,d\mu_{c,r}
 &=\E_X\int K_w(X,Xc+rHz)g_X(z)\,dm_k(z)\\
 &\le\left(\E_X\int g_X^p\,dm_k\right)^{1/p}
 \left(\E_X\int K_w(X,Xc+rHz)^{p'}\,dm_k\right)^{1/p'}\\
 &\le\exp(Cd)q_w^\theta,\qquad p'=p/(p-1).
\end{split}
\end{equation}
The last line uses $0\le K_w\le1$. Thus every test satisfying
\eqref{p:cap-dual-constraints} obeys \eqref{p:cap-dual-test}.

\smallskip\noindent
\emph{Representation by positive cap sums.}
The geometric estimate is complete; the remaining step uses only the
dictionary and its test bound. If $q_w=0$, the feasible test $h=1$ shows
that $f_w\mu_{c,r}=0$, and the empty sum suffices. Otherwise set
$K=\exp(Cd)q_w^\theta>0$, with the constant from
\eqref{p:cap-dual-test}, and define in real $L^1(\sigma)$
\[
 \mathcal C_K=\left\{\sum_{i\in I}a_i\phi_i:
 a_i\ge0,\ \sum_i a_ib_i\le K\right\}.
\]
Each series converges in $L^1$, since $b_i\ge1$ and
$\norm{\phi_i}_{L^1}=1$. This convex set is norm compact. To see this,
take a sequence and choose a coefficient array for each term. A diagonal
subsequence converges coefficientwise, since $0\le a_i\le K/b_i$.
The limiting array has cost at most $K$ by Fatou's lemma. There are
finitely many indices through every level $J$, and uniformly over all
admissible arrays,
\begin{equation}\label{p:cap-compact-tail}
 \left\|\sum_{j>J}\sum_{i\text{ at level }j}a_i\phi_i\right\|_{L^1}
 =\sum_{j>J}\sum_{i\text{ at level }j}a_i
 \le K2^{-\alpha(J+1)}.
\end{equation}
The same estimate holds for the limiting array. Finite-level convergence
followed by \eqref{p:cap-compact-tail} gives convergence in $L^1$.
This proves sequential compactness, and hence compactness in the metric
space $L^1(\sigma)$
\cite[Section~1.3, Theorem~1.37, p.~29]{SchnaubeltFA2025}.

Its signed downward closure
\[
 \mathcal D_K=\{u\in L^1(\sigma):u\le v\text{ a.e. for some }v\in\mathcal C_K\}
\]
is convex, contains every nonpositive $L^1$ function, and is norm closed.
In fact, if $u_m\to u$ and $u_m\le v_m\in\mathcal C_K$, compactness
provides a subsequence $v_m\to v\in\mathcal C_K$; then
\[
 \norm{(u-v)_+}_{L^1}
 \le\norm{u-u_m}_{L^1}+\norm{v_m-v}_{L^1}\longrightarrow0.
\]
Put $F=f_w\phi_*$. If $F\notin\mathcal D_K$, strict separation of the
closed convex set $\mathcal D_K$ and the compact singleton $\{F\}$
\cite[Section~5.2, Theorem~5.20(b), pp.~98--99]{SchnaubeltFA2025}
gives a continuous real functional $\ell$ with
\[
 \ell(F)>\sup_{u\in\mathcal D_K}\ell(u).
\]
A probability measure is localizable
\cite[Theorem~211L]{FremlinTaxonomy}, so real $L^1$--$L^\infty$
duality~\cite[Theorem~243G(b)]{FremlinFunctionSpaces} represents
$\ell(u)=\int hu\,d\sigma$ for a real $h\in L^\infty(\sigma)$.
The finite supremum forces $h\ge0$: if $h\le-\delta$ on a set $E$
of positive measure, the functions $-t\1_E\in\mathcal D_K$ would make
it infinite. Define
\[
 S_h=\sup_i\frac{\int h\phi_i\,d\sigma}{b_i},\qquad
 0\le S_h\le\norm h_{L^\infty}.
\]
Then
\begin{equation}\label{p:cap-support-functional}
 \sup_{u\in\mathcal D_K}\int hu\,d\sigma=KS_h.
\end{equation}
The cost bound gives the upper inequality, and the single terms
$(K/b_i)\phi_i$ give the reverse inequality by taking the supremum over
$i$. This does not require the supremum to be attained. If $S_h=0$,
the parent term gives $\int h\phi_*\,d\sigma=0$, and $0\le f_w\le1$
implies $\ell(F)=0$, contrary to strict separation. If $S_h>0$, the
function $h/S_h$ satisfies \eqref{p:cap-dual-constraints}, so
\eqref{p:cap-dual-test} again contradicts separation. Therefore
$F\in\mathcal D_K$. An admissible series dominates its density almost
everywhere; integrating gives the asserted measure inequality and cost
bound. Its total mass is at most $K$.
\end{proof}

\subsection{Propagation, bounded stopping, and the accuracy endpoint}

The preceding proposition applies to each cap in a joint-state bound.
The positivity of all measures makes the iteration linear before any
estimate is taken.

\begin{lemma}[Cost of a forward block]\label{p:cap-forward-step}
Let $\mathcal V$ and $\mathcal W$ be finite state sets with
$\abs{\mathcal W}\le2^M$.  For each $v\in\mathcal V$, let
$K_{v,w}$ be block kernels of the type in
\eqref{p:cap-reference-probabilities}, with likelihoods $f_{v,w}$.
Let $\eta_v$ be finite positive measures on the sphere and suppose
\[
 \eta_v\le\sum_i a_{v,i}\mu_{c_{v,i},r_{v,i}},\qquad
 \mathcal P=\sum_{v,i}a_{v,i}(2/r_{v,i})^\alpha<\infty,
\]
where each sum is countable, $a_{v,i}\ge0$, and $0<r_{v,i}\le2$.
Define the outgoing measures by
\[
 \eta'_w(E)=\sum_v\int_E f_{v,w}(s)\,\eta_v(ds).
\]
Then the $\eta'_w$ admit countable positive cap dominations whose total
cost $\mathcal P'$ satisfies
\begin{equation}\label{p:cap-cost-multiplier}
 \mathcal P'\le\mathcal P\exp(Cd)2^{M/p}.
\end{equation}
\end{lemma}

\begin{proof}
Multiplication by a nonnegative measurable function preserves a measure
inequality, as follows first for simple functions and then by monotone
convergence.  Summing over incoming states and cap terms therefore gives
\[
 \eta'_w\le\sum_{v,i}a_{v,i}f_{v,w}\mu_{c_{v,i},r_{v,i}}.
\]
Apply Proposition~\ref{p:cap-domination} separately to every term.
For a fixed incoming cap, write $q_{v,i,w}$ for its reference
probabilities.  They depend on that cap as well as on the starting state,
and satisfy $\sum_wq_{v,i,w}\le1$.  H\"older's inequality for the finite
sum gives
\[
 \sum_wq_{v,i,w}^{\theta}
 \le\abs{\mathcal W}^{1/p}\left(\sum_wq_{v,i,w}\right)^\theta
 \le2^{M/p}.
\]
If the outgoing terms for this parent have coefficients $\beta_j$ and radii
$\rho_j$, their contribution to the global cost is bounded by
\begin{align*}
 \sum_j a_{v,i}\beta_j(2/\rho_j)^\alpha
 &=a_{v,i}(2/r_{v,i})^\alpha
       \sum_j \beta_j(r_{v,i}/\rho_j)^\alpha\\
 &\le a_{v,i}(2/r_{v,i})^\alpha\exp(Cd)q_{v,i,w}^\theta.
\end{align*}
Sum first over $w$ and then over the countably many incoming terms to
obtain \eqref{p:cap-cost-multiplier}.  Tonelli's theorem applies
throughout because every summand is nonnegative.

At each of finitely many block boundaries there are only countably many
state--cap terms.  Choosing a dominating sum for each produces a
deterministic proof representation, with another countable sum at the
next boundary.  There is no choice indexed by the random signal or by
the fresh matrix.  The state measures here remain unnormalized joint
measures; the argument never divides them by their total masses.
\end{proof}

\begin{lemma}[Terminal success under a cap]\label{p:cap-terminal}
Let $Q$ be any probability law on unit-vector outputs, independent of
the signal, and put
$h_Q(s)=Q\{z:\arccos\inner{z}{s}\le\epsilon\}$ for
$0<\epsilon\le1/10$.  For every cap $B(c,r)$,
\begin{equation}\label{p:cap-terminal-bound}
 \int h_Q\,d\mu_{c,r}\le\exp(Cd)(\epsilon/r)^\alpha.
\end{equation}
\end{lemma}

\begin{proof}
For a fixed unit output $z$, write $\vartheta=\arccos\inner{z}{s}$.
Angular success implies $\norm{s-z}=2\sin(\vartheta/2)\le\epsilon$.  If
$\epsilon<r$, Lemma~\ref{p:cap-mass} bounds its probability under
$\mu_{c,r}$ by
\[
 \frac{\sigma(B(z,\epsilon))}{\sigma(B(c,r))}
 \le(A_0/a)^n(\epsilon/r)^n
 \le\exp(Cd)(\epsilon/r)^\alpha.
\]
If $\epsilon\ge r$, use probability at most one and
$(\epsilon/r)^\alpha\ge1$.  Integration over $Q$ proves the result.
\end{proof}

\begin{proposition}[A fixed stopping index]\label{p:cap-fixed-stop}
For all sufficiently large $d$, let a learner obey the observation and
information restrictions in Section~\ref{p:geometry-model}, with
$0<\epsilon\le1/10$, any nonnegative integer $M$ bits of state, and horizon $T$,
and let $\mathsf T$ be its stopping index.  For every fixed integer
$0\le t\le T$,
\begin{equation}\label{p:cap-fixed-stop-explicit}
 \Prob\{\mathsf T=t\text{ and }\arccos\inner{\widehat S}{S}\le\epsilon\}
 \le\exp(Cd)(\epsilon/2)^\alpha
       \left[\exp(Cd)2^{M/p}\right]^{\lceil t/k\rceil}.
\end{equation}
In particular, for a sequence $M(d)=o(d^2)$ the right side is eventually
at most
\begin{equation}\label{p:cap-fixed-stop-asymptotic}
 \exp\bigl(Cd(1+\lceil t/k\rceil)\bigr)(\epsilon/2)^\alpha,
\end{equation}
with an absolute $C$ and a dimension threshold that may depend on the
memory sequence.
\end{proposition}

\begin{proof}
Fix $t>0$ throughout the argument and split its first $t$ indices into
$b=\lceil t/k\rceil$ consecutive blocks of length at most $k$.  At a
prefinal boundary retain only paths that have not stopped and are eligible
to continue.  In the final block retain exactly the paths stopping at
$t$, with their terminal state.  For a fixed starting state and a supplied
block of pairs, integrating the internal randomness gives the probability
of each retained ending state.  These are Borel kernels with sum at most
one, since all omitted paths are discarded.  A shorter block is padded
by independent unused Gaussian rows, which the kernels ignore.  Its
likelihood for a signal $s$ is therefore $f_{v,w}(s)$ of
\eqref{p:cap-reference-probabilities}. Conditional on the fixed seed,
the fresh Gaussian feature rows in the block are jointly independent of the signal and entering state,
indeed of the signal, initialization, past rows, and past coins. Given the
signal, the past affects this likelihood only through the starting state
and the fixed index.

At any counted boundary, let $\eta_v(E)$ be the probability that
$S\in E$ and the path is counted in state $v$.  These are unnormalized
joint measures and their outgoing laws have exactly the formula in
Lemma~\ref{p:cap-forward-step}. Initially, $B(c,2)=S^{d-1}$ and
$\mu_{c,2}=\sigma$. Write $V_0$ for the initial finite state. For the
fixed shared seed $\xi$, joint initialization
independence gives
\[
 \eta_v^\xi(E)=\pi_\xi(v)\sigma(E),
 \qquad \pi_\xi(v)=\Prob\{V_0=v\mid\xi\},\qquad
 \sum_v\pi_\xi(v)=1.
\]
Thus the initial total cost is one before any discarded paths are removed,
and at most one afterward.
After $b$ applications of that lemma, the counted terminal measures
admit positive cap dominations of total cost at most
$[\exp(Cd)2^{M/p}]^b$.

At each fixed terminal state and index $t$, the output is drawn from a
fixed law using fresh randomness. Apply Lemma~\ref{p:cap-terminal} to each
term of its dominating cap sum.  A term of coefficient $a$ and
radius $r$ contributes at most
$\exp(Cd)(\epsilon/2)^\alpha a(2/r)^\alpha$.
Summing proves the conditional version of
\eqref{p:cap-fixed-stop-explicit}. At $t=0$, use the
initial domination and the same terminal estimate directly.  The index
has been fixed throughout, so only the at most $2^M$ states at each
ending boundary were counted.  No additional state is charged for the
value of $t$.

The countable dominating sums are chosen only after fixing the shared
seed. The bound is uniform in that seed, so the common convention of
Section~\ref{p:geometry-model} allows us to average the original
conditional success probabilities. No measurable choice of cap
decompositions across shared seeds is required.
Finally, for $M(d)=o(d^2)$ we eventually have $M(d)\le d^2$.  Since
$p\ge d/32$, the logarithm of the extra factor $2^{M/p}$ is then at
most $32(\log2)d$.  Absorbing it into the absolute exponential constant
proves \eqref{p:cap-fixed-stop-asymptotic}.
\end{proof}

We now sum the fixed-index estimate over all possible stopping times
and use the common full-data bound to absorb the resulting lower-order
terms.

\begin{proof}[Proof of Theorem~\ref{p:regression} by positive cap domination]
Put $L=\log(1/\epsilon)$.

For the given sequence $M(d)=o(d^2)$, use
\eqref{p:cap-fixed-stop-asymptotic} in all sufficiently large dimensions.
The stopping events are disjoint. Since $k\ge d/32$, $\alpha\ge d/3$,
and $\lceil t/k\rceil\le t/k+1$, summing over $0\le t\le T$ yields
\begin{equation}\label{p:cap-total-success}
 \Prob\{\text{success}\}
 \le(T+1)\exp(C_1d+C_2T-dL/3).
\end{equation}
Here $(\epsilon/2)^\alpha\le\exp(-dL/3)$, and $C_1,C_2$ are absolute.
If success is at least $2/3$, taking logarithms gives
\[
 \frac{dL}{3}
 \le C_1d+C_2T+\log(T+1)+\log(3/2)
 \le C_1d+(C_2+1)T+\log(3/2),
\]
since $\log(T+1)\le T$ for every $T\ge0$.
Lemma~\ref{p:haar-linear} also gives $T>d/8$, and therefore $T\ge1$.
Consequently
\[
 dL\le3(8C_1+C_2+2)T.
\]
This proves the claimed bound with an absolute constant, uniformly over
the full accuracy range. Only the dimension at which the memory factor
is absorbed may depend on the sequence $M(d)$.
\end{proof}
==== END Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/positive-caps.tex ====

==== BEGIN Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/projection.tex ====
\section{Integrated moments of orthonormal projections}
\label{p:projection}

This section answers the first question: how does a bound on the mass of
every Euclidean ball control the density after a random orthonormal
projection, when the label is integrated over its whole space? The proof
has two geometric parts. A frame calculation expresses the cost of
projecting several points through their affine Gram determinant. A covering
argument then integrates that determinant using the ball-mass bound.
We retain the dimensional factor in the density norm because it cancels
against the projected support volume in the regression application.

For integers \(1\le k<d\), let \(\mathcal V_{d,k}\) be the space of
\(k\)-by-\(d\) matrices \(P\) satisfying \(PP^{\mathsf T}=I_k\).
Write \(\vartheta_{d,k}\) for the law of the first \(k\) rows of a uniform
orthogonal matrix. One direct construction fixes the probability
normalization. For a square standard Gaussian matrix \(G\), which is
invertible almost surely, put
\(O=G(G^{\mathsf T}G)^{-1/2}\). Then \(O\) is orthogonal. For fixed
orthogonal \(U,V\), the same formula applied to \(UGV\) gives \(UOV\);
the Gaussian law is unchanged by both multiplications. Thus the law of
\(O\) is a probability invariant on both sides, the Haar probability
used here. Its columns can equivalently be sampled successively uniformly
in the orthogonal complements of the preceding columns. To verify the
equivalence, average either invariant frame law under an independent \(O\);
transitivity makes the averaged law independent of the initial frame.
As in Section~\ref{p:geometry-model}, \(v_k\) is the unit-ball volume.

\subsection{The projected frame and its determinant}

We first record the classical truncated Haar density, together with the
affine-height form used below. Jiang~\cite[Lemma~2.5]{Jiang2006} records
this formula and refers to earlier formulations by Diaconis, Eaton, and
Lauritzen and by Eaton. We include its derivation to retain the
dimensional normalization.

\begin{lemma}[Projected frame density]\label{p:frame-density}
Let \(k,m\ge1\) and \(k+m+1\le d\). Fix a \(d\)-by-\(m\) matrix \(E\)
with orthonormal columns, and draw \(P\sim\vartheta_{d,k}\). The
\(k\)-by-\(m\) matrix \(PE\) has Lebesgue density
\begin{equation}\label{p:frame-density-exact}
 \left(\prod_{j=0}^{m-1}
 \frac{\Gamma((d-j)/2)}
 {\pi^{k/2}\Gamma((d-j-k)/2)}\right)
 \det(I_k-ZZ^{\mathsf T})^{(d-k-m-1)/2}
 \1_{\{I_k-ZZ^{\mathsf T}>0\}}.
\end{equation}
Here \(>0\) means positive definite. In particular, this density is
bounded by \((C\sqrt d)^{km}\).

If \(x_1,\ldots,x_{m+1}\in\R^d\) are affinely independent and
\[
 \delta_i=\dist\bigl(x_i,\aff(x_1,\ldots,x_{i-1})\bigr),
 \qquad 2\le i\le m+1,
\]
then the joint Lebesgue density of the columns
\(P(x_i-x_1)\), \(2\le i\le m+1\), is bounded by
\begin{equation}\label{p:frame-difference-density}
 (C\sqrt d)^{km}\prod_{i=2}^{m+1}\delta_i^{-k}.
\end{equation}
\end{lemma}

\begin{proof}
Right rotational invariance allows us to replace the fixed columns of
\(E\) by an independent uniform orthonormal frame. Conditional on \(P\),
its projection has the same law as the first \(k\) coordinates of that
frame. Sample the full columns successively and let \(Z_j\) be the matrix
of the first \(k\) coordinates of its first \(j\) columns. Set
\[
 S_j=I_k-Z_jZ_j^{\mathsf T},\qquad S_0=I_k.
\]
Given the preceding full columns, the next column is uniform on the unit
sphere in their \(d-j\)-dimensional orthogonal complement. The coordinate
map from that complement to the first \(k\) coordinates has row Gram
matrix \(S_j\). When \(S_j>0\), multiplication by \(S_j^{-1/2}\) makes
its rows orthonormal. Lemma~\ref{p:coordinate-density} and a linear change
of variables therefore give the next projected column \(z\) conditional
density
\[
 c(d-j,k)(\det S_j)^{-1/2}
 (1-z^{\mathsf T}S_j^{-1}z)^{(d-j-k-2)/2}
\]
on \(z^{\mathsf T}S_j^{-1}z<1\). This expression depends only on \(Z_j\),
so it is also the conditional density given those projected columns.
The strict inequality implies \(S_{j+1}=S_j-zz^{\mathsf T}>0\)
almost surely. The determinant identity
\[
 \det S_{j+1}=\det S_j(1-z^{\mathsf T}S_j^{-1}z)
\]
shows that multiplication of the \(m\) conditional densities cancels
every intermediate determinant. The remaining factor is
\(\det S_m^{(d-k-m-1)/2}\), proving \eqref{p:frame-density-exact}.
Its exponent is nonnegative and \(0<\det S_m\le1\).

The normalizing constants have the stated scale. For a unit-scale gamma
variable \(G\) of shape \(a=(d-j-k)/2>0\), Cauchy--Schwarz and the gamma
recurrence give
\[
 \frac{\Gamma((d-j)/2)}{\Gamma((d-j-k)/2)}
 =\E G^{k/2}
 \le(\E G^k)^{1/2}
 =\left(\prod_{i=0}^{k-1}(a+i)\right)^{1/2}
 \le d^{k/2}.
\]
Together with the factor \(\pi^{-k/2}\), this bounds each \(c(d-j,k)\)
by \((C\sqrt d)^k\).

For the last assertion, Gram--Schmidt writes
\([x_2-x_1,\ldots,x_{m+1}-x_1]=ER\), where \(E\) has orthonormal
columns and \(R\) is triangular with
\(\abs{\det R}=\prod_{i=2}^{m+1}\delta_i\). Right multiplication by \(R\)
on \(k\)-by-\(m\) matrices has Jacobian \(\abs{\det R}^k\), one factor
for each row. Applying this change of variables to the preceding density
proves \eqref{p:frame-difference-density}.
\end{proof}

The product of the affine heights in \eqref{p:frame-difference-density}
is \(m!\) times the \(m\)-dimensional volume of the simplex spanned by
the points. Related simplex-volume factors occur in Drury's affine-plane
Jacobian~\cite[Lemma~1, pp.~497--498]{Drury1984}. Here the exponent and
normalization come from the displayed \(k\)-row change of variables.

\subsection{From local mass to an exact density norm}

The local growth hypothesis below is of Frostman type, and
inverse-distance averaging is a classical projection method; compare
Mattila~\cite[Lemma~5.1, p.~236, and Theorem~5.4, p.~237]{Mattila1975}.
We prove the quantitative affine-tube and growing-order moment bounds
needed here.

\begin{lemma}[Affine inverse distances]\label{p:affine-inverse}
Let \(0<\beta\le d\), \(K\ge0\), and \(R>0\). Let \(\nu\) be a finite
positive Borel measure supported in \(B(z,R)\subset\R^d\) such that
\begin{equation}\label{p:all-ball-mass}
 \nu(B(b,t))\le Kt^\beta
 \qquad(b\in\R^d,\ t>0).
\end{equation}
If \(F\) is an affine \(j\)-plane, \(k\ge1\) is an integer, and
\(\beta-j-k\ge1\), then \(\nu(F)=0\) and
\begin{equation}\label{p:affine-inverse-bound}
 \int\dist(x,F)^{-k}\,d\nu(x)\le C^d K R^{\beta-k},
\end{equation}
provided \(j,k\le d\).
\end{lemma}

\begin{proof}
For \(0<t\le R\), the projection of \(B(z,R)\) onto \(F\) is contained
in a \(j\)-ball of radius \(R\). A maximal \(t\)-separated subset is a
\(t\)-net with at most \((3R/t)^j\) points, by packing disjoint
\(j\)-balls of radius \(t/2\). For \(j=0\), one point suffices.
The corresponding ambient balls of radius \(2t\) cover the points of
\(B(z,R)\) within distance \(t\) of \(F\). Thus
\begin{equation}\label{p:affine-tube}
 \nu\{\dist(x,F)\le t\}\le 3^j2^\beta K R^j t^{\beta-j}.
\end{equation}
Because \(\beta-j>0\), continuity from above as \(t\downarrow0\)
gives \(\nu(F)=0\). Distances greater than \(R\) contribute at most
\(R^{-k}\nu(B(z,R))\le KR^{\beta-k}\). On the shell
\(2^{-h-1}R<\dist(x,F)\le2^{-h}R\), \eqref{p:affine-tube} gives a
contribution at most
\[
 3^j2^{\beta+k}KR^{\beta-k}\,2^{-h(\beta-j-k)}.
\]
The sum over \(h\ge0\) is at most twice its first term. Since
\(\beta,j,k\le d\), the resulting factor is bounded by \(C^d\).
\end{proof}

\begin{theorem}[Integrated orthonormal-projection moment]
\label{p:frame-moment}
Let \(d,k,q\) be integers and \(\beta\) a real number with
\(k\ge1\), \(q\ge2\), and
\begin{equation}\label{p:frame-margins}
 k+q\le d,\qquad 0<\beta\le d,\qquad
 \beta-k-(q-2)\ge1.
\end{equation}
Let \(\nu\) be a finite positive Borel measure supported in
\(B(z,R)\), \(R>0\), satisfying \eqref{p:all-ball-mass} for some
\(K\ge0\). Assume that \(P_\#\nu\) is absolutely continuous with
respect to Lebesgue measure for \(\vartheta_{d,k}\)-almost every \(P\).
There is a jointly measurable version \(g(P,u)\) of its density such that
\begin{equation}\label{p:frame-moment-bound}
 \left(\int_{\mathcal V_{d,k}}\int_{\R^k}g(P,u)^q\,du\,
 d\vartheta_{d,k}(P)\right)^{1/q}
 \le C^d(C\sqrt d)^{k(1-1/q)}
 K R^{\beta-k(1-1/q)}.
\end{equation}
For every \(P\), this version vanishes when \(\norm{u-Pz}>R\).
\end{theorem}

\begin{proof}
When \(K=0\), the measure is zero and the assertion is immediate.
For \(K>0\), let \(v_k\) be the unit-ball volume and define
\[
 g_\delta(P,u)=\frac{\nu\{x:\norm{Px-u}\le\delta\}}{v_k\delta^k}.
\]
These are jointly measurable nonnegative functions. Expanding their
\(q\)th powers and using Tonelli's theorem expresses the integrated
moment through \(q\) points \(x_1,\ldots,x_q\) drawn from \(\nu\).
The intersection of the \(q\) label balls of radius \(\delta\) has
volume at most \(v_k\delta^k\); it is empty unless
\(\norm{P(x_i-x_1)}\le2\delta\) for \(i\ge2\).

Put
\(\delta_i=\dist(x_i,\aff(x_1,\ldots,x_{i-1}))\).
Lemma~\ref{p:affine-inverse} shows that every affine plane encountered
here has zero \(\nu\)-mass: its dimension is at most \(q-2\), so the
last condition in \eqref{p:frame-margins} applies. Consequently the tuple
is affinely independent for \(\nu^{\otimes q}\)-almost every choice.
For such a tuple, Lemma~\ref{p:frame-density} applies with \(m=q-1\);
the condition \(k+q\le d\) is exactly its determinant condition. The
probability of all \(q-1\) inequalities is bounded by
\[
 (C\sqrt d)^{k(q-1)}
 \prod_{i=2}^q\delta_i^{-k}
 \bigl[v_k(2\delta)^k\bigr]^{q-1}.
\]
The label-ball volumes cancel those in the definition of \(g_\delta\).
Absorbing \(2^{k(q-1)}\) in \(C\), we obtain
\begin{equation}\label{p:frame-before-integration}
 \int\!\!\int g_\delta^q\,du\,d\vartheta_{d,k}
 \le (C\sqrt d)^{k(q-1)}
 \int\prod_{i=2}^q\delta_i^{-k}\,d\nu^{\otimes q}.
\end{equation}
The degenerate tuples form a null set and can be assigned an infinite
upper bound in this nonnegative integral.

Integrate first in \(x_q\), then in \(x_{q-1},\ldots,x_2\).
At each step Lemma~\ref{p:affine-inverse} bounds the current factor by
\(C^d K R^{\beta-k}\). The remaining first-point mass is at most
\(KR^\beta\). Hence the last integral in
\eqref{p:frame-before-integration} is at most
\[
 C^{d(q-1)}K^qR^{q\beta-k(q-1)}.
\]
This proves the \(q\)th power of \eqref{p:frame-moment-bound} uniformly
in \(\delta\).

Define \(g(P,u)=\liminf_{j\to\infty}g_{1/j}(P,u)\). The assumed absolute
continuity and Lebesgue differentiation
\cite[Theorem~1.6.19, pp.~146--147]{TaoMeasure2011} imply that, for almost every
\(P\), this is a density of \(P_\#\nu\) for almost every \(u\).
Fatou's lemma on the product space
\cite[Corollary~1.4.47, p.~110]{TaoMeasure2011} gives
\eqref{p:frame-moment-bound}. If \(\norm{u-Pz}>R\), sufficiently small
label balls miss \(P(B(z,R))\), since \(P\) is a contraction; the
displayed version is then zero. This limiting calculation concerns the
exact projected measure. It introduces no noise into an observation.
\end{proof}

We now spell out the two parameter choices that will be used. Their
normalizations differ, even though their frame calculation is shared.

\begin{corollary}[All-radii projection of spherical local mass]
\label{p:frame-n30}
For sufficiently large \(d\), put
\[
 n=d-1,\qquad k=q=\lfloor d/4\rfloor,\qquad \beta=n-q.
\]
Let \(0\le f\le1\) be Borel on \(S^{d-1}\), and suppose for \(K\ge0\) that
\[
 \int_{B(b,t)}f\,d\sigma\le Kt^\beta
 \qquad(b\in\R^d,\ t>0).
\]
For \(z\in\R^d\), \(R>0\), and \(E=B(z,R)\), the projection of \(\1_E f\sigma\) by
\(P\sim\vartheta_{d,k}\) has a jointly measurable Lebesgue density
\(g(P,u)\) satisfying
\begin{equation}\label{p:frame-n30-bound}
 \norm g_{L^q(\vartheta_{d,k}\,du)}
 \le C^d(C\sqrt d)^{k(1-1/q)}
 K R^{\beta-k(1-1/q)}.
\end{equation}
\end{corollary}

\begin{proof}
Restriction preserves the stated all-ball bound. For every \(P\), the
projection of \(\sigma\) is absolutely continuous by
Lemma~\ref{p:coordinate-density}, so the same holds for the restricted
weighted measure. The exact margins are
\[
 k+q=2\lfloor d/4\rfloor\le d,\qquad
 \beta-k-(q-2)=d+1-3\lfloor d/4\rfloor\ge d/4+1.
\]
Thus Theorem~\ref{p:frame-moment} applies. This also records the
nonnegative frame-determinant exponent
\((d-k-q)/2=(d-2\lfloor d/4\rfloor)/2\).
\end{proof}

\begin{theorem}[Normalized moment for unit-ball measures]
\label{p:frame-positive}
For sufficiently large \(d\), put
\[
 k=p=\lfloor d/16\rfloor,\qquad \lambda=(d-1)/2.
\]
Let \(X\) be a \(k\)-by-\(d\) standard Gaussian matrix and define
\[
 H=(XX^{\mathsf T})^{1/2},\qquad P=H^{-1}X
\]
on its probability-one full-row-rank event, and set \(P\) to a fixed frame
on the null complement. Let \(m_k\) be uniform
probability on the unit ball of \(\R^k\). Suppose \(\nu\) is a finite
positive Borel measure fixed independently of \(X\), of mass at most one, supported in the unit ball
of \(\R^d\), such that for a fixed \(D>0\),
\[
 \nu(B(b,t))\le D^d t^\lambda
 \qquad(b\in\R^d,\ t>0).
\]
Assume \(P_\#\nu\) is absolutely continuous for almost every \(X\).
There is a jointly measurable nonnegative \(g_X(z)\) such that, for almost
every \(X\), \(P_\#\nu(dz)=g_X(z)\,dz/v_k\). This version vanishes when
\(\norm z>1\) and satisfies
\begin{equation}\label{p:frame-positive-bound}
 \E_X\int g_X(z)^p\,dm_k(z)\le \exp(C_Ddp).
\end{equation}
\end{theorem}

\begin{proof}
Right rotational invariance of \(X\) makes \(P\) have law
\(\vartheta_{d,k}\); the independence assertion about \(P,H\) used later
is proved below. The exact determinant and inverse-distance margins are
\[
 k+p=2\lfloor d/16\rfloor\le d,\qquad
 \lambda-k-(p-2)
 =\frac{d-1}{2}-2\lfloor d/16\rfloor+2
 \ge\frac{3d}{8}+\frac32.
\]
Apply Theorem~\ref{p:frame-moment} with \(q=p\), \(\beta=\lambda\),
\(K=D^d\), and \(R=1\). If \(\ell(P,z)\) is its Lebesgue density,
then \(g_X(z)=v_k\ell(P,z)\) is the required normalized density. Moreover
\[
 \left(\E_X\int g_X^p\,dm_k\right)^{1/p}
 =v_k^{1-1/p}\norm\ell_{L^p(\vartheta_{d,k}\,dz)}.
\]
Use the unit-ball volume estimate \eqref{p:unit-ball-volume}.
Since \(k\ge d/32\) for sufficiently large \(d\),
\[
 v_k^{1-1/p}(C\sqrt d)^{k(1-1/p)}\le C^d.
\]
Theorem~\ref{p:frame-moment} now bounds the normalized \(L^p\) norm by
\(\exp(C_Dd)\), proving \eqref{p:frame-positive-bound}. The density
version and its support are inherited from that theorem. The mass-at-most-one
and absolute-continuity hypotheses have been retained explicitly.
\end{proof}

\subsection{Radial averaging and dimension-preserving propagation}

We next apply the all-radii estimate to the actual Gaussian data. A learner
may use both the row directions and their lengths and correlations. The
following factorization retains all of that radial information before
averaging it into the routing weights.

\begin{lemma}[Gaussian radial factor and frame]\label{p:radial-factor}
Let \(X\) be a \(k\)-by-\(d\) standard Gaussian matrix with \(k<d\).
Almost surely,
\[
 X=HP,\qquad H=(XX^{\mathsf T})^{1/2},\qquad P=H^{-1}X.
\]
The frame \(P\) has law \(\vartheta_{d,k}\) and is independent of \(H\).
\end{lemma}

\begin{proof}
Full row rank holds almost surely because the rank-deficient matrices are
the zero set of nonzero minors and the Gaussian law has a density. Right
multiplication of \(X\) by a fixed orthogonal matrix leaves its law
unchanged, fixes \(H\), and right-rotates \(P\). Let \(O\) be an independent
uniform orthogonal matrix. For bounded measurable \(\phi,\psi\), invariance
and averaging give
\[
 \E[\phi(H)\psi(P)]
 =\E\!\left[\phi(H)\int\psi(PO)\,d\mu(O)\right],
\]
where \(\mu\) is uniform orthogonal probability. The inner integral is
independent of \(P\): the right action on \(\mathcal V_{d,k}\) is
transitive, and \(\mu\) is invariant. Its value is
\(\int\psi\,d\vartheta_{d,k}\). This factorizes the expectation for all
bounded measurable tests, which proves the stated law and independence.
\end{proof}

\begin{proposition}[One-block all-radii propagation]\label{p:haar-block}
For sufficiently large \(d\), use \(k=q=\lfloor d/4\rfloor\) and
\(\beta=d-1-q\).
Let \(f_1,\ldots,f_N:S^{d-1}\to[0,1]\) be Borel functions satisfying
\[
 \int_{B(b,t)}f_w\,d\sigma\le Kt^\beta
 \qquad(b\in\R^d,\ t>0,\ 1\le w\le N).
\]
Let \(Q_w(X,y)\) be nonnegative Borel functions on
\(\R^{k\times d}\times\R^k\) with \(\sum_wQ_w\le1\), and define
\[
 f_{\mathrm{in}}(s)=\E_X\sum_{w=1}^N Q_w(X,Xs)f_w(s).
\]
Then
\begin{equation}\label{p:haar-block-bound}
 \int_{B(z,R)}f_{\mathrm{in}}\,d\sigma
 \le C^dN^{1/q}K R^\beta
 \qquad(z\in\R^d,\ R>0).
\end{equation}
\end{proposition}

\begin{proof}
Write \(X=HP\) as in Lemma~\ref{p:radial-factor} and average the full
radial dependence of the routing rule:
\[
 \tau_w(P,u)=\E_H Q_w(HP,Hu).
\]
These are measurable nonnegative weights with \(\sum_w\tau_w\le1\).
Independence gives the exact identity
\begin{equation}\label{p:haar-routing}
 f_{\mathrm{in}}(s)=
 \int\sum_w\tau_w(P,Ps)f_w(s)\,d\vartheta_{d,k}(P).
\end{equation}
Fix \(E=B(z,R)\), and let \(g_w(P,u)\) be the exact density in
Corollary~\ref{p:frame-n30} for \(\1_Ef_w\sigma\). After integrating
\eqref{p:haar-routing} over \(E\), pushforward integration yields
\(\int\!\int\sum_w\tau_w g_w\,du\,d\vartheta_{d,k}\).
Each \(g_w\) is supported in \(\norm{u-Pz}\le R\).
On this domain the measure with density \(\tau_w\), relative to frame
probability, label Lebesgue measure, and counting measure in \(w\), has
total mass at most \(v_kR^k\). Hölder's inequality therefore gives
\[
 \int_E f_{\mathrm{in}}\,d\sigma
 \le (v_kR^k)^{1-1/q}
 \left(\sum_w\int\!\!\int\tau_w g_w^q\,du\,d\vartheta_{d,k}\right)^{1/q}
 \le (v_kR^k)^{1-1/q}N^{1/q}\max_w\norm{g_w}_{L^q}.
\]
Substitute \eqref{p:frame-n30-bound}. The radius powers add exactly to
\(\beta\). Also \(k\ge d/8\), so \eqref{p:unit-ball-volume} gives
\[
 v_k^{1-1/q}(C\sqrt d)^{k(1-1/q)}\le C_0^d.
\]
This proves \eqref{p:haar-block-bound}. The original \(Q_w\) could use
all entries of \(H\); only after that dependence was retained did we
average it into \(\tau_w\).
\end{proof}

\subsection{Backward propagation of continuation success}

We now apply Proposition~\ref{p:haar-block} to the success probability of
a fresh continuation from each state. Its local-mass exponent survives
every block, and the resulting finite-dimensional estimate retains the
full dependence on \(M\).

\begin{proposition}[Success bound from orthonormal projections]
\label{p:haar-success-proposition}
There are absolute constants \(C\ge1\) and \(d_0\) such that the
following holds for every integer \(d\ge d_0\), every nonnegative integer
\(M\), every \(0<\epsilon\le1/10\), and every learner of deterministic
finite horizon \(T\) in Section~\ref{p:geometry-model}. Put
\[
 k=q=\lfloor d/4\rfloor,\qquad
 b=\lceil T/k\rceil,\qquad N_*=(k+2)2^M.
\]
Then
\begin{equation}\label{p:haar-success}
 \Prob\{\text{success}\}\le
 C^d\epsilon^q\bigl[C^dN_*^{1/q}\bigr]^b.
\end{equation}
The constant and dimension threshold are independent of \(M,\epsilon,T\)
and the learner's rules.
\end{proposition}

\begin{proof}
Use the fixed-seed and Borel-kernel convention of
Section~\ref{p:geometry-model}, and set \(n=d-1\) and \(\beta=n-q\).
For each terminal state and stopping index, let \(h(s)\) be the success
probability of its signal-independent output law. The cap estimates of
Lemma~\ref{p:cap-mass} give
\[
 \int_{B(z,R)}h\,d\sigma
 \le C^d\min\{R^n,\epsilon^n\}
 \le C^d\epsilon^q R^\beta
 \qquad(z\in\R^d,\ R>0).
\]
The last inequality follows from \(R\le\epsilon\) or
\(R\ge\epsilon\), respectively. Thus the all-radii coefficient for
every terminal function is at most \(K_0=C^d\epsilon^q\).

Divide the horizon into \(b\) blocks of \(k\) rows, padding the last
block with independent rows ignored by its rules. Starting at a specified
state and boundary index, define its continuation by a fresh future
execution. This definition does not condition on that state being reached.
The continuation functions are Borel and take values in \([0,1]\) by
Lemma~\ref{p:borel-kernels}.

Within a block, a destination is either a continuing state at the next
boundary or a terminal state tagged by its local stopping index. The
possible local stopping indices are \(0,1,\ldots,k\), including an
immediate stop. There are at most \((k+1)2^M\) terminal destinations and
\(2^M\) continuing destinations, hence at most \(N_*\) in total. The
global stopping index is determined by the fixed block start and this
local index, so the terminal output retains its full allowed dependence
on time.

Finite composition of the transition kernels produces Borel routing
probabilities \(Q_w(X,y)\) for these destinations, with
\(\sum_wQ_w\le1\). Their continuation functions \(f_w\) use only
future independent rows and coins; terminal destinations use the functions
\(h\) above. The incoming continuation therefore has precisely the form
\[
 f_{\mathrm{in}}(s)=\E_X\sum_wQ_w(X,Xs)f_w(s)
\]
from Proposition~\ref{p:haar-block}. The Gaussian block is fresh:
conditional on the fixed shared seed, its rows are jointly independent of
the signal and entering state, which depends only on initialization,
past pairs, and past coins.

Backward induction through the blocks multiplies the all-radii
coefficient by at most \(C^dN_*^{1/q}\) per block. This factor is at
least one, so the coefficient also bounds any earlier terminal option.
Integrate the initial continuation over \(B(0,1)\) and average over the
conditional initial-state law, which is independent of the signal and
rows. Conditional success is at most the right side of
\eqref{p:haar-success}. The bound is uniform in the fixed rules, so the
shared-seed convention gives the same bound for the original learner.
When \(T=0\), the terminal bound supplies the conclusion directly.
\end{proof}

\begin{proof}[Proof of Corollary~\ref{p:finite-memory-tradeoff} and first
proof of Theorem~\ref{p:regression}]
Put \(L=\log(1/\epsilon)\). Choose an absolute dimension threshold so
that Proposition~\ref{p:haar-success-proposition} applies and
\(k=q\ge d/8\). If success is at least \(2/3\),
\eqref{p:haar-success} implies
\[
 qL\le (b+1)d\log C
       +\frac bq\bigl(M\log2+\log(k+2)\bigr)
       +\log(3/2).
\]
Since \(b\le8T/d+1\) and \(\log(k+2)/q\) is bounded by an absolute
constant, this gives an absolute \(C_1\) such that
\begin{equation}\label{p:haar-memory-arithmetic}
 dL\le C_1(T+d)\left(1+\frac M{d^2}\right).
\end{equation}
No bound on \(M\) was used. Lemma~\ref{p:haar-linear} forces
\(T>d/8\), and hence \(T+d<9T\). Substitution into
\eqref{p:haar-memory-arithmetic} proves
Corollary~\ref{p:finite-memory-tradeoff} with an absolute constant.

Finally, if \(M(d)=o(d^2)\), then \(1+M(d)/d^2\le2\) for all
sufficiently large \(d\). The corollary proves
Theorem~\ref{p:regression}, with an absolute lower-bound constant and a
dimension threshold that may depend on the memory sequence. This proof
is uniform over the accuracy sequence and uses only within-block stopping
indices.
\end{proof}
==== END Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/projection.tex ====

==== BEGIN Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/riesz.tex ====
\section{Riesz estimates at fixed affine offsets}
\label{p:riesz-section}

An integrated density norm does not specify the value of a density on a
matrix-dependent graph of labels. We now construct a single density
version whose moment is controlled at every fixed affine offset. The
bound uses the supremum of ambient Riesz potentials of the original
measure. We first prove this analytic estimate, then use it on distance
shells to propagate finite-state continuation probabilities backward.
The shell argument retains an explicit logarithmic loss.

Throughout this section, fix an integer $d\ge16$ and put
\begin{equation}\label{p:riesz-parameters}
 k=q=\lfloor d/8\rfloor,\qquad \alpha=d/2.
\end{equation}
These choices give
\[
 q\ge2,\qquad d/16\le k=q\le d/8,\qquad
 \alpha-k-q\ge1,\qquad d-1-\alpha\ge1.
\]
The matrix $X$ will always denote a $k$ by $d$ standard Gaussian matrix.
Constants denoted by $C\ge1$ are absolute and may increase between uses.

\subsection{Ambient potentials and affine distances}

For a measurable $h:S^{d-1}\to[0,1]$, define the supremum of its
ambient Riesz potentials by
\begin{equation}\label{p:riesz-potential}
 V(h)=\sup_{z\in\R^d}
       \int_{S^{d-1}}\frac{h(s)}{\norm{s-z}^{\alpha}}\,d\sigma(s).
\end{equation}
For a measure $\mu$, the raw Riesz potential is
$U_\alpha^\mu(z)=\int\norm{s-z}^{-\alpha}\,d\mu(s)$
\cite[Section~1, p.~2]{CalefHardin2008v1}. Thus $V(h)$ is its supremum
over ambient centers for $\mu=h\sigma$; it is not the Riesz energy.
The kernel is understood as a nonnegative extended-valued function
at $s=z$. Write $B_r(z)=\{x\in\R^d:\norm{x-z}\le r\}$, and
intersect such balls with the sphere when integrating against
$\sigma$.

\begin{lemma}[Ambient potential bounds]\label{p:riesz-potential-finite}
For every $z\in\R^d$ and $0<r\le1/10$,
\begin{equation}\label{p:riesz-cap}
 \sigma(B_r(z))\le C^d r^{d-1}.
\end{equation}
Every measurable $h:S^{d-1}\to[0,1]$ has finite potential. Moreover, for
$0<\epsilon\le1/10$,
\begin{equation}\label{p:riesz-inner}
 \sup_{z\in\R^d}
 \int_{\norm{s-z}\le\epsilon}\norm{s-z}^{-\alpha}\,d\sigma(s)
 \le C^d\epsilon^{d-1-\alpha}.
\end{equation}
\end{lemma}

\begin{proof}
The ambient estimate \eqref{p:riesz-cap} follows from
Lemma~\ref{p:cap-mass}, with $2^{d-1}$ absorbed into $C^d$.
For dyadic outer radii $r_m=\epsilon2^{-m}$, the shell
$r_m/2<\norm{s-z}\le r_m$ contributes at most
$(2/r_m)^\alpha C^d r_m^{d-1}$. The point $s=z$ has zero
$\sigma$-measure, and
$\sum_{m\ge0}2^{-m(d-1-\alpha)}\le2$. Summing proves
\eqref{p:riesz-inner}. The same argument at radius $1/10$, together
with the kernel bound $10^\alpha$ outside that ball, proves
$V(h)<\infty$ uniformly over $0\le h\le1$.
\end{proof}

The potential bounds the measure of a tube around any affine subspace
through an ambient center. We use that fact to integrate successive
inverse distances when computing the Gaussian projection moment.

\Needspace{3\baselineskip}
\begin{lemma}[Inverse distance to an anchored affine space]
\label{p:riesz-distance}
Let $h:S^{d-1}\to[0,1]$ be measurable, $z\in\R^d$, $\rho>0$,
and let $F$ be an affine subspace through $z$ of dimension
$\ell\le q-1$.  Then $F\cap B_\rho(z)$ has zero $h\,d\sigma$
mass, and
\begin{equation}\label{p:riesz-distance-bound}
 \int_{B_\rho(z)}
       \operatorname{dist}(s,F)^{-k}h(s)\,d\sigma(s)
 \le C^d V(h)\rho^{\alpha-k}.
\end{equation}
\end{lemma}

\begin{proof}
For every ambient center $c$ and radius $r>0$, definition
\eqref{p:riesz-potential} gives
\begin{equation}\label{p:riesz-ball-control}
 \int_{B_r(c)}h\,d\sigma\le V(h)r^\alpha .
\end{equation}
Fix $0<r\le\rho$.  A maximal $r$-separated subset of
$F\cap B_\rho(z)$ has at most $(1+2\rho/r)^\ell
\le(3\rho/r)^\ell$ points, by comparing disjoint radius-$r/2$
balls in $F$ with the radius-$(\rho+r/2)$ ball.  It is an
$r$-net.  The orthogonal projection onto $F$ of any point in
$B_\rho(z)$ lies in $F\cap B_\rho(z)$, since $z\in F$.
Consequently the part of $B_\rho(z)$ within distance $r$ of $F$
is covered by the corresponding ambient radius-$2r$ balls.
Equation \eqref{p:riesz-ball-control} yields
\begin{equation}\label{p:riesz-tube}
 \int_{B_\rho(z)\cap\{\operatorname{dist}(s,F)\le r\}}
       h(s)\,d\sigma(s)
 \le 3^\ell2^\alpha V(h)\rho^\ell r^{\alpha-\ell}.
\end{equation}
This includes $\ell=0$, with a one-point net.  Since
$\alpha-\ell>0$, letting $r$ decrease to zero shows that
$F\cap B_\rho(z)$ has zero mass.

Every point of $B_\rho(z)$ is within distance $\rho$ of $F$.
Apply \eqref{p:riesz-tube} on the shells with outer distance
$r_m=\rho2^{-m}$ and bound the inverse power there by
$(2/r_m)^k$.  Their sum is at most
\[
 3^\ell2^{\alpha+k}V(h)\rho^{\alpha-k}
 \sum_{m\ge0}2^{-m(\alpha-\ell-k)}.
\]
Here
$\alpha-\ell-k\ge\alpha-(q-1)-k\ge2$,
so the series is at most $2$.  Since
$\ell\le d/8$, $\alpha=d/2$, and $k\le d/8$, the remaining
constant is at most $C^d$.  This proves
\eqref{p:riesz-distance-bound}.
\end{proof}

\subsection{A density at fixed affine offsets}

The next estimate uses $q$ points anchored at the chosen center $z$.
Their images under each Gaussian row have an anchored Gram matrix as
covariance. The inverse-distance bound just proved will integrate the
negative determinant power in the joint Gaussian density.

\begin{lemma}[Projection density at deterministic offsets]
\label{p:riesz-density}
Let $z\in\R^d$, $\rho>0$, let
$H\subset S^{d-1}\cap B_\rho(z)$ be measurable, and let
$h:S^{d-1}\to[0,1]$ be measurable. Fix these objects before drawing a
$k$ by $d$ standard Gaussian matrix $X$. The pushforward of
$h\mathbf 1_H\,d\sigma$ by $s\mapsto Xs$ admits a single jointly
Borel function
\[
 R:\R^{k\times d}\times\R^k\longrightarrow[0,\infty]
\]
such that $R(X,\cdot)$ is its Lebesgue density for every full-row-rank
$X$, and, for every fixed $b\in\R^k$,
\begin{equation}\label{p:riesz-density-bound}
 \left(\E_X R(X,Xz+b)^q\right)^{1/q}
 \le C^d V(h)\rho^{\alpha-k}.
\end{equation}
The same function $R$ is used for all $b$.  Moreover,
\begin{equation}\label{p:riesz-density-support}
 R(X,y)=0
 \quad\hbox{if}\quad
 \norm{y-Xz}>\norm X_{\mathrm{op}}\rho .
\end{equation}
\end{lemma}

\begin{proof}
Let $\mu$ be the finite Borel measure given by
$\mu(E)=\int_E h\mathbf1_H\,d\sigma$ on Borel subsets of the
sphere.  For $\eta>0$, let
$B_\eta^k=\{u\in\R^k:\norm u\le\eta\}$ and let
$\operatorname{vol}_k$ denote $k$-dimensional Lebesgue measure.  Define
\begin{equation}\label{p:riesz-ball-average}
 R_\eta(X,y)=
 \frac{1}{\operatorname{vol}_k(B_\eta^k)}
 \int \mathbf1_{\{\norm{Xt-y}\le\eta\}}\,d\mu(t).
\end{equation}
The integrand is Borel in $(X,y,t)$, so the parameter integral is
Borel in $(X,y)$.  We first prove
\eqref{p:riesz-density-bound} with $R_\eta$ in place of $R$,
uniformly in $\eta$.

Expand its $q$th moment at $Xz+b$ by Tonelli's theorem, using
$t_1,\ldots,t_q$ from the $q$ copies of $\mu$.  For a fixed tuple,
the columns $X(t_j-z)$ form an array whose $k$ rows are independent
centered Gaussian vectors with covariance
\[
 G=\bigl(\inner{t_i-z}{t_j-z}\bigr)_{1\le i,j\le q}.
\]
If $G$ is nonsingular, their joint density is bounded everywhere by
$(2\pi)^{-kq/2}(\det G)^{-k/2}$.  Therefore the probability that
all columns belong to the radius-$\eta$ ball about $b$ is at most
this bound times $\operatorname{vol}_k(B_\eta^k)^q$.

The singular tuples have zero $\mu^q$ mass.  Indeed, at the first
linearly dependent vector $t_j-z$, the point $t_j$ lies in
$z+\operatorname{span}(t_1-z,\ldots,t_{j-1}-z)$, an affine space
through $z$ of dimension at most $q-1$.  Lemma~\ref{p:riesz-distance}
assigns zero $\mu$ mass to it.  The degeneracy set is measurable,
and Fubini's theorem applied at each $j$ proves the claim.  For a
nonsingular tuple, Gram--Schmidt triangularizes the matrix with
columns $t_j-z$ with diagonal entries equal to the successive
orthogonal distances.  Taking the determinant of its Gram matrix
gives
\begin{equation}\label{p:riesz-gram}
 (\det G)^{-k/2}
 =\prod_{j=1}^q
 \operatorname{dist}\!\left(
 t_j,z+\operatorname{span}(t_1-z,\ldots,t_{j-1}-z)
 \right)^{-k}.
\end{equation}
Integrate this product first in $t_q$, then in $t_{q-1}$, and so on.
For every nonsingular prefix, Lemma~\ref{p:riesz-distance} bounds
the next integral by $C^dV(h)\rho^{\alpha-k}$.  The exceptional
prefixes have zero product measure by the same degeneracy argument.
It follows that the integral of
\eqref{p:riesz-gram} is at most
$(C^dV(h)\rho^{\alpha-k})^q$.  The ball volumes cancel in the
moment expansion, and the Gaussian prefactor is at most one.
Thus
\[
 \E_X R_\eta(X,Xz+b)^q
 \le \bigl(C^dV(h)\rho^{\alpha-k}\bigr)^q
\]
for every $\eta>0$ and every fixed $b$.

Now choose the function once and for all:
\begin{equation}\label{p:riesz-density-version}
 R(X,y)=\liminf_{m\to\infty}R_{1/m}(X,y).
\end{equation}
It is jointly Borel. To see that it is a density, fix a full-row-rank
$X$. Set $D=(XX^{\mathsf T})^{1/2}$ and $P=D^{-1}X$, so $D$ is invertible,
$P$ has orthonormal rows, and $X=DP$.
Lemma~\ref{p:coordinate-density} makes $P_\#\sigma$ absolutely
continuous, and the invertible map $D$ preserves absolute continuity.
Since $\mu\le\sigma$, the pushforward $X_\#\mu$ is also absolutely
continuous. The Lebesgue differentiation
theorem~\cite[Theorem~1.6.19]{TaoMeasure2011}, applied to its
$L^1$ density, shows that
\eqref{p:riesz-density-version} equals that density almost
everywhere in $y$.  A Gaussian $X$ has full row rank almost
surely, since each successive Gaussian row avoids the span of
the preceding rows.

For each fixed $b$, the identity
$R(X,Xz+b)=\liminf_m R_{1/m}(X,Xz+b)$ holds by the definition of
the single function $R$.  Fatou's
lemma~\cite[Corollary~1.4.47]{TaoMeasure2011} over $X$ now gives
\eqref{p:riesz-density-bound}.  These are separate moment
statements for each deterministic $b$; no simultaneous
almost-sure bound in $X$ over all offsets is asserted.  Finally,
if $\norm{y-Xz}>\norm X_{\mathrm{op}}\rho$, then every $Xt$ with
$t\in H$ is at distance at least
$\norm{y-Xz}-\norm X_{\mathrm{op}}\rho>0$ from $y$.  The averages in
\eqref{p:riesz-ball-average} are eventually zero, proving
\eqref{p:riesz-density-support}.
\end{proof}

The explicit choice \eqref{p:riesz-density-version} is the feature
needed for the next step. A density chosen only up to a
Lebesgue-null set in $y$ for each $X$ would not justify the moment
estimate at the matrix-dependent point $Xz+b$.
An integrated $L^q(dX\,dy)$ estimate controls a density only up to
product-null sets, while the graph $y=Xz+b$ has zero product measure.
Positive cap domination instead controls the measure of every Borel
set by a positive sum of cap measures.  Neither conclusion supplies
the specified-offset moment in Lemma~\ref{p:riesz-density}; its
anchored determinant estimate and explicit limit are therefore kept
as a separate argument.

\subsection{Continuation probabilities and the terminal potential}

We apply the specified-offset estimate to the finite-state experiment of
Section~\ref{p:geometry-model}. Fix nonnegative integers $M,T$ and an
accuracy $0<\epsilon\le1/10$, and write
\[
 p_{\mathrm{succ}}=\Prob\{\arccos\inner{\widehat S}{S}\le\epsilon\},
 \qquad L=\log(1/\epsilon),\qquad
 N=\lceil T/k\rceil,\qquad W=(T+2)2^M.
\]
The success probability averages over the uniform signal, Gaussian
features, and learner randomness. The factor $W$ will count the retained
states together with their possible terminal stopping indices.

\begin{proposition}[Riesz success estimate]\label{p:riesz-success}
There is an absolute constant $C_0\ge1$ such that every learner just
specified satisfies
\begin{equation}\label{p:riesz-success-bound}
 p_{\mathrm{succ}}\le B J^N,\qquad
 B=C_0^d\epsilon^{\,d/2-1},\qquad
 J=1+C_0^d(1+L)W^{1/q}.
\end{equation}
This includes $T=0$.  No asymptotic assumption on $M$ is needed for
this estimate.
\end{proposition}

We first bound the potential of each terminal output law. To control its
increase across a block, we apply Lemma~\ref{p:riesz-density} at $Xz+b$
and then integrate over $b$. The factor $1+L$ in
\eqref{p:riesz-success-bound} counts the distance shells and remains
in the final parameter argument.

Use the fixed-seed and Borel-kernel convention of
Section~\ref{p:geometry-model}: first fix an admissible shared seed,
under which the initial state is independent of the signal and rows,
and then apply Lemma~\ref{p:borel-kernels} to choose Borel rules. These
rules define continuations from every state. All bounds below are uniform
in the fixed rules; after proving the conditional bound, we average the
original conditional success probabilities over the seed.

Complete unused rules and terminal laws arbitrarily, and force a halt
by $T$.  After a halt, retain a tag consisting of the stopping index
and terminal state and ignore further samples.  At any time there are
at most $2^M$ live states and at most $(T+1)2^M$ such tags, including
a possible immediate halt. Hence the stated bound $W$ applies. Add
independent unused Gaussian rows after $T$ to complete the last block of length $k$.  Let
$\mathcal V_i$ be the state set at the boundary after block $i$,
$0\le i\le N$; thus $\lvert\mathcal V_i\rvert\le W$.

For every $v\in\mathcal V_i$ and $s\in S^{d-1}$, let $h_i(v,s)$ be
the success probability of the remaining execution started at that
boundary state.  This definition also applies to states not reached
by the original run.  At $i=N$ it is the success probability of the
fixed output law associated with the terminal state.  These functions
are Borel and take values in $[0,1]$: the terminal assertion follows
by integrating the Borel success indicator against the output law,
and the assertion at earlier boundaries follows inductively from
the formula below.  If $X$ is a fresh $k$ by $d$ standard Gaussian
matrix, then for $1\le i\le N$
\begin{equation}\label{p:riesz-recursion}
 h_{i-1}(v,s)
 =\E_X\sum_{w\in\mathcal V_i}K^{(i)}_{v,w}(X,Xs)h_i(w,s).
\end{equation}
Here $K^{(i)}_{v,w}(X,y)$ is the probability of the block transition
from $v$ to $w$ on the exact row pairs $(X,y)$.  These kernels are
Borel, nonnegative, and sum to one in $w$ for every $(X,y)$.
They incorporate internal randomization and the ignored rows after a
halt.  The functions $h_i(w,\cdot)$ are fixed independently of $X$.
The fresh Gaussian block is independent of the signal, initialization,
past rows, and past coins. Starting the continuation at the specified
state therefore gives exactly \eqref{p:riesz-recursion}; the state and
boundary index contain all retained sample-dependent information.

\begin{lemma}[Terminal potential]\label{p:riesz-terminal-lemma}
Let $Q$ be a signal-independent probability law on unit-vector outputs,
and let $h(s)=Q\{u:\arccos\inner{u}{s}\le\epsilon\}$. Then
\begin{equation}\label{p:riesz-terminal}
 V(h)\le C^d\epsilon^{d-1-\alpha}.
\end{equation}
\end{lemma}

\begin{proof}
Lemma~\ref{p:cap-mass} gives $\int h\,d\sigma\le\epsilon^{d-1}$,
also for a randomized output law. For any ambient center $z$, use
$h\le1$ and \eqref{p:riesz-inner} inside $B_\epsilon(z)$. Outside
that ball, bound the kernel by $\epsilon^{-\alpha}$ and use the total
mass bound. The sum is at most $C^d\epsilon^{d-1-\alpha}$ uniformly
in $z$, proving \eqref{p:riesz-terminal}.
\end{proof}

Set
\[
 V_i=\max_{v\in\mathcal V_i}V(h_i(v,\cdot)).
\]
The maximum is finite by Lemma~\ref{p:riesz-potential-finite}.
Lemma~\ref{p:riesz-terminal-lemma} gives $V_N\le C^d\epsilon^{d-1-\alpha}$.
We next estimate the contribution of a single distance shell in
\eqref{p:riesz-recursion}.

\subsection{One block and the distance shells}

\begin{lemma}[One shell across a block]\label{p:riesz-shell}
For $1\le i\le N$, $v\in\mathcal V_{i-1}$, $z\in\R^d$, and
$\rho>0$, let
$H_\rho(z)=\{s\in S^{d-1}:\rho/2<\norm{s-z}\le\rho\}$.
Then
\begin{equation}\label{p:riesz-shell-bound}
 \int_{H_\rho(z)}
   \frac{h_{i-1}(v,s)}{\norm{s-z}^{\alpha}}\,d\sigma(s)
 \le C^d W^{1/q}V_i.
\end{equation}
\end{lemma}

\begin{proof}
For each successor $w$, use the particular density $R_w(X,y)$
of Lemma~\ref{p:riesz-density} for the measure
$h_i(w,\cdot)\mathbf1_{H_\rho(z)}\,d\sigma$.
Tonelli's theorem, \eqref{p:riesz-recursion}, and pushforward
integration give
\begin{equation}\label{p:riesz-shell-pushforward}
\begin{split}
 \int_{H_\rho(z)}
    \frac{h_{i-1}(v,s)}{\norm{s-z}^{\alpha}}\,d\sigma(s)
 &\le (2/\rho)^\alpha
       \E_X\int_{\R^k}
       \sum_wK^{(i)}_{v,w}(X,y)R_w(X,y)\,dy\\
 &\le (2/\rho)^\alpha
       \E_X\int_{\norm{y-Xz}\le\norm X_{\mathrm{op}}\rho}
       \max_wR_w(X,y)\,dy .
\end{split}
\end{equation}
The pushforward identity used in the first inequality holds for every
full-row-rank $X$, hence almost surely.  The second inequality uses
the probability-vector property of $K^{(i)}$ and
\eqref{p:riesz-density-support}.

We need a deterministic integration region after averaging over
$X$.  Choose a sufficiently large absolute $D_0$ and partition
the matrices into
\[
 E_1=\{\norm X_{\mathrm{op}}\le D_0\sqrt d\},\qquad
 E_j=\{D_0(j-1)\sqrt d<\norm X_{\mathrm{op}}\le D_0j\sqrt d\}
 \quad(j\ge2).
\]
These bins obey
\begin{equation}\label{p:riesz-bins}
 \P(E_j)\le \exp\bigl(-4(j-1)^2d\bigr)\qquad(j\ge2).
\end{equation}
For completeness, take $1/4$-nets on the unit spheres of $\R^d$
and $\R^k$.  A maximal separated set has at most $9^d$ and
$9^k$ points, respectively, by the disjoint-ball volume argument.
Approximating each unit vector by its net point incurs an error
at most $\norm X_{\mathrm{op}}/2$ in a bilinear form.  Hence
$\norm X_{\mathrm{op}}$ is at most twice the largest absolute
bilinear form on the two nets.  Each such form is standard
Gaussian, so its elementary tail bound and a union bound give
\begin{equation}\label{p:riesz-operator-tail}
 \P\{\norm X_{\mathrm{op}}>t\}
 \le 2\cdot9^{d+k}\exp(-t^2/8).
\end{equation}
Putting $t=D_0(j-1)\sqrt d$ proves
\eqref{p:riesz-bins} after increasing $D_0$, since $k\le d/8$.

For every deterministic $b\in\R^k$, H\"older's inequality and
\eqref{p:riesz-density-bound} give
\begin{equation}\label{p:riesz-bin-holder}
\begin{split}
 \E_X\!\left[\mathbf1_{E_j}\max_wR_w(X,Xz+b)\right]
 &\le \P(E_j)^{1-1/q}
       \left(\sum_w\E_X R_w(X,Xz+b)^q\right)^{1/q}\\
 &\le \P(E_j)^{1-1/q}W^{1/q}
       C^dV_i\rho^{\alpha-k}.
\end{split}
\end{equation}
No conditional version of the density lemma is being used:
H\"older's inequality pays for the bin event.  For a fixed matrix
in $E_j$, translate $y=Xz+b$ in
\eqref{p:riesz-shell-pushforward}; the remaining region is
$\norm b\le D_0j\sqrt d\,\rho$.  Joint measurability permits
Tonelli's theorem to integrate \eqref{p:riesz-bin-holder} over
this deterministic ball.

The volume of that ball is at most $C^d j^k\rho^k$.  Indeed, the unit-ball bound \eqref{p:unit-ball-volume} gives
$v_k\le(2\pi e/k)^{k/2}$. Since $d/k\le16$,
$v_k(D_0j\sqrt d\,\rho)^k\le C^d j^k\rho^k$.
Also, by $q\ge2$ and \eqref{p:riesz-bins},
\[
 \sum_{j\ge1}j^k\P(E_j)^{1-1/q}
 \le 1+\sum_{j\ge2}
       \exp\bigl(k\log j-2(j-1)^2d\bigr)
 \le 2 .
\]
For the last bound use
$k\log j\le(d/8)(j-1)^2$ for $j\ge2$ and sum the resulting
geometric upper bound.  Combining the volume and bin estimates
with \eqref{p:riesz-shell-pushforward} proves
\eqref{p:riesz-shell-bound}.  The powers of the shell radius
cancel exactly:
\[
 \rho^{-\alpha}\rho^{\alpha-k}\rho^k=1.
\]
\end{proof}

\begin{proof}[Proof of Proposition~\ref{p:riesz-success}]
Outside $B_\epsilon(z)$ use the shells
\[
 2^m\epsilon<\norm{s-z}\le2^{m+1}\epsilon,
 \qquad m=0,1,\ldots .
\]
For every ambient $z$, at most $C(1+L)$ of these meet the
sphere.  If $\norm z\le3$, all distances are at most $4$, giving
at most $\lceil\log_2(4/\epsilon)\rceil$ nonempty shells.  If
$\norm z>3$, the distances lie between $\norm z-1$ and
$\norm z+1$, whose ratio is less than $2$; only a bounded number
of dyadic shells can then meet that interval.

Inside $B_\epsilon(z)$ use $h_{i-1}\le1$ and
\eqref{p:riesz-inner}.  On each remaining shell use
Lemma~\ref{p:riesz-shell}.  Taking the supremum over $z$ and the
maximum over $v$ gives
\begin{equation}\label{p:riesz-step}
 V_{i-1}\le C^d\epsilon^{d-1-\alpha}
          +C^d(1+L)W^{1/q}V_i .
\end{equation}
Choose $C_0$ large enough that the first term here and the
terminal value $V_N$ are at most $B$ in
\eqref{p:riesz-success-bound}, and that the second coefficient is
at most $J-1$.  With $U_i=\max\{V_i,B\}$, equation
\eqref{p:riesz-step} gives $U_{i-1}\le J U_i$, while $U_N=B$.
Hence $V_0\le BJ^N$, also when $N=0$.

At $z=0$ the kernel in \eqref{p:riesz-potential} equals one on
the unit sphere, so $\int h_0(v,s)\,d\sigma(s)\le V_0$ for
each initial state. For almost every fixed shared seed, averaging over its
conditional initial-state law preserves the bound, because that law is
independent of the signal and rows. Averaging the original conditional
success probabilities over the seed then
preserves it again.  This proves \eqref{p:riesz-success-bound}.
\end{proof}

\subsection{The logarithmic lower bound}

We now prove Theorem~\ref{p:regression} from the Riesz success estimate.
The parameter argument retains the stopping-index factor in $W$ and
the shell-count factor $1+L$. Terminal-tag counting controls both in
the only case still requiring proof, namely $T<dL$.

\begin{proof}[Proof of Theorem~\ref{p:regression} by the Riesz method]
There is a useful bound that counts possible terminal tags.
For fixed rules as above, write $p_{\mathrm{succ},\mathrm{rule}}$ for
the conditional success probability.
For a tag $a$, let $f_a(s)$ be the probability of reaching it
given $s$, and let $g_a(s)$ be its output law's success
probability.  This output law depends only on the tag, and
$0\le f_a\le1$.
Lemma~\ref{p:cap-mass} gives
$\int g_a\,d\sigma\le C^d\epsilon^{d-1}$, including a randomized
output law.  Sum over at most $W$ tags to obtain
\begin{equation}\label{p:riesz-packing}
 p_{\mathrm{succ},\mathrm{rule}}=\sum_a\int f_a(s)g_a(s)\,d\sigma(s)
 \le W C^d\epsilon^{d-1}.
\end{equation}
The right side is independent of the chosen rules, so averaging
also gives $p_{\mathrm{succ}}\le W C^d\epsilon^{d-1}$.

Write $L=\log(1/\epsilon)$.  If $T\ge dL$, the conclusion
already holds.  In the remaining case $T<dL$, assume $p_{\mathrm{succ}}\ge2/3$.
Taking logarithms in the averaged form of \eqref{p:riesz-packing} gives
\[
 (d-1)L
 \le M\log2+\log(T+2)+d\log C+\log(3/2).
\]
For the given memory sequence, eventually $M\le d^2$.  Since
$L\ge\log10$ and $T<dL$, we also have
\[
 \log(T+2)\le\log(2d)+\log L\le\log(2d)+L
\]
for large $d$.  It follows that
$(d-2)L\le d^2\log2+d\log C+\log(2d)+\log(3/2)$.
Consequently, only in this remaining case,
\begin{equation}\label{p:riesz-short-run}
 L\le Cd,\qquad \log W=M\log2+\log(T+2)\le Cd^2 .
\end{equation}
Thus the multiplier from Proposition~\ref{p:riesz-success} obeys
\[
 \log J
 \le \log2+d\log C_0+\log(1+L)+\frac{\log W}{q}
 \le Cd ,
\]
using $q\ge d/16$.  In particular the shell-count term has
been bounded rather than removed.

Now \eqref{p:riesz-success-bound} and $p_{\mathrm{succ}}\ge2/3$ imply
\begin{equation}\label{p:riesz-final}
 (d/2-1)L
 \le d\log C_0+N\log J+\log(3/2)
 \le Cd(1+N)+\log(3/2)
 \le C'(d+T),
\end{equation}
because $N=\lceil T/k\rceil\le16T/d+1$.
The common full-data bound, Lemma~\ref{p:haar-linear}, gives
$T>d/8$; hence the additive $d$ on the right of
\eqref{p:riesz-final} is at most $8T$.
For $d\ge4$ the left coefficient is at least $d/4$, so
$T\ge c\,dL$ for an absolute $c>0$. This combines with the
case $T\ge dL$ already separated.
\end{proof}
==== END Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//sections/riesz.tex ====

==== BEGIN Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//references.bib ====
@inproceedings{SSV2019,
  author = {Sharan, Vatsal and Sidford, Aaron and Valiant, Gregory},
  title = {Memory-Sample Tradeoffs for Linear Regression with Small Error},
  booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing},
  year = {2019},
  pages = {890--901},
  note = {Full version arXiv:1904.08544v2, 10 October 2020; theorem and section locators refer to that version. \url{https://arxiv.org/abs/1904.08544v2}. DOI: \url{https://doi.org/10.1145/3313276.3316403}}
}

@inproceedings{SteinhardtDuchi2015,
  author = {Steinhardt, Jacob and Duchi, John},
  title = {Minimax Rates for Memory-Bounded Sparse Linear Regression},
  booktitle = {Proceedings of the 28th Conference on Learning Theory},
  series = {Proceedings of Machine Learning Research},
  volume = {40},
  year = {2015},
  pages = {1564--1587},
  note = {\url{https://proceedings.mlr.press/v40/Steinhardt15.html}}
}

@inproceedings{SVW2016,
  author = {Steinhardt, Jacob and Valiant, Gregory and Wager, Stefan},
  title = {Memory, Communication, and Statistical Queries},
  booktitle = {29th Annual Conference on Learning Theory},
  series = {Proceedings of Machine Learning Research},
  volume = {49},
  year = {2016},
  pages = {1490--1516},
  note = {\url{https://proceedings.mlr.press/v49/steinhardt16.html}}
}

@inproceedings{Shamir2014,
  author = {Shamir, Ohad},
  title = {Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation},
  booktitle = {Advances in Neural Information Processing Systems},
  volume = {27},
  year = {2014},
  pages = {163--171},
  note = {\url{https://proceedings.neurips.cc/paper_files/paper/2014/hash/cc427d934a7f6c0663e5923f49eba531-Abstract.html}}
}

@misc{Raz2016,
  author = {Raz, Ran},
  title = {Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning},
  year = {2016},
  note = {arXiv:1602.05161v1, 16 February 2016. \url{https://arxiv.org/abs/1602.05161v1}}
}

@inproceedings{DKS2019,
  author = {Dagan, Yuval and Kur, Gil and Shamir, Ohad},
  title = {Space Lower Bounds for Linear Prediction in the Streaming Model},
  booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory},
  series = {Proceedings of Machine Learning Research},
  volume = {99},
  year = {2019},
  pages = {929--954},
  note = {Theorem locators refer to the published PMLR version. \url{https://proceedings.mlr.press/v99/dagan19b.html}}
}

@article{Mattila1975,
  author = {Mattila, Pertti},
  title = {Hausdorff Dimension, Orthogonal Projections and Intersections with Planes},
  journal = {Annales Academiae Scientiarum Fennicae, Series A I, Mathematica},
  volume = {1},
  number = {2},
  year = {1975},
  pages = {227--244},
  note = {DOI: \url{https://doi.org/10.5186/aasfm.1975.0110}}
}

@article{Drury1984,
  author = {Drury, S. W.},
  title = {Generalizations of {Riesz} Potentials and {$L^p$} Estimates for Certain \(k\)-Plane Transforms},
  journal = {Illinois Journal of Mathematics},
  volume = {28},
  number = {3},
  year = {1984},
  pages = {495--512}
}

@article{FranklMaehara1990,
  author = {Frankl, Peter and Maehara, Hiroshi},
  title = {Some Geometric Applications of the Beta Distribution},
  journal = {Annals of the Institute of Statistical Mathematics},
  volume = {42},
  number = {3},
  year = {1990},
  pages = {463--474},
  note = {DOI: \url{https://doi.org/10.1007/BF00049302}}
}

@misc{SchnaubeltFA2025,
  author = {Schnaubelt, Roland},
  title = {Functional Analysis: Lecture Notes of Winter Semester 2017/18},
  howpublished = {Karlsruhe Institute of Technology, author-hosted lecture notes},
  year = {2025},
  note = {Title-page version 21 July 2025; accessed 27 September 2026. \url{https://iana.math.kit.edu/downloads/iana3/schnaubelt/Skripten/fa17-skript.pdf}}
}

@misc{FremlinTaxonomy,
  author = {Fremlin, D. H.},
  title = {Measure Theory, Chapter 21: Taxonomy of Measure Spaces},
  howpublished = {University of Essex, author-hosted online development extract},
  note = {Section 211 version 20 November 2003; accessed 27 September 2026. \url{https://www1.essex.ac.uk/maths/people/fremlin/chap21.pdf}}
}

@misc{FremlinFunctionSpaces,
  author = {Fremlin, D. H.},
  title = {Measure Theory, Chapter 24: Function Spaces},
  howpublished = {University of Essex, author-hosted online development extract},
  note = {Chapter version 15 November 2013; Section 243 version 30 April 2004; accessed 27 September 2026. \url{https://www1.essex.ac.uk/maths/people/fremlin/chap24.pdf}}
}

@book{TaoMeasure2011,
  author = {Tao, Terence},
  title = {An Introduction to Measure Theory},
  publisher = {American Mathematical Society},
  series = {Graduate Studies in Mathematics},
  volume = {126},
  year = {2011},
  note = {Theorem and page locators refer to the author-hosted preliminary version; accessed 27 September 2026. \url{https://terrytao.wordpress.com/wp-content/uploads/2012/12/gsm-126-tao5-measure-book.pdf}}
}

@misc{CalefHardin2008v1,
  author = {Calef, Matthew T. and Hardin, Douglas P.},
  title = {{Riesz} \(s\)-Equilibrium Measures on \(d\)-Rectifiable Sets as \(s\) Approaches \(d\)},
  year = {2008},
  note = {arXiv:0808.3802v1, 28 August 2008; the potential definition is in Section 1, p.~2. \url{https://arxiv.org/abs/0808.3802v1}}
}

@article{Jiang2006,
  author = {Jiang, Tiefeng},
  title = {How Many Entries of a Typical Orthogonal Matrix Can Be Approximated by Independent Normals?},
  journal = {The Annals of Probability},
  volume = {34},
  number = {4},
  year = {2006},
  pages = {1497--1529},
  note = {Lemma locators refer to the published-article reprint, arXiv:math/0601457v2, 25 September 2006. \url{https://arxiv.org/abs/math/0601457v2}. DOI: \url{https://doi.org/10.1214/009117906000000205}}
}
==== END Projection-moments-positive-cap-domination-and-Riesz-estimates-on-the-sphere//references.bib ====