12.6. Асимптотические результаты

Определим нумератор

и сопоставим заданной последовательности V, превосходящей все свои собственные суффиксы, ряд

Тогда

Рекуррентное соотношение

приводит к уравнению

откуда

Пусть (не обязательно различные) комплексные корни многочлена Тогда

Следовательно,

что доказывает такую теорему:

12.62. Теорема.

где комплексные числа, определенные уравнением

Эта теорема дает точное выражение для но оно зависит от комплексных чисел Для конечных значений вычислять обычно легче по рекуррентному соотношению теоремы 12.35, так как эти вычисления относятся только к целым числам. Однако полученное уравнение очень полезно для получения асимптотических результатов.

12.63. Определение. Пусть

Так как все коэффициенты многочлена неотрицательные числа, не превосходящие то легко видеть, что числа с максимальным модулем вещественны и положительны и Ясно, что для больших

в том смысле, что

Аналогично,

Если

и

где превосходит все свои собственные суффиксы и X — максимальная подпоследовательность то

Другими словами, если фиксировать отношение и считать быстрорастущими, то

или, более точно,

Для данного функция является довольно сложной. Для того чтобы ее найти, надо сначала написать -ичное представление числа . Если превосходит все свои собственные суффиксы, то полагаем в противном случае полагаем где X — наименьший префикс, для которого . В качестве V выбирается затем наименьшая суперпоследовательность для определяется как логарифм (по основанию максимального взаимного корня многочлена

Пример функции для приведен на рисунке 12.1,

Рис. 12.1. График поведения как функции от .

Легко показать, что непрерывная монотонно невозрастающая функция от и. Нетрудно также показать, что производная от по и в каждой точке либо равна 0, либо не определена; при этом имеются точки неопределенности двух видов. Во-первых, концы интервалов, на которых постоянна. Точка и — левый конец такого интервала тогда и только тогда, когда конечная последовательность, превосходящая все свои собственные суффиксы; и — правый конец такого интервала тогда и только тогда, когда периодическая последовательность, равная некоторому своему суффиксу, но меньшая, чем все остальные суффиксы. В указанных концах интервалов не определена потому, что имеет производную только слева или только справа. Число точек такого типа счетно.

Более интересными представляются точки, в которых не имеет ни левой, ни правой производной. Это имеет место тогда и только тогда, когда бесконечная последовательность, превосходящая все свои собственные суффиксы, и 0 не является суффиксом и.

Множество точек и, в которых функция не дифференцируема, несчетно, но имеет меру 0. Питчер [1966] доказал также, что это множество имеет размерность по Хаусдорфу 1. Это обусловливается большой плотностью множества этих точек в окрестности точки . В общем случае можно высказать гипотезу, согласно которой размерность по Хаусдорфу множества точек на интервале а и [где ] равна . В некотором смысле представляется справедливым, что множество точек недифференцируемости функции в любом интервале сосредоточено вблизи левого конца этого интервала.

Для частного случая и изложенные выше результаты впервые были получены Манном. Он также показал, что единственный взаимный корень многочлена модуль которого больше 1. Таким образом, не только

но для достаточно больших

где означает ближайшее целое к х. К сожалению, этот более сильный результат не имеет места в общем случае. Для некоторых значений и многочлен имеет только один взаимный корень с модулем, большим единицы, а для других значений и многочлен имеет много таких взаимных корней. Мало также известно о том, какими функциями от и являются комплексные корни многочлена с меньшими модулями, хотя в этом направлении Логан [1967] получил некоторые предварительные неопубликованные результаты.