AFTD Auto-Formalizing Theoretical Domains

perm_distinct_abs_diffs_ascent_count_sub_half_unbounded

theoremverifiedformalization

For any permutation (a_n) of the positive integers whose consecutive absolute differences are pairwise distinct, A(X) − X/2 is unbounded above, where A(X) counts the v ≤ X whose successor in the sequence is larger than v.

Statement

theorem perm_distinct_abs_diffs_ascent_count_sub_half_unbounded (a : ℕ → ℕ)
    (hinj : Function.Injective a) (hpos : ∀ n, 0 < a n) (hsurj : ∀ v, 0 < v → ∃ n, a n = v)
    (hd : Function.Injective (fun n => Int.natAbs ((a (n + 1) : ℤ) - a n))) :
    ∀ C : ℝ, ∃ X : ℕ,
      C < (({v | 1 ≤ v ∧ v ≤ X ∧ ∃ n, a n = v ∧ v < a (n + 1)} : Set ℕ).ncard : ℝ) - X / 2
Formalizes
arXiv:2610.15860 (A note on the Slater–Vélez permutation), Lemma 1.
Verified
14 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof proceeds by contradiction, assuming that A(X) - X/2 is bounded above by a constant C. Because consecutive absolute differences are pairwise distinct, the sequence cannot decrease indefinitely, which guarantees infinitely many ascents; we fix a threshold Y containing at least ⌈C⌉ ascents F. Partitioning {1, ..., X} for a large X > Y into the ascents P above Y and the remaining values Q, the bounded ascent hypothesis gives a quadratic lower bound on ∑_{v ∈ P} v, while injectivity of the successor and difference maps gives quadratic lower bounds on the sums of s(v) and dd(v) over Q. Comparing these quadratic lower bounds with the linear upper bound on ∑_{v ∈ Q} (s(v) + dd(v)) forces X ≤ 2 * ∑_{v ∈ F} 2 * dd(v), which contradicts the choice of X = Y + 2E + 1.

  1. Assume for contradiction that A(X) - X/2 is bounded above by some real constant C for all X.

    We argue by contradiction, assuming there exists a real constant C such that for every X, the number of ascents up to X minus X/2 is at most C. We define the ascent predicate asc v (asserting that the successor of v is greater than v) and the finite set Af X of ascents in {1, ..., X}. Converting the set cardinality ncard to the finset cardinality card reformulates the contradiction hypothesis as |Af(X)| - X/2 ≤ C for all X.

    lines 6–20

    uses Set.ncard_coe_finset, and_assoc

      classical
      by_contra hcon
      push_neg at hcon
      obtain ⟨C, hC⟩ := hcon
      set asc : ℕ → Prop := fun v => ∃ n, a n = v ∧ v < a (n + 1) with hasc
      set Af : ℕ → Finset ℕ := fun X => (Icc 1 X).filter asc with hAf
      have hA : ∀ X, ((Af X).card : ℝ) - X / 2 ≤ C := by
        intro X
        have : ({v | 1 ≤ v ∧ v ≤ X ∧ ∃ n, a n = v ∧ v < a (n + 1)} : Set ℕ).ncard = (Af X).card := by
          rw [← Set.ncard_coe_finset]
          congr 1
          ext v
          simp [hAf, hasc, and_assoc]
        rw [← this]
        exact hC X
  2. Define preimages, successors, and consecutive differences, and establish their injectivity.

    Because the permutation a maps onto the positive integers, each positive integer v has an index n with a(n) = v; choice provides an inverse function idx. We then define the successor s(v) = a(idx(v) + 1) and consecutive difference dd(v) = |s(v) - v|. Injectivity of a implies that idx and s are injective on positive integers. Furthermore, the hypothesis that consecutive absolute differences are pairwise distinct implies that dd is injective on positive integers.

    lines 21–40

    uses Nat.succ_injective

      -- index, successor and difference of a value
      have hidx : ∀ v, ∃ n, 0 < v → a n = v := by
        intro v
        by_cases hv : 0 < v
        · obtain ⟨n, hn⟩ := hsurj v hv
          exact ⟨n, fun _ => hn⟩
        · exact ⟨0, fun h => absurd h hv⟩
      choose idx hidx using hidx
      set s : ℕ → ℕ := fun v => a (idx v + 1) with hs
      set dd : ℕ → ℕ := fun v => Int.natAbs ((a (idx v + 1) : ℤ) - a (idx v)) with hdd
      have hs_pos : ∀ v, 0 < s v := fun v => hpos _
      have hidx_inj : ∀ v w, 0 < v → 0 < w → idx v = idx w → v = w := by
        intro v w hv hw h
        rw [← hidx v hv, ← hidx w hw, h]
      have hs_inj : ∀ v w, 0 < v → 0 < w → s v = s w → v = w := by
        intro v w hv hw h
        exact hidx_inj v w hv hw (Nat.succ_injective (hinj h))
      have hdd_inj : ∀ v w, 0 < v → 0 < w → dd v = dd w → v = w := by
        intro v w hv hw h
        exact hidx_inj v w hv hw (hd h)
  3. Characterise ascents and express s(v) + dd(v) for ascents and descents.

    For any v > 0, v is an ascent if and only if v < s(v). Injectivity of a ensures s(v) ≠ v, so dd(v) is strictly positive. If v is a descent (not an ascent), then s(v) < v, so dd(v) = v - s(v) and s(v) + dd(v) = v. If v is an ascent, then s(v) > v, so dd(v) = s(v) - v and s(v) + dd(v) = v + 2 * dd(v).

    lines 41–74

    uses Nat.succ_ne_self, Int.natAbs_pos

      have hasc_iff : ∀ v, 0 < v → (asc v ↔ v < s v) := by
        intro v hv
        constructor
        · rintro ⟨n, hn, hlt⟩
          have : n = idx v := hinj (hn.trans (hidx v hv).symm)
          subst this
          exact hlt
        · intro h
          exact ⟨idx v, hidx v hv, h⟩
      have hs_ne : ∀ v, 0 < v → s v ≠ v := by
        intro v hv h
        have : a (idx v + 1) = a (idx v) := by rw [hidx v hv]; exact h
        exact absurd (hinj this) (Nat.succ_ne_self _)
      have hdd_pos : ∀ v, 0 < v → 0 < dd v := by
        intro v hv
        have := hs_ne v hv
        simp only [hs] at this
        simp only [hdd, Int.natAbs_pos]
        rw [hidx v hv]
        omega
      have hdesc : ∀ v, 0 < v → ¬ asc v → s v + dd v = v := by
        intro v hv hn
        rw [hasc_iff v hv] at hn
        have h1 : a (idx v) = v := hidx v hv
        simp only [hs, hdd] at hn ⊢
        rw [h1]
        omega
      have hascd : ∀ v, 0 < v → asc v → s v + dd v = v + 2 * dd v := by
        intro v hv ha
        rw [hasc_iff v hv] at ha
        have h1 : a (idx v) = v := hidx v hv
        simp only [hs, hdd] at ha ⊢
        rw [h1]
        omega
  4. There are infinitely many ascents in the sequence.

    If there were no ascents above some bound M, then past the index N = ∑_{v=1}^M (idx(v) + 1) all values a(n) would strictly exceed M. Without ascents, the sequence a(n) would strictly decrease for all n ≥ N: a(n + 1) < a(n). By induction, a(N + j) + j ≤ a(N) for all j, which produces a contradiction in the natural numbers when j = a(N) + 1.

    lines 75–107

    uses mem_Icc, single_le_sum, Nat.zero_le, Nat.succ_ne_self, Nat.le_add_right

      -- infinitely many ascents
      have hinf : ∀ M, ∃ v, M < v ∧ asc v := by
        intro M
        by_contra hno
        push_neg at hno
        -- after the indices of the values ≤ M, the sequence only descends
        set N := ∑ v ∈ Icc 1 M, (idx v + 1) with hN
        have hbig : ∀ n, N ≤ n → M < a n := by
          intro n hn
          by_contra hle
          push_neg at hle
          have hv : a n ∈ Icc 1 M := mem_Icc.2 ⟨hpos n, hle⟩
          have : idx (a n) = n := hinj (hidx (a n) (hpos n))
          have h2 : idx (a n) + 1 ≤ N := single_le_sum (f := fun v => idx v + 1)
            (fun _ _ => Nat.zero_le _) hv
          omega
        have hdec : ∀ n, N ≤ n → a (n + 1) < a n := by
          intro n hn
          have h1 := hno (a n) (hbig n hn)
          have h2 : ¬ a n < a (n + 1) := fun h => h1 ⟨n, rfl, h⟩
          have h3 : a (n + 1) ≠ a n := fun h => absurd (hinj h) (Nat.succ_ne_self n)
          omega
        have hdesc' : ∀ j, a (N + j) + j ≤ a N := by
          intro j
          induction j with
          | zero => simp
          | succ j ih =>
            have := hdec (N + j) (Nat.le_add_right _ _)
            have e : N + (j + 1) = N + j + 1 := by omega
            rw [e]
            omega
        have := hdesc' (a N + 1)
        omega
  5. The number of ascents |Af(Y)| grows arbitrarily large as Y increases.

    We prove by induction on m that there exists Y with |Af(Y)| ≥ m. For the inductive step, given Y with at least m ascents, the existence of an ascent v > Y allows us to insert v into Af(Y); since v ∉ Af(Y) and insert v (Af Y) ⊆ Af v, the cardinality of Af(v) is at least m + 1.

    lines 108–128

    uses Nat.zero_le, mem_insert, mem_filter, mem_Icc, le_rfl, card_le_card, card_insert_of_notMem

      have hgrow : ∀ m, ∃ Y, m ≤ (Af Y).card := by
        intro m
        induction m with
        | zero => exact ⟨0, Nat.zero_le _⟩
        | succ m ih =>
          obtain ⟨Y, hY⟩ := ih
          obtain ⟨v, hv, hav⟩ := hinf Y
          refine ⟨v, ?_⟩
          have hsub : insert v (Af Y) ⊆ Af v := by
            intro w hw
            rcases mem_insert.1 hw with rfl | hw
            · simp only [hAf, mem_filter, mem_Icc]
              exact ⟨⟨by omega, le_rfl⟩, hav⟩
            · simp only [hAf, mem_filter, mem_Icc] at hw ⊢
              exact ⟨⟨hw.1.1, by omega⟩, hw.2⟩
          have hvn : v ∉ Af Y := by
            simp only [hAf, mem_filter, mem_Icc]
            omega
          have := card_le_card hsub
          rw [card_insert_of_notMem hvn] at this
          omega
  6. Fix a threshold Y with at least ⌈C⌉ ascents and partition {1, ..., X}.

    We choose C₀ = ⌈C⌉₊ and find Y such that the set of ascents F = Af(Y) satisfies |F| ≥ C₀. We set the constant E = 2 * ∑_{v ∈ F} dd(v) and choose X = Y + 2E + 1. We partition {1, ..., X} into the ascents strictly above Y, denoted P = {v ∈ {Y + 1, ..., X} | asc(v)}, and the complement Q = {1, ..., X} \ P.

    lines 129–135

      set C₀ := ⌈C⌉₊ with hC₀
      obtain ⟨Y, hY⟩ := hgrow C₀
      set F := Af Y with hF
      set E := 2 * ∑ v ∈ F, dd v with hE
      set X := Y + 2 * E + 1 with hX
      set P := (Icc (Y + 1) X).filter asc with hP
      set Q := Icc 1 X \ P with hQ
  7. Establish size and sum identities for the partition of {1, ..., X} into P and Q.

    Because P ⊆ {1, ..., X} and Q is its set difference, their sizes satisfy |P| + |Q| = X, and the sum of their elements equals the sum of the first X positive integers. By induction on X, this sum satisfies the Gauss identity 2 * ∑_{v=1}^X v = X * (X + 1).

    lines 136–155

    uses card_sdiff_of_subset, card_le_card, Nat.card_Icc, add_comm, sum_sdiff, sum_Icc_succ_top, mul_add

      have hPsub : P ⊆ Icc 1 X := by
        intro v hv
        simp only [hP, mem_filter, mem_Icc] at hv
        exact mem_Icc.2 ⟨by omega, hv.1.2⟩
      have hpq : P.card + Q.card = X := by
        rw [hQ, card_sdiff_of_subset hPsub]
        have := card_le_card hPsub
        simp only [Nat.card_Icc] at this ⊢
        omega
      have hsum : ∑ v ∈ P, v + ∑ v ∈ Q, v = ∑ v ∈ Icc 1 X, v := by
        rw [hQ, add_comm]
        exact sum_sdiff hPsub
      have hgauss : ∀ X : ℕ, 2 * ∑ v ∈ Icc 1 X, v = X * (X + 1) := by
        intro X
        induction X with
        | zero => simp
        | succ X ih =>
          rw [sum_Icc_succ_top (by omega), mul_add, ih]
          ring
      -- the ascents above `Y`
  8. Establish the quadratic lower bound 2 * |P| * (|P| + 1) ≤ 2 * ∑_{v ∈ P} v on the ascents above Y.

    For each v ∈ P, the ascents up to v split disjointly as F ∪ {w ∈ P | w ≤ v}, so |Af(v)| = |F| + |{w ∈ P | w ≤ v}|. The upper bound |Af(v)| - v/2 ≤ C combined with C ≤ |F| yields 2 * |{w ∈ P | w ≤ v}| ≤ v. Applying the lemma finset_nat_mul_card_mul_succ_le_two_mul_sum with factor c = 2 turns this ranking condition into the bound 2 * |P| * (|P| + 1) ≤ 2 * ∑_{v ∈ P} v.

    lines 156–185

    uses disjoint_left, card_union_of_disjoint, Nat.le_ceil, finset_nat_mul_card_mul_succ_le_two_mul_sum

      have hP_rank : ∀ v ∈ P, 2 * (P.filter (· ≤ v)).card ≤ v := by
        intro v hv
        have hv' := hv
        simp only [hP, mem_filter, mem_Icc] at hv'
        have hsplit : Af v = F ∪ P.filter (· ≤ v) := by
          ext w
          simp only [hAf, hF, hP, mem_union, mem_filter, mem_Icc]
          constructor
          · rintro ⟨⟨h1, h2⟩, h3⟩
            by_cases hw : w ≤ Y
            · exact Or.inl ⟨⟨h1, hw⟩, h3⟩
            · exact Or.inr ⟨⟨⟨by omega, by omega⟩, h3⟩, h2⟩
          · rintro (⟨⟨h1, h2⟩, h3⟩ | ⟨⟨⟨h1, _⟩, h3⟩, h4⟩)
            · exact ⟨⟨h1, by omega⟩, h3⟩
            · exact ⟨⟨by omega, h4⟩, h3⟩
        have hdisj : Disjoint F (P.filter (· ≤ v)) := by
          rw [disjoint_left]
          intro w hw1 hw2
          simp only [hAf, hF, hP, mem_filter, mem_Icc] at hw1 hw2
          omega
        have hcardv : (Af v).card = F.card + (P.filter (· ≤ v)).card := by
          rw [hsplit, card_union_of_disjoint hdisj]
        have h1 := hA v
        rw [hcardv] at h1
        have h2 : C ≤ (C₀ : ℝ) := Nat.le_ceil C
        have h3 : ((C₀ : ℕ) : ℝ) ≤ (F.card : ℝ) := by exact_mod_cast hY
        push_cast at h1
        have : (2 * (P.filter (· ≤ v)).card : ℝ) ≤ v := by linarith
        exact_mod_cast this
      have hP_sum := finset_nat_mul_card_mul_succ_le_two_mul_sum 2 P hP_rank
  9. Establish quadratic lower bounds on the sums of s(v) and dd(v) over Q.

    Every v ∈ Q is strictly positive. Since s is injective on positive integers, its image s(Q) has cardinality |Q| and consists of positive integers; the lemma finset_nat_card_mul_succ_le_two_mul_sum_of_pos implies |Q| * (|Q| + 1) ≤ 2 * ∑_{v ∈ Q} s(v). By the exact same argument, since dd is injective and strictly positive on positive integers, |Q| * (|Q| + 1) ≤ 2 * ∑_{v ∈ Q} dd(v).

    lines 186–204

    uses finset_nat_card_mul_succ_le_two_mul_sum_of_pos, card_image_of_injOn, sum_image

      -- the rest
      have hQpos : ∀ v ∈ Q, 0 < v := by
        intro v hv
        simp only [hQ, mem_sdiff, mem_Icc] at hv
        omega
      have hQ_s : Q.card * (Q.card + 1) ≤ 2 * ∑ v ∈ Q, s v := by
        have hinjQ : Set.InjOn s Q := fun v hv w hw h => hs_inj v w (hQpos v hv) (hQpos w hw) h
        have := finset_nat_card_mul_succ_le_two_mul_sum_of_pos (Q.image s) (by
          intro w hw
          obtain ⟨v, _, rfl⟩ := mem_image.1 hw
          exact hs_pos v)
        rwa [card_image_of_injOn hinjQ, sum_image hinjQ] at this
      have hQ_d : Q.card * (Q.card + 1) ≤ 2 * ∑ v ∈ Q, dd v := by
        have hinjQ : Set.InjOn dd Q := fun v hv w hw h => hdd_inj v w (hQpos v hv) (hQpos w hw) h
        have := finset_nat_card_mul_succ_le_two_mul_sum_of_pos (Q.image dd) (by
          intro w hw
          obtain ⟨v, hv, rfl⟩ := mem_image.1 hw
          exact hdd_pos v (hQpos v hv))
        rwa [card_image_of_injOn hinjQ, sum_image hinjQ] at this
  10. Bound the combined sum ∑_{v ∈ Q} (s(v) + dd(v)) from above by ∑_{v ∈ Q} v + E.

    For any v ∈ Q, either v is not an ascent (so s(v) + dd(v) = v) or v is an ascent, in which case v ≤ Y because all ascents above Y belong to P. Hence v ∈ F, where s(v) + dd(v) = v + 2 * dd(v). Summing over Q, the additional terms occur only for v ∈ Q ∩ F, bounded by 2 * ∑_{v ∈ F} dd(v) = E.

    lines 205–226

    uses if_pos, sum_le_sum, sum_add_distrib, sum_ite_mem, mul_sum, sum_le_sum_of_subset_of_nonneg, inter_subset_right, Nat.zero_le

      have hQ_sd : ∑ v ∈ Q, (s v + dd v) ≤ ∑ v ∈ Q, v + E := by
        have h1 : ∀ v ∈ Q, s v + dd v ≤ v + (if v ∈ F then 2 * dd v else 0) := by
          intro v hv
          by_cases ha : asc v
          · have hvF : v ∈ F := by
              simp only [hQ, hP, mem_sdiff, mem_filter, mem_Icc, not_and] at hv
              simp only [hF, hAf, mem_filter, mem_Icc]
              refine ⟨⟨hv.1.1, ?_⟩, ha⟩
              by_contra hlt
              exact hv.2 ⟨by omega, hv.1.2⟩ ha
            rw [if_pos hvF, hascd v (hQpos v hv) ha]
          · rw [hdesc v (hQpos v hv) ha]
            omega
        calc ∑ v ∈ Q, (s v + dd v) ≤ ∑ v ∈ Q, (v + (if v ∈ F then 2 * dd v else 0)) :=
              sum_le_sum h1
          _ = ∑ v ∈ Q, v + ∑ v ∈ Q, (if v ∈ F then 2 * dd v else 0) := sum_add_distrib
          _ ≤ ∑ v ∈ Q, v + E := by
              gcongr
              rw [sum_ite_mem, hE, mul_sum]
              exact sum_le_sum_of_subset_of_nonneg inter_subset_right (fun _ _ _ => Nat.zero_le _)
      have hG := hgauss X
      rw [sum_add_distrib] at hQ_sd
  11. Derive X ≤ 2E and obtain a contradiction with the choice of X.

    Adding the lower bounds for Q gives 2 * |Q| * (|Q| + 1) ≤ 2 * ∑_{v ∈ Q} v + 2E. Adding the bound 2 * |P| * (|P| + 1) ≤ 2 * ∑_{v ∈ P} v yields 2 * |P| * (|P| + 1) + 2 * |Q| * (|Q| + 1) ≤ X * (X + 1) + 2E. Because |P| + |Q| = X, the left-hand side expands to X * (X + 1) + X + (|P| - |Q|)², which is at least X * (X + 1) + X. Non-linear arithmetic (nlinarith) deduces X ≤ 2E from this inequality. Finally, linear arithmetic (omega) closes the goal by showing X ≤ 2E contradicts the definition X = Y + 2E + 1.

    lines 227–241

    uses Nat.cast_le, sq_nonneg

      have key : X ≤ 2 * E := by
        have e1 : (P.card : ℤ) + Q.card = X := by exact_mod_cast hpq
        have e2 : (2 : ℤ) * (∑ v ∈ P, v + ∑ v ∈ Q, v : ℕ) = X * (X + 1) := by
          rw [hsum]; exact_mod_cast hG
        have e3 : (((2 * (P.card * (P.card + 1)) : ℕ) : ℤ)) ≤ ((2 * ∑ v ∈ P, v : ℕ) : ℤ) :=
          Nat.cast_le.2 hP_sum
        push_cast at e3
        have e4 : (Q.card : ℤ) * (Q.card + 1) ≤ 2 * ∑ v ∈ Q, (s v : ℤ) := by exact_mod_cast hQ_s
        have e5 : (Q.card : ℤ) * (Q.card + 1) ≤ 2 * ∑ v ∈ Q, (dd v : ℤ) := by exact_mod_cast hQ_d
        have e6 : ((∑ v ∈ Q, s v + ∑ v ∈ Q, dd v : ℕ) : ℤ) ≤ ((∑ v ∈ Q, v + E : ℕ) : ℤ) :=
          Nat.cast_le.2 hQ_sd
        push_cast at e6
        push_cast at e2
        nlinarith [sq_nonneg ((P.card : ℤ) - Q.card)]
      omega
