О множествах с малым числом расстояний на плоскости

Основная информация

• ID статьи: 2510.09800
• Название: On Few-Distance Sets in the Plane
• Автор: Lucas Wang
• Классификация: math.MG (Метрическая геометрия), math.CO (Комбинаторика)
• Дата подачи: 10 октября 2025 г. на arXiv
• Ссылка на статью: https://arxiv.org/abs/2510.09800

Аннотация

В данной работе исследуется задача о максимальном размере множества точек на плоскости, определяющих не более k расстояний. Пусть $g(k)$ — максимальный размер множества точек на плоскости, определяющих не более k расстояний. Автор доказывает: $\frac{\pi}{3}C(\Lambda_{hex}) k\sqrt{\log k} (1+o(1)) \leq g(k) \leq C k\log k$

Таким образом, установлен порядок роста $g(k) \asymp k\sqrt{\log k}$ и даны явные константы из гексагональной решётки. Для произвольной арифметической решётки $\Lambda$ автор также доказывает: $g_\Lambda(k) \geq \frac{\pi}{4} S^*(\Lambda) k\sqrt{\log k} (1+o(1))$

Кроме того, статья содержит количественные результаты устойчивости: если только множество точек X не является линейно-тяжёлым и не имеет двух популярных непараллельных трансляций, то либо почти все упорядоченные пары находятся ниже верхних квантилей мультимножества расстояний (локализация около центра), либо постоянная доля X∩W лежит в одном классе вычетов по модулю 2Λ.

Исследовательский контекст и мотивация

Предыстория задачи

Данное исследование вытекает из обратной задачи к классической проблеме расстояний Эрдёша. Исходная задача была решена Гутом-Кацем, которые доказали, что n точек на плоскости определяют по крайней мере $\Omega(n/\log n)$ различных расстояний. Данная работа исследует обратную задачу: какое максимальное количество точек может содержать множество на плоскости, если оно определяет не более k расстояний?

Значимость задачи

1. Теоретическое значение: это фундаментальная задача комбинаторной геометрии, связывающая метрическую геометрию, теорию чисел и аддитивную комбинаторику
2. Технические трудности: требует объединения теории решёток, геометрии инцидентности и методов аддитивной энергии
3. Прикладная ценность: связана с теорией кодирования, оптимизацией дискретной геометрии и другими областями

Ограничения существующих методов

• Верхняя граница Гута-Каца $g(k) \lesssim k\log k$ недостаточно точна
• Конструкции с окнами решётки дают только нижнюю границу $g(k) \gtrsim k\sqrt{\log k}$
• Отсутствуют явные константы и количественный анализ устойчивости

Исследовательская мотивация

Определить точный порядок роста $g(k)$, предоставить явные константы и понять структурные характеристики экстремальных конструкций.

Основные вклады

1. Определение точного порядка роста: доказано $g(k) \asymp k\sqrt{\log k}$, заполнен логарифмический разрыв между верхней и нижней границами
2. Явные константы: даны явные константы Бернайса $C(\Lambda_{hex})$ для гексагональной решётки
3. Единая нижняя граница для семейств решёток: установлена единая формула нижней границы для всех арифметических решёток $\Lambda$
4. Количественная теорема устойчивости: охарактеризованы структурные особенности почти оптимальных конструкций
5. Технические инновации: развиты новые методы анализа окон решёток и методы аддитивной энергии

Подробное описание методов

Определение задачи

Для положительного целого числа k найти: $g(k) := \max\{|X| : X \subset \mathbb{R}^2, |D(X)| \leq k\}$ где $D(X) = \{|x-y| : x \neq y \in X\}$ — множество расстояний, определяемых множеством X.

Основная техническая схема

1. Нижняя граница: метод окна решётки

Для арифметической решётки $\Lambda = \mathbb{Z}v_1 \oplus \mathbb{Z}v_2$ рассмотрим дисковое окно: $W_R = (\tau + \Lambda) \cap B(z, R)$

По асимптотической формуле Бернайса-Ландау количество расстояний равно: $|D(W_R)| = \frac{C(\Lambda)}{s(\Lambda)} \frac{4R^2}{\sqrt{\log(4R^2/s(\Lambda))}}(1 + o(1))$

2. Верхняя граница: метод геометрии инцидентности

Используя результат Гута-Каца, любое множество из n точек на плоскости определяет по крайней мере $c n/\log n$ различных расстояний, откуда: $g(k) \leq C k \log k$

3. Ключевая лемма: подсчёт упорядоченных пар

Определим подсчёт упорядоченных расстояний: $Q_{ord}(X) := \sum_{t \in D(X)} m_t^2$ где $m_t = \#\{(p,q) \in X^2 : p \neq q, |p-q| = t\}$.

По неравенству Коши-Шварца: $Q_{ord}(X) \geq \frac{n^2(n-1)^2}{k}$

Технические инновационные моменты

1. Явное выражение параметров решётки

Введены нормализованные параметры: $S^*(\Lambda) := \frac{s(\Lambda)}{A(\Lambda)C(\Lambda)}$ где $s(\Lambda)$ — константа масштабирования, $A(\Lambda)$ — кообъём, $C(\Lambda)$ — константа Бернайса.

2. Теория внутренне регулярных окон

Определено понятие внутренне регулярного окна, установлен точный контроль реализации расстояний в окнах решётки:

Лемма 2.11: Для решётки $\Lambda$ и радиуса покрытия $\mu(\Lambda)$, когда $R > \mu(\Lambda)$: $\{\lambda \in \Lambda : |\lambda| \leq 2R - 2\mu(\Lambda)\} \subseteq \{x-y : x,y \in (\tau + \Lambda) \cap B(0,R)\}$

