AFTD Auto-Formalizing Theoretical Domains

greedy_distinct_diff_seq_one_two_two

theoremverified

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.

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

    lines 2–3

      show greedy_distinct_diff_next [2, 1] = 4
      unfold greedy_distinct_diff_next
  2. 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.

    line 4

    uses le_antisymm

      apply le_antisymm
  3. sInf 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.

    lines 5–6

    uses Nat.sInf_le

      · apply Nat.sInf_le
        simp
  4. 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`).

    lines 7–10

    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

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