add_comm
Addition is commutative: a + b = b + a.
and_assoc
Logical conjunction is associative: (a ∧ b) ∧ c ↔ a ∧ b ∧ c.
card_image_of_injOn
The image of a finite set under an injective function on that set has the same cardinality as the set.
card_insert_of_notMem
Inserting an element not in a finite set increases its cardinality by 1.
card_le_card
If s ⊆ t, then the cardinality of s is at most that of t.
card_sdiff_of_subset
If s ⊆ t, the cardinality of the difference t \ s equals t.card - s.card.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
disjoint_left
Two sets are disjoint if and only if no element of the first belongs to the second.
finset_nat_card_mul_succ_le_two_mul_sum_of_pos
For any finite set of positive natural numbers S, |S|(|S| + 1) ≤ 2 * ∑ v ∈ S, v.
finset_nat_mul_card_mul_succ_le_two_mul_sum
If each element v of a finite set of natural numbers S satisfies c * |{x ∈ S | x ≤ v}| ≤ v, then c * |S|(|S| + 1) ≤ 2 * ∑ v ∈ S, v.
if_pos
An if-then-else evaluates to the then-branch when the condition is true.
Int.natAbs_pos
The absolute value of an integer is strictly positive if and only if the integer is non-zero.
inter_subset_right
The intersection of two sets s₁ ∩ s₂ is a subset of s₂.
le_rfl
Any element in a preorder is less than or equal to itself: a ≤ a.
mem_filter
An element belongs to the filtered set s.filter p if and only if it belongs to s and satisfies p.
mem_Icc
An element belongs to the closed interval Icc a b if and only if a ≤ x and x ≤ b.
mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
mul_add
Multiplication distributes over addition: a * (b + c) = a * b + a * c.
mul_sum
Multiplication distributes over finite summation: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Nat.card_Icc
The number of natural numbers in the closed interval [a, b] is b + 1 - a.
Nat.cast_le
The coercion from natural numbers to integers (or reals) preserves inequalities: (m : ℤ) ≤ (n : ℤ) ↔ m ≤ n.
Nat.le_ceil
A real number a is bounded above by its ceiling as a natural number: a ≤ ↑⌈a⌉₊.
Nat.le_add_right
A natural number n is at most n + k.
Nat.succ_injective
The successor function on natural numbers is injective.
Nat.succ_ne_self
A natural number is never equal to its successor: n + 1 ≠ n.
Nat.zero_le
Zero is less than or equal to every natural number: 0 ≤ n.
Set.ncard_coe_finset
The set cardinality (ncard) of a coerced finite set equals its Finset cardinality.
single_le_sum
A single non-negative term in a finite sum is bounded above by the entire sum.
sq_nonneg
The square of any real or integer number is non-negative: 0 ≤ x².
sum_add_distrib
The sum of (f x + g x) over a finite set equals the sum of f x plus the sum of g x.
sum_Icc_succ_top
The sum over Icc a (b + 1) equals the sum over Icc a b plus the term at b + 1.
sum_image
The sum of a function over the image f(s) equals the sum over s when f is injective on s.
sum_ite_mem
Summing an indicator that evaluates to f i on t and 0 elsewhere over s equals the sum of f over s ∩ t.
sum_le_sum
If f i ≤ g i on all elements of s, then ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
sum_le_sum_of_subset_of_nonneg
If s ⊆ t and f is non-negative on t \ s, then the sum of f over s is at most the sum over t.
sum_sdiff
For s₁ ⊆ s₂, the sum over s₂ \ s₁ plus the sum over s₁ equals the sum over 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 perm_distinct_abs_diffs_ascent_count_sub_half_unbounded (a : ℕ → ℕ)    (hinj : Function.Injective a) (hpos : ∀ n, 0 < a n) (hsurj : ∀ v, 0 < v → ∃ n, a n = v)    (hd : Function.Injective (fun n => Int.natAbs ((a (n + 1) : ℤ) - a n))) :    ∀ C : ℝ, ∃ X : ℕ,      C < (({v | 1 ≤ v ∧ v ≤ X ∧ ∃ n, a n = v ∧ v < a (n + 1)} : Set ℕ).ncard : ℝ) - X / 2 := open Finset in by  classical  by_contra hcon  push_neg at hcon  obtain ⟨C, hC⟩ := hcon  set asc : ℕ → Prop := fun v => ∃ n, a n = v ∧ v < a (n + 1) with hasc  set Af : ℕ → Finset ℕ := fun X => (Icc 1 X).filter asc with hAf  have hA : ∀ X, ((Af X).card : ℝ) - X / 2 ≤ C := by    intro X    have : ({v | 1 ≤ v ∧ v ≤ X ∧ ∃ n, a n = v ∧ v < a (n + 1)} : Set ℕ).ncard = (Af X).card := by      rw [← Set.ncard_coe_finset]      congr 1      ext v      simp [hAf, hasc, and_assoc]    rw [← this]    exact hC X  -- index, successor and difference of a value  have hidx : ∀ v, ∃ n, 0 < v → a n = v := by    intro v    by_cases hv : 0 < v    · obtain ⟨n, hn⟩ := hsurj v hv      exact ⟨n, fun _ => hn⟩    · exact ⟨0, fun h => absurd h hv⟩  choose idx hidx using hidx  set s : ℕ → ℕ := fun v => a (idx v + 1) with hs  set dd : ℕ → ℕ := fun v => Int.natAbs ((a (idx v + 1) : ℤ) - a (idx v)) with hdd  have hs_pos : ∀ v, 0 < s v := fun v => hpos _  have hidx_inj : ∀ v w, 0 < v → 0 < w → idx v = idx w → v = w := by    intro v w hv hw h    rw [← hidx v hv, ← hidx w hw, h]  have hs_inj : ∀ v w, 0 < v → 0 < w → s v = s w → v = w := by    intro v w hv hw h    exact hidx_inj v w hv hw (Nat.succ_injective (hinj h))  have hdd_inj : ∀ v w, 0 < v → 0 < w → dd v = dd w → v = w := by    intro v w hv hw h    exact hidx_inj v w hv hw (hd h)  have hasc_iff : ∀ v, 0 < v → (asc v ↔ v < s v) := by    intro v hv    constructor    · rintro ⟨n, hn, hlt⟩      have : n = idx v := hinj (hn.trans (hidx v hv).symm)      subst this      exact hlt    · intro h      exact ⟨idx v, hidx v hv, h⟩  have hs_ne : ∀ v, 0 < v → s v ≠ v := by    intro v hv h    have : a (idx v + 1) = a (idx v) := by rw [hidx v hv]; exact h    exact absurd (hinj this) (Nat.succ_ne_self _)  have hdd_pos : ∀ v, 0 < v → 0 < dd v := by    intro v hv    have := hs_ne v hv    simp only [hs] at this    simp only [hdd, Int.natAbs_pos]    rw [hidx v hv]    omega  have hdesc : ∀ v, 0 < v → ¬ asc v → s v + dd v = v := by    intro v hv hn    rw [hasc_iff v hv] at hn    have h1 : a (idx v) = v := hidx v hv    simp only [hs, hdd] at hn ⊢    rw [h1]    omega  have hascd : ∀ v, 0 < v → asc v → s v + dd v = v + 2 * dd v := by    intro v hv ha    rw [hasc_iff v hv] at ha    have h1 : a (idx v) = v := hidx v hv    simp only [hs, hdd] at ha ⊢    rw [h1]    omega  -- infinitely many ascents  have hinf : ∀ M, ∃ v, M < v ∧ asc v := by    intro M    by_contra hno    push_neg at hno    -- after the indices of the values ≤ M, the sequence only descends    set N := ∑ v ∈ Icc 1 M, (idx v + 1) with hN    have hbig : ∀ n, N ≤ n → M < a n := by      intro n hn      by_contra hle      push_neg at hle      have hv : a n ∈ Icc 1 M := mem_Icc.2 ⟨hpos n, hle⟩      have : idx (a n) = n := hinj (hidx (a n) (hpos n))      have h2 : idx (a n) + 1 ≤ N := single_le_sum (f := fun v => idx v + 1)        (fun _ _ => Nat.zero_le _) hv      omega    have hdec : ∀ n, N ≤ n → a (n + 1) < a n := by      intro n hn      have h1 := hno (a n) (hbig n hn)      have h2 : ¬ a n < a (n + 1) := fun h => h1 ⟨n, rfl, h⟩      have h3 : a (n + 1) ≠ a n := fun h => absurd (hinj h) (Nat.succ_ne_self n)      omega    have hdesc' : ∀ j, a (N + j) + j ≤ a N := by      intro j      induction j with      | zero => simp      | succ j ih =>        have := hdec (N + j) (Nat.le_add_right _ _)        have e : N + (j + 1) = N + j + 1 := by omega        rw [e]        omega    have := hdesc' (a N + 1)    omega  have hgrow : ∀ m, ∃ Y, m ≤ (Af Y).card := by    intro m    induction m with    | zero => exact ⟨0, Nat.zero_le _⟩    | succ m ih =>      obtain ⟨Y, hY⟩ := ih      obtain ⟨v, hv, hav⟩ := hinf Y      refine ⟨v, ?_⟩      have hsub : insert v (Af Y) ⊆ Af v := by        intro w hw        rcases mem_insert.1 hw with rfl | hw        · simp only [hAf, mem_filter, mem_Icc]          exact ⟨⟨by omega, le_rfl⟩, hav⟩        · simp only [hAf, mem_filter, mem_Icc] at hw ⊢          exact ⟨⟨hw.1.1, by omega⟩, hw.2⟩      have hvn : v ∉ Af Y := by        simp only [hAf, mem_filter, mem_Icc]        omega      have := card_le_card hsub      rw [card_insert_of_notMem hvn] at this      omega  set C₀ := ⌈C⌉₊ with hC₀  obtain ⟨Y, hY⟩ := hgrow C₀  set F := Af Y with hF  set E := 2 * ∑ v ∈ F, dd v with hE  set X := Y + 2 * E + 1 with hX  set P := (Icc (Y + 1) X).filter asc with hP  set Q := Icc 1 X \ P with hQ  have hPsub : P ⊆ Icc 1 X := by    intro v hv    simp only [hP, mem_filter, mem_Icc] at hv    exact mem_Icc.2 ⟨by omega, hv.1.2⟩  have hpq : P.card + Q.card = X := by    rw [hQ, card_sdiff_of_subset hPsub]    have := card_le_card hPsub    simp only [Nat.card_Icc] at this ⊢    omega  have hsum : ∑ v ∈ P, v + ∑ v ∈ Q, v = ∑ v ∈ Icc 1 X, v := by    rw [hQ, add_comm]    exact sum_sdiff hPsub  have hgauss : ∀ X : ℕ, 2 * ∑ v ∈ Icc 1 X, v = X * (X + 1) := by    intro X    induction X with    | zero => simp    | succ X ih =>      rw [sum_Icc_succ_top (by omega), mul_add, ih]      ring  -- the ascents above `Y`  have hP_rank : ∀ v ∈ P, 2 * (P.filter (· ≤ v)).card ≤ v := by    intro v hv    have hv' := hv    simp only [hP, mem_filter, mem_Icc] at hv'    have hsplit : Af v = F ∪ P.filter (· ≤ v) := by      ext w      simp only [hAf, hF, hP, mem_union, mem_filter, mem_Icc]      constructor      · rintro ⟨⟨h1, h2⟩, h3⟩        by_cases hw : w ≤ Y        · exact Or.inl ⟨⟨h1, hw⟩, h3⟩        · exact Or.inr ⟨⟨⟨by omega, by omega⟩, h3⟩, h2⟩      · rintro (⟨⟨h1, h2⟩, h3⟩ | ⟨⟨⟨h1, _⟩, h3⟩, h4⟩)        · exact ⟨⟨h1, by omega⟩, h3⟩        · exact ⟨⟨by omega, h4⟩, h3⟩    have hdisj : Disjoint F (P.filter (· ≤ v)) := by      rw [disjoint_left]      intro w hw1 hw2      simp only [hAf, hF, hP, mem_filter, mem_Icc] at hw1 hw2      omega    have hcardv : (Af v).card = F.card + (P.filter (· ≤ v)).card := by      rw [hsplit, card_union_of_disjoint hdisj]    have h1 := hA v    rw [hcardv] at h1    have h2 : C ≤ (C₀ : ℝ) := Nat.le_ceil C    have h3 : ((C₀ : ℕ) : ℝ) ≤ (F.card : ℝ) := by exact_mod_cast hY    push_cast at h1    have : (2 * (P.filter (· ≤ v)).card : ℝ) ≤ v := by linarith    exact_mod_cast this  have hP_sum := finset_nat_mul_card_mul_succ_le_two_mul_sum 2 P hP_rank  -- the rest  have hQpos : ∀ v ∈ Q, 0 < v := by    intro v hv    simp only [hQ, mem_sdiff, mem_Icc] at hv    omega  have hQ_s : Q.card * (Q.card + 1) ≤ 2 * ∑ v ∈ Q, s v := by    have hinjQ : Set.InjOn s Q := fun v hv w hw h => hs_inj v w (hQpos v hv) (hQpos w hw) h    have := finset_nat_card_mul_succ_le_two_mul_sum_of_pos (Q.image s) (by      intro w hw      obtain ⟨v, _, rfl⟩ := mem_image.1 hw      exact hs_pos v)    rwa [card_image_of_injOn hinjQ, sum_image hinjQ] at this  have hQ_d : Q.card * (Q.card + 1) ≤ 2 * ∑ v ∈ Q, dd v := by    have hinjQ : Set.InjOn dd Q := fun v hv w hw h => hdd_inj v w (hQpos v hv) (hQpos w hw) h    have := finset_nat_card_mul_succ_le_two_mul_sum_of_pos (Q.image dd) (by      intro w hw      obtain ⟨v, hv, rfl⟩ := mem_image.1 hw      exact hdd_pos v (hQpos v hv))    rwa [card_image_of_injOn hinjQ, sum_image hinjQ] at this  have hQ_sd : ∑ v ∈ Q, (s v + dd v) ≤ ∑ v ∈ Q, v + E := by    have h1 : ∀ v ∈ Q, s v + dd v ≤ v + (if v ∈ F then 2 * dd v else 0) := by      intro v hv      by_cases ha : asc v      · have hvF : v ∈ F := by          simp only [hQ, hP, mem_sdiff, mem_filter, mem_Icc, not_and] at hv          simp only [hF, hAf, mem_filter, mem_Icc]          refine ⟨⟨hv.1.1, ?_⟩, ha⟩          by_contra hlt          exact hv.2 ⟨by omega, hv.1.2⟩ ha        rw [if_pos hvF, hascd v (hQpos v hv) ha]      · rw [hdesc v (hQpos v hv) ha]        omega    calc ∑ v ∈ Q, (s v + dd v) ≤ ∑ v ∈ Q, (v + (if v ∈ F then 2 * dd v else 0)) :=          sum_le_sum h1      _ = ∑ v ∈ Q, v + ∑ v ∈ Q, (if v ∈ F then 2 * dd v else 0) := sum_add_distrib      _ ≤ ∑ v ∈ Q, v + E := by          gcongr          rw [sum_ite_mem, hE, mul_sum]          exact sum_le_sum_of_subset_of_nonneg inter_subset_right (fun _ _ _ => Nat.zero_le _)  have hG := hgauss X  rw [sum_add_distrib] at hQ_sd  have key : X ≤ 2 * E := by    have e1 : (P.card : ℤ) + Q.card = X := by exact_mod_cast hpq    have e2 : (2 : ℤ) * (∑ v ∈ P, v + ∑ v ∈ Q, v : ℕ) = X * (X + 1) := by      rw [hsum]; exact_mod_cast hG    have e3 : (((2 * (P.card * (P.card + 1)) : ℕ) : ℤ)) ≤ ((2 * ∑ v ∈ P, v : ℕ) : ℤ) :=      Nat.cast_le.2 hP_sum    push_cast at e3    have e4 : (Q.card : ℤ) * (Q.card + 1) ≤ 2 * ∑ v ∈ Q, (s v : ℤ) := by exact_mod_cast hQ_s    have e5 : (Q.card : ℤ) * (Q.card + 1) ≤ 2 * ∑ v ∈ Q, (dd v : ℤ) := by exact_mod_cast hQ_d    have e6 : ((∑ v ∈ Q, s v + ∑ v ∈ Q, dd v : ℕ) : ℤ) ≤ ((∑ v ∈ Q, v + E : ℕ) : ℤ) :=      Nat.cast_le.2 hQ_sd    push_cast at e6    push_cast at e2    nlinarith [sq_nonneg ((P.card : ℤ) - Q.card)]  omega
See it in the graphDiscuss this resultChallenge it