Roth's Theorem with Random Common Differences

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $(p_n)_{n\ge1}$ be a sequence in $[0,1]$. Form a random subset $S\subset\mathbb N$ by including each $n$ independently with probability $p_n$. A set $S$ is a set of two-recurrence if every $A\subset\mathbb N$ of positive upper density, \[ \overline d(A)=\limsup_{N\to\infty}\frac{|A\cap\{1,\ldots,N\}|}{N}>0, \] contains three distinct terms $a,a+d,a+2d$ with $d\in S$. The probability-one assertion concerns this simultaneous property for every such $A$, rather than a separate event for each fixed $A$.

Statement recorded in the supplied source.

Determine conditions on the inclusion probabilities $(p_n)$ under which $S$ is almost surely a set of two-recurrence. In particular, does this hold whenever $p_n=\min\{1,\omega(n)/n\}$ for a function $\omega:\mathbb N\to(0,\infty)$ satisfying $\omega(n)\to\infty$? The required conclusion is that, with probability one, every positive-upper-density set of integers contains a nontrivial three-term arithmetic progression whose common difference lies in $S$. [S1][S2]

Short English statement

Which independent random sets of allowed positive common differences preserve Roth's theorem for every positive-density set? The optimistic target permits inclusion probabilities only a diverging factor above $1/n$.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 100 (GREEN-010). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Ben Green, 100 Open Problems, author manuscript with December 2025 updates, Problem 10 and its comments, pp. 7--8. https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.