Autocorrelations of Random Binary Sequences

We define Bₙ to be the set of n -tuples of the form (a₀, …\,, aₙ₋₁) where aⱼ = ± 1 . If A ∈ Bₙ , then we call A a binary sequence and define the autocorrelations of A by cₖ := ∑ⱼ₌₀ⁿ⁻ᵏ⁻¹ aⱼ aⱼ₊ₖ for 0 ≤ k ≤ n-1 . The problem of finding binary sequences with autocorrelations ‘near zero’ has arisen in communications engineering and is also relevant to conjectures of Littlewood and Erdős on ‘flat’ polynomials with ± 1 coefficients. Following Turyn, we define \[ b(n) := min_{A ∈ { B}_n} max1 ≤ k ≤ n-1 |c_k|.\] The purpose of this article is to show that, using some known techniques from discrete probability, we can improve upon the best upper bound on $b(n)$ appearing in the previous literature, and we can obtain both asymptotic and exact expressions for the expected value of cₖᵐ if the aⱼ are independent ± 1 random variables with mean 0. We also include some brief heuristic remarks in support of the unproved conjecture that b(n) = O(√n) .