AFTD Auto-Formalizing Theoretical Domains

forest_symmetric_one_tail

theoremverified

For any nonempty finite uniform symmetric integer law, the probability of being at least one is at most one half.

Statement

theorem forest_symmetric_one_tail (α : Type) [Fintype α] [Nonempty α] (X : α → ℤ)
    (hs : ∀ z : ℤ, (Finset.univ.filter (fun a => X a = z)).card =
      (Finset.univ.filter (fun a => X a = -z)).card) :
    (((Finset.univ.filter (fun a => (1 : ℤ) ≤ X a)).card : ℝ) /
      (Fintype.card α : ℝ)) ≤ 1 / 2
Source
Helper for OP-1106, forest greedy carpooling; related background arXiv:2611.00388.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The theorem is proved by a symmetry-based counting argument. By the symmetry hypothesis on the distribution of X, there is a permutation of the domain that negates the value of X. This permutation pairs the positive tail {a | X a ≥ 1} bijectively with the negative tail {a | X a ≤ -1}, showing that both tails have identical cardinality. Since the positive and negative tails are disjoint subsets of the finite universe α, the positive tail can contain at most half the elements of α, giving the desired probability bound of at most 1/2.

  1. Obtain a sign-reversing permutation of α and define the positive and negative tail sets.

    Using the symmetry hypothesis on the fiber sizes of X, the lemma forest_symmetric_fiber_equiv provides a permutation e of α such that X (e a) = -X a for all a. We then define pos as the set of elements where X a ≥ 1 and neg as the set of elements where X a ≤ -1.

    lines 6–9

    uses forest_symmetric_fiber_equiv

      classical
      obtain ⟨e, he⟩ := forest_symmetric_fiber_equiv α X hs
      let pos : Finset α := Finset.univ.filter (fun a => 1 ≤ X a)
      let neg : Finset α := Finset.univ.filter (fun a => X a ≤ -1)
  2. The positive and negative tail sets have equal cardinality.

    The sign-reversing permutation e restricts to a bijection between the subtype {a // 1 ≤ X a} and the subtype {a // X a ≤ -1}, because 1 ≤ X a ↔ X (e a) = -X a ≤ -1. Since equivalent finite subtypes have the same cardinality, pos and neg contain the same number of elements.

    lines 10–15

    uses Fintype.card_subtype, Fintype.card_congr

      have heq : pos.card = neg.card := by
        let ep : {a // 1 ≤ X a} ≃ {a // X a ≤ -1} := e.subtypeEquiv (by
          intro a
          rw [he]
          omega)
        simpa only [Fintype.card_subtype] using Fintype.card_congr ep
  3. The positive and negative tail sets are disjoint.

    If an element a were in both pos and neg, it would satisfy both 1 ≤ X a and X a ≤ -1, which is impossible by integer linear arithmetic.

    lines 16–21

    uses Finset.disjoint_left.mpr, Finset.mem_filter.mp

      have hd : Disjoint pos neg := by
        apply Finset.disjoint_left.mpr
        intro a ha hb
        have h1 : 1 ≤ X a := (Finset.mem_filter.mp ha).2
        have h2 : X a ≤ -1 := (Finset.mem_filter.mp hb).2
        omega
  4. The sum of the sizes of the two tails is at most the total size of α.

    Because pos and neg are disjoint, the sum of their cardinalities equals the size of their union pos ∪ neg. Since this union is a subset of the universe α, its cardinality cannot exceed |α|.

    lines 22–26

    uses Finset.card_union_of_disjoint, Finset.card_le_card, Finset.subset_univ, Finset.card_univ

      have hsum : pos.card + neg.card ≤ Fintype.card α := by
        calc
          _ = (pos ∪ neg).card := (Finset.card_union_of_disjoint hd).symm
          _ ≤ (Finset.univ : Finset α).card := Finset.card_le_card (Finset.subset_univ _)
          _ = _ := Finset.card_univ
  5. Twice the cardinality of the positive tail is at most |α|, and |α| is strictly positive.

    Since |pos| = |neg| and |pos| + |neg| ≤ |α|, we have 2 * |pos| ≤ |α| in the natural numbers, which casts directly to an inequality in the reals. Furthermore, because α is nonempty, its cardinality is strictly positive.

    lines 27–29

    uses Fintype.card_pos

      have htwo : 2 * pos.card ≤ Fintype.card α := by omega
      have hr : (2 : ℝ) * pos.card ≤ Fintype.card α := by exact_mod_cast htwo
      have hp : (0 : ℝ) < Fintype.card α := by exact_mod_cast (Fintype.card_pos (α := α))
  6. The proportion of elements with X a ≥ 1 is at most 1/2.

    The target inequality |pos| / |α| ≤ 1/2 is rewritten by clearing the positive denominator |α|, which yields |pos| ≤ (1/2) * |α|. This follows directly from the earlier inequality 2 * |pos| ≤ |α|.

    lines 30–32

    uses div_le_iff₀

      change (pos.card : ℝ) / (Fintype.card α : ℝ) ≤ 1 / 2
      apply (div_le_iff₀ hp).2
      nlinarith
forest_symmetric_fiber_equiv
For any integer function with symmetric fiber sizes on a finite type α, there exists a permutation e of α such that X (e a) = -X a for all a.
Fintype.card_congr
An equivalence between two finite types implies that they have equal cardinality.
Fintype.card_subtype
The cardinality of a subtype {x // p x} equals the cardinality of the filtered Finset of elements satisfying p.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element belonging to the first set belongs to the second set.
Finset.mem_filter.mp
Membership in a filtered finite set Finset.filter p s implies membership in s and that the predicate p holds.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most that of the superset.
Finset.subset_univ
Every finite set of elements of a finite type is a subset of the universal Finset.
Finset.card_univ
The cardinality of the universal Finset of a finite type α equals the cardinality of α.
Fintype.card_pos
A nonempty finite type has strictly positive cardinality.
div_le_iff₀
For positive c, dividing b by c is at most a if and only if b is at most a * c.

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

theorem forest_symmetric_one_tail (α : Type) [Fintype α] [Nonempty α] (X : α → ℤ)    (hs : ∀ z : ℤ, (Finset.univ.filter (fun a => X a = z)).card =      (Finset.univ.filter (fun a => X a = -z)).card) :    (((Finset.univ.filter (fun a => (1 : ℤ) ≤ X a)).card : ℝ) /      (Fintype.card α : ℝ)) ≤ 1 / 2 := by  classical  obtain ⟨e, he⟩ := forest_symmetric_fiber_equiv α X hs  let pos : Finset α := Finset.univ.filter (fun a => 1 ≤ X a)  let neg : Finset α := Finset.univ.filter (fun a => X a ≤ -1)  have heq : pos.card = neg.card := by    let ep : {a // 1 ≤ X a} ≃ {a // X a ≤ -1} := e.subtypeEquiv (by      intro a      rw [he]      omega)    simpa only [Fintype.card_subtype] using Fintype.card_congr ep  have hd : Disjoint pos neg := by    apply Finset.disjoint_left.mpr    intro a ha hb    have h1 : 1 ≤ X a := (Finset.mem_filter.mp ha).2    have h2 : X a ≤ -1 := (Finset.mem_filter.mp hb).2    omega  have hsum : pos.card + neg.card ≤ Fintype.card α := by    calc      _ = (pos ∪ neg).card := (Finset.card_union_of_disjoint hd).symm      _ ≤ (Finset.univ : Finset α).card := Finset.card_le_card (Finset.subset_univ _)      _ = _ := Finset.card_univ  have htwo : 2 * pos.card ≤ Fintype.card α := by omega  have hr : (2 : ℝ) * pos.card ≤ Fintype.card α := by exact_mod_cast htwo  have hp : (0 : ℝ) < Fintype.card α := by exact_mod_cast (Fintype.card_pos (α := α))  change (pos.card : ℝ) / (Fintype.card α : ℝ) ≤ 1 / 2  apply (div_le_iff₀ hp).2  nlinarith
See it in the graphDiscuss this resultChallenge it