Problem 882

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?

Source: erdosproblems.com/882

Number theory
Primitive sets

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved on the site (the remarks credit the lower bound to Erdős, Lev, Rauzy, Sándor and Sárközy and the upper bound to the distinct-subset-sums bound of Problem 1). The frontmatter standing derives from the accepted claim page the two-sided bound of 1999, which fixes the size to its leading term $\log_2 n+O(\log\log n)$ ; a pending partial claim, Korsky's near-exact bounds, narrows it to two consecutive values.

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. 200 (1999), no. 1--3, 119--135, DOI 10.1016/S0012-365X(98)00385-9. Property R and the function $R(n)$ , p. 127; Theorem 5, $\frac{\log n}{\log2}-1<R(n)<\frac{\log n}{\log2}+\frac{\log\log n}{2\log2}+c$ for $n\ge3$ , p. 129; its proof, pp. 133--134; the article is in the publisher's open archive. Library home: Erdős 1999; result page Theorem 5.
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.

Problem 882

Status

Proof claims

Discussion