Convergence of the number of period sets in strings
Convergence du nombre d'ensembles de périodes d'un mot
Résumé
Consider words of length n. The set of all periods of a word of length n is a subset of {0, 1, 2,. .. , n−1}. However, any subset of {0, 1, 2,. .. , n−1} is not necessarily a valid set of periods. In a seminal paper in 1981, Guibas and Odlyzko have proposed to encode the set of periods of a word into an n long binary string, called an autocorrelation, where a one at position i denotes a period of i. They considered the question of recognizing a valid period set, and also studied the number of valid period sets for length n, denoted κn. They conjectured that ln(κn) asymptotically converges to a constant times ln 2 (n). If improved lower bounds for ln(κn)/ ln 2 (n) were proposed in 2001, the question of a tight upper bound has remained opened since Guibas and Odlyzko's paper. Here, we exhibit an upper bound for this fraction, which implies its convergence and closes this long standing conjecture. Moreover, we extend our result to nd similar bounds for the number of correlations: a generalization of autocorrelations which encodes the overlaps between two strings.
Considérons des mots de longueur $n$ sur un alphabet donné. L'ensemble de toutes les périodes d'un mot de longueur $n$ est un sous-ensemble de $\{0,1,2,\ldots,n-1\}$. Cependant, tout sous-ensemble de $\{0,1,2,\ldots,n-1\}$ n'est pas nécessairement un ensemble valide de périodes. Dans un article fondateur de 1981, Guibas et Odlyzko ont proposé de coder l'ensemble des périodes d'un mot dans une chaîne binaire de longueur $n$, appelée autocorrélation, où un 1 à la position $i$ indique que $i$ est une période. Ils ont examiné la question de la reconnaissance d'un ensemble de périodes valide, et ont également étudié le nombre d'ensembles de périodes valides, noté $\kappa_n$, pour une longueur de $n$. Ils ont conjecturé que $\ln(\kappa_n)$ converge asymptotiquement vers une constante fois $\ln^2(n)$. Si de meilleures bornes inférieures pour $\ln(\kappa_n)/\ln^2(n)$ ont été exhibées en 2001, la question d'une borne supérieure reste ouverte depuis l'article de Guibas et Odlyzko. Ici, nous exposons une borne supérieure pour cette fraction, ce qui implique sa convergence et clôt cette conjecture de longue date. En outre, nous étendons notre résultat pour trouver des bornes similaires pour le nombre de corrélations : une généralisation des autocorrélations qui encode les chevauchements entre deux chaînes.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
