\section{Introduction}

Let $\mu$ be a fixed nontrivial finitely supported measure on $\mathbf{Z}$, say $\mu = (\delta_{-1} + \delta_1) /2$.
Let $\M_n(\mu)$ denote the distribution of $n \times n$ matrices whose entries are independent with distribution $\mu$. Let $M \sim \M_n(\mu)$ and let $\phi(t) = \det (t - M)$ be the characteristic polynomial of $M$.
The following conjecture is due to Babai (1970s) and Vu--Wood (2009) (see \cite{vu-survey}*{Conjecture~11.1}).

\begin{conjecture}[Babai, Vu--Wood]
  \label{main-conjecture}
  $\phi$ is irreducible with high probability.\footnote{Throughout the paper we use the phrase ``with high probability'' to mean with probability $1 - o(1)$ as $n \to \infty$.
    Any stronger bounds are made explicit.}
\end{conjecture}

In this paper we will prove the above conjecture under certain conditions,
specified in the following two theorems.

\begin{theorem}
  \label{main-four-prime-case}
  Assume there is a product of four distinct primes $N = p_1 p_2 p_3 p_4$ such that $\mu \bmod N$ is uniform.
  Then with high probability $\phi$ is irreducible and $\opr{Gal}(\phi) \geq A_n$.
\end{theorem}

\begin{theorem}
  \label{main}
  Assume the extended Riemann hypothesis \textup{(ERH)}\footnote{The Riemann hypothesis for a number field $K$ asserts that the Dedekind zeta function $\zeta_K(z)$ has no zeros with $\Re z > 1/2$. The extended Riemann hypothesis asserts that the Riemann hypothesis holds for all number fields $K$.}.
  Then with high probability $\phi$ is irreducible and $\opr{Gal}(\phi) \geq A_n$.
  Quantitatively,
  \begin{align*}
    \mathbf{P}(\phi~\textup{irreducible})
     & = 1 - O(e^{-cn}),
    \\
    \mathbf{P}(\opr{Gal}(\phi) \geq A_n)
     & = 1 - O(e^{-cn^{1/2}}),
  \end{align*}
  where $c$ and the implicit constants depend on $\mu$.
\end{theorem}

Distinguishing between $A_n$ and $S_n$ remains open,
but presumably $\opr{Gal}(\phi)=S_n$ with high probability.

\subsection{Method}

Conjecture~\ref{main-conjecture} parallels a conjecture of Odlyzko and Poonen~\cite{OP} about random polynomials.
The Odlyzko--Poonen conjecture predicts that a random polynomial of degree $n$ with coefficients drawn independently at random from a nontrivial finitely supported measure $\mu$ is irreducible with probability $1-o(1)$.
This conjecture has recently been settled under conditions analogous to those above
by Bary-Soroker and Kozma~\cite{BSK}
and Breuillard and Varj\'u~\cite{BV},
respectively.
Both papers additionally prove that the Galois group is at least $A_n$, as above.

Both \cite{BSK} and \cite{BV} use a local-to-global principle to reduce the problem to a question about random polynomials mod $p$.
The difference between the methods is mainly the size of $p$.
The method of \cite{BSK} uses bounded primes, specifically the four primes specified in the hypothesis.
The reduction of the polynomial modulo any of these primes is uniform and hence its factorization is well-understood.
Moreover, the factorizations modulo different primes are independent.
One then proves that with high probability there can be no factorization upstairs that is compatible with the four factorizations downstairs.

On the other hand the method of \cite{BV} uses large primes.
It is a consequence of the prime ideal theorem that
for any fixed polynomial $\phi$
the number of roots of $\phi \bmod p$ is, on average over $p$,
equal to the number of distinct irreducible factors of $\phi$.
Hence if one can show that $\phi$ has only one root mod $p$ on average over large $p$ then it follows that $\phi$ is irreducible
or, possibly, a proper power,
an intuitively remote possibility that must be ruled out specially.
The size of $p$ is determined by the error term in the prime ideal theorem, which is how ERH comes into play.

In this paper we adapt both methods to the case of a characteristic polynomial $\phi(t) = \det(t - M)$.
At the level of detail just explained, nothing changes.
However, the local problem is completely different.
Whereas for random polynomials one needs to understand the roots of random polynomials mod $p$,
for the characteristic polynomial of a random matrix one needs to understand the eigenvalues of a random matrix mod $p$.

For the proof of Theorem~\ref{main-four-prime-case} one may use the fact that the characteristic polynomial of a uniformly random matrix mod $p$ is little different from a uniformly random polynomial,
apart from the smallest irreducible factors.

For the proof of Theorem~\ref{main}, one needs to understand the number of eigenvalues of $M$ mod $p$ for large $p$, say $p \approx e^{cn}$.
This problem has been studied in random matrix theory,
but we need a more general version of the closest result in the literature.

\subsection{The local problem}

Since $\lambda$ is an eigenvalue of $M$ if and only if $M - \lambda$ is singular, as far as the first moment goes it suffices to understand the singularity probability of a random matrix with independent (but not identically distributed) entries.

We will prove the following general result, of independent interest.
Let $q$ be an arbitrary prime power.
A measure $\mu$ on $\mathbf{F}_q$ is called \emph{$\alpha$-balanced} if
$\mu(x+H) \leq 1 - \alpha$ for every $x \in \mathbf{F}_q$ and every proper subgroup $H < \mathbf{F}_q$.
Let $\bm{\mu} = (\mu_{ij})_{1 \leq i,j\leq n}$ be a matrix of $\alpha$-balanced measures on $\mathbf{F}_q$, and let $\M(\bm{\mu})$ denote the distribution of matrices $M \in \M_n(q)$ with independent entries and $M_{ij} \sim \mu_{ij}$.

\begin{theorem}
  \label{thm:prob-M-nonsingular}
  For $M \sim \M(\bm{\mu})$,
  \[
    \mathbf{P}(M~\textup{nonsingular})
    = \prod_{i=1}^\infty (1-1/q^i) + O_\alpha(e^{-c\alpha n}).
  \]
\end{theorem}

For the purpose of proving Theorem~\ref{main}, we do not need the full strength here.
It would suffice to assume that $q$ is prime
and that each $\mu_{ij}$ is a translate of a common measure $\mu$,
and to establish a main term of the form $1-1/q+O(1/q^2)$,
but the full generality is interesting and not much more difficult.

Theorem~\ref{thm:prob-M-nonsingular}
is close to a result of Maples~\cite{maples} and Nguyen--Paquette~\cite{nguyen-paquette}*{Appendix~A}.
Our statement is more special in that we consider only constant $\alpha$,
but more general in that we do not assume the entries are identically distributed.
To prove this we follow \cites{maples, nguyen-paquette} closely,
making changes where necessary
and simplifications where possible.
(The recent paper \cite{LMN} is also relevant, but does not provide an exponential error bound, which is crucial for us.)

Theorem~\ref{thm:prob-M-nonsingular} is sufficient for proving the irreducibility part of Theorem~\ref{main},
but to prove that $\opr{Gal}(\phi) \geq A_n$ we must also bound correlations of eigenvalues.
For $\lambda \in \mathbf{F}_q$ let $E_\lambda$ be the event that $\lambda$ is an eigenvalue of $M$.
The following result is the most novel and most technical contribution of the paper.

\begin{theorem}
  \label{thm:correlation-bound}
  Assume $m < c \log n$ and $C \leq \log q < c (\alpha n)^{1/2} / m^{3/2}$.
  For $M \sim \M(\bm{\mu})$ and distinct $\lambda_1, \dots, \lambda_m \in \mathbf{F}_q$,
  \[
    \mathbf{P}(E_{\lambda_1} \cap \cdots \cap E_{\lambda_m})
    \leq (q-1)^{-m} + O_\alpha \br{\exp(-c (\alpha n)^{1/2} / m^{3/2})}.
  \]
\end{theorem}

\subsection{Dependence on CFSG}

The $\opr{Gal}(\phi) \geq A_n$ part of Theorem~\ref{main} is proved
by showing that $\opr{Gal}(\phi)$ is $m$-transitive with high probability for any constant $m$, and
then appealing to the following fact.

\begin{fact}
  \label{6trans}
  There is a constant $m$
  such that if $G \leq S_n$ and $G \ngeq A_n$
  then $G$ is at most $m$-transitive.
\end{fact}

This follows from the classification of finite 2-transitive groups,
which is a deep consequence of the classification of finite simple groups (CFSG),
and depends on detailed knowledge of the finite simple groups.
One may take $m = 5$, or even $m = 3$ for $n > 24$.
Alternatively, it follows from the Schreier conjecture, another hopelessly deep consequence of CFSG.
See \cite{dixon--mortimer}*{Section~7.3}.

Long before CFSG, Wielandt proved that any group not containing $A_n$ is at most $C\log n$-transitive, where $C \approx 1.998$ (see \cite{neumann}*{Section~2}; see \cite{dixon--mortimer}*{Theorem~5.5B} for a simplified proof with a slightly worse constant).
This appears to be where CFSG-free matters stand,
even after some 85 years.
The largest we can take $m$ in our proof is $(1 - o(1))\log_2 n$,
which is unfortunately a factor of about $1.4$ too small
to conflict with Wielandt's bound.

\subsection{Symmetric matrices}

It would be interesting to have variants of Theorems~\ref{main-four-prime-case} and \ref{main} in the case of random symmetric matrices,
including for example the adjacency matrix of a random graph.
It is known (first proved in \cite{CTV}) that a random symmetric matrix is nonsingular with high probability.
In the best-studied case of $\pm1$ entries, the strongest methods \citelist{\cite{ferber--jain}\cite{CM3}} prove this precisely by reducing mod $p$ for some prime $p \approx \exp(cn^{1/2})$
and showing that $M$ is nonsingular mod $p$ with high probability.
If one could prove that this probability is in fact close to $1-1/p$,
and if one could additionally allow an arbitrary shift in the diagonal entries (cf.~\cite{CTV}*{Section~6.4}),
then, assuming ERH, it would follow immediately by the \cite{BV} method that $\phi(t) = \det(t - M)$ is irreducible with high probability.

\subsection{Notation}

