An \( (n,r) \)-arc in \( \operatorname{PG}(2,q) \) is a set \( \mathcal{B} \) of points in \( \operatorname{PG}(2,q) \) such that each line in \( \operatorname{PG}(2,q) \) contains at most \( r \) elements of \( \mathcal{B} \) and such that there is at least one line containing exactly \( r \) elements of \( \mathcal{B} \). The value \( m_r(2,q) \) denotes the maximal number \( n \) of points in the projective geometry \( \operatorname{PG}(2,q) \) for which an \( (n,r) \)-arc exists. We show by systematically excluding possible automorphisms that putative \( (44,5) \)-arcs, \( (90,9) \)-arcs in \( \operatorname{PG}(2,11) \), and \( (39,4) \)-arcs in \( \operatorname{PG}(2,13) \)—in case of their existence—are rigid, i.e. they all would only admit the trivial automorphism group of order \( 1 \). In addition, putative \( (50,5) \)-arcs, \( (65,6) \)-arcs, \( (119,10) \)-arcs, \( (133,11) \)-arcs, and \( (146,12) \)-arcs in \( \operatorname{PG}(2,13) \) would be rigid or would admit a unique automorphism group (up to conjugation) of order \( 2 \).
Definition 1.1. An \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) is a set \({\mathcal B}\) of points in \(\operatorname{PG}(2,q)\) such that each line in \(\operatorname{PG}(2,q)\) contains at most \(r\) elements of \({\mathcal B}\) and such that there is at least one line containing exactly \(r\) elements of \({\mathcal B}\).
It is well-known (e.g. see [3]) that \((n,r)\)-arcs in \(\operatorname{PG}(2,q)\) are closely related to error-correcting linear codes: The \(n\) points of an \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) define the columns of a \(3\times n\) generator matrix of linear \([n,3,n-r]_q\) code, which is code of length \(n\), dimension \(3\), and minimum distance \(n-r\) with respect to the Hamming metric. The linear code is projective since the columns of any generator matrix are pairwise linearly independent.
Definition 1.2. Let \(m_r(2,q)\) denote the maximum number \(n\) for which an \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) exists.
A major goal in studying \((n,r)\)-arcs in \(\operatorname{PG}(2,q)\) is the determination of \(m_r(2,q)\).
In general it is hard to determine the exact value of \(m_r(2,q)\) and in most cases instead of the exact value only a lower and an upper bound for \(m_r(2,q)\) are known. An explicit construction of an \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) yields a lower bound \(m_r(2,q)\ge n\).
The values \(m_r(2,q)\) with \(q\le 9\) are exactly determined (see [3]). For \(m_r(2,q)\) with \(11\le q\le 19\) we refer to [2] whereas a table for \(23\le q\le 31\) can compiled from several sources e.g. [4,7,9,8,12,10,14,13,11,15,16,17,20].
In this article, we show that the putative \((n,r)\)-arcs in \(\operatorname{PG}(2,q)\) for \(q\in\{11,13\}\) for the open gaps between lower and upper bound on \(m_r(2,q)\)—in case of existence—are rigid or only admit a unique automorphism of order \(2\).
The construction of \((n,r)\)-arcs in \(\operatorname{PG}(2,q)\) with prescribed groups of automorphisms can be described as integer linear programming (see [6,4]):
In the following, let \[{\operatorname{GF}(q)^n\brack k},\] denote the set of \(k\)-dimensional subspaces of \(\operatorname{GF}(q)^n\), which is called the Grassmannian. Its cardinality is given by the Gaussian number, also called \(q\)-Binomial coefficient: \[{n\brack k}_q=\left|{\operatorname{GF}(q)^n\brack k}\right| =\prod_{i=0}^{k-1}\frac{q^n-q^i}{q^k-q^i}.\]
In terms of vector spaces, an \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) corresponds to a set \({\mathcal B}\subseteq{\operatorname{GF}(q)^3\brack 1}\) such that for all \(H\in{\operatorname{GF}(q)^3\brack 2}\) holds: \[|\{P\in{\mathcal B}\mid H\supseteq P\}|\le r.\]
If \({\operatorname{GF}(q)^3\brack 1}=\{P_1,\ldots,P_{q^2+q+1}\}\) and \({\operatorname{GF}(q)^3\brack 2}=\{H_1,\ldots,H_{q^2+q+1}\}\), where \({3\brack 1}_q={3\brack 2}_q=q^2+q+1\), we define the \((q^2+q+1)\times (q^2+q+1)\) incidence matrix \[A(q)=(a_{ij}),\] with entries \[a_{ij}:=\begin{cases} 1&\text{if $H_i\supseteq P_j$,}\\ 0&\text{otherwise.} \end{cases}\]
Lemma 2.1. If \(u=(1,\ldots,1)^T\) denotes the all-one vector any binary column vector \(x\) satisfying \[A(q)\cdot x\le r\cdot u,\] is equivalent to a \((u^T\cdot x,r)\)-arc in \(\operatorname{PG}(2,q)\).
Corollary 2.2. The determination of \(m_r(2,q)\) corresponds to the following integer linear programming problem: \[m_r(2,q)=\max_{x\in\{0,1\}^{q^2+q+1}}\{u^T\cdot x\mid A(q)\cdot x\le r\cdot u\}.\]
The incidence preserving bijections (automorphisms) of our ambient space for \((n,r)\)-arcs—the projective geometry \(\operatorname{PG}(2,q)\)—are defined by the projective semi-linear group \(\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) (see [1]). It acts transitively on the Grassmannian \({\operatorname{GF}(q)^3\brack k}\).
Hence, any subgroup \(G\le\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) partitions the Grassmannian into \(G\)-orbits. If \(\alpha\in\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) and \(S\in{\operatorname{GF}(q)^3\brack k}\) we denote by \[\alpha S:=\{\alpha x\mid x\in S\},\] the transformed subspace and by \[G(S):=\{\alpha S\mid \alpha\in G\},\] the \(G\)-orbit of \(S\). The set of all \(G\)-orbits will be written as \[G\backslash\!\!\backslash{\operatorname{GF}(q)^3\brack k}.\]
Definition 2.3. An \((n,r)\)-arc \({\mathcal B}\) in \(\operatorname{PG}(2,q)\) admits a subgroup \(G\le\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) as a group of automorphisms if and only if \({\mathcal B}\) consists of \(G\)-orbits on \({\operatorname{GF}(q)^3\brack 1}\). The maximal group of automorphisms of \({\mathcal B}\) is called the automorphism group of \({\mathcal B}\) and abbreviated by \[\operatorname{Aut}({\mathcal B}).\]
Definition 2.4. Let \(m^G_r(2,q)\) denote the maximal size \(n\) of an \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) admitting \(G\le\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) as a group of automorphisms.
Corollary 2.5. For any \(G\le\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) we get a lower bound \[m^G_r(2,q)\le m_r(2,q).\] In particular, for the trivial group \(G=\{1\}\) we have \[m^{\{1\}}_r(2,q)= m_r(2,q).\]
If \(\{P_1,\ldots,P_\ell\}\) denotes a set of representatives of the orbits \(G\backslash\!\!\backslash{\operatorname{GF}(q)^3\brack 1}\) and \(\{H_1\ldots,H_\ell\}\) a transversal of the orbits \(G\backslash\!\!\backslash{\operatorname{GF}(q)^3\brack 2}\) for any \(G\le\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) we define the \(G\)-incidence matrix \(A(G)=(a_{ij})\) with \[a_{ij}:=|\{P\in G(P_j)\mid H_i\supseteq P\}|.\] Furthermore, by \(w(G)=(w_1,\ldots,w_\ell)^T\) we denote the vector of the lengths of \(G\)-orbits on \({\operatorname{GF}(q)^3\brack 1}\), i.e. \[w_j:=|G(P_j)|.\] Note that the number of orbits of \(G\) on the set of points and hyperplanes is equal \[\ell=\left|G\backslash\!\!\backslash{\operatorname{GF}(q)^3\brack 1}\right|= \left|G\backslash\!\!\backslash{\operatorname{GF}(q)^3\brack 2}\right|\le q^2+q+1.\]
Theorem 2.6. Any binary vector \(x\) of length \(\ell=|G\backslash\!\!\backslash{\operatorname{GF}(q)^3\brack 1}|\) with \[A(G)\cdot x\le r\cdot u,\] corresponds to a \((w(G)^T\cdot x,r)\)-arc in \(\operatorname{PG}(2,q)\) admitting \(G\le \operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) as a group of automorphisms. In addition, we obtain the following integer linear programming: \[m^G_r(2,q)=\max_{x\in\{0,1\}^\ell}\{w(G)^T\cdot x\mid A(G)\cdot x\le r\cdot u\}.\]
An open gap is an entry in the tables of \(m_r(2,q)\) for which upper and lower bound differ: \[\ell\le m_r(2,q)\le u\quad\text{where}\quad \ell< u.\]
In that case the question is whether an \((\ell+1,r)\)-arc in \(\operatorname{PG}(2,q)\) exits or not. We call such an arc a putative arc in \(\operatorname{PG}(2,q)\). In [5] it was shown that for the gap \(100\le m_{10}(2,11)\le101\) a putative \((101,10)\)-arc in \(\operatorname{PG}(2,11)\) admits—in case of its existence—only the trivial automorphism group of order \(1\).
In this paper we consider the remaining gaps for \(q=11\) and \(q=13\) which are given in Table 1.
| \(m_5(2,11)\) | \(\in\) | \(\{43,44,45\}\) |
| \(m_9(2,11)\) | \(\in\) | \(\{89,90\}\) |
| \(m_4(2,13)\) | \(\in\) | \(\{38,39,40\}\) |
| \(m_5(2,13)\) | \(\in\) | \(\{49,50,51,52,53\}\) |
| \(m_6(2,13)\) | \(\in\) | \(\{64,65,66\}\) |
| \(m_10(2,13)\) | \(\in\) | \(\{118,119\}\) |
| \(m_11(2,13)\) | \(\in\) | \(\{132,133\}\) |
| \(m_12(2,13)\) | \(\in\) | \(\{145,146,147\}\) |
Definition 3.1. Let \({\mathcal B},{\mathcal B}'\) be an \((n,r)\)-arcs in \(\operatorname{PG}(2,q)\) The two sets \({\mathcal B}\) and \({\mathcal B}'\) are defined to be isomorphic if and only if there exists \(\alpha\in\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) such that \[\alpha{\mathcal B}:=\{\alpha P\mid P\in{\mathcal B}\}={\mathcal B}'.\] The set of all arcs that are isomorphic to \({\mathcal B}\) is denoted by \[\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)({\mathcal B}):=\{\alpha{\mathcal B}\mid \alpha\in\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\}.\]
Note that due to the incidence preserving property of \(\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) isomorphic arcs have the same parameters.
The following lemma is well-known from the theory of group actions (cf. [21]) and states that the automorphism groups of isomorphic objects are conjugated.
Lemma 3.2. Let \({\mathcal B}\) be an \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) and let \(\alpha\in\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\). Then we obtain: \[\operatorname{Aut}(\alpha{\mathcal B})=\alpha\operatorname{Aut}({\mathcal B})\alpha^{-1}=\{\alpha\beta\alpha^{-1}\mid \beta\in\operatorname{Aut}({\mathcal B})\}.\]
If \({\mathcal B}\) in an \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) with \(G\le\operatorname{Aut}({\mathcal B})\) then any isomorphic arc \({\mathcal B}'=\alpha {\mathcal B}\) for \(\alpha\in\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) admits the conjugated group \(G'=\alpha G\alpha^{-1}\) satisfies \[G'=\alpha G\alpha^{-1}\le\alpha\operatorname{Aut}(G)\alpha^{-1}=\operatorname{Aut}(\alpha{\mathcal B})=\operatorname{Aut}({\mathcal B}'),\] which means that the conjugated group \(G'\) also occurs as a group of automorphisms of \({\mathcal B}'\).
As a consequence, when aiming for \((n,r)\)-arcs in \(\operatorname{PG}(2,q)\) with prescribed groups of automorphisms it is sufficient to consider representatives of conjugacy classes of subgroups of \(\operatorname{PGL}(3,q)\) as possible candidates for potential groups to be prescribed.
Furthermore, any \((n,r)\)-arc \({\mathcal B}\) in \(\operatorname{PG}(2,q)\) with \(\{1\}<G\le\operatorname{Aut}({\mathcal B})\) also admits all cyclic subgroups \(C\le G\) as groups of automorphisms.
Corollary 3.3. If we can show for all representatives \(C\) of conjugacy classes of nontrivial cyclic subgroups of \(\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)\) that no \((n,r)\)-arc in \(\operatorname{PG}(2,q)\) exists with \(C\) as group as automorphisms, either the automorphism group of such arcs are trivial or arcs with that set of parameters do not exist.
In case of a prime field \(\operatorname{GF}(q)\) the projective semi-linear group is exactly the projective linear group \[\operatorname{P}\!\Gamma\!\operatorname{L}(3,q)=\operatorname{PGL}(3,q).\]
In the following, a transversal of conjugacy classes of cyclic subgroups of \(\operatorname{PGL}(3,q)\) will be abbreviated by \[\operatorname{Conj}(q).\]
Its cardinality is given by (see [22]): \[|\operatorname{Conj}(q)|=\begin{cases} q^2+q+2&\text{if $3$ divides $q-1$,}\\ q^2+q&\text{otherwise.} \end{cases}\]
Lemma 3.4. Let \(q\) be a prime. If \[m^C_r(2,q)<n\quad \forall C\in\operatorname{Conj}(q)\setminus\{\{1\}\},\] one of the following conditions holds:
1. \(m_r(2,q)<n\).
2. \((n,r)\)-arcs \({\mathcal B}\) in \(\operatorname{PG}(2,q)\) exist where \(\operatorname{Aut}({\mathcal B})=\{1\}\).
We now apply this corollary to the parameters \((q,n,r)=(11,44,5)\), \((q,n,r)=(11,90,9)\), and \((q,n,r)=(13,50,5)\). There are \(|\operatorname{Conj}(11)|=132\) conjugacy classes of cyclic subgroups of \(\operatorname{PGL}(3,11)\) and \(|\operatorname{Conj}(13)|=184\) classes in \(\operatorname{PGL}(3,13)\). We compute the representatives using GAP [18]. By solving the integer linear programming \(m^C_r(2,q)\) according to Theorem 2.6 for all \(C\in\operatorname{Conj}(q)\setminus\{1\}\) using Gurobi [19] we obtain with a runtime less than 3 hours on a 1.2 GHz Intel Core m3 processor the following result:
Theorem 3.5. In case of their existence the automorphism groups of \((44,5)\)-arcs, \((90,9)\)-arcs in \(\operatorname{PG}(2,11)\), and \((50,5)\)-arcs in \(\operatorname{PG}(2,13)\) would be trivial of order \(1\).
For the remaining parameters \(r\in\{5,6,10,11,12\}\) for \(q=13\) we apply a slightly adapted version of Lemma 3.4 since for these open cases exactly one cyclic subgroup \[C_0:=\left\langle \begin{pmatrix} 0&1&0\\ 1&0&0\\ 0&0&12 \end{pmatrix} \right\rangle,\] of order \(2\) could not directly be excluded to be a group of automorphisms of putative arcs since we cancelled the ILP solver for \(m_r^{C_0}(2,13)\) after 5000 seconds (for each value \(r\)).
But it is obvious to guess that this group can probably also be excluded if we spend more running time on the ILP solver.
Lemma 3.6. Let \(q\) be a prime. Let \(C_0\in\operatorname{Conj}(q)\). If \[m^C_r(2,q)<n\quad \forall C\in\operatorname{Conj}(q)\setminus\{\{1\},C_0\},\] one of the following conditions holds:
1. \(m_r(2,q)<n\).
2. \((n,r)\)-arcs \({\mathcal B}\) in \(\operatorname{PG}(2,q)\) exist where either \(\operatorname{Aut}({\mathcal B})=\{1\}\) or \(\operatorname{Aut}({\mathcal B})\) is conjugated to \(C_0\).
Finally, we get
Theorem 3.7. In case of their existence the automorphism groups of \((50,5)\)-arcs, \((65,6)\)-arcs, \((119,10)\)-arcs, \((133,11)\)-arcs, and \((146,12)\)-arcs in \(\operatorname{PG}(2,13)\) would either be trivial of order \(1\) or would be the following cyclic subgroup of order \(2\) (up to conjugation): \[C_0:=\left\langle \begin{pmatrix} 0&1&0\\ 1&0&0\\ 0&0&12 \end{pmatrix}\right\rangle.\]
The author declares that he has no competing interests.