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

References:

    erdosproblems.com/792

    Ben Green's Open Problem 1: a related question for sets of positive integers; see Green1.green_1 in FormalConjectures.GreensOpenProblems.«1».

    [AlKl90] Alon, N. and Kleitman, D. J., Sum-free subsets. A tribute to Paul Erdős (1990), 13-26. PDF

    [Be25b] Bedert, B., Large sum-free subsets of sets of integers via $L^1$-estimates for trigonometric series. arXiv:2502.08624 (2025).

    [Bo97] Bourgain, Jean, Estimates related to sumfree subsets of sets of integers. Israel J. Math. 97 (1997), 71-92. DOI

    [EGM14] Eberhard, Sean and Green, Ben and Manners, Freddie, Sets of integers with no large sum-free subset. Ann. of Math. (2) 180 (2014), 621-652.

    [Er65] Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math., Vol. VIII (1965), 181-189. PDF

    [Er73] Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117-138. PDF

@[expose] public sectionopen Filter Asymptoticsnamespace Erdos792

The largest size we can guarantee for a sum-free subset of any set of n integers.

Zero is allowed, as in the problem's wording. This gives f 1 = 0. The same number can be used twice in a sum, so a + a = c is forbidden too.

noncomputable def f (n : ℕ) : ℕ := sSup {m : ℕ | ∀ A : Finset ℤ, A.card = n → ∃ B : Finset ℤ, B ⊆ A ∧ IsSumFree (B : Set ℤ) ∧ m ≤ B.card}

The set {0} has no nonempty sum-free subset, so f 1 = 0.

m:ℕh_guarantee:m ∈ {m | ∀ (A : Finset ℤ), A.card = 1 → ∃ B ⊆ A, IsSumFree ↑B ∧ m ≤ B.card}B:Finset ℤh_subset:B ⊆ {0}h_sum_free:IsSumFree ↑{0}h_size:m ≤ B.cardh_zero:B = {0}⊢ m ≤ 0 All goals completed! 🐙

The set {1, 2} is not sum-free because 1 + 1 = 2.

⊢ ¬∀ x ∈ {1, 2}, ∀ y ∈ {1, 2}, x + y ∉ {1, 2} All goals completed! 🐙

The set {1, 3} is sum-free, even when we use the same number twice.

⊢ ∀ x ∈ {1, 3}, ∀ y ∈ {1, 3}, x + y ∉ {1, 3} All goals completed! 🐙def erdos_792.answer : ℕ → ℝ := ⊢ ℕ → ℝ All goals completed! 🐙

Let $f(n)$ be maximal such that in any $A\subset \mathbb{Z}$ with $\lvert A\rvert=n$ there exists some sum-free subset $B\subseteq A$ with $\lvert B\rvert \geq f(n)$, so that there are no solutions to $$a+b=c$$ with $a,b,c\in B$, allowing $a=b$. Estimate $f(n)$.

Since $f(n) = n/3 + o(n)$ is known, we interpret "estimate" as determining the order of magnitude of the excess $f(n) - n/3$.

@[category research open, question value, AMS 5 11] theorem erdos_792 : (fun n : ℕ => (f n : ℝ) - n / 3) =Θ[atTop] erdos_792.answer := ⊢ (fun n ↦ ↑(f n) - ↑n / 3) =Θ[atTop] erdos_792.answer All goals completed! 🐙

Alon and Kleitman [AlKl90, Proposition 1.1] improved the lower bound to $(n+1)/3$. Here we restrict to sets of $n \geq 3$ positive integers, to match Bourgain's bound below.

@[category research solved, AMS 5 11] theorem erdos_792.variants.alon_kleitman (A : Finset ℤ) (h_positive : ∀ a ∈ A, 0 < a) (h_card : 3 ≤ A.card) : ∃ B ⊆ A, IsSumFree (B : Set ℤ) ∧ A.card + 1 ≤ 3 * B.card := A:Finset ℤh_positive:∀ a ∈ A, 0 < ah_card:3 ≤ A.card⊢ ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 1 ≤ 3 * B.card All goals completed! 🐙

Bourgain [Bo97, Proposition 1.3] further improved the lower bound to $(n+2)/3$ for sets of $n \geq 3$ positive integers. The size restriction appears in the proof on p. 76; the set ${1,2}$ shows why it cannot be omitted.

@[category research solved, AMS 5 11] theorem erdos_792.variants.bourgain (A : Finset ℤ) (h_positive : ∀ a ∈ A, 0 < a) (h_card : 3 ≤ A.card) : ∃ B ⊆ A, IsSumFree (B : Set ℤ) ∧ A.card + 2 ≤ 3 * B.card := A:Finset ℤh_positive:∀ a ∈ A, 0 < ah_card:3 ≤ A.card⊢ ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 2 ≤ 3 * B.card All goals completed! 🐙

Bourgain's bound [Bo97] implies Alon and Kleitman's bound [AlKl90] on this domain.

@[category test, AMS 5 11] theorem erdos_792.variants.bourgain_implies_alon_kleitman : type_of% erdos_792.variants.bourgain → type_of% erdos_792.variants.alon_kleitman := ⊢ (∀ (A : Finset ℤ), (∀ a ∈ A, 0 < a) → 3 ≤ A.card → ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 2 ≤ 3 * B.card) → ∀ (A : Finset ℤ), (∀ a ∈ A, 0 < a) → 3 ≤ A.card → ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 1 ≤ 3 * B.card h:∀ (A : Finset ℤ), (∀ a ∈ A, 0 < a) → 3 ≤ A.card → ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 2 ≤ 3 * B.cardA:Finset ℤh_positive:∀ a ∈ A, 0 < ah_card:3 ≤ A.card⊢ ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 1 ≤ 3 * B.card h:∀ (A : Finset ℤ), (∀ a ∈ A, 0 < a) → 3 ≤ A.card → ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 2 ≤ 3 * B.cardA:Finset ℤh_positive:∀ a ∈ A, 0 < ah_card:3 ≤ A.cardB:Finset ℤh_subset:B ⊆ Ah_sum_free:IsSumFree ↑Bh_size:A.card + 2 ≤ 3 * B.card⊢ ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 1 ≤ 3 * B.card h:∀ (A : Finset ℤ), (∀ a ∈ A, 0 < a) → 3 ≤ A.card → ∃ B ⊆ A, IsSumFree ↑B ∧ A.card + 2 ≤ 3 * B.cardA:Finset ℤh_positive:∀ a ∈ A, 0 < ah_card:3 ≤ A.cardB:Finset ℤh_subset:B ⊆ Ah_sum_free:IsSumFree ↑Bh_size:A.card + 2 ≤ 3 * B.card⊢ A.card + 1 ≤ 3 * B.card All goals completed! 🐙end Erdos792