1 Introduction
Set
\([n]=\left\{ 1,\ldots ,n\right\} \). Let
\(S_n\) denote the symmetric group on [
n], and define
\(S_{n,k}\) as the set of all ordered tuples
\((x_1,\ldots ,x_k)\in [n]^k\) whose entries
\(x_j\) are distinct. Following [
14], a
PSCA of strength k and multiplicity \(\lambda \ge 1\) on n symbols is a matrix
\(A\in [n]^{(\lambda k!)\times n}\) with distinct symbols per row such that each sequence
\(s\in S_{n,k}\) is contained as a subsequence in exactly
\(\lambda \) rows (
s is said to be
covered \(\lambda \) times by
A). Denote the class of all such matrices
A by
\({\text {PSCA}}(n,k,\lambda )\). Let
\(g(n,k)\) be the minimum multiplicity
\(\lambda \) such that
\({\text {PSCA}}(n,k,\lambda )\) is non-empty, and call
\(g(n,k)\) the
perfect sequence covering array number (in analogy to [
2]). A PSCA can be seen as a
\((k,\lambda )\)-directed design of blocksize
n and order
n (cf. [
4]). PSCAs are particular
sequence covering arrays (SCAs), i.e., matrices with permutations as rows that cover each
\(s\in S_{n,k}\) at least once [
2]. SCAs were introduced in [
8] for the purpose of event sequence testing (cf. also [
2,
4]).
Recently, the following two results were obtained by Yuster.
We now point to an isomorphic structure being analyzed in the setting of min-wise independent permutations [
3]. We index families
\(\mathcal {F}\subset S_n\) by an index set
\([d]\),
\(d\in \mathbb {N}\). The elements are allowed to occur repeatedly, and hence the cardinality of
\(\mathcal {F}\) refers to the cardinality of the indexing set. We need the concept of the
rank of an element before we get to the actual definition of interest.
It is clear that (
2) corresponds to the following condition: For each sequence
\((x_1,\ldots ,x_k)\in S_{n,k}\) and for each permutation
\(\pi \) randomly drawn (uniform probability) from
\(\mathcal {F}\), we have
$$\begin{aligned} {\text {Pr}}\left[ \pi ( x_{1})< \pi (x_{2})< \cdots < \pi (x_{k})\right] = \frac{1}{k!}. \end{aligned}$$
(3)
Next, we give a proposition that illuminates the isomorphy of PSCAs and rankwise independent families. Before that, we need an appropriate mapping and an auxiliary observation from which the proposition follows. For the sake of completeness we include a proof of the following Lemma
3 which was already noticed in [
4, Lemma 1.1].
In the following, consider for a family
\(\mathcal {F}=(\pi _1,\ldots ,\pi _d)\subset S_n\) the mapping
$$\begin{aligned} A: \mathcal {F}\mapsto A(\mathcal {F}) := \begin{bmatrix}\pi _1^{-1}(1),&{}\ldots ,&{}\pi _1^{-1}(n) \\ \vdots &{}\ldots ,&{} \vdots \\ \pi _d^{-1}(1),&{}\ldots ,&{}\pi _d^{-1}(n)\end{bmatrix}\in [n]^{d\times n}. \end{aligned}$$
(4)
The inverse operation of
\(A(\cdot )\) in Proposition
4, i.e., the conversion of a PSCA to a rankwise independent family, is determined by interpreting the rows of the PSCA as permutations and successively storing their inverses one by one in a family of permutations.
In [
6] it is already remarked that
k-rankwise independence implies
\(\ell \)-rankwise independence, for all
\(\ell \in [k]\). In other words, a nesting property analogous to the one for PSCAs holds (if
\(A\in {\text {PSCA}}(n,k,\lambda )\), then also
\(A\in {\text {PSCA}}(n,\ell ,\lambda k!/\ell !)\) [
14]). We highlight that
k-rankwise independent families can be considered as
completely scrambling families1 (introduced by Spencer [
12]) with an additional requirement of regularity. Furthermore,
k-rankwise independence is a special case of
k-restricted min-wise independence (cf. Definition
3). It is known (cf. [
6, p. 139]) that these two notions coincide for
\(k=3\) and that
k-rankwise independence is strictly more specific when
\(k>3\). In [
3],
k-restricted min-wise independent families were introduced to efficiently estimate the resemblance of two documents. The latter is motivated by practice, where the aim is to reduce the computational cost of searching for near-duplicate documents on the World Wide Web [
3].
We can now transfer bounds from rankwise independent families to PSCAs (and vice versa).
2 Lower and upper bounds
In this section asymptotic results for rankwise independent permutations will be stated jointly with their implications (cf. Proposition
4) for the number
\(g(n,k)\).
The following result can in particular be analyzed when
h is a prime; we can therefore compare it with Theorem
1 and conclude that it improves the lower bound by the factor !
h, the
subfactorial of
h,
2 being superexponential in
h, but independent of
n.
The next Theorem
6 follows from the proof of [
6, Theorem 3.2]. It positively answers the question of Yuster on the existence of non-trivial upper bounds for
\(g(n,k)\) for fixed
k. In fact, the estimate is polynomial in
n.
We state more specific results for \(k\in \left\{ 3,4\right\} \). Originally, the subsequent result concerning 3-rankwise independence was established for the equivalent property of 3-restricted min-wise independence.
Table 1
Upper bounds for g(n, 4)
5 | \(~^*\)1 | 1 |
6 | \(~^*\)1 | 672 |
7 | \(~^*\)2 | 672 |
8–12 | 18 | – |
13 | 234 | – |
14–17 | 5040 |
672
|
18–21 | 5040 | 3 139 584 |
22 | 18 480 | – |
23 | 425 040 | – |
24 | 10 200 960 |
3 139 584
|
25–65 | – | 3 139 584 |
66–257 | – | 23 482 368 |
Table 2
Upper bounds for g(n, 3)
4 | | \(~^*\)1 | 1 |
5–7 | | \(~^*\)2 | 10 |
8 | | \(~^*\)3 | _ |
9 | | 4 | _ |
10–12 | | 6 | _ |
13–14 | | 7 | _ |
15–16 | | 16 |
10
|
17–19 | | 19 | 180 |
20–32 | | 96 | 180 |
33–64 | – | | 180 |
65–256 | – | | 340 |
3 Conclusion and open questions
In our discussion, we have found that the theory of PSCAs and the theory of min-wise independent permutations can benefit considerably from each other. Despite the isomorphy of many concepts in these theories, strong interconnections seemed not to be exploited in the past (perhaps because one theory consistently uses probabilistic language). By combining the latter theories, we have improved several bounds and established polynomial boundedness for
\(g(n,k)\), which Yuster asked for in [
14]. Furthermore, we achieved progress in another question appearing in [
14] which asks to find the right order of magnitude of
\(g(n,3)\): The quasi-linear upper bound (established in [
14]) is tightened by a factor of
\(\log _2\left( n\right) ^{0.81}\) (cf. (
8)). It remains open by how much lower and upper bounds for
\(g(n,3)\) can still be improved.
The great difficulty, already for
\(k\in \left\{ 3,4\right\} \) and small
n, to determine existence of PSCAs (on a certain number of rows) manifests itself in some works, which come up with computationally intensive search procedures [
5,
11]. It would be highly interesting to find out whether the regularity, that PSCAs have compared to SCAs, facilitates the determination of the complexity class of the problem of calculating
\(g(n,k)k!\), the minimum number of rows able to host a PSCA. For SCAs the respective problem concerning the minimal row count is still open (even if in [
2] NP-completeness has been established for an altered problem).
Aiming to calculate further exact values of
\(g(n,k)\), we experimentally tried, for
n being a divisor of
\(\lambda k!\), to seek small PSCAs by restricting the search space to a class of matrices
A (having permutations as rows) and satisfying the following “reflection symmetry” property: For any column indices
\(j_1<j_2\), the
\((j_1,j_2)\)-submatrix of
A satisfies that if
h rows coincide with
\((a,b)\in [n]^2\), then also
h rows coincide with (
b,
a). The motivation behind this additional assumption is that recently PSCAs being unions of cosets of
\(S_n\) have successfully been found (cf. [
11]) for several parameter constellations
\((n,k,\lambda )\). We suspect that our proposed kind of symmetry induces a suitable balancing of symbols being advantageous for finding PSCAs, too.
It appears that within the class of matrices having uniform columnwise distribution of symbols (cf. [
5]), this latter constraint still allows to find representatives of PSCAs. Indeed, by a recursive search for strength
\(k=3\), appending column to column, we find that such special representatives exist for the parameter constellation
\((n,k,\lambda )\in \left\{ (3,3,1),(6,3,2)\right\} \). Existence for the constellation (9, 3, 3) could no longer be determined due to computational limitations and we would find it interesting to investigate this case with more dedicated computational effort. The representative of
\({\text {PSCA}}(6,4,1)\) presented in [
10, Proposition 2.22] is reflection symmetric, too. For strength
\(k=4\), the constellation
\((n,k,\lambda )=(8,4,3)\) is next, for which it is still open whether it possesses such a special representative (since it was shown in [
5] that
\({\text {PSCA}}(8,4,2)=\emptyset \)).
Combinatorial aspects (e.g. enumeration for small n and efficient constructions) of the class of matrices satisfying the latter reflection symmetry might be of independent interest.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.