# Counting characters of small degree in upper unitriangular groups

Maria Loukaki  Department of Mathematics, University of Crete, 71409 Iraklio
Crete, Greece<EMAIL_ADDRESS>
###### Abstract.

Let $U_{n}$ denote the group of upper $n\times n$ unitriangular matrices over
a fixed finite field $\mathbf{F}$ of order $q$. That is, $U_{n}$ consists of
upper triangular $n\times n$ matrices having every diagonal entry equal to
$1$. It is known that the degrees of all irreducible complex characters of
$U_{n}$ are powers of $q$. It was conjectured by Lehrer that the number of
irreducible characters of $U_{n}$ of degree $q^{e}$ is an integer polynomial
in $q$ depending only on $e$ and $n$. We show that there exist recursive (for
$n$) formulas that this number satisfies when $e$ is one of $1,2$ and $3$, and
thus show that the conjecture is true in those cases.

##  1\. Introduction

We fix a prime $p$. Let $q$ be a fixed power of $p$ and
$\mathbf{F}_{q}=\mathbf{F}$ the finite field of order $q$. We write
$U_{n}(q)=U_{n}$ for the group of upper triangular $n\times n$ matrices over
$\mathbf{F}$, whose diagonal elements are all equal to $1$. We also write
$GL_{n}(q)$ for the general linear group of all $n\times n$ invertible
matrices over $\mathbf{F}$ and note that $U_{n}(q)$ is a $p$-Sylow subgroup of
$GL_{n}(q)$. Furthermore, for every finite group $G$ and every integer $k$ we
write

$N_{k}(G)=|\\{\chi\in\operatorname{Irr}(G)\mid\chi(1)=k\\}|,$

for the number of irreducible characters of $G$ of degree $k$.

In 1974 G. I. Lehrer, see [6], conjectured two results. First, he claimed that
the degrees of the irreducible representations of $U_{n}$ are of type $q^{e}$
for some $e\in\\{0,1,\cdots,\mu(n)\\}$, where

$\mu(n)=\begin{cases}m(m-1)\text{ if $n=2m$ and }\\\ m^{2}\text{ if
$n=2m+1$.}\end{cases}$

Next he conjectured that for any fixed $n$, the number of irreducible
characters of $U_{n}$ whose degree is $q^{e}$, i.e., $N_{q^{e}}(U_{n})$ in our
notation, is an integer polynomial in $q$ depending only on $e$.

As far as the first of his conjecture is concerned, it was shown by M. Isaacs
[5], that every irreducible character of $U_{n}$ has degree a power of $q$. In
addition, B. Huppert, [2], proved that the degrees of the irreducible
characters of $U_{n}$ is exactly the set $\\{q^{e}\mid 0\leq e\leq\mu(n)\\}$.

As for the second part of his conjecture, it still remains open apart for some
specific values of $e$.

The case $e=0$ is well known and easy to compute, that is,
$N_{1}(U_{n}(q))=N_{1}(U_{n})=q^{n-1}$. For greater values of $e$, M. Marjoram
[7] provided some first formulas. In particular, he proved that there exist
formulas for the number of irreducible characters having one of the next two
lowest degrees, that is $N_{q}(U_{n})$ and $N_{q^{2}}(U_{n})$. Also in his
unpublished thesis [8], M. Marjoram established formulas for the three highest
degrees when $n=2m$ is even, that is $N_{q^{\mu(n)}}(U_{2m})$,
$N_{q^{\mu(n)-1}}(U_{2m})$ and $N_{q^{\mu(n)-2}}(U_{2m})$, as well as a
formula for the number of irreducible characters of highest degree when $n$ is
odd, that is $N_{q^{\mu(n)}}(U_{2m+1})$.

In addition, I. M. Isaacs, in his paper [4], using a different method,
constructed specific polynomials for the number of irreducible characters of
$U_{n}(q)$ of degree $q,q^{\mu(n)}$ and $q^{\mu(n)-1}$. He also suggested a
stronger form a Lehrer’s conjecture (see Conjecture B in [4]), that the
functions $N_{q^{e}}(U_{n})$ are polynomials in $q-1$ with nonnegative integer
coefficients.

In this paper we use an elementary method to construct recursive formulas that
the number of irreducible characters of degree $q,q^{2}$ and $q^{3}$ satisfy
and thus we verify Lehrer’s conjecture. (Of course the cases $q$ and $q^{2}$
were already known by Marjoram’s formulas.) In a forthcoming paper we prove
analogous recursive formulas for the degrees $q^{\mu(n)},q^{\mu(n)-1}$ and
$q^{\mu(n)-2}$.

We follow the notation used in [3]. In addition, for any matrix
$X=(x_{i,j})\in GL_{n}(q)$ we write $R_{i}(X)$ for its $i$-row written as an
$1\times n$ matrix. We also write $C_{j}(X)$ for its $j$-column written as an
$n\times 1$ matrix. Also if $A=(a_{i,j})\in U_{n}$ then we say that its
$i$-row is trivial if the only nonzero element in that row is the diagonal
element $a_{i,i}=1$. Similarly, we say that the $j$-column of $A$ is trivial
if every entry in the $j$-column of $A$ is $0$ except $a_{j,j}=1$. We will
often consider the additive abelian group of the $st$-dimensional vector space
$\mathbf{F}^{st}$ (of order $q^{st}$) as the additive group of all $s\times t$
matrices over $\mathbf{F}$. When viewed as such we write it as
$\mathbf{F}^{s\times t}$.

