\documentclass[ALCO, Unicode]{cedram}
\usepackage[utf8]{inputenc}

\usepackage{amsmath,amsthm,amsfonts,amssymb}
\usepackage{graphicx,url}





\title{A polynomial construction of perfect sequence covering arrays}
\author[\initial{A.} \middlename{R.} Gentle]{\firstname{Aidan} \middlename{R.} \lastname{Gentle}}
\address{ School of Mathematics\\
Monash University\\
Vic 3800, Australia}
\email{aidan.gentle@monash.edu}

\keywords{sequence covering array, permutation representation, exact covering, projective geometry}

\subjclass{05B30, 05B40, 20B25, 51E20}






\begin{document}


\begin{abstract}
  A PSCA$(v, t, \lambda)$ is a multiset of permutations of the
  $v$-element alphabet $\{0, \dots, v-1\}$ such that every sequence of
  $t$ distinct elements of the alphabet appears in the specified order
  in exactly $\lambda$ permutations. For $v \geqslant t$,
  let $g(v, t)$ be the smallest positive integer $\lambda$ such
  that a PSCA$(v, t, \lambda)$ exists. Kuperberg, Lovett and Peled proved
  $g(v,t) = O(v^{t})$ using probabilistic methods. We present an explicit
  construction that proves $g(v,t) = O(v^{t(t-2)})$ for fixed $t \geqslant 4$.
  The method of construction involves taking a permutation representation
  of the group of projectivities of a suitable projective space of dimension
  $t - 2$ and deleting all but a certain number of symbols from each
  permutation. In the case that this space is a Desarguesian projective
  plane, we also show that there exists a permutation representation of the
  group of projectivities of the plane that covers the vast majority of 
  4-sequences of its points the same number of times.
\end{abstract}

\maketitle



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

For positive integers $v$ and $t$ with $v \geqslant t$, let $[v] = \{ 0, \dots, v-1 \}$, $\mathcal{S}_{v}$ be the group of permutations of $[v]$, and $\mathcal{S}_{v, t}$ be the set of ordered sequences of $t$ distinct elements of $[v]$. Unless stated otherwise, permutations are assumed to be written in one-line notation with $\pi \in \mathcal{S}_{v}$ being denoted by $( \pi(0), \pi(1), \dots, \pi(v-1))$. Additionally, the elements of a sequence $s \in \mathcal{S}_{v,t}$ are denoted by $(s_{1}, \dots, s_{t})$. For $\pi \in \mathcal{S}_{v}$ and $s \in \mathcal{S}_{v, t}$ we say that $\pi$ \emph{covers} $s$ if $\pi^{-1}(s_{i}) < \pi^{-1}(s_{i + 1})$ for $i \in \{1, \dots, t-1\}$. Several aspects of sequence covering have been studied including the problems of finding packings, coverings and perfect coverings of sequences. In this context, a packing is a set of permutations in $\mathcal{S}_{v}$ such that every sequence in $\mathcal{S}_{v,t}$ is covered by at most one permutation. In coding theory, these sets are referred to as \textit{ $(v-t)$-deletion correcting codes} \cite{Kle04, Lev91}. A covering of sequences is a set of permutations in $\mathcal{S}_{v}$ such that every sequence in $\mathcal{S}_{v,t}$ is covered by at least one permutation. These sets are referred to as \textit{sequence covering arrays} and were first studied by Spencer \cite{Spen71} as an extension of a problem studied by Dushnik \cite{Dush50} relating to the dimension of certain partial orders. More recently, sequence covering arrays have been investigated for their applications in event sequence testing \cite{Kuhn12}. 

In this paper, we are concerned with the problem of perfect coverings of sequences. A \emph{perfect sequence covering array} with order $v$, strength $t$ and multiplicity $\lambda$, denoted by PSCA$(v, t, \lambda)$, is a multiset $X$ of permutations in $\mathcal{S}_{v}$ such that every sequence in $\mathcal{S}_{v, t}$ is covered by exactly $\lambda$ permutations in $X$. If $T$ is a $t$-subset of $[v]$, then there are $t!$ ways of arranging the elements of $T$, each of which forms a sequence in $\mathcal{S}_{v,t}$ that must be covered by $\lambda$ permutations in a PSCA$(v, t, \lambda)$. Furthermore, every permutation in a PSCA$(v, t, \lambda)$ covers exactly one of these sequences, so a PSCA$(v, t, \lambda)$ must contain $t!\lambda$ permutations.

