/- 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.WellFounded

Complete 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 A

A 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 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 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 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 All goals completed! 🐙

The set of all natural numbers is subcomplete.

@[simp] theorem isSubcomplete_univ : IsSubcomplete Set.univ := ⊢ IsSubcomplete Set.univ k:ℕ⊢ 0 + k * 1 ∈ subsetSums Set.univ exact ⟨{k}, k:ℕ⊢ ↑{k} ⊆ Set.univ All goals completed! 🐙, k:ℕ⊢ 0 + k * 1 = ∑ i ∈ {k}, i 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 := M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:Set MB:Set Mh:A ⊆ Bha:IsAddComplete A⊢ IsAddComplete B filter_upwards [ha] with x M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:Set MB:Set Mh:A ⊆ Bha:IsAddComplete Ax:Mhx:x ∈ subsetSums A⊢ x ∈ subsetSums B All goals completed! 🐙namespace IsAddComplete

The 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) := A:Set ℕhA:IsAddComplete A⊢ IsLeast (thresholds A) (threshold A) A:Set ℕhA:IsAddComplete Am:ℕhm:∀ (b : ℕ), m ≤ b → b ∈ subsetSums A⊢ IsLeast (thresholds A) (threshold A) 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.

A:Set ℕB:Set ℕhA:IsAddComplete AhB:IsAddComplete Ba:ℕb:ℕha:IsLeast (thresholds A) ahb:IsLeast (thresholds B) bhab:b < a⊢ b < a All goals completed! 🐙

The empty set has no admissible threshold, so its threshold has the fallback value 0.

h:thresholds ∅ = ∅⊢ threshold ∅ = 0 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 := M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:Set MhA:IsAddStronglyComplete A⊢ IsAddComplete A 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 (M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:Set MB:Set Mh:A ⊆ Bha:IsAddStronglyComplete AC:Set MhC:C.Finite⊢ A \ C ⊆ B \ C 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) := M:Type u_1inst✝¹:AddCommMonoid Minst✝:Preorder MA:ℕ → MhA:IsAddStronglyCompleteNatSeq A⊢ IsAddComplete (Set.range A) 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, 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✝¹ All goals completed! 🐙⟩)

If A is strongly complete and the preimage of each element is finite, then the range of A is strongly complete.

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 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' A

Sequences 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.

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 AhB':B.Infinitehpre:(A ⁻¹' B).Infinitehlin:∀ (k : ℕ), n₀ ≤ k → k - n₀ ≤ A khlt:∀ (i j : ℕ), n₀ ≤ i → n₀ ≤ j → (A i < A j ↔ i < j)N:ℕm₁:ℕhm₁B:m₁ ∈ A ⁻¹' Bhm₁:n₀ + N < m₁m₂:ℕhm₂B:m₂ ∈ A ⁻¹' Bhm₂:m₁ < m₂m:ℕhmB:m ∈ A ⁻¹' Bhm:m₂ < mhAm₁:m₁ - n₀ ≤ A m₁hAm₂:m₂ - n₀ ≤ A m₂hAm:m + 1 - n₀ ≤ A (m + 1)C:Finset ℕhC:↑C ⊆ Set.range A \ BhsumC:A (m + 1) - 1 = ∑ i ∈ C, iS:Finset ℕ := {i ∈ Finset.range m | A i ≠ A m₁ ∧ A i ≠ A m₂}hS:S = {i ∈ Finset.range m | A i ≠ A m₁ ∧ A i ≠ A m₂}hCsub:C ⊆ Finset.image A Sh1:∑ j ∈ C, j ≤ ∑ i ∈ S, A ih2:∑ i ∈ S, A i + A m₁ + A m₂ ≤ ∑ i ∈ Finset.range m, A ithis:∑ i ∈ Finset.range m, A i ≤ A (m + 1)⊢ False All goals completed! 🐙