On simple additive configurations in random sets

We show that with high probability a random subset of [n] of
size \theta(n^{1-1/k}) contains two elements a and a+d^k, where d
is a positive integer. As a consequence, we prove an analogue of the
Sarkozy-Furstenberg theorem for a random subset of [n].