A new bound for Erdős’ minimum overlap problem
Volume 208 / 2023
Acta Arithmetica 208 (2023), 235-255
MSC: Primary 05A17; Secondary 11B75, 42A05, 90C25.
DOI: 10.4064/aa220728-7-6
Published online: 16 August 2023
Abstract
Let $n$ be a positive integer. The minimum overlap problem is to determine the minimum $M(n)$ over all equal sized partitions $A \cup B = [2n]$ of the maximum intersection of $A$ and a translation of $B$. We obtain a substantially improved lower bound, that is, $\lim _{n \to \infty } M(n)/n \gt 0.379005$. Our approach uses elementary Fourier analysis to translate the problem to a convex optimization program.