Acknowledgments Most of this work was done will I was visiting Georgia
Institute of Technology. I would like to thank the Math department for its
hospitality. I’m also grateful to the referee whose suggestions improved
dramatically the original paper. The short proof of Theorem 1 is his
contribution. Furthermore, as he pointed out the recursive formulas we prove
below for $N_{q^{3}}(U_{n})$ (see (6.3), (7.2) and (7.3)) imply that
$N_{q^{3}}(U_{n})$ is a polynomial function in $q-1$ with nonnegative integer
coefficients. Hence Isaacs conjecture holds for $e=3$. (Of course it holds for
$e=1$ and $e=2$).

##  2\. Orbits of unitriangular actions on $\mathbf{F}^{s\times t}$

The aim of this section is to compute the orbits of a specific action of
$H=U_{s}\times U_{t}$ on $\mathbf{F}^{s\times t}$.

######  Definition 1.

Let $T$ be an $s\times t$ matrix over $\mathbf{F}$. We call $T$ quasimonomial
if it has at most one non-zero entry in every column and row.

We write $E_{i,j}$ for the matrix that has $1$ in it’s $(i,j)$-entry and $0$
everywhere else. Clearly $E_{i,j}$ is quasimonomial. Furthermore, every
nonzero quasimonomial matrix $T$ can be written as

(2.1)
$T=f_{1}E_{i_{1},j_{1}}+f_{2}E_{i_{2},j_{2}}+\cdots+f_{k}E_{i_{k},j_{k}}$

with $j_{1}<j_{2}<\cdots<j_{k}$, all $i_{1},\dots,i_{k}$ distinct, and
$f_{1},\dots,f_{k}$ non-zero elements in $\mathbf{F}$. We call 2.1 the
standard form of the non-zero $T$ and we say that $k$ is the length of $T$.

######  Theorem 1.

Assume that the group $H=U_{s}\times U_{t}$ acts on $\mathbf{F}^{s\times t}$
in the following way

$X^{(A,B)}=A^{-1}XB,$

for all $X\in\mathbf{F}^{s\times t},A\in U_{s}$ and $B\in U_{t}$. Then the set
of distinct quasimonomial matrices in $\mathbf{F}^{s\times t}$ forms a
complete set of orbit representatives of the action of $H$ on
$\mathbf{F}^{s\times t}$.

###### Proof.

Let $X\in\mathbf{F}^{s\times t}$. We show that by performing admissible
transformations we can get a quasimonomial matrix. By an admissible
transformation we mean adding to a row (respectively a column) a multiple of a
subsequent row (resp. a previous column). By induction we can suppose that the
$(s-1)\times t$ submatrix of $X$ formed by all rows except the first one is
quasimonomial. Let $x_{i_{1},j_{1}},\ldots,x_{i_{l},j_{l}}$, $2\leq
i_{1}<\ldots<i_{l}$, be the non-zero elements in this submatrix. Then we can
suppose that $x_{1,j_{1}}=\ldots=x_{1,j_{l}}=0$. If the rest of elements in
the first row are now zero we are done. Otherwise let $x_{1,j}$ be the first
non-zero element in the first row. Then, except for $x_{1,j}$, the $j$th
column is zero and, by performing admissible column transformations, we can
have that $x_{1,j}$ is the unique non-zero element in the first row, and thus
obtain a quasimonomial matrix.

To prove uniqueness, we argue again by induction on $s$ and $t$. If $X,Y$ are
quasimonomial matrices in the same orbit, we can suppose that the last $s-1$
rows and the first $t-1$ columns of $X$ and $Y$ are the same. We only need to
show that $x_{1,t}=y_{1,t}$. If some element in the first row or in the last
column different from the $(1,t)$-entry is non-zero, then $x_{1,t}=y_{1,t}=0$
and $X=Y$. Otherwise comparing the $(1,t)$-entry in $XB=AY$ we get
$x_{1,t}=y_{1,t}$ and $X=Y$.

∎

When a first version of this paper appeared, Vera-López, Arregi and Ormaetxea
told me (I thank them for that) about a more general result concerning
conjugacy classes in unitriangular groups (see [9], [10], [11]), whose special
case is Theorem 1.

##  3\. Irreducible characters in $U_{n}$

In this section we will show how Section 2 is connected to Lehrer’s
conjecture. We follow Marjoram’s approach on the problem, and Proposition 1
below follows from his paper [7].

For a fixed but arbitrary integer $n$ we consider the upper unitriangular
group $U_{n}$ over $\mathbf{F}_{q}$, and its two subgroups $M_{n,t}$ and
$H_{n,t}$ defined in the following way. If $1\leq t\leq n$ and $s=n-t$ then

$M_{n,t}=\\{\left(\begin{matrix}I_{t}&C\\\
0&I_{s}\end{matrix}\right):C\in\mathbf{F}^{t\times s}\\}=\\{X\in U_{n}\text{
with }x_{i,j}=0\text{ if either \, $i<j\leq t$ or $t<i<j$}\\}$

and

$H_{n,t}=\\{\left(\begin{matrix}B&0\\\ 0&A\end{matrix}\right):A\in U_{s}\text{
and }B\in U_{t}\\}=\\{X\in U_{n}\text{ with }x_{i,j}=0\text{ if $i\leq t$ and
$j>t$}\\}.$

It is easy to see that for all $t=1,\dots,n$, the group $M_{n,t}$ is an
abelian normal subgroup of $U_{n}$, isomorphic to $\mathbf{F}^{t\times s}$. In
addition, $H_{n,t}$ complements $M_{n,t}$ in $U_{n}$, and is isomorphic to
$U_{s}\times U_{t}$. We identify $H_{n,t}$ with $U_{s}\times U_{t}$ and we
write its elements as $(A,B)$ with $A\in U_{s}$ and $B\in U_{t}$. We also
identify the $M_{n,t}$ with $\mathbf{F}^{t\times s}$, and thus we write the
elements of $M_{n,t}$ as $C\in\mathbf{F}^{t\times s}$. Note that with these
identifications, the conjugation action of $H_{n,t}$ on $M_{n,t}$ in
$U=M_{n,t}\rtimes H_{n,t}$ is given as

