Аннотация:
Пусть $w$ – бесконечное (вправо) слово над алфавитом из $q$ букв. Его подслова образованы отрезками подряд идущих букв, а арифметические подслова – отрезками вдоль арифметических прогрессий (например, слово оооопсбот есть арифметическое подслово слова обороноспособность). Асимптотика по $n$ числа подслов и числа арифметических подслов данной длины $n$ определяют сложность и арифметическую сложность слова соответственно. Какой может быть сложность слова, до конца не известно: есть ряд примеров и немного общих теорем. Мы приведем серию примеров слов, арифметическая сложность которых растет как $cn^{a}(1+o(1))$, где $a$ – трансцендентное, по всей видимости, число. Доказательство асимптотики опирается на тауберову теорему Винера о плотности сдвигов функции, преобразование Фурье которой не имеет вещественных нулей. Доклад основан на совместной работе с Жюльеном Кассенем и Анной Фрид.
|
