/- Copyright 2026 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 FormalConjecturesUtil

Erdős Problem 345

References:

    erdosproblems.com/345

    [ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980), p. 55.

    [Ki17] Kim, D., On the largest integer that is not a sum of distinct positive nth powers. Journal of Integer Sequences 20 (2017), Article 17.7.5. arXiv:1610.02439

@[expose] public sectionnamespace Erdos345open IsAddComplete

The set of $k$-th powers of positive integers.

def kthPowers (k : ℕ) : Set ℕ := {x | ∃ n : ℕ, 0 < n ∧ n ^ k = x}

Let $A\subseteq \mathbb{N}$ be a complete sequence, and define the threshold of completeness $T(A)$ to be the least integer $m$ such that all $n\geq m$ are in $$P(A) = \left{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right}$$ (the existence of $T(A)$ is guaranteed by completeness).

Is it true that there are infinitely many $k$ such that $T(n^k)>T(n^{k+1})$?

Here $T(n^k)$ means the threshold of the positive $k$-th powers. Least-threshold witnesses ensure that the thresholds exist. We restrict to $k\geq 1$, since the zeroth powers form ${1}$, which is incomplete. Positive powers are complete [Ki17].

@[category research open, question, AMS 5 11] theorem erdos_345 : {k : ℕ | 0 < k ∧ ∃ a b : ℕ, IsLeast (thresholds (kthPowers k)) a ∧ IsLeast (thresholds (kthPowers (k + 1))) b ∧ b < a}.Infinite := ⊢ {k | 0 < k ∧ ∃ a b, IsLeast (thresholds (kthPowers k)) a ∧ IsLeast (thresholds (kthPowers (k + 1))) b ∧ b < a}.Infinite All goals completed! 🐙

Every set of positive $k$-th powers with $k\geq 1$ is complete [Ki17].

@[category research solved, AMS 5 11] theorem kthPowers_isAddComplete : ∀ k : ℕ, 0 < k → IsAddComplete (kthPowers k) := ⊢ ∀ (k : ℕ), 0 < k → IsAddComplete (kthPowers k) All goals completed! 🐙

Under the convention $0\in\mathbb{N}$, the threshold of the first powers is $0$: the empty sum represents $0$, and every positive integer is a singleton sum.

@[category test, AMS 5 11] theorem isLeast_thresholds_one : IsLeast (thresholds (kthPowers 1)) 0 := ⊢ IsLeast (thresholds (kthPowers 1)) 0 n:ℕx✝:0 ≤ n⊢ n ∈ subsetSums (kthPowers 1) x✝:0 ≤ 0⊢ 0 ∈ subsetSums (kthPowers 1)n:ℕx✝:0 ≤ nhn:n > 0⊢ n ∈ subsetSums (kthPowers 1) x✝:0 ≤ 0⊢ 0 ∈ subsetSums (kthPowers 1) exact ⟨∅, x✝:0 ≤ 0⊢ ↑∅ ⊆ kthPowers 1 All goals completed! 🐙, x✝:0 ≤ 0⊢ 0 = ∑ i ∈ ∅, i All goals completed! 🐙⟩ n:ℕx✝:0 ≤ nhn:n > 0⊢ n ∈ subsetSums (kthPowers 1) refine ⟨{n}, ?_, n:ℕx✝:0 ≤ nhn:n > 0⊢ n = ∑ i ∈ {n}, i All goals completed! 🐙⟩ n:ℕx✝:0 ≤ nhn:n > 0x:ℕhx:x ∈ ↑{n}⊢ x ∈ kthPowers 1 n:ℕx✝:0 ≤ nhn:n > 0x:ℕhx:x = n⊢ x ∈ kthPowers 1 exact ⟨n, hn, n:ℕx✝:0 ≤ nhn:n > 0x:ℕhx:x = n⊢ n ^ 1 = x All goals completed! 🐙⟩@[category test, AMS 5 11] theorem threshold_one : threshold (kthPowers 1) = 0 := threshold_eq_of_isLeast isLeast_thresholds_oneend Erdos345