\section{Collision matrices and circular clusters}\label{sec:rank}

The standard incidence-rank formula gives the number of vertices minus the number of components; see \citep[Theorem~2.3]{Bapat2010}.
The following extension includes disjoint cluster indicators.

\begin{lemma}\label{lem:functional-rank}
Let $g:[\ell]\to[\ell]$ have no fixed points, and let $B_0,B_1,\ldots,B_q$ partition $[\ell]$, with $B_0$ possibly empty and $B_a\ne\varnothing$ for $a\ge1$.
Over a field of characteristic zero or characteristic $p>\ell$, put
\begin{equation*}
D_{ij}=\mathbf1_{j=i}-\mathbf1_{j=g(i)},
\qquad w_a=\mathbf1_{B_a}.
\end{equation*}
If $C_1,\ldots,C_\kappa$ are the directed cycles of $g$ and $T$ is the $\kappa\times q$ matrix with $T_{ua}=\lvert C_u\cap B_a\rvert$, $1\le a\le q$, interpreted in the field, then
\begin{equation}\label{eq:functional-rank}
\rank[D\mid w_1\mid\cdots\mid w_q]
=\ell-\kappa+\rank T\ge\frac{\ell+q}{2}.
\end{equation}
\end{lemma}

\begin{proof}
The equations $D^{\mathsf T}y=0$ read
\begin{equation*}
y_j=\sum_{i:g(i)=j}y_i.
\end{equation*}
Each functional-graph component consists of a directed cycle with trees feeding into it.
Deleting leaves forces $y$ to vanish off the cycles; on each cycle it is constant.
Thus $\ker D^{\mathsf T}$ has basis $\mathbf1_{C_1},\ldots,\mathbf1_{C_\kappa}$ and $\rank D=\ell-\kappa$.
The map $\pi(y)_u=\sum_{i\in C_u}y_i$ has kernel $\operatorname{im}D$, by inclusion and dimension.
The images $\pi(w_a)$ form $T$, proving the rank equality.

Write $t=\rank T$ and select $t$ rows spanning its row space.
For every nonzero column $a$, choose a vertex of $B_a$ on a selected cycle where that column is nonzero.
A zero column has no cycle intersection: a positive intersection size is at most $\ell$ and cannot vanish in the stated characteristic.
For such a column choose an off-cycle vertex of $B_a$.
These $q$ distinct representatives avoid all $\kappa-t$ unselected cycles.
Each such cycle has at least two vertices.
Hence $\ell\ge q+2(\kappa-t)$, which proves the inequality.
\end{proof}

Let $M,L,m,\ell$ be integers with
\begin{equation}\label{eq:geometry-range}
2\le\ell\le M,\qquad L\ge M,\qquad m\ge2(\ell+1)L.
\end{equation}
Fix $0\le b<m$, disjoint sets $U,Q\subseteq\{b+1,\ldots,\min(m,b+M)\}$ with $\lvert Q\rvert=\ell$, and a cyclic order $(q_1,\ldots,q_\ell)$ of $Q$.
For each $i$, let $I_i$ be a nonempty proper cyclic prefix beginning at $q_i$, let $t_i\in\{0,\ldots,m\}$ satisfy $\lvert t_i-b\rvert>2M$, and choose
\begin{equation*}
J_i\subseteq\{t_i+1,\ldots,\min(m,t_i+M)\}.
\end{equation*}
Define the $\ell\times m$ matrix
\begin{equation}\label{eq:witness-matrix}
(H_j)_i=\mathbf1_{j\le b}-\mathbf1_{j\le t_i}
+\mathbf1_{j\in U}+\mathbf1_{j\in I_i}-\mathbf1_{j\in J_i}.
\end{equation}

Mark $b,t_1,\ldots,t_\ell$ on $\Z/m\Z$.
Join consecutive distinct marks when their clockwise gap is shorter than $2L$; the connected components are the clusters.
Equal residues are in the same cluster.
If there is only one distinct mark, its sole gap has length $m$.
Let $q$ count the clusters not containing $b$, and set $B_a=\{i:t_i\text{ lies in cluster }a\}$, with $B_0$ corresponding to the source cluster.
The linear anchors $0$ and $m$ remain distinct in~\eqref{eq:witness-matrix}.

