min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_five
For $n = 5$, every subset $F \subseteq (\mathrm{Fin}\ 5 \to \mathrm{Bool})$ of cardinality $2^{5-4} = 2$ has average pairwise Hamming distance at least $(5-4)/2 = 1/2$.
Statement
theorem min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_five
(F : Finset (Fin 5 → Bool)) (hF : F.card = 2 ^ (5 - 4)) :
(5 - 4 : ℝ) / 2 ≤ avg_pairwise_hamming_dist F- Source
- arXiv:2610.40486 Sec. 3
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- avg_pairwise_hamming_distFor an implicit dimension $n$ and a finite subset $F : \mathrm{Finset} (\mathrm{Fin}\ n \to \mathrm{Bool})$, the average pairwise Hamming…
Read back from the Lean
For any finite set $F$ of functions from Fin 5 to Bool (i.e., bitstrings of length 5), if the cardinality of $F$ equals $2^{5 - 4}$ (which is 2), then $(5 - 4 : \mathbb{R}) / 2$ (which is $1/2$) is less than or equal to the average pairwise Hamming distance of $F$ (the sum of the Hamming distances between all pairs of elements in $F$, divided by $|F|^2$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Because $|F| = 2^{5-4} = 2$, the set $F$ consists of exactly two distinct Boolean vectors $a$ and $b$. Expanding the definition of average pairwise Hamming distance over $F = \{a, b\}$ simplifies the double sum to $2 d(a, b) / 4 = d(a, b) / 2$. Since $a \ne b$, their Hamming distance is an integer at least $1$, which immediately implies that the average pairwise Hamming distance is at least $1/2 = (5-4)/2$.
$F = \{a, b\}$ for two distinct elements $a \ne b$, and the goal reduces to showing $1/2 \le \mathrm{avg\_pairwise\_hamming\_dist}\{a, b\}$.
The tactic `norm_num` evaluates the numerical expressions $2^{5-4} = 2$ and $(5-4)/2 = 1/2$. Then, `Finset.card_eq_two.mp` decomposes the two-element set $F$ into $\{a, b\}$ with $a \ne b$.
uses
Finset.card_eq_two.mpnorm_num at hF ⊢ obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.mp hF
The average pairwise Hamming distance of $\{a, b\}$ simplifies to $(d(a, b) + d(a, b)) / 4$.
Unfolding the definition of `avg_pairwise_hamming_dist`, the average distance is the double sum $\sum_{x, y \in \{a, b\}} d(x, y)$ divided by $|F|^2 = 2^2 = 4$. Expanding the sum gives four terms: the self-distances $d(a, a) = d(b, b) = 0$ vanish, and by symmetry of Hamming distance (`hammingDist_comm`), $d(b, a) = d(a, b)$, leaving $(d(a, b) + d(a, b)) / 4$.
uses
hammingDist_communfold avg_pairwise_hamming_dist simp [hab, hammingDist_comm]
The Hamming distance $d(a, b)$ is at least 1 as a real number.
Since $a \ne b$, `hammingDist_pos.mpr` shows that their Hamming distance is strictly positive in $\mathbb{N}$, so $1 \le d(a, b)$. Casting this inequality to $\mathbb{R}$ gives $1 \le d(a, b)$, and symmetry (`hammingDist_comm`) also yields $1 \le d(b, a)$.
uses
hammingDist_pos.mpr,hammingDist_commhave hd_nat : 1 ≤ hammingDist a b := hammingDist_pos.mpr hab have hd : (1 : ℝ) ≤ (hammingDist a b : ℝ) := by exact_mod_cast hd_nat have hd' : (1 : ℝ) ≤ (hammingDist b a : ℝ) := by simpa [hammingDist_comm] using hd
The average pairwise Hamming distance is at least $1/2$. automation
After `norm_num` normalizes the fractions, `linarith` closes the goal using the inequality $1 \le d(a, b)$: $(d(a, b) + d(a, b)) / 4 = 2 d(a, b) / 4 = d(a, b) / 2 \ge 1/2$.
norm_num linarith
Finset.card_eq_two.mp- A finite set has cardinality 2 if and only if it consists of two distinct elements.
hammingDist_comm- Hamming distance is symmetric: $d(x, y) = d(y, x)$.
hammingDist_pos.mpr- Two vectors that are not equal have strictly positive Hamming distance.
- The hypothesis `hd'` on lines 11–12 stating $1 \le d(b, a)$ is redundant, as symmetry has already reduced the expression in line 8 to terms involving only $d(a, b)$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The density 1/16 average Hamming distance lower bound holds for n = 5. -/theorem min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_five (F : Finset (Fin 5 → Bool)) (hF : F.card = 2 ^ (5 - 4)) : (5 - 4 : ℝ) / 2 ≤ avg_pairwise_hamming_dist F := by norm_num at hF ⊢ obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.mp hF unfold avg_pairwise_hamming_dist simp [hab, hammingDist_comm] have hd_nat : 1 ≤ hammingDist a b := hammingDist_pos.mpr hab have hd : (1 : ℝ) ≤ (hammingDist a b : ℝ) := by exact_mod_cast hd_nat have hd' : (1 : ℝ) ≤ (hammingDist b a : ℝ) := by simpa [hammingDist_comm] using hd norm_num linarith