AFTD Auto-Formalizing Theoretical Domains

card_pairs_with_gap

theoremverified

For integers 1 ≤ k ≤ n - 1, the number of pairs (i, j) in {0, ..., n-1}^2 with j - i = k is n - k.

Statement

theorem card_pairs_with_gap (n : ℕ) (k : ℕ) (hk : k ∈ Finset.Icc 1 (n - 1)) :
    ((Finset.univ ×ˢ Finset.univ : Finset (Fin n × Fin n)).filter
      (fun ⟨i, j⟩ => (i : ℕ) + k = (j : ℕ))).card = n - k
Source
arXiv:2610.38368, Section 2
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any natural numbers $n$ and $k$, if $k$ belongs to the closed interval $[1, n - 1]$ (that is, $1 \le k \le n - 1$), then the number of pairs $(i, j) \in \mathrm{Fin}(n) \times \mathrm{Fin}(n)$ satisfying $i + k = j$ (when $i$ and $j$ are coerced to natural numbers) is equal to $n - k$.

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

The proof counts the pairs (i, j) in {0, ..., n-1}^2 with gap j - i = k by constructing an explicit bijection between this set and {0, ..., n - k - 1}. A valid pair is uniquely determined by its first component i, which determines j as i + k. Since j < n, the first component must satisfy i < n - k, and conversely every i < n - k uniquely yields a valid pair (i, i + k).

  1. k ≤ n

    From the assumption k ∈ [1, n - 1], the interval membership lemma `Finset.mem_Icc` gives 1 ≤ k ≤ n - 1. Linear integer arithmetic (`omega`) then deduces that k ≤ n.

    lines 5–7

    uses Finset.mem_Icc

      have hk_le : k ≤ n := by
        rw [Finset.mem_Icc] at hk
        omega
  2. It suffices to show that |s| = |t|, where s is the set of pairs with difference k and t = Fin (n - k).

    Let s be the finset of pairs (i, j) in Fin n × Fin n satisfying i + k = j, and let t be the universal finset of Fin (n - k). By `Finset.card_univ` and `Fintype.card_fin`, the cardinality of t is n - k. Replacing n - k with |t| reduces the theorem to showing |s| = |t|.

    lines 8–12

    uses Finset.card_univ, Fintype.card_fin

      let s := ((Finset.univ ×ˢ Finset.univ : Finset (Fin n × Fin n)).filter
          (fun ⟨i, j⟩ => (i : ℕ) + k = (j : ℕ)))
      let t : Finset (Fin (n - k)) := Finset.univ
      have ht_card : t.card = n - k := by rw [Finset.card_univ, Fintype.card_fin]
      rw [← ht_card]
  3. The forward map (i, j) ↦ i well-defines a map from s to Fin (n - k).

    We invoke `Finset.card_bij'` to establish |s| = |t| by constructing a bijection. The forward map sends a pair p = (i, j) ∈ s to its first component i. From p ∈ s, `Finset.mem_filter.mp` gives i + k = j. Since j < n, linear arithmetic (`omega`) ensures that i < n - k, so i is a valid element of Fin (n - k).

    lines 13–17

    uses Finset.card_bij', Finset.mem_filter.mp

      refine Finset.card_bij' (s := s) (t := t)
        (fun p hp => ⟨p.1.1, by
          have hp' : (p.1 : ℕ) + k = (p.2 : ℕ) := (Finset.mem_filter.mp hp).2
          have hj : (p.2 : ℕ) < n := p.2.2
          omega⟩)
  4. The candidate inverse map a ↦ (a, a + k) is well-defined and maps t into s, while the forward map lands in t.

    For each a ∈ Fin (n - k), we have a < n - k. Since k ≤ n, linear arithmetic (`omega`) proves both a < n and a + k < n, defining a pair (a, a + k) in Fin n × Fin n. The forward map maps into t trivially by `Finset.mem_univ` because t is the full universe. To show (a, a + k) ∈ s, `Finset.mem_filter` requires the pair to lie in Fin n × Fin n (which holds by `Finset.mem_product.mpr` and `Finset.mem_univ`) and satisfy the gap condition a + k = a + k, which holds definitionally by `rfl`.

    lines 18–23

    uses Finset.mem_univ, Finset.mem_filter, Finset.mem_product.mpr

        (fun a ha => (⟨a.1, by omega⟩, ⟨a.1 + k, by omega⟩))
        (fun a ha => Finset.mem_univ _)
        (fun a ha => by
          rw [Finset.mem_filter]
          refine ⟨Finset.mem_product.mpr ⟨Finset.mem_univ _, Finset.mem_univ _⟩, ?_⟩
          rfl)
  5. The inverse map is a left inverse on s: recovering the pair from its first component yields (i, j).

    Given a pair (i, j) ∈ s, the forward map extracts i, and the inverse map forms (i, i + k). By extensionality (`ext`), the first component is i = i by definition (`rfl`), and the second component is i + k = j, which holds directly from the filter condition extracted by `Finset.mem_filter.mp`.

    lines 24–28

    uses Finset.mem_filter.mp

        (fun ⟨i, j⟩ hp => by
          have hp' : (i : ℕ) + k = (j : ℕ) := (Finset.mem_filter.mp hp).2
          ext
          · rfl
          · exact hp')
  6. The inverse map is a right inverse on t: projecting (a, a + k) to its first component recovers a.

    Given a ∈ Fin (n - k), the inverse map constructs (a, a + k), and the forward map projects to the first component. By extensionality (`ext`), its underlying natural number is a, which matches definitionally (`rfl`).

    lines 29–31

        (fun a ha => by
          ext
          rfl)
Finset.mem_Icc
An element lies in a closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n = {0, ..., n-1} is n.
Finset.card_bij'
Two finsets s and t have the same cardinality if there exist maps between them that are mutually inverse on s and t.
Finset.mem_filter.mp
If an element belongs to a filtered finset {x ∈ s | P(x)}, then it belongs to s and satisfies the predicate P.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.mem_filter
An element belongs to a filtered finset {x ∈ s | P(x)} if and only if it belongs to s and satisfies P.
Finset.mem_product.mpr
A pair (a, b) belongs to the Cartesian product s × t if a ∈ s and b ∈ t.

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 number of pairs in {0, ..., n-1}^2 with difference k is n - k. -/theorem card_pairs_with_gap (n : ℕ) (k : ℕ) (hk : k ∈ Finset.Icc 1 (n - 1)) :    ((Finset.univ ×ˢ Finset.univ : Finset (Fin n × Fin n)).filter      (fun ⟨i, j⟩ => (i : ℕ) + k = (j : ℕ))).card = n - k := by  have hk_le : k ≤ n := by    rw [Finset.mem_Icc] at hk    omega  let s := ((Finset.univ ×ˢ Finset.univ : Finset (Fin n × Fin n)).filter      (fun ⟨i, j⟩ => (i : ℕ) + k = (j : ℕ)))  let t : Finset (Fin (n - k)) := Finset.univ  have ht_card : t.card = n - k := by rw [Finset.card_univ, Fintype.card_fin]  rw [← ht_card]  refine Finset.card_bij' (s := s) (t := t)    (fun p hp => ⟨p.1.1, by      have hp' : (p.1 : ℕ) + k = (p.2 : ℕ) := (Finset.mem_filter.mp hp).2      have hj : (p.2 : ℕ) < n := p.2.2      omega⟩)    (fun a ha => (⟨a.1, by omega⟩, ⟨a.1 + k, by omega⟩))    (fun a ha => Finset.mem_univ _)    (fun a ha => by      rw [Finset.mem_filter]      refine ⟨Finset.mem_product.mpr ⟨Finset.mem_univ _, Finset.mem_univ _⟩, ?_⟩      rfl)    (fun ⟨i, j⟩ hp => by      have hp' : (i : ℕ) + k = (j : ℕ) := (Finset.mem_filter.mp hp).2      ext      · rfl      · exact hp')    (fun a ha => by      ext      rfl)
See it in the graphDiscuss this resultChallenge it