/-
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 FormalConjecturesUtilErdős Problem 748
References:
[CaEr90] Cameron, P. J. and Erdős, P., On the number of sets of integers with various properties. (1990), 61-79.
[Er94b] Erdős, Paul, Some problems in number theory, combinatorics and combinatorial geometry. Math. Pannon. (1994), 261-269.
[Er98] Erdős, Paul, Some of my new and almost new problems and results in combinatorial number theory. Number theory (Eger, 1996) (1998), 169-180.
[Gr04] Green, Ben, The Cameron-Erdős conjecture. Bull. London Math. Soc. (2004), 769-778.
[Sa03] Sapozhenko, A. A., The Cameron-Erdős conjecture. Dokl. Akad. Nauk (2003), 749-752.
@[expose] public sectionopen Filter Realnamespace Erdos748open scoped Classical in
f n counts the number of sum-free $A\subseteq {1,\ldots,n}$, i.e. $A$ contains no
solutions to $a=b+c$ with $a,b,c\in A$.
noncomputable def f (n : ℕ) : ℕ :=
((Finset.Icc 1 n).powerset.filter fun A : Finset ℕ ↦ IsSumFree (A : Set ℕ)).cardLet $f(n)$ count the number of sum-free $A\subseteq {1,\ldots,n}$, i.e. $A$ contains no solutions to $a=b+c$ with $a,b,c\in A$. Is it true that $$f(n)=2^{(1+o(1))\frac{n}{2}}?$$
The Cameron–Erdős conjecture. This is true, and in fact $f(n) \ll 2^{n/2}$, which was proved independently by Green [Gr04] and Sapozhenko [Sa03].
The statement $f(n)=2^{(1+o(1))n/2}$ is formalised as $\log_2 f(n)/n\to 1/2$.
@[category research solved, question, AMS 5 11, formal_proof using lean4 at
"https://github.com/plby/lean-proofs/blob/8822f7ddef30fadbd92e1c6ab4ed897af356af5e/src/latest/ErdosProblems/Erdos748.lean#L1228"]
theorem erdos_748 :
Tendsto (fun n : ℕ ↦ logb 2 (f n) / n) atTop (nhds (1 / 2)) := ⊢ Tendsto (fun n ↦ logb 2 ↑(f n) / ↑n) atTop (nhds (1 / 2))
All goals completed! 🐙It is trivial to see that $f(n) \geq 2^{\frac{n}{2}}$, considering all subsets of $(n/2,n]$. The source writes $[n/2,n]$, but for even $n$ that interval is not sum-free, since $n/2 + n/2 = n$.
@[category textbook, AMS 5 11]
theorem erdos_748.variants.lower_bound (n : ℕ) :
(2 : ℝ) ^ ((n : ℝ) / 2) ≤ (f n : ℝ) := n:ℕ⊢ 2 ^ (↑n / 2) ≤ ↑(f n)
All goals completed! 🐙Green [Gr04] and Sapozhenko [Sa03] proved that $f(n) \ll 2^{n/2}$.
@[category research solved, AMS 5 11]
theorem erdos_748.variants.green_sapozhenko :
∃ C : ℝ, ∀ n : ℕ, (f n : ℝ) ≤ C * 2 ^ ((n : ℝ) / 2) := ⊢ ∃ C, ∀ (n : ℕ), ↑(f n) ≤ C * 2 ^ (↑n / 2)
All goals completed! 🐙In fact, both Green [Gr04] and Sapozhenko [Sa03] prove the stronger asymptotic $f(n) \sim c_n 2^{n/2}$, where $c_n$ takes on one of two values depending on the parity of $n$.
@[category research solved, AMS 5 11]
theorem erdos_748.variants.asymptotic :
∃ c₀ c₁ : ℝ, 0 < c₀ ∧ 0 < c₁ ∧
Tendsto (fun m : ℕ ↦ (f (2 * m) : ℝ) / 2 ^ m) atTop (nhds c₀) ∧
Tendsto (fun m : ℕ ↦ (f (2 * m + 1) : ℝ) / 2 ^ ((2 * m + 1 : ℝ) / 2)) atTop
(nhds c₁) := ⊢ ∃ c₀ c₁,
0 < c₀ ∧
0 < c₁ ∧
Tendsto (fun m ↦ ↑(f (2 * m)) / 2 ^ m) atTop (nhds c₀) ∧
Tendsto (fun m ↦ ↑(f (2 * m + 1)) / 2 ^ ((2 * ↑m + 1) / 2)) atTop (nhds c₁)
All goals completed! 🐙end Erdos748