2023

1]Center for the Mathematics and Symmetry and Computation, University of
Western Australia, Perth, 6009, Australia

2]Department of Mathematics: Analysis, Logic and Discrete Mathematics, Ghent
University, Belgium

3]Department of Mathematics and Data Science, Vrije Universiteit Brussel,
Belgium

4]Department of Mathematics, University of California San Diego, United States

# The proportion of non-degenerate complementary subspaces in classical spaces

S.P. Glasby<EMAIL_ADDRESS>Ferdinand Ihringer
<EMAIL_ADDRESS>Sam Mattheus<EMAIL_ADDRESS>[  [  [  [

###### Abstract

Given positive integers $e_{1},e_{2}$, let $X_{i}$ denote the set of
$e_{i}$-dimensional subspaces of a fixed finite vector space
$V=({\mathbb{F}}_{q})^{e_{1}+e_{2}}$. Let $Y_{i}$ be a non-empty subset of
$X_{i}$ and let $\alpha_{i}=|Y_{i}|/|X_{i}|$. We give a positive lower bound,
depending only on $\alpha_{1},\alpha_{2},e_{1},e_{2},q$, for the proportion of
pairs $(S_{1},S_{2})\in Y_{1}\times Y_{2}$ which intersect trivially. As an
application, we bound the proportion of pairs of non-degenerate subspaces of
complementary dimensions in a finite classical space that intersect trivially.
This problem is motivated by an algorithm for recognizing classical groups. By
using techniques from algebraic graph theory, we are able to handle orthogonal
groups over the field of order 2, a case which had eluded Niemeyer, Praeger,
and the first author.

###### keywords:

expander mixing lemma, finite classical group, opposition graph

##  1 Introduction

In this paper we use techniques from algebraic graph theory to solve a problem
that arose from computational group theory. More precisely, we use the
expander mixing lemma for bipartite graphs to establish bounds that are useful
for algorithms which ‘recognise’ classical groups acting on their natural
module, a central and difficult computational problem. The nature of this
recognition problem is sketched in Section 1.2.

Let ${\mathbb{F}}$ be a finite field, let $e_{1},e_{2}$ be positive integers
and let $V={\mathbb{F}}^{e_{1}+e_{2}}$ be an $(e_{1}+e_{2})$-dimensional
${\mathbb{F}}$-space endowed with a non-degenerate quadratic, symplectic or
hermitian form. We bound the probability that a non-degenerate
$e_{1}$-subspace $S_{1}$ of $V$, and a non-degenerate $e_{2}$-subspace $S_{2}$
of $V$, intersect trivially that is, satisfy $S_{1}\cap S_{2}=\\{0\\}$. Except
for orthogonal spaces with $q=2$, this problem was solved in (GNP2022, ,
Theorem 1.1), using a combinatorial double-counting argument (GNP2022, , §3).
The following theorem gives sharper bounds, without exception, and is proved
via relatively straightforward calculations involving the second largest
eigenvalue of a graph, see Section 1.1.

######  Theorem 1.1.

Let $V={\mathbb{F}}^{e_{1}+e_{2}}$ be a non-degenerate orthogonal, symplectic
or hermitian space where ${\mathbb{F}},e_{1},e_{2}$ are given in Table 1. Let
$Y_{i}$ be the set of all non-degenerate $e_{i}$-subspaces of $V$ (of a fixed
type $\sigma_{i}\in\\{-,+\\}$ in the orthogonal case). Then the proportion of
pairs $(S_{1},S_{2})\in Y_{1}\times Y_{2}$ for which $S_{1}\cap S_{2}=\\{0\\}$
is at least $1-\frac{c}{|{\mathbb{F}}|}$ where $c$ is given in Table 1. We may
take $c=\frac{3}{2}$ if $(e_{1},e_{2},q)\neq(1,1,2)$.

Table 1: Choices for ${\mathbb{F}}$, $e_{1}$, $e_{2}$, form on $V$, $Y_{i}$ and $c$ in Theorem 1.1 ${\mathbb{F}}$ | $e_{1}$ | $e_{2}$ | form on $V={\mathbb{F}}^{e_{1}+e_{2}}$ |  $e_{i}$-subspaces $Y_{i}$ | $c$
---|---|---|---|---|---
${\mathbb{F}}_{q}$ | even | even | orthogonal of | non-degenerate of | $\nicefrac{{3}}{{2}}$
|  |  | type $\varepsilon\in\\{-,+\\}$ | type $\sigma_{i}\in\\{-,+\\}$ |
${\mathbb{F}}_{q}$ | even | even | symplectic | non-degenerate | $\nicefrac{{10}}{{7}}<\nicefrac{{3}}{{2}}$
${\mathbb{F}}_{q^{2}}$ | $\geqslant 1$ | $\geqslant 1$ | hermitian | non-degenerate | $\nicefrac{{3}}{{2}}$
|  |  |  | $(e_{1},e_{2},q)\neq(1,1,2)$ |

The non-degenerate subspaces of a symplectic space have even dimension so that
$e_{1}$ and $e_{2}$ are both even in the second line of Table 1. In the case
that $V$ is a non-degenerate orthogonal space the $e_{i}$ are also both even;
however this is for a different reason. The authors of GNP2022a , in
forthcoming work, describe an algorithm for recognising classical groups, and
the papers GNP2022 ; GNP2022a  provide the necessary background. In the
algorithmic application the subspace $S_{i}$ is the image of $g_{i}-1$ for
some element $g_{i}$ of the orthogonal group on $V$, and $S_{i}$ is non-
degenerate of _minus_ type by (GNP2022a, , Lemma 3.8(b)). Hence the $e_{i}$
are even in the first line of Table 1, as claimed.

In the unitary case, we have $c=2$ when $(e_{1},e_{2},q)=(1,1,2)$ and $c=1.26$
when $e_{1},e_{2}\geqslant 2$, see Theorem 5.2. The bounds listed in Table 1
all satisfy $1-\frac{3}{2|{\mathbb{F}}|}\geqslant\frac{1}{4}$, and they
facilitate a uniform analysis, for all fields, of a randomized algorithm for
recognising classical groups. In contrast, the values of $c$ in (GNP2022, ,
Table 1) are 2.69 (for $q\geqslant 3$), 1.67 and 1.8 in the orthogonal,
symplectic and unitary cases, respectively. Further, our methods are somewhat
stronger and easier to apply than those in GNP2022 , and offer hope for
extensions, see Section 6.

###  1.1 $q$-Kneser graphs

Let $V=({\mathbb{F}}_{q})^{d}$ be a $d$-dimensional vector space over the
field with $q$ elements. Let $e_{1},e_{2}$ be positive integers. For $i=1,2$,
denote by $X_{i}$ the set of $e_{i}$-dimensional subspaces of $V$. We refer to
an element $S_{i}\in X_{i}$ as an _$e_{i}$ -subspace_ or an _$e_{i}$ -space_.
Let $\Gamma_{d,e_{1},e_{2}}$ be the bipartite graph whose vertex set is the
disjoint union $X_{1}\mathbin{\dot{\cup}}X_{2}$ (where we take two disjoint
copies of the set of $e_{1}$-spaces if $e_{1}=e_{2}$), and where two vertices
$(S_{1},S_{2})\in X_{1}\times X_{2}$ are adjacent whenever $S_{1}$ and $S_{2}$
intersect trivially. The condition $S_{1}\cap S_{2}=\\{0\\}$ is equivalently
to $\dim(S_{1}+S_{2})=e_{1}+e_{2}$.

The $q$-Kneser graph $q{\kern-1.0pt}K(d,e)$ has been previously studied, for
example, see BBS2011 ; CCESW2020 . The vertices of $q{\kern-1.0pt}K(d,e)$
comprise $e$-subspaces of $V=({\mathbb{F}}_{q})^{d}$ and $\\{S_{1},S_{2}\\}$
is an edge if $S_{1}\cap S_{2}=\\{0\\}$. If $q{\kern-1.0pt}K(d,e)$ has
adjacency matrix $A$, then the _bipartite double_ of $q{\kern-1.0pt}K(d,e)$
has adjacency matrix $\left[\begin{smallmatrix}0&A\\\
A^{T}&0\end{smallmatrix}\right]$ and is isomorphic to $\Gamma_{d,e,e}$. The
spectrum of $qK(d,e)$ (i.e, the set of eigenvalues of $A$) is known, and hence
too for its bipartite double $\Gamma_{d,e,e}$, and can be obtained from
Delsarte (Delsarte1976, , Theorem 10) or Eisfeld (Eisfeld1999, , Theorem 2.7).
The spectrum of $\Gamma_{d,e_{1},e_{2}}$ when $e_{1}\neq e_{2}$ is more
complicated. Brouwer Brouwer2010  gives the spectrum of $\Gamma_{3,1,2}$; also
Suda and Tanaka ST2014  study “cross-independent” sets in
$\Gamma_{d,e_{1},e_{2}}$ with $d\geqslant 2e_{1},2e_{2}$. However, for our
applications we want $d=e_{1}+e_{2}$, as this is the key case for GNP2022
which underpins GNP2022a .

We henceforth assume that $d=e_{1}+e_{2}$, and write
$\Gamma_{e_{1},e_{2}}=\Gamma_{d,e_{1},e_{2}}$. Since
$\Gamma_{e_{1},e_{2}}\cong\Gamma_{e_{2},e_{1}}$, we shall assume additionally,
without loss of generality, that $e_{1}\geqslant e_{2}$.

For each $e_{1}$-subspace $S_{1}$ of $({\mathbb{F}}_{q})^{e_{1}+e_{2}}$, there
are $q^{e_{1}e_{2}}$ choices for an $e_{2}$-subspace $S_{2}$ with $S_{1}\cap
S_{2}=\\{0\\}$. Similarly, for each $e_{2}$-subspace $S_{2}$ there are
$q^{e_{2}e_{1}}$ choices for an $e_{1}$-subspace $S_{1}$ with $S_{1}\cap
S_{2}=\\{0\\}$. Hence the graph $\Gamma_{e_{1},e_{2}}$ is
$q^{e_{1}e_{2}}$-regular. The following result is proved in Section 2, it
determines the distinct eigenvalues of $\Gamma_{e_{1},e_{2}}$, but not their
multiplicities.

######  Proposition 1.2.

Suppose that $e_{1}\geqslant e_{2}\geqslant 1$ and $d=e_{1}+e_{2}$. The
distinct eigenvalues of the bipartite graph $\Gamma_{e_{1},e_{2}}$ are
$\lambda_{0}>\cdots>\lambda_{e_{2}}>-\lambda_{e_{2}}>\cdots>-\lambda_{0}$
where $\lambda_{j}=q^{m_{j}}$ for $0\leqslant j\leqslant e_{2}$ and
$m_{j}=e_{1}e_{2}-\frac{j(d+1-j)}{2}$.

The number $\genfrac{[}{]}{0.0pt}{}{a}{b}_{q}$ of $b$-subspaces of the
$a$-dimensional vector space $({\mathbb{F}}_{q})^{a}$ is

$\genfrac{[}{]}{0.0pt}{}{a}{b}_{q}=\prod_{i=0}^{b-1}\frac{q^{a-i}-1}{q^{b-i}-1}=\prod_{i=0}^{b-1}\frac{q^{a-i-1}+\cdots+q+1}{q^{b-i-1}+\cdots+q+1}=\prod_{i=1}^{b}\frac{q^{a-i+1}-1}{q^{i}-1}.$

The second middle product shows that $\lim_{q\to
1}\genfrac{[}{]}{0.0pt}{}{a}{b}_{q}=\prod_{i=0}^{b-1}\frac{a-i}{b-i}=\binom{a}{b}$,
and $\genfrac{[}{]}{0.0pt}{}{a}{b}_{q}\sim q^{b(a-b)}$ as $q\to\infty$. The
next result is proved in Section 3 using Proposition 1.2, and the expander
mixing lemma for regular bipartite graphs, see Lemma 3.1.

######  Proposition 1.3.

Suppose that $e_{1}\geqslant e_{2}\geqslant 1$ and $d=e_{1}+e_{2}$. Let
$Y_{1}\subseteq X_{1}$ and $Y_{2}\subseteq X_{2}$ be non-empty. Put
$\alpha_{i}=|Y_{i}|/|X_{i}|$ for $i\in\\{1,2\\}$. Then
$\alpha_{1}\alpha_{2}>0$ and

$\frac{|\\{(S_{1},S_{2})\in Y_{1}\times Y_{2}:S_{1}\cap
S_{2}=0\\}|}{|Y_{1}|\cdot|Y_{2}|}\geqslant\frac{q^{e_{1}e_{2}}}{\genfrac{[}{]}{0.0pt}{}{d}{e_{1}}_{q}}\left(1-\sqrt{(\tfrac{1}{\alpha_{1}}-1)(\tfrac{1}{\alpha_{2}}-1)}q^{-\frac{d}{2}}\right).$

Suppose that $\min\\{\alpha_{1},\alpha_{2}\\}\geqslant\alpha>0$ and
$\omega_{q}(e)=\prod_{i=1}^{e}(1-q^{-i})$. Then

$\frac{|\\{(S_{1},S_{2})\in Y_{1}\times Y_{2}:S_{1}\cap
S_{2}=0\\}|}{|Y_{1}|\cdot|Y_{2}|}>\omega_{q}(e_{2})\left(1-\left(\frac{1}{\alpha}-1\right)q^{-\frac{d}{2}}\right).$

###  1.2 Recognising classical groups and outline of the paper

A group $G$ satisfying $\textup{SL}_{d}(q)\trianglelefteqslant
G\leqslant{\mathrm{GL}}_{d}(q)$ is generated by a set $\mathcal{X}$ of
elementary matrices, corresponding to elementary row operations. Furthermore,
given an element $g\in G$ there is an efficient algorithm (e.g. Gaussian
elimination) which writes $g$ as a word in $\mathcal{X}$. However, in
computational problems $G$ may be generated by a set $\mathcal{Y}$ of
arbitrary-looking matrices, and ‘recognising’ $G$ involves writing each
element of $\mathcal{X}$ as a word in $\mathcal{Y}$. A particularly helpful
special case is when $G$ is generated by a set
$\mathcal{Y}^{\prime}=\\{g_{1},g_{2}\\}$ of two matrices with
$S_{1}=\textup{im}(g_{1}-1)$ and $S_{2}=\textup{im}(g_{2}-1)$ non-degenerate
complementary subspaces, and a key problem is to write each element of
$\mathcal{X}$ as a word in $\mathcal{Y}^{\prime}$. This problem is practically
difficult, as is the analogous problem for classical groups, and its solution
uses random selections in $G$ and the natural $G$-module
$V=({\mathbb{F}}_{q})^{d}$. The authors of GNP2022 ; GNP2022a  describe in
forthcoming work an algorithm to solve this word problem, and the translation
from a problem in group theory to a geometric problem is described, in part,
in GNP2022 ; GNP2022a . Further context and details are given in (GNP2022a, ,
Section 3).

In Section 2, we determine the distinct eigenvalues of $\Gamma_{e_{1},e_{2}}$
by proving Proposition 1.2. The proof relies on an explicit algorithm in
DBMM2020  based on the seminal work of Brouwer Brouwer2010 . In Section 3, the
role of the second largest eigenvalue $\lambda_{2}$ of $\Gamma_{e_{1},e_{2}}$
is elucidated in the expander mixing lemma for bipartite graphs: we give a
short proof in Lemma 3.1. In addition, we prove Proposition 1.3 which shows
that bounds (lower and upper) can be determined simply by computing two ratios
$\alpha_{1}$ and $\alpha_{2}$. Bounds for the orthogonal case are computed in
Section 4, for the symplectic and unitary cases in Section 5, and computing
$\alpha_{1},\alpha_{2}$ is key. The orthogonal case is hardest because of the
types of the (even dimensional) non-degenerate subspaces $S_{1}$ and $S_{2}$.
Finally, Section 6 discusses the general case $d>e_{1}+e_{2}$.

##  2 Eigenvalues

The graph $\Gamma_{e_{1},e_{2}}$ can be described in the spherical building of
type ${\mathrm{A}}_{d-1}$, corresponding to the classical group
$\textup{PSL}_{d}(q)$. Adjacency in $\Gamma_{e_{1},e_{2}}$ corresponds to
opposition in ${\mathrm{A}}_{d-1}$ (that is, an $e_{1}$-space and an
$e_{2}$-space in ${\mathrm{A}}_{d-1}$ are opposite in a building-theoretical
sense precisely when they are complementary, see Brouwer2010  and (DBMM2020, ,
Lemma 3.7)). The Coxeter diagram for ${\mathrm{A}}_{d-1}$ is shown in Fig. 1.
Brouwer observed in (Brouwer2010, , Theorem 1.1) that for any opposition graph
of a spherical building over ${\mathbb{F}}_{q}$, its eigenvalues are powers of
$q$. Implicitly, Brouwer2010  describes an algorithm to calculate the
eigenvalues of graphs such as $\Gamma_{e_{1},e_{2}}$. This algorithm is
explicitly stated in (DBMM2020, , Algorithms 1, 2), which we sometimes refer
to simply as Algorithms 1, 2.

$1$$2$$e_{2}$$e_{1}$$d-2$$d-1$ Figure 1: The Coxeter diagram of
${\mathrm{A}}_{d-1}$ where $d=e_{1}+e_{2}$ and $e_{1}\geqslant e_{2}$.

The key observation in Brouwer2010  is that we can calculate the eigenvalues
of the oppositeness relation from the irreducible characters of the Coxeter
group associated with the building. In the case of ${\mathrm{A}}_{d-1}$ this
means that we can calculate the eigenvalues of any opposition graph in
${\mathrm{A}}_{d-1}$ such as $\Gamma_{e_{1},e_{2}}$ from the irreducible
characters of the symmetric group ${\mathrm{Sym}}(d)$.

The symmetric group is viewed in this setting as a Coxeter group with the set
of adjacent transpositions $\\{s_{1},\dots,s_{d-1}\\}$ as its set of
generators $S$, where $s_{i}=(i,i+1)$ for $i\in\\{1,\dots,d-1\\}$.

The unique longest word in ${\mathrm{Sym}}(d)$ with respect to the Coxeter
generators is denoted $w_{0}$. Its length is $\binom{d}{2}$ and

$w_{0}=\begin{pmatrix}1&2&\cdots&d\\\
d&d-1&\cdots&1\end{pmatrix}=\prod_{i=1}^{d-1}s_{d-1}\cdots s_{i+1}s_{i}.$

For instance, $w_{0}=s_{3}s_{2}s_{1}s_{3}s_{2}s_{3}$ when $d=4$.

We follow (DBMM2020, , Algorithms 1, 2) to calculate the eigenvalues of
$\Gamma_{e_{1},e_{2}}$ _up to sign_. This suffices since the graph
$\Gamma_{e_{1},e_{2}}$ is bipartite, and $\lambda$ is an eigenvalue of
$\Gamma_{e_{1},e_{2}}$ if and only if $-\lambda$ is an eigenvalue.

We apply Algorithm 2 to the building of type ${\mathrm{A}}_{d-1}$ with Coxeter
group $W={\mathrm{Sym}}(d)$. An $e_{1}$-space is a partial flag of type
$\\{e_{1}\\}$, its cotype is $J=\\{1,\ldots,d-1\\}\setminus\\{e_{1}\\}$. Set
$W_{J}=\langle s_{i}:i\in J\rangle$. Then
$W_{J}\cong{\mathrm{Sym}}(e_{1})\times{\mathrm{Sym}}(e_{2})$ as
$e_{2}=d-e_{1}$.

A _partition_ $\mu$ of $d$, denoted $\mu\vdash d$, is a sequence
$[\mu_{1},\ldots,\mu_{k}]$ of positive integers with
$\mu_{1}\geqslant\cdots\geqslant\mu_{k}>0$ and $\sum_{i=1}^{k}\mu_{i}=d$. The
irreducible complex characters of ${\mathrm{Sym}}(d)$ have the form
$\chi_{\mu}$ for a unique $\mu\vdash d$. The parts of the conjugate partition
$\mu^{*}$ of $\mu$ satisfy $\mu^{*}_{i}=|\\{j\mid\mu_{j}\geqslant i\\}|$. We
define two invariants $a(\mu)$ and $a^{*}(\mu)$ as

$a(\mu)=\sum_{i=1}^{k}(i-1)\mu_{i},\quad\textup{and}\quad
a^{*}(\mu)=\sum_{i=1}^{k}\frac{\mu_{i}(\mu_{i}-1)}{2}=\sum_{i=1}^{k}\binom{\mu_{i}}{2},$
(1)

and note that $a^{*}(\mu)=a(\mu^{*})$, see (GP2000, , §§5.4.1, 5.4.2) and
_c.f._ (DBMM2020, , Proposition 3.3).

######  Proposition 2.1 ((GP2000, , Proposition 5.4.11)).

Let $d\geqslant 1$. Let $\chi_{\mu}$ denote a character of ${\mathrm{Sym}}(d)$
corresponding to the partition $\mu$ of $d$. Then

$\binom{d}{2}\frac{\chi_{\mu}(r)}{\chi_{\mu}(1)}=a^{*}(\mu)-a(\mu),\quad\text{where
$r\in{\mathrm{Sym}}(d)$ is a transposition.}$

Following (DBMM2020, , Algorithm 1), we denote by $R$ a set of representatives
of the conjugacy classes containing the generators in $S$. Then observe that
$R$ comprises one transposition $r$ since the conjugacy class $s_{i}^{W}$
comprises all transpositions in $W={\mathrm{Sym}}(d)$ for any
$i\in\\{1,\dots,d-1\\}$, so that $|r^{W}|=\binom{d}{2}$. Furthermore, the
structure constant $q_{s}$ in Algorithm 1 equals $q$ by the comment after
(DBMM2020, , Proposition 2.4). In summary, the output of Algorithm 1 is the
eigenvalue $\lambda_{\mu}$, where $\lambda^{2}_{\mu}=q^{e_{\mu}}$ and the
value of
$e_{\mu}=\binom{d}{2}\left(1+\frac{\chi_{\mu}(s)}{\chi_{\mu}(1)}\right)$ is
independent of the choice of $s\in S$.

Algorithm 2 applied to $W={\mathrm{Sym}}(d)$ can be described as follows. It
is convenient to compute the eigenvalue $\lambda_{\mu}$ of $\chi_{\mu}$ up to
sign, as remarked above.

  1. 1.

Decompose the induced character $\mathrm{ind}^{W}_{W_{J}}(1_{W_{J}})$ as a sum
$\sum\chi_{\mu}$ of irreducible characters of $W$, and determine the relevant
partitions $\mu$ of $d$.

  2. 2.

For each $\mu$ appearing in Step 1, calculate using Proposition 2.1 the
exponent
$e_{\mu}=\binom{d}{2}\left(1+\frac{\chi_{\mu}(r)}{\chi_{\mu}(1)}\right)$ where
$r$ is a transposition.

  3. 3.

Calculate the length $\ell=\binom{e_{1}}{2}+\binom{e_{2}}{2}$ of the longest
word in $W_{J}$, see below.

  4. 4.

The eigenvalues of $\Gamma_{e_{1},e_{2}}$ are now $\pm q^{e_{\mu}/2-\ell}$
with $\mu$ determined in Step 1.

This description concurs with that of Algorithm 2 in DBMM2020 , except that in
Step 2, for the output of Algorithm 1 we use buildings of type
${\mathrm{A}}_{d-1}$ and Proposition 2.1.

Proof: [Proof of Proposition 1.2] Step 1 of Algorithm 2 determines, via
Frobenius reciprocity, the irreducible characters of $W={\mathrm{Sym}}(d)$
that do not vanish when restricted to $W_{J}$. Precisely, we apply Pieri’s
rule (GP2000, , Corollary 6.1.7) to find the decomposition
$\mathrm{ind}^{W}_{W_{J}}(1_{W_{J}})=\sum_{j=0}^{e_{1}}\chi_{[d-j,j]}$. This
completes Step 1 of Algorithm 2.

For Step 2 of Algorithm 2, we apply Proposition 2.1 to each character
$\chi_{[d-j,j]}$ of ${\mathrm{Sym}}(d)$. Write $\mu=[d-j,j]$ where
$d-j\geqslant e_{1}\geqslant e_{2}\geqslant j$. (When $j=0$, we identify
$\mu_{2}=[d,0]$ with $\mu_{2}=[d]$.) The functions $a(\mu)$ and $a^{*}(\mu)$
in (1) are:

$a(\mu)=j\qquad\textup{and}\qquad
a^{*}(\mu)=\binom{d-j}{2}+\binom{j}{2}\quad\textup{for $0\leqslant j\leqslant
e_{2}$.}$

Hence, by Proposition 2.1,

$e_{\mu}=\binom{d}{2}+\binom{d-j}{2}+\binom{j}{2}-j=d^{2}-d+j^{2}-jd-j.$

This completes Step 2 of Algorithm 2.

In Step 3, the length of the longest word $\ell$ in
$W_{J}={\mathrm{Sym}}(e_{1})\times{\mathrm{Sym}}(e_{2})$ is
$\binom{e_{1}}{2}+\binom{e_{2}}{2}$. Thus $\ell=\frac{d^{2}-d-2e_{1}e_{2}}{2}$
and, by Step 4, the eigenvalue corresponding to $\chi_{\mu}$ is $\pm
q^{m_{j}}$ where

$m_{j}=\frac{e_{\mu}}{2}-\ell=\frac{j^{2}-jd-j+2e_{1}e_{2}}{2}=e_{1}e_{2}-\frac{j(d+1-j)}{2}.$

##  3 The Density Bound

We state a version of the expander mixing lemma for regular, bipartite graphs.
This is stated in (Haemers1995, , Theorem 5.1) using the language of block
designs. Its proof is short, so we include it here. Given a graph $\Gamma$, we
write $E(Y_{1},Y_{2})$ for the number of edges between subsets $Y_{1}$ and
$Y_{2}$ of the set of vertices of $\Gamma$.

######  Lemma 3.1.

Let $\Gamma$ be a $k$-regular bipartite graph with vertex set
$X_{1}\mathbin{\dot{\cup}}X_{2}$. Let $Y_{i}\subseteq X_{i}$ with
$\alpha_{i}\coloneq|Y_{i}|/|X_{i}|$ for $i\in\\{1,2\\}$. Suppose that the
eigenvalues of the adjacency matrix of $\Gamma$ are
$\lambda_{1}\geqslant\lambda_{2}\geqslant\cdots\geqslant\lambda_{|X_{1}|+|X_{2}|}$.
Then

$\left|\frac{E(Y_{1},Y_{2})}{E(X_{1},X_{2})}-\alpha_{1}\alpha_{2}\right|\leqslant\frac{\lambda_{2}}{k}\sqrt{\alpha_{1}\alpha_{2}(1-\alpha_{1})(1-\alpha_{2})}.$

Since the graph $\Gamma$ has $|X_{1}|k=k|X_{2}|$ edges by $k$-regularity, it
follows that $|X_{1}|=|X_{2}|$. Our proof follows Haemers1995  and uses
interlacing : Recall that the quotient matrix $B=(b_{ij})$ of a partition
$P_{1}\mathbin{\dot{\cup}}\cdots\mathbin{\dot{\cup}}P_{m}$ of the vertex set
of $\Gamma$ into $m$ parts is an $(m\times m)$-matrix where
$b_{ij}=E(P_{i},P_{j})/|P_{i}|$. The eigenvalues of $B$ interlace those of the
adjacency matrix $A$ of $\Gamma$ by (Haemers1995, , Theorem 2.1), that is if
the spectrum of $A$ is
$\lambda_{1}\geqslant\lambda_{2}\geqslant\cdots\geqslant\lambda_{n}$ and the
spectrum of $B$ is $\mu_{1}\geqslant\mu_{2}\geqslant\cdots\geqslant\mu_{m}$,
then $\lambda_{i}\geqslant\mu_{i}\geqslant\lambda_{n-m+i}$ holds for all
$i\in\\{1,\dots,m\\}$.

Proof: [Proof of Lemma 3.1.] If $\alpha_{1}=0$, then $Y_{1}$ is empty. Hence
$E(Y_{1},Y_{2})=0$ and the bound holds with equality. If $\alpha_{1}=1$, then
$Y_{1}=X_{1}$ and by $k$-regularity

$\frac{E(Y_{1},Y_{2})}{E(X_{1},X_{2})}=\frac{k|Y_{2}|}{k|X_{2}|}=\alpha_{2},$

and again the bound holds with equality. Similar arguments show that the bound
holds for $\alpha_{2}\in\\{0,1\\}$. Henceforth assume that
$0<\alpha_{1},\alpha_{2}<1$.

Write $D\coloneq E(X_{1},X_{2})$ and $E\coloneq E(Y_{1},Y_{2})$. Let
$B=(b_{i,j})$ be the quotient matrix relative to the partition
$Y_{1}\mathbin{\dot{\cup}}(X_{1}\setminus
Y_{1})\mathbin{\dot{\cup}}Y_{2}\mathbin{\dot{\cup}}(X_{2}\setminus Y_{2})$ of
the vertex set of $\Gamma$. Then

$\displaystyle b_{1,3}+b_{1,4}$
$\displaystyle=\frac{E(Y_{1},X_{2})}{|Y_{1}|}=k,\
b_{1,3}=\frac{E(Y_{1},Y_{2})}{|Y_{1}|}=\frac{E}{\alpha_{1}|X_{1}|},\quad\textup{
and similarly}$ $\displaystyle b_{2,3}+b_{2,4}$
$\displaystyle=\frac{E(X_{1}\setminus Y_{1},X_{2})}{|X_{1}\setminus
Y_{1}|}=k,$ $\displaystyle b_{2,3}$
$\displaystyle=\frac{E(X_{1}{\setminus}Y_{1},Y_{2})}{|X_{1}{\setminus}Y_{1}|}=\frac{E(X_{1},Y_{2}){-}E}{(1-\alpha_{1})|X_{1}|}=\frac{\alpha_{2}D{-}E}{(1-\alpha_{1})|X_{1}|}.$

Thus

$B=\begin{pmatrix}0&0&\frac{E}{\alpha_{1}|X_{1}|}&k{-}\frac{E}{\alpha_{1}|X_{1}|}\\\
0&0&\frac{\alpha_{2}D-E}{(1-\alpha_{1})|X_{1}|}&k{-}\frac{\alpha_{2}D-E}{(1-\alpha_{1})|X_{1}|}\\\
\frac{E}{\alpha_{2}|X_{2}|}&k{-}\frac{E}{\alpha_{2}|X_{2}|}&0&0\\\
\frac{\alpha_{1}D-E}{(1-\alpha_{2})|X_{2}|}&k{-}\frac{\alpha_{1}D-E}{(1-\alpha_{2})|X_{2}|}&0&0\end{pmatrix}.$
(2)

Set $\delta=|X_{1}||X_{2}|\alpha_{1}\alpha_{2}(1-\alpha_{1})(1-\alpha_{2})$.
Using a computer, we find that

$\det(tI-B)=(t^{2}-k^{2})(t^{2}-\gamma^{2}/\delta)\qquad\textup{where
$\gamma=E-D\alpha_{1}\alpha_{2}$}.$

As $|X_{1}|=|X_{2}|$, the eigenvalues
$\mu_{1}\geqslant\mu_{2}\geqslant\mu_{3}\geqslant\mu_{4}$ of $B$ equal $\pm
k,\pm\mu$ where

$\mu\coloneq\frac{\left|E-D\alpha_{1}\alpha_{2}\right|}{|X_{1}|\sqrt{\alpha_{1}\alpha_{2}(1-\alpha_{1})(1-\alpha_{2})}}.$

However, $\Gamma$ is $k$-regular, so its largest eigenvalue $\lambda_{1}$ is
$k$ by (BH2012, , Proposition 1.3.8). It follows from interlacing that
$\mu_{1}=k$ and $\mu_{2}=\mu$. In addition, interlacing implies that
$\mu_{2}\leqslant\lambda_{2}$, that is

$\frac{\left|E(Y_{1},Y_{2})-E(X_{1},X_{2})\alpha_{1}\alpha_{2}\right|}{|X_{1}|\sqrt{\alpha_{1}\alpha_{2}(1-\alpha_{1})(1-\alpha_{2})}}\leqslant\lambda_{2}.$

Using $|X_{1}|=E(X_{1},X_{2})/k$ proves the assertion.

Proof: [Proof of Proposition 1.3] For $i\in\\{1,2\\}$, let $X_{i}$ denote the
set of $e_{i}$-subspaces of $V$. It follows from Proposition 1.2 that
$\lambda_{1}=q^{e_{1}e_{2}}=k$ and $\lambda_{2}=q^{e_{1}e_{2}-d/2}$. Taking
$\Gamma=\Gamma_{e_{1},e_{2}}$ in Lemma 3.1 gives

$\displaystyle\frac{E(Y_{1},Y_{2})}{E(X_{1},X_{2})}\geqslant\alpha_{1}\alpha_{2}-\sqrt{\alpha_{1}\alpha_{2}(1-\alpha_{1})(1-\alpha_{2})}q^{-\frac{d}{2}}.$

Since $E(X_{1},X_{2})=k\cdot|X_{1}|$, we have

$\displaystyle\frac{E(Y_{1},Y_{2})}{|Y_{1}|\cdot|Y_{2}|}$
$\displaystyle=\frac{|X_{1}|^{2}}{|Y_{1}|\cdot|Y_{2}|}\cdot\frac{E(Y_{1},Y_{2})}{|X_{1}|^{2}}=(\alpha_{1}\alpha_{2})^{-1}\cdot\frac{k}{|X_{1}|}\cdot\frac{E(Y_{1},Y_{2})}{E(X_{1},X_{2})}$
$\displaystyle\geqslant\frac{k}{|X_{1}|}\cdot\left(1-\sqrt{\tfrac{(1-\alpha_{1})(1-\alpha_{2})}{\alpha_{1}\alpha_{2}}}q^{-\frac{d}{2}}\right)$
$\displaystyle=\frac{k}{|X_{1}|}\cdot\left(1-\sqrt{(\tfrac{1}{\alpha_{1}}-1)(\tfrac{1}{\alpha_{2}}-1)}q^{-\frac{d}{2}}\right).$

The first claimed inequality follows by rewriting $k/|X_{1}|$ because

$\frac{k}{|X_{1}|}=\frac{q^{e_{1}e_{2}}}{\genfrac{[}{]}{0.0pt}{}{d}{e_{1}}_{q}}=\frac{\omega_{q}(e_{1})\omega_{q}(e_{2})}{\omega_{q}(e_{1}+e_{2})}>\omega_{q}(e_{2}).$

The second inequality now follows from
$\sqrt{(\tfrac{1}{\alpha_{1}}-1)(\tfrac{1}{\alpha_{2}}-1)}\leqslant\tfrac{1}{\alpha}-1$.

######  Corollary 3.2.

The second bound in Proposition 1.3 implies that

$\frac{|\\{(S_{1},S_{2})\in Y_{1}\times Y_{2}:S_{1}\cap
S_{2}=0\\}|}{|Y_{1}|\cdot|Y_{2}|}>\left(1-\frac{3}{2}q^{-1}\right)\left(1-\left(\frac{1}{\alpha}-1\right)q^{-d/2}\right).$

Proof: Since $\omega_{q}(\infty)>1-q^{-1}-q^{-2}$ by (NP1995, , Lemma 3.5), it
follows that

$\omega_{q}(e_{2})>\omega_{q}(\infty)>1-q^{-1}-q^{-2}\geqslant
1-\frac{3}{2q}.$

The result now follows from Proposition 1.3.

##  4 Proof in the orthogonal case

In this section, we prove the orthogonal bound in Theorem 1.1.

######  Theorem 4.1.

Suppose that $e_{1},e_{2}\geqslant 2$ are even and
$V=({\mathbb{F}}_{q})^{e_{1}+e_{2}}$ is an $(e_{1}+e_{2})$-dimensional vector
space equipped with a non-degenerate quadratic form of type
$\varepsilon\in\\{-,+\\}$. For $i\in\\{1,2\\}$ and for
$\sigma_{i}\in\\{-,+\\}$, let $Y_{i}$ denote the set of all non-degenerate
$e_{i}$-spaces of type $\sigma_{i}$. The proportion of pairs $(S_{1},S_{2})\in
Y_{1}\times Y_{2}$ for which $S_{1}\cap S_{2}=\\{0\\}$ is at least
$1-\frac{3}{2q}$ for all $e_{1},e_{2}\geqslant 2$,
$\varepsilon,\sigma_{1},\sigma_{2}\in\\{-,+\\}$ and all prime-powers
$q\geqslant 2$.

Proof: Let $e_{1}=2m_{1}$, $e_{2}=2m_{2}$ and let $V=({\mathbb{F}}_{q})^{d}$
be a non-degenerate orthogonal space of type $\varepsilon\in\\{-,+\\}$ where
$d=e_{1}+e_{2}$. We will assume, without loss of generality, that
$e_{2}\leqslant e_{1}$ and hence that $m_{2}\leqslant m_{1}$. Denote the
isometry group of $V$ by ${\mathrm{GO}}_{d}^{\varepsilon}(q)$. We use the
formula for $|{\mathrm{GO}}^{\sigma}_{2m}(q)|$ in (Taylor91, , p. 141), where
$\sigma\in\\{+,-\\}$ is identified with $1,-1$, respectively. Since
$q^{2m}-1=(q^{m}-\sigma)(q^{m}+\sigma)$, we have

$|{\mathrm{GO}}^{\sigma}_{2m}(q)|=2q^{m(m-1)}(q^{m}-\sigma)\prod_{i=1}^{m-1}(q^{2i}-1)=\frac{2q^{m(2m-1)}}{1+\sigma
q^{-m}}\prod_{i=1}^{m}(1-q^{-2i}).$

Hence $|{\mathrm{GO}}^{\sigma}_{2m}(q)|\sim 2q^{m(2m-1)}$ as $q\to\infty$.
Recall that $\omega_{q^{2}}(m)=\prod_{i=1}^{m}(1-q^{-2i})$.

Let $Y_{1}$ denote the set of non-degenerate $e_{1}$-spaces in $V$ of type
$\sigma_{1}$. The stabilizer of $S_{1}\in Y_{1}$ in
${\mathrm{GO}}^{\varepsilon}_{d}(q)$ is
${\mathrm{GO}}^{\sigma_{1}}_{e_{1}}(q)\times{\mathrm{GO}}^{\varepsilon\sigma_{1}}_{e_{2}}(q)$
since $S_{1}^{\perp}$ has type $\varepsilon\sigma_{1}$ by (KL, , Lemma
2.5.11(ii)). It follows from the Orbit-Stabilizer Lemma that

$\displaystyle|Y_{1}|=\frac{|{\mathrm{GO}}^{\varepsilon}_{d}(q)|}{|{\mathrm{GO}}^{\sigma_{1}}_{e_{1}}(q){\times}{\mathrm{GO}}^{\varepsilon\sigma_{1}}_{e_{2}}(q)|}$
$\displaystyle=\frac{q^{e_{1}e_{2}}(1{+}\sigma_{1}q^{-m_{1}})(1{+}\varepsilon\sigma_{1}q^{-m_{2}})}{2(1+\varepsilon
q^{-m_{1}-m_{2}})}\frac{\omega_{q^{2}}(m_{1}+m_{2})}{\omega_{q^{2}}(m_{1})\omega_{q^{2}}(m_{2})}.$

Hence $|Y_{1}|\sim\frac{1}{2}q^{e_{1}e_{2}}$ as $q\to\infty$. We shall write

$\genfrac{[}{]}{0.0pt}{}{d}{e_{1}}_{q}=\frac{q^{e_{1}e_{2}}}{B_{q}(e_{1},e_{2})}\quad\textup{where}\quad
B_{q}(e_{1},e_{2})\coloneq\frac{\omega_{q}(e_{1})\omega_{q}(e_{2})}{\omega_{q}(e_{1}+e_{2})}.$

Then

$|Y_{1}|=\frac{q^{e_{1}e_{2}}\lambda(\sigma_{1},\varepsilon)}{B_{q^{2}}(m_{1},m_{2})}\quad\textup{where}\quad\lambda(\sigma_{1},\varepsilon)=\frac{(1+\sigma_{1}q^{-m_{1}})(1+\varepsilon\sigma_{1}q^{-m_{2}})}{2(1+\varepsilon
q^{-m_{1}-m_{2}})}.$

Hence

$\alpha_{1}=\frac{|Y_{1}|}{\genfrac{[}{]}{0.0pt}{}{d}{e_{1}}_{q}}=\frac{\lambda(\sigma_{1},\varepsilon)B_{q}(e_{1},e_{2})}{B_{q^{2}}(m_{1},m_{2})}.$

Proposition 1.3 gives the lower bound

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}\geqslant
B_{q}(e_{1},e_{2})\left(1-\sqrt{\left(\frac{1}{\alpha_{1}}-1\right)\left(\frac{1}{\alpha_{2}}-1\right)}q^{-d/2}\right)$

A computer program FI  checks that the above bound is greater than
$1-\frac{1.5}{q}$ for all $q\leqslant 5$ and $1\leqslant m_{2}\leqslant
m_{1}\leqslant 6$ except when $q\leqslant 5$ and $m_{1}=m_{2}=1$, or
$(q,m_{2},m_{1})$ equals $(2,1,2)$, $(2,1,3)$, $(2,2,2)$. For these seven
exceptions, we used the GAP package FinInG FinIng  to do an exact count. The
GAP/FinIng code FI  verifies that the lower bound $1-\frac{1.5}{q}$ holds in
these cases. Thus when $q\leqslant 5$, we will henceforth assume that
$m_{1}+m_{2}\geqslant 7$, and hence that $d=2m_{1}+2m_{2}\geqslant 14$.

Observe now that $\lambda(\sigma_{1},\varepsilon)\geqslant\lambda(-,+)$. Take
a lower bound $\alpha_{1}\geqslant\alpha$ and $\alpha_{2}\geqslant\alpha$
where
$\alpha\coloneq\lambda(-,+)B_{q}(e_{1},e_{2})B_{q^{2}}(m_{1},m_{2})^{-1}$.
Proposition 1.3 gives the lower bound

$\displaystyle\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}$ $\displaystyle\geqslant
B_{q}(e_{1},e_{2})\left(1-\left(\frac{1}{\alpha}-1\right)q^{-d/2}\right)$
$\displaystyle=B_{q}(e_{1},e_{2})\left(1+q^{-d/2}\right)-\lambda(-,+)^{-1}B_{q^{2}}(m_{1},m_{2})q^{-d/2}.$
(3)

We next consider the case $q\leqslant 5$ and $m_{1}+m_{2}\geqslant 7$. Since
$B_{q^{2}}(m_{1},m_{2})$ is a decreasing function of $m_{2}$, it follows that

$B_{q^{2}}(m_{1},m_{2})\leqslant B_{q^{2}}(7-m_{2},m_{2})\leqslant
B_{q^{2}}(1,6).$

Furthermore, $B_{q}(e_{1},e_{2})\geqslant\omega_{q}(e_{1})>\omega_{q}(\infty)$
and $1+q^{-d/2}>1$ so

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}>\omega_{q}(\infty)-\lambda(-,+)^{-1}B_{q^{2}}(1,6)q^{-7}.$

Similar reasoning gives

$\displaystyle\lambda(-,+)^{-1}=\frac{2(1+q^{-m_{1}-m_{2}})}{(1-q^{-m_{1}})(1-q^{-m_{2}})}$
$\displaystyle\leqslant\frac{2(1+q^{-7})}{(1-q^{-m_{1}})(1-q^{-(7-m_{1})})}$
$\displaystyle\leqslant\frac{2(1+q^{-7})}{(1-q^{-1})(1-q^{-6})}.$

Using the more accurate lower bound
$\omega_{q}(\infty)>1-q^{-1}-q^{-2}+q^{-5}$ from (NP1995, , Lemma 3.5), one
can check by computer that

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}>1-q^{-1}-q^{-2}+q^{-5}-\frac{2(1+q^{-7})}{(1-q^{-1})(1-q^{-6})}B_{q^{2}}(1,6)q^{-7}>1-\frac{3}{2q}$

