1 Introduction
We study finite 2-designs admitting a great deal of symmetry, and explore several extreme cases suggested by bounds on the so-called Delandtsheer–Doyen parameters. We consider 2-\((v, k, \lambda )\) designs: these are structures \({\mathscr {D}}= ({\mathscr {P}},{\mathscr {B}})\) with two types of objects called points (elements of \({\mathscr {P}}\)) and blocks (elements of \({\mathscr {B}}\)). There are \(v = |{\mathscr {P}}|\) points, and we require that each block is a k-subset of \({\mathscr {P}}\), and that each pair of distinct points lies in exactly \(\lambda \) blocks. As a consequence of these conditions, the number r of blocks containing a given point is also constant. The standard parameters associated with a 2-\((v, k, \lambda )\) design are v, k, r, \(\lambda \), and the number \(b = |{\mathscr {B}}|\) of blocks, and we note that v, k, \(\lambda \) determine b and r. Additional Delandtsheer–Doyen parameters arise under certain symmetry conditions: automorphisms of \({\mathscr {D}}\) (permutations of \({\mathscr {P}}\) leaving \({\mathscr {B}}\) invariant) act on points, blocks, and flags (incident point-block pairs), and the following implications hold for transitivity of a subgroup \(G \leqslant \text {Aut}({\mathscr {D}})\) in these actions (the second implication follows from Block’s Lemma, see [8, (2.3.2)]):
A celebrated result from 1961 of Higman and McLaughlin [11], for 2-designs with \(\lambda = 1\), shows that flag-transitivity implies point-primitivity for these designs. Generalising this result, several other conditions on the parameters of a 2-\((v,k,\lambda )\) design were given in the 1960s by Dembowski [8, (2.3.7)] and Kantor [14, Theorems 4.7, 4.8] under which flag-transitivity implies point-primitivity. On the other hand, examples were known of block-transitive groups which were not point-primitive, such as the ones we present in Example 4.1. Nevertheless it was hoped that (in some sense) most block-transitive groups on 2-designs would be point-primitive (to allow use of the powerful theory for primitive permutation groups). This hope was realised by Delandtsheer and Doyen [7] in 1989. Indeed a recent paper of Zhan et al [21] shows how these two methods (the approach in [7] for point-imprimitive designs and the theory of primitive permutation groups for the point-primitive ones) can be applied to make very significant progress towards a complete classification of block-transitive 2-designs with a fixed block size k, namely for \(k=4\) in [21]; see a brief discussion in Remark 4.5. The theorem of Delandtsheer and Doyen, which we state below, implies that every block-transitive group will be point-primitive provided that the number of points is large enough, specifically \(v > \left( \left( {\begin{array}{c}k\\ 2\end{array}}\right) - 1\right) ^2\) is sufficient. For a block-transitive group preserving a non-trivial point-partition, an unordered pair of points contained in the same class of the partition is called an inner pair, and is called an outer pair if the two points lie in different classes. Since the group is block-transitive, the numbers of inner pairs and outer pairs in a block B are constants, independent of the choice of \(B\in {\mathscr {B}}\), and their sum is \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) \).flag-transitive \(\Rightarrow \) block-transitive \(\Rightarrow \) point-transitive.
Theorem 1.1
[7, Theorem] Let \({\mathscr {D}}= ({\mathscr {P}}, {\mathscr {B}})\) be a 2-\((v, k, \lambda )\) design, let \(B \in {\mathscr {B}}\), and let \(G \leqslant \text {Aut}({\mathscr {D}})\) be block-transitive. Suppose that \(v = cd\) for some integers \(c \geqslant 2\) and \(d \geqslant 2\), and that G leaves invariant a partition \({\mathscr {C}}\) of \({\mathscr {P}}\) with d classes, each of size c. Then there exist positive integers m and n such thatMoreover, n is the number of inner pairs contained in B and mc is the number of outer pairs contained in B.
$$\begin{aligned} c = \frac{\left( {\begin{array}{c}k\\ 2\end{array}}\right) - n}{m} \quad \text {and} \quad d = \frac{\left( {\begin{array}{c}k\\ 2\end{array}}\right) - m}{n}. \end{aligned}$$
(1)
Advertisement
We call the integers (m, n) the Delandtsheer–Doyen parameters for \({\mathscr {D}}\) (relative to G and \({\mathscr {C}}\)). A major open question regarding these numbers is:
Question 1
Which Delandtsheer–Doyen parameters (m, n) are possible?
While these numbers have combinatorial significance, as given by Theorem 1.1, the purpose of this paper is to report on restrictions we discovered that the Delandtsheer–Doyen parameters place on the action of the group G. Let \(K = G^{\mathscr {C}}\) denote the subgroup of \(\text {Sym}({\mathscr {C}})\) induced by G, and for \(C \in {\mathscr {C}}\), let \(H = G_C^C\) denote the subgroup of \(\text {Sym}(C)\) induced on C by its setwise stabiliser \(G_C\). By the Embedding Theorem [19, Theorem 5.5], we may assume that \(G \leqslant H \wr K \leqslant \text {Sym}(C) \wr \text {Sym}({\mathscr {C}}) \cong \text {Sym}(c) \wr \text {Sym}(d)\) in its imprimitive action on \({\mathscr {P}}= {\mathbb {Z}}_c \times {\mathbb {Z}}_d\). For a transitive subgroup \(X \leqslant \text {Sym}(\Omega )\), the rank of X is the number \(\text {Rank}(X)\) of orbits in \(\Omega \) of a point stabiliser \(X_\alpha \) (for \(\alpha \in \Omega \)); and \(\text {Rank}(X)\) is also equal to the number of X-orbits in \(\Omega \times \Omega \), see [19, Lemma 2.28]. Similarly we denote by \(\text {PairRank}(X)\) the number of X-orbits on the unordered pairs of distinct points from \(\Omega \), and it is not difficult to see that \((\text {Rank}(X)-1)/2 \leqslant \text {PairRank}(X)\leqslant \text {Rank}(X)-1\). A summary of the major restrictions we obtain on the Delandtsheer–Doyen parameters is given by the following theorem.
Theorem 1.2
Let \({\mathscr {D}}\), G, \({\mathscr {C}}\), c, d, m, and n be as in Theorem 1.1. Let \(C \in {\mathscr {C}}\) and \(H = G_C^C\), \(K = G^{\mathscr {C}}\). Then
$$\begin{aligned} \frac{\text {Rank}(H)-1}{2} \leqslant \text {PairRank}(H)\leqslant n, \quad \text{ and }\quad \frac{\text {Rank}(K)-1}{2} \leqslant \text {PairRank}(K)\leqslant m. \end{aligned}$$
Advertisement
Theorem 1.2 follows immediately from Proposition 3.2, which contains additional detailed information about the permutation actions of the groups H and K. Refining Question 1 we might ask:
Question 2
For what values of (m, n) can we have \(\text {Rank}(H) = 2n + 1\) and \(\text {Rank}(K) = 2m + 1\)? For what values of (m, n) can we have \(\text {PairRank}(H) = n\) and \(\text {PairRank}(K) = m\)?
Some rather incomplete answers to Question 2 may be deduced from certain results and examples of block-transitive designs in [6, 16, 17]. Examining these from the point of view of the Delandtsheer–Doyen parameters, we obtain the next result.
Proposition 1.3
(a)
For any \(N > 0\), there exists an example in Theorem 1.2 with
\(\text {Rank}(H)\) \(= 2n + 1\), \(\text {Rank}(K) = 2m + 1\), and with both \(n, m > N\).
(b)
For any \(k \geqslant 3\), there exist examples in Theorem 1.2 with \(m=n=\text {PairRank}(H) = \text {PairRank}(K) = 1\), but with \(\text {Rank}(H) = \text {Rank}(K) = 2\).
(c)
There exists a 2-\((cd, k, \lambda )\) design \({\mathscr {D}}\) (for some \(\lambda \)) in Theorem 1.2 with \(n = m = 1\), and \(\max \{ \text {Rank}(H), \text {Rank}(K) \} = 3\), if and only if \(k = 8\) and \(c = d = 27\). Moreover, in the case \(\lambda = 1\), there are up to isomorphism exactly 467 such designs.
We note that additional examples may be constructed of block-transitive, point-imprimitive 2-\((729, 8, \lambda )\) designs in Proposition 1.3(c) using the technique from [6, Proposition 1.1] applied to a subgroup of \(\text {Sym}(c) \wr \text {Sym}(c)\) properly containing the group G of Theorem 1.2. Such examples will have larger values of \(\lambda \). Also we note that additional examples for the case \(k=4\) in Proposition 1.3(b) may be found in [21]. Proposition 1.3 will be proved in Sect. 4.
In the final Sect. 5 we present a new design construction that yields additional pairs (m, n) with the second property requested in Question 2. The construction is different from, but was inspired by, the design construction in [6, Proposition 2.2]. We believe that our construction produces an infinite family of examples, but justification for this relies on two number theoretic conjectures which we comment on in Sect. 1.1. The construction in Sect. 5 requires integer pairs [n, c] with the following property.
Definition 1.4
An integer pair [n, c] is said to be useful if the following two conditions hold:
(1)
\(n \geqslant 2\) and c is a prime power such that \(c \equiv 1 \pmod {2n}\); and
(2)
\(c + n = \left( {\begin{array}{c}k\\ 2\end{array}}\right) \) for some integer \(k \geqslant 2n\).
We show in Lemma 5.3 that for useful pairs [n, c], the value of k satisfies \(2n + 2 \leqslant k \leqslant n + d\), where \(d = 1 + (c-1)/n\). Table 1 gives a list of all useful pairs [n, c] such that \(n \leqslant 20\) and \(c \leqslant 1300\), together with the corresponding values of k and d. In addition, for \(n\in \{11, 13, 16, 18\}\), the table contains the parameters c, k, d, for the smallest value of c such that [n, c] is useful. We note that the only integers n in the range \(2\leqslant n\leqslant 20\) which do not appear in the table are \(n\in \{6, 10, 15\}\), and we prove in Lemma 5.6 that for these three values of n there is no c such that [n, c] is a useful pair.
Table 1
Examples of useful pairs [n, c], together with the values for k and d
We are principally interested in which values of n are possible since, in our design Construction 5.4 based on a useful pair [n, c], the Delandtsheer–Doyen parameters turn out to be (1, n). Moreover, these designs also satisfy the bounds \(\text {PairRank}(H) = n\) and \(\text {PairRank}(K) = 1\) in Question 2 (see Theorem 5.5). The following theorem is an immediate consequence of Theorem 5.5.
Theorem 1.5
Suppose that [n, c] is useful with \(c + n = \left( {\begin{array}{c}k\\ 2\end{array}}\right) \), and let \(d = 1 + (c-1)/n\). Then there exists a 2-\((cd, k, \lambda )\) design (for some \(\lambda \)) admitting a block-transitive, point-imprimitive group \(H \wr K\) with \(H \leqslant \text {Sym}(c)\) and \(K = \text {Sym}(d)\), and with Delandtsheer–Doyen parameters (1, n) such that \(\text {Rank}(H) = \text {PairRank}(H) + 1 = n + 1\) and \(\text {Rank}(K) = \text {PairRank}(K) + 1 = 2\).
Apart from the examples given to prove Proposition 1.3, Theorems 1.5, and 5.5, Questions 1 and 2 are in general wide open, and we would be very interested in knowing more general answers. In particular, we note that Theorem 1.5 does not produce designs with Delandtsheer–Doyen parameters (1, n) for \(n=6, 10\) or 15 (Lemma 5.6). Nevertheless there might be alternative constructions with Delandtsheer–Doyen parameters (1, n) for such n.
Question 3
For which values of n do examples exist with Delandtsheer–Doyen parameters (1, n), and with \((\text {PairRank}(K), \text {PairRank}(H))=(1,n)\)? Are there examples for all n?
In particular, it would be good to know for which values of n there exists at least one useful pair [n, c]. We finish this introductory section with some commentary on number theoretic questions related to the existence of useful pairs.
1.1 Useful pairs and conjectures from number theory
By Dirichlet’s Theorem on arithmetic progressions (see [20, Chap. VIII.1]), for any positive integer n, there exist infinitely many primes c such that \(c \equiv 1 \pmod {2n}\). However it is unclear how many such pairs [n, c] sum to a triangular number \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) \). In the light of Dirichlet’s Theorem and the relatively large number of useful pairs of the form [2, c] we found with \(c < 1300\), we asked, in an earlier version of this paper [3]:
Question 4
Are there infinitely many prime powers c such that [2, c] is a useful pair?
This question, and our discussion in [3] of its links with the Bunyakovsky Conjecture in Number Theory, attracted the attention of Gareth Jones and Alexander Zvonkin who had worked on a somewhat similar problem concerning projective primes [12]. They applied their methods and heuristics to our questions and found 12, 357, 532 integers \(t\leqslant 10^8\) such that \(c(t):=\left( {\begin{array}{c}8t+3\\ 2\end{array}}\right) -2\) is a prime and [2, c(t)] is a useful pair, and hence corresponds to a 2-design in Theorem 5.5, see [13, Table 2]. This means that, for a uniformly distributed random positive integer \(t\leqslant 10^8\), the probability that [2, c(t)] is a useful pair is approximately 0.12 - more that one chance in nine. We are excited by the extensive discussions which ensued between Gareth, Alexander and the authors, and we present here a modified commentary from the one given in [3]. In particular, although Question 4 remains open we feel optimistic that the answer should be a resounding ‘yes’.
The conditions for [n, c] to be useful imply in particular that, if \(k\equiv r\pmod {4n}\), then \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) \equiv \left( {\begin{array}{c}r\\ 2\end{array}}\right) \equiv n+1\pmod {2n}\). Thus, for fixed integers n, r such that \(n\geqslant 2\), \(1\leqslant r<4n\), and \(\left( {\begin{array}{c}r\\ 2\end{array}}\right) \equiv n+1\pmod {2n}\), we seek integers of the form \(k=4nt+r\), with \(k\geqslant 2n\), such that \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) -n=c\) is a prime power. In other words, we seek non-negative integers t such that the value of the following quadratic polynomialis equal to a prime power c. In summary, [n, c] is a useful pair if and only if c is a prime power arising as \(f_{n,r}(t)\) for some t. For example, if \(n=2\) and \(r=3\), then \(f_{2,3}(t)=32t^2+20t+1\). It was this polynomial, exhibited in our earlier draft, which Jones and Zvonkin first studied, seeking integers t such that \(f_{2,3}(t)\) is a prime. Although we are interested in the larger class of integers which evaluate to prime powers, it is the primes which dominate: for example in the range \(1\leqslant t\leqslant 10^7\), there are 1, 405, 448 integers t for which \(f_{2,3}(t)\) is a prime but only eight integers giving proper prime powers [13, Sects. 11.1 and 13].
$$\begin{aligned} f(t)= f_{n,r}(t) = 8n^2t^2 + 2n(2r-1)t + \left( \frac{r(r-1)}{2}-n\right) \end{aligned}$$
(2)
In 1857, the Russian mathematician Viktor Bunyakovsky (or Bouniakowsky) studied integer polynomials f(t) for which the sequence \(f(1),f(2),f(3),\ldots \) contains infinitely many primes. He observed first that such polynomials f must satisfy the following three conditions: and then, in [5], he conjectured that these three conditions are also sufficient to ensure that f(t) is a prime for infinitely many positive integers t. For example, the three conditions are satisfied by the polynomial \(f_{n,r}(t)\) if and only if n is not a triangular number \(\left( {\begin{array}{c}a\\ 2\end{array}}\right) \), for some integer a, see [13, Lemma 8.1]. In particular \(f_{2,3}(t)\) satisfies all three conditions and hence the Bunyakovsky Conjecture implies a positive answer to Question 4.
(i)
The leading coefficient is positive;
(ii)
The polynomial is irreducible over the integers; and
(iii)
\(\gcd (f(1),f(2),f(3),\ldots )=1\) (or equivalently, f is not identically zero
modulo any prime p);
Unfortunately the Bunyakovsky Conjecture is still open, apart from the degree 1 case which is Dirichlet’s Theorem. In 1962 the conjecture was refined by Bateman and Horn [4] who proposed an approximation E(x) for the number of positive integers \(t\leqslant x\) for which f(t) is prime. Then very recently Li [15] suggested an improved version of the Bateman–Horn estimate, namelythe infinite product being over all primes p, and \(\omega _f(p)\) being the number of solutions of the equation \(f(t)=0\) in the field of order p. A recent helpful discussion of links between the Bateman–Horn and Bunyakovsky Conjectures (and other conjectures) may be found in [2].
$$\begin{aligned} E(x) = C(f)\cdot \int _{2}^{x} \frac{dt}{\ln (f(t))},\ \text{ where }\ C(f)=\prod _p \left( 1-\frac{1}{p}\right) ^{-1} \left( 1-\frac{\omega _f(p)}{p}\right) , \end{aligned}$$
In [13, Sects. 9–11], Jones and Zvonkin report on the very interesting and encouraging results of their investigations. In particular they show that if \(f_{n,r}(t)\) does not satisfy the three Bunyakovsky conditions, then \(f_{n,r}(t)\) is reducible [13, Lemma 8.1] and the only possible prime power value \(f_{n,r}(t)\), for \(t\geqslant 0\), is \(f_{n,r}(0)\), [13, Proposition 13.2]; indeed this can happen as seen in Table 1 above, for example \(f_{3,8}(0)= 25\). For the general case where the three Bunyakovsky conditions hold, Jones and Zvonkin determine both the estimates E(x), and also the exact numbers Q(x) of integers \(t\leqslant x\) giving prime values f(t), for various polynomials \(f_{n,r}(t)\) as in (2) for \(1\leqslant t\leqslant 10^8\), namely they study the pairs n, r suggested by our examples in Table 1 with \(n\in \{2, 4, 5, 7, 8, 9\}\). In all cases they found that the Bateman–Horn–Li estimate E(x) is a very good predictor of the true number Q(x) of prime values, for example,
Their data provides persuasive evidence for the truth of the Bunyakovsky Conjecture and Bateman–Horn estimate. Moreover, their enumerations have produced more that \(232\times 10^6\) useful pairs [n, c] with \(n\in \{2,4,5,7,8,9\}\) and c prime, and with this encouraging evidence we ask:for \(f=f_{2,3}\) and \(t\leqslant 10^8\), \(Q(x) = 12,357,532\) and \(E(10^8)=12,362,961.06\).
Question 5
For which integers n do there exist infinitely many useful pairs [n, c]?
2 Permutation group concepts
Let X be a transitive permutation group on a set \(\Omega \). An X-orbital is an X-orbit in \(\Omega \times \Omega \). Clearly, \(\{ (\alpha ,\alpha ) \ | \ \alpha \in \Omega \}\) is an orbital and is called the trivial orbital; all other orbitals are said to be non-trivial.
For any X-orbital \(\Delta \) and any \(\alpha \in \Omega \), the set \(\Delta (\alpha ) = \{ \beta \ | \ (\alpha ,\beta ) \in \Delta \}\) is an \(X_\alpha \)-orbit, and is called a suborbit of X. The set of X-orbitals is in one-to-one correspondence with the set of all \(X_\alpha \)-orbits in \(\Omega \), such that the orbital \(\Delta \) corresponds to the \(X_\alpha \)-orbit \(\Delta (\alpha )\). In particular, the trivial orbital corresponds to the trivial suborbit \(\{\alpha \}\).
The cardinality \(|\Delta (\alpha )|\) is a subdegree of X, and the number of X-orbitals (including the trivial orbital) is the rank of X, denoted \(\text {Rank}(X)\).
For each X-orbital \(\Delta \), the set \(\Delta ^* = \{ (\beta ,\alpha ) \ | \ (\alpha ,\beta ) \in \Delta \}\) is also an X-orbital, called the paired orbital of \(\Delta \). If \(\Delta = \Delta ^*\), then \(\Delta \) is said to be self-paired. For any \(\alpha \in \Omega \), the set \(\Delta (\alpha ) \cup \Delta ^*(\alpha )\) is therefore either a single suborbit, or the union of two suborbits of equal lengths. We call the cardinalitythe symmetrised subdegree corresponding to \(\Delta \) (or to \(\Delta ^*\)). Note that \(u_\Delta = \delta _\Delta |\Delta (\alpha )|\) where \(\delta _\Delta = 1\) or 2 according as \(\Delta (\alpha )\) is self-paired or not. Let \({\mathscr {O}}_X\) denote the set of all \(\{\Delta , \Delta ^*\}\), where \(\Delta \) is a non-trivial X-orbital. Then \({\mathscr {O}}_X\) is in one-to-one correspondence with the set of X-orbits on the unordered pairs of distinct points from \(\Omega \), and we call \(|{\mathscr {O}}_X|\) the pair-rank of X, denoted \(\text {PairRank}(X)\). It follows from the definition thatGiven permutation groups \(H\leqslant \text {Sym}(\Sigma )\) and \(K\leqslant \text {Sym}(d)\), acting on sets \(\Sigma \) and \({\mathbb {Z}}_d=\{1,\dots ,d\}\) respectively, the wreath product \(H\wr K = H^d\rtimes K\) acts (imprimitively) on \(\Sigma \times {\mathbb {Z}}_d\) as follows (see [19, Lemma 5.4]):This action leaves invariant the partition \({\mathscr {C}}\) of \(\Sigma \times {\mathbb {Z}}_d\) with classes \(C_j = \{ (x,j) \mid x \in \Sigma \}\) for \(j \in {\mathbb {Z}}_d\). The direct product \(H\times K\) also acts (in product action) on \(\Sigma \times {\mathbb {Z}}_d\) as followsand leaves invariant both the partition \({\mathscr {C}}\) and also the partition with classes \(C_x'=\{(x,j) \mid j \in {\mathbb {Z}}_d \}\) for \(x \in \Sigma \).
$$\begin{aligned} u_\Delta := \big |\Delta (\alpha ) \cup \Delta ^*(\alpha )\big | \end{aligned}$$
$$\begin{aligned} \text {PairRank}(X) + 1 \leqslant \text {Rank}(X) \leqslant 2\,\text {PairRank}(X) + 1. \end{aligned}$$
(3)
$$\begin{aligned} (x,j)^{(h_1,\dots ,h_d)\sigma } = \left( x^{h_j},j^\sigma \right) , \quad \text{ for }\ (h_1,\dots ,h_d) \in H^d, \sigma \in K, \text{ and }\ (x,j) \in \Sigma \times {\mathbb {Z}}_d. \end{aligned}$$
(4)
$$\begin{aligned} (x,i)^{(h, \sigma )} = \left( x^{h},i^\sigma \right) ,\ \text{ for }\ h\in H, \sigma \in K \end{aligned}$$
(5)
3 Proof of Theorem 1.2
Let \({\mathscr {D}}= ({\mathscr {P}},{\mathscr {B}})\) be a 2-\((v, k, \lambda )\) design, with \(v = cd\) for some integers \(c \geqslant 2\) and \(d \geqslant 2\). Suppose that \(G \leqslant \text {Aut}({\mathscr {D}})\) is transitive on the block set \({\mathscr {B}}\) and leaves invariant a non-trivial partition \({\mathscr {C}}\) of \({\mathscr {P}}\) with d classes \(C_1, \ldots , C_d\), each of size c. The following lemma establishes useful identities between the parameters.
Lemma 3.1
Let \({\mathscr {D}}\), \({\mathscr {C}}\), c, d be as above. Let m and n satisfy Eq. (1). Then the following identities hold.
(a)
\(cd-1= \left( {\begin{array}{c}k\\ 2\end{array}}\right) \cdot \frac{c-1}{n} = \left( {\begin{array}{c}k\\ 2\end{array}}\right) \cdot \frac{d-1}{m}\);
(b)
\(m(c-1)=n(d-1)\);
(c)
The number of blocks is \(|{\mathscr {B}}| =\frac{ cd(c-1)\lambda }{2n}=\frac{ cd(d-1)\lambda }{2m}\).
Proof
(a)
By Eq. (1), we have
$$\begin{aligned} cd - 1 = \frac{\left( {\begin{array}{c}k\\ 2\end{array}}\right) - n}{m} \cdot \frac{\left( {\begin{array}{c}k\\ 2\end{array}}\right) - m}{n} - 1 = \frac{\left( {\begin{array}{c}k\\ 2\end{array}}\right) \left( \left( {\begin{array}{c}k\\ 2\end{array}}\right) - n - m\right) }{nm} = \left( {\begin{array}{c}k\\ 2\end{array}}\right) \cdot \frac{c-1}{n} = \left( {\begin{array}{c}k\\ 2\end{array}}\right) \cdot \frac{d-1}{m}. \end{aligned}$$
(b)
Part (b) follows immediately from Part (a).
(c)
Note that \( \lambda (v-1) = r(k-1)\) and \( vr = bk\) (see for instance [8, (5) on p. 57]), and so \(|{\mathscr {B}}| = v(v-1)\lambda /(k(k-1)) = cd(cd-1)\lambda /(k(k-1))\). Hence \(|{\mathscr {B}}| = cd(c-1)\lambda /(2n)=cd(d-1)\lambda /(2m)\) using Part (a).
Let \(K = G^{\mathscr {C}}\) denote the induced action of G on the set \({\mathscr {C}}= \{C_1, \ldots , C_d\}\) of imprimitivity classes, and for \(C \in {\mathscr {C}}\) let \(H = G_C^C\) denote the induced action on C of the setwise stabiliser \(G_C\). Then by the Embedding Theorem for transitive permutation groups (see [19, Theorem 5.5]), we may assume that \(G \leqslant H \wr K \leqslant \text {Sym}(C) \wr \text {Sym}({\mathscr {C}}) \cong \text {Sym}(c) \wr \text {Sym}(d)\) with the action as in (4).
Let \(X = H^d = H_1 \times \cdots \times H_d\) be the base group of the wreath product \(H \wr K\), such that for each \(i \in \{1, \ldots , d\}\), \(H_i \cong H\) and \(H_i\) induces H on \(C_i\) and fixes all other classes pointwise. Let \(\Sigma \) be a non-trivial H-orbital. Then for each i, there is a corresponding \(H_i\)-orbital \(\Sigma _i\) for the action of \(H_i\) on \(C_i\).
Proposition 3.2
Let \({\mathscr {D}}\) and G be as above and let \(B \in {\mathscr {B}}\). Let m and n be as in Theorem 1.1.
(a)
For a non-trivial orbital \(\Delta \) of K with symmetrised subdegree \(u_\Delta \), the number \(nu_\Delta /(c-1)\) is an integer and there are exactly \(cn u_\Delta /(c-1)\) pairs \(\{\alpha , \beta \}\) in B such that \(\alpha \in C_i\) and \(\beta \in C_j\) for some \((C_i,C_j) \in \Delta \). Moreover, \((\text {Rank}(K)-1)/2 \leqslant \text {PairRank}(K) \leqslant m\).
(b)
For a non-trivial orbital \(\Sigma \) of H with symmetrised subdegree \(u_\Sigma \), the number \(n u_\Sigma /(c-1)\) is an integer and is equal to the number of pairs \(\{\alpha , \beta \}\) in B such that \((\alpha ,\beta ) \in \Sigma _i\) for some \(i \in \{1, \ldots , d\}\). Moreover, \((\text {Rank}(H)-1)/2 \leqslant \text {PairRank}(H) \leqslant n\).
Part of (a) is proved in [17, Lemma 2.1], but with different notation so we give brief details here (note that our parameter \(u_\Delta \) is equal to the expression \(2u/\delta \) in that reference).
Proof
We first prove part (a). For \(\Delta \) a non-trivial orbital of K, letThe number of choices of \((C_i,C_j)\) is \(|\Delta | = d|\Delta (C_i)| = du_\Delta /\delta _\Delta \), and for each choice, there are \(c^2\) pairs \(\{\alpha ,\beta \} \in {\mathscr {S}}(\Delta )\) with \(\alpha \in C_i, \beta \in C_j\). If \(\Delta = \Delta ^*\), that is, if \(\delta _\Delta = 1\), then we have counted each unordered pair \(\{\alpha ,\beta \} \in {\mathscr {S}}(\Delta )\) twice so \(|{\mathscr {S}}(\Delta )| = c^2du_\Delta /2\), while if \(\Delta \ne \Delta ^*\), that is, if \(\delta _\Delta = 2\), then there is no double counting, and \(|{\mathscr {S}}(\Delta )| = c^2du_\Delta /\delta _\Delta = c^2du_\Delta /2\). Hence \(|{\mathscr {S}}(\Delta )| = c^2du_\Delta /2\) in either case.
$$\begin{aligned} {\mathscr {S}}(\Delta ) = \big \{ \{\alpha ,\beta \} \ | \ \alpha \in C_i, \ \beta \in C_j \ \text {for some} \ (C_i,C_j) \in \Delta \big \}. \end{aligned}$$
Since G leaves \({\mathscr {S}}(\Delta )\) invariant and is transitive on \({\mathscr {B}}\), each block B contains the same number of pairs from \({\mathscr {S}}(\Delta )\), say \(n_\Delta \) pairs. Thus, counting pairs \((\{\alpha ,\beta \}, B)\) with \(\{\alpha ,\beta \} \in {\mathscr {S}}(\Delta )\), \(B \in {\mathscr {B}}\), and \(\{\alpha ,\beta \} \subseteq B\), we obtain \(|{\mathscr {B}}| n_\Delta = \lambda |{\mathscr {S}}(\Delta )| = \lambda c^2du_\Delta /2\). Since \(|{\mathscr {B}}| = cd(c-1)\lambda /(2n)\) by Lemma 3.1(c), it follows that \(n_\Delta = cnu_\Delta /(c-1)\). In particular \(nu_\Delta /(c-1)\) is an integer.
Note that \({\mathscr {S}}(\Delta ^*) = {\mathscr {S}}(\Delta )\), and that each outer pair in B lies in exactly one of the sets \({\mathscr {S}}(\Delta )\). Thus the number of outer pairs in B, namely mc by Theorem 1.1, is equal to the sum of the \(n_\Delta \) over the set \({\mathscr {O}}_K\) of all pairs \(\{\Delta ,\Delta ^*\}\) of non-trivial K-orbitals; that is,Since each \(nu_\Delta /(c-1)\) is an integer, each term of the summation above is a positive integer multiple of c. Hence m is greater than or equal to \(|{\mathscr {O}}_K|\) which, as we noted in Sect. 2, is equal to \(\text {PairRank}(K)\). Thus, using (3),Now we prove part (b). Let \(\Sigma \) be a non-trivial orbital of H. Note that \(|\Sigma | = c|\Sigma (\alpha )| = cu_\Sigma /\delta _\Sigma \) and that, for each \(i\leqslant d\), there is a corresponding \(H_i\)-orbital \(\Sigma _i\). LetSince G is transitive on \({\mathscr {C}}\), the set \({\mathscr {S}}'(\Sigma )\) contains equally many pairs from each class in \({\mathscr {C}}\). So for a fixed class \(C \in {\mathscr {C}}\), and viewing \(\Sigma \) as an H-orbital in \(C\times C\),If \(\Sigma = \Sigma ^*\) then \(\delta _\Sigma = 1\) and each unordered pair \(\{\alpha ,\beta \} \in {\mathscr {S}}'(\Sigma )\) from C is counted twice (since both \((\alpha ,\beta )\) and \((\beta ,\alpha )\) lie in \(\Sigma \)), so \(|{\mathscr {S}}'(\Sigma )| = d|\Sigma |/2 = dcu_\Sigma /2\). On the other hand, if \(\Sigma \ne \Sigma ^*\), then \(\delta _\Sigma = 2\) and \(|{\mathscr {S}}'(\Sigma )| = d|\Sigma | = dcu_\Sigma /2\). Hence in both cases \(|{\mathscr {S}}'(\Sigma )| = dcu_\Sigma /2\). Since G leaves \({\mathscr {S}}'(\Sigma )\) invariant and is transitive on \({\mathscr {B}}\), each block B contains the same number of pairs from \({\mathscr {S}}'(\Sigma )\), say \(n_\Sigma \) pairs. Thus, counting pairs \((\{\alpha ,\beta \},B)\) with \(\{\alpha ,\beta \} \in {\mathscr {S}}'(\Sigma )\), \(B \in {\mathscr {B}}\), and \(\{\alpha ,\beta \} \subseteq B\), we obtain \(|{\mathscr {B}}|n_\Sigma = \lambda |{\mathscr {S}}'(\Sigma )| = \lambda dcu_\Sigma /2\). Using Lemma 3.1(c) we obtain that \(n_\Sigma =nu_\Sigma /(c-1).\) In particular, \(nu_\Sigma /(c-1)\) is a positive integer. Note that \({\mathscr {S}}'(\Sigma ) = {\mathscr {S}}'(\Sigma ^*)\) for any non-trivial H-orbital \(\Sigma \), and that each inner pair in B lies in exactly one of the sets \({\mathscr {S}}'(\Sigma )\). Thus the number of inner pairs in B is equal to the sum of the numbers \(n_\Sigma \) over the set \({\mathscr {O}}_H\) of all pairs \(\{\Sigma ,\Sigma ^*\}\) of non-trivial H-orbitals. HenceSo, using (3), \(n \geqslant |{\mathscr {O}}_H| = \text {PairRank}(H) \geqslant (\text {Rank}(H) - 1)/2\), which completes the proof. \(\square \)
$$\begin{aligned} mc = \sum _{\{\Delta ,\Delta ^*\} \in {\mathscr {O}}_K} \frac{cnu_\Delta }{c-1}. \end{aligned}$$
$$\begin{aligned} m \geqslant |{\mathscr {O}}_K| = \text {PairRank}(K) \geqslant (\text {Rank}(K) - 1)/2. \end{aligned}$$
$$\begin{aligned} {\mathscr {S}}'(\Sigma ) = \big \{ \{\alpha ,\beta \} \ | \ (\alpha ,\beta ) \in \Sigma _i \ \text {for some} \ i \in \{1, \ldots , d\} \big \}. \end{aligned}$$
$$\begin{aligned} |{\mathscr {S}}'(\Sigma )|&= d \cdot \big |\big \{ \{\alpha ,\beta \} \ | \ \alpha , \beta \in C; \ \{\alpha ,\beta \} \in {\mathscr {S}}'(\Sigma ) \big \}\big | \\&= d \cdot \big |\big \{ \{\alpha ,\beta \} \ | \ (\alpha ,\beta ) \in \Sigma \big \}\big |. \end{aligned}$$
$$\begin{aligned} n = \sum _{\{\Sigma ,\Sigma ^*\} \in {\mathscr {O}}_H} \frac{n u_\Sigma }{c-1}. \end{aligned}$$
(6)
Proposition 3.2 has the following corollary. It is easy to prove: the condition \(m = 1\) implies by Proposition 3.2(a) that \(\text {PairRank}(K) = 1\), that is to say, K is transitive on unordered pairs of distinct classes of \({\mathscr {C}}\). This means in particular that K is primitive on \({\mathscr {C}}\), see [19, Lemma 2.30]. Similarly, \(n = 1\) implies that H is primitive on C. Part (b) of this corollary was proved also in [17, Lemma 2.3].
Corollary 3.3
Let \({\mathscr {D}}\), G, H, K, \({\mathscr {C}}\), C, m, and n be as in Proposition 3.2.
(a)
If \(m = 1\) then K is primitive on \({\mathscr {C}}\).
(b)
If \(n = 1\) then H is primitive on C.
Our last result of this section looks at cases where the upper bound on \(\text {Rank}(K)\) or \(\text {Rank}(H)\) is sharp. A transitive permutation group is 3/2-transitive if all its non-trivial suborbits have the same size.
Lemma 3.4
(a)
\(\text {Rank}(H) = 2n + 1\) implies that |H| is odd, and H is 3/2-transitive on C with all \(H_\alpha \)-orbits in \(C \setminus \{\alpha \}\) of size \((c-1)/(2n)\);
(b)
\(\text {Rank}(K) = 2m + 1\) implies that |K| is odd, and K is 3/2-transitive on \({\mathscr {C}}\) with all \(K_C\)-orbits in \({\mathscr {C}}\setminus \{C\}\) of size \((d-1)/(2m)\).
Proof
Suppose first that \(\text {Rank}(H) = 2n + 1\). By Proposition 3.2, \((\text {Rank}(H) - 1)/2 \leqslant |{\mathscr {O}}_H| = \text {PairRank}(H) \leqslant n\). Our assumption that \(\text {Rank}(H) = 2n + 1\) therefore implies that equality holds, and hence \(\Sigma \ne \Sigma ^*\) for each non-trivial H-orbital \(\Sigma \). By a result on permutation groups (see, for instance, [19, Lemma 2.27]), H has odd order. Also \(|{\mathscr {O}}_H| = n\), and by Proposition 3.2, each of the n summands in (6) is a positive integer. Hence each of these summands is equal to 1, that is, \(u_\Sigma = (c-1)/n\) for each non-trivial H-orbital \(\Sigma \). Thus, for each such \(\Sigma \), we have \(|\Sigma (\alpha )| = u_\Sigma /2 = (c-1)/(2n)\) since \(\Sigma \ne \Sigma ^*\), and in particular H is 3/2-transitive on C. The proof of part (b) is similar. \(\square \)
4 Exploring examples: Proof of Proposition 1.3
In this section we explore the examples required to prove Proposition 1.3, and we also discuss the results of [21] in Remark 4.5. For the first part we investigate the class of projective plane examples given in [17, Example on p. 232] and mentioned in [18, p. 312]. We show that these examples satisfy all the conditions in Lemma 3.4 parts (a) and (b), and that in this family there are designs for which the Delandtsheer–Doyen parameters are (simultaneously) arbitrarily large. This therefore will prove Proposition 1.3(a).
Example 4.1
Let q be a prime power such that \(q^2 + q + 1\) is not prime, say \(q^2 + q + 1 = cd\) where \(c, d \geqslant 2\). Let \({\mathscr {D}}= ({\mathscr {P}},{\mathscr {B}})\) where \({\mathscr {P}}\) and \({\mathscr {B}}\) are the points and lines, respectively, of the Desarguesian projective plane \(\text {PG}_2(q)\). Then \(v = |{\mathscr {P}}| = q^2 + q + 1 = cd\) and \(k = q+1\). Let G be a Singer cycle, that is, a cyclic subgroup of automorphisms of \({\mathscr {D}}\) of order cd acting regularly on \({\mathscr {P}}\). Then G is also transitive (in fact regular) on \({\mathscr {B}}\) (see [8, Result 1 of Sect. 2.3]). Also G preserves a partition \({\mathscr {C}}\) of \({\mathscr {P}}\) into d classes of size c, namely the set of orbits in \({\mathscr {P}}\) of the unique cyclic (normal) subgroup of G of order c.
The information given in Example 4.1 tells us that \({\mathscr {D}}\) is a 2-\((cd, q+1, 1)\) design admitting \(G = {\mathbb {Z}}_{cd}\) as a point-imprimitive, block-transitive group of automorphisms. We now prove the other assertions mentioned above.
Lemma 4.2
Let \({\mathscr {D}}\), G, \({\mathscr {C}}\) be as in Example 4.1.
(a)
The Delandtsheer–Doyen parameters (m, n) for \({\mathscr {D}}\) relative to G and \({\mathscr {C}}\) are
$$\begin{aligned} m = \frac{d-1}{2} \quad \text{ and } \quad n = \frac{c-1}{2}. \end{aligned}$$
(b)
The group G is permutationally isomorphic to a subgroup of \(H \wr K\) where \(H = {\mathbb {Z}}_c\), the group induced on a class of \({\mathscr {C}}\), and \(K = {\mathbb {Z}}_d\), the group induced on \({\mathscr {C}}\).
(d)
For any \(N > 0\) there exists q such that \(q^2+q+1 = cd\) with both \(m > N\) and \(n > N\).
Proof
Since \(G = {\mathbb {Z}}_{cd}\), the group induced on each class is \(H = {\mathbb {Z}}_c\), and the group G induced on \({\mathscr {C}}\) is \(K = {\mathbb {Z}}_d\). By [19, Theorem 5.5], G is permutationally isomorphic to a subgroup of \(H \wr K\). Moreover, H and K are regular of degree c and d, respectively, and hence in particular each is 3/2-transitive. Thus \(\text {Rank}(H) = c\) and \(\text {Rank}(K) = d\), and by Theorem 1.1, the Delandtsheer–Doyen parameters (m, n) are such that \(c = \left( \left( {\begin{array}{c}k\\ 2\end{array}}\right) - n\right) /m\) and \(d = \left( \left( {\begin{array}{c}k\\ 2\end{array}}\right) - m\right) /n\). By Lemma 3.1(a) \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) = n \cdot \frac{cd-1}{c-1} = n \cdot \frac{q^2 + q}{c-1}.\) However, also \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) = q(q + 1)/2\) since \(k=q+1\), and therefore \(c = 2n + 1\). From Lemma 3.1(b) we obtain \(d = m(c-1)/n + 1 = 2m + 1\). Thus \(\text {Rank}(H) = 2n + 1\) and \(\text {Rank}(K) = 2m + 1\), which are the maximum possible values by Proposition 3.2, and are the upper bounds of Theorem 1.2. This proves parts (a)–(c).
To show that n and m can simultaneously be arbitrarily large, consider \(q = p^{2f}\) for a prime p and an integer f. ThenWe may take \(d = p^{2f} + p^f + 1\) and \(c = p^{2f} - p^f + 1\), so that by part (a), \(m = p^f\left( p^f + 1\right) /2\) and \(n = p^f\left( p^f - 1\right) /2\). For any fixed prime p and any given bound N, we can find f such that \(p^f\left( p^f - 1\right) /2 > N\), and then we will have \(m, n > N\), so part (d) holds. \(\square \)
$$\begin{aligned} cd = q^2 + q + 1 = \frac{q^3 - 1}{q-1} = \frac{p^{3f} - 1}{p^f - 1} \cdot \frac{p^{3f} + 1}{p^f + 1} = \left( p^{2f} + p^f + 1\right) \left( p^{2f} - p^f + 1\right) . \end{aligned}$$
Proposition 1.3(a) follows from Lemma 4.2. Now we establish the other parts of Proposition 1.3 using results from [6, 16, 17]. Namely, Lemma 4.4(a) proves Proposition 1.3(b), and Lemma 4.4(b) proves Proposition 1.3(c). Note that \(m = n = 1\) implies that \(c = d = \left( {\begin{array}{c}k\\ 2\end{array}}\right) - 1\) by Theorem 1.1.
Remark 4.3
The three 2-designs referred to in Lemma 4.4(a) are described in the text following [6, Theorem 5.1]. For the convenience of the reader we give a brief concrete, and fairly uniform, description of these designs. All three designs are based on a point set \({\mathscr {P}}=\Sigma \times \Sigma \), where \(\Sigma =\{1, 2,\dots , c\}\) and \(c=\left( {\begin{array}{c}k\\ 2\end{array}}\right) -1\); and all three designs admit a group of automorphisms preserving the partition \({\mathscr {C}}=\{C_i\mid i\in \Sigma \}\) of \({\mathscr {P}}\), where \(C_i=\{(x,i)\mid x\in \Sigma \}\) for \(i\in \Sigma \). The groups are either \(H\wr K=H^c\rtimes K\) or \(H\times K\), where \(H\cong K\cong \text {Sym}(c)\), and their actions are given by (4) or (5), respectively. For \(j=1,2,3\), the design \({\mathscr {D}}_j=({\mathscr {P}},{\mathscr {B}}_j)\) has block set \({\mathscr {B}}_j=\{B_j^g\mid g\in G_j\}\) where \(G_1=H\wr K\) and \(G_2=G_3=H\times K\), and whereThe block sets for \({\mathscr {D}}_2\) and \({\mathscr {D}}_3\) are viewed as edge sets for bipartite graphs in the analysis in [6, Sect. 3], and these two designs admit a vertex-primitive group \((H\times K).2\cong \text {Sym}(c)\wr \text {Sym}(2)\), but we do not need these details here. The graph theoretic construction in these latter two cases is explored more fully in a forthcoming paper [1] of the second and third authors, together with Alavi and Daneshkhah. In particular graph theoretic criteria are given for the existence of the additional symmetry needed for the designs to admit the point-primitive group \(\text {Sym}(c)\wr \text {Sym}(2)\).
$$\begin{aligned} B_1&= B_2 = \{(i,i) \mid 1\leqslant i\leqslant k-1\}\cup \{(k-2, k-1)\},\\ B_3&= \{(i,i) \mid 1\leqslant i\leqslant k-2\}\cup \{(k-2, k-1), (k-1, k-3)\}. \end{aligned}$$
Lemma 4.4
Let k be an integer, \(k \geqslant 3\), and let \(c = \left( {\begin{array}{c}k\\ 2\end{array}}\right) - 1\).
(a)
There exist at least three pairwise non-isomorphic 2-\((c^2, k, \lambda )\) designs (for some values of \(\lambda \)), the first admitting \(H \wr K\) and the others admitting \(H\times K\), as a block-transitive, point-imprimitive group of automorphisms with Delandtsheer–Doyen parameters \((m,n) = (1,1)\), where \(H = K = \text {Sym}(c)\) and hence with \(\text {Rank}(X) = \text {PairRank}(X) + 1 = 2\), for \(X \in \{H,K\}\).
(b)
There exists a 2-\((c^2, k, \lambda )\) design \({\mathscr {D}}\) (for some \(\lambda \)) as in Theorem 1.2, with \(n = m = 1\) and \(\max \{\text {Rank}(H), \text {Rank}(K)\} = 3\), if and only if \(k = 8\) and \(c = 27\). Moreover, in the case \(\lambda = 1\), there are up to isomorphism exactly 467 such designs.
Proof
(a) The three designs are the ones described above. They are pairwise non-isomorphic and each has Delandtsheer–Doyen parameters \((m,n) = (1,1)\) (see [6, Proposition 3.5 and Theorem 5.1]). Also the groups \(H = K = \text {Sym}(c)\) satisfy \(\text {Rank}(H) = \text {Rank}(K) = 2\) and \(\text {PairRank}(H) = \text {PairRank}(K) = m = n = 1\).
(b) Suppose that, for some \(\lambda \), there exists a 2-\((c^2, k, \lambda )\) design as in Theorem 1.2 with \(n = m = 1\) and \(\max \{\text {Rank}(H), \text {Rank}(K)\} = 3\). Then it follows from [6, Theorem 5.2] that \(k = 3, 4, 5\), or 8 (because otherwise \(\text {Rank}(H) = \text {Rank}(K) = 2\)), and so \(c = 2, 5, 9\), or 27, respectively. By assumption some \(X \in \{H,K\}\) has rank 3, and hence \(\text {PairRank}(X) = 1\) by Theorem 1.2, that is to say, X is transitive on unordered pairs. However there is no transitive rank 3 group of degree \(c = 2\), and there is no transitive rank 3 group of degree \(c = 5\) or \(c = 9\) that is transitive on unordered pairs (by [14, Proposition 3.1], or see [10, Theorem 9.4B]). Hence \(k = 8\) and \(c = 27\). In [16, 17], it is proved that there are, up to isomorphism, exactly 467 examples of 2-(729, 8, 1) designs (linear spaces) with these properties. \(\square \)
In Remark 4.5 below we make some comments on the classification results in [21] of various families of block-transitive 2-designs with block size \(k=4\). We note that the number of such designs with all the properties of Lemma 4.4(a) is exactly three.
Remark 4.5
In [21], Zhan et al classify two families of block-transitive \(2-(v,4,\lambda )\) designs. The first family comprises all such designs which admit a point-imprimitive, block-transitive subgroup of automorphisms, and the second family consists of those designs admitting a block-transitive subgroup which is point-primitive of product type. We make several comments about both the methods used and the examples arising in these classifications. Although the authors of [21] made significant progress towards classifying block-transitive \(2-(v,4,\lambda )\) designs, they have only partially classified the point-primitive examples. We know of at least two additional infinite families of examples: namely, the design of points and lines of \({\text{ P }G}_d(3)\), and the design \({\mathscr {D}}({\mathscr {S}})\) obtained from [9, Construction 1.1] with input design \({\mathscr {S}}\) being the design of points and lines of \({\text{ P }G}_d(4)\). Both of these families have an almost simple point-primitive automorphism group. It would be an interesting test case for the efficacy of our approach to see a complete classification of block-transitive 2-designs with small block size, such as block size \(k=4\).
(i)
In [21, Theorem 1.1], it is shown that, up to isomorphism, there are exactly 57 \(2-(v,4,\lambda )\) designs admitting a point-imprimitive, block-transitive group; [21, Table 2] lists the value of \(\lambda \) for each of these designs, the number ‘Nr’ of pairwise-non-isomorphic designs with this value of \(\lambda \) and, for each of these Nr designs, a ‘base block’ and a block-transitive, point-imprimitive subgroup N[i] of automorphisms. (The group N[i] in [21, Table 2] is the group \(\mathtt {TransitiveGroup}(25,i)\) in the classification of transitive groups of small degree in Magma.) An earlier table [21, Table 1] lists all pairs \((\lambda , i)\) for which there exists a \(2-(v,4,\lambda )\) design admitting the group N[i] as a point-imprimitive, block-transitive subgroup of automorphisms. Computing the automorphism groups of these designs using Magma, we found that the second table [21, Table 1] almost always lists the largest point-imprimitive, block-transitive subgroup for each design. The exceptions are that, for \(\lambda =2\) the design listing \(G=N[9]\) has largest point-imprimitive block-transitive subgroup N[19]; for \(\lambda =10\) two of the designs listing \(G=N[34]\) have largest point-imprimitive block-transitive subgroup N[52]; and for \(\lambda =50\) the design listing \(G=N[66]\) has largest point-imprimitive block-transitive subgroup N[149].
(ii)
If the authors of [21] had considered the Delandtsheer–Doyen parameters of these designs, their proof would have been greatly simplified. Indeed for \(k=4\), Theorem 1.1 yields integers of the form \(c = \frac{6 - n}{m}\geqslant 2\) and \(d = \frac{6 - m}{n}\geqslant 2\), for some positive integers m, n, and from this it follows easily that (c, d, m, n) is either (5, 5, 1, 1), or (2, 2, 2, 2). The latter case corresponds to a trivial design with only one block. Thus the original result [7, Theorem] from 1989 immediately yields, for a nontrivial design, that \(v=cd=25\). It also implies that the Delandtsheer–Doyen parameters must be \(m=n=1\). Our first result, Theorem 1.2, then shows that the design admits a point-imprimitive group \(G\leqslant H\wr K\) with H, K subgroups of \(S_5\) satisfying \(\text {PairRank}(H)=n=1\) and \(\text {PairRank}(K)=m=1\), that is to say, the groups H, K are transitive on unordered pairs. The only such subgroups are \(\text {AGL}(1,5),A_5,S_5\), and each of these is 2-transitive, so H and K have rank 2. Thus these 57 designs are precisely the designs satisfying the conditions of Proposition 1.3(b) with \(k=4\).
(iii)
In Lemma 4.4(a), the relevant designs are precisely those for which \(H=K=S_5\), with H, K as in part (ii), and using Magma, we find that, of the 57 block-transitive point-imprimitive 2-designs listed in [21, Table 2], exactly three of them have \(H=K=S_5\), namely those lines in [21, Table 2] with \((\lambda , G)\) one of (18, N[99]), (72, N[99]) or (150, N[209]), using the names for groups as in part (i). We also observe that the unique design with \((\lambda , G)=(150, N[209])\) is the Cameron–Praeger design \({\mathscr {D}}(5,5;\mathbf{x})\) with \(\mathbf{x}=(2,1,1,0,0)\) and \(G=S_5\wr S_5\) of [6, Proposition 2.2]. It is also the design \({\mathscr {D}}_1\) of Remark 4.3 for \(k=4\), while the other two designs, with \((\lambda , G) = (18, N[99])\) or (72, N[99]), are the designs \({\mathscr {D}}_3, {\mathscr {D}}_2\) of Remark 4.3 for \(k=4\), respectively. We conclude that the three designs described in Remark 4.3 are the only examples for Lemma 4.4(a) when \(k=4\).
(iv)
For the 54 other designs listed in [21, Table 2], the block-transitive, point-imprimitive subgroup of automorphisms \(G\leqslant H\wr K\) listed in [21, Table 2] is such that at least one of H, K is a proper subgroup of \(S_5\). It turns out, on examining the largest point-imprimitive block-transitive groups for these designs using Magma, that each of H, K is either \(\text {AGL}(1,5)\) or \(S_5\), that is to say, whenever \(A_5\) is contained in one of these groups it is in fact equal to \(S_5\). (For some of these designs there is a smaller block-transitive point-imprimitive group for which H and/or K is \(A_5\).)
(v)
While exploring the 57 designs of [21, Table 2] admitting a block-transitive, point-imprimitive subgroup of automorphisms, we computed the full automorphism group of each design, using Magma. It turns out that for ten of the designs the full automorphism group is point-primitive: eight admit a primitive group of affine type, and the other two admit a primitive group of product action type. The latter two designs (with a product action primitive group) are equal to two of the three designs listed in [21, Theorem 2], which the authors did not seem to notice. Namely the unique designs in [21, Table 2] with \(\lambda =18\) and \(\lambda =72\), have point-primitive full automorphism group \(S_5\wr S_2\), and these two designs are the designs \({\mathscr {D}}_3\) and \({\mathscr {D}}_2\) from Remark 4.3, respectively. They are also two of the three designs we identified in part (iii) above. The third design in [21, Theorem 1.2] is a block-transitive, point-primitive \(2-(25,4,12)\) design with automorphism group \(S_5\wr S_2\) (which has no block-transitive, point-imprimitive subgroup) and so is different from the design with \(\lambda =12\) listed in [21, Table 2]. For a nice description of this third design, take point set \({\mathscr {P}}=\Sigma \times \Sigma \) as in Remark 4.3 with \(c=5\), and block set \({\mathcal {B}}=\{B^g|g\in S_5\wr S_2\}\) where \(B=\{(1,1),(1,2),(2,3),(2,4)\}\).
5 New design construction
In this section, we will construct block-transitive imprimitive designs with \(m=1\) such that \(\text {Rank}(H) = \text {PairRank}(H) + 1 = n + 1\) and \(\text {Rank}(K) = \text {PairRank}(K) + 1 = m + 1 = 2\), for some fixed values of n and of c.
Let \({\mathbb {F}}\) be a field of order \(c=p^a\) such that \(c \equiv 1 \pmod {2n}\), and let \(\zeta \) be a primitive element of \({\mathbb {F}}\). Let \(H = N \rtimes \langle \zeta ^n \rangle \) be the subgroup of the affine group \(\text {AGL}(1,c)\) acting on \({\mathbb {F}}\), where N is the group of translations, and we identify \(\zeta ^n\) with multiplication by \(\zeta ^n\). Note that \(\langle \zeta ^n \rangle \) contains \(-1\) since \(c \equiv 1 \pmod {2n}\). We record some information about the permutation action of H on \({\mathbb {F}}\). The assertions are straightforward to check and details are left to the reader.
Lemma 5.1
Let \({\mathbb {F}}\), c, \(\zeta \), N, and H be as above. Then the following hold:
(a)
N is regular on \({\mathbb {F}}\), and \(H_0 = \langle \zeta ^n \rangle \) is the stabiliser in H of \(0 \in {\mathbb {F}}\).
(b)
The \(H_0\)-orbits in \({\mathbb {F}}\setminus \{0\}\) are \(\Delta _i(0) = \left\{ \zeta ^{i+jn} \mid 0 \leqslant j < (c-1)/n \right\} \) with associated H-orbital \(\Delta _i = (0,\zeta ^i)^H\), for \(0 \leqslant i < n\). Each \(\Delta _i\) is self-paired (since \(-1 \in H_0\)).
(c)
The H-orbits on 2-subsets of \({\mathbb {F}}\) are \({\mathscr {O}}_i = \{ \{\alpha ,\beta \} \mid (\alpha ,\beta ) \in \Delta _i \}\), for \(0 \leqslant i < n\), each of which has size \(c(c-1)/(2n)\). Moreover, the setwise stabiliser of each pair of points is cyclic of order 2.
(d)
\(\text {Rank}(H) = \text {PairRank}(H) + 1 = n + 1\)
We use this group H in the design construction. The point-imprimitive group of automorphisms will be \(G := H \wr K\), where \(K = \text {Sym}(d)\) is the symmetric group on \(R = {\mathbb {Z}}_d\). As in (4), G acts imprimitively on \({\mathbb {F}}\times R\) and leaves invariant the partition \({\mathscr {C}}\) of \({\mathbb {F}}\times R\) with classes \(C_j = \{ (x,j) \mid x \in {\mathbb {F}}\}\) for \(j \in R\). The proof of Lemma 5.2, which records various properties of this action, is straightforward and details are left to the reader.
Lemma 5.2
Let \({\mathbb {F}}\), R, \({\mathscr {C}}\), and G be as above. Then the following hold:
(a)
The partition \({\mathscr {C}}\) of \({\mathbb {F}}\times R\) is nontrivial and G-invariant.
(b)
G is transitive on the set \({\mathscr {O}}_{out}\) of \({\mathscr {C}}\)-outer pairs from \({\mathbb {F}}\times R\), and \(|{\mathscr {O}}_{out}| = c^2d(d-1)/2\).
(c)
G has exactly n orbits on the set of \({\mathscr {C}}\)-inner pairs from \({\mathbb {F}}\times R\), namely Moreover, for each i we have \(|{\mathscr {O}}_{inn,i}| = dc(c-1)/(2n)\).
$$\begin{aligned} {\mathscr {O}}_{inn,i} = \{ \{(x,j), (y,j)\} \mid \{x,y\} \in {\mathscr {O}}_i, j \in R \},\quad \text{ for }\ 0 \leqslant i < n. \end{aligned}$$
For the construction below to work, we need some conditions on n and c which are exactly the conditions described in Definition 1.4. Suppose now that [n, c] is a useful pair, as in Definition 1.4. Then \(c = p^a\), for some odd prime p and \(a \geqslant 1\), and \(c \equiv 1 \pmod {2n}\), \(c + n = \left( {\begin{array}{c}k\\ 2\end{array}}\right) \) for some integer \(k \geqslant 2n\), and \(n\geqslant 2\). First we derive an upper bound and an improved lower bound for k.
Lemma 5.3
Let n, c, and k be as above and let \(d = 1 + (c-1)/n\). Then \(2n + 2 \leqslant k \leqslant n + d\).
Proof
From Definition 1.4 we have \(c + n = k(k-1)/2 \geqslant n(k-1)\). Suppose first, for a contradiction, that \(k > n + d\). Thenand hence \(n < 1 + 1/n\) which is not possible for any \(n \geqslant 2\). Hence \(k \leqslant n + d\). Finally, if \(k = 2n\) or \(k = 2n + 1\), thenand in either case \(c \equiv 0 \pmod {2n}\), which is a contradiction. Hence \(k \geqslant 2n + 2\). \(\square \)
$$\begin{aligned} k > n + d = n + 1 + \frac{c-1}{n} = n - \frac{1}{n} + \frac{c+n}{n} \geqslant n - \frac{1}{n} + (k-1), \end{aligned}$$
$$\begin{aligned} c = \left( {\begin{array}{c}k\\ 2\end{array}}\right) - n \in \{ 2n(n-1), 2n^2 \}, \end{aligned}$$
Construction 5.4
Let [n, c] be a useful pair as in Definition 1.4, with \(c = p^a\) for some odd prime p and \(a \geqslant 1\), \(d = 1 + (c-1)/n\), and k, \({\mathbb {F}}\), R, G, and \({\mathscr {C}}\) as above. Define the design \({\mathscr {D}}= ({\mathscr {P}},{\mathscr {B}})\) to have point set \({\mathscr {P}}:= {\mathbb {F}}\times R\) and block set \({\mathscr {B}}:= B^G\), where \(B \subseteq {\mathscr {P}}\) is given byNote that \(n+1 \leqslant k-n-1 \leqslant d-1\), by Lemma 5.3, so the second set in the union defining B has size \(k-2n\geqslant 2\), and B is a well defined k-subset of \({\mathscr {P}}\).
$$\begin{aligned} B = \{ (0,i), (\zeta ^i,i) \mid 0 \leqslant i \leqslant n-1 \} \cup \{ (0,i) \mid n \leqslant i \leqslant k-n-1 \}. \end{aligned}$$
(7)
Theorem 5.5
Let \({\mathscr {D}}\) and G be as in Construction 5.4. Then \({\mathscr {D}}= ({\mathscr {P}},{\mathscr {B}})\) is a 2-\((cd, k, \lambda )\) design, and \(G = H \wr K\) is a block-transitive, point-imprimitive group of automorphisms leaving invariant the point-partition \({\mathscr {C}}\), such that:
(a)
The Delandtsheer–Doyen parameters of \({\mathscr {D}}\) are \((m,n) = (1,n)\);
(b)
\(\text {Rank}(H) = \text {PairRank}(H) + 1 = n + 1\) and \(\text {Rank}(K) = \text {PairRank}(K) + 1 = m + 1 = 2\); and
(c)
\(\displaystyle {\lambda = c^{k-n-1} \left( \frac{d-1}{2}\right) ^{n-1} \frac{(d-1)!}{n!(k-2n)!(d-k+n)!}}\).
Proof
By (7) and Lemma 5.2, for each \(i=0,\dots ,n-1\), the set B contains exactly \(n_i = 1\) inner pair from \({\mathscr {O}}_{inn,i}\), namely \(\{ (0,i), (\zeta ^i,i) \}\). Hence B contains exactly \(n_{out} := \left( {\begin{array}{c}k\\ 2\end{array}}\right) - n\) outer pairs. By [6, Proposition 1.3], \({\mathscr {D}}\) is a 2-design if and only if, for any G-orbit \({\mathscr {O}}\) in the set of 2-subsets of \({\mathscr {P}}\), the ratio \(|\{ \{x,y\} \mid \{x,y\} \in {\mathscr {O}}, \ \{x,y\} \subseteq B \}|/|{\mathscr {O}}|\) is independent of \({\mathscr {O}}\), that is to say, \({\mathscr {D}}\) is a 2-design if and only ifHence, by Lemma 5.2, \({\mathscr {D}}\) is a 2-design if and only ifor equivalently,From the definition of d, this is equivalent to \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) - n = c\), and this equality holds by Definition 1.4. Hence \({\mathscr {D}}\) is a 2-design with cd points and block size k, that is to say, a 2-\((cd, k, \lambda )\) design for some \(\lambda \). By Definition 1.4 and Lemma 5.3, the class size is \(c = \left( {\begin{array}{c}k\\ 2\end{array}}\right) - n\) and the number of classes is \(d = (n + c - 1)/n = \left( \left( {\begin{array}{c}k\\ 2\end{array}}\right) - 1\right) /n\), and it follows from Theorem 1.1 that the Delandtsheer–Doyen parameters are \((m,n) = (1,n)\). This proves part (a). The assertions in part (b) follow from Lemma 5.1(d) for H, and the fact that \(K = \text {Sym}(d)\) has \(\text {Rank}(K) = \text {PairRank}(K) + 1 = 2 = m+1\).
$$\begin{aligned} \frac{n_0}{|{\mathscr {O}}_{inn,0}|} = \dots = \frac{n_{n-1}}{|{\mathscr {O}}_{inn,n-1}|} = \frac{n_{out}}{|{\mathscr {O}}_{out}|}. \end{aligned}$$
$$\begin{aligned} \frac{1}{dc(c-1)/(2n)} = \frac{\left( {\begin{array}{c}k\\ 2\end{array}}\right) -n}{c^2d(d-1)/2}, \end{aligned}$$
$$\begin{aligned} \left( {\begin{array}{c}k\\ 2\end{array}}\right) -n = \frac{nc(d-1)}{c-1}. \end{aligned}$$
By Lemma 3.1(c) and since \(m=1\), we have \(\lambda = 2|{\mathscr {B}}|/cd(d-1)\). Recall (from the definition of H) that a point stabiliser in H is cyclic of order \((c-1)/n = d-1\), and (from Lemma 5.1(c)) that the stabiliser in H of each unordered pair of points is cyclic of order 2. From these and the definition of B we see that the stabiliserHencewhich yields\(\square \)
$$\begin{aligned} G_B = ({\mathbb {Z}}_2\wr \text {Sym}(n)) \times ({\mathbb {Z}}_{d-1} \wr \text {Sym}(k-2n)) \times (H \wr \text {Sym}(d-k+n)). \end{aligned}$$
$$\begin{aligned} |{\mathscr {B}}| = |G:G_B|&= \frac{|H|^d d!}{2^n(d-1)^{k-2n} |H|^{d-k+n} n! (k-2n)! (d-k+n)!} \\&= \frac{c^{k-n} (d-1)^n}{2^n} \cdot \frac{d!}{n!(k-2n)!(d-k+n)!} \end{aligned}$$
$$\begin{aligned} \lambda&= \frac{2}{cd(d-1)} \cdot c^{k-n} \left( \frac{d-1}{2}\right) ^n \frac{d!}{n! (k-2n)! (d-k+n)!} \\&= c^{k-n-1} \left( \frac{d-1}{2}\right) ^{n-1} \frac{(d-1)!}{n!(k-2n)!(d-k+n)!}. \end{aligned}$$
The smallest useful pair is \([n,c] = [2,13]\), and for this pair the value of \(\lambda \) is 197730.
Note there are many useful pairs, see Table 1, and the plentiful occurrence of such pairs is discussed in Sect. 1.1, but they do not exist for every n, as proved in the following lemma.
Lemma 5.6
If [n, c] is a useful pair, then \(n\notin \{6,10,15\}\). Moreover, if \(n\in \{6,10,15\}\) and [n, c] satisfies all the conditions of a useful pair except that \(k< 2n\), then [n, c, k, d] is one of [6, 49, 11, 9], [10, 81, 14, 9], or [15, 121, 17, 9].
Proof
Let \(n\in \{6,10,15\}\), and let [n, c] satisfy all the conditions for a useful pair except possibly \(k\geqslant 2n\). Then \( \left( {\begin{array}{c}k\\ 2\end{array}}\right) -n\equiv 1\pmod {2n}\), so \(k(k-1)\equiv 2n+2\pmod {4n}\). This implies that \(k\equiv r \pmod {4n}\), with r as in Table 2. Thus \(k=4nb+r\) for some non-negative integer b and, as a quadratic polynomial g(b), the expression \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) -n\) happens to factorise as \((2nb+x)(4nb+y)\) for some integers x, y satisfying \(1<x\leqslant y\), as in Table 2. Since g(b) is a power of a prime p, each of the factors \(2nb+x\) and \(4nb+y\) is also a power of p, say \(2nb+x=p^e\) and \(4nb+y=p^f\). A straightforward arithmetic analysis yields precisely the parameter tuples in the statement. We give brief details for the case \(n=6\) only. For \(n=6\), \(y-2x=p^e(p^{f-e}-2)=\pm 7\), so \(p=7\), \(e=f=1\), and hence \(x=y=7\) which forces \(b=0\). Thus \([n,c,k,d]=[6, 49, 11, 9]\). These values do not satisfy the condition \(k\geqslant 2n\) so [6, 49] is not a useful pair. \(\square \)
Table 2
Factorisations \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) -n=(2nb+x)(4nb+y)\) for \(k=4nb+r\)
n
| 6 | 10 | 15 | |||||||
r
| 11 | 14 | 14 | 19 | 22 | 27 | 17 | 29 | 32 | 44 |
x
| 7 | 5 | 9 | 7 | 13 | 11 | 11 | 17 | 13 | 19 |
y
| 7 | 17 | 9 | 23 | 17 | 31 | 11 | 23 | 37 | 49 |
Finally we observe that Construction 5.4 can be generalised to produce a larger family of 2-designs with the Delandtsheer–Doyen parameter \(m\geqslant 1\). However we do not find any designs in this larger family meeting the upper bounds of Theorem 1.2 on \(\text {Rank}\) or \(\text {PairRank}\) when \(m>1\).
Remark 5.7
Consider the following relaxation of the conditions for a useful pair in Definition 1.4. We still ask that \(c = p^a\) for some odd prime p and \(a \geqslant 1\), and that \(c\equiv 1\pmod {2n}\), where \(n\ge 2\); but we relax Definition 1.4(2) to the condition \(mc+n=\left( {\begin{array}{c}k\\ 2\end{array}}\right) \) for some integers \(m\geqslant n, k\geqslant 2n\), and we set \(d = 1 + m(c-1)/n\). We take \({\mathbb {F}}\), R, \({\mathscr {P}}= {\mathbb {F}}\times R\), \({\mathscr {C}}\), H, \(K=\text {Sym}(d)\), \(G=H\wr K\), as above, and we define a design \({\mathscr {D}}= ({\mathscr {P}},{\mathscr {B}})\) to have block set \({\mathscr {B}}:= B^G\), with B as in (7). Arguing as in the proof of Theorem 5.5, B contains n inner pairs and \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) -n\) outer pairs, and \({\mathscr {D}}\) is a 2-design if and only if \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) -n = nc(d-1)/(c-1)\). This condition holds by our new requirement on \(\left( {\begin{array}{c}k\\ 2\end{array}}\right) \) and new definition of d. Thus we obtain a block-transitive, point-imprimitive 2-design with Delandtsheer–Doyen parameters (m, n). However, the action induced by G on \({\mathscr {C}}\) is \(K=\text {Sym}(d)\) with \((\text {Rank}(K)-1)/2=\text {PairRank}(K)=1\), and this is equal to the bound m only when \(m=1\).
We tried quite hard, but unsuccessfully, to find a construction having a ‘top group’ K with \(\text {PairRank}(K)=m\), for some given \(m>1\), and meeting the bound of Theorem 1.2 on \(\text {PairRank}(K)\). It would be very interesting indeed to have examples with \(\text {PairRank}(K)=m>1\).
Acknowledgements
The authors are grateful to Gareth Jones and Alexander Zvonkin for their interest in our work: in particular for their advice on the Bunyakovsky and Bateman–Horn Conjectures, and their enumeration of large families of useful pairs [n, c]. In addition, many articles referring to Bunyakovsky’s original paper cite an incorrect title for [5], and we are grateful to Alexander Zvonkin for pointing this out to us. The authors also appreciate helpful advice and comments from two anonymous referees.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.