On two-point configurations in random set

Hoi Nguyen

We show that with high probability a random set of size $\Theta (n^{1-1/k})$ of $\{1,...,n\}$ contains two elements $a$ and $a+d^k$, where $d$ is a positive integer. As a consequence, we…