holds for $q\leqslant 5$.

Finally, suppose that $q\geqslant 7$ and $1\leqslant m_{2}\leqslant m_{1}$
holds. When $m_{1}=m_{2}=1$, it follows from (5) and $1+q^{-d/2}>1$ that

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}>\frac{1}{(1+q^{-1}+q^{-2})(1+q^{-2})}-\frac{2q^{-2}}{(1-q^{-1})^{2}}.$

This is bound is dominated by the first term and is a decreasing function of
$q$. Hence the bound is greater than $1-\frac{1.5}{q}$ for all $q\geqslant 7$.
It remains to consider the case $m_{1}+m_{2}\geqslant 3$ and hence $d\geqslant
6$. Arguing as above, and using $q\geqslant 7$, gives

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}>1-q^{-1}-q^{-2}+q^{-5}-\frac{2(1+q^{-3})}{(1{-}q^{-1})(1{-}q^{-2})}B_{q^{2}}(1,2)q^{-3}>1-\frac{3}{2q}.$

Thus in all cases the bound $1-\frac{3}{2q}$ holds, as claimed.

##  5 Proof in the symplectic and unitary cases

In this section, we prove the symplectic and unitary bounds in Theorem 1.1.

######  Theorem 5.1.

Suppose that $e_{1},e_{2}\geqslant 2$ are even and
$V=({\mathbb{F}}_{q})^{e_{1}+e_{2}}$ is an $(e_{1}+e_{2})$-dimensional
symplectic space. For $i\in\\{1,2\\}$ let $Y_{i}$ denote the set of all non-
degenerate $e_{i}$-spaces of $V$. The proportion of pairs $(S_{1},S_{2})\in
Y_{1}\times Y_{2}$ for which $S_{1}\cap S_{2}=\\{0\\}$ is at least
$1-\frac{10}{7q}$ for all $e_{1},e_{2}$ and all prime-powers $q\geqslant 2$.

