\section{Affine systems in a random permutation}\label{sec:pooling}

For an $h\times m$ matrix $H$ with columns $H_1,\ldots,H_m$, set
\begin{equation}\label{eq:affine-rank}
S(H)=\Span\{H_j-H_{j'}:j,j'\in[m]\},
\qquad d=\dim S(H).
\end{equation}
An actual column value is a vector $c$ that occurs as some $H_j$; its multiplicity is $\lvert\{j\in[m]:H_j=c\}\rvert$.
When $x$ is a permutation of $X$, replacing every column $H_j$ by $H_j+c$ translates $Hx$ by the fixed vector $c\sum_{u\in X}u$.
The affine column dimension is therefore the relevant quantity.
The rank-exposure argument is standard; see \citep[proof of Proposition~2.2]{Odlyzko1988} and \citep[Lemma~3.7]{Kwan2025}.
Related exposures retaining a large reservoir occur in the chain estimate \citep[Corollary~4.2]{Pham2026}.
Disjoint position pools recover independent scalar sums inside a permutation.

\begin{lemma}\label{lem:pooling}
Fix an integer $h\ge1$ and $0<\gamma\le1$.
Suppose $H$ is an $h\times m$ matrix over $\Fp$ with an actual column value $c_0$ of multiplicity at least $\gamma m$.
Suppose actual column values $c_1,\ldots,c_q$ each have multiplicity at least $L$ and the differences $c_1-c_0,\ldots,c_q-c_0$ are independent.
If $x:[m]\to X$ is a uniform bijection onto an arbitrary $m$-element set $X\subseteq\Fp$, then, for every fixed $z\in\Fp^h$,
\begin{equation}\label{eq:pooling-bound}
\Pr(Hx=z)\le P_{h,\gamma}m^{-d-\eta q}
\end{equation}
provided $p\ge m^{1+\beta}$ and $m$ exceeds a threshold depending only on $h,\gamma,C$.
The constant $P_{h,\gamma}$ has the same parameter dependence.
The independence assumption implies $q\le d\le h$.
The cases $q=0$ and $d=0$ are allowed.
\end{lemma}

\begin{proof}
If $d=0$, every column is $c_0$, necessarily $q=0$, and $Hx=c_0\sum_{u\in X}u$ is deterministic.
Assume $d\ge1$.
Extend the specified differences to a basis
\begin{equation*}
v_i=c_i-c_0,\qquad 1\le i\le d,
\end{equation*}
by choosing further actual column values.
For $i\le q$, select $L$ positions of column value $c_i$; for $q<i\le d$, select one.
Denote these disjoint position sets by $E_i$ and their sizes by $r_i$.
None is a baseline position.

Put
\begin{equation*}
a=\frac{\gamma}{4h},\qquad
t=\left\lfloor\frac{\gamma m}{2h}\right\rfloor.
\end{equation*}
For $m\ge4h/\gamma$, one has $t\ge am$.
Choose disjoint sets $F_i$ of $t$ baseline positions, also disjoint from every $E_i$.
There are enough baseline positions because $dt\le ht\le\gamma m/2$.
The disjoint pools $E_i\cup F_i$ have sizes $N_i=t+r_i\in[am,m]$.

Condition on the assignments outside these pools and on the unordered value set $Y_i$ assigned to each pool.
Every nonempty fibre has exactly $\prod_iN_i!$ assignments, one for each tuple of bijections from the pools to their value sets.
The restrictions to the pools are therefore independent uniform bijections.
Pool $i$ contributes
\begin{equation*}
c_0\sum_{y\in Y_i}y+v_iZ_i,
\qquad Z_i=\sum_{j\in E_i}x_j
\end{equation*}
to $Hx$.
The baseline terms and the contribution outside the pools are fixed.
Since $v_1,\ldots,v_d$ are independent, $Hx=z$ permits at most one tuple $(Z_1,\ldots,Z_d)$.

For $i\le q$, Lemma~\ref{lem:scalar-range} bounds the largest atom of $Z_i$ by $K_am^{-1-\eta}$.
For $i>q$, the singleton value is uniform on $Y_i$ and has largest atom $N_i^{-1}\le a^{-1}m^{-1}$.
Multiplying the bounds on each fibre and averaging proves~\eqref{eq:pooling-bound}, with
\begin{equation*}
P_{h,\gamma}=\max\{1,K_a,a^{-1}\}^{h}.
\end{equation*}
Increase the threshold to include $m_a$ and $4h/\gamma$.
This constant also covers $d=0$.
\end{proof}

The residual right-hand side may vary between fibres, since the bound is uniform in $z$.
It is fixed on each fibre before the independent pool assignments are exposed.