forest_symmetric_one_tail
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
- forest_symmetric_fiber_equivAny finite uniform integer law with symmetric value counts admits a permutation that negates every value.
- Used by 1
- forest_greedy_envelope_preserved_by_independent_mergeIndependent symmetric finite uniform discrepancy laws of fixed parity that satisfy the envelope still satisfy it after one greedy step…
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.
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.
uses
forest_symmetric_fiber_equivclassical 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)
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.
uses
Fintype.card_subtype,Fintype.card_congrhave 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
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.
uses
Finset.disjoint_left.mpr,Finset.mem_filter.mphave 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
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 |α|.
uses
Finset.card_union_of_disjoint,Finset.card_le_card,Finset.subset_univ,Finset.card_univhave 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
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.
uses
Fintype.card_poshave 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 (α := α))
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| ≤ |α|.
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
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.
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