(3.1) $C^{(A,B)}=B^{-1}CA,$

for all $(A,B)\in H_{n,t}$ and $C\in M_{n,t}$. The product that appears at the
right hand side of the equation above is the standard product of matrices.

Marjoram has given a nice characterization for the abelian group
$\operatorname{Irr}(M_{n,t})$, and the way $H_{n,t}$ acts on that group. We
collect his results (Lemma 2 and 3 in [7]) in the next proposition.

######  Proposition 1.

Let $M_{n,t}$ and $H_{n,t}$ be defined as above, for fixed but arbitrary $n$
and $t$. Then $\operatorname{Irr}(M_{n,t})$ is isomorphic to the abelian
additive group $\mathbf{F}^{s\times t}$ of all the $s\times t$ matrices over
$\mathbf{F}=\mathbf{F}_{q}$. The isomorphism is given by
$D\in\mathbf{F}^{s\times t}\to\lambda_{D}\in\operatorname{Irr}(M_{n,t})$,
where the map $\lambda_{D}:M_{n,t}\to\mathbf{C}$ is defined as

$\lambda_{D}(C)=\omega^{T(tr(DC))},\text{ for all }C\in M_{n,t},$

where $\omega$ is a primitive $p$-root of unity,
$T:\mathbf{F}_{q}\to\mathbf{F}_{p}$ is the usual trace map from the extension
field of $q$ elements $\mathbf{F}_{q}$ to the ground field $\mathbf{F}_{p}$ of
$p$ elements and $tr(DC)$ denotes the trace of the square $s\times s$ matrix
$DC$. Furthermore identifying $H_{n,t}$ with $U_{s}\times U_{t}$, we get that
the action of $H_{n,t}$ on $\operatorname{Irr}(M_{n,t})$ is given as

$\lambda_{D}^{(A,B)}(C)=\lambda_{D}(C^{(A^{-1},B^{-1})})=\lambda_{D}(BCA^{-1})=\omega^{T(tr(DBCA^{-1}))}=\omega^{T(tr(A^{-1}DBC))}=\lambda_{A^{-1}DB}(C),$

for all $D\in\mathbf{F}^{s\times t},C\in\mathbf{F}^{t\times s}$ and all
$(A,B)\in U_{s}\times U_{t}\cong H_{n,t}$. Thus $U_{s}\times U_{t}\cong
H_{n,t}$ acts on $\operatorname{Irr}(M_{n,t})\cong\mathbf{F}^{s\times t}$ as

$D^{(A,B)}=A^{-1}DB.$

What the above proposition says is that, identifying
$\operatorname{Irr}(M_{n,t})$ with $\mathbf{F}^{s\times t}$ and $H_{n,t}$ with
$U_{s}\times U_{t}$, then Theorem 1 provides a complete set of orbit
representatives of the action of $H_{n,t}$ on $\operatorname{Irr}(M_{n,t})$.
In particular,

(3.2) $\Omega_{n,t}=\\{T\in\mathbf{F}^{s\times t}\mid T\text{
quasimonomial}\\}.$

is such a set of representatives.

Now, let $G$ be any finite group $N$ an abelian normal subgroup of $G$ and $H$
a complement of $N$ in $G$, then it is easy to characterize the irreducible
characters of $G$. In particular, if $\lambda\in\operatorname{Irr}(N)$, and
$G_{\lambda}$ is the stabilizer of $\lambda$ in $G$, then Gallagher’s theorem
and Clifford Theory implies that $\lambda$ extends to $G_{\lambda}$ and a
canonical extension $\lambda^{e}$ is given as $\lambda^{e}(hn)=\lambda(n)$,
for all $h\in H_{\lambda}=G_{\lambda}\cap H$ and $n\in N$. Every character
$\Psi\in\operatorname{Irr}(H_{\lambda})$ defines a unique irreducible
character $\Psi\cdot\lambda^{e}$ of $G_{\lambda}$ lying above $\lambda$ and
inducing irreducibly on $G$. Distinct irreducible characters
$\Psi\in\operatorname{Irr}(H_{\lambda})$ define distinct irreducible
characters $(\Psi\cdot\lambda^{e})^{G}$ of $G$. In addition, every
$\chi\in\operatorname{Irr}(G)$ lies above some
$\lambda\in\operatorname{Irr}(N)$ and thus $\chi=(\Psi\cdot\lambda^{e})^{G}$,
for some $\Psi\in\operatorname{Irr}(H_{\lambda})$. Note that
$\chi(1)=\Psi(1)(|H|/|H_{\lambda}|)$.

The group $G$ acts on $\operatorname{Irr}(N)$ and divides its members into
conjugacy classes. (Observe that the $G$-classes of $\operatorname{Irr}(N)$
are also the $H$-conjugacy classes of $\operatorname{Irr}(N)$.) Let
$\Omega\subseteq\operatorname{Irr}(N)$ consisting of one representative from
every $G$-conjugacy class of irreducible characters of $N$. Then

$\operatorname{Irr}(G)=\cup_{\lambda\in\Omega}\\{(\Psi\lambda^{e})^{G}\mid\Psi\in\operatorname{Irr}(H_{\lambda})\\}.$

Hence if $N_{k}(G)=|\\{\chi\in\operatorname{Irr}(G)\mid\chi(1)=k\\}|$, for any
finite group $G$, and any $k=1,2\cdots$, then

$N_{k}(G)=\sum_{\lambda\in\Omega}N_{\frac{k}{|H:H_{\lambda}|}}(H_{\lambda})=\sum_{\lambda\in\Omega}N_{\frac{k}{|O_{\lambda}|}}(H_{\lambda})$

