AFTD Auto-Formalizing Theoretical Domains

fin_forward_pairs_card

theoremverified

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

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.

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

    lines 8–10

      classical
      let S := ((univ : Finset (Fin g)).product univ).filter
        (fun p : Fin g × Fin g => p.2.val+d = p.1.val)
  2. 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.

    lines 11–12

    uses card_bij

      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⟩))
  3. 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.

    lines 13–14

        · intro a ha
          simp [S]
  4. 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.

    lines 15–17

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

    lines 18–23

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

    line 24

    uses card_univ, Fintype.card_fin

      simpa 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

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