[23] Let be any infinite binary sequence. Show that for all constants c there are infinitely many m such that for all n with

[23] Let ω be any infinite binary sequence. Show that for all constants c there are infinitely many m such that for all n with m ≤

n ≤ 2m, C(ω1:n) ≤ n − c.

Comments. We are guaranteed to find long complexity oscillations (of length m) in an infinite binary sequence ω relatively near the beginning

(namely ωm:2m), even if ω is Martin-L¨of random. Source: [H.P. Katseff and M. Sipser, Theoret. Comput. Sci., 15(1981), 291–309].