where $O_{\lambda}$ is the $H$-orbit of $\lambda$ in $\operatorname{Irr}(N)$.

Applying the above argument to the groups $U_{n}=M_{n,t}\rtimes H_{n,t}$ for
any arbitrary but fixed integer $n$ and any $t=1,\dots,n-1$, we conclude that

(3.3)
$N_{k}(U_{n})=\sum_{T\in\Omega_{n,t}}N_{\frac{k}{|H_{n,t}:H_{n,t,T}|}}(H_{n,t,T})=\sum_{T\in\Omega_{n,t}}N_{\frac{k}{|O_{T}|}}(H_{n,t,T}),$

where $\Omega_{n,t}$ is the set of quasimonomial matrices in
$\mathbf{F}^{s\times t}$, $O_{T}$ is the $H_{n,t}$-orbit of
$T\in\mathbf{F}^{s\times t}\cong\operatorname{Irr}(M_{n,t})$ and $H_{n,t,T}$
is the stabilizer of $T$ in $H_{n,t}\cong U_{s}\times U_{t}$.

Case 1: $t=1$. So $s=n-1$ and the groups $H_{n,1}$ and $M_{n,1}$ become
$U_{n-1}\times U_{1}\cong U_{n-1}$ and $\mathbf{F}^{1\times n-1}$
respectively. Furthermore,
$\operatorname{Irr}(M_{n,1})\cong\mathbf{F}^{n-1\times 1}$ and
$\Omega_{n,1}=\\{T\in\mathbf{F}^{n-1,1}\mid T\text{ quasimonomial}\\}$
consists of the matrices $T_{i}=fE_{i,1}$, for all $i=1,\dots,n-1$, and $f\neq
0\in\mathbf{F}$, along with the zero matrix. So we get $q-1$ matrices of type
$fE_{i,1}$. For any $n$ and any $i=1,\dots,n$ we define $P_{n,i}$ as

$P_{n,i}=\\{A\in U_{n}\mid C_{i}(A)\text{ is trivial}\\}.$

Then it is easy to check that $H_{n,1,T_{i}}=P_{n-1,i}$ while
$|O_{T_{i}}|=q^{i-1}$. Thus in view of equation 3.3 we get

(3.4)
$N_{k}(U_{n})=\sum_{T\in\Omega_{n,1}}N_{\frac{k}{|O_{T}|}}(H_{n,1,T})=(q-1)\sum_{i=1}^{n-1}N_{\frac{k}{q^{i-1}}}(P_{n-1,i})+N_{k}(U_{n-1}),$

where the last summand is the contribution of the zero matrix whose orbit size
is $1$ and the stabilizer group is $H_{n,1}\cong U_{n-1}$ itself. For
$k=q^{e}$, $e=0,1,\dots,\mu(n)$ the above equation, along with the fact that
$P_{n-1,1}=U_{n-1}$, implies

(3.5)
$N_{k}(U_{n})=qN_{k}(U_{n-1})+(q-1)\sum_{i=2}^{n-1}N_{\frac{k}{q^{i-1}}}(P_{n-1,i}).$

Observe that for $k=1$ equation (3.5) provides the well known formula
$N_{1}(U_{n})=qN_{1}(U_{n-1})$, for all $n\geq 2$.

Case 2: $t=2$ and thus $s=n-2$. (Assume $n\geq 4$ for the rest of the
section.) Now the groups $H_{n,2}$ and $M_{n,2}$ become $U_{n-2}\times
U_{2}\cong U_{n-2}\times\mathbf{F}$ and $\mathbf{F}^{2\times n-2}$
respectively. Furthermore,
$\operatorname{Irr}(M_{n,2})\cong\mathbf{F}^{n-2\times 2}$ and
$\Omega_{n,2}=\\{T\in\mathbf{F}^{n-2,2}\mid T\text{ quasimonomial}\\}$
consists of matrices whose length is either $1$ or $2$ along with the zero
matrix. In particular, the non-zero matrices in $\Omega_{n,2}$ are of the
following two types:
Those of length $1$, i.e. $T_{i,j}=fE_{i,j}$, $j=1,2$ and $i=1,\dots,n-2$,
while $f\neq 0\in\mathbf{F}$. For any fixed $i$ and $j$ we get $q-1$ such. If
$j=1$ then $T_{i,1}=fE_{i,1}$, for $i=1,\dots,n-2$. In this case it is left to
the reader to check that $|O_{T_{i,1}}|=q^{i}$ while
$H_{n,2,T_{i,1}}=\\{(A,B)\mid A\in U_{n-2},\,B\in U_{2}\text{ with $C_{i}(A)$
and $R_{1}(B)$ trivial }\\}$. Thus $H_{n,2,T_{i,1}}\cong P_{n-2,i}$.
If $j=2$ then $T_{i,2}=fE_{i,2}$, for some $i=1,\dots,n-2$. In this case
$|O_{T_{i,2}}|=q^{i-1}$ while $H_{n,2,T_{i,2}}=\\{(A,B)\mid A\in
U_{n-2},\,B\in U_{2}\text{ with $C_{i}(A)$ and $R_{2}(B)$ being trivial
}\\}\cong P_{n-2,i}\times\mathbf{F}$.

The second type are those of length $2$, i.e.,
$T_{i_{1},i_{2}}=f_{1}E_{i_{1},1}+f_{2}E_{i_{2},2}$ for some $i_{1}\neq i_{2}$
and $f_{1},f_{2}$ non-zero elements in $\mathbf{F}$. We get exactly
$(q-1)^{2}$ such distinct quasimonomial characters.
One can easily check that if $i_{1}>i_{2}$, then
$|O_{T_{i_{1},i_{2}}}|=q^{i_{1}+i_{2}-1}$, while the stabilizer of
$T_{i_{1},i_{2}}$ in $H_{n,2}$ equals

