Proof of a conjecture on word complexity
Florence Levé, Patrice Séébold · Bulletin of the Belgian Mathematical Society - Simon Stevin · 2001
An integer n is k-reachable if there exists a word of length k which contains exactly n non-empty different factors.Given k, all the k-reachable integers are between k and k(k+1) 2 but, between these two values, not all the integers are k-reachable.We give a general construction which associates to each k a family of words containing for each k-reachable integer n, exactly one word having n different factors.This also proves the conjecture of Kása about the smallest number m k such that all the integers between m k and k(k+1) 2 are k-reachable. RésuméUn entier n est k-atteignable s'il existe un mot de longueur k contenant exactement n facteurs non vides différents.Étant donné k, tous les entiers k-atteignables sont compris entre k et k(k+1) 2; mais entre ces deux valeurs, tous les entiers ne sont pas k-atteignables.Nous donnons une construction générale pour associer à chaque k une famille de mots qui, pour tout entier k-atteignable n, contient exactement un mot ayant n facteurs différents.Cette construction nous permet également de prouver la conjecture de Kása concernant le plus petit nombre m k tel que tous les entiers compris entre m k et k(k+1) 2 sont k-atteignables.