min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_four
For $n = 4$, every subset $F \subseteq (\mathrm{Fin}\ 4 \to \mathrm{Bool})$ of cardinality $2^{4-4} = 1$ attains average pairwise Hamming distance $(4-4)/2 = 0$ and is a $0$-dimensional subcube is_subcube (4 - 4) F.
Statement
theorem min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_four
(F : Finset (Fin 4 → Bool)) (hF : F.card = 2 ^ (4 - 4)) :
avg_pairwise_hamming_dist F = (4 - 4 : ℝ) / 2 ∧ is_subcube (4 - 4) F- Source
- arXiv:2610.40486 Sec. 3
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- is_subcubeFor an implicit dimension $n$, a dimension $d : \mathbb{N}$, and a finite subset…
Read back from the Lean
For every finite set F of Boolean functions on 4 coordinates (F : Finset (Fin 4 → Bool)) whose cardinality is 2^(4 - 4) (which equals 1): 1. The average pairwise Hamming distance of F equals (4 - 4 : ℝ) / 2 (which equals 0). 2. F is a (4 - 4)-dimensional subcube (i.e., a 0-dimensional subcube).
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
Since F has cardinality 2^(4 - 4) = 1, it must be a singleton {c}. The average pairwise Hamming distance of a singleton is 0 because the only pair is (c, c), whose Hamming distance is zero. Furthermore, {c} is a 0-dimensional subcube obtained by fixing all coordinates (the full set Finset.univ) to agree with c.
F is a singleton {c} for some boolean vector c : Fin 4 → Bool.
The hypothesis hF states that |F| = 2^(4 - 4) = 1. By Finset.card_eq_one.mp, any finite set of cardinality 1 is a singleton {c}. We substitute F = {c} throughout the goal.
uses
Finset.card_eq_one.mpobtain ⟨c, hFc⟩ := Finset.card_eq_one.mp (by norm_num at hF; exact hF) subst hFc
The average pairwise Hamming distance of {c} is (4 - 4) / 2 = 0.
We split the goal into the two conjuncts. Unfolding the definition of avg_pairwise_hamming_dist on {c} yields the sum of Hamming distances over all pairs in {c} divided by |{c}|². The only pair is (c, c), whose Hamming distance is 0 by hammingDist_self. The expression evaluates to 0 / 1 = 0, matching (4 - 4) / 2.
uses
hammingDist_selfconstructor · unfold avg_pairwise_hamming_dist simp [hammingDist_self]
{c} is a 0-dimensional subcube.
By definition, a subset of (Fin 4 → Bool) is a subcube of dimension d if there is a coordinate subset S with |S| + d = 4 and a center point such that the subset consists of all vectors agreeing with the center on S. Here the dimension is 4 - 4 = 0, so we fix all coordinates by taking S = Finset.univ and the center point c. The dimension condition |Finset.univ| + 0 = 4 holds since Fin 4 has 4 elements. Finally, by set extensionality and function extensionality (funext_iff), a vector x equals c if and only if x i = c i for all i ∈ Finset.univ.
uses
funext_iff· refine ⟨Finset.univ, c, ?_, ?_⟩ · simp · ext x simp [funext_iff]
Finset.card_eq_one.mp- A finite set has cardinality 1 if and only if it is a singleton {a} for some element a.
hammingDist_self- The Hamming distance between any element and itself is zero.
funext_iff- Two functions are equal if and only if they agree on all inputs.
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 minimum average Hamming distance conjecture holds for n = 4. -/theorem min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_four (F : Finset (Fin 4 → Bool)) (hF : F.card = 2 ^ (4 - 4)) : avg_pairwise_hamming_dist F = (4 - 4 : ℝ) / 2 ∧ is_subcube (4 - 4) F := by obtain ⟨c, hFc⟩ := Finset.card_eq_one.mp (by norm_num at hF; exact hF) subst hFc constructor · unfold avg_pairwise_hamming_dist simp [hammingDist_self] · refine ⟨Finset.univ, c, ?_, ?_⟩ · simp · ext x simp [funext_iff]