Proof: Let $e_{1}=2m_{1}$, $e_{2}=2m_{2}$ and let $V=({\mathbb{F}}_{q})^{d}$
be a non-degenerate symplectic space where $d=e_{1}+e_{2}$. As before, we
shall assume, without loss of generality, that $2\leqslant e_{2}\leqslant
e_{1}$ and hence that $1\leqslant m_{2}\leqslant m_{1}$. Let $m=m_{1}+m_{2}$.
The isometry group ${\mathrm{Sp}}_{2m}(q)$ of $V$ has order
$q^{m^{2}}\prod_{i=1}^{m}(q^{2i}-1)=q^{2m^{2}+m}\omega_{q^{2}}(m)$ by
(Taylor91, , p. 70).

Let $Y_{i}$ denote the set of non-degenerate $e_{i}$-spaces in $V$. Clearly
$|Y_{1}|=|Y_{2}|$. The stabilizer of $S_{1}\in Y_{1}$ in ${\mathrm{Sp}}(V)$ is
${\mathrm{Sp}}(S_{1})\times{\mathrm{Sp}}(S_{1}^{\perp})$. Therefore

$\displaystyle|Y_{2}|=|Y_{1}|=\frac{|{\mathrm{Sp}}_{e_{1}+e_{2}}(q)|}{|{\mathrm{Sp}}_{e_{1}}(q){\times}{\mathrm{Sp}}_{e_{2}}(q)|}$
$\displaystyle=\frac{q^{e_{1}e_{2}}\omega_{q^{2}}(m_{1}+m_{2})}{\omega_{q^{2}}(m_{1})\omega_{q^{2}}(m_{2})}$
$\displaystyle=\frac{q^{e_{1}e_{2}}}{B_{q^{2}}(m_{1},m_{2})}\quad\text{where
$B_{q}(e_{1},e_{2})=\frac{\omega_{q}(e_{1})\omega_{q}(e_{2})}{\omega_{q}(e_{1}+e_{2})}$.}$

