PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

A new bound for Erdős’ minimum overlap problem

Volume 208 / 2023

Ethan Patrick White Acta Arithmetica 208 (2023), 235-255 MSC: Primary 05A17; Secondary 11B75, 42A05, 90C25. DOI: 10.4064/aa220728-7-6 Published online: 16 August 2023


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.


  • Ethan Patrick WhiteDepartment of Mathematics
    The University of British Columbia
    Vancouver, BC
    Canada V6T 1Z2

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image