Cross-intersection bound from cube separation

ID: cross-intersection-bound-from-cube-separation

If two nonempty set families on coordinates have every cross-intersection greater than an integer , their density product obeys the displayed bound. Complementing the second set family separates it from the first by Hamming distance greater than . Harper inequality bounds the first set family's radius- neighbourhood from below. If , disjointness yields . The binary entropy function tail estimate bounds these two factors by Gaussian tails; their deficits from the middle rank sum to at least , proving the claim.

New to topics? Read the docs here!