Since
$|X_{1}|=\genfrac{[}{]}{0.0pt}{}{d}{e_{1}}_{q}=\genfrac{[}{]}{0.0pt}{}{d}{e_{2}}_{q}=|X_{2}|=q^{e_{1}e_{2}}/B_{q}(e_{1},e_{2})$,
we have

$\alpha_{1}=\frac{|Y_{1}|}{|X_{1}|}=\frac{q^{e_{1}e_{2}}}{B_{q^{2}}(m_{1},m_{2})}\cdot\frac{B_{q}(e_{1},e_{2})}{q^{e_{1}e_{2}}}=\frac{B_{q}(e_{1},e_{2})}{B_{q^{2}}(m_{1},m_{2})}.$

Proposition 1.3 gives the lower bound

$\displaystyle\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}$ $\displaystyle\geqslant
B_{q}(e_{1},e_{2})\left(1-\left(\frac{1}{\alpha_{1}}-1\right)q^{-d/2}\right)$
$\displaystyle\geqslant
B_{q}(e_{1},e_{2})-\left(B_{q^{2}}(m_{1},m_{2})-B_{q}(e_{1},e_{2})\right)q^{-d/2}$
$\displaystyle>B_{q}(e_{1},e_{2})-B_{q^{2}}(m_{1},m_{2})q^{-d/2}.$

