card_pairs_with_gap
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).
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.
uses
Finset.mem_Icchave hk_le : k ≤ n := by rw [Finset.mem_Icc] at hk omega
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|.
uses
Finset.card_univ,Fintype.card_finlet 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]
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).
uses
Finset.card_bij',Finset.mem_filter.mprefine 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⟩)
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`.
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)
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`.
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')
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`).
(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.
- In Lean, an element of `Fin n` consists of a natural number bundled with a proof that it is strictly less than `n`. Constructing elements of `Fin n` or `Fin (n - k)` therefore requires verifying inequality bounds, which are handled throughout the proof by the `omega` tactic.
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.
/-- 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)