1 Introduction

Packing codes in the symmetric group for the Hamming distance have been studied since the 1970s [3]. See [4] for a recent survey. Note that transitive sets of permutations are more abundant than t-transitive groups of permutations that only exist ( apart from trivial examples) for \(t\le 6\) [3, 4]. In [5] covering codes in the symmetric group are considered. In particular, it is shown there that t-transitive groups in the symmetric group \(S_n\) on n letters have covering radius for the Hamming distance at most \(n-t\), and that this bound is tight.

In the present paper, we prove bounds of similar order for t-designs in \(S_n\) in the sense of Godsil [6, 10, 11]. These objects are defined in the setting of polynomial spaces, a generalization of association schemes [2, 7]. An alternative definition in the language of distance degree regular spaces can be found in [14, 15]. It is known that t-transitive groups are t-designs, but the converse is not generally true. To derive these bounds, we extend the method of [16] from the Hamming space to the space of permutations. This method is based on the polynomials orthogonal w.r.t. the weight distribution of the cosets of the code considered. If the dual distance of the code is large enough, these polynomials coincide with the celebrated Krawtchouk polynomials [17], and the zeros of these can be used to bound the extreme points of the distribution. In that coding analogy, Charlier polynomials and their zeros play the role of Krawtchouk polynomials. Charlier polynomials have already appeared implicitly in the study of permutation groups, in the work of Frobenius, who proved that the first k power moments of the statistics of fixed points coincide with that of a Poisson law up to order k [9]. But we know that they are orthogonal w.r.t. that distribution on the real line [13]. An important difference between these two families of orthogonal polynomials is that the integrality of the zeros of Charlier polynomials is easier to decide. This technical point simplifies the proofs of the bounds in comparison with the coding situation.

The note is arranged as follows. The next section collects notions and definitions needed for the other sections. Section 3 recalls the current results on t-designs of permutations. Section 4 contains the main results.

2 Background material

2.1 Permutations groups

A permutation group G acting on a set X of n elements is transitive if there is only one orbit on X. It is t-transitive if it is transitive in its action on \({ X^t}\) the set of distinct t-tuples from X. It is sharply t-transitive if this action is regular, concretely if \(|G|=\frac{n!}{(n-t)!}\). We extend this terminology by relaxing the group hypothesis to a set of permutations action on X. It is well-known amongst geometers and group theorists that a set of sharply 2-transitive permutations on a set of size n is equivalent to the existence of a projective plane PG(2, n), that is to say a \(2-(n^2+n+1,n+1,1)\) design [4].

2.2 Permutation codes

Consider the symmetric group on n letters \(S_n\) with metric

$$\begin{aligned} d_S(\sigma ,\theta )=n-F(\sigma \theta ^{-1}), \end{aligned}$$

where \(F(\nu )\) denotes the number of fixed points of \(\nu \). The space \((S_n,d_S)\) is a metric space. Let \(w_k\) denote the numbers of permutations on n letters with k fixed points. A generating function for these numbers (sometimes called rencontres numbers) is

$$\begin{aligned} \sum _{k=0}^nw_ku^k=n!\sum _{j=0}^n\frac{(u-1)^j}{j!}, \end{aligned}$$

as per [19]. It is clear that \(d_S\) is not a shortest path distance since \( d_S(\sigma ,\theta )=1\) is impossible. Codes in \((S_n,d_S)\) were studied in [18] by using the conjugacy scheme of the group \(S_n\). For next paragraph, define

$$\begin{aligned} E_i=\{(x,y) \in S_n^2 \mid d_S(x,y)=i\} \end{aligned}$$

for all \(i\in \{0,1,\ldots , n\}\). In that range of i, write \(v_i=|E_i|/n!\). Note that \(v_i=w_{n-i}\). If \(Y\subseteq S_n\) is any set of permutations its covering radius \(\rho (Y)\) is defined as

$$\begin{aligned} \rho (Y)=\max \{ \min \{ d_S(x,y) \mid y \in Y\}\mid x \in S_n\}. \end{aligned}$$

2.3 Permutation designs

If D is any non-void subset of \(S_n\), we define its frequencies as

$$\begin{aligned} \forall i \in [0..n], \, f_i=\frac{|D^2\cap E_i|}{|D|^2}. \end{aligned}$$