Note that
$B_{q}(e_{1},e_{2})\geqslant\omega_{q}(e_{1})>\omega_{q}(\infty)>1-q^{-1}-q^{-2}$
by (NP1995, , Lemma 3.5). Also, $1>B_{q^{2}}(m_{1},m_{2})$ and
$d=e_{1}+e_{2}\geqslant 4$. If $q\geqslant 5$, we have

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}\geqslant
1-q^{-1}-q^{-2}-q^{-2}>1-\frac{10}{7}q^{-1}.$

For $q\in\\{2,3,4\\}$ we have $\omega_{2}(\infty)>0.288$,
$\omega_{3}(\infty)>0.56$ and $\omega_{4}(\infty)>0.688$. Thus when
$q\in\\{2,3,4\\}$ and $d\geqslant 20$, we have

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}\geqslant\omega_{q}(\infty)-q^{-10}>1-\frac{10}{7}q^{-1}.$

Finally, if $q\in\\{2,3,4\\}$ and $d=e_{1}+e_{2}<20$, then a computer program
shows that the last inequality below is satisfied

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}\geqslant
B_{q}(e_{1},e_{2})(1+q^{-d/2})-B_{q^{2}}(m_{1},m_{2})q^{-d/2}>1-\frac{10}{7}q^{-1}.$

