An ``average distance'' inequality for large subsets of the cube (Q757399)

For a subset \(A\subset \{0,1\}^ n\) the average distance in A is defined by \(dist(A)=\frac{1}{| A|^ 2}\sum_{x\in A}\sum_{y\in A}H(x,y)\), where \(H(x,y)=| \{i| x_ i\neq y_ i\}|\) is the Hamming distance between \((x_ 1,...,x_ n)\) and \((y_ 1,...,y_ n)\). We show that \(dist(A)\geq \frac{n+1}{2}-\frac{2^{n-1}}{| A|}\) for every \(A\subset \{0,1\}^ n\). This bound is good for large subsets of the cube. It is tight for \(| A| =2^{n-1}\), where the subcubes of dimension n-1 are the only extremal configurations.