August 19, 2024
We define totally-isotropic space polynomials of alternating matrix spaces over finite fields, by analogy with independence polynomials of graphs. Our main result shows that totally-isotropic polynomials of graphical alternating matrix spaces give rise to a natural \(q\)-analogue of graph independence polynomials.
For \(p\)-groups of class \(2\) and exponent \(p\), this family of polynomials over fields of order \(p\) can be naturally interpreted as enumerating their abelian subgroups containing the commutator subgroup according to the orders. With this interpretation, our main result has implications to graphical groups over \(\mathbb{F}_p\) where \(p\) is an odd prime, in the same spirit as the results in (Bull. Lond. Math. Soc., 2022) by Rossmann, who studied enumerating conjugacy classes of graphical groups over finite fields.
Let \(G=(S, E)\) be a finite, simple, and undirected graph, where \(S\) is a finite vertex set, and \(E\subseteq \binom{S}{2}\) is the edge set. We say that \(W\subseteq S\) is an independent set of \(G\), if \(W\) does not contain any edge in \(E\). The maximum independent set size of \(G\) is denoted by \(\alpha(G)\).
Let \(x\) be a variable. For \(n\in \mathbb{N}\), \([n]:=\{1, 2, \dots, n\}\). The independence polynomial of \(G\) in \(x\) is the enumeration polynomial of independent sets of size \(i\). That is, for \(i\in\mathbb{N}\), let \(c_i(G)\) be the number of independent sets of size \(i\) in \(G\). The independence polynomial of \(G\) is \[\mathrm{I}(G, x):=1+\sum_{i\in[\alpha(G)]}c_i(G)\cdot x^i\in \mathbb{Z}[x].\]
Independence polynomials of graphs were first introduced by Gutman and Harary [1] and have received considerable attention in combinatorics and physics. We refer the readers to [2]–[4] for more research on this.
A basic property of graph independence polynomials is as follows. Let \(G_1=(S_1, E_1)\) and \(G_2=(S_2, E_2)\) be two graphs with disjoint vertex sets. Their union is then \(G=(S, E)\), where \(S=S_1\cup S_2\) and \(E=E_1\cup E_2\). It is easy to observe (see e.g. [2]) \[\label{eq:graph95union} \mathrm{I}(G, x)=\mathrm{I}(G_1, x)\cdot \mathrm{I}(G_2, x).\tag{1}\]
Let \(\mathbb{F}_q^n\) be the linear space of length-\(n\) column vectors over the finite field \(\mathbb{F}_q\) of order \(q\). We use \(\mathrm{M}(n, q)\) to denote the linear space of \(n\times n\) matrices over \(\mathbb{F}_q\).
A matrix \(B\in\mathrm{M}(n,q)\) is alternating if for any \(u\in \mathbb{F}_q^n\), \(u^{\mathrm{t}}Bu=0\). We use \(\Lambda(n, q)\) to denote the linear space of \(n\times n\) alternating matrices over \(\mathbb{F}_q\). A subspace \(\mathcal{B}\) of \(\Lambda(n, q)\) is called an alternating matrix space, denoted by \(\mathcal{B}\leq\Lambda(n, q)\).
Definition 1. Let \(\mathcal{B}\leq\Lambda(n, q)\) be an alternating matrix space. We say that \(U\leq \mathbb{F}_q^n\) is a totally-isotropic space of \(\mathcal{B}\), if for every \(u_1, u_2\in U\), and every \(B\in \mathcal{B}\), \(u_1^{\mathrm{t}}Bu_2=0\).
The maximum totally-isotropic space dimension of \(\mathcal{B}\) is denoted by \(\alpha(\mathcal{B})\). We use \(c_i(\mathcal{B})\) to denote the number of \(i\)-dimensional totally-isotropic subspaces of \(\mathcal{B}\).
Let \(p\) be a prime. Recall that a group \(P\) is a \(p\)-group of class \(2\) and exponent \(p\), if \(|P|\) is a power of \(p\), every \(g\in P\) satisfies \(g^p=\mathop{\mathrm{id}}\) (the exponent condition), and the commutator subgroup \([P,P]\) is contained in the centre \(\mathrm{Z}(P)\) (the nilpotency class \(2\) condition). When \(p\) is odd, \(p\)-groups of class \(2\) and exponent \(p\) give rise to alternating bilinear maps, and therefore alternating matrix spaces, via Baer’s correspondence [5]. Via this correspondence, totally-isotropic spaces of alternating matrix spaces naturally correspond to certain abelian subgroups of \(p\)-groups of class \(2\) and exponent \(p\). As a result, several classical works in group theory, such as [6]–[8], studied totally-isotropic spaces with group-theoretic implications, as will be explained in more detail in Section 1.3.
Some recent works studied totally-isotropic spaces of alternating matrix spaces in analogy with independent sets of graphs [9], [10]. This is due to a natural procedure of associating alternating matrix spaces with graphs, by sending an edge \(\{i, j\}\in \binom{[n]}{2}\), \(i<j\), to an \(n\times n\) elementary alternating matrix \(A_{i, j}\) where the \((i, j)\)th entry is \(1\), the \((j, i)\)th entry is \(-1\), and the rest being \(0\). From a graph \(G=([n], E)\) and a field \(\mathbb{F}\), this construction produces a graphical (alternating) matrix space \(\mathcal{B}_G\leq \Lambda(n, \mathbb{F})\). It was first used by Tutte [11] and Lovász [12] in the context of graph perfect matchings.
The correspondence between independent sets and totally-isotropic spaces was first studied in [9]. For example, one result in [9] shows that the independence number \(\alpha(G)\) is equal to \(\alpha(\mathcal{B}_G)\), the totally-isotropic number of its corresponding graphical matrix space (regardless of the underlying field). This connection was extended to hypergraphs and spaces of alternating multilinear forms [10].
More connections between graphs and matrix spaces can be found in [13].
Recall that given \(\{i, j\}\in \binom{[n]}{2}\), \(i<j\), the \(n\times n\) elementary alternating matrix \(A_{i,j}\) is the matrix with the \((i,j)\)th entry being \(1\), \((j, i)\)th entry being \(-1\), and other entries being \(0\).
Given a graph \(G=([n], E)\) where \(E\subseteq\binom{[n]}{2}\), let \(\mathcal{G}_q:=\mathrm{span}\{A_{i,j} \mid \{i, j\}\in E\}\leq \Lambda(n, q)\).
Our first main result is concerned with enumerating totally-isotropic spaces of graphical matrix spaces. The proof of the following theorem is in Section 2.
Theorem 1. For any \(1\leq i\leq \alpha(G)\), there exists \(c_i(y)\in\mathbb{Z}[y]\), such that \(c_i(q)=c_i(\mathcal{G}_q)\) for a prime power \(q\), and \(c_i(1)=c_i(G)\).
Theorem 1 shows that there exist polynomials \(c_i(y)\) that capture simultaneously the cases of the number of size-\(i\) independent sets for \(G\) with \(y=1\), and the number of \(i\)-dimensional totally-isotropic spaces for \(\mathcal{G}_q\) with \(y=q\) a prime power.
Based on Theorem 1, we define totally-isotropic space polynomials for alternating matrix spaces over finite fields, following graph independence polynomials. As in the graph case, such polynomials are enumeration polynomials of \(i\)-dimensional totally-isotropic spaces of alternating matrix spaces over \(\mathbb{F}_q\). To define such polynomials, there is one twist in the choice of bases of polynomial rings. In the graph setting, the basis is naturally \(\{x^i\mid i\in\mathbb{N}\}\subseteq \mathbb{Z}[x]\) and Equation 1 follows easily. In the alternating matrix space setting, we introduce the following.
Let \(x\) and \(y\) be variables. In the alternating matrix space setting, we make use of the following basis of \(\mathbb{Z}[y][x]\): for \(d=0\), set \(x_y^d:=1\). For \(d\geq 1\), we set \[\label{eq:xyd} x_y^d:=x\cdot (x-(y-1))\cdot \ldots\cdot (x-(y^{d-1}-1)).\tag{2}\] Note that \(x^d\) is the leading term in \(x_y^d\), and its coefficient is \(1\). Therefore, in the \(\mathbb{Z}[y]\)-module \(\mathbb{Z}[y][x]\), the change-of-basis matrix from \(\{x^d\mid d\in \mathbb{N}\}\) to \(\{x_y^d\mid d\in\mathbb{N}\}\) is unitriangular. It follows that \(\{x_y^d\mid d\in\mathbb{N}\}\) is a basis of \(\mathbb{Z}[y][x]\) as a \(\mathbb{Z}[y]\)-module.
We shall use \(x_y^d\) with \(y\) assigned as \(1\) or a prime power \(q\). Note that \(x_1^d=x^d\).
We now define the following.
Definition 2. Let \(\mathcal{B}\leq\Lambda(n, q)\) be an alternating matrix space. The totally-isotropic space polynomial of \(\mathcal{B}\) is \[\mathrm{TI}(\mathcal{B}, x):= 1+\sum_{i\in[\alpha(\mathcal{B})]}c_i(\mathcal{B})\cdot x_q^i\in \mathbb{Z}[x].\]
Note that \(\mathrm{TI}(\mathcal{B}, x)\) is an integer polynomial, as by setting \(y=q\) in \(x_y^i\), \(x_q^i\) is an integer polynomial. The reason for using \(x_q^i\) in the definition of \(\mathrm{TI}(\mathcal{B}, x)\) will be clear in the following.
We now turn to totally-isotropic space polynomials for graphical matrix spaces.
Let \(G\) be a graph and \(\mathcal{G}_q\) be the graphical matrix space of \(G\). Recall that \(\alpha(\mathcal{G}_q)=\alpha(G)\) for any prime power \(q\) by [9]. This ensures that \(\mathrm{TI}(\mathcal{G}_q, x)\) is of the same degree as \(\mathrm{I}(G, x)\).
Our main result considerably strengthens the above connection. It shows that there exists a polynomial \(\mathrm{I}(G, x, y)\in \mathbb{Z}[y][x]\) that captures simultaneously the cases of \(\mathrm{TI}(\mathcal{G}_q, x)\) for prime power \(y=q\) and \(\mathrm{I}(G, x)\) for \(y=1\). The following result follows from Theorem 1, the definition of \(\mathrm{TI}(\mathcal{B}, x)\), and \(x_1^d=x^d\).
Theorem 2. Let \(x\) and \(y\) be variables. For a graph \(G=([n], E)\), there exists a polynomial \[\mathrm{I}(G, x, y)=1+\sum_{i\in[\alpha(G)]}c_i(y)\cdot x_y^i\in \mathbb{Z}[y][x],\] where \(c_i(y)\in\mathbb{Z}[y]\), such that \(\mathrm{I}(G, x, y)\) satisfies the following:
when \(y=q\) is a prime power, \(\mathrm{I}(G, x, q)=\mathrm{TI}(\mathcal{G}_q, x)\);
when \(y=1\), \(\mathrm{I}(G, x, 1)=\mathrm{I}(G, x)\).
We now explain the reason for using \(x_y^d\) as a basis of \(\mathbb{Z}[y][x]\).
Let \(\mathcal{B}\leq \Lambda(n_1, q)\) and \(\mathcal{C}\leq \Lambda(n_2, q)\). The disjoint direct sum of \(\mathcal{B}\) and \(\mathcal{C}\) is \(\mathcal{A}=\{\begin{bmatrix} B & 0 \\ 0 & C \end{bmatrix}\mid B\in \mathcal{B}, C\in \mathcal{C}\}\leq \Lambda(n_1+n_2, q)\). The disjoint direct sum of two alternating matrix spaces can be viewed as corresponding to the union of two graphs. Indeed, by [14], a graph \(G\) is connected if and only if its associated graphical matrix space cannot be written as the disjoint direct sum of two alternating matrix spaces.
The following proposition corresponds to Equation 1 in the graph setting. Its proof is in Section 3.
Proposition 3. Let \(\mathcal{B}\leq\Lambda(n_1, q)\), \(\mathcal{C}\leq\Lambda(n_2, q)\), and \(\mathcal{A}\leq \Lambda(n_1+n_2, q)\) be the disjoint direct sum of \(\mathcal{B}\) and \(\mathcal{C}\). Then \[\mathrm{TI}(\mathcal{A}, x)=\mathrm{TI}(\mathcal{B}, x)\cdot\mathrm{TI}(\mathcal{C}, x).\]
Let \(p\) be a prime \(>2\). Alternating matrix spaces over \(\mathbb{F}_p\) are closely related to finite \(p\)-groups of class \(2\) and exponent \(p\) via Baer’s correspondence [5]. That is, from such a group \(P\) one can construct an alternating matrix space \(\mathcal{B}_P\). We briefly review this process here.
Let \(P\) be a \(p\)-group of class \(2\) and exponent \(p\). By taking the commutator map in \(P\), we obtain an alternating bilinear map \(\phi_P:P/[P, P]\times P/[P, P]\to[P, P]\). As \(P/[P,P]\) and \([P, P]\) are elementary abelian groups, we can set \(P/[P,P]\cong\mathbb{Z}_p^n\) and \([P, P]\cong \mathbb{Z}_p^m\). Let us fix a basis of \(P/[P,P]\) as \(\{e_1, \dots, e_n\}\), and a basis of \([P,P]\) as \(\{f_1, \dots, f_m\}\). For each \(f_i\), from \(\phi_P\) we obtain an alternating matrix \(F_i\in \Lambda(n, p)\), where the \((j, k)\)th entry of \(F_i\) is the coefficient of \(f_i\) in \(\phi_P(e_j, e_k)\). Therefore, by fixing bases of \(P/[P,P]\) and \([P,P]\), one can obtain an \(m\)-tuple of \(n\times n\) alternating matrices over \(\mathbb{F}_p\), whose linear span is denoted by \(\mathcal{B}_P\leq \Lambda(n, p)\).
Conversely, from an alternating matrix space \(\mathcal{B}\) one can construct such a group \(P_\mathcal{B}\). For a detailed description of this procedure we refer readers to [14], [15].
Let \(P\) be a \(p\)-group of class \(2\) and exponent \(p\). Since \(P\) has exponent \(p\), every abelian subgroup of \(P\) is elementary abelian, that is, isomorphic to \(\mathbb{Z}_p^k\) for some \(k \in \mathbb{N}\). Moreover, if \(B\) is an abelian subgroup of \(P\), then \(B=B'\times B''\), where \(B''=B\cap [P,P]\) and \(B'\cap [P,P]=1\). Since \([P,P]\leqslant Z(P)\), it follows that \(B'[P,P]\) is again abelian. Hence every abelian subgroup of \(P\) is contained in an abelian subgroup containing the commutator subgroup.
It follows that totally isotropic subspaces of \(\mathcal{B}_P\) correspond to abelian subgroups of \(P\) that contain the commutator subgroup. This observation was used by Alperin to construct large abelian subgroups of \(p\)-groups of class \(2\) and exponent \(p\) [6]. It is also the starting point of work of Ol’shanskii [7] and of Buhler, Gupta and Harris [8] on the construction of \(p\)-groups with small maximal abelian subgroups.
Our totally isotropic space polynomials can be viewed as enumeration polynomials for abelian subgroups of \(p\)-groups of class \(2\) and exponent \(p\) containing the commutator subgroup.
Let \(P\) be a \(p\)-group of class \(2\) and exponent \(p\). Let \(A_i(P)\) be the set of abelian subgroups \(S\) in \(P\) containing \([P, P]\), with \(S/[P,P]\) being of order \(p^i\), and let \(a_i(P):=|A_i(P)|\). Let \(x\) be a variable, and \(\alpha(P):=\max\{i\in\mathbb{N}\mid A_i(P)\neq\emptyset\}\). The enumeration polynomial of abelian subgroups of \(P\) containing the commutator subgroup is naturally \[\mathrm{Ab}(P, x):=1+\sum_{i\in[\alpha(P)]}a_i(P)\cdot x_p^i \in\mathbb{Z}[x].\]
Let \(\mathcal{B}_P\) be the alternating matrix space associated with \(P\) via the construction in Section 1.3.1. We then have \(\mathrm{Ab}(P, x)=\mathrm{TI}(\mathcal{B}_P, x)\). Note that while our construction of \(\mathcal{B}_P\) from \(P\) is basis-dependent, the resulting polynomial \(\mathrm{TI}(\mathcal{B}_P, x)\) does not depend on the basis choices.
Furthermore, disjoint direct sums of alternating matrix spaces correspond to direct products of groups [16]. Let \(P\) and \(Q\) be two \(p\)-groups of class \(2\) and exponent \(p\), and \(P\times Q\) be their direct product. Then Proposition 3 gives us that \(\mathrm{Ab}(P, x)\cdot \mathrm{Ab}(Q, x)=\mathrm{Ab}(P\times Q, x).\)
A closely related work is by T. Rossmann, who studied enumeration functions of conjugacy classes of graphical groups over finite fields [17]. Given a graph \(G\) and a commutative ring \(R\), one can construct an associated graphical group. When \(R=\mathbb{F}_p\) with \(p>2\), this group is a \(p\)-group of class \(2\) and exponent \(p\). In [17], Rossmann first introduced a new family of graph polynomials in two variables. He then showed that specialising the first variable gives rise to the enumeration polynomial of conjugacy classes of graphical groups over finite fields [17].
One consequence is that the number of size-\(e\) conjugacy classes of graphical groups over finite fields of order \(q\) is given by a polynomial in \(q-1\) with integer coefficients [17]. Analogously, our Theorem 1 can be interpreted as follows: for graphical groups over the prime field \(\mathbb{F}_p\), with \(p>2\), the number of rank-\(i\) elementary abelian subgroups containing the commutator subgroup is given by evaluating an integer polynomial at \(p\).
We note that the proof of [17], as that of our Theorem 2, deals with alternating bilinear maps, or equivalently in this case, alternating matrix spaces. Indeed, putting in the language of alternating matrix spaces, for \(\mathcal{B}\leq\Lambda(n, q)\), the object to enumerate for [17] is \[\label{eq:rossmann} \{v\in\mathbb{F}_q^n\mid \dim(\{Bv\mid B\in \mathcal{B}\})=e\}.\tag{3}\]
Rossmann also showed that the product of conjugacy class enumeration polynomials of two graphical groups gives the conjugacy class enumeration polynomial of the graphical group corresponding to the disjoint union of the two graphs [17]. Rossmann did not need our \(x_q^i\), because the objects to enumerate there are vectors (Equation 3 ), instead of subspaces as in our case.
Rossmann’s work [17], together with the results of the present paper, suggest that enumerating certain structures in finite groups leads to enumeration polynomials generalising corresponding graph-theoretic enumeration polynomials. It is reasonable to expect that further correspondences of this kind remain to be explored. For example, [9] established a correspondence between vertex colourings of graphs and direct sum decompositions into totally isotropic spaces of alternating bilinear maps. This raises the question of whether one may define a linear-algebraic analogue of the chromatic polynomials of graphs.
Computing graph independence polynomials is a natural problem, and it has been studied from several perspectives, including recursive identities and decomposition formulas [1], as well as algorithmic approaches via the hard-core model partition function [18]. While the proof of Theorem 2 yields a method for computing TI polynomials of graphical matrix spaces through analysing the underlying graph structure, it would be of interest to develop more efficient methods, either through recursive identities or from an algorithmic viewpoint.
Overall, it could be of interest to further the study of \(I(G, x, q)\) by transferring questions and methodologies for the independence polynomials such as in [1]. We leave these to future works.
Our goal is to show that for any \(1\leq i\leq \alpha(G)\), there exists \(c_i(q)\in\mathbb{Z}[q]\), such that \(c_i(q)=c_i(\mathcal{G}_q)\) for any prime power \(q\), and \(c_i(1)=c_i(G)\). Briefly speaking, this requires us to identify some combinatorial properties of \(G\) which essentially determine \(c_i(\mathcal{G}_q)\).
In the following we use \(e_i\) to denote the \(i\)th standard basis vector of \(\mathbb{F}_q^n\).
Some subsets of Grassmannians. Let \(\mathrm{Gr}(i, n, q)\) be the Grassmannian of \(i\)-dimensional subspaces of \(\mathbb{F}_q^n\). We will consider the following subsets of \(\mathrm{Gr}(i,n,q)\), each arising as the set of \(\mathbb{F}_q\)-rational points of a subvariety of the Grassmannian.
Let \(\binom{[n]}{i}\) be the set of size-\(i\) subsets of \([n]\). The natural total order of \([n]\) induces the lexicographic total order on \(\binom{[n]}{i}\).
For any \(i\)-dimensional subspace \(U\leqslant\mathbb{F}_q^n\), there is a unique matrix \(T_U\in \mathbb{F}_q^{n\times i}\) in reduced column echelon form whose columns form a basis of \(U\). Let \(P_U\in \binom{[n]}{i}\) be the set of pivot-row indices of \(T_U\). Equivalently, if the Plücker coordinates of \(U\) are indexed by elements of \(\binom{[n]}{i}\), then \(P_U\) is the lexicographically first index at which the Plücker coordinate is non-zero. In general, if \(T\) is any \(n \times i\) matrix whose columns span \(U\), then \(P_U\) indexes the lexicographically first full-rank minor of \(T\).
For \(P\in \binom{[n]}{i}\), define \[\mathrm{Gr}(i,n,q)_P:=\{U\leqslant\mathbb{F}_q^n\mid P_U=P\}.\] Thus \(\mathrm{Gr}(i,n,q)_P\) consists of those \(i\)-dimensional subspaces whose reduced column echelon form has pivot rows indexed by \(P\).
Fix \(P\in\binom{[n]}{i}\). For any \(U\in \mathrm{Gr}(i,n,q)_P\), let \(T_U\in \mathbb{F}_q^{n\times i}\) be the unique matrix in reduced column echelon form whose columns form a basis of \(U\). Then \(P_U=P\) is the set of pivot-row indices of \(T_U\). Define \(Q_U\subseteq [n]\setminus P_U\) to be the set of non-pivot row indices at which \(T_U\) has a non-zero row, namely \[Q_U:=\{j\in [n]\setminus P_U \mid \text{the jth row of }T_U\text{ is non-zero}\}.\] Equivalently, \[Q_U=\bigl\{j\in [n]\setminus P_U \mid U\not\subseteq \mathrm{span}\{e_k\mid k\in [n],\, k\neq j\}\bigr\}.\]
For \(P\in \binom{[n]}{i}\) and \(Q\subseteq [n]\setminus P\), define \[\mathrm{Gr}(i,n,q)_{P,Q}:=\{U\in \mathrm{Gr}(i,n,q)\mid P_U=P,\;Q_U=Q\}.\]
The following example illustrates that \(P_U\) records the pivot rows of \(T_U\), while \(Q_U\) records the non-pivot rows of \(T_U\) that are non-zero.
Example 1. Suppose \(q\geq 5\). Let \(n=5\) and \(i=2\), and let \(U\leqslant\mathbb{F}_q^5\) be the column space of \[T_U= \begin{pmatrix} 1&0\\ 2&4\\ 0&1\\ 0&0\\ 3&5 \end{pmatrix}.\] This matrix is in reduced column echelon form, and its pivot rows are \(1\) and \(3\). Hence \[P_U=\{1,3\}.\] Among the non-pivot rows \(2,4,5\), the \(2\)nd and \(5\)th rows are non-zero, while the \(4\)th row is zero. Therefore \[Q_U=\{2,5\}.\] Thus \(U\in \mathrm{Gr}(2,5,q)_{P,Q}\) for \(P=\{1,3\}\) and \(Q=\{2,5\}\).
Relating independent sets with \(\mathrm{Gr}(i, n, q)_P\). Let \(G=([n], E)\) be a graph. For \(1\leq i\leq \alpha(G)\), let \(S_i(G)\) be the set of size-\(i\) independent sets of \(G\). For a prime power \(q\), let \(S_i(\mathcal{G}_q)\) be the set of \(i\)-dimensional totally-isotropic spaces of \(\mathcal{G}_q\). Let \(\mathrm{Gr}(i, n, q, G):=\mathrm{Gr}(i, n, q)\cap S_i(\mathcal{G}_q)\).
For \(P\in\binom{[n]}{i}\), let \(\mathrm{Gr}(i, n, q, G)_P=\mathrm{Gr}(i, n, q)_P\cap S_i(\mathcal{G}_q)\).
Claim 4. \(\mathrm{Gr}(i, n, q, G)_P\neq\emptyset\) if and only if \(P\) is an independent set.
Proof. If \(P\) is a size-\(i\) independent set \(P\) of \(G\), \(\mathrm{Gr}(i, n, q)_P\cap S_i(\mathcal{G}_q)\) is non-empty, as it contains the subspace \(\mathrm{span}\{e_i\mid i\in P\}\leq\mathbb{F}_q^n\).
Suppose \(U\in\mathrm{Gr}(i, n, q)\) is a totally-isotropic space of \(\mathcal{G}_q\). As already observed in [9], it can be verified easily that, if the Plücker coordinate of \(U\) at \(R\in\binom{[n]}{i}\) is non-zero, then \(R\) is a size-\(i\) independent set of \(G\). It follows that if \(P\in\binom{[n]}{i}\) is not an independent set, then \(\mathrm{Gr}(i, n, q)_P\cap S_i(\mathcal{G}_q)=\emptyset\). ◻
By Claim 4, we have \(\mathrm{Gr}(i, n, q, G)\) is a disjoint union of \(\mathrm{Gr}(i, n, q, G)_P\) over \(P\in S_i(G)\).
Relating graph structures with \(\mathrm{Gr}(i, n, q)_{P, Q}\). Let \(P\in S_i(G)\), so \(\mathrm{Gr}(i, n, q, G)_P\) is non-empty.
Let \(\mathrm{Gr}(i, n, q, G)_{P, Q}:=\mathrm{Gr}(i, n, q)_{P, Q}\cap S_i(\mathcal{G}_q)\). We wish to understand when \(\mathrm{Gr}(i, n, q, G)_{P, Q}\) is empty. This is easy for \(Q=\emptyset\): in this case, \(\mathrm{Gr}(i, n, q, G)_{P, \emptyset}=\{\mathrm{span}\{e_i\mid i\in P\}\}\).
In general, for \(P, Q\subseteq[n]\), let \(G[P\cup Q]\) be the induced subgraph of \(G\) on \(P\cup Q\). Fix \(Q\subseteq[n]\setminus P\). Take some \(U\in \mathrm{Gr}(i, n, q)_{P, Q}\). Let \(T\) be an \(n\times i\) matrix whose columns form a basis of \(U\). For \(u\in [n]\), let \(r_u\) be the \(u\)th row of \(T\).
Lemma 1. Let \(U\in\mathrm{Gr}(i, n, q)_{P, Q}\) and \(T\) be as above. Then \(U\) is a totally-isotropic space for \(\mathcal{G}_q\) if and only if for any edge \(\{u, v\}\) in \(G[P\cup Q]\), \(r_u\) and \(r_v\) are linearly dependent.
Proof. Recall that \(G=([n], E)\). To start with, note that \(U\) is a totally-isotropic space of \(\mathcal{G}_q\) if and only if for any \(\{u, v\}\in E\), \[\label{eq:all-zero} r_u^{\mathrm{t}}r_v-r_v^{\mathrm{t}}r_u=0_{i\times i},\tag{4}\] where \(0_{i\times i}\) denotes the \(i\times i\) all-zero matrix. (Recall that \(r_u\) and \(r_v\) are row vectors.)
If \(u\not\in P\cup Q\), then \(r_u\) is the zero vector, so Equation 4 is satisfied. The same holds for \(v\). Therefore, we only need to consider \(u, v\in P\cup Q\). Then note that Equation 4 just expresses that \(r_u\) and \(r_v\) are linearly dependent, concluding the proof. ◻
Claim 5. Let \(u, v\in P\), \(u\neq v\). If \(G[P\cup Q]\) contains a path connecting \(u\) and \(v\), then \(\mathrm{Gr}(i, n, q, G)_{P, Q}=\emptyset\).
Proof. For the sake of contradiction, suppose \(\mathrm{Gr}(i, n, q, G)_{P, Q}\) is non-empty. Take an \(n\times i\) matrix \(T\) whose column span is in \(\mathrm{Gr}(i, n, q, G)_{P, Q}\). By Lemma 1, rows of \(T\) corresponding to the vertices on this path are all linearly dependent. It follows that row \(u\) and row \(v\) are linearly dependent, which is not possible because \(u, v\in P\). ◻
Claim 5 implies that for \(\mathrm{Gr}(i, n, q, G)_{P, Q}\) to be non-empty, every connected component of \(G[P\cup Q]\) contains at most one \(u\in P\).
Claim 6. Let \(C\subseteq P\cup Q\) be a connected component of \(G[P\cup Q]\), and suppose \(C\) contains exactly one \(u\in P\). If there exists \(v\in C\) with \(v< u\), then \(\mathrm{Gr}(i, n, q, G)_{P, Q}=\emptyset\).
Proof. For the sake of contradiction, suppose \(\mathrm{Gr}(i, n, q, G)_{P, Q}\) is non-empty. Take an \(n\times i\) matrix \(T\) whose column span \(U\) is in \(\mathrm{Gr}(i, n, q, G)_{P, Q}\). For \(w\in [n]\), let \(r_w\) be the \(w\)th row of \(T\). Note that \(v\in Q\), as \(u\) is the only vertex of \(C\) lying in \(P\). Furthermore, \(r_v\) is non-zero, and it is linearly dependent with \(r_u\). So if \(v<u\), we can replace \(u\) with \(v\) in \(P\), so \(P\) cannot be the lexicographic-first non-zero Plücker coordinate of \(U\). ◻
Claim 7. Let \(D\subseteq P\cup Q\) be a connected component of \(G[P\cup Q]\), and suppose \(D\) does not contain \(u\in P\). If \(\min\{v\mid v\in D\}<\min\{u\mid u\in P\}\), then \(\mathrm{Gr}(i, n, q, G)_{P, Q}=\emptyset\).
Proof. For the sake of contradiction, suppose \(\mathrm{Gr}(i, n, q, G)_{P, Q}\) is non-empty. Take an \(n\times i\) matrix \(T\) whose column span \(U\) is in \(\mathrm{Gr}(i, n, q, G)_{P, Q}\). As \(D\) does not contain \(u\in P\), we have \(D\subseteq Q\). If \(\min\{v\mid v\in D\}<\min\{u\mid u\in P\}\), then the lexicographically first non-zero row of \(T\) is indexed by some \(v'\in Q\setminus P\). It follows \(P\) cannot be the lexicographic-first non-zero Plücker coordinate of \(U\). ◻
The conditions in Claims 5, 6, 7 can then be used to deduce a characterisation of non-empty \(\mathrm{Gr}(i, n, q, G)_{P, Q}\).
Lemma 2. \(\mathrm{Gr}(i, n, q, G)_{P, Q}\neq\emptyset\) if and only if \(G[P\cup Q]\) satisfies the following:
every connected component of \(G[P\cup Q]\) contains at most one \(u\in P\),
any connected component \(C\) with one \(u\in P\) satisfies \(v\geq u\) for \(v\in C\),
and any connected component \(D\) with no \(u\in P\) satisfies \(\min\{v\mid v\in D\}> \min\{u\mid u\in P\}\).
Furthermore, when \(\mathrm{Gr}(i,n,q,G)_{P,Q}\neq\emptyset\) and \(Q\neq\emptyset\), \(\lvert \mathrm{Gr}(i,n,q,G)_{P,Q}\rvert\) can be expressed as a non-empty and finite product of factors of the form \(q^e-1\), with \(e\in\mathbb{N}\).
Proof. The only if direction has been shown by Claims 5, 6, and 7. For the if direction, we can construct \(U\in \mathrm{Gr}(i, n, q, G)_{P, Q}\) when \(G[P\cup Q]\) satisfies the conditions in the statement. This construction process also gives the number of such \(U\).
Recall that \[\mathrm{Gr}(i, n, q, G)_{P, Q}=\mathrm{Gr}(i, n, q)_{P, Q}\cap S_i(\mathcal{G}_q).\] Subspaces in \(\mathrm{Gr}(i, n, q)_{P, Q}\) are in one-to-one correspondence with matrices \(T\) of size \(n\times i\), such that the submatrix of \(T\) indexed by \(P\) is the identity matrix, and the non-zero rows of \(T\) are in \(P\cup Q\). For \(u\in [n]\), let \(r_u\) be the \(u\)th row of \(T\). We turn to examine those \(T\) whose column span is totally-isotropic for \(\mathcal{G}_q\), and count the numbers of such \(T\).
By Lemma 1, the column span of \(T\) is totally-isotropic for \(\mathcal{G}_q\) if and only if for any edge \(\{u, v\}\in G[P\cup Q]\), \(r_u\) and \(r_v\) are linearly dependent. This is the condition we will need to keep track of during the construction. Now consider the following two cases.
For a connected component \(C\) with \(u\in P\), note that \(C\) contains exactly one \(u\in P\), as \(T\) is assumed to be the identity on the rows indexed by \(P\). Consider \(v\in C\), \(v\neq u\). Then we must have \(r_v=\alpha\cdot r_u\) with non-zero \(\alpha\in\mathbb{F}_q\). This gives \((q-1)^{|C|-1}\) possibilities for \(r_v\), \(v\neq u\), \(v\in C\).
For a connected component \(D\) with no \(u\in P\), let \(v^*=\min\{v\mid v\in D\}\). Suppose \(|\{u\in P\mid u<v^*\}|=d\). Note that \(d\geq 1\). In this case, there are \(q^d-1\) possibilities for a non-zero \(r_{v^*}\), because \(r_{v^*}\) must be spanned by \(\{r_u : u \in P,\, u < v^*\}\). For other \(v\in D\), \(r_v=\alpha\cdot r_{v^*}\), so there are \((q-1)^{|D|-1}\) possibilities.
It can be seen that the resulting matrix \(T\) spans a totally-isotropic space, as for any edge \(\{u, v\}\in G[P\cup Q]\), \(r_u\) and \(r_v\) are linearly dependent. Furthermore, the above assignments of \(r_v\) for \(v\in C\), \(v\neq u\) and \(r_v\) for \(v\in D\) give rise to, and cover, \(T\in \mathrm{Gr}(i, n, q)_{P, Q}\) corresponding to totally-isotropic \(U\in\mathrm{Gr}(i, n, q, G)_{P, Q}\). That is, there are two types of restrictions: the restriction from the graph \(G[P\cup Q]\), and the restriction of the lexicographic order. These two types of restrictions together give a product of factors of the form \(q^e-1\).
Finally, note that if \(Q\neq\emptyset\), then at least one of the following two cases must hold, namely case (a) with \(|C|>1\), or case (b) with \(|D|\geq 1\). In the former case, there exists \(v\in C\), \(v\neq u\), such that \(r_v=\alpha\cdot r_u\), leading to a factor of \((q-1)\). In the latter case, there is at least a factor of the form \(q^d-1\). That is, some non-trivial \(q^e-1\) factor appears as long as \(Q\neq \emptyset\). The proof is concluded. ◻
Concluding the proof of Theorem 1. We have seen that \(\mathrm{Gr}(i, n, q, G)\) is a disjoint union of \(\cup_{P\in S_i(G)}\mathrm{Gr}(i, n, q, G)_P\).
For \(P\in S_i(G)\), let \[\mathcal{Q}_P=\{Q\subseteq[n]\setminus P\mid G[P\cup Q] \text{ satisfies (1), (2) and (3) in Lemma~\ref{lem:Q}}\}.\] Then we have \[\mathrm{Gr}(i, n, q, G)_P=\bigcup_{Q\in \mathcal{Q}_P} \mathrm{Gr}(i, n, q, G)_{P, Q}.\] We now distinguish between two cases. First, when \(Q=\emptyset\), it is easy to observe that \(|\mathrm{Gr}(i, n, q, G)_{P, \emptyset}|=1\). Second, when \(Q\neq\emptyset\), by Lemma 2, \(|\mathrm{Gr}(i, n, q, G)_{P, Q}|\) is a non-empty product of \(q^e-1\) where the exponents only depend on \(P\), \(Q\), and the graph structure \(G[P\cup Q]\). Therefore, for \(P\in S_i(G)\), \[|\mathrm{Gr}(i, n, q, G)_{P}|=1+\sum_{Q\in\mathcal{Q}_P, Q\neq \emptyset} \prod_{e_i}(q^{e_i}-1)\] for any \(q\). In particular, \(|\mathrm{Gr}(i, n, 1, G)_{P}|=1\). This concludes the proof of Theorem 1. 0◻
The goal of this section is to prove Proposition 3. We first prepare for the proof.
We use \(\genfrac{[}{]}{0pt}{}{n}{k}_{q}\) to denote the Gaussian binomial coefficient counting the number of \(k\)-dimensional subspaces of \(\mathbb{F}_q^n\). That is, \[\genfrac{[}{]}{0pt}{}{n}{k}_{q}=\frac{(q^n-1)\cdot(q^n-q)\cdot\ldots\cdot(q^n-q^{k-1})}{(q^k-1)\cdot(q^k-q)\cdot\ldots\cdot(q^k-q^{k-1})}.\]
We also need to work with the following setting. Let \(X_1\) be the subspace of \(\mathbb{F}_q^{n_1+n_2}\) spanned by the first \(n_1\) standard basis vectors, and let \(X_2\) be the subspace of \(\mathbb{F}_q^{n_1+n_2}\) spanned by the last \(n_2\) standard basis vectors. Let \(\pi_1\) be the projection from \(\mathbb{F}_q^{n_1+n_2}\) onto \(X_1\) along \(X_2\), and let \(\pi_2\) be the projection from \(\mathbb{F}_q^{n_1+n_2}\) onto \(X_2\) along \(X_1\).
Let \(U\leq X_1\) and \(V\leq X_2\), with \(\dim(U)=d\) and \(\dim(V)=e\). We are interested in subspaces \(W\leq \mathbb{F}_q^{n_1+n_2}\) such that \(\pi_1(W)=U\) and \(\pi_2(W)=V\). Note that \(\max\{d, e\}\leq \dim(W)\leq d+e\). Let \(s:=d+e-\dim(W)\), so \(0\leq s\leq \min\{d, e\}\).
Given \(d, e, s\in \mathbb{N}, s\leq \min\{d, e\}\), we define \[\label{eq:Cdesq} C_{d, e, s, q}=\genfrac{[}{]}{0pt}{}{d}{s}_{q}\cdot \genfrac{[}{]}{0pt}{}{e}{s}_{q}\cdot (q^s-1)\cdot \ldots\cdot (q^s-q^{s-1}).\tag{5}\] When \(q\) is obvious from the context, we may simply write \(C_{d, e, s}\) instead of \(C_{d, e, s, q}\).
We then show the following counting result; see Section 3.1 for its proof.
Lemma 3. The number of \((d+e-s)\)-dimensional \(W\) with \(\pi_1(W)=U\) and \(\pi_2(W)=V\) is \(C_{d, e, s, q}\).
We now relate \(C_{d,e,s,q}\) with \(x_q^d\) introduced in Equation 2 ; see Section 3.2 for its proof.
Lemma 4. For \(d, e\in\mathbb{N}\), we have \[\label{eq:xqd} x_q^d\cdot x_q^e=\sum_{s=0}^{\min\{d, e\}}C_{d, e, s, q}\cdot x_q^{d+e-s}.\tag{6}\]
We now prove Proposition 1.5 using Lemmas 3.1 and 3.2.
Proposition 3, restated. Let \(\mathcal{B}\leq\Lambda(n_1, q)\), \(\mathcal{C}\leq\Lambda(n_2, q)\), and \(\mathcal{A}\leq \Lambda(n_1+n_2, q)\) be the disjoint direct sum of \(\mathcal{B}\) and \(\mathcal{C}\). Then \(\mathrm{TI}(\mathcal{A}, x)=\mathrm{TI}(\mathcal{B}, x)\cdot\mathrm{TI}(\mathcal{C}, x)\).
Proof of Proposition 3. Let \(X_1\) be the subspace of \(\mathbb{F}_q^{n_1+n_2}\) spanned by the first \(n_1\) standard basis vectors, and let \(X_2\) be the subspace of \(\mathbb{F}_q^{n_1+n_2}\) spanned by the last \(n_2\) standard basis vectors. Let \(\pi_1\) be the projection from \(\mathbb{F}_q^{n_1+n_2}\) onto \(X_1\) along \(X_2\), and let \(\pi_2\) be the projection from \(\mathbb{F}_q^{n_1+n_2}\) onto \(X_2\) along \(X_1\).
Let \(U\leq X_1\) be a totally-isotropic space of \(\mathcal{B}\), and \(V\leq X_2\) be a totally-isotropic space of \(\mathcal{C}\). Suppose \(\dim(U)=d\) and \(\dim(V)=e\). Therefore, \(U\) contributes \(x_q^d\) in \(\mathrm{TI}(\mathcal{B}, x)\), and \(V\) contributes \(x_q^e\) in \(\mathrm{TI}(\mathcal{C}, x)\).
As \(\mathcal{A}\) is the disjoint direct sum of \(\mathcal{B}\) and \(\mathcal{C}\), it can be verified that \(W\) is totally-isotropic for \(\mathcal{A}\) if and only if \(\pi_1(W)\) is totally-isotropic for \(\mathcal{B}\) and \(\pi_2(W)\) is totally-isotropic for \(\mathcal{C}\).
Lemma 3 shows that \(C_{d, e, s, q}\) is the number of totally-isotropic spaces \(W\) such that \(\pi_1(W)=U\), \(\pi_2(W)=V\), \(\dim(W)=d+e-s\). Lemma 4 shows that the number \(C_{d, e, s, q}\) is the coefficient of \(x_q^{d+e-s}\) in the expansion of \(x_q^d\cdot x_q^e\). The proof is then concluded. ◻
After the proof, it may be instructive to examine an example.
Example 2. Let \(\mathcal{B}\leq\Lambda(n_1, q)\) and \(\mathcal{C}\leq\Lambda(n_2, q)\). Let \(\mathcal{A}\leq\Lambda(n_1+n_2, q)\) be the disjoint direct sum of \(\mathcal{B}\) and \(\mathcal{C}\). Let \(U_1=\mathrm{span}\{u_1\}\) be a \(1\)-dimensional subspace of \(\mathbb{F}_q^{n_1}\) and \(U_2=\mathrm{span}\{u_2\}\) a \(1\)-dimensional subspace of \(\mathbb{F}_q^{n_2}\). By the alternating property, \(U_1\) and \(U_2\) are totally-isotropic spaces of \(\mathcal{B}\) and \(\mathcal{C}\), respectively.
Suppose we are interested in \(W\leq\mathbb{F}_q^{n_1+n_2}\) such that \(\pi_1(W)=U_1\) and \(\pi_2(W)=U_2\), where \(\pi_1\) is the projection to the first \(n_1\) coordinates, and \(\pi_2\) is the projection to the last \(n_2\) coordinates. Note that such \(W\) is a totally-isotropic space for \(\mathcal{A}\). We then see that \(\dim(W)=2\) or \(\dim(W)=1\). When \(\dim(W)=2\), such \(W\) is unique. When \(\dim(W)=1\), then \(W=\mathrm{span}\{w\}\in \mathbb{F}_q^{n_1+n_2}\) for some non-zero \(w\in \mathbb{F}_q^{n_1+n_2}\). Suppose \(w=\begin{bmatrix} w_1\\ w_2 \end{bmatrix}\), where \(w_1\in\mathbb{F}_q^{n_1}\). We can then fix \(w_1=u_1\), and after that, \(w_2\) can be any non-zero scalar multiple of \(u_2\). It follows that there are \((q-1)\) such \(1\)-dimensional \(W\).
We then see that this is consistent with the choices of \(x_q^i\). That is, \(x_q\cdot x_q=x^2=x(x-(q-1))+(q-1)\cdot x=x_q^2+(q-1)\cdot x_q\).
We need to count the number of \(W\leq\mathbb{F}_q^{n_1+n_2}\) such that \[\label{eq:W} \dim(W)=d+e-s, \pi_1(W)=U, \text{ and } \pi_2(W)=V.\tag{7}\] Let \(K_1=\ker(\pi_2)\cap W=X_1\cap W\), and \(K_2=\ker(\pi_1)\cap W=X_2\cap W\). By \(\dim(W)=\dim(V)+\dim(K_1)\), we have \(\dim(K_1)=\dim(W)-\dim(V)=d+e-s-e=d-s\). Similarly, we have \(\dim(K_2)=e-s\).
Take any \(W\leq \mathbb{F}_q^{n_1+n_2}\) satisfying Equation 7 . Let \(T\in\mathrm{M}((n_1+n_2)\times (d+e-s), q)\) be a matrix whose columns span \(W\). By arranging an appropriate basis of \(W\), we can set \[\label{eq:T} T=\begin{bmatrix} T_1 & T_2 & 0_{n_1\times (e-s)} \\ 0_{n_2\times (d-s)} & T_3 & T_4 \end{bmatrix},\tag{8}\] where \(T_2\in \mathrm{M}(n_1\times s, q)\) and \(T_3\in \mathrm{M}(n_2\times s, q)\). We then see that the columns of \(\begin{bmatrix} T_1 \\ 0_{n_2\times (d-s)} \end{bmatrix}\) span \(K_1\), the columns of \(\begin{bmatrix} 0_{n_1\times (e-s)} \\ T_4 \end{bmatrix}\) span \(K_2\), the columns of \(\begin{bmatrix} T_2 \\ 0_{n_2\times s} \end{bmatrix}\) span \(L_1\) which is a complementary subspace of \(K_1\) in \(U\), and the columns of \(\begin{bmatrix} 0_{n_1\times s} \\ T_3 \end{bmatrix}\) span \(L_2\) which is a complementary subspace of \(K_2\) in \(V\). That is, \(U=K_1\oplus L_1\) and \(V=K_2\oplus L_2\).
Any subspace \(W\) satisfying Equation 7 has an ordered linear basis as columns of a matrix \(T\) in Equation 8 . On the other hand, every such \(T\) gives rise to such a subspace \(W\). However, two different \(T\) and \(T'\) may give rise to the same \(W\). It is clear that for \(T\) and \(T'\) to give rise to the same \(W\), then \(T\) and \(T'\) must be related by the following transformations:
Elementary operations on the first \(d-s\) columns. This means that to avoid double counting, we need to count the number of subspaces spanned by \(\begin{bmatrix} T_1 \\ 0_{n_2\times (d-s)} \end{bmatrix}\).
Elementary operations on the last \(e-s\) columns. This means that to avoid double counting, we need to count the number of subspaces spanned by \(\begin{bmatrix} 0_{n_1\times (e-s)} \\ T_4 \end{bmatrix}\).
Adding columns from the first \(d-s\) columns and the last \(e-s\) columns to the middle \(s\) columns. This means that to avoid double counting, we don’t need to enumerate complementary subspaces of \(K_1\) in \(U\), but any representative complementary subspace would suffice. Similarly, we don’t need to enumerate complementary subspaces of \(K_2\) in \(V\).
Elementary operations on the middle \(s\) columns. This means that to avoid double counting, we can fix an ordered basis of \(L_1\), that is the \(T_2\) part in Equation 8 . Note that this leaves \(T_3\) part undetermined.
Summarising the above, we proceed with the counting. To start with, by (1) and (2), the choices of \(K_1\) and \(K_2\) are uniquely determined by \(W\), and there are \(\genfrac{[}{]}{0pt}{}{d}{s}_{q}\cdot \genfrac{[}{]}{0pt}{}{e}{s}_{q}\) such choices. Once these \(K_1\) and \(K_2\) are fixed, by (3), we can fix \(L_1\) and \(L_2\) as complementary subspaces of \(K_1\) in \(U\) and \(K_2\) in \(V\), respectively. By (4), the \(T_3\) part needs to be an ordered basis of \(L_2\), and the number of ordered bases is \((q^s-1)\cdot \ldots\cdot (q^s-q^{s-1})\). Putting these together, we get the number of such subspaces \(W\) as \[\genfrac{[}{]}{0pt}{}{d}{s}_{q}\cdot \genfrac{[}{]}{0pt}{}{e}{s}_{q}\cdot (q^s-1)\cdot \ldots\cdot (q^s-q^{s-1})= C_{d, e, s, q}.\] This concludes the proof of Lemma 3. 0◻
By switching the role of \(d\) and \(e\) in the following if necessary, we can assume \(e\leq d\). Proof by induction on \(e\). If \(e=0\), then this holds trivially.
Consider the case \(e\geq 1\), and assume that the claim holds for all integers from \(1\) up to \(e-1\). By induction, we have \[\begin{align} x_q^d\cdot x_q^e & = & x_q^d\cdot x_q^{e-1}\cdot (x-(q^{e-1}-1)) \\ & = & \left(\sum_{s=0}^{e-1}C_{d, e-1, s}\cdot x_q^{d+e-1-s}\right)\cdot \left(x-(q^{e-1}-1)\right). \end{align}\] For \(i\in\{0, 1, \dots, e-1\}\), we have \[\begin{align} & & C_{d, e-1, i}\cdot x_q^{d+e-1-i}\cdot (x-(q^{e-1}-1)) \nonumber\\ & = & C_{d, e-1, i}\cdot x_q^{d+e-1-i}\cdot (x-(q^{d+e-1-i}-1) \nonumber \\ & & \quad +(q^{d+e-1-i}-1)-(q^{e-1}-1)) \nonumber\\ & = & C_{d, e-1, i}\cdot x_q^{d+e-1-i}\cdot (x-(q^{d+e-i-1}-1)) \nonumber\\ & & \quad +C_{d, e-1, i}\cdot x_q^{d+e-1-i}\cdot (q^{d+e-i-1}-q^{e-1}) \nonumber\\ & = & C_{d, e-1, i}\cdot x_q^{d+e-i}+C_{d, e-1, i}\cdot x_q^{d+e-1-i}\cdot q^{e-1}\cdot (q^{d-i}-1). \label{eq:ed} \end{align}\tag{9}\]
First, set \(i=0\) in the formula in Equation 9 to obtain \[C_{d, e-1, 0}\cdot x_q^{d+e}+C_{d, e-1, 0}\cdot x_q^{d+e-1}\cdot q^{e-1}\cdot (q^{d}-1).\] We then see that the coefficient of \(x_q^{d+e}\) is \(C_{d, e-1, 0}\). As \(C_{d, e-1, 0}=C_{d, e, 0}\), we have \(C_{d, e-1, 0}\cdot x_q^{d+e}=C_{d, e, 0}\cdot x_q^{d+e}\), giving us the term corresponding to \(s=0\) in Equation 6 .
Second, set \(i=e-1\) in the formula in Equation 9 to obtain \[C_{d, e-1, e-1}\cdot x_q^{d+1}+C_{d, e-1, e-1}\cdot x_q^{d}\cdot q^{e-1}\cdot (q^{d-e+1}-1).\] We then see that the coefficient of \(x_q^d\) is \(C_{d, e-1, e-1}\cdot q^{e-1}\cdot (q^{d-e+1}-1)\), which is equal to \(C_{d, e, e}\). This can be seen by setting \(s=e\) in Equation 5 , which gives \(C_{d, e, e}=\genfrac{[}{]}{0pt}{}{d}{e}_{q}\cdot \genfrac{[}{]}{0pt}{}{e}{e}_{q}\cdot (q^e-1)\cdot\ldots\cdot (q^e-q^{e-1})=(q^d-1)\cdot\ldots\cdot(q^d-q^{e-1})=C_{d, e-1, e-1}\cdot(q^d-q^{e-1})=C_{d, e-1,e-1}\cdot q^{e-1}\cdot (q^{d-e+1}-1)\).
Third, it remains to examine \(x_q^{d+e-j}\) for \(j\in \{1, \dots, e-1\}\). Its coefficient has two summands: one is \(C_{d, e-1, j}\), coming from setting \(i=j\) in Equation 9 , and the other is \(C_{d, e-1, j-1}\cdot q^{e-1}\cdot (q^{d-j+1}-1)\), coming from setting \(i=j-1\) in Equation 9 . Then it suffices to show the following.
Claim 8. For \(i\in \{0, 1, \dots, e-2\}\), we have \[C_{d, e-1, i}\cdot q^{e-1}\cdot (q^{d-i}-1)+C_{d, e-1, i+1}=C_{d, e, i+1}.\]
Proof. To start with, we have that \[\begin{align} & & C_{d, e-1, i}\cdot q^{e-1}\cdot (q^{d-i}-1)+C_{d, e-1, i+1} \\ & = & \genfrac{[}{]}{0pt}{}{d}{i}_{q}\cdot \genfrac{[}{]}{0pt}{}{e-1}{i}_{q}\cdot (q^i-1)\cdot\ldots\cdot (q^i-q^{i-1})\cdot q^{e-1}\cdot (q^{d-i}-1)\\ & & \quad +\genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot\genfrac{[}{]}{0pt}{}{e-1}{i+1}_{q}\cdot (q^{i+1}-1)\cdot \ldots\cdot (q^{i+1}-q^i)\\ & = & \genfrac{[}{]}{0pt}{}{d}{i}_{q}\cdot \genfrac{[}{]}{0pt}{}{e-1}{i}_{q}\cdot (q^{i+1}-q)\cdot\ldots\cdot (q^{i+1}-q^i)\cdot q^{e-1-i}\cdot (q^{d-i}-1)\\ & & \quad +\genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot\genfrac{[}{]}{0pt}{}{e-1}{i+1}_{q}\cdot (q^{i+1}-1)\cdot \ldots\cdot (q^{i+1}-q^i) \\ & = & (q^{i+1}-q)\cdot \ldots \cdot (q^{i+1}-q^i) \\ & & \quad \cdot\Huge( \genfrac{[}{]}{0pt}{}{d}{i}_{q}\cdot \genfrac{[}{]}{0pt}{}{e-1}{i}_{q}\cdot q^{e-1-i}\cdot (q^{d-i}-1) + \genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot\genfrac{[}{]}{0pt}{}{e-1}{i+1}_{q}\cdot (q^{i+1}-1) \Huge). \end{align}\] Finally, we note (1) \(\genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot(q^{i+1}-1)=\genfrac{[}{]}{0pt}{}{d}{i}_{q} \cdot(q^{d-i}-1)\) and (2) a \(q\)-Pascal identity \(\genfrac{[}{]}{0pt}{}{e-1}{i}_{q}\cdot q^{e-1-i}+\genfrac{[}{]}{0pt}{}{e-1}{i+1}_{q}=\genfrac{[}{]}{0pt}{}{e}{i+1}_{q}\). These allow us to obtain \[\begin{align} & & \genfrac{[}{]}{0pt}{}{d}{i}_{q}\cdot \genfrac{[}{]}{0pt}{}{e-1}{i}_{q}\cdot q^{e-1-i}\cdot (q^{d-i}-1) + \genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot\genfrac{[}{]}{0pt}{}{e-1}{i+1}_{q}\cdot (q^{i+1}-1) \\ & = & \genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot \genfrac{[}{]}{0pt}{}{e-1}{i}_{q}\cdot q^{e-1-i}\cdot (q^{i+1}-1) + \genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot\genfrac{[}{]}{0pt}{}{e-1}{i+1}_{q}\cdot (q^{i+1}-1) \\ & = & \genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot (q^{i+1}-1)\cdot (\genfrac{[}{]}{0pt}{}{e-1}{i}_{q}\cdot q^{e-1-i}+\genfrac{[}{]}{0pt}{}{e-1}{i+1}_{q})\\ & = & \genfrac{[}{]}{0pt}{}{d}{i+1}_{q}\cdot (q^{i+1}-1)\cdot \genfrac{[}{]}{0pt}{}{e}{i+1}_{q}. \end{align}\] This concludes the proof of Claim 8. ◻
Letting \(j=i+1\), we obtain \(C_{d, e, j}=C_{d, e-1, j-1}\cdot q^{e-1}\cdot (q^{d-j+1}-1)+C_{d, e-1, j}\). This concludes the proof of Lemma 4.0◻
I would like to thank Yuval Wigderson for his feedback on an early draft of this paper. I would like to express my sincere thanks to the anonymous reviewers for their careful and thoughtful reviews.