On Szemerédi’s theorem with differences from a random set
We consider, over both the integers and finite fields, Szemerédi’s theorem on $k$-term arithmetic progressions where the set $S$ of allowed common differences in those progressions is restricted and random. Fleshing out a line of enquiry suggested by Frantzikinakis et al., we show that over the integers, the conjectured threshold for $\Pr (d \in S)$ for Szemerédi’s theorem to hold a.a.s. follows from a conjecture about how so-called dual functions are approximated by nilsequences. We also show that the threshold over finite fields is different from this threshold over the integers.