У меня и Воутер ван Дорна на arXiv опубликована статья «Темпы роста последовательностей, определяемые бесквадратными свойствами её сдвигов». В этой статье мы отвечаем на несколько вопросов Эрдаша (задачи 1102 и 1103 на веб-сайте задач Эрдаша) о том, как быстро может расти последовательность возрастающих натуральных чисел, если ограничить её сдвиги взаимодействием с множеством бесквадратных чисел различными способами.
Например, Эрдёш определил, что последовательность обладает «Свойством P», если каждый из её сдвигов пересекается только в конечном числе точек. Эрдёш считал это довольно ограничивающим условием, написав: «Вероятно, последовательность, обладающая свойством P, должна расти довольно быстро, но у меня нет результатов в этом направлении».
Мы показываем, что, хотя эти последовательности должны иметь плотность ноль, они могут расти сколь угодно медленно в том смысле, что можно иметь для всех достаточно больших и любой заданной функции, которая стремится к бесконечности. Например, можно найти последовательность, которая растёт как :
* Эрдёш заметил, что любая достаточно быстро растущая (допустимая) последовательность будет обладать свойством P, но далее Эрдёш пишет: «У меня нет точной информации о скорости увеличения, которой должна обладать последовательность, имеющая свойство Q».
Наши результаты в этом направлении могут быть неожиданными: мы показываем, что существуют последовательности со свойством P с плотностью ровно . Это требует рекурсивной конструкции решета, в которой начинается с начальной шкалы и находится гораздо большее число такое, что является бесквадратным для большинства бесквадратных чисел (и для всех бесквадратных чисел).
Эрдёш пишет: «На самом деле можно найти последовательность, которая растёт экспоненциально. Должна ли такая последовательность действительно расти так быстро? Я не думаю, что существует такая последовательность с полиномиальным ростом». Здесь наши результаты относительно слабы: мы можем построить такую последовательность, которая растёт как , но не знаем, является ли это оптимальным вариантом; лучшая нижняя граница, которую мы можем получить для роста, исходя из большого решета, равна .
Мы подозреваем, что дальнейший прогресс в решении этой проблемы требует достижений в теории обратных решёток.
Эрдёш также упоминает о другом свойстве, называемом свойством Q, которое утверждает, что существует бесконечно много таких, что все элементы (не только маленькие) являются бесквадратными. Здесь ситуация близка, но не совсем такая же, как для свойства P; мы показываем, что последовательности со свойством Q должны иметь верхнюю плотность строго меньше, но могут иметь плотность, сколь угодно близкую к этому значению.
Наблюдение Ружи состоит в том, что первая последовательность больше второй для бесконечно многих . Эрдёш спросил: «Вероятно, это верно для всех больших x. Было бы интересно оценить A(x) как можно точнее».
Для всех достаточно больших . Численно кажется, что на самом деле эта гипотеза верна для всех :
Для полного подтверждения гипотезы во всех случаях потребуется дополнительная работа. Это потенциально может быть краудсорсинговым проектом (подобно проекту Эрдаша — Гая — Селфриджа, о котором сообщалось в предыдущем сообщении в блоге).