Gaps in Multiplicative Sidon Sets

Abstract

For a positive integer $n$, let $g(n)$ denote the infimum of all real numbers $L$ such that there exists a multiplicative Sidon set $A\subseteq \{1,2,\dots ,n\}$ that intersects every interval $[x,x+L]\subseteq [1,n]$. Sárközy asked for estimates on $g(n)$, and he in particular asked whether one has $g(n)\le \sqrt{n}$ for every $n\in \mathbb{N}$. We first show that this estimate does indeed hold, with a proof that was autonomously discovered and formally verified in Lean by Aristotle. Next, we improve the upper bound further and, with $\ddot{I}=\frac{13-\sqrt{69}}{10}<0.47$, prove that $g(n){\ll }_{\epsilon }{n}^{\ddot{I}+\epsilon }$ for every $\epsilon >0$.

7 pages