######  Theorem 5.2.

Suppose $V=({\mathbb{F}}_{q^{2}})^{e_{1}+e_{2}}$ is an
$(e_{1}+e_{2})$-dimensional hermitian space where $e_{1},e_{2}\geqslant 1$.
For $i\in\\{1,2\\}$, let $Y_{i}$ denote the set of all non-degenerate
$e_{i}$-spaces of $V$. The proportion of pairs $(S_{1},S_{2})\in Y_{1}\times
Y_{2}$ for which $S_{1}\cap S_{2}=\\{0\\}$ is at least $1-\frac{c}{q^{2}}$
where $c=2$ when $(e_{1},e_{2},q)=(1,1,2)$, $c=\frac{3}{2}$ when
$\min\\{e_{1},e_{2}\\}=1$ and $(e_{1},e_{2},q)\neq(1,1,2)$, and $c=1.26$
otherwise.

Proof: Let $V=({\mathbb{F}}_{q^{2}})^{d}$ be a non-degenerate unitary space
where $d=e_{1}+e_{2}$. Let ${\mathrm{GU}}_{d}(q)$ denote the isometry group of
$V$. We have $|{\mathrm{GU}}_{d}(q)|\sim q^{d^{2}}$ as $q\to\infty$, more
precisely
$|{\mathrm{GU}}_{d}(q)|=q^{d(d-1)/2}\prod_{i=1}^{d}(q^{i}-(-1)^{i})=q^{d^{2}}\omega_{-q}(d)$
by (Taylor91, , p. 118) where