Asymptotic notation is used incessantly, especially $O$ and $o$ notation.
Subscripted $O_\alpha$ warns that the implicit constant depends on $\alpha$.
We do not track explicitly the dependency on $\mu$, but it will not tax the motivated reader to work it out.
The notation $X \lesssim Y$ means $X \leq O(Y)$ (equivalent to number theorists' $\ll$), while $X \asymp Y$ means $X \lesssim Y$ and $X \gtrsim Y$.
Often we will simply write $C$ or $c$ to denote constants, $C$ suggesting a big constant and $c$ a little constant.
Such constants may change from line to line, though we will sometimes write $c'$ to warn that the constant has changed.

If $\mu$ is a probability measure we write $X \sim \mu$ to mean that $X$ is a random variable with law $\mu$.
We will occasionally write $X \sim S$ for a finite set $S$ to mean that $X$ is uniformly distributed on $S$, as in $M \sim \M_n(q)$, where $\M_n(q)$ denotes the set of $n\times n$ matrices over $\mathbf{F}_q$.

In the later sections of the paper we write $[n]$ for $\{1, \dots, n\}$.

\subsection*{Acknowledgements}

I am grateful to
P\'eter Varj\'u and Emmanuel Breuillard for advice and encouragement,
Hoi Nguyen for a discussion about Maples's method,
Kyle Luh for the proof of Proposition~\ref{one-simple-eig},
Bhargav Narayanan for discussions about the sparse problem in Section~\ref{sec:local-problem-part-2},
and Laci Pyber for comments on Wielandt's transitivity bound.

\section{The four prime method}

In this section we use the \cite{BSK} method to prove Theorem~\ref{main-four-prime-case},
which applies to any measure $\mu$ which is uniform modulo the product of some four distinct primes $N = p_1 p_2 p_3 p_4$,
such as the uniform measure on $\{1, \dots, 210\}$.
We will apply several results directly from \cite{BSK}.

The reduction $\phi \bmod p_i$ is the characteristic polynomial of a uniform random matrix in $\M_n(p_i)$,
and these reductions are independent for different $p_i$.
The factorization of $\phi \bmod p_i$ can be compared with the factorization of a random permutation $\pi \in S_n$ into cycles,
and by considering the Frobenius elements we can glean information about $\opr{Gal}(\phi)$.
The reason we need four primes is the following theorem about random permutations.

\begin{theorem}[\citelist{\cite{PPR-invariable} \cite{EFG-invariable}}]
  Say that $\pi_1, \dots, \pi_k \in S_n$ \emph{invariably generate at least $A_n$} if $\langle \pi_1', \dots, \pi_k'\rangle \geq A_n$ whenever $\pi_i'$ is conjugate to $\pi_i$ for each $i$.
  Then four random permutations invariably generate at least $A_n$ with probability bounded away from zero (but three do not).
\end{theorem}

The following lemma makes precise the sense in which the factorization of $\phi \bmod p_i$ can be compared with the factorization of a random permutation.

\begin{lemma}
  \label{TV}
  For $\Lambda$ a random partition of $n$ with some distribution, let $\Lambda_r$ denote the subsequence of parts of size at least $r$.
  For $\Lambda$ generated in any of the following ways the corresponding distributions $\Lambda_r$ are within $o(1)$ in total variation distance as $r,n \to \infty$:
  \begin{enumerate}[(1)]
    \item\label{distMn} the degrees of the irreducible factors of $\phi(t) = \det(t-M)$ where $M \sim \M_n(q)$, for any prime power $q$;
    \item\label{distGLn} the same but with $M \sim \opr{GL}_n(q)$;
    \item\label{distPn} the degrees of the irreducible factors of a uniformly random monic polynomial $\phi$ of degree $n$ mod $q$, for any prime power $q$;
    \item\label{distSn} the cycle lengths of a random permutation $\pi \sim S_n$;
    \item\label{distZn} the partition consisting of $Z_i$ copies of $i$ for each $i \geq 1$, where $Z_1, Z_2, \dots$ are independent Poisson random variables with $\mathbf{E} Z_i = 1/i$, conditional on $\sum_{i \geq 1} i Z_i = n$.
  \end{enumerate}
\end{lemma}
\begin{proof}
  The equivalence \ref{distGLn} $\iff$ \ref{distPn} is proved in \cite{hansen-schmutz}.
  The equivalence of \ref{distPn} and \ref{distSn} is \cite{BSK}*{Lemma~6}.
  The distributions \ref{distSn} and \ref{distZn} are equivalent.
  The only link which does not seem to be in the literature is the least surprising one \ref{distMn} $\iff$ \ref{distGLn}.

  In any case, these and many other distributions are treated uniformly by \cite{ABT}.
  See particularly \cite{ABT}*{Theorem~3.2}, with $\theta=1$.
  Let $C_d$ be the number of parts of $\Lambda$ of size $d$.
  The only hypothesis necessary about $\Lambda$, which we must check, is that there are independent random variables $(Z_d : d \geq 1)$ satisfying the conditioning relation (CR)
  \[
    \mathbf{P}(C_1=c_1, \dots, C_n=c_n)
    = \mathbf{P}\br{Z_1=c_1, \dots, Z_n=c_n \;\middle|\; \sum_{d=1}^n d Z_d = n},
  \]
  and satisfying a technical condition called the uniform logarithmic condition (ULC),
  which asserts roughly that for large $d$ we may approximate $Z_d$ by a coin flip with expected value $1/d$: see \cite{ABT} for the precise formulation.

  We need not consider the distributions \ref{distSn} or \ref{distZn}, because \cite{ABT} uses \ref{distZn} as the reference distribution, and \ref{distSn} is equivalent.
  The distribution \ref{distPn} is covered by \cite{ABT}*{Proposition~1.1}.
  Hence it suffices to check (CR) and (ULC) for \ref{distMn} and \ref{distGLn}.

  Consider \ref{distMn}.
  From \cite{reiner}, the number of $g \in \M_n(q)$ with characteristic polynomial $f_1^{n_1} \cdots f_k^{n_k}$, where $f_i$ is irreducible and monic of degree $d_i$, is
  \[
    q^{n^2-n} \frac{F(q, n)}{\prod_{i=1}^k F(q^{d_i}, n_i)},
  \]
  where
  \[
    F(q, n) = q^{-n^2} |\opr{GL}_n(q)| = (1-q^{-1}) \cdots (1-q^{-n}).
  \]
  Let $C_d$ be the number of irreducible factors of $\phi(t) = \det(t - M)$ of degree $d$ counting multiplicity, where $M \sim \M_n(q)$.
  Let $I(d)$ be the number of irreducible polynomials in $\mathbf{F}_q[t]$ of degree $d$.
  Then $\mathbf{P}(C_1=c_1, \dots, C_n=c_n)$ is the coefficient of $u_1^{c_1} \cdots u_n^{c_n}$ in
  \[
    F(q,n)
    \prod_{d \geq 1} \br{\sum_{c \geq 0}
      \frac{u_d^c}{q^{dc} F(q^d, c)}
    }^{I(d)},
  \]
  assuming $\sum d c_d = n$.
  For each $d \geq 1$ let $Z_d$ be an independent random variable with probability generating function
  \begin{equation}
    \label{Mn-Zgf}
    \sum_{c \geq 0} \mathbf{P}(Z_d = c) u^c
    = \br{\zeta_d^{-1} \sum_{c \geq 0} \frac{u^c}{q^{dc} F(q^d, c)}}^{I(d)},
  \end{equation}
  where the normalizing factor $\zeta_d$ is
  \[
    \zeta_d = \sum_{c \geq 0} \frac1{q^{dc} F(q^d, c)}
    = 1 + q^{-d} + O(q^{-2d}).
  \]
  Then it follows that, if $\sum d c_d = n$,
  \begin{align*}
    \mathbf{P}(C_1=c_1, \dots, C_n=c_n)
     & = F(q,n) \prod_{d \geq1} \zeta_d^{I(d)} \mathbf{P}(Z_d = c_d) \\
     & = \beta_n \mathbf{P}(Z_1 = c_1, \dots, Z_n = c_n),
  \end{align*}
  for some constant $\beta_n$ independent of $c_1, \dots, c_n$.
  Hence (CR) is satisfied.
  Moreover, from the definition of $Z_d$, using $I(d) = q^d/d + O(q^{d/2})$,
  \begin{align*}
    \mathbf{P}(Z_d = 1)
     & = \zeta_d^{-I(d)} \frac{I(d)}{q^d F(q^d, 1)} \\
     & = e^{-1/d} / d + O(q^{-d/2})
  \end{align*}
  and
  \begin{align*}
    \mathbf{P}(Z_d = l)
     & \lesssim \zeta_d^{-I(d)} \binom{I(d) + l - 1}{l} q^{-dl} \\
     & \leq O(I(d)/q^d)^l                                       \\
     & \leq O(1/d)^l.
  \end{align*}

  Hence (ULC) is satisfied with, in the notation of \cite{ABT}, $e(d) = O(1/d)$ and $c_l = e^{-l}$.

  The case of \ref{distGLn} is almost identical, but the factor $f(t) = t$ must be excluded.
  Let $I'(d) = I(d)$ for $d > 1$ and let $I'(1) = I(1) - 1 = q-1$.
  Let $\phi(t) = \det(t - M)$ where $M \sim \opr{GL}_n(q)$ and let $C_d$ be the number of irreducible factors of degree $d$.
  Then $\mathbf{P}(C_1 = c_1, \dots, C_n = c_n)$ is the coefficient of $u_1^{c_1} \cdots u_n^{c_n}$ in
  \[
    \prod_{d \geq 1} \br{ \sum_{c \geq 0} \frac{u_d^c}{q^{dc} F(q^d, c)}}^{I'(d)},
  \]
  provided $\sum d c_d = n$.
  The rest of the verification is the same but with $I'(d)$ in place of $I(d)$, which makes no essential difference.

  Hence for $\Lambda, \Lambda'$ defined by any of \ref{distMn}--\ref{distZn},
  \cite{ABT}*{Theorem~3.2} shows that $d_{\mathrm{TV}}(\Lambda_r, \Lambda'_r) \to 0$ as $r, n \to \infty$.
\end{proof}

\begin{remark}
  The proof leads to a bound on the total variation distance of $O(1/r)$ (see \cite{ABT-book}*{Theorem~6.9}).
  A more special analysis likely demonstrates an exponential bound,
  but such a bound is not useful to us due to more severe losses in other parts of the argument.
\end{remark}

We now return to the setting of a random matrix $M \sim \M_n(\mu)$
and its characteristic polynomial $\phi(t) = \det(t - M)$.

\begin{proposition}
  \label{four-prime-prop-1}
  Assume there is a product of four distinct primes $N = p_1 p_2 p_3 p_4$ such that $\mu \bmod N$ is uniform.
  Let $E$ be the event that there is some $d \in [n^{1/4}, n)$ such that
  for each $i \in \{1, 2, 3, 4\}$ the reduction
  $\phi \bmod p_i$ has a divisor of degree $d$.
  Then $\mathbf{P}(E) = o(1)$.
\end{proposition}
\begin{proof}
  Let $\delta > 0$ be a small constant.
  Let $d_i$ be the sum of the degrees of all irreducible factors $\psi \mid \phi \bmod p_i$ of degree $\deg \psi < n^\delta$.
  Then obviously $n-d_i$ is the sum of the degrees of the irreducible factors of degree at least $n^\delta$.
  By the previous lemma with $r = n^\delta$, $d_i$ may be compared to the analogous quantity for a random permutation.
  Applying, e.g., \cite{BSK}*{Lemma~5}, it follows that $d_i \leq 2 n^{\delta}$ with high probability.

  Hence $E$ is almost contained in the event $E'$ that there is some $d \geq n^{1/4}$ such that for each $i$ the reduction $\phi \bmod p_i$ has a divisor of degree in $[d - 2n^\delta, d]$
  made up only of irreducible factors of degree at least $n^\delta$.
  Since this event depends only on the large irreducible factors we may again apply the previous lemma to compare it with the analogous event for a random permutation.
  Applying \cite{BSK}*{Lemma~8}, it follows that $E'$ is unlikely (provided $\delta$ is sufficiently small).
\end{proof}

Hence with high probability $\phi$ does not have a divisor of degree larger than $n^{1/4}$.
Small-degree factors can be ruled out more straightforwardly,
using the fact that there are not many possibilities for low-degree eigenvalues,
and the result \cite{bourgain-vu-wood}*{Corollary~3.3} that each fixed $\lambda$ has an exponentially small probability of being an eigenvalue.
For example, see \cite{O'RW}*{Theorem~2.4} for the case of $\pm1$ random variables.
Hence with high probability $\phi$ is irreducible.

Finally, we claim that $\opr{Gal}(\phi) \geq A_n$ with high probability.
For this we need only assume that there is at least one prime $p$ such that $\mu \bmod p$ is uniform.

\begin{proposition}
  \label{four-prime-prop-2}
  Assume there is a prime $p$ such that $\mu \bmod p$ is uniform.
  Let $F$ be the event that $\opr{Gal}(\phi)$ is a transitive group other than $S_n$ or $A_n$.
  Then $\mathbf{P}(F) = o(1)$.
\end{proposition}
\begin{proof}
  Again let $\delta>0$ be a small constant.
  The reduction $\phi \bmod p$ is the characteristic polynomial of a random matrix $M \sim \M_n(p)$.
  Let $\Lambda$ be the partition of $n$ defined by the factorization of $\phi \bmod p$.
  Let $F'$ be the event that the parts of size smaller than $n^\delta$ can be adjusted so that $\Lambda$ becomes the cycle type of an element of some transitive group $G \ngeq A_n$.
  By Lemma~\ref{TV}, $F'$ may be compared with the analogous event for a random permutation.
  Hence, by \cite{BSK}*{Lemma~9}, $\mathbf{P}(F') = o(1)$.

  Moreover, the proof of \cite{BSK}*{Lemma~9} shows that $F \subset F'$.
  Briefly, the reduction $\phi \bmod p$ factorizes as
  \[
    \phi \bmod p = \psi_1 \psi_2 \qquad (\psi_1~\text{square-free}, \psi_2~\text{square-full}, \gcd(\psi_1, \psi_2) = 1),
  \]
  and with high probability $\deg \psi_2 < n^\delta$.
  Let $K$ be the splitting field of $\phi$, let $\mathfrak{p}$ be a prime over $p$, and let $k = K/\mathfrak{p}$ be the residue field, which is an extension of $\mathbf{F}_p$.
  The Frobenius automorphism of $k / \mathbf{F}_p$ lifts to an element of $\opr{Gal}(\phi) = \opr{Gal}(K/\mathbf{Q})$,
  and its cycle type restricted to the roots of $\phi$ lying over roots of $\psi_1$ is determined by the factorization of $\psi_1$.
  Hence $F \subset F'$, so $\mathbf{P}(F) = o(1)$.
\end{proof}

\begin{remark}
  The bounds proved in this section are rather poor.
  The proof of Proposition~\ref{four-prime-prop-1} gives a bound of $n^{-c}$ for some constant $c>0$.
  The proof of Proposition~\ref{four-prime-prop-2} gives only $(\log n)^{-c}$, though this could likely be improved to $n^{-c}$ with further work.
\end{remark}

\section{Global to local via the prime ideal theorem}
\label{sec:local-global}

\def\Primes{P}

In this section we reduce Theorem~\ref{main} to Theorems~\ref{thm:prob-M-nonsingular} and \ref{thm:correlation-bound}
using the \cite{BV} method.
Let $\Omega$ be the set of roots of $\phi$ in $\mathbf{C}$ and let $G = \opr{Gal}(\phi)$.
Let $R_\phi(p)$ be the number of roots of $\phi$ in $\mathbf{F}_p$.
It is a consequence of the prime ideal theorem
that $R_\phi(p)$ is on average close to the number of orbits $|\Omega / G|$;
in particular,
\[
  \phi~\text{irreducible (or a proper power)}
  \iff
  R_\phi(p) \sim 1 ~ \text{on average}.
\]
More generally for $m \geq 1$ the $m$th moment of $R_\phi(p)$ is $|\Omega^m/G| + o(1)$,
so
\[
  G~\text{is $m$-transitive}
  \iff
  R_\phi(p)^m \sim B_m ~ \text{on average},
\]
where $B_m$ is the $m$th Bell number.
Moreover, assuming ERH, there is a strong effective bound on how large $p$ must be for these asymptotics to hold.

Let $K$ be a number field.
Let $\Delta_K$ denote the discriminant of $K$.
If $\psi$ is a polynomial, let $\Delta_\psi$ denote the discriminant of $\psi$.
For each integer $q$ let $\Primes_K(q)$ be the number of prime ideals $\mathfrak{p}$ of $\mathcal{O}_K$ of norm $q$.
For $\omega = (\omega_1, \dots, \omega_m) \in \Omega^m$,
let $\mathbf{Q}(\omega)$ denote the subfield of $\mathbf{C}$ generated by $\omega_1, \dots, \omega_m$.
Note that $\mathbf{Q}(\omega^g) = \mathbf{Q}(\omega)^g$ for any $g \in G$, so $\Primes_{\mathbf{Q}(\omega^g)}(p) = \Primes_{\mathbf{Q}(\omega)}(p)$,
so it makes to write $\Primes_{\mathbf{Q}(\omega)}(p)$ for $\omega \in \Omega^m/G$.

\begin{proposition}[\cite{BV}*{Proposition~16}]
  \label{BV-prop-16}
  Let $\phi \in \mathbf{Z}[x]$,
  let $\tilde \phi$ be the square-free part of $\phi$,
  and let $p$ be a prime not dividing $\Delta_{\tilde\phi}$.
  Then, for $m \geq 1$,
  \[
    R_\phi(p)^m = \sum_{\omega \in \Omega^m / G} \Primes_{\mathbf{Q}(\omega)}(p).
  \]
\end{proposition}

Rational primes will be weighted by $w_X(\log p)$, where
\[
  w_X(u) = u \cdot 2 \exp(-X) \indic{u \in (X - \log 2, X]}.
\]
Sums over all rational primes are denoted simply $\sum_p$.

\begin{proposition}[\cite{BV}*{Proposition~9}]
  \label{prime-ideal-theorem}
  If RH holds for $K$ then
  \[
    \sum_p \Primes_K(p) w_X(\log p) = 1 + O(X^2 \exp(-X/2) \log|\Delta_K|).
  \]
\end{proposition}

Combining the two propositions, we have the following one.

\begin{proposition}
  \label{local-global-general}
  Let $\phi \in \mathbf{Z}[x]$ be a polynomial of degree $n$ and let $m \geq 1$.
  Assume RH holds for $\mathbf{Q}(\omega)$ for each $\omega \in \Omega^m$.
  Then
  \[
    \sum_p R_\phi(p)^m w_X(\log p)
    = |\Omega^m/G|
    + O(m n^{2m-1} X^2 \exp(-X/2) \log |\Delta_{\tilde\phi}|).
  \]
\end{proposition}
\begin{proof}
  By the two previous propositions,
  \begin{align*}
    \sum_p R_\phi(p)^m w_X(\log p)
     & = \sum_p \sum_{\omega \in \Omega^m/G} \Primes_{\mathbf{Q}(\omega)}(p) w_X(\log p) + E          \\
     & = \sum_{\omega \in \Omega^m/G} (1 + O(X^2 \exp(-X/2) \log |\Delta_{\mathbf{Q}(\omega)}|)) + E,
  \end{align*}
  where $E$ is the error arising from primes $p \mid \Delta_{\tilde \phi}$.
  If $\psi \mid \tilde\phi$ is irreducible and $\omega_1$ is a root of $\psi$ then
  \[
    |\Delta_{\mathbf{Q}(\omega_1)}| \leq |\Delta_\psi| \leq |\Delta_{\tilde \phi}|
  \]
  (the quotient $|\Delta_\psi|/|\Delta_{\mathbf{Q}(\omega_1)}|$ is $[\mathcal{O}_{\mathbf{Q}(\omega_1)} : \mathbf{Z}[\omega_1]]^2$).
  Recall that, for $K_1, K_2$ number fields,
  \[
    |\Delta_{K_1 K_2}| \leq |\Delta_{K_1}|^{[K_1K_2:K_1]} |\Delta_{K_2}|^{[K_1K_2:K_2]} \leq |\Delta_{K_1}|^{\deg K_2} |\Delta_{K_2}|^{\deg K_1}.
  \]
  Hence by induction we have, for $\omega \in \Omega^m$,
  \[
    |\Delta_{\mathbf{Q}(\omega)}| \leq |\Delta_{\tilde \phi}|^{m n^{m-1}}.
  \]
  Hence
  \begin{align*}
    \sum_p R_\phi(p)^m w_X(\log p)
     & = \sum_{\omega \in \Omega^m / G} (1 + O(X^2 \exp(-X/2) \cdot m n^{m-1} \log|\Delta_{\tilde \phi}|)) + E \\
     & = |\Omega^m / G| + O(m n^{2m-1} X^2 \exp(-X/2) \log|\Delta_{\tilde \phi}|) + E.
  \end{align*}
  We have $|R_\phi(p)| \leq n$ and $\sum_{\omega \in \Omega^m / G} \Primes_{\mathbf{Q}(\omega)}(p) \leq n^m$ identically,
  so each $p \mid \Delta_{\tilde \phi}$ contributes to $E$ at most
  \[
    n^m w_X(\log p) \lesssim n^m X \exp(-X)
  \]
  and there are at most $O(\log |\Delta_{\tilde \phi}|)$ such primes,
  so
  \[
    |E| \lesssim n^m X \exp(-X) \log |\Delta_{\tilde \phi}|.
  \]
  This error is subsumed by the other one.
\end{proof}

We need a bound for the discriminant of $\tilde \phi$ when $\phi$ is a characteristic polynomial.

\begin{lemma}
  Let $M$ be an $n \times n$ matrix whose entries are bounded by $H$
  and let $\phi$ be the characteristic polynomial of $M$.
  Let $\psi$ be any polynomial dividing $\phi$.
  Then
  \[
    |\Delta_\psi| \leq H^{n(n-1)} n^{n^2} .
  \]
\end{lemma}
\begin{proof}
  If $\lambda$ is an eigenvalue of $M$ then $|\lambda| \leq Hn$.
  Let $\lambda_1, \dots, \lambda_d$ be the roots of $\psi$.
  By definition $|\Delta_\psi|$ is the square of the determinant of the Vandermonde matrix $(\lambda_i^j)_{i,j}$.
  The $j$th column of this matrix has Euclidean norm bounded by $d^{1/2} (Hn)^j$.
  Thus by Hadamard's inequality
  \[
    |\Delta_\psi|^{1/2} = |\det(\lambda_i^j)|
    \leq d^{d/2} (Hn)^{d(d-1)/2}
    \leq n^{n/2} (Hn)^{n(n-1)/2}.
    \qedhere
  \]
\end{proof}

Combining the previous proposition and the lemma, we have:

\begin{proposition}
  \label{local-global}
  Assume $\phi$ is the characteristic polynomial of an $n \times n$ matrix with entries bounded by $H$.
  Let $m \geq 1$, and assume RH holds for all fields generated by at most $m$ roots of $\phi$.
  Then
  \[
    \sum_p R_\phi(p)^m w_X(\log p)
    = |\Omega^m/G|
    + O(m n^{2m+1} X^2 \exp(-X/2) \log(Hn)).
  \]
\end{proposition}

We have thus reduced the determination of $|\Omega^m / G|$ to the local problem of determining $R_\phi(p)^m$.
Note that, if $\phi(t) = \det(t-M)$ then $R_\phi(p)$ is simply the number of eigenvalues of $M$ acting on the finite vector space $\mathbf{F}_p^n$.
We turn to this problem in the next two sections, in which we will prove Theorems~\ref{thm:prob-M-nonsingular} and \ref{thm:correlation-bound}.
Assume for now those theorems have been proved and we will prove Theorem~\ref{main}.

Consider first $m = 1$.
Assume $\mu$ is supported on $[-H,H]$.
For $\lambda \in \mathbf{F}_p$, let $E_\lambda$ be the event that $\phi(\lambda)=0$, i.e., that $\lambda$ is an eigenvalue of $M$ mod $p$.
For $p > 2H+1$, $\mu \bmod p$ is $\alpha$-balanced for some constant $\alpha$ (since $\mu$ is nontrivial).
By Theorem~\ref{thm:prob-M-nonsingular} applied to $M - \lambda$,
\[
  \mathbf{P}(E_\lambda) = 1/p + O(1/p^2 + e^{-cn}).
\]
Hence, by linearity of expectation,
\[
  \mathbf{E} R_\phi(p) = 1 + O(1/p + p e^{-cn}).
\]
It follows that
\begin{align*}
  \mathbf{E} \sum_p R_\phi(p) w_X(\log p)
   & = \sum_p (1 + O(1/p + p e^{-c n})) w_X(\log p)      \\
   & = \sum_p (1 + O(e^{-X} + e^{X - c n})) w_X(\log p).
\end{align*}
Applying Proposition~\ref{prime-ideal-theorem} with $K = \mathbf{Q}$,
this is
\[
  (1 + O(e^{-X} + e^{X - c n}))
  (1 + O(X^2 e^{-X/2}))
  = 1 + O(X^2 e^{-X/2} + e^{X - c n})
  .
\]
On the other hand by Proposition~\ref{local-global} it is also
\[
  \mathbf{E} |\Omega / G| + O(n^3 X^2 \exp(-X/2) \log(Hn)).
\]
Taking $X = c n / 2$, we deduce that
\[
  \mathbf{E} |\Omega / G| = 1 + O(n^5 \log(Hn) e^{-c' n}) = 1 + O(e^{-c''n}).
\]
Hence
\[
  \mathbf{P}(|\Omega / G| > 1) \lesssim e^{-c' n}.
\]
Hence $\phi$ has a unique irreducible factor with probability $1 - O(e^{-cn})$.

The possibility that $\phi$ is a proper power
is ruled out by the following proposition,
which shows that $\phi$ has at least one simple root in $\mathbf{C}$.
(Of course, if $\phi$ is irreducible then the entire spectrum of $M$ is simple.)

\begin{proposition}
  \label{one-simple-eig}
  With probability $1 - O(e^{-cn})$,
  the matrix $M$ has at least one simple complex eigenvalue.
\end{proposition}
\begin{proof}
  Let $\bar\mu$ be the mean of $\mu$.
  If $\bar\mu = 0$ then the entire spectrum of $M$ is simple with probability $1 - O(e^{-cn})$ by \cite{l-o'r-simple-spec}*{Corollary~1.10}.
  Suppose $\bar\mu \neq 0$. Let $N = M - \bar\mu J$, where $J$ is the ones matrix.
  Then $\|N\| \lesssim n^{1/2} $ with probability $1 - O(e^{-cn})$ (see \cite{vershynin-book}*{Theorem~4.4.5}),
  while the spectrum of $\bar\mu J$ consists of $\bar\mu n$ and $0$ with multiplicity $n-1$,
  so a continuity argument as in \cite{silverstein}*{p.~526} shows that $M$ has a unique eigenvalue $\lambda$ such that $|\lambda - \bar\mu n| \leq \|N\|$.\footnote{The bound provided by this argument is unfortunately not uniform in $\bar\mu$ near 0, so neither is our main theorem.}
\end{proof}

Now consider arbitrary $m \geq 2$.
Assume $m < c \log n$ and $C \leq \log p < c n^{1/2} / m^{3/2}$.
By Theorem~\ref{thm:correlation-bound}, for distinct $\lambda_1, \dots, \lambda_m \in \mathbf{F}_p$,
\[
  \mathbf{P}(E_{\lambda_1} \cap \cdots \cap E_{\lambda_m})
  \leq (p-1)^{-m} + O\br{\exp(-c n^{1/2} / m^{3/2})}.
\]
It follows that
\begin{align*}
  \sum_{\lambda_1, \dots, \lambda_m~\text{distinct}} \mathbf{P}(E_{\lambda_1} \cap \cdots \cap E_{\lambda_m})
   & \leq
  \frac{p(p-1) \cdots (p-m+1)}{(p-1)^m} + O(p^m e^{-cn^{1/2} / m^{3/2}})
  \\
   & \leq
  1 + O(1/p + p^m e^{-cn^{1/2} / m^{3/2}})
  .
\end{align*}
Summing over all $\lambda_1, \dots, \lambda_m$ and considering all possible partitions of $\{1, \dots, m\}$ defined by equality among the $\lambda$'s,
it follows that
\[
  \mathbf{E} R_\phi(p)^m
  \leq
  B_m
  (1 + O(1/p + p^m e^{-cn^{1/2} / m^{3/2}})).
\]
Averaging over primes, and again using Proposition~\ref{prime-ideal-theorem} with $K = \mathbf{Q}$,
\begin{align*}
  \mathbf{E} \sum_p R_\phi(p)^m w_X(\log p)
   & \leq
  \sum_p B_m (1 + O(1 / p + p^m e^{-c n^{1/2} / m^{3/2}})) w_X(\log p)  \\
   & =
  B_m
  (1 + O(e^{-X} + e^{m X - c n^{1/2} / m^{3/2}})) (1 + O(X^2 e^{-X/2})) \\
   & =
  B_m
  \br{1 + O(X^2 e^{-X/2} + e^{m X - c n^{1/2} / m^{3/2}})}.
\end{align*}
Fix $X = cn^{1/2} / m^{5/2}$ for a sufficiently small constant $c$.
Using $B_m \leq m^m$, it follows that
\[
  \mathbf{E} \sum_p R_\phi(p)^m w_X(\log p)
  \leq B_m +
  O\br{
  e^{-cn^{1/2} / m^{5/2}}

  }.
\]
On the other hand, by Proposition~\ref{local-global} we also have
\[
  \mathbf{E} \sum_p R_\phi(p)^m w_X(\log p)
  = \mathbf{E} |\Omega^m / G| + O(m n^{2m+1} X^2 e^{-X/2} \log(Hn)).
\]
Hence
\[
  \mathbf{E}|\Omega^m / G|
  \leq
  B_m
  + O\br{
  e^{-cn^{1/2} / m^{5/2}}

  }.
\]
Trivially $|\Omega^m / G| \geq B_m$, so
\[
  \mathbf{P}(|\Omega^m / G| > B_m)
  \lesssim
  e^{-cn^{1/2} / m^{5/2}}
  .
\]
Note that $|\Omega^m / G| = B_m$ if and only if $G$ is $m$-transitive.
Taking $m$ to be a sufficiently large constant,
it follows from Fact~\ref{6trans} that $\opr{Gal}(\phi) \geq A_n$ with probability $1 - O(e^{-cn^{1/2}})$, as claimed.

\section{The local problem, part 1: singularity of matrices over \texorpdfstring{$\mathbf{F}_q$}{F\_q}}

In this section we prove Theorem~\ref{thm:prob-M-nonsingular}.
Recall the context:
A measure $\mu$ on $\mathbf{F}_q$ is called \emph{$\alpha$-balanced} if
$\mu(x+H) \leq 1 - \alpha$ for every $x \in \mathbf{F}_q$ and every proper subgroup $H < \mathbf{F}_q$.
Let $\bm{\mu} = (\mu_{ij})_{1 \leq i,j\leq n}$ be a matrix of $\alpha$-balanced measures on $\mathbf{F}_q$, and let $\M(\bm{\mu})$ denote the distribution of matrices $M \in \M_n(q)$ with independent entries and $M_{ij} \sim \mu_{ij}$.
The claim is that
\[
  \mathbf{P}(M~\textup{nonsingular}) = \prod_{i=1}^\infty (1-1/q^i) + O_\alpha(e^{-c\alpha n}).
\]

Fix some constant parameters
\[
  \zeta \ll \delta \ll \eta \ll 1.
\]
Let $X_1, \dots, X_n$ be the rows of $M$, so
\begin{equation}
  \label{Xi-law}
  X_i \sim \mu_{i1} \otimes \cdots \otimes \mu_{in}.
\end{equation}
Let $M_k$ be the top $k \times n$ submatrix.
Let $\opr{row} M_k$ be the row space of $M_k$, i.e.,
\[
  \opr{row} M_k = \langle X_1, \dots, X_k\rangle.
\]
We will prove that $\opr{row} M_k$ is suitably generic with respect to $\bm{\mu}$ with high probability
for all $k \geq (1-\eta)n$.
For a subspace $V \leq \mathbf{F}_q^n$, let
\begin{align*}
  \rho_i(V) & = \max_{x \in \mathbf{F}_q^n} |\mathbf{P}(X_i \in x + V) - 1/q^{\opr{codim} V}|; \\
  \rho(V)   & = \max_i \rho_i(V).
\end{align*}
The quantity $\rho_i(V)$ measures the nonuniformity of $X_i$ mod $V$,
and $\rho(V)$ measures the maximum nonuniformity among $X_1, \dots, X_n$ mod $V$.
For $v \in \mathbf{F}_q^n$, the \emph{support} of $v$ is
\[
  \opr{supp} v = \{ i \in [n] : v_i \neq 0 \}.
\]
We use the following taxonomy for subspaces $V \leq \mathbf{F}_q^n$
(adapted from \cite{maples}):
\begin{description}
  \item[sparse] $V$ is called \emph{sparse} if there is a nonzero $v \perp V$ with $|\opr{supp} v| \leq \delta n$;
  \item[unsaturated] $V$ is called \emph{unsaturated} if $V$ is not sparse and
        \[
          \rho(V) > \max(e^{-\zeta \alpha n}, 10/q^{\opr{codim} V});
        \]
  \item[semi-saturated] $V$ is called \emph{semi-saturated} if $V$ is not sparse and
        \[
          e^{-\zeta \alpha n} < \rho(V) \leq 10/q^{\opr{codim} V};
        \]
  \item[saturated] $V$ is called \emph{saturated} if $V$ is not sparse and
        \[
          \rho(V) \leq e^{-\zeta \alpha n}.
        \]
\end{description}

In this language, the main assertion is the following.

\begin{theorem}
  \label{thm:saturation}
  For $M \sim \M(\bm{\mu})$ and $k \geq (1- \eta)n$,
  \[
    \mathbf{P}(\opr{row} M_k~\textup{is saturated}) = 1 - O_\alpha(e^{-c\alpha n}).
  \]
\end{theorem}

The proof occupies the rest of this section, but first let us see how Theorem~\ref{thm:prob-M-nonsingular} follows.
The following theorem is a generalization.

\begin{theorem}
  \label{thm:prob-Mk-nonsingular}
  For $M \sim \M(\bm{\mu})$,
  \[
    \mathbf{P}(\dim \opr{row} M_k = k) = \prod_{i=n-k+1}^\infty (1-1/q^i) + O_\alpha(e^{-c\alpha n}).
  \]
\end{theorem}

To deal with $k < (1-\eta)n$ we will use the following well-known lemma of Odlyzko,
which will also be used repeatedly in the rest of the paper.

\begin{lemma}[Odlyzko, see \citelist{\cite{bourgain-vu-wood}*{Lemma~B.1}
  \cite{maples}*{Lemma~2.2}}]
  \label{odlyzko}
  If $V \leq \mathbf{F}_q^n$ is an affine subspace and $X \in \mathbf{F}_q^n$ has independent $\alpha$-balanced entries then
  \[
    \mathbf{P}(X \in V) \leq (1-\alpha)^{\opr{codim} V}.
  \]
\end{lemma}

\begin{proof}[Proof of Theorem~\ref{thm:prob-Mk-nonsingular}]
  Let
  \[
    \varepsilon_k = \left|
    \mathbf{P}(\dim \opr{row} M_k = k)
    - \prod_{i = n-k+1}^\infty (1-1/q^i)
    \right|.
  \]
  We claim that $\varepsilon_k \leq e^{-c\alpha n}$ for all $k$.
  If $k-1 < (1-\eta)n$, then by Odlyzko's lemma
  \[
    \mathbf{P}(\dim \opr{row} M_k < k)
    \leq k (1 - \alpha)^{n-k+1} \leq n e^{-\alpha \eta n},
  \]
  and
  \[
    \prod_{i=n-k+1}^\infty (1-1/q^i) = 1 + O(1/q^{n-k+1}) = 1 + O(2^{-\eta n}),
  \]
  so the claim holds trivially.
  Suppose $k-1 \geq (1-\eta) n$.
  We have $\dim \opr{row} M_k = k$ if and only if $\dim \opr{row} M_{k-1} = k-1$ and $X_k \notin \opr{row} M_{k-1}$.
  Conditional on $\opr{row} M_{k-1}$ being saturated and $(k-1)$-dimensional,
  \[
    \mathbf{P}(X_k \notin \opr{row} M_{k-1}) = 1-1/q^{n-k+1} + O(e^{-c\alpha n}).
  \]
  Hence, using Theorem~\ref{thm:saturation},
  \begin{align*}
    \mathbf{P}(\dim \opr{row} M_k = k)
     & = \mathbf{P}(\dim \opr{row} M_{k-1} = k-1) (1-1/q^{n-k+1}+ O(e^{-c\alpha n}))
    \\
     & \qquad + O(\mathbf{P}(\opr{row} M_{k-1}~\text{not saturated}))                         \\
     & = \mathbf{P}(\dim \opr{row} M_{k-1} = k-1) (1-1/q^{n-k+1}) + O_\alpha(e^{-c\alpha n}).
  \end{align*}
  Hence
  \[
    \varepsilon_k \leq \varepsilon_{k-1} + O_\alpha(e^{-c\alpha n}).
  \]
  It follows that $\varepsilon_k \lesssim_\alpha n e^{-c\alpha n} \lesssim_\alpha e^{-c'\alpha n}$, as claimed.
\end{proof}

We now proceed with the proof of Theorem~\ref{thm:saturation}.
The proof consists of bounding the probability that $\opr{row} M_k$ is sparse, semi-saturated, or unsaturated.
The unsaturated case is the most interesting and will be handled last.

\subsection{Sparse subspaces}

Note $(\opr{row} M_k)^\perp = \ker M_k$.
Suppose $\opr{supp} v = \{j_1, \dots, j_s\}$.
Let $C_j \in \mathbf{F}_q^k$ denote the $j$th column of $M_k$.
If $M_k v = 0$ then
\begin{equation}
  \label{Cjs}
  C_{j_s} \in \langle C_{j_1}, \dots, C_{j_{s-1}} \rangle.
\end{equation}
For fixed $j_1, \dots, j_s$, \eqref{Cjs} occurs with probability at most $(1-\alpha)^{k-s+1}$ by Odlyzko's lemma.
Hence, by the union bound,
\[
  \mathbf{P}(\opr{row} M_k~\text{is sparse})
  \leq \sum_{s \leq \delta n} \binom{n}{s} (1-\alpha)^{k-s+1}.
\]
Assuming $\delta = \delta(\alpha)$ is sufficiently small and $k \geq (1-\eta)n$, this is bounded by $e^{-c\alpha n}$ as desired.

\begin{remark}
  To make $\delta$ and ultimately the constant $c$ in Theorem~\ref{thm:saturation} independent of $\alpha$, use the above argument only for $s$ up to $O(\alpha^{-1})$.
  For larger $s$, use the following argument.

  Suppose $v \in \ker M_k$ has minimal support, say $S \subset [n]$ of size $s$.
  The set of vectors $u \in \ker M_k$ supported on $S$ must be precisely the line $\langle v \rangle$, or else we could find a linear combination with smaller support.
  There are some $s-1$ rows $(X_i : i \in T)$ of $M_k$ whose restrictions to $S$ span $v^\perp|_S$,
  and in particular determine $v$ up to a scalar.
  For fixed $S$, $T$, and $v$, and $M' = (X_i : i \notin T)$,
  \[
    \mathbf{P}(M' v = 0) = \prod_{i \notin T} \mathbf{P}(X_i \cdot v = 0).
  \]
  By \cite{maples}*{Lemma~2.4} or \cite{nguyen-paquette}*{Theorem~A.21}, $\mathbf{P}(M' v = 0) \leq (2/3)^{k-s+1}$.
  Hence by summing over $S$ and $T$ we get the bound
  \[
    \sum_{C\alpha^{-1} < s \leq \delta n} \binom{n}{s} \binom{k}{s-1} (2/3)^{k-s+1},
  \]
  which is negligible as long as $\delta$ is sufficiently small independently of $\alpha$.

  This improvement is not important for the application to Theorem~\ref{main}, in which $\alpha$ is considered a constant.
\end{remark}

\subsection{Semi-saturated subspaces}

The \emph{large spectrum} of a measure $\mu$ on $\mathbf{F}_q$ is
\[
  \opr{Spec}_t \mu = \{ u \in \mathbf{F}_q : |\hat{\mu}(u)| \geq t \}.
\]
Here we are identifying $\mathbf{F}_q$ with its own dual group in the usual way by fixing a nontrivial character $\chi : \mathbf{F}_q \to S^1$ and defining
\[
  \hat{\mu}(u) = \sum_{x \in \mathbf{F}_q} \mu(x) \chi(-ux).
\]

\begin{lemma}[\cite{maples}*{Lemma~3.2}; see also \cite{tao-vu}*{Lemma~4.37}]
  \label{spec-lemma}
  For $\varepsilon_1, \dots, \varepsilon_k \geq 0$,
  \[
    \opr{Spec}_{1-\varepsilon_1} \mu + \cdots + \opr{Spec}_{1-\varepsilon_k} \mu
    \subset \opr{Spec}_{1-k(\varepsilon_1 + \cdots + \varepsilon_k)} \mu.
  \]
\end{lemma}

The following lemma is essentially contained in \cite{maples}*{Section~3.2}.

\begin{lemma}
  \label{small-spec}
  Suppose $\mu$ is an $\alpha$-balanced measure on $\mathbf{F}_q$.
  Then
  \[
    |\opr{Spec}_{1-\varepsilon \alpha} \mu \setminus\{0\}| \lesssim \varepsilon^{1/2} q.
  \]
\end{lemma}
\begin{proof}
  Since $\mu$ is $\alpha$-balanced, for any nonzero subgroup $H \leq \mathbf{F}_q$ we have
  \[
    \min_H |\hat{\mu}|^2
    \leq \|\hat{\mu}|_H\|_2^2
    = \|\mu \bmod H^\perp\|_2^2
    \leq 1-\alpha.
  \]
  Hence $\opr{Spec}_{1-\alpha/2}\mu$ does not contain a subgroup.
  On the other hand, by Lemma~\ref{spec-lemma},
  \[
    k \opr{Spec}_{1-k^{-2} \alpha / 2} \mu \subset \opr{Spec}_{1 - \alpha/2} \mu.
  \]
  Hence by Kneser's theorem
  \[
    k |\opr{Spec}_{1-k^{-2} \alpha / 2} \mu \setminus\{0\}| \leq |\opr{Spec}_{1-\alpha/2} \mu\setminus\{0\}| < q.
  \]
  Take $k \asymp \varepsilon^{-1/2}$.
\end{proof}

Now suppose $V$ is a semi-saturated subspace of codimension $d \geq n-k$, so
\begin{equation}
  \label{semi-sat}
  e^{-\zeta \alpha n} < \max_i \rho_i(V) \leq 10 / q^d .
\end{equation}
Let $i$ be an index realizing the maximum.
By Fourier analysis,
\begin{align*}
  \mathbf{P}(X_i \in x + V)
   & = \frac1{|V^\perp|} \sum_{v \in V^\perp} \chi(x \cdot v) \prod_{j=1}^n \hat{\mu}_{ij}(v_j),
  \\
  \rho_i(V)
   & \leq \frac1{|V^\perp|} \sum_{v \in V^\perp \setminus\{0\}} \prod_{j=1}^n |\hat{\mu}_{ij}(v_j)|.
\end{align*}
Hence there is some $v \in V^\perp \setminus\{0\}$ such that
\[
  \rho_i(V) \leq \prod_{j=1}^n |\hat{\mu}_{ij}(v_j)|.
\]
Taking logarithms and using ${\log x \leq x - 1}$,
\[
  \sum_{j=1}^n (1 - |\hat{\mu}_{ij}(v_j)|)
  \leq \log \rho_i(V)^{-1}
  < \zeta \alpha n.
\]
By Markov's inequality there is a set $J \subset [n]$ of size $|J| \geq (1-\delta/2)n$ such that
\[
  1 - |\hat{\mu}_{ij}(v_j)| \leq 2 \delta^{-1} \zeta \alpha
\]
for all $j \in J$, i.e.,
\[
  v_j \in \opr{Spec}_{1 - 2 \delta^{-1} \zeta \alpha} \mu_{ij}.
\]
Moreover, since $V$ is not sparse, $|\opr{supp} v| > \delta n$,
so there is a set $J' = J \cap \opr{supp} v$ of size $|J'| \geq (\delta/2)n$
such that
\[
  v_j \in \opr{Spec}_{1 - 2 \delta^{-1} \zeta \alpha} \mu_{ij} \setminus\{0\}
\]
for all $j \in J'$.
By Lemma~\ref{small-spec},
\[
  |\opr{Spec}_{1-2\delta^{-1} \zeta \alpha} \mu_{ij} \setminus\{0\} |
  \lesssim \delta^{-1/2} \zeta^{1/2} q.
\]
Hence the number of possibilities for $v$,
accounting for the choice of $i \in [n]$ and $J' \subset [n]$,
is bounded by
\[
  n 2^n (C \delta^{-1/2} \zeta^{1/2} q)^{(\delta/2)n} q^{(1-\delta/2)n}
  = O(1)^n (\zeta / \delta)^{\delta n/4} q^n.
\]
The number of $d$-dimensional subspaces containing $v$ is $O(q^{n(d-1) - d(d-1)})$,
so the number of possibilities for $V$ is
\begin{equation}
  \label{semi-sat-poss}
  O(1)^n (\zeta / \delta)^{\delta n/4} q^{dn - d(d-1)}.
\end{equation}
For any fixed such $V$, we have
\[
  \mathbf{P}(\opr{row} M_k \leq V) \leq (11 / q^d)^k,
\]
by \eqref{semi-sat}.
Hence
\begin{align*}
  \mathbf{P}(\opr{row} M_k \leq \textup{some semi-saturated}~ & V~\text{of codim}~d)
  \\
                                                 & \lesssim O(1)^n (\zeta / \delta)^{\delta n/4} q^{dn - d(d-1)} (11 / q^d)^k
  \\
                                                 & = O(1)^n (\zeta / \delta)^{\delta n/4} q^{d(n - d + 1 - k)}
  \\
                                                 & \leq O(1)^n (\zeta/\delta)^{\delta n/4} q^d,
\end{align*}
where in the last line we used $d \geq n-k$.
Using \eqref{semi-sat} again, this is bounded by
\[
  O(1)^n (\zeta / \delta)^{\delta n/4} e^{\zeta \alpha n}.
\]
As long as $\zeta$ is sufficiently small depending on $\delta$ this is exponentially negligible.

\subsection{Unsaturated subspaces}

Finally, we consider unsaturated subspaces.
Let $\UU_i$ be the set of unsaturated subspaces $V \leq \mathbf{F}_q^n$ such that
\[
  \rho(V) = \rho_i(V).
\]
It suffices to show that
\begin{equation}
  \label{unsat-goal}
  \mathbf{P}(\opr{row} M_k \in \UU_i) \leq e^{-cn}
\end{equation}
for each $i$ separately.
To do this we will construct
new measures $(\nu_{ij})_{1 \leq j \leq n}$,
each still $\alpha/8$-balanced,
such that if (cf.~\eqref{Xi-law})
\begin{equation}
  \label{Yi-law}
  Y \sim \nu_{i1} \otimes \cdots \otimes \nu_{in}
\end{equation}
and $N$ is $M_k$ but with most of the rows replaced with independent copies of $Y$
then, for any $V \in \UU_i$,
\[
  \mathbf{P}(\opr{row} M_k = V) \leq e^{-cn} \mathbf{P}(\opr{row} N = V).
\]
We will then use the disjointness of the events $\{\opr{row} N = V\}$ to infer \eqref{unsat-goal}.

Let $Y_1, \dots, Y_r$ be independent copies of $Y$,
and $V$ a subspace.
Let
\[
  B_V = \{Y_1, \dots, Y_r~\text{lin.~ind.~and in}~V\}.
\]
Clearly
\begin{align*}
  \mathbf{P}(B_V)
   & =
  \mathbf{P}(Y_1, \dots, Y_r \in V)
  - \mathbf{P}(Y_1, \dots, Y_r ~ \text{lin.~dep.~in}~V) \\
   & =
  \mathbf{P}(Y \in V)^r
  - \mathbf{P}(Y_1, \dots, Y_r ~ \text{lin.~dep.~in}~V),
\end{align*}
and by Odlyzko's lemma
\[
  \mathbf{P}(Y_1, \dots, Y_r ~ \text{lin.~dep.~in}~V)
  \leq r \mathbf{P}(Y \in V)^{r-1} (1-\alpha/8)^{n-r+1}
\]
so
\begin{equation}
  \label{BV-ratio}
  \frac{\mathbf{P}(B_V)}{\mathbf{P}(Y \in V)^r}
  \geq 1 - r (1 - \alpha/8)^{n-r+1} / \mathbf{P}(Y \in V).
\end{equation}
When we fix parameters we will ensure that this is at least $1/2$.

By independence of $X_1, \dots, X_k$ and $Y_1, \dots, Y_r$,
\[
  \mathbf{P}(\opr{row} M_k = V)
  = \frac{\mathbf{P}(B_V \wedge \opr{row} M_k = V)}{\mathbf{P}(B_V)}.
\]
If $B_V$ holds and $\opr{row} M_k = V$ then,
by the Steinitz exchange lemma from elementary linear algebra,
we can find $k - r$ rows of $M_k$ that together with $Y_1, \dots, Y_r$ span $V$,
and the remaining rows of $M_k$ must also be contained in $V$;
hence
\[
  \mathbf{P}(B_V \wedge \opr{row} M_k = V)
  \leq \sum_{\substack{R \subset [k] \\ |R|=r}}
  \mathbf{P}(\opr{row} N_R = V) \prod_{i' \in R} \mathbf{P}(X_{i'} \in V),
\]
where $N_R$ is $M_k$ but with the rows $(X_{i'} : i' \in R)$ replaced with $(Y_1, \dots, Y_r)$.
Thus
\[
  \mathbf{P}(\opr{row} M_k = V)
  \lesssim \sum_{\substack{R \subset [k] \\ |R|=r}}
  \mathbf{P}(\opr{row} N_R = V) \max_{i'} \pfrac{\mathbf{P}(X_{i'} \in V)}{\mathbf{P}(Y \in V)}^r.
\]
Summing over $V \in \UU_i$,
\begin{align*}
  \mathbf{P}(\opr{row} M_k \in \UU_i)
   & \lesssim \sum_{\substack{R \subset [k]         \\ |R|=r}}
  \mathbf{P}(\opr{row} N_R \in \UU_i) \max_{V \in \UU_i}
  \max_{i'} \pfrac{\mathbf{P}(X_{i'} \in V)}{\mathbf{P}(Y \in V)}^r \\
   & \leq \binom{k}{r} \max_{V \in \UU_i}
  \max_{i'} \pfrac{\mathbf{P}(X_{i'} \in V)}{\mathbf{P}(Y \in V)}^r.
\end{align*}
Fix $r = \floor{0.99k}$.
To complete the proof of \eqref{unsat-goal},
we must show that $(\nu_{ij})_{1\leq j\leq n}$ can be chosen so that, for all $V \in \UU_i$,
\begin{enumerate}[(a)]
  \item\label{a} $\mathbf{P}(Y \in V) > 2r (1-\alpha/8)^{n-r+1}$ (so that \eqref{BV-ratio} $\geq 1/2$);
  \item\label{b} $\max_{i'} \mathbf{P}(X_{i'} \in V) / \mathbf{P}(Y \in V) \leq 0.6$.
\end{enumerate}

We will construct $(\nu_{ij})_{1 \leq j \leq n}$ so that, for all $V \in \UU_i$,
\begin{equation}
  \label{eqn-to-arrange}
  \rho_i(V) \leq (1/2 + o(1)) |\mathbf{P}(Y \in V) - 1/q^{\opr{codim} V}|,
\end{equation}
and the conditions \ref{a} and \ref{b} above follow from this.
Indeed, for $V \in \UU_i$ of codimension $d$,
\[
  |\mathbf{P}(Y \in V) - 1/q^d| \geq (2 + o(1)) \max(e^{-\zeta \alpha n}, 10/q^d).
\]
Since the right-hand side is bigger than $1/q^d$
the absolute values on the left-hand side may be dropped,
so certainly \ref{a} is satisfied (since $r \leq 0.99n$ and $\zeta \ll 1$).
Also
\begin{align*}
  \mathbf{P}(X_{i'} \in V)
   & \leq 1/q^d + \rho(V)                             \\
   & \leq 1/q^d + (1/2 + o(1)) (\mathbf{P}(Y \in V) - 1/q^d)) \\
   & = (1/2 + o(1)) (\mathbf{P}(Y \in V) + 1/q^d)             \\
   & \leq (1/2 + 1/21 + o(1)) \mathbf{P}(Y \in V),
\end{align*}
so \ref{b} is satisfied too.

\begin{lemma}[Cf.~\cite{maples}*{Proposition~3.6}]
  \label{lem:nu}
  Let $\mu$ be an $\alpha$-balanced measure on $\mathbf{F}_q$.
  There is a probability measure $\nu$ with the following properties:
  \begin{enumerate}[(1)]
    \item\label{nu1} $\nu$ is $\alpha/8$-balanced;
    \item\label{nu2} $\hat{\nu} > 0$;
    \item\label{nu3} $\hat{\nu}^4 \geq |\hat{\mu}|$;
    \item\label{nu4} $\hat{\nu}(s + t)^2 \geq |\hat{\mu}(s)| |\hat{\mu}(t)|$ for all $s, t \in \mathbf{F}_q$.
  \end{enumerate}
\end{lemma}
\begin{proof}
  Fix any constant $\gamma \leq 1/8$ and let
  \[
    \nu = (1-\gamma)\delta + \gamma \mu * \mu^-,
  \]
  where $\delta$ is the mass at zero
  and $\mu^-$ is the image of $\mu$ under $x \mapsto -x$.
  Clearly $\nu$ is $\gamma\alpha$-balanced, so \ref{nu1} holds.
  The Fourier transform of $\nu$ is
  \[
    \hat{\nu} = 1-\gamma + \gamma |\hat{\mu}|^2,
  \]
  so \ref{nu2} holds.
  Suppose $|\hat{\mu}(s)| = 1-\varepsilon$.
  Then
  \[
    \hat{\nu}(s)
    = 1 - \gamma + \gamma(1 - \varepsilon)^2
    \geq 1 - 2\gamma\varepsilon,
  \]
  so
  \[
    \hat{\nu}(s)^4 \geq 1 - 8\gamma\varepsilon.
  \]
  Since $\gamma \leq 1/8$ this proves \ref{nu3}.
  For \ref{nu4}, let $\varepsilon_1 = 1 - |\hat{\mu}(s)|$ and $\varepsilon_2 = 1 - |\hat{\mu}(t)|$.
  Then, by Lemma~\ref{spec-lemma}, $|\hat{\mu}(s+t)| \geq 1 - 2(\varepsilon_1+\varepsilon_2)$, so
  \begin{align*}
    \hat{\nu}(s+t)

     & \geq 1 - \gamma + \gamma (1 - 4(\varepsilon_1 + \varepsilon_2))        \\
     & = 1 - 4\gamma(\varepsilon_1+\varepsilon_2)                             \\
     & \geq (1 - 8\gamma\varepsilon_1)^{1/2} (1 - 8\gamma\varepsilon_2)^{1/2}
    .
  \end{align*}
  Since $\gamma \leq 1/8$ this proves \ref{nu4}.
\end{proof}

Let $\nu_{ij}$ be the measure constructed as above from $\mu_{ij}$.
Let $Y$ satisfy \eqref{Yi-law}. The following lemma verifies \eqref{eqn-to-arrange} and thus completes the proof of \eqref{unsat-goal}.

\begin{lemma}[Cf.~\cite{maples}*{Lemma~2.8}]
  \label{Y-lemma}
  Let $V$ be a subspace, and assume every nonzero $v \perp V$ has at least $s$ nonzero entries. Then
  \[
    \rho_i(V) \leq \br{1/2 + e^{-c\alpha s}} |\mathbf{P}(Y \in V) - 1/q^{\opr{codim} V}|.
  \]
\end{lemma}
\begin{proof}
  Define
  \begin{align*}
    f(v)  & = \prod_{j=1}^n \hat{\mu}_{ij}(v_j),
          &
    F(t)  & = \{v \in V^\perp : |f(v)| \geq t\},
          &
    F'(t) & = F(t) \setminus\{0\},
    \\
    g(v)  & = \prod_{j=1}^n \hat{\nu}_{ij}(v_j),
          &
    G(t)  & = \{v \in V^\perp : g(v) \geq t\},
          &
    G'(t) & = G(t) \setminus\{0\}.
  \end{align*}
  By Fourier analysis,
  \begin{align*}
    \mathbf{P}(X_i \in x + V) & = \frac1{|V^\perp|} \sum_{v \in V^\perp} \chi(x \cdot v) f(v), \\
    \mathbf{P}(Y \in V)       & = \frac1{|V^\perp|} \sum_{v \in V^\perp} g(v),
  \end{align*}
  so it suffices to prove
  \[
    \sum_{v \in V^\perp \setminus\{0\}} |f(v)|
    \leq \br{\frac12 + e^{-c\alpha s}} \sum_{v \in V^\perp \setminus\{0\}} g(v).
  \]

  Since $|f(v)| \leq g(v)^4$ (by Lemma~\ref{lem:nu}\ref{nu3}) we have
  \[
    \sum_{v \in V^\perp \setminus\{0\} : f(v) < \varepsilon} |f(v)|
    \leq \varepsilon^{3/4} \sum_{v \in V^\perp \setminus\{0\}} g(v).
  \]
  The other part is
  \[
    \sum_{v \in V^\perp \setminus\{0\} : f(v) \geq \varepsilon} |f(v)|
    = \int_\varepsilon^\infty |F'(t)| \, dt + \varepsilon |F'(\varepsilon)|.
  \]
  By Lemma~\ref{lem:nu}\ref{nu4} and tensorization,
  \[
    g(u+v)^2 \geq |f(u)| |f(v)|
  \]
  for all $u, v \in \mathbf{F}_q^n$. Hence
  \[
    F(t) + F(t) \subset G(t).
  \]
  Thus by Kneser's theorem either
  \begin{equation}
    \label{2F'}
    2|F'(t)| \leq |G'(t)|
  \end{equation}
  or $G(t)$ contains a nontrivial subgroup.
  Assume $G(\varepsilon)$ does not contain a nontrivial subgroup.
  Then \eqref{2F'} holds for all $t \geq \varepsilon$, so
  \[
    \int_\varepsilon^\infty |F'(t)| \, dt + \varepsilon |F'(\varepsilon)|
    \leq \frac12 \br{
      \int_\varepsilon^\infty |G'(t)| \, dt + \varepsilon |G'(\varepsilon)|
    }
    = \frac12 \sum_{v \in V^\perp \setminus\{0\} : g(v) \geq \varepsilon} g(v).
  \]
  Hence
  \[
    \sum_{v \in V^\perp \setminus\{0\}} |f(v)|
    \leq \br{\frac12 + \varepsilon^{3/4}} \sum_{v \in V^\perp \setminus\{0\}} g(v).
  \]

  It remains to choose $\varepsilon$ so that $G(\varepsilon)$ does not contain a nontrivial subgroup.
  Suppose $G(\varepsilon)$ contains $tv$ for all $t \in \mathbf{F}_p$ (the prime subfield of $\mathbf{F}_q$), where $v \in V^\perp$, i.e.,
  \[
    \prod_{i=1}^n \hat{\nu}_{ij}(t v_j) \geq \varepsilon.
  \]
  By the AM--GM inequality,
  \[
    \frac1n \sum_{j=1}^n \hat{\nu}_{ij}(tv_j)^2 \geq \varepsilon^{2/n}.
  \]
  Let $S = \opr{supp} v$, and for each $j \in S$ let $H_j$ be the subgroup of $\mathbf{F}_q$ generated by $v_j$.
  Then
  \begin{align*}
    \varepsilon^{2/n}
     & \leq \frac{|S^c|}{n} + \frac1n \sum_{j \in S} \|\hat{\nu}|_{H_j}\|_2^2
     &                                                                        & \text{(by averaging over $t \in \mathbf{F}_p$)}          \\
     & = \frac{|S^c|}{n} + \frac1n \sum_{j \in S} \|\nu \bmod H_j^\perp\|_2^2
     &                                                                        & \text{(by Parseval)}                             \\
     & \leq \frac{|S^c|}{n} + \frac{|S|}{n} (1 - \alpha/8)
     &                                                                        & \text{(since $\nu_{ij}$ is $\alpha/8$-balanced)} \\
     & \leq 1-s/n + (s/n)(1-\alpha / 8)
     &                                                                        & \text{(since $|S| \geq s$)}                      \\
     & = 1 - (s/n) (\alpha /8).
  \end{align*}
  Hence $\varepsilon \leq \exp(-\alpha s / 16)$.
  Thus we may take $\varepsilon = \exp(-\alpha s / 17)$.
\end{proof}

\section{The local problem, part 2: correlations of eigenvalues}
\label{sec:local-problem-part-2}

In this section we study correlations of eigenvalues.
Assume $m > 1$ and let $\lambda_1, \dots, \lambda_m \in \mathbf{F}_q$.
For $M \sim \M(\bm{\mu})$, let
\[
  R = R_{\lambda_1, \dots, \lambda_m} =
  \bigcap_{j=1}^m
  \opr{row}(M - \lambda_j)
  .
\]
From elementary linear algebra,
\begin{equation}
  \label{R-perp}
  R^\perp
  = \sum_{j=1}^m \ker(M - \lambda_j)
  = \ker (M - \lambda_1) \cdots (M - \lambda_m)
  .
\end{equation}
We will adapt the method of the previous section to prove that $R$ is suitably generic with high probability.
However, one or two aspects of the proof are now much more troublesome,
so we must make a few adjustments to the hypotheses and taxonomy:
\begin{enumerate}
  \item Assume $m$ is not too large: $m 2^m < c \alpha^2 n / \log n$.
  \item Assume $q$ is not too large: $\log q < c \alpha^2 n / (m 2^m)$.
  \item Assume $q$ is not too small: $q \geq C$ for some large constant $C$ ($C = \zeta^{-1/2}$).
  \item Call $V$ sparse only if there is some nonzero $v \perp V$ with $|\opr{supp} v| \leq C \alpha^{-1}$ for some large constant $C$.
  \item Narrow the definitions of unsaturated and semi-saturated and broaden the definition of saturated by replacing $e^{-\zeta \alpha n}$ with the larger quantity
        \[
          \exp(-\zeta (\alpha n / m)^{1/2}).
        \]
\end{enumerate}

\begin{theorem}
  \label{thm:saturation-m}
  For $M \sim \M(\bm{\mu})$ and fixed distinct $\lambda_1, \dots, \lambda_m \in \mathbf{F}_q$,
  \[
    \mathbf{P}\br{
      R_{\lambda_1, \dots, \lambda_m}~\textup{is saturated}
    }
    = 1 - O_\alpha(\exp\br{ -c \alpha n / (m 2^m)}).
  \]
\end{theorem}

The most novel part of the argument is now the treatment of sparse vectors, which requires some reasoning about the polynomial evaluation $(M - \lambda_1) \cdots (M - \lambda_m) v$.
The unsaturated case is also more complicated and the reason we need to broaden the meaning of saturated.

\subsection{Sparse subspaces}

From \eqref{R-perp}, $v \perp R$ if and only if
\begin{equation}
  \label{M-lambda-v-condition}
  (M - \lambda_1) \cdots (M - \lambda_m) v = 0.
\end{equation}
For each fixed $v$ (sparse or not) we will show that \eqref{M-lambda-v-condition} has probability bounded by $O(\exp\br{-\alpha n / (m 2^{m+1})})$.
Since the number of $v$ of support size at most $s$ is at most $\binom{n}{s} q^s$, we may sum over all possibilities for $v$, and it follows that
\[
  \mathbf{P}(\exists~\text{nonzero}~ v \perp R~\text{of support}\leq s)
  \lesssim \binom{n}{s} q^s \exp(-\alpha n / (m2^{m+1})).
\]
We are assuming that $s \leq C \alpha^{-1}$ (with the value of $C$ determined by a later part of the argument), so this is exponentially negligible provided
\[
  C \alpha^{-1} (\log n + \log q) < c \alpha n / (m 2^m),
\]
as in our hypotheses.

To bound the probability of \eqref{M-lambda-v-condition},
we use a block decomposition of $M$
combined with a decoupling trick familiar from the quadratic Littlewood--Offord problem (see \cite{CTV}*{Lemma~6.3} or \cite{tao-vu}*{Section~7.6}).
To explain the trick, suppose $X$ and $Y$ are independent random variables and $f(X, Y)$ is a function taking values in a vector space, and suppose we are interested in $\mathbf{P}(f(X, Y) = 0)$.
Let $X'$ be an independent copy of $X$.
By Cauchy--Schwarz,
\begin{align*}
  \mathbf{P}(f(X, Y) = 0)
   & \leq \mathbf{P}(f(X, Y) = f(X', Y) = 0)^{1/2}  \\
   & \leq \mathbf{P}(f(X, Y) - f(X', Y) = 0)^{1/2}.
\end{align*}
In particular, applying this iteratively to a function of the form $f(X_1, \dots, X_k, Y)$,
\[
  \mathbf{P}(f(X_1, \dots, X_k, Y) = 0)
  \leq \mathbf{P}\br{
    \sum_{\omega \subset [k]}
    (-1)^{|\omega|} f(X^\omega, Y) = 0
  }^{1/2^k},
\]
where $X^\omega$ indicates $(X_1, \dots, X_k)$ but with $X_i$ replaced with $X'_i$ for $i \in \omega$.
This trick is useful for reducing a polynomial problem to a multilinear problem.

Suppose $[n]$ is partitioned into $m$ blocks of sizes $n_1, \dots, n_m \geq \floor{n/m}$.
Let the corresponding block decomposition of $M$ be
\[
  M =
  \begin{pmatrix}
    B_{11} & \cdots & B_{1m} \\
    \vdots & \ddots & \vdots \\
    B_{m1} & \cdots & B_{mm}
  \end{pmatrix}
  .
\]
Here $B_{ab}$ is an $n_a \times n_b$ matrix
with independent $\alpha$-balanced entries, and different blocks are independent.
Let $f(t) = (t - \lambda_1) \cdots (t - \lambda_m)$.
The block decomposition of $f(M)v$ is
\[
  f(M)v =
  \br{\sum_{x_1, \dots, x_m} (B_{x_0x_1} - \lambda_1 \delta_{x_0x_1}) \cdots (B_{x_{m-1} x_m} - \lambda_m \delta_{x_{m-1} x_m}) v_{x_m}

  }_{x_0=1}^m.
\]

We will treat the blocks $B_{12}, B_{23}, \dots, B_{m1}$ specially.
Let $B'_{12}, B'_{23}, \dots, B'_{m1}$ be independent copies of these blocks.
For $\omega \subset [m]$ let $M^\omega$ be equal to $M$ but with the blocks indicated by $\omega$ replaced with their primed versions, e.g.,
\[
  M^{[m]} =
  \begin{pmatrix}
    B_{11}    & B_{12}'   & B_{13}    & \cdots & B_{1m}     \\
    B_{21}    & B_{22}    & B_{23}'   & \cdots & B_{2m}     \\
              & \vdots    &           & \ddots & \vdots     \\
    B_{m-1,1} & B_{m-1,2} & B_{m-1,3} & \cdots & B_{m-1,m}' \\
    B_{m1}'   & B_{m2}    & B_{m3}    & \cdots & B_{mm}
  \end{pmatrix}.
\]
By $m$ applications of Cauchy--Schwarz,
\[
  \mathbf{P}(f(M)v = 0)
  \leq \mathbf{P}\br{\sum_{\omega\subset[m]} (-1)^{|\omega|} f(M^\omega) v = 0}^{1/2^m}.
\]
The first block of $\sum_{\omega \subset[m]} (-1)^{|\omega|} f(M^\omega) v$ is
\[
  \sum_{\omega \subset[m]} (-1)^{|\omega|} (f(M^\omega)v)_1
  = (B_{12} - B_{12}') (B_{23} - B_{23}') \cdots (B_{m1} - B_{m1}') v_1.
\]

We may assume $v_1 \neq 0$.
Each of the differences $B_{12} - B'_{12}, \dots, B_{m1} - B_{m1}'$ is again a matrix with independent $\alpha$-balanced entries.
If $(f(M)v)_1 = 0$, there is some largest index $i$ such that
\[
  (B_{i,i+1} - B'_{i,i+1}) \cdots (B_{m1} - B'_{m1}) v_1 = 0.
\]
Since different blocks are independent, it follows from $m$ applications of Odlyzko's lemma that
\[
  \mathbf{P}((B_{12} - B'_{12}) \cdots (B_{m1} - B'_{m1}) v_1 = 0)
  \leq \sum_{i=1}^m (1-\alpha)^{n_i}
  \leq m (1-\alpha)^{\floor{n/m}}
\]
Hence
\[
  \mathbf{P}(f(M)v = 0)
  \leq \br{m (1-\alpha)^{\floor{n/m}}}^{1/2^m}
  \lesssim (1-\alpha)^{\floor{n/m}/2^m}.
\]
Assuming $m < n/2$, we may bound this by
\[
  \exp(-\alpha n / (m 2^{m+1})),
\]
which proves our claim.

\subsection{Semi-saturated subspaces}

The following lemma is a linear version of the Chinese remainder theorem. It will be used several times.

\begin{lemma}
  \label{CRT}
  Let $\lambda_1, \dots, \lambda_m \in \mathbf{F}_q$ be distinct,
  let $V_1, \dots, V_m$ be subspaces such that $V_1^\perp, \dots, V_m^\perp$ are independent,
  and let $V = V_1 \cap \cdots \cap V_m$.
  There are $x_1, \dots, x_n \in \mathbf{F}_q^n$ such that
  \[
    \bigcap_{j=1}^m (\lambda_j e_i + V_j)
    =
    x_i + V
    \qquad (1 \leq i \leq n).
  \]
\end{lemma}
\begin{proof}
  The linear map $\mathbf{F}_q^n / V \to \mathbf{F}_q^n / V_1 \oplus \cdots \oplus \mathbf{F}_q^n / V_m$ is injective by definition of $V$,
  so surjective by comparing dimensions.
\end{proof}

Suppose $V \leq \mathbf{F}_q^n$ is semi-saturated and $d$-codimensional.
Then
\[
  e^{-\zeta \alpha n}
  \leq \exp(-\zeta (\alpha n / m)^{1/2})
  < \rho(V)
  \leq 10 / q^d.
\]
Consider all ways of decomposing $V^\perp = V_1^\perp \oplus \cdots \oplus V_m^\perp$, and we will consider the possibility
\[
  \opr{row}(M - \lambda_j) \leq V_j  \qquad (j \in [m]).
\]
Since $V^\perp$ has dimension $d$, the number of ways of decomposing $V^\perp$ is bounded by
the number of partitions of $[d]$ into $m$ intervals times the number of ordered bases of $V^\perp$,
which is at most $2^d q^{d^2}$.
For each, we have, using Lemma~\ref{CRT},
\begin{align*}
  \mathbf{P}\br{X_i \in \bigcap_{j=1}^m \br{\lambda_j e_i + V_j}}
   & = \mathbf{P}(X_i \in x_i + V) \\
   & \leq 11 / q^d
\end{align*}
since $V$ is semi-saturated.
Hence, by independence of the rows,
\[
  \mathbf{P}\br{
    \bigcap_{j=1}^m \{
    \opr{row}(M - \lambda_j) \leq V_j
    \}
  } \leq (11 / q^d)^n.
\]
Hence
\[
  \mathbf{P}\br{
    \bigcap_{j=1}^m \opr{row}(M - \lambda_j) \leq V
  } \leq O(1)^n q^{d^2 - dn}.
\]
As in the previous section, there is some $i \in [n]$ and some $v \in V^\perp \setminus\{0\}$ such that
\[
  \sum_{j=1}^n (1 - |\hat{\mu}_{ij}(v_j)|) < \zeta \alpha n,
\]
so by Markov's inequality there is a set $J \subset [n]$ of size $|J| \geq n/2$ such that
\[
  v_j \in \opr{Spec}_{1 - 2\zeta \alpha} \mu_{ij}
\]
for all $j \in J$.
By Lemma~\ref{small-spec}, assuming $q \geq \zeta^{-1/2}$ (one of our hypotheses),
\[
  |\opr{Spec}_{1-2\zeta\alpha} \mu| \leq O(\zeta^{1/2} q) + 1 = O(\zeta^{1/2} q).
\]
Hence the number of possibilities for $v$ is bounded by
\[
  n 2^n O(\zeta^{1/2} q)^{n/2} q^{n/2} = O(1)^n \zeta^{n/4} q^n,
\]
and the number of possibilities for $V$ is bounded by
\[
  O(1)^n \zeta^{n/4} q^{dn - d(d-1)}.
\]
Hence
\[
  \mathbf{P}\br{
    R
    ~\text{semi-saturated}
    \wedge
    \opr{codim} R = d
  }
  \leq O(1)^n \zeta^{n/4} q^d.
\]
For any semi-saturated $V$ we have $q^d = O(1)^n$,
so this is negligible provided $\zeta$ is sufficiently small.

\subsection{Unsaturated subspaces}

\def\mathcal{R}{\mathcal{R}}
Finally we consider unsaturated subspaces.
Let $\UU_i$ be the set of $m$-tuples $(V_1, \dots, V_m)$ such that $V = V_1 \cap \cdots \cap V_m$ is unsaturated and $\rho(V) = \rho_i(V)$.
Let $\mathcal{R}$ be the $m$-tuple $(\opr{row}(M - \lambda_j))_{j=1}^m$ whose intersection is $R$.
It suffices to show that
\begin{equation}
  \label{unsat-goal-m>1}
  \mathbf{P}(\mathcal{R} \in \UU_i) \leq e^{-cn}
\end{equation}
for each $i$.
Here is a brief summary of the argument.
Let $\nu_{ij}$ be constructed from $\mu_{ij}$ as in Lemma~\ref{lem:nu}.
Let
\[
  \mathcal{R}' = (\opr{row}(N_1), \dots, \opr{row}(N_m)),
\]
where $N_j$ is $M - \lambda_j$ but with most of the rows replaced with independent copies of $Y$, where $Y$ satisfies \eqref{Yi-law}.
Then we will show that, for any $\VV \in \UU_i$,
\[
  \mathbf{P}(\mathcal{R} = \VV) \leq e^{-cn} \mathbf{P}(\mathcal{R}' = \VV).
\]
We will then use the disjointness of the events $\{\mathcal{R}' = \VV\}$ to infer \eqref{unsat-goal-m>1}.

Let $\VV \in \UU_i$.
Let $Y_1, \dots, Y_r$ be independent copies of $Y$.
Let $t = n - r$.
Let
\[
  B_V = \{Y_1, \dots, Y_r~\text{lin.~ind.~and in}~V\}.
\]
As before, by Odlyzko's lemma
\begin{equation}
  \label{BV-ratio-m>1}
  \mathbf{P}(B_V) \geq
  1 - r (1 - \alpha/8)^{t+1} / \mathbf{P}(Y \in V).
\end{equation}
We will again ensure that this is at least $1/2$.
By independence of $X_1, \dots, X_n$ and $Y_1, \dots, Y_r$,
\begin{equation}
  \label{B-conditioning}
  \mathbf{P}(\mathcal{R} = \VV)
  = \frac{\mathbf{P}(B_V \wedge \mathcal{R} = \VV)}{\mathbf{P}(B_V)}.
\end{equation}
If $B_V$ holds and $\opr{row}(M - \lambda_j) = V_j$ for each $j$ then,
by the exchange lemma,
for each $j \in \{1, \dots, m\}$
there is a set $T_j \subset [n]$ of size $t$ such that
$\opr{row}(N_j) = V_j$, where $N_j$ is the matrix obtained from $M - \lambda_j$ by replacing the rows indexed by $T_j^c$ with $Y_1, \dots, Y_r$.
The rows indexed by $T_j^c$ must also be contained in $V_j$.
Let $T = T_1 \cup \cdots \cup T_m$.\footnote{The need to take the union here is the reason we have to broaden the definition of unsaturated,
  and ultimately the reason why $O(\exp(-cn^{1/2}))$ appears in Theorem~\ref{main} rather than $O(e^{-cn})$.}
Then
\def\Sigma{\Sigma}
\def{\sigma \in \SS}{{\sigma \in \Sigma}}
\[
  \label{B&R-bound}
  \mathbf{P}(B \wedge \mathcal{R} = \VV)
  \leq \sum_{\sigma \in \SS}
  \mathbf{P}(\mathcal{R}_\sigma = \VV)
  \prod_{i'\notin T} \mathbf{P}\br{\bigcap_{j=1}^m \{X_{i'} - \lambda_j e_{i'} \in V_j\}},
\]
where $\Sigma$ is the set of all $\sigma = (T_1, \dots, T_m)$ such that $T_j \subset[n]$ and $|T_j|=t$ for each $j$,
and
\[
  \mathcal{R}_\sigma = (\opr{row}(N_1), \dots, \opr{row}(N_m)).
\]
Hence, using Lemma~\ref{CRT},
\begin{align*}
  \mathbf{P}(\mathcal{R} = \VV)
   & \lesssim \sum_{\sigma \in \SS}
  \mathbf{P}(\mathcal{R}_\sigma = \VV)
  \frac{\prod_{i' \notin T} \mathbf{P}\br{\bigcap_{j=1}^m \{X_{i'} - \lambda_j e_{i'} \in V_j\}}}
  {\mathbf{P}(Y \in V)^r}
  \\
   & = \sum_{\sigma \in \SS}
  \mathbf{P}(\mathcal{R}_\sigma = \VV)
  \frac{\prod_{i' \notin T} \mathbf{P}\br{X_{i'} - x_{i'} \in V}}
  {\mathbf{P}(Y \in V)^r}
  \\
   & \leq \sum_{\sigma \in \SS}
  \mathbf{P}(\mathcal{R}_\sigma = \VV)
  \max_{i'} \frac{\mathbf{P}(X_{i'} - x_{i'} \in V)^{n - mt}}{\mathbf{P}(Y \in V)^r}
  .
\end{align*}
Summing over $\VV \in \UU_i$,
and assuming $mt < n/2$,
\begin{align*}
  \mathbf{P}(R \in \UU_i)
   & \lesssim \sum_{\sigma \in \SS}
  \mathbf{P}(\mathcal{R}_\sigma \in \UU_i)
  \max_{\VV \in \UU_i} \theta_\VV^{n/2} / \mathbf{P}(Y \in V)^{(m-1)t}
  \\
   & \leq
  \binom{n}{t}^m \max_{\VV \in \UU_i} \theta_\VV^{n/2} / \mathbf{P}(Y \in V)^{(m-1)t}
  ,
\end{align*}
where
\[
  \theta_\VV
  = \max_{i'} \frac{\mathbf{P}(X_{i'} - x_{i'} \in V)}{\mathbf{P}(Y \in V)}.
\]
To complete the argument, we must show that, for all $\VV \in \UU_i$,
\begin{enumerate}[(a)]
  \item\label{a-m>1} $\mathbf{P}(Y \in V) \geq 2 r (1 - \alpha/8)^{t+1}$ (so that \eqref{BV-ratio-m>1} $\geq 1/2$);
  \item\label{a'-m>1} $\mathbf{P}(Y \in V)^{(m-1)t} > e^{-n/10}$;
  \item\label{b-m>1} $\theta_\VV \leq 0.6$.
\end{enumerate}

Let $\VV \in \UU_i$ and let $d = \opr{codim} V$.
By Lemma~\ref{Y-lemma},
\[
  10 / q^d
  < \rho(V) = \rho_i(V)
  \leq \br{1/2 + e^{-c\alpha s}} |\mathbf{P}(Y \in V) - 1/q^d|,
\]
provided that $V^\perp$ has no nonzero vector with support size less than $s$.
In particular $\mathbf{P}(Y \in V) > 20(1 + 2e^{-c\alpha s})^{-1} / q^d$,
and
\begin{align*}
  \mathbf{P}(X_{i'} \in V)
   & \leq 1/q^d + \rho(V)                                                   \\
   & \leq 1/q^d + (1/2 + e^{-c\alpha s}) (\mathbf{P}(Y \in V) - 1/q^d))             \\
   & \leq (1/2 + e^{-c\alpha s}) (\mathbf{P}(Y \in V) + 1/q^d)                      \\
   & \leq (1/2 + e^{-c\alpha s})(1 + (1 + 2e^{-c\alpha s})/20) \mathbf{P}(Y \in V),
\end{align*}
so \ref{b-m>1} is satisfied, provided $s > C \alpha^{-1}$ for large enough $C$.
Moreover, since
\[
  \mathbf{P}(Y \in V) > \rho(V),
\]
\ref{a-m>1} and \ref{a'-m>1} are satisfied provided
\[
  \rho(V) \geq \max\left\{
  2 r \exp(- c \alpha t),
  \exp(- c (m-1)^{-1} t^{-1} n)
  \right\}.
\]
A good choice for $t$ is $t \asymp (\alpha^{-1} n/m)^{1/2}$.
Then it suffices that
\[
  \rho(V) > \exp\br{ -\zeta (\alpha n / m)^{1/2}}
\]
for sufficiently small constant $\zeta$,
as in the definition of unsaturated.

\subsection{Correlations of eigenvalues}

In this last subsection we will use Theorem~\ref{thm:saturation-m} to prove Theorem~\ref{thm:correlation-bound}.
We assume $m < c \log n$ and
\[
  C \leq \log q
  < (\zeta / 2) (\alpha n)^{1/2} / m^{3/2}.
\]
Let $\lambda_1, \dots, \lambda_m \in \mathbf{F}_q$ be distinct and let $M \sim \M(\bm{\mu})$.
Recall that $E_\lambda$ is the event that $M$ has eigenvalue $\lambda$.
We will estimate
\[
  \mathbf{P}(E_{\lambda_1} \cap \cdots \cap E_{\lambda_m}).
\]

Let
\[
  R = \bigcap_{j=1}^m \opr{row}(M - \lambda_j).
\]
By Theorem~\ref{thm:saturation-m},
\[
  \mathbf{P}(R~\text{not saturated})
  \lesssim_\alpha
  \exp\br{ -c \alpha n / (m 2^m)}.
\]
By Theorem~\ref{thm:prob-Mk-nonsingular},
\[
  \mathbf{P}(\opr{codim} R \geq md)
  \leq \sum_{j=1}^m \mathbf{P}(\opr{codim} \opr{row}(M - \lambda_j) \geq d)
  \lesssim m q^{-d}.
\]
Fix an integer $d \geq 1$ so that
\[
  \frac{d \log q}{\zeta (\alpha n)^{1/2} / m^{3/2}} \in [1/4, 1/2] .
\]
Then
\begin{equation}
  \label{R-sat-and-large}
  \mathbf{P}(R~\text{saturated} \wedge \opr{codim} R \leq md)
  = 1 - O_\alpha(\exp(-c \zeta (\alpha n)^{1/2} / m^{3/2})).
\end{equation}

Let $E_\lambda(v) = \{Mv = \lambda v\}$.
Since $\lambda_1, \dots, \lambda_m$ are distinct,
\[
  E_{\lambda_1} \cap \cdots \cap E_{\lambda_m}
  = \bigcup_{\substack{v_1, \dots, v_m \in \mathbf{F}_q^n \\
      \text{lin. ind.}}}
  E_{\lambda_1}(v_1) \cap \cdots \cap E_{\lambda_m}(v_m).
\]
Fix linearly independent $v_1, \dots, v_m \in \mathbf{F}_q^n$.
Let $V = v_1^\perp \cap \cdots \cap v_m^\perp$.
If the event ${E_{\lambda_1}(v_1) \cap \cdots \cap E_{\lambda_m}(v_m)}$ holds
then $R \leq V$,
so
\[
    \rho(V) \leq q^{\dim(V/R)} \rho(R).
\]
Assuming $R$ is saturated and $\opr{codim} R \leq md$, we therefore must have
\begin{equation}
  \label{eq:V-sat}
  \rho(V)
  < \exp(-(\zeta/2) (\alpha n / m)^{1/2})
\end{equation}
(a deterministic condition on $V$).
Now
\begin{align}
  E_{\lambda_1}(v_1) \cap \cdots \cap E_{\lambda_m}(v_m)
   & = \bigcap_{j=1}^m \bigcap_{i=1}^n
  \left\{ (X_i - \lambda_j e_i) \cdot v_j = 0 \right\} \\
   & = \bigcap_{i=1}^n
  \left\{X_i \in \bigcap_{j=1}^m \br{\lambda_j e_i + v_j^\perp} \right\}.
  \label{Evi-rows}
\end{align}
By Lemma~\ref{CRT} there are $x_1, \dots, x_n \in \mathbf{F}_q^n$ (depending on $\lambda_1, \dots, \lambda_m, v_1, \dots, v_m$) such that
\[
  \bigcap_{j=1}^m \br{\lambda_j e_i + v_j^\perp}
  = x_i + V.
\]
Hence
\begin{align*}
  \mathbf{P}\br{X_i \in \bigcap_{j=1}^m \br{\lambda_j e_i + v_j^\perp}}
   & = \mathbf{P}(X_i \in x_i + V) \\
   & = 1/q^m + O(\rho(V)).
\end{align*}
Thus by \eqref{Evi-rows} and independence of $X_1, \dots, X_n$,
\[
  \mathbf{P}\br{E_{\lambda_1}(v_1) \cap \cdots \cap E_{\lambda_m}(v_m)}
  = (1/q^m + O(\rho(V)))^n
  = q^{-mn} \exp O(q^m \rho(V) n).
\]
Summing over all linearly independent $v_1, \dots, v_m$ up to scale,
ignoring those not satisfying \eqref{eq:V-sat},
and accounting for the possibility that $R$ is either not saturated
or of codimension at least $m d$ using \eqref{R-sat-and-large},
it follows that
\begin{align*}
  \mathbf{P}(E_{\lambda_1} \cap \cdots \cap E_{\lambda_m})
   & \leq \frac{(q^n - 1)^m}{(q-1)^m} q^{-mn} \exp O(\exp(-c \zeta (\alpha n / m)^{1/2}) n) \\
   & \qquad + O_\alpha(\exp(-c\zeta (\alpha n)^{1/2} / m^{3/2})                             \\
   & = (q-1)^{-m}
  + O_\alpha(\exp(-c \zeta (\alpha n)^{1/2} / m^{3/2}))
  .
\end{align*}
This finishes the proof of Theorem~\ref{thm:correlation-bound}.


\section{Introduction}\label{sec:intro}

Horizontal coordinate assignment is the final phase
of Sugiyama's framework for drawing directed graphs~\cite{sugiyama_etal:81,hn-hgda-13}.
By that point, the original graph has been transformed into a directed acyclic graph
with its vertices assigned to a sequence of layers,
and ordered within these layers.
Moreover, the layer assignment is proper,
i.e., edges spanning layers are subdivided by dummy vertices
so that two vertices are adjacent only if they are assigned to neighboring layers.

Brandes and Köpf~\cite{bk-fshca-02} proposed a simple algorithm
to determine $x$-coordinates for the vertices such that
their order is preserved and
the distance between each two vertices is at least some~$\delta > 0$.
The algorithm runs in time linear in the size of the input
and is implemented and taught widely.

The original publication, however, contains two mistakes.
The first is well known and easy to fix.
The other, however, is not commonly known, less straightforward,
and, to the best of our knowledge, no solution has been proposed.

The purpose of this short paper is
to identify clearly where these two mistakes occur,
and to provide suitable corrections.
Our proposed corrections do not alter the behavior of the algorithm
and do not clash with extensions that have been proposed to accommodate,
for instance, vertices of varying size, ports, and other constraints~\cite{b-rasf-07,rsch-sphnca-15}.

\section{Background}\label{sec:recap}

In this section we sketch the algorithm of Brandes and Köpf.
Two mistakes, both occurring in the same subroutine,
are identified and corrected in the next section.

In the horizontal coordinate assignment problem,
we are given a layered directed acyclic graph $G=(V\uplus B,E;L)$,
i.e., a directed acyclic graph $G=(V\cup B,E)$
with two types of vertices
(original vertices and potential bend points of edges)
and a sequence of layers $L=(L_1,\ldots,L_h)$
that forms an ordered partition of $V\cup B$.
The layering is required to be proper,
i.e., adjacent vertices are in neighboring layers.
Moreover, the vertices are ordered
within each layer $L_i=\{\vertex{i}{1},\ldots,\vertex{i}{|L_i|}\}$,
where $\vertex{i}{k}$ denotes the $k$th vertex in the $i$th layer.
Thus, the topology of the drawing has already been fixed,
and the horizontal coordinate assignment algorithm is now to determine
the shape and the final metrics.

\begin{figure}
\centering
\includegraphics[width=0.75\linewidth]{example}\\
\caption{Example illustrating the various definitions.
The vertices in $V\cup B$ together with the alignment (black) and predecessor (orange) relations
form a directed graph, the strongly connected components of which are the blocks (light blue rectangles). Blocks therefore form a DAG and are assigned to a class (green polygon) defined by the highest sink (labeled vertex) they can reach.}
\label{fig:example}
\end{figure}

The algorithm of Brandes and Köpf consists of the following three steps,
the first two of which are repeated four times,
once for each combination of vertical and horizontal orientations.
We describe the top-to-bottom, left-to-right case
in which vertices are left-aligned conditional on upper neighbors;
the other three cases are symmetric.
Figure~\ref{fig:example} illustrates the subsequent definitions.
\begin{enumerate}
\item \emph{Vertical alignment:}
  Every vertex $v\in V\cup B$ is assigned a vertex, $\align{v}$,
  that can be~$v$ itself or otherwise it is either a neighbor on the next lower level
  or the uppermost vertex when tracing back these alignment pointers.
  This partitions the vertex set into singly-linked (possibly singleton) cycles
  called \emph{blocks}, where the topmost vertex in a block is called the \emph{root}.
  All vertices in a block ultimately receive the same $x$-coordinate
  in order to straighten long edges (by aligning subdivision vertices in~$B$)
  and to reduce edge lengths (by aligning vertices in $V$ with a median neighbor
  in the layer above).
\item \emph{Horizontal compaction:} Next, vertices are aligned to the left.
  By adding an edge between every vertex and its predecessor (left neighbor), if present,
  we obtain a directed acyclic graph of blocks.
  The sinks of this DAG are blocks whose roots are leftmost in their layer
  and are hence ordered vertically.
  Let the sink of a vertex be the highest sink reachable from any vertex in its block by the predecessor and alignment edges.
  All vertices and blocks with the same highest sink form a \emph{class}.
  In Figure~\ref{fig:example}, there are three sinks defining a class, namely $v_1^{(1)}$, $v_1^{(2)}$, and $v_1^{(4)}$.
  The vertices in a class have a unique minimum $x$-coordinate relative to their common sink,
  and it can be obtained from longest-path layering.
  We say two classes are \emph{neighboring} each other if they contain vertices on the same layer.
  If a class is not neighboring another class with a higher sink,
  its own sink is placed at $x$-coordinate zero.
  In Figure~\ref{fig:example}, this is the case for the class with sink $v_1^{(1)}$.
  Otherwise it is placed as close to higher classes as possible.
  In Figure~\ref{fig:example}, this is the case for the two other classes.
\item \emph{Balancing:} The four $x$-coordinates per vertex
  obtained from repeating the previous steps with different orientations
  are combined into one by aligning the four resulting drawings and taking the average of the two median coordinates per vertex.
\end{enumerate}
Both problems occur in the horizontal compaction step.
We therefore reproduce the pseudo-code of Alg.~3 from the original publication.
It does not require any special data structures other than the vertex arrays
listed in Tab.~\ref{tab:vars}.

\begin{table}
\caption{All auxiliary data is stored in vertex arrays.}
\label{tab:vars}
\centering
\begin{tabular}{|r@{\quad}|@{\quad}l|}\hline
$\vertex{i}{k}$ & $k$th vertex in $i$th layer\\[0.5ex]\hline
\bf array & \bf content\\\hline
$\pos{v}$ & rank in layer, i.e., $\pos{\vertex{i}{k}}=k$\\
$\pred{v}$ & preceding vertex in same layer, i.e., $\pred{\vertex{i}{k}}=\vertex{i}{k-1}$\\
$\align{v}$ & vertex below in same block (or root for lowest)\\
$\root{v}$ & highest vertex in same block\\
$\sink{v}$ & if $v$ is a root:\enskip highest leftmost root, defining the class\\
$\shift{v}$ & if $v$ is a sink:\enskip offset by which class is to be shifted\\
$x[v]$ & horizontal coordinate (relative to sink, later absolute)\\\hline
\end{tabular}
\end{table}

\begin{algorithm}[t]
\renewcommand{\thealgocf}{3}
\caption{Horizontal compaction}
\BlankLine
\KwSty{function} place\_block($v$)\\
\Begin
{ \If{$x[v]$ undefined}
  { $x[v]\gets0$;\quad $w\gets v$\;
    \Repeat{$w=v$}
    { \If{$\pos{w}>1$}
      { $u\gets\root{\pred{w}}$\;
        place\_block($u$)\;
        \lIf{$\sink{v}=v$}{$\sink{v}\gets\sink{u}$}
        \uIf{$\sink{v}\neq\sink{u}$}{{\color{red!50!black}\nlset{(A)}\label{ln:offset}}$\shift{\sink{u}}\gets\min\{ \shift{\sink{u}},\, x[v] - x[u] - \delta \}$\;}
        \Else{$x[v]\gets\max\{ x[v],\,x[u]+\delta\}$\;}
      }
      $w\gets\align{w}$\;
    }
  }
}
\BlankLine
initialize $\sink{v}\gets v$, $v\in V\cup B$\;
initialize $\shift{v}\gets\infty$, $v\in V\cup B$\;
initialize $x[v]$ to be undefined, $v\in V\cup B$\;
\BlankLine
{\scriptsize // root coordinates relative to sink}\\
\ForEach{$v\in V\cup B$}{\lIf{$\root{v}=v$}{place\_block($v$)}}
\BlankLine
{\scriptsize // absolute coordinates}\\
\ForEach{$v\in V\cup B$}
{ $x[v]\gets x[\root{v}]$\;
  {\color{red!50!black}\nlset{(S)}\label{ln:shift}}\If{$\shift{\sink{\root{v}}}<\infty$}
  {$x[v]\gets x[v]+\shift{\sink{\root{v}}}\;$}
}
\end{algorithm}

\section{Problems and Corrections}\label{sec:corrections}

The problematic lines of pseudo-code concern the computation
of absolute coordinates and the accumulation of shift values for classes.
They are marked~\ref{ln:shift} and~\ref{ln:offset} in Alg.~3.

\paragraph{Double shifting.}
The easier problem manifests itself in line~\ref{ln:shift} of Alg.~3.
To determine absolute coordinates, we want to combine, for every vertex,
the relative coordinate of its block with respect to the sink of its class (stored at the root),
with the offset of the entire class (stored at the sink).
The way Alg.~3 is formulated, offsets are actually added twice
for vertices whose root has already been shifted to its final $x$-coordinate.

Multiple implementors have noted and fixed the problem in different ways.
The correction we provide in Alg.~3a
involves aligning blocks in the recursive subroutine \textsf{place\_block}
as soon as the relative coordinate of the root with respect to the sink has been determined.
In this way, block alignment and shifting are separated and
only offsets have to be added to every vertex in the last line of Alg.~3b.
Given the name of the subroutine, this should have been the procedure all along.
And to simplify later steps, we also assign the sink to vertices, not just roots.

\begin{algorithm}[t]
\renewcommand{\thealgocf}{3a}
\caption{\label{alg:placeblock}Placing a block (not just the root)}
\BlankLine
\KwSty{function} place\_block($v$)
\SetKwBlock{Begin}{}{end}
\Begin
{ \If{$x[v]$ undefined}
  { $x[v]\gets0$\,;\quad $w\gets v$\;
    \Repeat{$w=v$}
    { \If{$\pos{w}>1$}
      { $u\gets\root{\pred{w}}$\;
        place\_block($u$)\;
        \lIf{$\sink{v}=v$}{$\sink{v}\gets\sink{u}$}
        \lIf{$\sink{v}=\sink{u}$}
            {$x[v]\gets\max\{ x[v],\,x[u]+\delta\}$}
        {\color{red!50!black}{\scriptsize // class offsets (shift of sinks) are calculated later}}
      }
      $w\gets\align{w}$\;
    }
    {\color{red!50!black}{\scriptsize // align the whole block}\\
    \While{$\align{w}\neq v$}{$w\gets\align{w}$\; $x[w]\gets x[v]$\; $\sink{w}\gets\sink{v}$}}
  }
}
\end{algorithm}

\paragraph{Shift accumulation.}
Problem~\ref{ln:offset} is a serious flaw that has not been documented before.
It is not clear how often it has actually resulted in visually notable problems,
but it is easy to craft instances in which it becomes severe.

During compaction, shift values are determined
for preceding classes relative to the current class.
The implicit assumption in line~\ref{ln:offset} is, however,
that the current class is not shifted itself.
As a consequence, shift values are not accumulated along critical paths in the DAG of classes.
It is not sufficient to consider the shift value of $\sink{v}$ in line~\ref{ln:offset}
because it may not be in its final state, yet.
The correction we propose in Alg.~3b therefore
separates the determination of shift values
from the placement of blocks relative to the sink of their class.

A high-level solution is to construct the DAG of classes
and perform another longest-path layering,
this time with respect to the sources in the DAG,
by placing each class as close as possible to its right neighbors.
The following lemma implies that classes are stacked diagonally, top-to-bottom, right-to-left.
It is therefore possible to accumulate shift values in this order
without recursion or explicit representation of all preceding classes.

\begin{lemma}
Let $\vertex{i}{k_1},\vertex{i}{k_2}$
be two vertices in the same layer $L_i$, $1\leq i\leq h$
with $\sink{\vertex{i}{k_1}}=\vertex{h_1}{1}$ and $\sink{\vertex{i}{k_2}}=\vertex{h_2}{1}$
after all blocks have been placed.
If $k_1<k_2$, then $h_2\leq h_1$.
\end{lemma}
\begin{proof}
In the directed graph consisting of the alignment and predecessor relations,
every vertex can reach all sinks (and maybe more) that any vertex further to the left can reach.
The highest reachable sink is therefore at least as high as that of any vertex to the left.
\end{proof}

The monotonic ordering of classes can be utilized as follows.
Instead of ensuring that all critical paths determining the total shifts of the classes
have already been traversed by recursion
(as in the placement of blocks)
we can now start from the class with the highest sink
because we know it is rightmost in each layer.
For each sink, from top to bottom, we trace the lower contour of each class,
and make sure that the preceding classes are shifted such that
a minimum separation guarantees they do not overlap.
This is similar to the shifting of subtrees
in the tree-drawing algorithm of Reingold and Tilford~\cite{reingold/tilford:81}.

\begin{algorithm}[t]
\renewcommand{\thealgocf}{3b}
\caption{Horizontal compaction}
initialize $\sink{v}\gets v$, $v\in V\cup B$\;
initialize $\shift{v}\gets\infty$, $v\in V\cup B$\;
initialize $x[v]$ to be undefined, $v\in V\cup B$\;
\BlankLine
{\scriptsize // coordinates relative to sink}\\
\ForEach{$v\in V\cup B$}{\lIf{$\root{v}=v$}{place\_block($v$)}}
\BlankLine
{\color{red!50!black}
{\scriptsize // class offsets}\\
\For{$i=1,\ldots,h$}
{ \If{$\sink{\vertex{i}{1}}=\vertex{i}{1}$}
  { \lIf{$\shift{\sink{\vertex{i}{1}}}=\infty$}{$\shift{\sink{\vertex{i}{1}}}\gets0$}
    $j\gets i$\,;\quad$k\gets1$\;
    \Repeat{$k>|L_j|$ \KwSty{or} $\sink{v}\neq\sink{\vertex{j}{k}}$}
    { $v\gets\vertex{j}{k}$\;
      \While{$\align{v}\neq\root{v}$}
      { $v\gets\align{v}$\,;\quad$j\gets j+1$\;
        \If{$\pos{v}>1$}
        { $u\gets\pred{v}$\;
          \mbox{\color{black}$\shift{\sink{u}}\gets\min\{\shift{\sink{u}},\, {\color{red!50!black}\shift{\sink{v}}+}x[v]-(x[u]+\delta) \}$}
        }
      }
      $k\gets\pos{v}+1$
    }
  }
}}
\BlankLine
{\scriptsize // absolute coordinates}\\
\lForEach{$v\in V\cup B$}{\color{red!50!black}$x[v]\gets x[v]+\shift{\sink{v}}$}
\end{algorithm}

The implementation shown in Alg.~3b traverses the layers from top to bottom.
If the leftmost vertex is a sink that still has an infinite shift value,
the class is not to the left of any previously processed class with a higher sink.
It can therefore be aligned without any offset, i.e., a shift value of zero.
The lower contour of a class is traced by either moving down in a block (using $\align{v}$)
or, if we have reached the lower end of a block pointing back at the root,
moving one position to the right.
The tracing ends when there is no right neighbor
or if the right neighbor is part of a class with a higher sink.

While traversing the lower contour,
a predecessor~$u$ of the current vertex~$v$, if any,
belongs to a class with a lower sink.
We therefore update the shift value of $\sink{u}$
to ensure minimum separation between the classes of~$u$ and~$v$.
Since we are starting with an upper bound and proceed from right to left,
shift values can only decrease,
pushing classes further to the left after their initial placement.

\section{Discussion}\label{sec:concl}

We identified and corrected two flaws in the compaction step
of the well-known horizontal coordinate assignment algorithm
of Brandes and Köpf~\cite{bk-fshca-02}.
The corrections are internal to the algorithm,
they do not alter running time in any substantial way,
and are unlikely to interfere with any of the algorithm's extensions.

The first mistake was the result of a discrepancy between the implementation
and an attempt to make the pseudo-code more readable.
Others have identified and corrected the issue before,
notably Florian Fischer (Diplom~2004, Passau)
and John Julian Carstens (M.Sc.~2012, Kiel) in their theses.
A frequently proposed correction
only checks whether the vertex to be shifted is a root,
and therefore relies implicitly on the top-to-bottom processing order
to ensure that roots are shifted
before the other members of a block inherit their coordinate.
We believe that the correction proposed here is more appropriate.

Walter and Zink recently noted and clearly identified problem~\ref{ln:offset}.
We developed multiple corrections,
but present only one that aligns most closely with the original algorithm.
We shortly describe one alternative version of Alg.~3b in the appendix,
also because it operates more explicitly on the DAG of classes.
These corrections were developed without realizing that
the problem had already been identified
by Damon Lundin while working for IBM Blueworks Live (personal communication, 2013).
He even proposed a fix that bears similarity with our independently developed solutions
but does not work in general.
Unfortunately, the conversation was only recovered while preparing this contribution.

\bibliographystyle{splncs04}