Résumé
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.