\begin{lemma}\label{lem:witness-columns}
Under~\eqref{eq:geometry-range}, in characteristic zero or characteristic $p>\ell$, the affine column dimension $d$ of $H$ satisfies $d\ge(\ell+q)/2$.
There are actual column values $c_0,\ldots,c_q$ such that $c_0$ occurs at least $m/[2(\ell+1)]$ times, each other $c_a$ occurs at least $L$ times, and $c_1-c_0,\ldots,c_q-c_0$ are independent.
\end{lemma}

\begin{proof}
Let $g(i)\ne i$ be the cyclic position immediately after $I_i$.
Neither $U$ nor $J_i$ meets $Q$, and the prefix difference in~\eqref{eq:witness-matrix} is constant on $Q$.
Let $D$ be the matrix of Lemma~\ref{lem:functional-rank} for this map $g$, and write $D_{\cdot j}$ for its $j$-th column.
Taking consecutive cyclic source-column differences gives
\begin{equation}\label{eq:source-differences}
H_{q_j}-H_{q_{j-1}}=D_{\cdot j},
\qquad q_0=q_\ell.
\end{equation}
Thus $\operatorname{im}D\subseteq S(H)$.

At least one circular gap has length at least $2L$, by~\eqref{eq:geometry-range}.
Every cluster lies in an arc of length less than $2\ell L$, and there are $q+1$ intercluster gaps.
Write $H_j=A_j+E_j$, with $(A_j)_i=\mathbf1_{j\le b}-\mathbf1_{j\le t_i}$.
For an intercluster gap of length $G$ from $a$ to the next mark $a+G$, the columns $A_j$ are constant on the half-open circular arc $(a,a+G]$.
Here a position of residue zero means column $m$.
Retain the positions at distances $M+1,\ldots,G$ clockwise from $a$, including the next mark itself.
The corrections $E_j$ are supported at distances $1,\ldots,M$ clockwise after marked anchors.
Since no mark lies strictly inside the gap, these corrections vanish at every retained position.
There are $G-M\ge2L-M\ge L$ such positions, all with the same column value.
The largest gap supplies an actual column value occurring at least
\begin{equation*}
\frac{m}{\ell+1}-M\ge\frac{m}{2(\ell+1)}
\end{equation*}
times.

Extend $A_j$ periodically.
Its circular jump at residue $a$ is
\begin{equation}\label{eq:gap-jump}
A_{a+1}-A_a
=-\mathbf1_{a\equiv b}\mathbf1_{[\ell]}
+\sum_{i:t_i\equiv a}e_i.
\end{equation}
At residue zero the left side is $A_1-A_m$.
Indeed the circular derivative of $\mathbf1_{j\le t}$ is $-\mathbf1_{a\equiv t}+\mathbf1_{a\equiv0}$, including $t=0,m$.
Crossing free cluster $a$ changes the constant gap value by $w_a$; crossing the source cluster changes it by $-\sum_{a=1}^q w_a$.
The $w_a$ are independent because their supports are disjoint and nonempty.
The $q+1$ actual gap values therefore have affine dimension $q$ and are affinely independent.
Choose the largest-gap value as $c_0$.
Their differences span all $w_a$ and supply the required repeated independent directions.
Together with~\eqref{eq:source-differences}, Lemma~\ref{lem:functional-rank} gives $d\ge(\ell+q)/2$.
\end{proof}

\begin{lemma}\label{lem:anchor-count}
For fixed $b,\ell,L,m$ satisfying $m\ge2(\ell+1)L$, the number of ordered anchor tuples $(t_1,\ldots,t_\ell)\in\{0,\ldots,m\}^\ell$ with $q$ free clusters is at most
\begin{equation}\label{eq:anchor-count}
A_\ell m^qL^{\ell-q},
\qquad A_\ell=(\ell+1)^{\ell+1}(8\ell+2)^\ell.
\end{equation}
\end{lemma}

\begin{proof}
Partition the labels $0,1,\ldots,\ell$ into their clusters, with label zero representing $b$.
There are at most $(\ell+1)^{\ell+1}$ partitions.
The least label of each free cluster has at most $m+1\le2m$ anchor choices.
Every other target lies at circular distance less than $2\ell L$ from its representative, which has at most $(8\ell+2)L$ possible linear anchors, counting both representatives of residue zero.
The resulting bound is~\eqref{eq:anchor-count}, since
$2^q(8\ell+2)^{\ell-q}\le(8\ell+2)^\ell$.
\end{proof}