/- 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 344

References:

    erdosproblems.com/344

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

    [Er61b] Erdős, P., On the representation of large integers as sums of distinct summands taken from a fixed set. Acta Arith. (1961/62), 345-354.

    [Fo66] Folkman, J., On the representation of integers as sums of distinct terms from a fixed sequence. Canadian J. Math. 18 (1966), 643-655.

    [SzVu06] Szemerédi, E. and Vu, V., Long arithmetic progressions in sumsets: thresholds and bounds. J. Amer. Math. Soc. 19 (2006), 119-169.

    [SzVu06b] Szemerédi, E. and Vu, V., Finite and infinite arithmetic progressions in sumsets. Ann. of Math. 163 (2006), 1-35.

@[expose] public sectionopen Filternamespace Erdos344

If $A\subseteq \mathbb{N}$ is a set of integers such that $$\lvert A\cap {1,\ldots,N}\rvert\gg N^{1/2}$$ for all $N$ then must $A$ be subcomplete? That is, must $$P(A) = \left{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right}$$ contain an infinite arithmetic progression?

This is true, and was proved by Szemerédi and Vu [SzVu06].

The implied constant is absolute, as in [SzVu06b, Corollary 1.4].

@[category research solved, question, AMS 5 11, formal_proof using lean4 at "https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos344.lean#L8994"] theorem erdos_344 : ∃ C : ℝ, 0 < C ∧ ∀ A : Set ℕ, (∀ᶠ N : ℕ in atTop, C * Real.sqrt N ≤ A.countUpTo N) → IsSubcomplete A := ⊢ ∃ C, 0 < C ∧ ∀ (A : Set ℕ), (∀ᶠ (N : ℕ) in atTop, C * √↑N ≤ ↑(A.countUpTo N)) → IsSubcomplete A All goals completed! 🐙

The stronger conjecture that this is true under $$\lvert A\cap {1,\ldots,N}\rvert\geq (2N)^{1/2}$$ seems to be still open (this would be best possible as shown by [Er61b]).

The bound is required for all sufficiently large $N$: at $N=1$, it is impossible since $\lvert A\cap{1}\rvert\leq 1<\sqrt{2}$.

@[category research open, question, AMS 5 11] theorem erdos_344.variants.sqrt_two : ∀ A : Set ℕ, (∀ᶠ N : ℕ in atTop, Real.sqrt (2 * N) ≤ A.countUpTo N) → IsSubcomplete A := ⊢ ∀ (A : Set ℕ), (∀ᶠ (N : ℕ) in atTop, √(2 * ↑N) ≤ ↑(A.countUpTo N)) → IsSubcomplete A All goals completed! 🐙

Folkman proved this under the stronger assumption that $$\lvert A\cap {1,\ldots,N}\rvert\gg N^{1/2+\epsilon}$$ for some $\epsilon>0$ [Fo66].

C:ℝleft✝:0 < Ch:∀ (A : Set ℕ), (∀ᶠ (N : ℕ) in atTop, C * √↑N ≤ ↑(A.countUpTo N)) → IsSubcomplete Aε:ℝhε:0 < εc:ℝhc:0 < cA:Set ℕhA:∀ᶠ (N : ℕ) in atTop, c * ↑N ^ (1 / 2 + ε) ≤ ↑(A.countUpTo N)hpow:Tendsto (fun N ↦ ↑N ^ ε) atTop atTopN:ℕhN:c * ↑N ^ (1 / 2 + ε) ≤ ↑(A.countUpTo N)hNe:C / c ≤ ↑N ^ εhsplit:↑N ^ (1 / 2 + ε) = √↑N * ↑N ^ ε⊢ c * ↑N ^ ε * √↑N = c * (√↑N * ↑N ^ ε); All goals completed! 🐙 _ ≤ A.countUpTo N := hNC:ℝhlim:Tendsto (fun N ↦ √↑N) atTop atTopN:ℕhN:C ≤ √↑Nhc:Set.univ.countUpTo N = N⊢ C * √↑N ≤ ↑N calc C * Real.sqrt N ≤ Real.sqrt N * Real.sqrt N := C:ℝhlim:Tendsto (fun N ↦ √↑N) atTop atTopN:ℕhN:C ≤ √↑Nhc:Set.univ.countUpTo N = N⊢ C * √↑N ≤ √↑N * √↑N All goals completed! 🐙 _ = N := Real.mul_self_sqrt (Nat.cast_nonneg N)end Erdos344