$\omega_{-q}(d)=\prod_{i=1}^{d}(1-(-q)^{-i}).$

The proportion of pairs $(S_{1},S_{2})\in Y_{1}\times Y_{2}$ for which
$S_{1}\cap S_{2}=\\{0\\}$ is unchanged if we swap the subscripts. Thus we can
henceforth assume that $1\leqslant e_{2}\leqslant e_{1}$. Proposition 1.3
gives poor bounds when $e_{2}=1$. When $e_{2}=1$, it turns out to be simple to
overestimate the complementary proportion using ideas in the proof of
(GNP2022, , Theorem 4.1). The proportion of non-degenerate $e_{1}$-subspaces
(where $e_{1}=d-1$) that contain a given 1-subspace is at most $c_{1}/q^{2}$
where $c_{1}\coloneq\frac{1+q^{-e_{1}}}{1-q^{-1-e_{1}}}$ by (GNP2022, , p. 9).
This equals $\frac{2}{q^{2}}$ if $(e_{1},e_{2},q)=(1,1,2)$. If $e_{1}\geqslant
2$, we have $c_{1}\leqslant\frac{1+2^{-2}}{1-2^{-3}}<\frac{3}{2}$, and if
$q\geqslant 3$ we have
$c_{1}\leqslant\frac{1+q^{-1}}{1-q^{-2}}=\frac{1}{1-q^{-1}}\leqslant\frac{3}{2}$.
Thus when $e_{1}\geqslant 2$ and $e_{2}=1$ the complementary proportion is at
most $\frac{3}{2q^{2}}$. This proves the claim when $e_{2}=1$. We henceforth
assume that $2\leqslant e_{2}\leqslant e_{1}$.

The stabilizer of $S_{1}\in Y_{1}$ in ${\mathrm{GU}}(V)$ is
${\mathrm{GU}}(S_{1})\times{\mathrm{GU}}(S_{1}^{\perp})$. Hence

$\displaystyle|Y_{1}|=|Y_{2}|=\frac{|{\mathrm{GU}}_{e_{1}+e_{2}}(q)|}{|{\mathrm{GU}}_{e_{1}}(q){\times}{\mathrm{GU}}_{e_{2}}(q)|}$
$\displaystyle=\frac{q^{2e_{1}e_{2}}\omega_{-q}(e_{1}+e_{2})}{\omega_{-q}(e_{1})\omega_{-q}(e_{2})}=\frac{q^{2e_{1}e_{2}}}{B_{-q}(e_{1},e_{2})}.$

Replacing $q$ with $q^{2}$ shows that
$|X_{1}|=|X_{2}|=(q^{2})^{e_{1}e_{2}}/B_{q^{2}}(e_{1},e_{2})$, and hence

$\alpha_{1}=\frac{|Y_{1}|}{|X_{1}|}=\frac{B_{q^{2}}(e_{1},e_{2})}{B_{-q}(e_{1},e_{2})}.$

Proposition 1.3, with $q$ replaced with $q^{2}$, gives the lower bound