For $v \geqslant t$, let $g(v, t)$ be the smallest positive integer $\lambda$ such that a PSCA$(v, t, \lambda)$ exists. Observe that $\mathcal{S}_{v}$ is a PSCA$(v, t, v!/t!)$, so $g(v, t)$ is well defined and $g(v, t) \leqslant v!/t!$. Much of the research into perfect sequence covering arrays has focussed on determining or bounding $g(v,t)$. By writing a permutation in $\mathcal{S}_{v}$ in one-line notation, we can form a permutation in $\mathcal{S}_{v-1}$ by removing the symbol $v-1$ from the initial permutation and shifting each symbol that appeared to the right of $v-1$ one position to the left. If $v > t$ and we perform this symbol deletion to each permutation of a PSCA$(v, t, \lambda)$, then we obtain a PSCA$(v-1, t, \lambda)$. Hence, $g(v, t) \geqslant g(v-1, t)$. For $2 \leqslant t' \leqslant t$, a PSCA$(v, t, \lambda)$ is also a PSCA$(v, t', \lambda \binom{t}{t'})$, so $g(v, t') \leqslant \binom{t}{t'}g(v, t)$.

In this paper, we present an explicit construction of a PSCA$(v,t,\lambda)$ for all $v \geqslant t \geqslant 4$. The method of this construction involves taking a suitable permutation representation of the group $\textup{PGL}(t-1,q)$ of projectivities of the projective space $\textup{PG}(t-2,q)$. We show that in such a permutation representation, there is a subset of $q+1$ symbols such that any $t$-sequence of symbols from this subset is covered by $\lambda$ permutations for a given constant $\lambda$. Hence, deleting all but the symbols in this subset forms a PSCA$(q+1,t,\lambda)$. This construction yields the following upper bound on $g(v,t)$.
\begin{theo}\label{t:upperbound}
For $v \geqslant t \geqslant 4$,
\begin{equation*}
g(v, t) <  \frac{(2v)^{(t-1)^{2}}}{t!(2v - 1)}.
\end{equation*}
\end{theo}

This bound is derived through purely constructive means however, a probabilistic upper bound does exist. A \textit{$t$-wise uniform set of permutations} is a set $T \subseteq \mathcal{S}_{v}$ such that for any $a,b \in \mathcal{S}_{v,t}$,
\begin{equation*}
\frac{1}{\vert T \vert} \vert \{ \pi \in T : \pi(a_{i}) = b_{i}, 1\leqslant i \leqslant t\} \vert = \frac{t!}{v!}.
\end{equation*}
A $t$-wise uniform set of permutations $T \subseteq \mathcal{S}_{v}$ is also a PSCA$(v,t,\vert T \vert/t!)$. Kuperberg, Lovett and Peled \cite{Kup17} proved that for any $t \leqslant v$, there is a $t$-wise uniform set of permutations $T \subseteq \mathcal{S}_{v}$ with $\vert T \vert \leqslant (cv)^{ct}$ for some universal constant $c > 0$. Although this result gives a tighter bound on $g(v,t)$ than Theorem \ref{t:upperbound}, it is not yet known how to efficiently construct either a PSCA or a $t$-wise uniform set of permutations with this size. 

Recently, Iurlano \cite{Iur22} has established an equivalence between PSCAs of strength $t$ and families of \textit{$t$-rankwise independent permutations}. Iurlano also uses a construction of Itoh, Takei and Tarui \cite{ITT00} of $t$-rankwise independent permutations to build PSCAs with $v^{O(t^{2}/\textup{ln }t)}$ permutations.

Our construction can also be applied when $t = 3$. However, an infinite family of PSCA$(v,3,\lambda)$ built by Yuster \cite{Yus19} established that $g(v,3) \leqslant cv(\log v)^{\log 7}$ for an absolute constant $c$. This result provides a tighter bound on $g(v,3)$ than Theorem \ref{t:upperbound} would, were it to be extended to the $t=3$ case.

In proving Theorem \ref{t:upperbound}, we show that sequences of $t$ points of $\textup{PG}(t-2,q)$ belonging to a particular family are covered by a constant number of permutations in a representation of $\textup{PGL}(t-1,q)$. In the $t=4$ case, we can choose a particular representation of $\textup{PGL}(3,q)$ to ensure that sequences of four points of $\textup{PG}(2,q)$ belonging to a separate family are also covered by the same constant number of permutations. Although accounting for this new family of sequences does not provide a substantial improvement to the bound $g(v,4) = O(v^{8})$ implied by Theorem \ref{t:upperbound}, it does prove the following theorem.

\begin{theo}\label{t:collineationgroup}
Let $q$ be a prime power and let $r = q^{2} + q + 1$. Then there is a permutation representation $\Psi \leqslant \mathcal{S}_{r}$ of $\textup{PGL}(3,q)$ such that the number of sequences in $\mathcal{S}_{r,4}$ that are covered by exactly $\vert \Psi \vert/4!$ permutations in $G$ is greater than
\begin{equation*}
\left( 1 - \frac{1}{q} \right) \vert \mathcal{S}_{r,4} \vert.
\end{equation*}
\end{theo}

In building a PSCA$(v,4,\lambda)$, we take a prime power $q$ such that $q \geqslant v$, find a suitable permutation representation of $\textup{PGL}(3,q)$ in $\mathcal{S}_{q^{2} + q + 1}$ and then delete all but $v$ symbols from each permutation in this group. As a consequence of this symbol deletion, the number of permutations in the resulting PSCA on $v$ symbols is approximately $v^{8}$. Theorem \ref{t:collineationgroup} implies that it is possible to find a set of permutations in $\mathcal{S}_{v}$ with size approximately $v^{4}$ such that the vast majority of 4-sequences are covered by a constant number of permutations. This reduced size is much closer to the lower bound proved by Yuster \cite{Yus19}, which says that $g(v,4) \geqslant v(v-3)/48$. However, as the permutation representation presented in Theorem \ref{t:collineationgroup} may or may not be a PSCA, it is still unclear what the asymptotic behaviour of $g(v,4)$ should be.

In addition to the asymptotic results cited above, research in this area has uncovered exact values of $g(v,t)$ \cite{GeWa22, Lev91, Math99, Njl22, Yus19} as well as the non-existence of a PSCA$(v,t,\lambda)$ \cite{Chee13, GeWa22, Kle04, Math99} for certain choices of $v$, $t$ and $\lambda$.

The paper is organised as follows. In Section~\ref{s:generous}, we introduce notation and some basic ideas that lay the groundwork for the constructions in the subsequent sections. In Section~\ref{s:collineation}, we prove Theorem \ref{t:upperbound}. In Section~\ref{s:almost}, we prove Theorem \ref{t:collineationgroup}.
















\section{Preliminaries}\label{s:generous}

We begin by recalling some definitions regarding group actions. For a set $X$, let $\text{Sym}(X)$ denote the group of permutations of $X$. Note that when $X = [v]$, $\text{Sym}(X) = \mathcal{S}_{v}$. An \emph{action} of a group $G$ on $X$ is a homomorphism $\phi: G \rightarrow \text{Sym}(X)$. For $g \in G$ and $x \in X$, we use $gx$ to refer to the image of $x$ under the permutation $\phi(g)$. The \textit{orbit} of $x$ is the set $\textup{Orb}(x) \coloneqq  \{ gx : g \in G \}$. The \textit{stabiliser} of $x$ is the set $\textup{Stab}(x) \coloneqq  \{ g \in G : gx = x \}$. The stabiliser of $x$ forms a subgroup of $G$. In what follows, we make use of the Orbit-Stabiliser Theorem.

\begin{theo}
If $G$ is a group acting on $X$, then for any $x \in X$, 
\begin{equation*}
\vert \textup{Orb}(x) \vert \vert \textup{Stab}(x) \vert = \vert G \vert.
\end{equation*}
\end{theo}


A permutation group $G \leqslant \mathcal{S}_{v}$ has the following natural action on $\mathcal{S}_{v,t}$. If $g \in G$ and $s \in \mathcal{S}_{v,t}$, then $gs = (g(s_{1}), \dots, g(s_{t}))$. Consider an array $\textsf{A}$ with columns indexed by $[v]$ and rows indexed by the elements of $G$ where $\textsf{A}[g,i] = g(i)$. Let $s \in \mathcal{S}_{v,t}$ and consider the corresponding sequence of columns of \textsf{A}. In row $g$ and in columns $(s_{1}, \dots, s_{t})$ of \textsf{A}, we find the sequence $(g(s_{1}), \dots, g(s_{t})) = gs$. So the sequences that appear in the columns $(s_{1}, \dots, s_{t})$ of \textsf{A} are exactly those in $\textup{Orb}(s)$. For $x \in \textup{Orb}(s)$, the set of rows of \textsf{A} in which the sequence $x$ appears in the columns $(s_{1}, \dots, s_{t})$ is $\{ g : gs = x \}$. This set is a coset of $\textup{Stab}(s)$ so it must have the same size as $\textup{Stab}(s)$. The permutation $g$ covers $gs$ if and only if $s_{1} < \dots < s_{t}$. Define $\textup{Asc}(s) \coloneqq  \{ x \in \textup{Orb}(s) : x_{1} < \dots < x_{t} \}$. We now have the following lemma.
\begin{lemm}\label{l:ascstab}
If $G \leqslant \mathcal{S}_{v}$ is a permutation group and $s \in \mathcal{S}_{v, t}$, then the number of permutations in $G$ that cover $s$ is $\vert \textup{Asc}(s) \vert \vert \textup{Stab}(s) \vert$.

\end{lemm} 

To conclude this section, we consider deleting symbols from permutations. For $\pi \in \mathcal{S}_{v}$ and $j \in [v]$, we define $\pi_{[j]}$ to be the permutation in $\mathcal{S}_{j}$ obtained by deleting the symbols $\{j, j+1, \dots, v-1\}$ from $\pi$. The permutation $\pi_{[j]}$ covers a sequence $s \in \mathcal{S}_{j, t}$ if and only if $\pi$ also covers $s$. If $X$ is a multiset of permutations in $\mathcal{S}_{v}$, then for $j \in [v]$, we define $X_{[j]}$ to be the multiset $\{ \pi_{[j]} : \pi \in X\}$. Then, for any sequence $s \in \mathcal{S}_{j,t}$, the number of permutations in $X_{[j]}$ that cover $s$ is equal to the number of permutations in $X$ that cover $s$. In the next section we construct a PSCA of strength $t$ by deleting symbols from a suitable multiset of permutations.






\section{Collineations of projective spaces} \label{s:collineation}




In this section we prove Theorem \ref{t:upperbound}. We begin by introducing some definitions regarding projective spaces. Let $q = p^{m}$ for some prime $p$ and for some integer $m \geqslant 1$ and let $\textrm{GF}(q)$ be the field with $q$ elements. Now let $n \geqslant 2$ and let $V$ be an $(n+1)$-dimensional vector space over $\textrm{GF}(q)$. Then the \textit{$n$-dimensional projective space} over $\textrm{GF}(q)$, denoted by $\textrm{PG}(n,q)$ is the set of all 1-dimensional subspaces of $V$. The elements of $\textrm{PG}(n,q)$ are called \textit{points}. If $W$ is a subspace of $V$, then $W$ forms a set of points in $\textrm{PG}(n,q)$ with $W$ containing the point $X$ if $X$ is a subspace of $W$. A 2-dimensional subspace of $V$ forms a \textit{line} in $\textrm{PG}(n,q)$ and an $n$-dimensional subspace of $V$ forms a \textit{hyperplane} in $\textrm{PG}(n,q)$. A \textit{collineation} of $\textrm{PG}(n,q)$ is a permutation of the points of $\textrm{PG}(n,q)$ that maps lines to lines. Let $A \in \textrm{GL}(n+1,q)$ be a non-singular matrix and suppose that $Au = v$ for vectors $u \in X$ and $v \in Y$ where $X$ and $Y$ are points in $\textrm{PG}(n,q)$. Then $A(cu) = cv$ for $c \in \textrm{GF}(q)$. Thus, every vector in $X$ is mapped by $A$ to a vector in $Y$. Hence, $A$ induces a permutation of the points of $\textrm{PG}(n,q)$. Permutations formed in this way are called \textit{projectivities}. The set of all projectivities of $\textrm{PG}(n,q)$ forms the group $\textrm{PGL}(n+1,q)$. A \textit{frame} of $\textrm{PG}(n,q)$ is an ordered sequence of $n + 2$ points in $\textrm{PG}(n,q)$ such that no $n+1$ of these points lie in the same hyperplane of $\textrm{PG}(n,q)$. The following theorem is a statement of the Fundamental Theorem of Projective Geometry (see e.g. \cite{Hir79}).

\begin{theo}\label{t:fundamental}
For any two frames in $\textup{PG}(n,q)$, there is a unique projectivity of $\textup{PG}(n,q)$ mapping one frame to the other.
\end{theo}

Let $r$ be the number of points in $\textrm{PG}(n,q)$. Projectivities are defined as permutations of the points of $\textrm{PG}(n,q)$ but we can view projectivities as permutations of $[r]$ by labelling the points of $\textrm{PG}(n,q)$. For a bijection $\psi: \textrm{PG}(n,q) \rightarrow [r]$ and a projectivity $f$, define $f_{\psi} \in \mathcal{S}_{r}$ by $f_{\psi}(i) = \psi(f(\psi^{-1}(i)))$. Then let $\Psi \coloneqq  \{ f_{\psi} : f \in \textrm{PGL}(n+1,q) \}$. Note $\Psi$ is a permutation subgroup of $\mathcal{S}_{r}$. The order of $\Psi$ is given by
\begin{equation*}
\vert \Psi \vert = \vert \textrm{PGL}(n+1,q)\vert = \frac{\prod_{i=0}^{n} (q^{n+1} - q^{i})}{q-1}.
\end{equation*}
By establishing the bijection $\psi$, points of $\textrm{PG}(n,q)$ are associated with elements of $[r]$ and so we can treat lines and hyperplanes as subsets of $[r]$ and frames as sequences in $\mathcal{S}_{r,n+2}$.


\begin{lemm}\label{l:framecover}
For a bijection $\psi: \textup{PG}(n,q) \rightarrow [r]$ and a frame $s \in \mathcal{S}_{r,n+2}$, the number of permutations in $\Psi$ that cover $s$ is $\vert \Psi \vert / (n+2)!$. 
\end{lemm}

\begin{proof}
By Theorem \ref{t:fundamental}, every frame in $\mathcal{S}_{r,n+2}$ is part of the same orbit under the action of $\Psi$. For any frame $s \in \mathcal{S}_{r,n+2}$, any reordering of the points of $s$ will form another frame. Of all the $(n+2)!$ ways of ordering the points of $s$, only one of these sequences is in ascending order. Thus, $\vert \textup{Asc}(s) \vert = \vert \textup{Orb}(s) \vert/(n+2)!$. Therefore, by Lemma \ref{l:ascstab}, the number of permutations in $\Psi$ that cover $s$ is
\begin{equation*}
\vert \textup{Stab}(s) \vert \vert \textup{Asc}(s) \vert = \frac{\vert \textup{Stab}(s) \vert \vert \textup{Orb}(s) \vert}{(n+2)!} = \frac{\vert \Psi \vert}{(n+2)!}. \qedhere
\end{equation*}
\end{proof}

A \textit{$k$-arc} in $\textrm{PG}(n,q)$ is a set of $k$ points in $\textrm{PG}(n,q)$, no $n+1$ of which lie in a hyperplane of $\textrm{PG}(n,q)$. 

\begin{theo}[e.g.~\cite{Ball19}]\label{t:arcsize}
For $q \geqslant n$, there exists a $(q+1)$-arc in $\textup{PG}(n,q)$.
\end{theo}

\begin{lemm}\label{l:construction}
For $q \geqslant n+1$, if $\psi: \textup{PG}(n,q) \rightarrow [r]$ is a bijection such that $\{ \psi^{-1}(i) : i \in [q+1] \}$ is a $(q+1)$-arc, then $\Psi_{[q+1]}$ is a $\textup{PSCA}(q+1, n+2, \vert \Psi \vert/(n+2)!)$.
\end{lemm}

\begin{proof}
Let $s \in \mathcal{S}_{q+1, n+2}$ and let $\psi$ be as defined in the lemma statement. Then $s$ is a frame. Thus, by Lemma \ref{l:framecover}, $s$ is covered by $\vert \Psi \vert/(n+2)!$ permutations in $\Psi$. Hence, $s$ is covered by $\vert \Psi \vert/(n+2)!$ permutations in $\Psi_{[q+1]}$. Therefore, $\Psi_{[q+1]}$ is a PSCA$(q+1, n+2, \vert \Psi \vert/(n+2)!)$.
\end{proof}

Note that for $q \geqslant n+1$, Theorem \ref{t:arcsize} guarantees the existence of a bijection $\psi$ satisfying the condition of Lemma \ref{l:construction}. We are now ready to prove Theorem \ref{t:upperbound}

\begin{proof}[Proof of Theorem \ref{t:upperbound}]
Let $q$ be the smallest power of 2 such that $q \geqslant v$. Then $q < 2v$. Let $n = t - 2$. Then, by Lemma \ref{l:construction},
\begin{equation*}
g(v,t) \leqslant \frac{\vert \textrm{PGL}(n+1,q) \vert}{(n+2)!} < \frac{\vert \textrm{PGL}(t-1,2v) \vert}{t!} = \frac{\prod_{i=0}^{t-2}((2v)^{t-1} - (2v)^{i})}{t!(2v - 1)} < \frac{(2v)^{(t-1)^{2}}}{t!(2v - 1)}. \qedhere
\end{equation*}
\end{proof}




\section{Almost perfect 4-sequence covering arrays}\label{s:almost}

We now focus specifically on the case where $n=2$. That is, we consider sequences of four points in $\textrm{PG}(2,q)$. In the previous section, we present a construction of a PSCA$(v,4,\lambda)$ with $O(v^{8})$ permutations. In this section, we adjust this construction such that the size of the new construction is $O(v^{4})$. In this new construction we can guarantee that almost all sequences are covered by the same number of permutations (see Theorem \ref{t:collineationgroup}). This shows that we can greatly reduce the size of the construction in Section~\ref{s:collineation} when $t=4$ while still ensuring that most sequences are covered by the same number of permutations. 

The sequences now under consideration are those containing four points of $\textup{PG}(2,q)$. These sequences can be divided into three families. The first family contains all sequences of four points such that no three are collinear. As hyperplanes and lines are the same in $\textup{PG}(2,q)$, these sequences are frames. By Lemma \ref{l:framecover}, in any permutation representation $\Psi \leqslant \mathcal{S}_{r}$ of $\textrm{PGL}(3,q)$ as defined in Section~\ref{s:collineation}, any frame is covered by $\vert \Psi \vert/24$ permutations. The second family contains all sequences with three collinear points but not four. The third family contains all sequences of four collinear points. 

Let $r = q^{2} + q + 1$ be the number of points in $\textrm{PG}(2,q)$. A \textit{difference set} of $\mathbb{Z}_{r}$ is a set $A = \{ a_{0}, a_{1}, \dots, a_{q} \} \subset \mathbb{Z}_{r}$ such that for any non-zero element $x \in \mathbb{Z}_{r}$, there are $i$ and $j$ such that $a_{i} - a_{j} = x$. For any prime power $q$, it is possible to label the points of $\textrm{PG}(2,q)$ such that the labelled lineset has the form $\{ \{ a_{i} + j : i \in [q+1] \} : j \in \mathbb{Z}_{r} \}$, where $A = \{a_{0}, \dots, a_{q}\}$ is a difference set of $\mathbb{Z}_{r}$ and addition is performed modulo $r$ \cite{Sin37}. Let $\psi$ be such a labelling. In this section we show that in the corresponding permutation representation $\Psi \leqslant \mathcal{S}_{r}$ of $\textup{PGL}(3,q)$, each sequence containing at most three collinear points is covered by $\vert \Psi \vert/24$ permutations. This in turn proves Theorem~\ref{t:collineationgroup}.

The consequence of this result is that for fixed $v$, we can find a much smaller multiset of permutations than the multiset built in Section~\ref{s:collineation} such that the vast majority of sequences are covered by a constant number of permutations. This prompts two immediate questions. The first is whether the bound in Theorem \ref{t:upperbound} can be reduced specifically when $t=4$. Indeed, in Section~\ref{s:collineation}, our construction relied on reducing the point set to a subset where no three points lay on the same hyperplane. Here, it seems we can relax that condition to one that requires that no four points lie on the same line. A \textit{$(k,d)$-arc} in $\textrm{PG}(2,q)$ is a set of $k$ points in $\textrm{PG}(2,q)$, no $d+1$ of which lie on the same line. Thus, we can build a PSCA of strength 4 by taking the representation $\Psi$ and deleting all but a subset of symbols that form a $(k,3)$-arc. The size of a $(k,3)$-arc in $\textrm{PG}(2,q)$ is at most twice the size of the arc used in the construction in Section~\ref{s:collineation} (i.e. $2(q+1)$) \cite{Thas75}. Hence, adapting the construction in Section~\ref{s:collineation} would only yield an improvement on the bound in Theorem \ref{t:upperbound} by a constant factor of at most $2^{8}$ when~$t = 4$. 

The second question is whether the permutation representation $\Psi$ may actually form a PSCA by covering sequences containing four collinear points with the same constant number of permutations. A computer search was performed over difference sets of $\mathbb{Z}_{r}$ for prime power orders $4 \leqslant q \leqslant 25$. This search found no representations of $\textup{PGL}(3,q)$ that also formed a PSCA of strength 4. However, a representation of $\textup{P}\Gamma\textup{L}(3,4)$ which forms a PSCA was presented by Gentle and Wanless \cite{GeWa22}. The group $\textup{P}\Gamma\textup{L}(3,q)$ is the product of $\textup{PGL}(3,q)$ with the group of field automorphisms of $\textup{GF}(q)$. In particular, $\textup{P}\Gamma\textup{L}(3,4)$ is twice as large as $\textup{PGL}(3,4)$. Moreover, Gentle and Wanless \cite{GeWa22} also present examples of representations of $\textup{PGL}(3,2)$ and $\textup{PGL}(3,3)$ that form PSCAs of strength 4.





The remainder of this section is devoted to a series of lemmas that collectively prove Theorem \ref{t:collineationgroup}. Consider sequences that contain three collinear points but not four. For $i \in \{1, 2, 3, 4\}$, let $T_{i}$ be the set of sequences $s$ of four points in $\textrm{PG}(2,q)$ for which there exists a line $\ell$ such that $s_{i}$ does not lie on $\ell$, but $s_{k}$ does for $k \in \{1, 2, 3, 4\} \backslash \{i \}$. By definition, if $s \in T_{i}$, then the points $\{ s_{k} : k \in \{1, 2, 3, 4\} \backslash \{i \}\}$ are collinear. However, if $j \neq i$ and $s' \in T_{j}$, then the points $\{ s'_{k} : k \in \{1, 2, 3, 4\} \backslash \{i \}\}$ are not collinear. Therefore, $s'$ is not in the orbit of $s$ under the action of $\textrm{PGL}(3,q)$. The following lemma addresses the case where $s$ and $s'$ both belong to $T_{i}$.
\begin{lemm}
If $s$ and $s'$ are sequences in $T_{i}$ for some $i \in \{1,2,3,4\}$ then there exists a projectivity of $\textup{PG}(2,q)$ that maps $s$ to $s'$.
\end{lemm}