$H_{n,2,T_{i_{1},i_{2}}}=\\{(A,1)\mid A\in U_{n-2}\text{ with $C_{i_{1}}(A)$
and $C_{i_{2}}(A)$ being trivial}\\}\cong P_{n-2,i_{1}}\cap P_{n-2,i_{2}}.$

On the other hand if $i_{1}<i_{2}$, then
$|O_{T_{i_{1},i_{2}}}|=q^{i_{1}+i_{2}-2}$, while the stabilizer
$H_{n,2,T_{i_{1},i_{2}}}$ of $T_{i_{1},i_{2}}$ in $H_{n,2}=U_{n-2}\times
U_{2}$ consists of all matrices $(A,B)\in U_{n-2}\times U_{2}$ that satisfy
$a_{i_{1},i_{2}}=-f_{1}/f_{2}\cdot b_{1,2}$ while $C_{i_{1}}(A)$ is a trivial
column and $a_{x,i_{2}}=0$ for all $i_{1}\neq x=1,\dots,i_{2}-1$. For $1\leq
i_{1}<i_{2}\leq n$ we define

(3.6) $Q_{n,i_{1},i_{2}}=\\{A\in U_{n}\mid a_{y,i_{1}}=0=a_{x,i_{2}},\text{
for all $i_{1}\neq x=1,\dots,i_{2}-1$ and $y=1,\dots,i_{1}-1$}\\}.$

Then it is easy to see that $H_{n,2,T_{i_{1},i_{2}}}\cong
Q_{n-2,i_{1},i_{2}}$. Finally the zero matrix has orbit length $1$ and its
stabilizer in $H_{n,2}$ is $H_{n,2}\cong U_{n-2}\times\mathbf{F}$. Collecting
all the above and applying equation 3.3 along with equation (3.5) and the fact
that $N_{k}(M\times\mathbf{F})=|\mathbf{F}|\cdot N_{k}(M)=qN_{k}(M)$ for any
group $M$, we get

(3.7)
$N_{k}(U_{n})=qN_{k}(U_{n-1})+N_{\frac{k}{q}}(U_{n-1})-N_{\frac{k}{q}}(U_{n-2})+\\\
(q-1)^{2}\sum_{1\leq i_{2}<i_{1}\leq
n-2}N_{\frac{k}{q^{i_{1}+i_{2}-1}}}(P_{n-2,i_{1}}\cap P_{n-2,i_{2}})+\\\
(q-1)^{2}\sum_{1\leq i_{1}<i_{2}\leq
n-2}N_{\frac{k}{q^{i_{1}+i_{2}-2}}}(Q_{n-2,i_{1},i_{2}}).$

for all $n\geq 4$ and all $k$. Some of the summands above are easy to compute.
First observe that $P_{n-2,i}\cap P_{n-2,n-2}\cong P_{n-3,i}$ for all
$i=1,\dots,n-3$, and all $n\geq 5$. Thus (3.5) implies

$(q-1)^{2}\sum_{i=1}^{n-3}N_{\frac{k}{q^{n-3+i}}}(P_{n-2,i}\cap
P_{n-2,n-2})=(q-1)[N_{\frac{k}{q^{n-2}}}(U_{n-2})-N_{\frac{k}{q^{n-2}}}(U_{n-3})].$

In addition, $P_{n-2,i}\cap P_{n-2,1}=P_{n-2,i}$, for all $i=2,\dots,n-3$ and
all $n\geq 5$. Hence

$(q-1)^{2}\sum_{i=2}^{n-3}N_{\frac{k}{q^{i}}}(P_{n-2,i}\cap
P_{n-2,1})=(q-1)[N_{\frac{k}{q}}(U_{n-1})-qN_{\frac{k}{q}}(U_{n-2})-(q-1)N_{\frac{k}{q^{n-2}}}(U_{n-3})].$

Furthermore, for all $i=1,\dots,n-3$ and all $n\geq 5$, the group
$Q_{n-2,i,n-2}$ is isomorphic to $P_{n-3,i}\times\mathbf{F}$. This along with
(3.5) implies

(3.8)
$(q-1)^{2}\sum_{i=1}^{n-3}N_{\frac{k}{q^{n-4+i}}}(Q_{n-2,i,n-2})=q(q-1)[N_{\frac{k}{q^{n-3}}}(U_{n-2})-N_{\frac{k}{q^{n-3}}}(U_{n-3})].$

We finally observe that $Q_{n-2,1,2}=U_{n-2}$. Replacing all the above in
equation (3.7) we get

(3.9)
$N_{k}(U_{n})=qN_{k}(U_{n-1})+qN_{\frac{k}{q}}(U_{n-1})-qN_{\frac{k}{q}}(U_{n-2})+\\\
(q-1)[N_{\frac{k}{q^{n-2}}}(U_{n-2})-qN_{\frac{k}{q^{n-2}}}(U_{n-3})+qN_{\frac{k}{q^{n-3}}}(U_{n-2})-qN_{\frac{k}{q^{n-3}}}(U_{n-3})]+\\\
(q-1)^{2}\sum_{2\leq i_{2}<i_{1}\leq
n-3}N_{\frac{k}{q^{i_{1}+i_{2}-1}}}(P_{n-2,i_{1}}\cap P_{n-2,i_{2}})+\\\
(q-1)^{2}\sum_{1\leq i_{1}<i_{2}\leq n-3\text{ and
}(i_{1},i_{2})\neq(1,2)}N_{\frac{k}{q^{i_{1}+i_{2}-2}}}(Q_{n-2,i_{1},i_{2}}),$

