AFTD Auto-Formalizing Theoretical Domains

min_avg_pairwise_hamming_dist_density_one_sixteenth_n_eq_five

theoremverified

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$.

  1. $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$.

    lines 5–6

    uses Finset.card_eq_two.mp

      norm_num at hF ⊢
      obtain ⟨a, b, hab, rfl⟩ := Finset.card_eq_two.mp hF
  2. 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$.

    lines 7–8

    uses hammingDist_comm

      unfold avg_pairwise_hamming_dist
      simp [hab, hammingDist_comm]
  3. 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)$.

    lines 9–12

    uses hammingDist_pos.mpr, 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
  4. 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$.

    lines 13–14

      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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it