Аннотация:
Бинарная функция разбиения $b(n)$ – это функция натурального аргумента $n$, равная количеству всевозможных разложений $n$ в сумму степеней двойки (не обязательно различных). Задача об асимтотическом поведении $b(n)$ при $n\to \infty$ восходит к Л.Эйлеру. Она была в основном решена
Малером в 1940, затем асимптотика уточнялась в работах де Брёйна, Пеннингтона, Кнута, Фрёйберга.
В более общей постановке, задано множество целых неотрицательных чисел $D$ (“словарь”),
и количество раз, которое каждая степень двойки встречается в разложении числа $n$ должно принадлежать $D$. Полученная функция разбиения $b_D(n)$ изучалась для различных словарей $D$
в работах Таттурри, Карлитца, Резника, Дюмона, Сидорова, Томаса, Харе, и др.
Оказывается, что асимптотика функции $b_D(n)$ тесно связана со свойствами решений одного класса функциональных уравнений. Такие уравнения детально изучались в литературе, но в связи с совсем другими задачами. Применяя эту связь, удается получить точную информацию об асимптотке функции $b_D(n)$ для произвольных конечных словарей $D$. В частности, охарактеризовать все словари, для которых эта функция имеет степенной рост. Вопрос о регулярном степенном росте решен “в принципе”, а окончательное решение упирается в одну открытую проблему о циклотомических полиномах. Ряд других открытых проблем также будет сформулирован.
|