for all $n\geq 5$ and all $k$. Note that in the equation above, the sum
$i_{1}+i_{2}$ is greater or equal to 5 when $i_{2}<i_{1}$, while
$i_{1}+i_{2}\geq 4$ when $i_{1}<i_{2}$.

##  4\.  Linear characters of $P_{n,i}$ and $Q_{n,i,j}$

The aim of this section is to compute the number of linear characters of
$P_{n,i}$ and $Q_{n,i,j}$. These groups are examples of  pattern groups , a
term introduced by M. Isaacs. We give here the basic definitions and
properties we need, for more details the reader could see [4].

Let $\mathcal{P}$ be a subset of the set of pairs $\\{(i,j)\mid 1\leq i<j\leq
n\\}$. $\mathcal{P}$ is called a closed pattern if it has the property that
$(i,k)\in\mathcal{P}$ whenever $(i,j),(j,k)\in\mathcal{P}$, for some
$j\in\\{i+1,\ldots,k-1\\}$. The set of unitriangular matrices $X\in U_{n}$
whose nonzero entries are restricted to lie at positions in the pattern
$\mathcal{P}$ is a subgroup of $U_{n}$ called a pattern group. If $G$ is a
pattern group corresponding to the closed pattern $\mathcal{P}$ with
$|\mathcal{P}|=k$, then $G$ is generated by the matrices $I_{n}+aE_{i,j}$,
$(i,j)\in\mathcal{P}$, $a\in\mathbf{F}^{*}$ and $|G|=|\mathbf{F}|^{k}$.

Direct computations show that
$[I_{n}+aE_{i,j},I_{n}+bE_{l,k}]=I_{n}+abE_{i,k}$ if $j=l$ and $I_{n}$
otherwise. A pair $(i,j)\in\mathcal{P}$ is called minimal if it is not
possible to find numbers $j_{1}<j_{2}<\ldots<j_{l},l\geq 1$, such that
$(i,j_{1}),(j_{1},j_{2}),\dots,(j_{l},k)\in\mathcal{P}$. Then $G^{\prime}$ is
the pattern group associated to
$\mathcal{P}_{0}=\\{(i,k)\in\mathcal{P}\mid(i,k)\text{ is not minimal}\\}$.
Thus $|G:G^{\prime}|=q^{t}$, where $t$ is the number of minimal pairs in
$\mathcal{P}$ (see Theorem 2.1 in [4]).

For the group $P_{n,i}$, $n\geq 3,i\leq n-1$ observe that there are $n-1$
minimal pairs: $(k,k+1),k\neq i-1,1\leq k\leq n-1$ and $(i-1,i+1)$. Therefore

(4.1) $N_{1}(P_{n,i})=q^{n-1}.$

For the group $Q_{n,i,i+1}$ with $2\leq i\leq n-2$ there are $n-1$ minimal
pairs: $(k,k+1),k\neq i-1,1\leq k\leq n-1$ and $(i-1,i+2)$. For the group
$Q_{n,i,j}$ with $1<i<j-1\leq n-1$, there are $n$ minimal pairs:
$(k,k+1),k\neq i-1,j-1,1\leq k\leq n-1$ and $(i-1,i+1),(i,j),(j-1,j+1)$.
Therefore

(4.2) $N_{1}(Q_{n,i,j})=\begin{cases}q^{n-1}\text{ if $i=j-1$ }\\\ q^{n}\text{
if $i<j-1$ }.\\\ \end{cases}$

##  5\.  Computing $N_{q}(P_{n,2})$

With the aid of $N_{1}(P_{n,i})$ and $N_{1}(Q_{n,i,j})$ we give the recursive
formulas for $N_{k}(U_{n})$ when $k=q$ and $k=q^{2}$ and compute
$N_{q}(P_{n,2})$. For $k=q$ and $n\geq 5$, equation (3.5), implies

(5.1)
$N_{q}(U_{n})=qN_{q}(U_{n-1})+(q-1)N_{1}(P_{n-1,2})=qN_{q}(U_{n-1})+q^{n-2}(q-1).$

It is straight forward to see that $N_{q}(U_{3})=q-1$ while
$N_{q}(U_{4})=q(q-1)(q+1)$. So the formula
$N_{q}(U_{n})=q^{n-3}(q-1)((n-3)q+1)$ for $N_{q}(U_{n})$ obtained by both
Marjoram [7] and Isaacs [4] satisfies (5.1).

For $k=q^{2}$ and $n=5$ equation (3.9) implies
$N_{q^{2}}(U_{5})=q(q-1)(2q^{2}+q-1)$. In addition, for all $n\geq 6$ we have

(5.2)
$N_{q^{2}}(U_{n})=qN_{q^{2}}(U_{n-1})+qN_{q}(U_{n-1})-qN_{q}(U_{n-2})+(q-1)^{2}N_{1}(Q_{n-2,1,3})=\\\
\ qN_{q^{2}}(U_{n-1})+q^{n-4}(q-1)[q^{3}+(n-5)q^{2}-(n-6)q-1].$

It is straight forward to check that the above recursive formula is satisfied
by

(5.3)
$N_{q^{2}}(U_{n})=q^{n-4}(q-1)\\{(n-5)q^{3}+(\frac{(n-5)(n-4)}{2}+2)q^{2}+[1-\frac{(n-6)(n-5)}{2}]q-n+4\\}.$

On the other hand equation (3.5) for $k=q^{2}$ and $n\geq 5$, implies

(5.4) $N_{q^{2}}(U_{n})=qN_{q^{2}}(U_{n-1})+(q-1)[q^{n-2}+N_{q}(P_{n-1,2})].$

Combining the above with (5.2) we get

