greedy_distinct_diff_seq_one_two_two
The greedy sequence started at 1, 2 has third term 4 (3 is refused since |3 − 2| = 1 is already a difference).
Statement
theorem greedy_distinct_diff_seq_one_two_two : greedy_distinct_diff_seq 1 2 2 = 4- Source
- Sanity lemma for the definition of the greedy sequence, arXiv:2610.15860 (A note on the Slater–Vélez permutation) (the sequence 1, 2, 4, 7, 3, 8, …).
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- greedy_distinct_diff_seqThe greedy sequence with distinct consecutive differences started at a₁, a₂ (term 0 is a₁, term 1 is a₂; each later term is the least…
- greedy_distinct_diff_nextGiven the terms so far (most recent first), the next greedy term: the least positive integer not used yet whose absolute difference with…
The proof, explained
The greedy sequence started at 1, 2 chooses at step 2 the smallest positive integer not in {1, 2} whose distance from the preceding term 2 is not equal to |2 − 1| = 1. The proof unfolds this definition to an infimum of admissible candidates and shows it equals 4 by antisymmetry. The upper bound holds because 4 belongs to the candidate set, while the lower bound holds because candidates cannot be 1 or 2 (already used) or 3 (giving duplicate difference |3 − 2| = 1), forcing every candidate to be at least 4.
The goal reduces to showing that the infimum of the admissible candidate set after sequence [2, 1] is 4.
By definition, the third term of the greedy sequence (at index 2) is the greedy choice following the history [2, 1]. Unfolding `greedy_distinct_diff_next`, this choice is defined as the infimum of all positive integers c that do not already appear in [2, 1] and whose absolute difference with 2 is not equal to any existing consecutive difference (the only existing difference being |2 − 1| = 1).
show greedy_distinct_diff_next [2, 1] = 4 unfold greedy_distinct_diff_next
It suffices to prove sInf S ≤ 4 and 4 ≤ sInf S.
By the antisymmetry of the partial order on natural numbers (`le_antisymm`), establishing equality reduces to proving the two inequalities.
uses
le_antisymmapply le_antisymmsInf S ≤ 4.
By `Nat.sInf_le`, the infimum of a set of natural numbers is at most any element of the set. Simplification verifies that 4 satisfies all membership conditions: 0 < 4, 4 ∉ [2, 1], and |4 − 2| = 2 ≠ 1.
uses
Nat.sInf_le· apply Nat.sInf_le simp
4 ≤ sInf S.
By `le_csInf`, a lower bound on every element of a nonempty set is a lower bound on its infimum; nonemptiness is witnessed by 4 ∈ S. For any candidate c in the set, simplifying its defining conditions gives c > 0, c ≠ 1, c ≠ 2, and |c − 2| ≠ 1. This rules out 1, 2, and 3, which implies 4 ≤ c by linear integer arithmetic (`omega`).
uses
le_csInf· apply le_csInf ⟨4, by simp⟩ rintro c ⟨hc0, hc1, hc2⟩ simp at hc1 hc2 omega
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- If an element m belongs to a set of natural numbers s, then the infimum of s is at most m.
le_csInf- In a conditionally complete lattice, if a set s is nonempty and a is a lower bound for s, then a ≤ sInf s.
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 greedy_distinct_diff_seq_one_two_two : greedy_distinct_diff_seq 1 2 2 = 4 := by show greedy_distinct_diff_next [2, 1] = 4 unfold greedy_distinct_diff_next apply le_antisymm · apply Nat.sInf_le simp · apply le_csInf ⟨4, by simp⟩ rintro c ⟨hc0, hc1, hc2⟩ simp at hc1 hc2 omega