fin_forward_pairs_card
For d at most g, the number of ordered pairs of elements of Fin g whose first value is the second value plus d is g-d.
Statement
theorem fin_forward_pairs_card (g d : ℕ) (hd : d ≤ g) : (((univ : Finset (Fin g)).product univ).filter (fun p : Fin g × Fin g => p.2.val+d = p.1.val)).card = g-d
- Source
- Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- biclique_exact_forward_pairs_sumIf bicliques own every forward pair at distance d exactly once on Fin g, the sum of their numbers of such pairs is g-d.
The proof, explained
The proof shows that the set S of pairs (p₁, p₂) ∈ Fin g × Fin g satisfying p₂ + d = p₁ has cardinality g - d by constructing an explicit bijection between Fin (g - d) and S. Each a ∈ Fin (g - d) is sent to the pair (a + d, a), which is valid since a + d < g. The map is injective by projecting to the second coordinate, and surjective because for any pair p ∈ S, the relation p₂ + d = p₁ < g ensures p₂ < g - d, so p₂ serves as the preimage.
Let S denote the set of pairs in Fin g × Fin g satisfying p₂ + d = p₁.
We enable classical logic and define S as an abbreviation for the finset of pairs p ∈ Fin g × Fin g filtered by the condition that p.2.val + d = p.1.val.
classical let S := ((univ : Finset (Fin g)).product univ).filter (fun p : Fin g × Fin g => p.2.val+d = p.1.val)
The cardinality of Fin (g - d) equals the cardinality of S, provided the map a ↦ (a + d, a) is a bijection.
We apply card_bij with the mapping sending each a ∈ Fin (g - d) to the pair (a + d, a). Linear arithmetic (omega) verifies that a + d < g (since a < g - d) and a < g (since d ≤ g), ensuring the components are valid elements of Fin g.
uses
card_bijhave he : (univ : Finset (Fin (g-d))).card = S.card := by apply card_bij (fun a ha => (⟨a.val+d, by omega⟩, ⟨a.val, by omega⟩))
The map sends every element of Fin (g - d) into S.
For any a ∈ Fin (g - d), its image pair (a + d, a) satisfies the defining condition of S, because the second component plus d is a + d, which equals the first component. Unfolding S and simplifying closes the goal.
· intro a ha simp [S]
The map is injective.
Assume two elements a, b ∈ Fin (g - d) have identical image pairs (a + d, a) = (b + d, b). Applying congrArg with the projection to the second component gives a.val = b.val, from which a = b follows by Fin.ext.
uses
Fin.ext,congrArg· intro a ha b hb heq apply Fin.ext exact congrArg (fun p : Fin g × Fin g => p.2.val) heq
The map is surjective onto S.
Given any pair p ∈ S, its components satisfy p.2.val + d = p.1.val. Since p.1.val < g, linear arithmetic shows p.2.val < g - d, so p.2 defines an element a ∈ Fin (g - d). The image of a is (p.2.val + d, p.2.val), which equals (p.1, p.2) = p componentwise.
uses
mem_univ,Prod.ext,Fin.ext· intro p hp have hp' : p.2.val+d = p.1.val := (mem_filter.mp hp).2 have hpg : p.1.val < g := p.1.isLt have hpi : p.2.val < g-d := by omega refine ⟨⟨p.2.val, hpi⟩, mem_univ _, ?_⟩ apply Prod.ext <;> apply Fin.ext <;> dsimp <;> omega
The cardinality of S is g - d.
From the bijection we have |S| = |Fin (g - d)|. Rewriting the cardinality of Fin (g - d) to g - d and unfolding S completes the proof.
uses
card_univ,Fintype.card_finsimpa only [card_univ, Fintype.card_fin, S] using he.symm
card_bij- Two finsets have the same cardinality if there is a map between them that lands in the target, is injective, and is surjective.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
congrArg- Equality is preserved under function application: if x = y, then f x = f y.
mem_univ- Every element of a finite type belongs to its universal finset univ.
Prod.ext- Two pairs are equal if their first components are equal and their second components are equal.
card_univ- The cardinality of the universal finset of a type is the cardinality of the type.
Fintype.card_fin- The cardinality of Fin n is n.
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.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem fin_forward_pairs_card (g d : ℕ) (hd : d ≤ g) : (((univ : Finset (Fin g)).product univ).filter (fun p : Fin g × Fin g => p.2.val+d = p.1.val)).card = g-d := by classical let S := ((univ : Finset (Fin g)).product univ).filter (fun p : Fin g × Fin g => p.2.val+d = p.1.val) have he : (univ : Finset (Fin (g-d))).card = S.card := by apply card_bij (fun a ha => (⟨a.val+d, by omega⟩, ⟨a.val, by omega⟩)) · intro a ha simp [S] · intro a ha b hb heq apply Fin.ext exact congrArg (fun p : Fin g × Fin g => p.2.val) heq · intro p hp have hp' : p.2.val+d = p.1.val := (mem_filter.mp hp).2 have hpg : p.1.val < g := p.1.isLt have hpi : p.2.val < g-d := by omega refine ⟨⟨p.2.val, hpi⟩, mem_univ _, ?_⟩ apply Prod.ext <;> apply Fin.ext <;> dsimp <;> omega simpa only [card_univ, Fintype.card_fin, S] using he.symm