(5.5)
$N_{q}(P_{4,2})=\frac{1}{q-1}(N_{q^{2}}(U_{5})-qN_{q^{2}}(U_{4}))-q^{3}=q(q^{2}-1),$

while for $n\geq 6$

(5.6) $N_{q}(P_{n-1,2})=q^{n-4}(q-1)[q^{2}+(n-5)q+1].$

##  6\. The group $Q_{n,1,3}$.

The aim in this section is to compute $N_{q}(Q_{n,1,3})$, for all $n\geq 4$.
We point out that we are not able to compute the number of irreducible
characters of degree $q$ for every group $Q_{n,i,j}$ where $i,$ and $j$ are
arbitrary. But we can do it for the group $Q_{n,1,3}$, and this is enough for
the computation of $N_{q^{3}}(U_{n})$.

Assume that $n\geq 4$. Note that, according to its definition, $Q_{n,1,3}$
consists of all $n\times n$ unitriangular matrices whose $(2,3)$-entry is
zero. We write $Q_{n,1,3}$ as a semidirect product using the following groups.
Let $M$ be the subgroup of $Q_{n,1,3}$ consisting of matrices all of whose
non-diagonal elements are zero except for the first row. Assume further that
$H$ is the subgroup of $Q_{n,1,3}$ consisting of matrices whose non-diagonal
entries in the first row are zero. Then it is clear that $M$ is an abelian
normal subgroup of $Q_{n,1,3}$ isomorphic to $\mathbf{F}^{1\times
n-1}\cong\mathbf{F}^{n-1}$. Observe that $H$ is isomorphic to $P_{n-1,2}$.
Furthermore, $Q_{n,1,3}=M\rtimes H$ and the conjugation action of $H$ on $M$
is given as

$\left(\begin{matrix}1&0\\\
0&X^{-1}\end{matrix}\right)\left(\begin{matrix}1&C\\\
0&I_{n-1}\end{matrix}\right)\left(\begin{matrix}1&0\\\
0&X\end{matrix}\right)=\left(\begin{matrix}1&CX\\\
0&I_{n-1}\end{matrix}\right),$

where $X\in P_{n-1,2}$ and $C\in\mathbf{F}^{1\times n-1}$.

Now we apply Proposition 1 to the group $M=\mathbf{F}^{1\times n-1}$ (with $M$
in the place of $M_{n,t}$ for $t=1$). So the group of irreducible characters
$\operatorname{Irr}(M)$ of $M$ is isomorphic to the abelian additive group
$\mathbf{F}^{n-1\times 1}$. Thus we regard the irreducible characters of $M$
as column vectors over $\mathbf{F}$, and for every
$\chi\in\operatorname{Irr}(M)$ we write
$\chi=(\chi_{1},\ldots,\chi_{n-1})^{t}$ with $\chi_{i}\in\mathbf{F}$. Under
the isomorphism between $\operatorname{Irr}(M)$ and $\mathbf{F}^{n-1\times 1}$
the action of an element $\left(\begin{matrix}1&0\\\ 0&X\end{matrix}\right)$
becomes multiplication on the left by $X^{-1}$. It is straightforward to see
that the $H$-invariant irreducible characters of $M$ are those with
$\chi_{3}=\chi_{4}=\ldots=\chi_{n-1}=0$, and thus they look like
$(\chi_{1},\chi_{2},0,\ldots,0)^{t}$ with $\chi_{1},\chi_{2}\in\mathbf{F}$.
Hence we get $q^{2}$ such irreducible characters.

Furthermore, if $\chi=(\chi_{1},\ldots,\chi_{n-1})^{t}\neq(0,\ldots,0)^{t}$ is
any character in $\operatorname{Irr}(M)$, and $k$ is the biggest index with
$\chi_{k}\neq 0$, then if $k=1,2$ the character $\chi$ is $H$-invariant ,
while if $k\geq 3$ the $H$-orbit of $\chi$ contains all the characters of type
$(f_{1},\ldots,f_{k-1},\chi_{k},0,\ldots,0)^{t}$, where $f_{i}\in\mathbf{F}$
are arbitrary. Hence we get orbits of length $q^{k-1}$. Therefore for any
$\chi\in\operatorname{Irr}(M)$ either $\chi$ is $H$-invariant or its
stabilizer $H_{\chi}$ in $H$ has index at least $q^{2}$. That is, there are no
irreducible characters in $\operatorname{Irr}(M)$ whose stabilizer in $H$ has
index $q$ in $H$.

Now we follow the argument after equation (3.2), for the group
$Q_{n,1,3}=M\rtimes H$, to get $N_{q}(Q_{n,1,3})=q^{2}\cdot N_{q}(P_{n-1,2})$,
for all $n\geq 4$. If $n=4$ then $P_{3,2}\cong\mathbf{F}^{2}$ and thus

(6.1) $N_{q}(P_{3,2})=N_{q}(Q_{4,1,3})=0.$

If $n=5$ then in view of (5.5) we get

(6.2) $N_{q}(Q_{5,1,3})=q^{3}(q^{2}-1)$

In addition, for all $n\geq 6$, we use (5.6) to get

(6.3) $N_{q}(Q_{n,1,3})=q^{n-2}(q-1)[q^{2}+(n-5)q+1].$

##  7\. Computing $N_{q^{3}}(U_{n})$.

For $n=5$, equation (3.9) implies that $N_{q^{3}}(U_{5})=q(q-1)(2q-1)$.
Furthermore, when $k=q^{3}$ and $n=6$ equation (3.9) along with (6.1) and
(4.2) implies

$N_{q^{3}}(U_{6})=q^{2}(q-1)(4q^{2}+q-3).$

For the case $n=7$ we similarly get

