\section{Collision pairs lie on rational graphs}\label{sec:graphs}
From now on we work inside the sector $\sect$ of \S\ref{sec:dictionary}
and with a large length $L$. Recall that a \emph{collision pair} is an ordered
pair $(v,w)$ of distinct primitive vectors of $\sect$ with $N(v)=N(w)\le L$, and
that its \emph{collision vector} is $z=(v,w)\in\bZ^4$. If $w=kv$ with
$k\in\cK$, then $w=v$ by Lemma~\ref{lem:dictionary}(b); so the two members
of a collision pair are never related by an element of $\cK$.

Throughout this section and the next, $\kappa$ and $C_{\mathrm{sep}}$ denote the
constants of Proposition~\ref{prop:turn}(b) and Lemma~\ref{lem:excision}(c),
and $C_{\mathrm{exc}}$ the constant of Definition~\ref{def:excision}.

\subsection{The rank reduction}
Fix a parameter $A_0\ge1$ and put
\begin{equation}\label{eq:B0}
 B_0:=\max\Bigl\{A_0,\ \frac{C_{\mathrm{sep}}A_0+4}{\kappa}\Bigr\},
 \qquad\text{so that}\qquad \kappa B_0\ge C_{\mathrm{sep}}A_0+4 ;
\end{equation}
define the \emph{coarse level} $H_{\mathrm c}$, the \emph{fine level} $H_{\mathrm f}$ and
the \emph{normal bound} $M_1$ by
\[
 H_{\mathrm c}:=\lceil A_0\log(2+L)\rceil,\qquad
 H_{\mathrm f}:=\lceil B_0\log(2+L)\rceil,\qquad
 M_1:=C_1L^3 ,
\]
where $C_1$ is the constant appearing in \eqref{eq:normal-size} below. If
$A_0$ is sufficiently large, then $H_{\mathrm c}\ge C_{\mathrm{exc}}\log(2+M_1)$ for
all $L\ge1$, so the $(M_1,H_{\mathrm c})$-excision of Definition~\ref{def:excision}
is defined.

We call a primitive vector of $\sect$ with $N\le L$
\emph{deleted} if it is excised by the $(M_1,H_{\mathrm c})$-excision or lies on a
ray of the fan $\mathcal F_{H_{\mathrm f}}$, and \emph{retained} otherwise. A
collision pair is retained if both its members are.

