Maximal arithmetic progressions in random subsets (Q2461042)

The authors study the length of maximal progressions in a random uniform subset of \(\{0,1\}^N\). That is, let \(\xi_1,\xi_2,\dots,\xi_N\) be a random word in \(\{0,1\}^N\), chosen uniformly. Consider the random set \(\Xi_N\) of elements \(i\) such that \(\xi_i=1\). Let \(U^{(N)}\) denote the maximal length arithmetic progression in \(\Xi_N\), and let \(W^{(N)}\) denote the maximal length aperiodic arithmetic progression \(\pmod N\) in \(\Xi_N\). A consequence of the main result is that the expectation of both \(U^{(N)}\) is roughly \(2\log N/\log 2'\). They also show that the limit law of the centered version of both \(W^{(N)}\) is of the same extreme type as that of the longest run in \(\Xi_n\).