Thus, \(f_0=\frac{1}{|D|}\), and \(\sum \nolimits _{i=0}^n f_i=1\). Note also that if \(D=S_n\), then \(f_i=\frac{v_i}{n!}\).

Definition 1

The set \(D \subseteq X\) is a t-design for some integer t if

$$\begin{aligned} \sum _{j=0}^n f_jj^i= \sum _{j=0}^n \frac{v_j}{n!}j^i. \end{aligned}$$

for \(i=1,\ldots ,t\).

(Note that trivially \(\sum \nolimits _{j=0}^n f_jj^0=1\) so that we do not consider \(i=0\).) Thus, distances in t-designs are very regularly distributed. For a 2-design, for instance, the average and variance of the distance coincide with that of the whole space.

Remark: Our notion of design is a special case of designs in polynomial spaces of [10].

2.4 Orthogonal polynomials

Definition 2

We define a scalar product on \(\mathbb {R}[x]\) attached to D by the relation

$$\begin{aligned} \langle f,g \rangle _D=\sum _{i=0}^n f_i f(i)g(i). \end{aligned}$$

Thus, in the special case of \(D=S_n\) we have

$$\begin{aligned} \langle f,g \rangle _{S_n}=\frac{1}{n!}\sum _{i=0}^n v_i f(i)g(i). \end{aligned}$$

We require the so-called Charlier polynomials.

Let

$$\begin{aligned} C_k(x)=(-1)^k+\sum \limits _{i=1}^k(-1)^{k-i}{k \atopwithdelims ()i} x(x-1)\cdots (x-i+1). \end{aligned}$$

An exponential generating function is given in [13, (1.12.11)] as:

$$\begin{aligned} e^t(1-t)^x=\sum _{n=0}^\infty C_n(x)\frac{t^n}{n!}. \end{aligned}$$

Thus, for concreteness, \(C_0(x)=1,\,C_1(x)=x-1,\, C_2(x)=x^2-3x+1\).

The scalar product attached to the space \((S_n,d_S)\) is then

$$\begin{aligned} \langle f,g\rangle _{S_n}=\frac{1}{n!} \sum _{k=0}^n w_{n-k} f(k)g(k). \end{aligned}$$

It is remarkable that the following orthogonality relation is not found in the classical treatises [13, 17] on orthogonal polynomials. See [15, Lemma 1] for a proof.

Lemma 1

For a given \(n\ge 1\), the reversed Charlier polynomials \(\widehat{C_k(x)}=C_k(n-x)\) satisfy the orthogonality relation

$$\begin{aligned} \langle \widehat{C_r},\widehat{C_s}\rangle _{S_n}=r! \delta _{rs}, \end{aligned}$$

for \(r,s\le n/2\), where \(\delta \) denotes the Kronecker symbol.

3 Structure theorems

The following result is derived in [6], and in a different language in [15].

Theorem 1

If \(D\subseteq S_n\) is a t-transitive permutation group, then it is a t-design in \((S_n,d_S)\). If \(D\subseteq S_n\) is a t-design that is a subgroup of \(S_n\), then it is a t-transitive permutation group.

We require the following characterization of 1-designs from [15].

Lemma 2

A subset \(D\subseteq S_n\) is a 1-design in \((S_n,d_S)\) iff \(\sum \nolimits _{j=0}^njf_j=n-1\). In particular, this condition is satisfied if we have n permutations at pairwise distance n when \(f_1=f_2=\cdots =f_{n-1}=0\), and \(f_n=\frac{n-1}{n}\).

4 Main result

We begin with two lemmas on the zeros of Charlier polynomials.

Lemma 3

The polynomial \(C_k\) has exactly k real zeros in \((0,\infty )\).

Proof

Direct application of Theorem 3.3.1 of [17] to the Charlier polynomials which are orthogonal w.r.t. the probability measure of a Poisson law of parameter one [17, p.34]\(.\square \)

In the following, we will denote by x(k) the largest zero of \(C_k\). This definition makes sense by Lemma 3.

Lemma 4

If z is a zero of \(C_k\) for \(k>1\), then z cannot be an integer.

Proof

