Antichain Codes

A family of sets $A$ is said to be an antichain if $x\subset ̸y$ for all distinct $x,y\in A$, and it is said to be a distance-$r$ code if every pair of distinct elements of $A$ has Hamming distance at least $r$. Here, we prove that if $A\subset 2^{[n]}$ is both an antichain and a distance-$(2r+1)$ code, then $\mathrm{\mid }A\mathrm{\mid }=O_r(2^n{n}^{-r-1\mathrm{/}2})$. This result, which is best-possible up to the implied constant, is a purely combinatorial strengthening of a number of results in Littlewood–Offord theory; for example, our result gives a short combinatorial proof of Hálasz’s theorem, while all previously known proofs of this result are Fourier-analytic.