perm_distinct_abs_diffs_ascent_count_sub_half_unbounded
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
- finset_nat_card_mul_succ_le_two_mul_sum_of_posThe sum of q distinct positive integers is at least q(q+1)/2.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - finset_nat_mul_card_mul_succ_le_two_mul_sumIf S is a finite set of natural numbers in which every v is at least c times its rank (the number of elements of S that are ≤ v), then…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
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.
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.
uses
Set.ncard_coe_finset,and_assocclassical 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
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.
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)
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).
uses
Nat.succ_ne_self,Int.natAbs_poshave 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
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.
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
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.
uses
Nat.zero_le,mem_insert,mem_filter,mem_Icc,le_rfl,card_le_card,card_insert_of_notMemhave 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
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.
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
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).
uses
card_sdiff_of_subset,card_le_card,Nat.card_Icc,add_comm,sum_sdiff,sum_Icc_succ_top,mul_addhave 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`
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.
uses
disjoint_left,card_union_of_disjoint,Nat.le_ceil,finset_nat_mul_card_mul_succ_le_two_mul_sumhave 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
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).
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
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.
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_lehave 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
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.
uses
Nat.cast_le,sq_nonneghave 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₂.
- The key inequality X ≤ 2E in the final step is closed by the automated non-linear arithmetic tactic `nlinarith` supplied with the identity (|P| - |Q|)² ≥ 0, which algebra establishes since 2(|P|² + |Q|²) = (|P| + |Q|)² + (|P| - |Q|)² = X² + (|P| - |Q|)² ≥ X².
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 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