If z is an integral zero of \(C_k(x)\), then z divides \(C_k(0)=(-1)^k\); hence, since z is nonnegative, \(z=1\). But \(C_k(1)=(-1)^k(1-k)\) which is \(\ne 0\) for \(k>1\). \(\square \)

Define the half-strength of a t-design as \(s=\lfloor \frac{t+1}{2}\rfloor \). The next result, which motivates this note, derives an upper bound on the covering radius of a design of given half-strength.

Theorem 2

If D is a design of \(S_n\) of half-strength \(s>1\), then

$$\begin{aligned} \rho (D) < n-x(s). \end{aligned}$$

Proof

Define \(P_s(x)={\widehat{C}}_s(x)/(n-x-x(s))\). Since \(P_s\) is a polynomial of degree \(<s\), we have, by orthogonality

$$\begin{aligned} \langle {\widehat{C}}_s, P_s\rangle _{S_n}=\langle 1, {\widehat{C}}_s P_s \rangle _{S_n}=0. \end{aligned}$$

The degree of \({\widehat{C}}_s P_s\) is \(s+s-1 \le t\); we have by definition of a t-design

$$\begin{aligned} \langle 1, {\widehat{C}}_s P_s \rangle _D=\langle 1, {\widehat{C}}_s P_s \rangle _{S_n}=0. \end{aligned}$$

Since, for a given \(\sigma \in S_n\), the translate \(\sigma D\) is also a t-design, we can write

$$\begin{aligned} \langle 1, {\widehat{C}}_s P_s \rangle _{\sigma D}=0=\sum _{i=0}^nf_i{\widehat{C}}_s P_s(i), \end{aligned}$$

where the \(f_i\)’s are the frequencies of \( \sigma D\). Note that the sign of

$$\begin{aligned} {\widehat{C}}_s P_s=\frac{\big ({\widehat{C}}_s(x)\big )^2}{(n-x-x(s))} \end{aligned}$$

is that of \(n-x-x(s)\). If we assume, looking for a contradiction, that \(\rho (D) \ge n-x(s)\) we see that all terms in the above sum being nonnegative, must be zero. Hence, all distances of \(\sigma \) to D must be roots of \({\widehat{C}}_s\), which is impossible for \(s>1\), by Lemma 4. \(\square \)

Example 1

Computing the roots of \(C_k(x)\) using Wolfram online yields

  • If \(t=2\), then \(s=1\) and \(\rho (D) < n-1\); hence, \(\rho (D) \le n-2\), since \(x(1)=1\).

  • If \(t=3\) or \(t=4\), then \(s=2\) and \(\rho (D) \le n-3\), since \(x(2)\approx 2.616\).

  • If \(t=5\) or \(t=6\), then \(s=3\) and \(\rho (D) \le n-5\), since \(x(3)\approx 4.115\).

  • If \(t=7\) or \(t=8\), then \(s=4\) and \(\rho (D) \le n-6\), since \(x(4)\approx 5.544\).

In the cases \(t=3,5\) our bound coincides with that of [5]. For \(t=2,4,6,7\) it is weaker by one unit.

In general, it is known that \(x(k)\le k+2\sqrt{k} +1\). See [12, Th. 4]. It can be shown that \(x(k)=\Omega (\sqrt{k})\) by [1, Theorem 3.1], combined with estimates on the largest zero of Hermite polynomials [8].

If the strength is small, a direct power moment method is often more effective.

Theorem 3

If D is a 1-design of \(S_n\), then \(\rho (D) \le n-1\).

Proof

By Lemma 2, we know that the average distance in the shifted design \(\sigma D\) is \(n-1\). Hence, \(d(\sigma , D)\le n-1\). Since \(\sigma \) is arbitrary in \(S_n\), the result follows. \(\square \)

Thus, for \(t=1\) also, our bound coincides with that of [5].

5 Conclusion

In this note, we have studied the covering radius of permutation designs. We have obtained a general upper bound (Theorem 1) on that quantity, dependent on the largest zero x(t) of the Charlier polynomial of degree t. In order to compare Theorem 1 with the bound of [5], we would need an asymptotic equivalent of x(t) when \(t\rightarrow \infty \). We could not find any such result in the literature of orthogonal polynomials [1, 12, 13, 17]. This is the main open problem.