A polynomial construction of perfect sequence covering arrays

Gentle, Aidan R.

doi:10.5802/alco.308

Gentle, Aidan R.¹

¹ School of Mathematics Monash University Vic 3800, Australia

Algebraic Combinatorics, Volume 6 (2023) no. 5, pp. 1383-1394.

Abstract

A PSCA $(v, t, λ)$ is a multiset of permutations of the $v$ -element alphabet ${0, \dots, v - 1}$ such that every sequence of $t$ distinct elements of the alphabet appears in the specified order in exactly $λ$ permutations. For $v ⩾ t$ , let $g (v, t)$ be the smallest positive integer $λ$ such that a PSCA $(v, t, λ)$ exists. Kuperberg, Lovett and Peled proved $g (v, t) = O (v^{t})$ using probabilistic methods. We present an explicit construction that proves $g (v, t) = O (v^{t (t - 2)})$ for fixed $t ⩾ 4$ . The method of construction involves taking a permutation representation of the group of projectivities of a suitable projective space of dimension $t - 2$ and deleting all but a certain number of symbols from each permutation. In the case that this space is a Desarguesian projective plane, we also show that there exists a permutation representation of the group of projectivities of the plane that covers the vast majority of 4-sequences of its points the same number of times.

Received: 2022-10-02
Revised: 2023-03-27
Accepted: 2023-03-30
Published online: 2023-11-07

DOI: 10.5802/alco.308

Classification: 05B30, 05B40, 20B25, 51E20
Keywords: sequence covering array, permutation representation, exact covering, projective geometry

Author's affiliations:

Gentle, Aidan R. ¹

¹ School of Mathematics Monash University Vic 3800, Australia

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2023__6_5_1383_0,
     author = {Gentle, Aidan R.},
     title = {A polynomial construction of perfect sequence covering arrays},
     journal = {Algebraic Combinatorics},
     pages = {1383--1394},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {5},
     year = {2023},
     doi = {10.5802/alco.308},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.308/}
}

TY  - JOUR
AU  - Gentle, Aidan R.
TI  - A polynomial construction of perfect sequence covering arrays
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 1383
EP  - 1394
VL  - 6
IS  - 5
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.308/
DO  - 10.5802/alco.308
LA  - en
ID  - ALCO_2023__6_5_1383_0
ER  -

%0 Journal Article
%A Gentle, Aidan R.
%T A polynomial construction of perfect sequence covering arrays
%J Algebraic Combinatorics
%D 2023
%P 1383-1394
%V 6
%N 5
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.308/
%R 10.5802/alco.308
%G en
%F ALCO_2023__6_5_1383_0

Gentle, Aidan R. A polynomial construction of perfect sequence covering arrays. Algebraic Combinatorics, Volume 6 (2023) no. 5, pp. 1383-1394. doi : 10.5802/alco.308. https://alco.centre-mersenne.org/articles/10.5802/alco.308/

References
Cited by

[1] Ball, Simeon; Lavrauw, Michel Arcs in finite projective spaces, EMS Surv. Math. Sci., Volume 6 (2019) no. 1-2, pp. 133-172 | DOI | MR | Zbl

[2] Chee, Yeow Meng; Colbourn, Charles J.; Horsley, Daniel; Zhou, Junling Sequence covering arrays, SIAM J. Discrete Math., Volume 27 (2013) no. 4, pp. 1844-1861 | DOI | MR | Zbl

[3] Dushnik, Ben Concerning a certain set of arrangements, Proc. Amer. Math. Soc., Volume 1 (1950), pp. 788-796 | DOI | MR | Zbl

[4] Gentle, Aidan R.; Wanless, Ian M. On perfect sequence covering arrays, Ann. Comb., Volume 27 (2023), pp. 539-564 | DOI | MR

[5] Hirschfeld, J. W. P. Projective geometries over finite fields, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979, xii+474 pages | MR

[6] Itoh, Toshiya; Takei, Yoshinori; Tarui, Jun On permutations with limited independence, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), ACM, New York (2000), pp. 137-146 | MR | Zbl

[7] Iurlano, Enrico Growth of the perfect sequence covering array number, Des. Codes Cryptogr., Volume 91 (2023) no. 4, pp. 1487-1494 | DOI | MR | Zbl

[8] Klein, Andreas On perfect deletion-correcting codes, J. Combin. Des., Volume 12 (2004) no. 1, pp. 72-77 | DOI | MR | Zbl

[9] Kuhn, D. Richard; Higdon, James M.; Lawrence, James F.; Kacker, Raghu N.; Lei, Yu Combinatorial methods for event sequence testing, 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation, IEEE (2012), pp. 601-609 | DOI

[10] Kuperberg, Greg; Lovett, Shachar; Peled, Ron Probabilistic existence of regular combinatorial structures, Geom. Funct. Anal., Volume 27 (2017) no. 4, pp. 919-972 | DOI | MR | Zbl

[11] Levenshteĭn, V. I. Perfect codes in the metric of deletions and insertions, Diskret. Mat., Volume 3 (1991) no. 1, pp. 3-20 | DOI | MR | Zbl

[12] Mathon, Rudolf; Tran, Van Trung Directed $t$ -packings and directed $t$ -Steiner systems, Volume 18, 1999 no. 1-3, pp. 187-198 (Designs and codes—a memorial tribute to Ed Assmus) | DOI | MR | Zbl

[13] Na, Jingzhou; Jedwab, Jonathan; Li, Shuxing A group-based structure for perfect sequence covering arrays, Des. Codes Cryptogr., Volume 91 (2023) no. 3, pp. 951-970 | DOI | MR | Zbl

[14] Singer, James A theorem in finite projective geometry and some applications to number theory, Trans. Amer. Math. Soc., Volume 43 (1938) no. 3, pp. 377-385 | DOI | MR | Zbl

[15] Spencer, J. Minimal scrambling sets of simple orders, Acta Math. Acad. Sci. Hungar., Volume 22 (1971/72), pp. 349-353 | DOI | MR | Zbl

[16] Thas, J. A. Some results concerning ${(q + 1) (n - 1); n}$ -arcs and ${(q + 1)$ $(n - 1) + 1; n}$ -arcs in finite projective planes of order $q$ , J. Combinatorial Theory Ser. A, Volume 19 (1975) no. 2, pp. 228-232 | DOI | MR | Zbl

[17] Yuster, Raphael Perfect sequence covering arrays, Des. Codes Cryptogr., Volume 88 (2020) no. 3, pp. 585-593 | DOI | MR | Zbl

Cited by Sources: