Аннотация:
Обозначим через $\|n\|$ сложность числа $n$, т.е. наименьшее число единиц, необходимое для записи $n$ с использованием произвольного числа сложений, умножений и скобок. Хорошо известно двустороннее неравенство $3\log_3 n\leq\|n\|\leq 3\log_2 n$, имеющее место для всех $n$ и свидетельствующее о логарифмическом поведении функции сложности $\|n\|$. В то время как нижняя оценка $3\log_3 n$ достигается бесконечно часто на степенях числа $3$, наилучшая верхняя оценка до сих пор остаётся неизвестной, хотя и получены некоторые улучшения тривиальной границы $3\log_2 n$. Кроме того, для "типичных" чисел, т.е. для почти всех чисел $n$, справедливо более сильное неравенство $\|n\|\leq C_{avg}\log n$, где, важно отметить, $C_{avg}\approx 3.236<\sup_{n} \frac{\|n\|}{\log n}$ .
Мы покажем, что на самом деле выполнено $\|n\|\leq C_{avg}\log n+o(\log n)$ при $n\to\infty$, откуда, в частности, вытекает, что $\limsup\limits_{n\to\infty}\frac{\|n\|}{\log n}\leq C_{avg}$. Мы также получим первую нетривиальную оценку снизу $\|n\|\geq 3.06\log_3 n$ для почти всех $n$.
Доклад основан на совместной работе с Сергеем Владимировичем Конягиным
Ссылка на онлайн трансляцию семинара https://mian.ktalk.ru/awo7gpxikhtb?pinCode=9201
|
