2025-11-23T02:07:24.002029

A Density Condition on Point Sets with Slowly-Scaling Distinct Dot Products

Gandhi

The distinct dot products problem, a variation on the ErdÅs distinct distance problem, asks "Given a set $P_n$ of $n$ points in $\mathbb{R}^2$, what is the minimum number $|D(P_n)|$ of distinct dot products formed between them, asymptotically?" The best proven lower-bound is $|D(P_n)| \gtrsim n^{2/3+7/1425}$, due to work by Hanson$\unicode{x2013}$Roche-Newton$\unicode{x2013}$Senger, and a recent improvement by Kokkinos. However, the slowest-scaling known constructions have $|D(P_n)|\sim n$, leaving quite a large gap in the bound. Finding a sublinearly-scaling construction, or disproving its existence, would narrow this gap. We provide a condition that a sequence of point configurations $(P_n)_{n \in \mathbb{N}}$ must satisfy in order for $|D(P_n)|$ to scale 'slowly' i.e. $|D(P_n)| \ll n^{3/4}$. Namely, we prove that any such configuration must contain a point-rich line that gets arbitrarily 'dense' as the sequence progresses.

academic

A Density Condition on Point Sets with Slowly-Scaling Distinct Dot Products

基本信息

论文ID: 2510.14585
标题: A Density Condition on Point Sets with Slowly-Scaling Distinct Dot Products
作者: Anshula Gandhi (University of Cambridge)
分类: math.CO (组合数学)
发表时间: 2025年10月16日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.14585

摘要

本文研究了不同点积问题(distinct dot products problem)，这是Erdős不同距离问题的一个变体。问题询问：给定 $\mathbb{R}^2$ 中 $n$ 个点的集合 $P_n$ ，它们之间形成的不同点积的最小数量 $|D(P_n)|$ 的渐近行为是什么？目前最好的下界是 $|D(P_n)| \gtrsim n^{2/3+7/1425}$ ，而已知最慢增长的构造具有 $|D(P_n)|\sim n$ 的规模，存在较大的界限差距。本文提供了点配置序列 $(P_n)_{n \in \mathbb{N}}$ 必须满足的条件，使得 $|D(P_n)|$ "缓慢"增长，即 $|D(P_n)| \ll n^{3/4}$ 。具体而言，证明了任何此类配置必须包含一条随着序列进展变得任意"稠密"的富点直线。

研究背景与动机

1. 核心问题

本文研究的不同点积问题是著名的Erdős不同距离问题的变体。给定平面上 $n$ 个点，问题是确定它们之间能形成的不同点积数量的最小值。这是一个基本的组合几何问题，具有重要的理论意义。

2. 问题重要性

理论意义: 该问题是组合几何中的经典问题，与加法组合学、调和分析等多个数学分支相关
技术挑战: 存在显著的上下界差距，目前最好的下界约为 $n^{2/3}$ ，而已知构造仅达到 $n$ 的线性增长
方法论价值: 研究此问题的技术可能应用于其他相关的组合问题

3. 现有方法局限性

下界技术: Hanson-Roche-Newton-Senger和Kokkinos的工作给出了 $n^{2/3+c}$ 的下界，但仍与线性上界存在差距
构造方法: 已知的最慢增长构造(如几何级数排列的点或圆上等间距点)都达到线性增长 $\sim n$
理论空白: 缺乏对亚线性增长可能性的深入理解

4. 研究动机

本文旨在填补理论空白，通过识别缓慢增长点配置必须满足的结构性条件，为最终解决上下界差距提供新的洞察。

核心贡献

密度条件定理: 证明了任何具有 $|D(P_n)| \ll n^{3/4}$ 的点配置序列必须包含一条"稠密"的富点直线
结构性刻画: 为缓慢增长的点配置提供了必要的几何结构条件
技术框架: 建立了分析直线-圆形配置的系统方法
理论洞察: 揭示了点配置密度与点积数量之间的深层联系

方法详解

任务定义

给定点配置序列 $(P_n)_{n \in \mathbb{N}}$ ，其中每个 $P_n$ 是 $\mathbb{R}^2$ 中 $n$ 个不同点的集合，定义点积集合 $D(P_n) := \{p_i \cdot p_j | p_i, p_j \in P_n\}$ 。目标是刻画使得 $|D(P_n)| \ll n^{3/4}$ 的配置的必要条件。

核心架构

1. 支撑直线和圆的分析

支撑直线定义: 给定点集 $P \subset \mathbb{R}^2$ ，其支撑直线是过原点且斜率来自集合 $R(P) := \{p_y/p_x | (p_x, p_y) \in P\}$ 的直线。

支撑圆定义: 支撑圆是以原点为圆心，半径来自集合 $R(P) := \{\sqrt{p_x^2 + p_y^2} | (p_x, p_y) \in P\}$ 的圆。

2. 流行直线和圆的存在性

引理3.6 (流行直线的存在性): 对于具有 $\ll n^α$ 个点积的配置序列，必存在包含 $\gg n^{2-2α}$ 个点的"流行直线"。

引理4.6 (流行圆的存在性): 对于具有 $\ll n^α$ 个点积的配置序列，必存在包含 $\gg n^{1-α}$ 个点的"流行圆"。

3. 直线-圆配置的点积计数

通过复点积的概念 $p \star q := |p||q|e^{i(\arg p - \arg q)}$ ，分析直线上点与圆上点之间的点积数量。

技术创新点

1. 桶划分技术

将实轴划分为"桶" $B_i$ ，每个桶对应几何级数中相邻项之间的区间。通过分析复点积在各桶中的投影，计算不同点积的数量。

2. 密度条件的引入

定义6.2 ( $b$ -稠密): 称 $\ell$ 个共线点的集合 $L$ 为 $b$ -稠密，如果存在 $\sim \ell$ 对相邻点 $p, q \in L$ 使得 $|p|/|q|$ 落在区间 $(b,1)$ 内。

3. 反证法框架

通过证明如果所有富点直线都满足良好间距条件，则必有 $|D(P_n)| \gtrsim n^{3/4}$ ，从而得出缓慢增长配置的密度条件。

主要结果

核心定理

定理6.3 (缓慢增长的密度条件): 设 $(P_n)_{n \in \mathbb{N}}$ 是点配置序列，其中每个 $P_n$ 是 $\mathbb{R}^2$ 中 $n$ 个不同点的集合，且 $|D(P_n)| \ll n^{3/4}$ 。则对所有 $b \in (0,1)$ ，存在子序列使得子序列中每个配置都包含一个 $b$ -稠密的点集 $L$ ，该集合沿过原点的直线排列且 $|L| \gtrsim n^{1/2}$ 。