$\displaystyle\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}$ $\displaystyle\geqslant
B_{q^{2}}(e_{1},e_{2})\left(1-\left(\frac{1}{\alpha_{1}}-1\right)q^{-d}\right)$
$\displaystyle=B_{q^{2}}(e_{1},e_{2})(1+q^{-d})-B_{-q}(e_{1},e_{2})q^{-d}$
$\displaystyle>B_{q^{2}}(e_{1},e_{2})-B_{-q}(e_{1},e_{2})q^{-d}.$ (4)

Note that
$B_{q^{2}}(e_{1},e_{2})\geqslant\omega_{q^{2}}(e_{1})>\omega_{q^{2}}(\infty)>1-q^{-2}-q^{-4}$
by (NP1995, , Lemma 3.5).

To find an upper bound for
$B_{-q}(e_{1},e_{2})=\prod_{i=1}^{e_{2}}\frac{(1-(-q)^{-i})}{(1-(-q)^{-e_{1}-i})}$,
we will use

$(1-q^{-2i})(1+q^{-(2i+1)})<1<(1+q^{-(2j-1)})(1-q^{-2j}).$ (5)

It follows from (5) that $\prod_{i=1}^{e_{2}}(1-(-q)^{-i})\leqslant 1+q^{-1}$
for all $e_{2}\geqslant 1$ and

$\prod_{i=1}^{e_{2}}(1-(-q)^{-e_{1}-i})\geqslant\begin{cases}1&\textup{if
$e_{1}$ even, $e_{2}$ even,}\\\ 1+q^{-e_{1}-e_{2}}&\textup{if $e_{1}$ even,
$e_{2}$ odd,}\\\ 1-q^{-e_{1}-1}&\textup{if $e_{1}$ odd, $e_{2}$ even,}\\\
(1-q^{-1-e_{1}})(1-q^{-e_{1}-e_{2}})&\textup{if $e_{1}$ odd, $e_{2}$
odd.}\end{cases}$

Hence the above product is greater than or equal to $(1-q^{-4})(1-q^{-6})$ for
all $2\leqslant e_{2}\leqslant e_{1}$. Therefore
$B_{-q}(e_{1},e_{2})\leqslant\frac{1+q^{-1}}{(1-q^{-4})(1-q^{-6})}$.

Since $d\geqslant 4$, it follows from (4) that

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}>1-q^{-2}-q^{-4}-\frac{(1+q^{-1})q^{-4}}{(1-q^{-4})(1-q^{-6})}.$

This is greater than $1-\frac{1.26}{q^{2}}$ for all $q\geqslant 4$.

Suppose now that $q\in\\{2,3\\}$ and $d\geqslant 10$. Then

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}>\omega_{q^{2}}(\infty)-\frac{(1+q^{-1})q^{-10}}{(1-q^{-4})(1-q^{-6})}$

and since $\omega_{4}(\infty)>0.6885$, $\omega_{9}(\infty)>0.876$, the above
bound is greater than $1-\frac{1.26}{q^{2}}$ for $q\in\\{2,3\\}$. It remains
to consider $q\leqslant 3$ and $2\leqslant e_{2}\leqslant e_{1}$ where
$e_{1}+e_{2}<10$. In this case, a simple computer program verifies that

$\frac{E(Y_{1},Y_{2})}{|Y_{1}||Y_{2}|}\geqslant
B_{q^{2}}(e_{1},e_{2})(1+q^{-d})-B_{-q}(e_{1},e_{2})q^{-d}>1-\frac{1.26}{q^{2}}.$

##  6 Future Work

A more general problem when $e_{1}+e_{2}<d$ is considered in GNP2022a . Here
$V={\mathbb{F}}^{d}$ is a finite non-degenerate classical space and a lower
bound of the form $1-\frac{c}{|{\mathbb{F}}|}$ is sought for the proportion of
non-degenerate pairs $(S_{1},S_{2})$ satisfying $\dim(S_{i})=e_{i}$ and
$S_{1}\cap S_{2}=\\{0\\}$. The bound given in (GNP2022a, , Theorem 1.1) has
the form $1-\frac{c}{|{\mathbb{F}}|}$ in the symplectic case, and the
orthogonal case for $q>2$, but only $1-\frac{c}{|{\mathbb{F}}|^{1/2}}$ in the
unitary case. If one could compute the second eigenvalue $\lambda_{2}$ of the
bipartite graph $\Gamma_{d,e_{1},e_{2}}$ when $e_{1}+e_{2}<d$, _c.f._
Proposition 1.2, then it may be possible to obtain sharper lower bounds of the
form $1-\frac{c}{|{\mathbb{F}}|}$ via Lemma 3.1, in all cases.

#### Acknowledgment

We thank the referee for their very helpful comments. The first author is
supported by the Australian Research Council Discovery Grant DP190100450. The
second author is supported by a postdoctoral fellowship of the Research
Foundation – Flanders (FWO).

Data sharing is not applicable to this article as no datasets were generated
or analysed during the current study.

## References

  * (1) J. Bamberg, A. Betten, J. De Beule, P. Cara, M. Lavrauw and M. Neunhöffer, FinInG, Finite Incidence Geometry, Version 1.4.1, 2018. Refereed GAP package.
  * (2) A. Blokhuis, A. E. Brouwer and T. Szőnyi, On the chromatic number of $q$-Kneser graphs, Des. Codes Cryptogr. 65 (2012) 187–197.
  * (3) A. E. Brouwer, The eigenvalues of oppositeness graphs in buildings of spherical type, In Combinatorics and graphs, volume 531 of Contemp. Math., pp. 1–10. Amer. Math. Soc., Providence, RI, 2010.
  * (4) A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, 2012.
  * (5) H. Cai, J. Chrisnata, T. Etzion, M. Schwartz and A. Wachter-Zeh, Network-coding solutions for minimal combination networks and their sub-networks, IEEE Trans. Inform. Theory 66(11) (2020) 6786–6798.
  * (6) J. De Beule, S. Mattheus and K. Metsch, An algebraic approach to Erdős-Ko-Rado sets of flags in spherical buildings, J. Combin. Theory Ser. A 192 (2022), paper no. 105657, 33 pp.
  * (7) P. Delsarte, Association schemes and $t$-designs in regular semilattices, J. Combin. Theory Ser. A 20 (1976) 230–243.
  * (8) J. Eisfeld, The eigenspaces of the Bose-Mesner algebras of the association schemes corresponding to projective spaces and polar spaces, Des. Codes Cryptogr. 17 (1999) 129–150.
  * (9) M. Geck and G. Pfeiffer, Characters of finite Coxeter groups and Iwahori-Hecke algebras, vol. 21 of London Mathematical Society Monographs. New Series. The Clarendon Press, Oxford University Press, New York, 2000.
  * (10) S. P. Glasby, A. C. Niemeyer and C. E. Praeger, The probability of spanning a classical space by two non-degenerate subspaces of complementary dimensions, _Finite Fields Their Appl._ 82 (2022), paper no. 102055.
  * (11) S. P. Glasby, A. C. Niemeyer and C. E. Praeger, Random generation of direct sums of finite non-degenerate subspaces, _Linear Algebra Appl._ Linear Algebra Appl. 649 (2022), 408–432.
  * (12) W. H. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 226–228 (1995) 593–616.
  * (13) F. Ihringer, GAP/FinIng code for the small orthogonal cases in Theorem 4.1, https://stephenglasby.github.io/publications/
  * (14) P. Kleidman and M. Liebeck, _The subgroup structure of the finite classical groups_ , London Mathematical Society Lecture Note Series, 129. Cambridge University Press, Cambridge, 1990.
  * (15) P. M. Neumann and C. E. Praeger, Cyclic matrices over finite fields, J. London Math. Soc. 52(2) (1995), 263–284.
  * (16) S. Suda and H. Tanaka, A cross-intersection theorem for vector spaces based on semidefinite programming, Bull. London Math. Soc. 46 (2014) 342–348.
  * (17) D. E. Taylor, The Geometry of the Classical Groups, Heldermann, Berlin, 1992.