FINITE TRANSITIVE GROUPS HAVING MANY SUBORBITS OF CARDINALITY AT MOST TWO AND AN APPLICATION TO THE ENUMERATION OF CAYLEY GRAPHS

NEW

Problem: Let $G\leq \operatorname{Sym}(\Omega)$ be a finite transitive permutation group. For $\alpha\in\Omega$, let $G_\alpha$ be its stabilizer and define

$${\bf I}_\Omega(G)= \frac{|\{\omega\in\Omega:\ |\omega^{G_\alpha}|\le 2\}|}{|\Omega|}.$$

This is independent of $\alpha$. The conjecture asserts that if ${\bf I}_\Omega(G)>1/2$, then

$${\bf I}_\Omega(G)=\frac{q+1}{2q}$$

for some $q\in\mathbb Q$ with $2q\in\mathbb N$, equivalently ${\bf I}_\Omega(G)=1/2+1/n$ for some $n\in\mathbb N$.

Result: The conjecture is false.

Let $U$ be a $3$-dimensional vector space over $\mathbb F_2$, let $z\notin U$, and put

$$V=U\oplus \langle z\rangle .$$

Let $L=\operatorname{GL}(U)$ act on $V$ by acting naturally on $U$ and fixing $z$. Let

$$G=V\rtimes L.$$

Choose distinct nonzero $a,b\in U$, and set

$$W=\langle z+a,\ z+b\rangle\le V.$$

Let $\Omega$ be the set of right cosets of $W$ in $G$. Then $G$ acts transitively on $\Omega$, with point stabilizer $W$.

For $\ell\in L$, the conjugate $W^\ell$ has the form

$$W_{c,d}:=\langle z+c,\ z+d\rangle$$

for distinct nonzero $c,d\in U$. The $L$-orbit of $W$ is exactly the set of all such $W_{c,d}$, indexed by unordered pairs $\{c,d\}\subset U^\#$. Hence it has size

$$\binom{7}{2}=21.$$

For a coset corresponding to $\ell$, the $W$-suborbit length is

$$|W:W\cap W^\ell|.$$

Since $\dim W=2$, this length is at most $2$ iff $W\cap W^\ell\neq 0$.

Now $W$ has nonzero vectors

$$z+a,\quad z+b,\quad a+b.$$

Among the $21$ subspaces $W_{c,d}$:

• those containing $z+a$: $6$;
• those containing $z+b$: $6$;
• those containing $a+b$: $3$.

Their pairwise intersections are all the single subspace $W$, so by inclusion-exclusion the number meeting $W$ nontrivially is

$$6+6+3-1-1-1+1=13.$$

Therefore

$${\bf I}_\Omega(G)=\frac{13}{21}>\frac12.$$

But

$$\frac{13}{21}-\frac12=\frac5{42},$$

so if $\frac{13}{21}=(q+1)/(2q)$, then $q=21/5$, hence $2q=42/5\notin\mathbb N$. Thus ${\bf I}_\Omega(G)$ is not of the conjectured form.

Citation: The conjecture and notation are from Pablo Spiga, “Finite transitive groups having many suborbits of cardinality at most two and an application to the enumeration of Cayley graphs,” arXiv:2109.13882. The counterexample above disproves Conjecture 1.3.