3. Анализ аддитивной энергии

Через аддитивную энергию $E_+(X) = \sum_v r_X(v)^2$ анализируется структура множества точек: $Q_{ord}(X) \leq E_+(X) + C n^3 \log n + O(n^2)$

Экспериментальная установка

Схема теоретической верификации

Данная работа является в основном теоретической, результаты проверяются следующим образом:

1. Асимптотический анализ: проверка применения формулы Бернайса-Ландау
2. Вычисление констант: расчёт конкретных параметров гексагональной решётки
3. Проверка граничных случаев: верификация известных результатов для малых значений k

Ключевые параметры

• Гексагональная решётка: $s(\Lambda_{hex}) = 2/\sqrt{3}$
• Вычисление радиуса покрытия и констант решётки
• Выбор параметров устойчивости

Результаты экспериментов

Основные результаты теорем

Теорема 3.4 (точные границы для арифметических решёток): Для нормализованной арифметической решётки $\Lambda$ ($\lambda_1(\Lambda) = 1$) существует $k_0(\Lambda)$ такое, что для всех $k \geq k_0(\Lambda)$: $\frac{\pi}{4} S^*(\Lambda) k\sqrt{\log k} (1 + o_\Lambda(1)) \leq g_\Lambda(k) \leq C k \log k$

Теорема 7.1 (глобальный результат): $\frac{\pi}{3} C(\Lambda_{hex}) k\sqrt{\log k} (1 + o(1)) \leq g(k) \leq C k \log k$

Результаты устойчивости

Теорема 7.3 (количественная устойчивость): Для множества точек $X \subset \mathbb{R}^2$, $|X| = n$, $|D(X)| \leq k$, $k \leq C n/\log n$, выполняется одно из следующих условий:

1. Некоторая прямая содержит по крайней мере $cn$ точек
2. Существуют непараллельные векторы $v_1, v_2$ и решёточный прямоугольник $W$ с большой степенью перекрытия
3. Существует $z \in X$ такой, что $|X \cap B(z, t_*)|$ близко к $n$

Ключевые оценки

По предложению 5.1, количество расстояний во внутренне регулярном окне $W_R$ удовлетворяет: $\frac{C(\Lambda)}{s(\Lambda)} \frac{4(1-c)^2R^2}{\sqrt{\log(4R^2/s(\Lambda))}}(1 + o(1)) \leq |D(W_R)| \leq \frac{C(\Lambda)}{s(\Lambda)} \frac{4R^2}{\sqrt{\log(4R^2/s(\Lambda))}}(1 + o(1))$

Связанные работы

История проблемы расстояний

1. Проблема расстояний Эрдёша: Гут-Кац (2015) доказали $m(n) \gtrsim n/\log n$
2. Случай малых k: Эрдёш-Фишберн определили точные значения для $k \leq 5$
3. Конструкции решёток: нижние границы получены через асимптотику Бернайса-Ландау

Связанные методы

1. Геометрия инцидентности: редукция Элекеша-Шамира и метод Гута-Каца
2. Аддитивная комбинаторика: теорема Балога-Семереди-Гауэрса и теорема Фреймана
3. Теория решёток: теория представления квадратичными формами и свойства покрытия

Преимущества данной работы

• Впервые определён точный порядок роста $k\sqrt{\log k}$
• Предоставлены явные константы и единая схема
• Развита новая теория устойчивости

Заключение и обсуждение

Основные выводы

1. Определён точный порядок роста $g(k) \asymp k\sqrt{\log k}$
2. Гексагональная решётка обеспечивает оптимальную конструкцию нижней границы
3. Почти оптимальные конструкции обладают специфическими структурными характеристиками

Ограничения

1. Точные значения констант допускают дальнейшие улучшения
2. Результаты устойчивости имеют сильную зависимость от параметров
3. Анализ неарифметического случая неполон

Направления будущих исследований

1. Улучшение явных констант
2. Расширение на многомерный случай
3. Исследование аналогичных задач при других геометрических ограничениях

Глубокая оценка

Достоинства

1. Теоретическая глубина: решена долгостоящая открытая задача, определён точный порядок роста
2. Технические инновации: искусное объединение теории решёток, аддитивной комбинаторики и геометрии инцидентности
3. Полнота результатов: не только асимптотические результаты, но и явные константы и анализ устойчивости
4. Единство методов: единая схема для всех арифметических решёток

Недостатки

1. Вычислительная сложность: вычисление явных констант достаточно сложно
2. Область применения: в основном ограничена арифметическими решётками
3. Параметры устойчивости: количественная устойчивость зависит от многих параметров

Влияние

1. Академическая ценность: решение фундаментальной задачи комбинаторной геометрии
2. Вклад методов: развитые методы применимы к связанным задачам
3. Теоретическое совершенствование: важное дополнение к теории проблем расстояний

Области применения

1. Оптимизация дискретной геометрии
2. Конструкции множеств расстояний в теории кодирования
3. Задачи представления квадратичными формами в теории чисел
4. Структурный анализ в аддитивной комбинаторике

Библиография

Ключевые ссылки в статье включают:

1. P. Erdős and P. C. Fishburn, "Maximum planar sets that determine k distances"
2. L. Guth and N. H. Katz, "On the Erdős distinct distances problem in the plane"
3. G. Elekes and M. Sharir, "Incidences in three dimensions and distinct distances in the plane"
4. Классические работы по асимптотической теории Бернайса-Ландау
5. Литература по теореме БСГ и теореме Фреймана в аддитивной комбинаторике

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