(7.1) $N_{q^{3}}(U_{7})=q^{2}(q-1)[3q^{4}+6q^{3}-2q^{2}-5q+1].$

In general, for all $n\geq 8$ equation (3.9) implies

(7.2)
$N_{q^{3}}(U_{n})=qN_{q^{3}}(U_{n-1})+qN_{q^{2}}(U_{n-1})-qN_{q^{2}}(U_{n-2})+\\\
(q-1)^{2}[N_{q}(Q_{n-2,1,3})+N_{1}(Q_{n-2,2,3})+N_{1}(Q_{n-2,1,4})].$

According to (5.3), for all $n\geq 8$ we get

(7.3)
$N_{q^{2}}(U_{n-1})-N_{q^{2}}(U_{n-2})=q^{n-6}(q-1)\\{(n-6)q^{4}+[\frac{(n-6)(n-5)}{2}-(n-7)+2]q^{3}-\\\
[(n-7)(n-6)+1]q^{2}+[4-n+\frac{(n-8)(n-7)}{2}]q+n-6\\}$

Furthermore, using (4.2) and (6.3) along with (7.3) in equation (7.2) and we
get

(7.4)
$N_{q^{3}}(U_{n})=qN_{q^{3}}(U_{n-1})+q^{n-5}(q-1)\\{q^{5}+(2n-14)q^{4}+[25-3n+\frac{(n-6)(n-5)}{2}]q^{3}+\\\
[n-11-(n-7)(n-6)]q^{2}+[5-n+\frac{(n-8)(n-7)}{2}]q+n-6\\},$

for all $n\geq 8$. As we have already computed the formula for
$N_{q^{3}}(U_{7})$, we can easily check that the following equation satisfies
the recursive formula (7.4) for all $n\geq 8$.

(7.5)
${}N_{q^{3}}(U_{n})=q^{n-5}(q-1)\\{A_{n}q^{5}+B_{n}q^{4}+C_{n}q^{3}+D_{n}q^{2}+E_{n}q+F_{n}\\},$

where

  * •

$A_{n}=n-7$

  * •

$B_{n}=3+(n-7)(n-6)$

  * •

$C_{n}=40(n-7)-\frac{17}{4}(n+8)(n-7)+\frac{1}{12}n(n+1)(2n+1)-64$

  * •

$D_{n}=(n-7)(7n+3)-\frac{1}{6}n(n+1)(2n+1)+138$

  * •

$E_{n}=(n-7)(-\frac{17}{4}n-1)+\frac{1}{12}n(n+1)(2n+1)-75$

  * •

$F_{n}=1+\frac{(n-7)(n-4)}{2}$.

It is clear that the polynomials $A_{n},B_{n}$ and $F_{n}$ in $n$ are integer
valued for every $n$. To show that the same holds for the polynomials
$C_{n},D_{n}$ and $E_{n}$ we make use of the following lemma.

######  Lemma 1.

Let $P(n)$ be a polynomial in $n$ of degree $m$ with rational coefficients. If
$P(n)$ is an integer for $m+1$ consecutive integers, then the polynomial is
integer valued.

###### Proof.

We will use induction on the degree $m$ of $P(n)$. It is clear that for $m=1$
holds.

Assume it holds for all polynomials of degree less that $m$, we will show that
it also holds for those of degree $m$. The polynomial $Q(n):=P(n+1)-P(n)$ has
degree smaller than $m$. In addition, if $P$ has integer values for $m+1$
consecutive integers $k,k+1,\dots,k+m$, then $Q(n)$ is integer valued for the
$m$ consecutive integers $k,k+1,\dots,k+m-1$. Therefore the inductive
hypothesis implies that $Q(n)$ is integer valued for every $n$. This along
with the fact that $P(n)$ is integer valued for $n=k+m$, implies that $P(n)$
is an integer for every $n$. ∎

Now, it is straight forward to check that $C_{7},C_{8},C_{9}$ and $C_{10}$ are
integers. Hence the above lemma implies that $C_{n}$ is an integer valued
polynomial. Similarly we show that $D_{n}$ and $E_{n}$ are integer valued.
Hence $N_{q^{3}}(U_{n})$ is a polynomial in $q$ with integer coefficients.

## References

  * [1] G. Higman, Enumerating $p$-groups. I. Inequalities, Proc. London Math. Soc. (3) 10 (1960), 24–30.
  * [2] B. Huppert, Character Theory of Finite Groups, Walter de Gruyter, Berlin, 1998.
  * [3] I.M. Isaacs, Character Theory of Finite Groups, Dover, New York, 1994.
  * [4] I.M. Isaacs, Counting characters of upper triangular groups, J. of Algebra, 315 (2007), 698-719.
  * [5] I.M. Isaacs, Characters of groups associated with finite algebras, J. of Algebra, 177 (1995), 708–730.
  * [6] G.I. Lehrer, Discrete series and unipotent subgroup, Compositio Math. 28 (1974), 9–19.
  * [7] M. Marjoram, Irreducible characters of small degree of the unitriangular group, Irish Math.Soc. Bull. 42 (1999), 21–31.
  * [8] M Marjoram, Irreducible characters of Sylow $p$-subgroups of classical groups, PH.D. Thesis, (1997), National University of Ireland, Dublin.
  * [9] A. Vera-López, J.M. Arregi, Conjugacy classes in Sylow p-subgroups of $Gl(n,q)$, J. of Algebra, 152 (1992), 1–19.
  * [10] A. Vera-López, J.M. Arregi, Some algorithms for the calculation of conjugacy classes in the Sylow p-subgroups of $Gl(n,q)$, J. of Algebra, 177 (1995), 889–925.
  * [11] A. Vera-López, J.M. Arregi, Polynomial properties in unitriangular matrices, J. of Algebra, 244 (2001), 343–351.