/-
Copyright 2025 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import Mathlib.Algebra.BigOperators.Group.Finset.Basic
public import Mathlib.Algebra.Order.BigOperators.Group.Finset
public import Mathlib.Data.Set.Finite.Lattice
public import Mathlib.Order.Filter.AtTopBot.Basic
public import Mathlib.Order.Filter.AtTopBot.Defs
public import Mathlib.Order.Interval.Finset.Nat
public import Mathlib.Order.Lattice.Nat
public import Mathlib.Order.WellFoundedComplete and subcomplete sets
A complete set has all sufficiently large elements among its finite subset sums. A subcomplete set of natural numbers has an infinite arithmetic progression among those sums.
@[expose] public sectionvariable {M : Type*} [AddCommMonoid M]open scoped List
The set of subset sums of a set A ⊆ M.
def subsetSums (A : Set M) : Set M :=
{n | ∃ B : Finset M, ↑B ⊆ A ∧ n = ∑ i ∈ B, i}
If A ⊆ B, then subsetSums A ⊆ subsetSums B.
@[gcongr]
theorem subsetSums_mono {A B : Set M} (h : A ⊆ B) : subsetSums A ⊆ subsetSums B :=
fun _ ⟨C, hC⟩ => ⟨C, hC.1.trans h, hC.2⟩
The set of subset sums of a sequence ℕ → M, where repetition is allowed.
def subseqSums' (A : ℕ → M) : Set M :=
{n | ∃ B : Finset ℕ, n = ∑ i ∈ B, A i}Zero is a finite subset sum of every set.
@[simp]
theorem zero_mem_subsetSums (A : Set M) : 0 ∈ subsetSums A := M:Type u_1inst✝:AddCommMonoid MA:Set M⊢ 0 ∈ subsetSums A
exact ⟨∅, M:Type u_1inst✝:AddCommMonoid MA:Set M⊢ ↑∅ ⊆ A All goals completed! 🐙, M:Type u_1inst✝:AddCommMonoid MA:Set M⊢ 0 = ∑ i ∈ ∅, i All goals completed! 🐙⟩A set of natural numbers is subcomplete if its finite subset sums contain an infinite arithmetic progression with positive common difference.
def IsSubcomplete (A : Set ℕ) : Prop :=
∃ a d : ℕ, 0 < d ∧ ∀ k : ℕ, a + k * d ∈ subsetSums AA superset of a subcomplete set is subcomplete.
theorem IsSubcomplete.mono {A B : Set ℕ} (hAB : A ⊆ B) (hA : IsSubcomplete A) :
IsSubcomplete B := A:Set ℕB:Set ℕhAB:A ⊆ BhA:IsSubcomplete A⊢ IsSubcomplete B
A:Set ℕB:Set ℕhAB:A ⊆ Ba:ℕd:ℕhd:0 < dhk:∀ (k : ℕ), a + k * d ∈ subsetSums A⊢ IsSubcomplete B
All goals completed! 🐙A finite set is not subcomplete because its finite subset sums are bounded.
A:Set ℕhA:A.Finitea:ℕd:ℕhd:0 < dhk:∀ (k : ℕ), a + k * d ∈ subsetSums Ahbound:∀ s ∈ subsetSums A, s ≤ ∑ n ∈ hA.toFinset, n⊢ False
set S := ∑ n ∈ hA.toFinset, n A:Set ℕhA:A.Finitea:ℕd:ℕhd:0 < dhk:∀ (k : ℕ), a + k * d ∈ subsetSums AS:ℕ := ∑ n ∈ hA.toFinset, nhbound:∀ s ∈ subsetSums A, s ≤ S⊢ False
have h1 := hbound _ (hk (S + 1)) A:Set ℕhA:A.Finitea:ℕd:ℕhd:0 < dhk:∀ (k : ℕ), a + k * d ∈ subsetSums AS:ℕ := ∑ n ∈ hA.toFinset, nhbound:∀ s ∈ subsetSums A, s ≤ Sh1:a + (S + 1) * d ≤ S⊢ False
have h2 : S + 1 ≤ (S + 1) * d := Nat.le_mul_of_pos_right _ hd A:Set ℕhA:A.Finitea:ℕd:ℕhd:0 < dhk:∀ (k : ℕ), a + k * d ∈ subsetSums AS:ℕ := ∑ n ∈ hA.toFinset, nhbound:∀ s ∈ subsetSums A, s ≤ Sh1:a + (S + 1) * d ≤ Sh2:S + 1 ≤ (S + 1) * d⊢ False
omega All goals completed! 🐙The set of all natural numbers is subcomplete.
@[simp]
theorem isSubcomplete_univ : IsSubcomplete Set.univ := by ⊢ IsSubcomplete Set.univ
refine ⟨0, 1, one_pos, fun k ↦ ?_⟩ k:ℕ⊢ 0 + k * 1 ∈ subsetSums Set.univ
exact ⟨{k}, by k:ℕ⊢ ↑{k} ⊆ Set.univ simp All goals completed! 🐙, by k:ℕ⊢ 0 + k * 1 = ∑ i ∈ {k}, i simp All goals completed! 🐙⟩The empty set is not subcomplete.
@[simp]
theorem not_isSubcomplete_empty : ¬ IsSubcomplete ∅ :=
not_isSubcomplete_of_finite Set.finite_emptyvariable [Preorder M]
A set A ⊆ M is complete if every sufficiently large element of M is a subset sum of A.
def IsAddComplete (A : Set M) : Prop :=
∀ᶠ k in Filter.atTop, k ∈ subsetSums A
If A ⊆ B and A is complete, then B is also complete.
@[gcongr]
theorem IsAddComplete.mono {A B : Set M} (h : A ⊆ B) (ha : IsAddComplete A) : IsAddComplete B := by M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:Set MB:Set Mh:A ⊆ Bha:IsAddComplete A⊢ IsAddComplete B
filter_upwards [ha] with x hx M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:Set MB:Set Mh:A ⊆ Bha:IsAddComplete Ax:Mhx:x ∈ subsetSums A⊢ x ∈ subsetSums B
exact (subsetSums_mono h) hx All goals completed! 🐙namespace IsAddCompleteThe admissible thresholds of a set of natural numbers: every integer at or above the threshold is a finite subset sum of the set.
def thresholds (A : Set ℕ) : Set ℕ :=
{m | ∀ n, m ≤ n → n ∈ subsetSums A}
The least admissible threshold of a set of natural numbers. For an incomplete set this
returns 0. See threshold_isLeast for complete sets.
noncomputable def threshold (A : Set ℕ) : ℕ :=
sInf (thresholds A)Every natural number at or above an admissible threshold is also an admissible threshold.
theorem thresholds_mono {A : Set ℕ} {m m' : ℕ} (hm : m ∈ thresholds A) (h : m ≤ m') :
m' ∈ thresholds A :=
fun n hn ↦ hm n (h.trans hn)The threshold of a complete set is its least admissible threshold.
theorem threshold_isLeast {A : Set ℕ} (hA : IsAddComplete A) :
IsLeast (thresholds A) (threshold A) := by A:Set ℕhA:IsAddComplete A⊢ IsLeast (thresholds A) (threshold A)
obtain ⟨m, hm⟩ := Filter.eventually_atTop.mp hA A:Set ℕhA:IsAddComplete Am:ℕhm:∀ (b : ℕ), m ≤ b → b ∈ subsetSums A⊢ IsLeast (thresholds A) (threshold A)
exact ⟨Nat.sInf_mem ⟨m, hm⟩, fun _ hn ↦ Nat.sInf_le hn⟩ All goals completed! 🐙A least admissible threshold equals the threshold of the set.
theorem threshold_eq_of_isLeast {A : Set ℕ} {a : ℕ} (h : IsLeast (thresholds A) a) :
threshold A = a :=
le_antisymm (Nat.sInf_le h.1) (h.2 (Nat.sInf_mem ⟨a, h.1⟩))Comparing thresholds of complete sets is equivalent to comparing their least-threshold witnesses.
theorem threshold_descent_iff {A B : Set ℕ} (hA : IsAddComplete A) (hB : IsAddComplete B) :
threshold B < threshold A ↔
∃ a b : ℕ, IsLeast (thresholds A) a ∧ IsLeast (thresholds B) b ∧ b < a := by A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete B⊢ threshold B < threshold A ↔ ∃ a b, IsLeast (thresholds A) a ∧ IsLeast (thresholds B) b ∧ b < a
constructor mp A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete B⊢ threshold B < threshold A → ∃ a b, IsLeast (thresholds A) a ∧ IsLeast (thresholds B) b ∧ b < ampr A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete B⊢ (∃ a b, IsLeast (thresholds A) a ∧ IsLeast (thresholds B) b ∧ b < a) → threshold B < threshold A
· mp A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete B⊢ threshold B < threshold A → ∃ a b, IsLeast (thresholds A) a ∧ IsLeast (thresholds B) b ∧ b < a intro h mp A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete Bh:threshold B < threshold A⊢ ∃ a b, IsLeast (thresholds A) a ∧ IsLeast (thresholds B) b ∧ b < a
exact ⟨_, _, threshold_isLeast hA, threshold_isLeast hB, h⟩ All goals completed! 🐙
· mpr A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete B⊢ (∃ a b, IsLeast (thresholds A) a ∧ IsLeast (thresholds B) b ∧ b < a) → threshold B < threshold A rintro ⟨a, b, ha, hb, hab⟩ mpr A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete Ba:ℕb:ℕha:IsLeast (thresholds A) ahb:IsLeast (thresholds B) bhab:b < a⊢ threshold B < threshold A
rw [threshold_eq_of_isLeast ha, mpr A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete Ba:ℕb:ℕha:IsLeast (thresholds A) ahb:IsLeast (thresholds B) bhab:b < a⊢ threshold B < a mpr A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete Ba:ℕb:ℕha:IsLeast (thresholds A) ahb:IsLeast (thresholds B) bhab:b < a⊢ b < a threshold_eq_of_isLeast hb mpr A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete Ba:ℕb:ℕha:IsLeast (thresholds A) ahb:IsLeast (thresholds B) bhab:b < a⊢ b < a mpr A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete Ba:ℕb:ℕha:IsLeast (thresholds A) ahb:IsLeast (thresholds B) bhab:b < a⊢ b < a]mpr A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete Ba:ℕb:ℕha:IsLeast (thresholds A) ahb:IsLeast (thresholds B) bhab:b < a⊢ b < a
exact hab All goals completed! 🐙
The empty set has no admissible threshold, so its threshold has the fallback value 0.
theorem threshold_empty : threshold ∅ = 0 := by ⊢ threshold ∅ = 0
have h : thresholds (∅ : Set ℕ) = ∅ := by
apply Set.eq_empty_iff_forall_notMem.mpr ⊢ ∀ (x : ℕ), x ∉ thresholds ∅ h:thresholds ∅ = ∅⊢ threshold ∅ = 0
intro m hm m:ℕhm:m ∈ thresholds ∅⊢ False h:thresholds ∅ = ∅⊢ threshold ∅ = 0
obtain ⟨B, hB, hs⟩ := hm (m + 1) (Nat.le_succ m) m:ℕhm:m ∈ thresholds ∅B:Finset ℕhB:↑B ⊆ ∅hs:m + 1 = ∑ i ∈ B, i⊢ False h:thresholds ∅ = ∅⊢ threshold ∅ = 0
have hB0 : B = ∅ := Finset.eq_empty_iff_forall_notMem.mpr fun x hx ↦ hB hx m:ℕhm:m ∈ thresholds ∅B:Finset ℕhB:↑B ⊆ ∅hs:m + 1 = ∑ i ∈ B, ihB0:B = ∅⊢ False h:thresholds ∅ = ∅⊢ threshold ∅ = 0
simp [hB0] at hs h:thresholds ∅ = ∅⊢ threshold ∅ = 0 h:thresholds ∅ = ∅⊢ threshold ∅ = 0
simp [threshold, h] All goals completed! 🐙end IsAddComplete
A set A ⊆ M is complete if every sufficiently large element of M is a subset sum of A.
def IsAddStronglyComplete (A : Set M) : Prop :=
∀ ⦃B : Set M⦄, B.Finite → IsAddComplete (A \ B)A strongly complete set is complete.
theorem IsAddStronglyComplete.isAddComplete {A : Set M} (hA : IsAddStronglyComplete A) :
IsAddComplete A := by M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:Set MhA:IsAddStronglyComplete A⊢ IsAddComplete A simpa using hA Set.finite_empty All goals completed! 🐙
If A ⊆ B and A is strongly complete, then B is also strongly complete.
theorem IsAddStronglyComplete.mono {A B : Set M} (h : A ⊆ B) (ha : IsAddStronglyComplete A) :
IsAddStronglyComplete B := fun C hC => (ha hC).mono (by M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:Set MB:Set Mh:A ⊆ Bha:IsAddStronglyComplete AC:Set MhC:C.Finite⊢ A \ C ⊆ B \ C grind All goals completed! 🐙)
A sequence A is strongly complete if fun m => A (n + m) is still complete for all n.
def IsAddStronglyCompleteNatSeq (A : ℕ → M) : Prop :=
∀ n, IsAddComplete (Set.range (fun m => A (n + m)))A strongly complete sequence is complete.
theorem IsAddStronglyCompleteNatSeq.isAddComplete {A : ℕ → M}
(hA : IsAddStronglyCompleteNatSeq A) :
IsAddComplete (Set.range A) := by M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → MhA:IsAddStronglyCompleteNatSeq A⊢ IsAddComplete (Set.range A) simpa using hA 0 All goals completed! 🐙open scoped Classical in
If the range of a sequence A is strongly complete, then A is strongly complete.
theorem IsAddStronglyCompleteNatSeq.of_isAddStronglyComplete {A : ℕ → M}
(h : IsAddStronglyComplete (.range A)) : IsAddStronglyCompleteNatSeq A :=
fun n => (h (Finset.finite_toSet _)).mono (A := .range A \ ((Finset.range n).image A))
(fun _ ⟨⟨y, hy⟩, q⟩ => ⟨y - n, by M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyComplete (Set.range A)n:ℕx✝¹:Mx✝:x✝¹ ∈ Set.range A \ ↑(Finset.image A (Finset.range n))y:ℕhy:A y = x✝¹q:x✝¹ ∉ ↑(Finset.image A (Finset.range n))⊢ (fun m ↦ A (n + m)) (y - n) = x✝¹ grind All goals completed! 🐙⟩)
If A is strongly complete and the preimage of each element is finite, then the range of A
is strongly complete.
theorem IsAddStronglyCompleteNatSeq.isAddStronglyComplete {A : ℕ → M}
(h : IsAddStronglyCompleteNatSeq A) (hA : ∀ m, (A ⁻¹' {m}).Finite) :
IsAddStronglyComplete (.range A) := by M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).Finite⊢ IsAddStronglyComplete (Set.range A)
refine fun B hB => ?_ M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finite⊢ IsAddComplete (Set.range A \ B)
obtain ⟨n, hn⟩ := Finset.exists_nat_subset_range (hB.preimage' (fun b _ => hA b)).toFinset M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:⋯.toFinset ⊆ Finset.range n⊢ IsAddComplete (Set.range A \ B)
rw [Set.Finite.toFinset_subset, M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ ↑(Finset.range n)⊢ IsAddComplete (Set.range A \ B) M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio n⊢ IsAddComplete (Set.range A \ B) Finset.coe_range M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio n⊢ IsAddComplete (Set.range A \ B) M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio n⊢ IsAddComplete (Set.range A \ B)] at hn M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio n⊢ IsAddComplete (Set.range A \ B)
refine (h (n + 1)).mono ?_ M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio n⊢ (Set.range fun m ↦ A (n + 1 + m)) ⊆ Set.range A \ B
refine fun x ⟨y, hy⟩ => ⟨⟨n + 1 + y, hy⟩, fun hx => ?_⟩ M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio nx:Mx✝:x ∈ Set.range fun m ↦ A (n + 1 + m)y:ℕhy:(fun m ↦ A (n + 1 + m)) y = xhx:x ∈ B⊢ False
have : n + 1 + y ∈ Set.Iio n := by M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).Finite⊢ IsAddStronglyComplete (Set.range A) M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio nx:Mx✝:x ∈ Set.range fun m ↦ A (n + 1 + m)y:ℕhy:(fun m ↦ A (n + 1 + m)) y = xhx:x ∈ Bthis:n + 1 + y ∈ Set.Iio n⊢ False grind M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio nx:Mx✝:x ∈ Set.range fun m ↦ A (n + 1 + m)y:ℕhy:(fun m ↦ A (n + 1 + m)) y = xhx:x ∈ Bthis:n + 1 + y ∈ Set.Iio n⊢ False M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → Mh:IsAddStronglyCompleteNatSeq AhA:∀ (m : M), (A ⁻¹' {m}).FiniteB:Set MhB:B.Finiten:ℕhn:A ⁻¹' B ⊆ Set.Iio nx:Mx✝:x ∈ Set.range fun m ↦ A (n + 1 + m)y:ℕhy:(fun m ↦ A (n + 1 + m)) y = xhx:x ∈ Bthis:n + 1 + y ∈ Set.Iio n⊢ False
grind All goals completed! 🐙
A sequence A is complete if every sufficiently large element of M is a sum of
(not necessarily distinct) terms of A.
def IsAddCompleteNatSeq' (A : ℕ → M) : Prop :=
∀ᶠ k in Filter.atTop, k ∈ subseqSums' ASequences whose partial sums are dominated by the next term
If A : ℕ → ℕ is strictly increasing from index n₀ on and A 0 + ⋯ + A (m - 1) ≤ A (m + 1)
for m ≥ n₀, then removing infinitely many terms from A destroys completeness. This is the
argument of Graham [Gr64d] for the sequence n ↦ fib n - (-1) ^ n: once three terms
A m₁ < A m₂ < A m are removed, the remaining terms below A (m + 1) sum to at most
A (m + 1) - 2, so A (m + 1) - 1 is not a sum of distinct remaining terms.
Let A : ℕ → ℕ be strictly increasing from index n₀ on, with
A 0 + ⋯ + A (m - 1) ≤ A (m + 1) for all m ≥ n₀. Then Set.range A \ B is not complete for
any infinite B ⊆ Set.range A.
theorem not_isAddComplete_range_diff_of_sum_range_le {A : ℕ → ℕ} {n₀ : ℕ}
(hA : StrictMono fun k => A (n₀ + k))
(hsum : ∀ m, n₀ ≤ m → ∑ i ∈ Finset.range m, A i ≤ A (m + 1))
{B : Set ℕ} (hB : B ⊆ Set.range A) (hB' : B.Infinite) :
¬ IsAddComplete (Set.range A \ B) := by