Scrambling permutations and related structures : Asymtotics and constructions

Abstract

Eine Familie von Permutationen der symmetrischen Gruppe S_n heißt k-scrambling, falls zu jeder beliebigen Abfolge paarweise verschiedenener Positionen (p_1,...,p_k) eine Permutation existiert, deren Auswertung in p_1 minimal unter den restlichen Auswertungen in p_j ist. Die speziellere Eigenschaft vollständig k-scrambling zu sein, erfordert darüber hinaus, dass die sukzessiven Auswertungen in p_1,...,p_k eine monoton steigende Folge bilden. Familien, die zusätzlichen Verschärfungen letzterer beider Eigenschaften genügen, nennt man k-restricted min-wise independent bzw. stimmen im zweiteren, stärkeren Fall (bis auf isomorphe Identifikation) mit Perfect Sequence Covering Arrays (PSCAs) der Stärke k überein. Die Bestimmung von Permutationsfamilien, die diesen unterschiedlich starken Eigenschaften genügen und möglichst kleine (oder gar minimal mögliche) Kardinalität besitzen, ist nicht-trivial und von großer Bedeutung für andere mathematische Richtungen (Ordnungstheorie, Geometrie, Graphentheorie etc.) sowie für eine Vielzahl praktischer Anwendungen wie etwa automatisiertes Testing von Software und schnelle Ähnlichkeitsschätzung von Dokumenten für Suchmaschinen. Wir analysieren das asymptotische Verhalten dieser kleinstmöglichen Kardinalitäten und befassen uns auch mit algorithmischen Zugängen, um solche Familien explizit zu konstruieren. Hierbei gelingt es uns eine offene Frage von R. Yuster nach der polynomialen Beschränktheit der Größen von PSCAs [Yus20] positiv zu beantworten; wir erhalten außerdem verbesserte asymptotische untere Schranken sowie für k=3 und k=4 verbesserte asymptotische obere Schranken. Auch im nicht-asymptotischen Bereich – also für konkrete, kleine Werte von n – erreichen wir für k=3 und k=4 einige Verbesserungen (bis zu Faktor 7.5 im Vergleich zum derzeit verfügbaren State of the art in der Literatur). Abschließend schlagen wir eine neue Klasse von Permutationsfamilien vor, die einer gewissen Spiegelungssymmetrie genügen, und nutzen sie zur Ausdünnung des Suchraumes, der überprüft werden muss, um PSCAs computergestützt systematisch via Backtracking zu suchen. Diese Klasse könnte womöglich nützlich sein, um mit ausreichend Rechenleistung künftig weitere Verbesserungen im nicht-asymptotischen Bereich zu erzielen.

A family of permutations of the symmetric group S_n is called k-scrambling if for any sequence of pairwise distinct positions (p_1,...,p_k) there exists a permutation whose evaluation in p_1 is minimal among the remaining evaluations in p_j. Moreover, the more special property of being completely k-scrambling requires that the successive evaluations in p_1,...,p_k form a monotonically increasing sequence. Families satisfying additional sharpenings of the latter two properties are k-restricted min-wise independent or, in the second, stronger case coincide (up to isomorphic identification) with perfect sequence covering arrays (PSCAs) of strength k. Determining permutation families that satisfy these differently strong properties and have small (or even minimal possible) cardinality is non-trivial and of great importance for other mathematical branches (order theory, geometry, graph theory, etc.) as well as for a variety of practical applications such as automated testing of software and fast similarity estimation of documents for web search engines. We analyze the asymptotic behavior of these smallest possible cardinalities and also address algorithmic approaches to construct such families explicitly. Here we succeed in answering positively an open question of R. Yuster on the polynomial boundedness of the cardinalities of PSCAs [Yus20]; we also obtain improved asymptotic lower bounds and for k=3 and k=4 improved asymptotic upper bounds. Even in the non-asymptotic range – i.e., for concrete, small values of n – we achieve some improvements for k=3 and k=4 (up to a factor of 7.5 compared to the currently available state of the art in the literature). Finally, we propose a new class of permutation families that satisfy a certain reflection symmetry, and use it to restrict the search space that needs to be scanned in order to computationally seek PSCAs systematically via backtracking. This class could potentially be useful to achieve further improvements in the non-asymptotic range in the future with sufficient computational power.