\begin{lemma}\label{lem:ranktwo}
Let $A_0$ be sufficiently large.
\begin{enumerate}
\item The number of deleted vectors is at most $CL^2/A_0+C_{A_0}L\log^2L$,
with $C$ independent of $A_0$.
\item If $L$ is sufficiently large in terms of $A_0$, then for every
ordered pair $(\Sigma,\Sigma')$ of Farey sectors of level
$H_{\mathrm f}$, the collision vectors of the retained collision pairs
$(v,w)\in\Sigma\times\Sigma'$ span a subspace of $\bR^4$ of dimension at
most two.
\end{enumerate}
\end{lemma}

\begin{proof}
(a) By Lemma~\ref{lem:excision}(b), the $(M_1,H_{\mathrm c})$-excision deletes at
most
\[
 C\,\frac{\log(2+M_1)}{H_{\mathrm c}}\,L^2+CL\log^2(2+M_1)+CH_{\mathrm c}^2
\]
vectors, and
$\log(2+M_1)\le C\log(2+L)$, so this is at most $CL^2/A_0+C_{A_0}L\log^2L$.
The rays of $\mathcal F_{H_{\mathrm f}}$ carry at most $CH_{\mathrm f}^2\le C_{A_0}\log^2L$
primitive vectors.

(b) Fix $(\Sigma,\Sigma')$. Let $\lambda_\Sigma$ be the inward supporting
functional at one boundary vector of $\Sigma$, as in
Proposition~\ref{prop:turn}(b), and similarly $\lambda_{\Sigma'}$. For a
primitive $v\in\Sigma$ with $N(v)\le L$ choose a supporting functional
$\gamma$ at $v$; then $N(v)=\gamma(v)$ and
$|\gamma-\lambda_\Sigma|\le Ce^{-\kappa H_{\mathrm f}}$ by
Proposition~\ref{prop:turn}(b), so
\begin{equation}\label{eq:eta}
 |N(v)-\lambda_\Sigma(v)|\le|\gamma-\lambda_\Sigma|\,|v|\le\eta:=CLe^{-\kappa H_{\mathrm f}},
\end{equation}
using $|v|\le N(v)/c\le CL$. The same holds for $w\in\Sigma'$ with
$\lambda_{\Sigma'}$.

Consider the linear form
\[
 \ell:=(\lambda_\Sigma,-\lambda_{\Sigma'})\ \text{ on }\bR^4,\qquad
 \ell(v,w)=\lambda_\Sigma(v)-\lambda_{\Sigma'}(w).
\]
Its norm satisfies $c\le|\ell|\le C$. If $z=(v,w)$ is the collision
vector of a retained collision pair in $\Sigma\times\Sigma'$, then
$N(v)=N(w)$ and \eqref{eq:eta} give
\begin{equation}\label{eq:ell-small}
 |z|\le CL,\qquad|\ell(z)|\le2\eta .
\end{equation}

\emph{Dimension four is impossible.} Suppose $z_1,\dots,z_4$ are linearly
independent collision vectors as above. Their determinant is a nonzero
integer. Write $z_i=t_i\hat\ell+z_i^\perp$ with $\hat\ell=\ell/|\ell|$
(viewing $\ell$ as a vector of $\bR^4$), $t_i=\ell(z_i)/|\ell|$ and
$z_i^\perp\perp\hat\ell$. In the expansion of the determinant by
multilinearity, the term with no factor $\hat\ell$ vanishes because the
$z_i^\perp$ lie in a three-dimensional space, and so do the terms with two
or more factors $\hat\ell$. Each of the four remaining terms is bounded by
$|t_i|$ times a three-dimensional volume of vectors of norm at most $CL$.
Hence
\[
 1\le|\det(z_1,\dots,z_4)|\le4\cdot\frac{2\eta}{|\ell|}(CL)^3\le CL^4e^{-\kappa H_{\mathrm f}}.
\]
Since $e^{-\kappa H_{\mathrm f}}\le(2+L)^{-\kappa B_0}$ and $\kappa B_0>4$ by
\eqref{eq:B0}, this is impossible for large $L$.

\emph{Dimension three is impossible.} Suppose the span $W$ of the
collision vectors is three-dimensional. Since $W$ is spanned by integral
vectors, it has a primitive integral normal vector $\nu=(\alpha,\beta)$,
$\alpha,\beta\in\bZ^2$, unique up to sign. Choose linearly independent
collision vectors $z_1,z_2,z_3\in W$. Under the identification
$\Lambda^3\bR^4\cong\bR^4$, the exterior product $z_1\wedge z_2\wedge z_3$
is an integral vector orthogonal to $W$, hence a nonzero integer multiple
of $\nu$. Therefore the three-dimensional volume $\operatorname{vol}_3(z_1,z_2,z_3)$
is at least $|\nu|$, while it is at most $(CL)^3$; so
\begin{equation}\label{eq:normal-size}
 |\nu|\le C_1L^3=M_1 .
\end{equation}

Every $z\in W$ can be written $z=\sum c_iz_i$, and by Cramer's rule
\[
 |c_i|\le|z|\,\frac{\operatorname{vol}_2(z_k,z_m)}{\operatorname{vol}_3(z_1,z_2,z_3)}\le\frac{|z|(CL)^2}{|\nu|},
 \qquad\{k,m\}=\{1,2,3\}\setminus\{i\}.
\]
With
\eqref{eq:ell-small} this gives
\begin{equation}\label{eq:ell-on-W}
 |\ell(z)|\le\varepsilon|\ell|\,|z|\quad(z\in W),\qquad
 \varepsilon:=\frac{CL^3e^{-\kappa H_{\mathrm f}}}{|\nu|}\le CL^3e^{-\kappa H_{\mathrm f}}.
\end{equation}

Decompose $\ell=\ell_W+\ell_\perp$ with $\ell_W\in W$ and
$\ell_\perp\in\bR\nu$; then $|\ell_W|\le\varepsilon|\ell|$, so the angle
between $\ell$ and the line $\bR\nu$ is at most $\pi\varepsilon/2$, and
$\nu/|\nu|=\pm\ell/|\ell|+O(\varepsilon)$ in $\bR^4$. Comparing second
blocks gives
\[
 \frac{\beta}{|\nu|}=\mp\frac{\lambda_{\Sigma'}}{|\ell|}+O(\varepsilon).
\]
Since $|\lambda_{\Sigma'}|/|\ell|\ge c$ and $\varepsilon\to0$ as
$L\to\infty$ (because $\kappa B_0>3$), for large $L$ we obtain $\beta\ne0$,
$|\beta|\ge c|\nu|$, and
\begin{equation}\label{eq:beta-angle}
 \angle\bigl(\lambda_{\Sigma'},\{\beta,-\beta\}\bigr)\le C\varepsilon\le CL^3e^{-\kappa H_{\mathrm f}}.
\end{equation}

Now let $w\in\Sigma'$ be the second member of one of the retained
collision pairs spanning $W$, and let $\gamma$ be a supporting functional
at $w$. By Proposition~\ref{prop:turn}(b), $|\gamma-\lambda_{\Sigma'}|\le Ce^{-\kappa H_{\mathrm f}}$,
so by \eqref{eq:beta-angle} $\angle(\gamma,\{\beta,-\beta\})\le CL^3e^{-\kappa H_{\mathrm f}}$.
On the other hand $\beta$ is a nonzero integral form with
$|\beta|\le|\nu|\le M_1$, and $w$ is retained by the $(M_1,H_{\mathrm c})$-excision,
so Lemma~\ref{lem:excision}(c) gives
$\angle(\gamma,\{\beta,-\beta\})\ge ce^{-C_{\mathrm{sep}}H_{\mathrm c}}$. Combining the two bounds gives
\[
 ce^{-C_{\mathrm{sep}}H_{\mathrm c}}\le CL^3e^{-\kappa H_{\mathrm f}},\qquad\text{that is,}\qquad
 (2+L)^{\kappa B_0-C_{\mathrm{sep}}A_0-3}\le C ,
\]
which contradicts the choice \eqref{eq:B0} of $B_0$ for large $L$. Hence $\dim W\le2$.
\end{proof}

\subsection{Graph pieces, degenerate pieces, and two complexity bounds}
\label{sec:pieces}
Keep the notation of Lemma~\ref{lem:ranktwo}, and let $L$ be large enough
for Lemma~\ref{lem:ranktwo}(b). Fix an ordered pair
$(\Sigma,\Sigma')$ of sectors of level $H_{\mathrm f}$, let $W\subset\bR^4$ be the
span of the collision vectors of the retained collision pairs in
$\Sigma\times\Sigma'$, a rational subspace of dimension at most two, and
let $\pi_1,\pi_2:\bR^4\to\bR^2$ be the two coordinate projections. There
are three cases.

\begin{enumerate}
\item[(a)] Suppose $\dim W\le1$. Two proportional collision vectors $(v,w)$ and
$t(v,w)$ with $v,tv$ primitive in $\sect$ have $t=1$; so there is at most
one retained collision pair in $\Sigma\times\Sigma'$.
\item[(b)] Suppose $\dim W=2$ and one of $\pi_1(W)$, $\pi_2(W)$ is a line. Say
$\pi_1(W)$ is a line; it contains at most one primitive vector $v$ of
$\sect$, and the partners $w$ of $v$ lie on the curve $\{N=N(v)\}$. The
unit squares centred at the lattice points of this curve are disjoint and
contained in the region $\{N(v)-C\le N\le N(v)+C\}$, which has area
$O(L+1)$. Hence there are at most $C(L+1)$ retained collision pairs in
$\Sigma\times\Sigma'$. The same bound holds if $\pi_2(W)$ is a line.
\item[(c)] Suppose $\dim W=2$ and both projections are two-dimensional. Then $W$
is the graph of the linear map $G=\pi_2\circ(\pi_1|_W)^{-1}$, which lies
in $\GL_2(\bQ)$ because $W$ is rational, and every retained collision pair
in $\Sigma\times\Sigma'$ has the form $(v,Gv)$. We then call the set of
these pairs the \emph{graph piece} of $(\Sigma,\Sigma')$ and
$G=G_{\Sigma,\Sigma'}$ its matrix; $G\notin\cK$ by the remark at the
beginning of the section.
\end{enumerate}

In cases (a) and (b) we speak of a \emph{degenerate piece}. The fan of
level $H_{\mathrm f}$ has $O(H_{\mathrm f}^2)$ sectors, hence $O(H_{\mathrm f}^4)=O_{A_0}(\log^4L)$
ordered sector pairs; so
\begin{equation}\label{eq:degenerate}
 \text{the degenerate pieces contain }O_{A_0}(L\log^4L)=o_{A_0}(L^2)
 \text{ retained collision pairs in total.}
\end{equation}

For $G\in\GL_2(\bQ)$ we define the \emph{input lattice} and the
\emph{output lattice}
\[
 \Lambda_{\rm in}(G):=\bZ^2\cap G^{-1}\bZ^2,\qquad
 \Lambda_{\rm out}(G):=G\Lambda_{\rm in}(G)=\bZ^2\cap G\bZ^2 ;
\]
thus $\Lambda_{\rm in}(G)$ is the set of integral $v$ with $Gv$ integral,
and both lattices have finite index in $\bZ^2$. We write
\[
 I_{\rm in}(G):=[\bZ^2:\Lambda_{\rm in}(G)],\qquad
 I_{\rm out}(G):=[\bZ^2:\Lambda_{\rm out}(G)],\qquad
 I(G):=\max\{I_{\rm in}(G),I_{\rm out}(G)\}
\]
for the two indices and the \emph{index} of $G$, $h(G):=\max_{i,k}|G_{ik}|$
for its \emph{entry height}, and $q(G)$ for the least positive integer
with $q(G)G$ integral.

\begin{lemma}\label{lem:indices}
Let $G\in\GL_2(\bQ)$ and $R\ge1$.
\begin{enumerate}
\item Let $\mathcal P$ be a set of pairs $(v,Gv)$ with
$v\in\Lambda_{\rm in}(G)$, $|v|\le R$ and $|Gv|\le R$, and assume that
$\mathcal P$ contains two pairs whose first members are linearly
independent. Then $|\mathcal P|\le CR^2/I(G)$.
\item The integer $q(G)$ divides $I_{\rm in}(G)$, and
$|\det G|=I_{\rm out}(G)/I_{\rm in}(G)$; in particular $|\det G|\le I(G)$.
\end{enumerate}
\end{lemma}

\begin{proof}
(a) Let $(v_1,Gv_1),(v_2,Gv_2)\in\mathcal P$ with $v_1,v_2$ independent.
The lattice $\Lambda_{\rm in}(G)$ contains the lattice spanned by
$v_1,v_2$, whose covering radius is at most $|v_1|+|v_2|\le2R$; so the
covering radius of $\Lambda_{\rm in}(G)$ is at most $2R$, and its Voronoi
cells have diameter at most $4R$. The Voronoi cells centred at the first
members $v$ of the pairs in $\mathcal P$ are pairwise disjoint, have area
$I_{\rm in}(G)$, and lie in the disc of radius $5R$; hence
$|\mathcal P|\le25\pi R^2/I_{\rm in}(G)$.

The same argument with the second members $Gv\in\Lambda_{\rm out}(G)$,
which include the independent vectors $Gv_1,Gv_2$, gives
$|\mathcal P|\le25\pi R^2/I_{\rm out}(G)$.

(b) The index $n=I_{\rm in}(G)$ annihilates
$\bZ^2/\Lambda_{\rm in}(G)$, so $n\bZ^2\subset\Lambda_{\rm in}(G)$ and
$nG\bZ^2\subset\bZ^2$; thus $nG$ is integral and $q(G)\mid n$. The
determinant identity expresses that $G$ multiplies covolumes by
$|\det G|$.
\end{proof}

\begin{lemma}\label{lem:height}
Let $G\in\GL_2(\bQ)$ with $h(G)>10(1+|\det G|)$. Then the set of lines
\[
 \{\bR x:\ x\in\bR^2\setminus\{0\},\ N(Gx)=N(x)\}
\]
has exactly two elements.
In particular, at most two primitive vectors $v\in\sect$ satisfy
$N(Gv)=N(v)$.
\end{lemma}

\begin{proof}
\emph{Step 1: the case $|\tr M|>1+\det M$.} Let $M$ be a real $2\times2$ matrix with $\det M>0$ and
$|\tr M|>1+\det M$. Then $N(Mx)=N(x)$ holds for exactly two directions
$x$. Indeed, the discriminant $(\tr M)^2-4\det M>(1-\det M)^2\ge0$ shows
that $M$ has two distinct real eigenvalues of the same sign. Replacing $M$
by $-M$, which changes neither $\det M$ nor the equation since $N$ is even,
we may take them positive, $\lambda_1>\lambda_2>0$. Then
$\lambda_1+\lambda_2>1+\lambda_1\lambda_2$ means
$(\lambda_1-1)(1-\lambda_2)>0$, so $\lambda_1>1>\lambda_2$.

Let $x_1,x_2$ be eigenvectors for $\lambda_1,\lambda_2$. On the
eigenlines, $N(Mx_1)=\lambda_1N(x_1)\ne N(x_1)$ and
$N(Mx_2)=\lambda_2N(x_2)\ne N(x_2)$. Every other direction is represented
by $\varepsilon tx_1+x_2$ with $t>0$ and $\varepsilon=\pm1$.

Fix $\varepsilon$ and put $f(t):=N(\varepsilon tx_1+x_2)$, a positive, strictly
convex, locally Lipschitz function of $t\ge0$ with $f(t)/t\to N(x_1)$ as
$t\to\infty$; let $t_*\ge0$ be its minimizer. With
$k:=\lambda_1/\lambda_2>1$ the equation
$N(M(\varepsilon tx_1+x_2))=N(\varepsilon tx_1+x_2)$ reads $F(t)=0$ with
\[
 F(t):=\lambda_2f(kt)-f(t).
\]
For $t\le t_*/k$ we have $t\le kt\le t_*$, so $f(kt)\le f(t)$ and
$F(t)\le(\lambda_2-1)f(t)<0$. For almost every $t>t_*/k$ we have
$F'(t)=\lambda_1f'(kt)-f'(t)>0$: if $t\le t_*$ then $f'(t)\le0<f'(kt)$,
and if $t>t_*$ then $f'(kt)\ge f'(t)>0$ because $f'$ is nondecreasing, so
$F'(t)\ge(\lambda_1-1)f'(t)>0$. Hence $F$ is strictly increasing on
$[t_*/k,\infty)$, with $F(t_*/k)<0$ and $F(t)/t\to(\lambda_1-1)N(x_1)>0$.
So $F$ has exactly one zero for each $\varepsilon$, and $N(Mx)=N(x)$ has
exactly two solution directions.

\emph{Step 2: reduction to Step 1.} Let $G$ be as in the lemma. If $\det G<0$, replace $G$ by
$M:=sG$, where $s=\left(\begin{smallmatrix}-1&1\\0&1\end{smallmatrix}\right)$ is the generator of $\cK$ of determinant $-1$;
since $N\circ s=N$ this does not change the solution set, and
$h(G)\le2h(M)$ because $G=sM$ and $s$ has entries in $\{0,\pm1\}$ with at
most two nonzero entries per row. Otherwise put $M:=G$.

Write
$M=\left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right)$,
$\delta:=\det M>0$, $\sigma:=\tr M=a+d$ and $\tau:=\tr(rM)=c-b+d$, where
$r=\left(\begin{smallmatrix}0&1\\-1&1\end{smallmatrix}\right)$ is the generator of $\cK$ of order six; then
$\tr(r^2M)=\tau-\sigma$, and $M$, $rM$, $r^2M$ all have determinant
$\delta$ and the same solution set, since $N\circ r=N$.

If one of
$|\sigma|,|\tau|,|\tau-\sigma|$ exceeds $1+\delta$, Step 1 applies to the
corresponding matrix and we are done. Otherwise
$|\sigma|,|\tau|\le1+\delta$. Substituting $a=\sigma-d$ and $c=\tau+b-d$
into $\delta=ad-bc$ gives
\[
 b^2-bd+d^2=\sigma d-\tau b-\delta\le(1+\delta)(|b|+|d|)
 \le\sqrt2\,(1+\delta)\,|(b,d)|,
\]
and $b^2-bd+d^2\ge|(b,d)|^2/2$, so $|(b,d)|\le2\sqrt2\,(1+\delta)$. Then
\[
 |a|\le|\sigma|+|d|\le(1+2\sqrt2)(1+\delta),\qquad
 |c|\le|\tau|+|b|+|d|\le(1+\delta)+\sqrt2\,|(b,d)|\le5(1+\delta),
\]
so $h(M)\le5(1+\delta)$ and $h(G)\le10(1+\delta)=10(1+|\det G|)$, contrary
to the hypothesis. Hence the first case occurs.
\end{proof}

\subsection{Summary of the reduction}
We apply Lemmas~\ref{lem:indices} and \ref{lem:height} to the graph pieces
of the $O_{A_0}(\log^4L)$ sector pairs of level $H_{\mathrm f}$. A graph piece
contains two pairs with independent first members (its collision vectors
span a plane), and every pair $(v,Gv)$ in it satisfies $|v|,|Gv|\le CL$; so by
Lemma~\ref{lem:indices}(a) it contains at most $CL^2/I(G)$ pairs. Hence the
graph pieces with $I(G)>(\log L)^5$ contain $O_{A_0}(L^2/\log L)$ retained
collision pairs in total. By Lemma~\ref{lem:height}, a graph piece with
$h(G)>10(1+|\det G|)$ contains at most two pairs, so these pieces contain
$O_{A_0}(\log^4L)$ pairs in total. Together with the bound \eqref{eq:degenerate} for the
degenerate pieces we conclude:
\begin{equation}\label{eq:initialgraphs}
 \begin{minipage}{0.86\textwidth}
 all but $o_{A_0}(L^2)$ of the retained collision pairs lie on graph pieces
 whose matrix $G\in\GL_2(\bQ)\setminus\cK$ satisfies
 \[
  I(G)\le(\log L)^5\qquad\text{and}\qquad h(G)\le10(1+|\det G|)\le10(1+I(G)).
 \]
 \end{minipage}
\end{equation}