Paperlane

no. 5 · Friday 30 October 2026

Average pairwise Hamming distance of a subset in a hypercube

Yijia Fang and Hao Huang

math.CO

Abstract

In this note, we prove that for a subset $\mathcal{F}$ of $\{0,1\}^n$ of density $\frac{1}{8}$, its average pairwise Hamming distance is at least $\frac{n-3}{2}$, with equality attained only by $(n-3)$-dimensional subcubes. This answers a question of Lei Yu, and solves an important open case of a more general question posed by Ahlswede and Katona in 1977.

fields
Combinatorics, Information Theory
pdf ↗ page arXiv:2610.40486 ↗