Exact Expressions for the Maximal Probability that all k-wise Independent Bits are 1

Abstract Let M ( n , k , p ) denote the maximum probability of the event $$X_1 = X_2 = \cdots = X_n=1$$ X 1 = X 2 = ⋯ = X n = 1 under a k -wise independent distribution whose marginals are Bernoulli random variables with mean p . A long-standing question is to calculate M ( n , k , p ) for all values of n , k , p . This problem has been partially addressed by several authors, primarily with the goal of answering asymptotic questions. The present paper focuses on obtaining exact expressions for this probability. For a wide range of parameters n , k , and p , we find exact expressions for M ( n , k , p ). We also present results from several numerical studies, giving rise to eight open conjectures.