/-
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.
-/modulepublicimportFormalConjecturesUtil
[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.
[ELRSS99] Erdős, P., Lev, V., Rauzy, G., Sándor, C. and Sárközy, A., Greedy algorithm,
arithmetic progressions, subset sums and divisibility. Discrete Math. (1999), 119-135.
What is the size of the largest $A\subseteq {1,\ldots,n}$ such that in the set
$$\left{ \sum_{a\in S} a : \emptyset\neq S\subseteq A\right}$$
no two distinct elements divide each other?
A problem of Erdős and Sárközy. The answer is $(1+o(1))\log_2 n$: the lower bound
$\lvert A\rvert > \log_2 n - 1$ is achieved by the construction of Erdős, Lev, Rauzy, Sándor
and Sárközy [ELRSS99] (see erdos_882.variants.lower_bound), while
Erdős Problem 1 gives
$\lvert A\rvert \leq \log_2 n + \tfrac{1}{2}\log_2\log n + O(1)$.
Erdős, Lev, Rauzy, Sándor and Sárközy [ELRSS99] proved that
$\lvert A\rvert > \log_2 n - 1$ is achievable, taking
$A = {2^m - 2^{m-1}, 2^m - 2^{m-2}, \ldots, 2^m - 1}$.
The key property of this construction is that distinct nonempty subsets have subset sums
which never divide one another.
The linked theorem no_div is phrased in terms of index sets $S \subseteq {0, \ldots, m-1}$,
i.e. $\sum_{i \in S_1} (2^m - 2^i) \nmid \sum_{i \in S_2} (2^m - 2^i)$ for distinct nonempty
$S_1, S_2$; it transfers to subsets of A m via the injectivity of $i \mapsto 2^m - 2^i$
(see card_A).
The lower bound of [ELRSS99] in quantitative form: for every $n \geq 1$ there is a subset-sum
antichain $A \subseteq {1, \ldots, n}$ with $\lvert A\rvert > \log_2 n - 1$, namely $A_m$
with $m = \lfloor \log_2 n \rfloor$ (by erdos_882.variants.lower_bound, A_subset_Icc
and card_A).
A sorry-free Lean 4 proof of this statement is the theorem erdos_882 of [Alexeev].
That formalisation expresses the antichain condition as primitivity of the set of nonempty
subset sums (no element divides another one). For $A \subseteq {1, \ldots, n}$ this is
equivalent to IsSubsetSumAntichain A: if two distinct subsets had the same sum, then
removing their common elements would leave two disjoint nonempty subsets with a common sum
$t \geq 1$, so that $t$ and $2t$ would both be nonempty subset sums.
Sándor's construction (reported without reference in [Er98]) is claimed to achieve
$\lvert A\rvert = (1-o(1))\log_2 n$ with $A = {2^i + m 2^m : 0 \leq i < m}$ and
$n = 2^{m-1} + m 2^m$.