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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>X</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>X</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>=</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>X</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> 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.