\begin{proof}
Let $\{i,j,k,\ell\} = \{1,2,3,4\}$ and let $s_{i} = a$, $s_{j} = b$, $s_{k} = c$, $s_{\ell} = d$ and $s'_{i} = a'$, $s'_{j} = b'$, $s'_{k} = c'$, $s'_{\ell} = d'$. Hence, both $\{ a, b, c \}$ and $\{ a', b', c' \}$ are sets of non-collinear points. As such, the non-zero vectors $u \in a$, $v \in b$ and $w \in c$ form a basis of $V$, as do the non-zero vectors $u' \in a'$, $v' \in b'$ and $w' \in c'$. We can find a matrix $A \in \textrm{GL}(3, q)$ such that $Au = u'$, $Av = v'$ and $Aw = w'$. Let $f$ be the projectivity of $\textrm{PG}(2,q)$ induced by $A$. Then $f(a) = a'$, $f(b) = b'$ and $f(c) = c'$. Let $x \in d$. Since $b,c$ and $d$ are collinear, $x = \alpha v + \beta w$ for some non-zero $\alpha, \beta \in \textrm{GF}(q)$. Hence, $Ax = \alpha v' + \beta w'$. Let $x' \in d'$ and similarly note that $x' = \alpha' v' + \beta' w'$ for some non-zero $\alpha',\beta' \in \textrm{GF}(q)$. We can then find a matrix $B \in \textrm{GL}(3, q)$ such that $Bu' = u'$, $Bv' = \alpha^{-1}\alpha'v'$ and $Bw' = \beta^{-1}\beta'w'$. Then, $BAx = \alpha'v' + \beta'w' = x'$. Let $g$ be the projectivity induced by $B$ and observe $g \circ f (a) = a'$, $g \circ f (b) = b'$, $g \circ f (c) = c'$ and $g \circ f (d) = d'$. Therefore, the projectivity $g \circ f$ maps $s$ to $s'$.
\end{proof}

Now we choose some bijection $\psi : \textrm{PG}(2,q) \rightarrow [r]$ and consider the corresponding permutation group $\Psi \leqslant \mathcal{S}_{r}$. Let $L$ be the subsets of $[r]$ corresponding to lines of $\textrm{PG}(2,q)$. Then each line $\ell \in L$ can be represented by $\ell = \{\ell_{0}, \dots, \ell_{q}\} \subseteq [r]$ where $\ell_{0} < \ell_{1} < \dots < \ell_{q}$. Our next goal is to find $\vert \textup{Asc}(s) \vert$ for $s \in T_{i}$. First consider $T_{1}$. Let $\ell \in L$ and let $i \in [q+1]$. There are $\binom{q - i}{2}$ 3-subsets of $\ell$ that have $\ell_{i}$ as their minimal element and there are $\ell_{i} - i$ points less than $\ell_{i}$ that do not lie on $\ell$. Therefore,
\begin{equation}
\vert \textup{Asc}(s) \vert = \sum_{\ell \in L} \sum_{i = 0}^{q} \binom{q - i}{2} (\ell_{i} - i) \textup{ for } s \in T_{1}.  \label{e:asct1} \tag{\textup{E1}}
\end{equation}

 
Next, consider $T_{2}$. Suppose we build a sequence in $T_{2}$ containing three points on $\ell$ such that $\ell_{i}$ is the minimum of these points. Then, for $j > i$, there are $q - j$ points on $\ell$ greater than $\ell_{j}$ and $(\ell_{j} - j) - (\ell_{i} - i)$ points between $\ell_{i}$ and $\ell_{j}$ that do not lie on $\ell$. Therefore, for $s \in T_{2}$,
\begin{align*}
\vert \textup{Asc}(s) \vert &=  \sum_{\ell \in L}  \sum_{0 \leqslant i < j \leqslant q} (q - j)((\ell_{j} - j) -  (\ell_{i} - i))  \\
&= \sum_{\ell \in L} \left( \sum_{j = 1}^{q} \sum_{i = 0}^{j-1} (q - j)\ell_{j} - \sum_{j=1}^{q}\sum_{i=0}^{j-1} (q-j)j \right. \\
&\qquad\left. - \sum_{i=0}^{q-1}\sum_{j=i+1}^{q} (q-j)\ell_{i} + \sum_{i=0}^{q-1}\sum_{j=i+1}^{q} (q-j)i \right) \\
&= \sum_{\ell \in L} \left( \sum_{j=1}^{q} \left(j(q-j)\ell_{j} - j^{2}(q-j)\right) - \sum_{i=0}^{q-1} \left( \binom{q-i}{2}\ell_{i} - \binom{q-i}{2}i \right) \right). 
\end{align*}
Therefore,
\begin{equation}
\vert \textup{Asc}(s) \vert = \sum_{\ell \in L} \sum_{i=0}^{q} \left( i(q-i) - \binom{q-i}{2} \right)(\ell_{i} - i) \textup{ for } s \in T_{2}. \label{e:asct2} \tag{\textup{E2}}
\end{equation}

Next, consider $T_{3}$. Suppose we build a sequence in $T_{3}$ containing three points on $\ell$ such that $\ell_{j}$ is the maximum of these points. Then, for $i < j$, there are $i$ points on $\ell$ less than $\ell_{i}$ and $(\ell_{j} - j) - (\ell_{i} - i)$ points between $\ell_{i}$ and $\ell_{j}$ that do not lie on $\ell$. Therefore, for $s \in T_{3}$,
\begin{align}
\vert \textup{Asc}(s) \vert &=  \sum_{\ell \in L}  \sum_{0 \leqslant i < j \leqslant q} i((\ell_{j} - j) -  (\ell_{i} - i))  \nonumber\\
&= \sum_{\ell \in L} \left( \sum_{j = 1}^{q} \sum_{i = 0}^{j-1} i\ell_{j} - \sum_{j=1}^{q}\sum_{i=0}^{j-1} ij - \sum_{i=0}^{q-1}\sum_{j=i+1}^{q} i\ell_{i} + \sum_{i=0}^{q-1}\sum_{j=i+1}^{q} i^{2} \right) \nonumber\\
&= \sum_{\ell \in L} \left( \sum_{j=1}^{q} \left( \binom{j}{2}\ell_{j} - \binom{j}{2}j \right) - \sum_{i=0}^{q-1} \left( i(q-i)\ell_{i} - i^{2}(q - i) \right) \right). \nonumber
\end{align}
Therefore,
\begin{equation}
\vert \textup{Asc}(s) \vert = \sum_{\ell \in L} \sum_{i=0}^{q} \left( \binom{i}{2} - i(q-i) \right)(\ell_{i} - i) \textup{ for } s \in T_{3}. \label{e:asct3} \tag{\textup{E3}}
\end{equation}

Finally, consider $T_{4}$. Let $\ell \in L$ and let $i \in [q+1]$. There are $\binom{i}{2}$ 3-subsets of $\ell$ whose maximum is $\ell_{i}$ and there are $q^{2} + q - \ell_{i} - (q-i)$ points greater $\ell_{i}$ that do not lie on $\ell$. Therefore,
\begin{align}
\vert \textup{Asc}(s) \vert = \sum_{\ell \in L}  \sum_{i = 0}^{q} \binom{i}{2} (q^{2} - (\ell_{i} - i)) \textup{ for } s \in T_{4}.  \label{e:asct4} \tag{\textup{E4}}
\end{align}
Therefore,
\begin{align}
\eqref{e:asct1} + \eqref{e:asct2} + \eqref{e:asct3} + \eqref{e:asct4} &= \sum_{\ell \in L} \sum_{i = 0}^{q} \binom{i}{2}q^{2} \nonumber\\
&= \frac{(q^{2} + q + 1)q^{3}(q + 1)(q - 1)}{6}. \label{e:asctot} \tag{\textup{E5}}
\end{align}

Later in this section, we will prove the existence of a particular representation $\Psi$ such that \eqref{e:asct1} = \eqref{e:asct2} = \eqref{e:asct3} = \eqref{e:asct4}. Our first step is to equate \eqref{e:asct1} + \eqref{e:asct4} and \eqref{e:asct2} + \eqref{e:asct3} for which we require the following lemma. 


\begin{lemm}\label{l:linesum}
Let $L$ be the lineset of $\textup{PG}(2,q)$ as subsets of $[r]$. Then,
\begin{equation*}
\sum_{\ell \in L} \sum_{i = 0}^{q} i\ell_{i} = \frac{(q^{2} + q )(q^{2} + q + 1)(2q^{2} + 2q + 1)}{6}
\end{equation*}
\end{lemm}

\begin{proof}
Let $j \in [r]$ and let $J = \{ (i, \ell) : \ell_{i} = j \}$. Consider $\sum_{(i,\ell) \in J} i \ell_{i}$. For each pair $(i, \ell) \in J$, $\ell_{i} = j$ and $i$ is the number of points less than $j$ that lie on $\ell$. There are $j$ elements of $[r]$ less than $j$, each of which must lie on the same line as $j$ exactly once. Therefore,
\begin{equation*}
\sum_{(i,\ell) \in J} i \ell_{i} = j \sum_{(i,\ell) \in J} i = j^{2}.
\end{equation*}
Therefore, 
\begin{equation*}
\sum_{\ell \in L} \sum_{i = 0}^{q} i\ell_{i} = \sum_{j = 0}^{q^{2} + q} j^{2} = \frac{(q^{2} + q)(q^{2} + q + 1)(2q^{2} + 2q + 1)}{6} \qedhere
\end{equation*}


\end{proof}

\begin{lemm}\label{l:ascsum}
In any representation $\Psi$, \eqref{e:asct1} $+$ \eqref{e:asct4} $=$ \eqref{e:asct2} $+$ \eqref{e:asct3} $=$ \eqref{e:asctot}/$2$.
\end{lemm}
\begin{proof}
Using the expressions \eqref{e:asct2} and \eqref{e:asct3},
\begin{align*}
\eqref{e:asct2} + \eqref{e:asct3} &= \sum_{\ell \in L} \sum_{k = 0}^{q} \left( \binom{k}{2} - \binom{q - k}{2} \right)(\ell_{k} - k)\\
&= \frac{1}{2} \sum_{\ell \in L} \sum_{k = 0}^{q} \left(2k(q - 1) - (q^{2} - q) \right)(\ell_{k} - k).
\end{align*}
First, consider
\begin{align*}
\sum_{\ell \in L} \sum_{k = 0}^{q}  (q^{2} - q)(\ell_{k} - k).
\end{align*}
The sum $\sum_{\ell \in L} \sum_{k = 0}^{q} \ell_{k}$ is just the sum of all the points of every line of $\textrm{PG}(2,q)$. Each point appears on $q + 1$ lines so this is equal to $\binom{q^{2} + q + 1}{2}(q + 1)$. Next, $\sum_{\ell \in L}\sum_{k = 0}^{q} k = (q^{2} + q + 1)\binom{q + 1}{2}$. Therefore,
\begin{align*}
\sum_{\ell \in L} \sum_{k = 0}^{q}  (q^{2} - q)(\ell_{k} - k) &= (q^{2} - q) \left( \binom{q^{2} + q + 1}{2}(q + 1) - (q^{2} + q + 1)\binom{q + 1}{2} \right)\\
&= (q^{2} + q + 1)(q^{2} - q)(q + 1) \left( \frac{q^{2} + q}{2} - \frac{q}{2} \right)\\
&= \frac{1}{2}(q^{2} + q + 1)(q^{3} - q)q^{2}.
\end{align*}
Next, consider
\begin{equation*}
\sum_{\ell \in L} \sum_{k = 0}^{q} k (\ell_{k} - k).
\end{equation*}
By Lemma \ref{l:linesum}, this is equal to
\begin{equation*}
\frac{1}{6}  (q^{2} + q)(q^{2} + q + 1)\left(2q^{2} + 2q + 1 - 2q - 1\right) = \frac{(q^{2} + q + 1)(q^{2} + q)q^{2}}{3}.
\end{equation*}
Therefore,
\begin{align*}
\eqref{e:asct2} + \eqref{e:asct3} &= \frac{1}{2}\left( \frac{2(q^{2} + q + 1)(q^{3} - q)q^{2}}{3} - \frac{(q^{2} + q + 1)(q^{3} - q)q^{2}}{2} \right)\\
&= \frac{(q^{2} + q + 1)(q^{3} - q)q^{2}}{12}\\
&= \eqref{e:asctot}/2.
\end{align*}
As \eqref{e:asct1} + \eqref{e:asct2} + \eqref{e:asct3} + \eqref{e:asct4} = \eqref{e:asctot}, it must also be true that \eqref{e:asct1} + \eqref{e:asct4} = \eqref{e:asctot}/2.
\end{proof} 

Lemma \ref{l:ascsum} applies generally to any representation of $\textrm{PGL}(3,q)$, but now we will choose a specific representation according to a difference set of $\mathbb{Z}_{r}$. Recall that a difference set is a set $A = \{ a_{0}, a_{1}, \dots, a_{q} \} \subset \mathbb{Z}_{r}$ such that for any non-zero element $x \in \mathbb{Z}_{r}$, there are $i$ and $j$ such that $a_{i} - a_{j} = x$. For the rest of this section, we choose $\psi$ such that the lines of $\textrm{PG}(2,q)$ are mapped to sets of the form $\{ a_{i} + j : i \in [q+1] \}$ for $j \in \mathbb{Z}_{r}$ and a difference set $A = \{a_{0}, \dots, a_{q}\}$ where $a_{i} < a_{i+1}$ for $i \in \{0, \dots, q-1 \}$. Furthermore, we can assume without loss of generality that $a_{0} = 0$. Let $A + j$ denote the line $\{ a_{i} + j : i \in [q+1] \}$. For any integer $k$, define $a_{k(q + 1) + i} \coloneqq  a_{i}$. 

Our goal is to show that for this particular choice of $\psi$, in the corresponding permutation subgroup $\Psi \leqslant \mathcal{S}_{r}$, \eqref{e:asct1} = \eqref{e:asct2} = \eqref{e:asct3} = \eqref{e:asct4}. This will be done by proving that for $i \in [q+1]$
\begin{equation*}
\sum_{\ell \in L} (q^{2} + q - \ell_{q - i}) = \sum_{\ell \in L} \ell_{i}.
\end{equation*}
To do so, we first require the following lemma.

\begin{lemm}\label{l:diffset}
For the difference set $A = \{ a_{0}, a_{1}, \dots, a_{q} \} \subset \mathbb{Z}_{r}$, and for $i \in [q+1]$,
\begin{equation}
\sum_{k = 0}^{q} (a_{k + i} - a_{k})(a_{k} - a_{k - 1}) = \sum_{k = 0}^{q} (a_{k + 1} - a_{k})(a_{k} - a_{k - i}) \label{e:diffset}
\end{equation} 
\end{lemm}

\begin{proof}
\begin{align*}
\sum_{k = 0}^{q} (a_{k + i} - a_{k})(a_{k} - a_{k - 1}) &= \sum_{k = 0}^{q} \left(a_{k + i}a_{k} - a_{k + i}a_{k - 1} - a_{k}^{2} + a_{k}a_{k - 1}\right)\\
&= \sum_{k=0}^{q} \left( a_{k}a_{k-i} - a_{k+1}a_{k-i} - a_{k}^{2} + a_{k+1}a_{k}\right)\\
&= \sum_{k = 0}^{q} (a_{k + 1} - a_{k})(a_{k} - a_{k-i}). \qedhere
\end{align*}


\end{proof}

\begin{lemm}
Let $L = \{A + j: j \in \mathbb{Z}_{r} \}$ for the difference set $A = \{ a_{0}, \dots, a_{q} \}$. For $i \in [q+1]$
\begin{equation}
\sum_{\ell \in L} (q^{2} + q - \ell_{q - i}) = \sum_{\ell \in L} \ell_{i}. \label{e:lineflip}
\end{equation}
\end{lemm}

\begin{proof}
First, we consider $\sum_{\ell \in L} \ell_{i}$ for $i \in [q+1]$. Consider the values of $j$ for which $a_{k} + j$ is the smallest element of $A + j$. First, when $j = q^{2} + q + 1 - a_{k}$, the smallest element of $A + j$ is $a_{k} + j = 0$. Then, when $j = q^{2} + q + 1 - a_{k - 1} - 1$, the smallest element of $A + j$ is $a_{k} + j = a_{k} - a_{k - 1} - 1$ and the largest element of $A + j$ is $a_{k - 1} + j = q^{2} + q$. Hence, the smallest element of $A + (j + 1)$ would be $a_{k - 1} + (j + 1) = 0$. So, for $j \in [q^{2} + q + 1 - a_{k}, q^{2} + q - a_{k - 1}]$, the smallest point on the line $A + j$ is $a_{k} + j$. The $i$th smallest point on these lines will therefore be $a_{k + i} + j$ and will range in value from $a_{k + i} - a_{k}$ to $a_{k + i} - a_{k - 1} - 1$. The sum of the integers in this interval is
\begin{equation*}
\binom{a_{k} - a_{k - 1}}{2} + (a_{k + i} - a_{k})(a_{k} - a_{k - 1}).
\end{equation*}
Therefore,
\begin{equation*}
\sum_{\ell \in L} \ell_{i} = \sum_{k = 0}^{q} \left( \binom{a_{k} - a_{k - 1}}{2} + (a_{k + i} - a_{k})(a_{k} - a_{k - 1}) \right).
\end{equation*}

Similarly, the range of values for $j$ for which $a_{k} + j$ is the largest point of the line $A + j$ is the interval $[ q^{2} + q + 1 - a_{k + 1}, q^{2} + q + 1 - a_{k} - 1]$. For these lines, the $i$th largest point is $a_{k - i} + j$ which ranges in value from $q^{2} + q + 1 + a_{k - i} - a_{k + 1}$ to $q^{2} + q + a_{k - i} - a_{k}$. Therefore,
\begin{align*}
\sum_{\ell \in L} (q^{2} + q - \ell_{q - i}) &= \sum_{k=0}^{q} \sum_{j = q^{2} + q + 1 - a_{k + 1}}^{q^{2} + q  - a_{k}} (q^{2} + q - (a_{k - i} + j))\\
&= \sum_{k=0}^{q} \sum_{j = 0}^{a_{k + 1} - a_{k} - 1} (a_{k} - a_{k - i} + j)\\
&= \sum_{k=0}^{q} \left(\binom{a_{k + 1} - a_{k}}{2} + (a_{k + 1} - a_{k})(a_{k} - a_{k - i})\right).
\end{align*} 
By Lemma \ref{l:diffset},
\begin{equation*}
\sum_{\ell \in L} (q^{2} + q - \ell_{q - i}) =  \sum_{k = 0}^{q} \left( \binom{a_{k + 1} - a_{k}}{2} + (a_{k + i} - a_{k})(a_{k} - a_{k - 1}) \right) = \sum_{\ell \in L} \ell_{i}. \qedhere
\end{equation*}


\end{proof}

Now we can prove that for this choice of $\Psi$, \eqref{e:asct1} = \eqref{e:asct2} = \eqref{e:asct3} = \eqref{e:asct4}.
\begin{lemm}\label{l:equalasc}
Let $\psi: \textup{PG}(2,q) \rightarrow [r]$ be a bijection such that the lines of $\textup{PG}(2,q)$ are mapped to the sets $\{A + j: j \in \mathbb{Z}_{r} \}$ for the difference set $A = \{ a_{0}, \dots, a_{q} \}$. Then, $\eqref{e:asct1} = \eqref{e:asct2} = \eqref{e:asct3} = \eqref{e:asct4} = \eqref{e:asctot}/4$.
\end{lemm}

\begin{proof}
We can substitute \eqref{e:lineflip} into \eqref{e:asct4} and obtain
\begin{align*}
\eqref{e:asct4} &= \sum_{\ell \in L} \left( \sum_{i = 0}^{q} \binom{i}{2} (q^{2} - (\ell_{i} - i)) \right)\\
&= \sum_{\ell \in L} \left( \sum_{i = 0}^{q} \binom{i}{2} (q^{2} + i - (q^{2} + q - \ell_{q - i}) ) \right)\\
&= \sum_{\ell \in L} \left( \sum_{i = 0}^{q} \binom{i}{2} (\ell_{q - i} - (q - i)  ) \right)\\
&= \sum_{\ell \in L} \left( \sum_{i = 0}^{q} \binom{q - i}{2} (\ell_{i} - i  ) \right)\\
&= \eqref{e:asct1}.
\end{align*}
By Lemma \ref{l:ascsum}, \eqref{e:asct1} + \eqref{e:asct4} = \eqref{e:asctot}/2. Therefore, \eqref{e:asct1} = \eqref{e:asct4} = \eqref{e:asctot}/4. We can also substitute \eqref{e:lineflip} into \eqref{e:asct3} and find
\begin{align*}
\eqref{e:asct3} &= \sum_{\ell \in L} \left( \sum_{0 \leqslant i < j \leqslant q} i((\ell_{j} - j) - (\ell_{i} - i)) \right)\\
&= \sum_{\ell \in L} \left( \sum_{0 \leqslant i < j \leqslant q} i((q^{2} + q - \ell_{q - j} - j) - (q^{2} + q - \ell_{q - i} - i)) \right)\\
&= \sum_{\ell \in L} \left( \sum_{0 \leqslant i < j \leqslant q} i((\ell_{q - i} - (q - i)) -  (\ell_{q - j} - (q - j))) \right)\\
&= \sum_{\ell \in L} \left( \sum_{0 \leqslant i < j \leqslant q} (q - j)((\ell_{j} - j) - (\ell_{i} - i)) \right)\\
&= \eqref{e:asct2}.
\end{align*}
Again, by Lemma \ref{l:ascsum}, \eqref{e:asct2} + \eqref{e:asct3} = \eqref{e:asctot}/2. Therefore, \eqref{e:asct2} = \eqref{e:asct3} = \eqref{e:asctot}/4.
\end{proof}

We are now ready to prove Theorem \ref{t:collineationgroup}


\begin{proof}[Proof of Theorem \ref{t:collineationgroup}]
If $\psi$ is of the form outlined in Lemma \ref{l:equalasc}, then under the action of $\Psi$ on $\mathcal{S}_{r,4}$, and for $i \in \{1, 2, 3, 4\}$ and $s \in T_{i}$, 
\begin{equation*}
\vert \textup{Asc}(s) \vert = \frac{\eqref{e:asctot}}{4} = \frac{(q^{2} + q + 1)q^{3}(q + 1)(q - 1)}{24}.
\end{equation*}
Now consider $\textup{Stab}(s)$ and note that $\vert \textup{Stab}(s) \vert = \vert \textrm{PGL}(3, q) \vert/\vert T_{i} \vert$. There are $(q+1)q(q-1)$ 3-sequences that can be formed from points of a given line $\ell$. There are then $q^{2}$ points not on $\ell$. Therefore,
\begin{align*}
\vert T_{i} \vert = (q^{2} + q + 1)q^{3}(q+1)(q-1).
\end{align*}
Thus,
\begin{equation*}
\vert \textup{Stab}(s) \vert \vert \textup{Asc}(s) \vert = \frac{\vert \Psi \vert}{(q^{2} + q + 1)q^{3}(q+1)(q-1)} \frac{(q^{2} + q + 1)q^{3}(q + 1)(q - 1)}{24} = \frac{\vert \Psi \vert}{24}.
\end{equation*}
Thus, by Lemma \ref{l:ascstab}, every sequence in $T_{i}$ for $i \in \{1,2,3,4\}$ is covered by $\vert \Psi \vert / 24$ permutations in $\Psi$. By Lemma \ref{l:framecover}, we also know that every frame in $\mathcal{S}_{r,4}$ is covered by $\vert \Psi \vert/24$ permutations in $\Psi$. Moreover, by Theorem \ref{t:fundamental}, the number of frames in $\mathcal{S}_{r,4}$ is exactly 
\begin{equation*}
\vert \textup{PGL}(3,q)\vert = (q^{2} + q + 1)q^{3}(q+1)(q-1)^{2}.
\end{equation*} 
Adding this to the number of sequences in $T_{i}$ for $i \in \{1,2,3,4\}$ we find that the number of sequences in $\mathcal{S}_{r,4}$ that are covered by exactly $\vert \Psi \vert /24$ permutations in $\Psi$ is at least
\begin{equation*}
(q^{2} + q + 1)q^{3}(q+1)(q-1)(q+3).
\end{equation*}
We divide this number by $\vert \mathcal{S}_{r,4} \vert$ and conclude 
\begin{align*}
\frac{(q^{2} + q + 1)q^{3}(q+1)(q-1)(q+3)}{\vert \mathcal{S}_{r,4} \vert} &= \frac{(q^{2} + q + 1)q^{3}(q+1)(q-1)(q+3)}{(q^{2} + q + 1)(q^{2} + q)(q^{2} + q - 1)(q^{2} + q - 2)}\\
&= \frac{q^{2}(q + 3)}{(q^{2} + q - 1)(q + 2)}\\
&> \frac{q}{q+1}.
\end{align*}
This completes the proof.
\end{proof}

\section*{Acknowledgements}

The author is grateful to Daniel Horsley, Ian Wanless, Jonathan Jedwab, Shuxing Li and Jingzhou Na for useful discussions. The author was supported by an Australian Government Research Training Program (RTP) Scholarship.








\bibliographystyle{mersenne-plain}
\bibliography{ALCO_Gentle_810.bib}


\end{document}