The independence of two randomness properties of sequences over finite fields

We prove the logical independence of a complexity-theoretic and a statistical randomness property of sequences over a finite field. The two properties relate to the linear complexity profile and to the ∞-distribution of sequences, respectively. The proofs are given by constructing counterexamples to the presumed logical implications between these two properties.

► Complexity-theoretic and statistical randomness properties are usually independent. ► A good linear complexity profile need not imply an ∞-distribution. ► An ∞-distribution need not imply a good linear complexity profile.