Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 963

Statement. Let $f(n)$ be the maximal $k$ such that in any set $A\subset \mathbb{R}$ of size $n$ there is a subset $B\subseteq A$ of size $\lvert B\rvert\geq k$ which is dissociated that is, the sums $\sum_{b\in S}b$ are distinct for all $S\subseteq B$ . Estimate $f(n)$ - in particular, is it true that

f(n)\geq \lfloor \log_2 n\rfloor?

Status. Open. The site labels the problem OPEN, with its note that no finite computation can settle it (page last edited 23 January 2026).

Source. erdosproblems.com/963, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #963, https://www.erdosproblems.com/963.

References.

[Er65] Erdős, P., Extremal problems in number theory. Proc. Sympos. Pure Math. VIII, Amer. Math. Soc. (1965), 181--189. Printed p. 188: the bound $k\ge\lfloor\log n/\log3\rfloor$ , called not difficult and given without proof, the question whether $\lfloor\log n/\log2\rfloor$ is attainable, and the example $a_i=i$ . Library home: erdos_1965_extremal_problems_number_theory.
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999); the site cites item 1.22.

Formalization. No external statement recorded.

Current assessment

The question (site formulation, page last edited 23 January 2026). The statement above; OPEN. The site's one remark records that Erdős noted the greedy bound $f(n)\ge\lfloor\log_3 n\rfloor$ . In [Er65] (p. 188) he calls the bound not difficult and prints no proof; the greedy argument, worked out on the card for that paper, takes a maximal dissociated $B\subseteq A$ , so that every element of $A$ is a combination of elements of $B$ with coefficients in $\{-1,0,1\}$ and $n\le3^{|B|}$ . The same paragraph of [Er65] asks whether $\lfloor\log_2 n\rfloor$ is attainable and says that the example $a_i=i$ , $1\le i\le n$ , shows that this bound, if true, is nearly best possible: a dissociated $k$ -subset of $\{1,\ldots,n\}$ has $2^k$ distinct subset sums in $[0,kn]$ , so $2^k\le kn+1$ and $f(n)\le\log_2 n+O(\log\log n)$ . The known bounds are $\lfloor\log_3 n\rfloor\le f(n)\le\log_2 n+O(\log\log n)$ ; whether $f(n)\ge\lfloor\log_2 n\rfloor$ for every $n$ is the open question, and the problem has no claim page.

The finite comparison below rules out the initial interval as a universal minimizer of the largest dissociated-subset size. It does not resolve the logarithmic lower-bound question.

The site's discussion thread carries two arguments, neither a dated manuscript, so neither gets a claim page; the discussion card records the thread. In post 2027 (5 December 2025) KoishiChan claims that every $n$ -element set of reals contains a dissociated subset of size $(1-o(1))\log_2 n$ , by a recursion that dilates the set modulo a prime and finds well-populated progression cells through a character-sum second moment. The replies report an off-by-one defect, which the author says is fixed by lowering a parameter by one, and a review carried out with ChatGPT Pro, as the post names it, which found minor issues; on 23 January 2026 the site's curator, Thomas Bloom, wrote in post 3664 that the argument looked good to him and asked for a formal write-up; the site labels the problem OPEN and lists no proof claim (page last edited 23 January 2026). The bound is recorded here as an unverified community claim: an asymptotic lower bound, which would not by itself decide the $\lfloor\log_2 n\rfloor$ question. In post 3658 (23 January 2026) a commenter claims the exact bound $f(n)\ge\lfloor\log_2 n\rfloor$ , labeling the proof AI-assisted; it rests on the unproved assertion that $\{1,\ldots,n\}$ minimizes the largest dissociated subset among $n$ -element real sets, which post 3662 rejects and the 13-element example below refutes, so the argument gives neither a proof nor a disproof of the problem.

Search scope, 2026-10-06: the site's problem page (OPEN, last edited 23 January 2026, source keys [Er65] and [Va99, 1.22], no proof claims) and its discussion thread of 20 posts through 3 September 2026; the community database lists the problem as open and unformalized as of its last update, and formal-conjectures has no statement file for it.

Known Results

Write $d(A)$ for the largest size of a dissociated subset of a finite real set $A$ . BAKKAOUI's posts 8701 and 8709, 3 September 2026, give the fixed set

A^*=\{1,2,3,4,5,6,7,8,9,10,12,13,15\}

with $d(A^*)=4$ , whereas $d(\{1,\ldots,13\})=5$ . The source-owned reconstruction gives the exact witnesses, all 1287 required five-subset checks, and the heredity and interval upper-bound arguments. Post 8709 corrects post 8701; the author says that AI agents assisted the searches and the literature check and that the displayed example was checked by hand in exact integer arithmetic.

Because $A^*$ is itself an allowed real set, this yields $f(13)\le4$ . It does not yield $f(13)=4$ ; $\lfloor\log_2 13\rfloor=3$ , so this example does not refute the catalog's proposed lower bound. It settles no instance of the question, so it has no claim page.

The larger searches through n=16 and window 34, the claimed OEIS identity and the negative literature search remain source-reported computations. Their bounded domains cannot establish the minimum over all real sets, the first possible positive-integer failure, or exceptional behavior at n=13.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (62)

Other Number Theory Dissociation dimension bounds A construction for sets of integers with distinct subset sums On the dimension of additive sets library/additive_combinatorics/dubroff_2021_note_erdos_distinct_subset_sums_problem library/additive_combinatorics/erdos_1965_extremal_problems_number_theory Mean Values of Character Sums BAKKAOUI's dissociated-set counterexample The initial interval need not minimize dissociation On unique sums in Abelian groups Lattice 3-polytopes with few lattice points Proposition 2.2: the volume vector determines a point set up to unimodular maps when its gcd is one Theorem 1.1: classification of lattice 3-polytopes with five lattice points Theorem 1.2: structure of lattice 3-polytopes of size five by signature Theorem 1.3 (Corollary 5.1): finitely many lattice 3-polytopes of each size and width above one A construction for sets of integers with distinct subset sums Theorem 2.1: the sets S_{n,m} built from the difference vector d_n have distinct subset sums for m >= 2n Theorem (abstract, p. 1, unnumbered): f(n) < 0.22002 * 2^n for all sufficiently large n On the dimension of additive sets Variations on the Erdős distinct-sums problem The continuous knapsack set Lemma 2.8 (p. 7): a facet with distinct positive continuous coefficients yields an empty lattice polytope Theorem 2.6 (p. 6): a facet descends to the knapsack set with one continuous variable per distinct nonzero coefficient Theorem 2.9 (p. 8): a facet of the continuous knapsack hull has at most 2^n - n distinct nonzero continuous coefficients additive_combinatorics/dubroff_2021_note_erdos_distinct_subset_sums_problem additive_combinatorics/erdos_1965_extremal_problems_number_theory Erdős Problems: discussion thread for Problem 963 The vertex ideal of a lattice Corollary 4.7 (p. 18): the product ideal and the vertex ideal have the same radical Definition 4.1 (p. 15): the product ideal of a lattice, contained in the vertex ideal Proposition 2.1 (p. 3): the vertices of all fibers of a lattice form an order ideal, so the vertex ideal exists Theorem 2.10 (p. 6): the radical of the vertex ideal is the Stanley–Reisner ideal of the lattice's matroid complex Theorem 2.8 (p. 5): the vertex ideal is generated by the lcm monomials of the positive circuits of the Graver basis On Isoperimetric Stability Theorem 2: small edge boundary with respect to an independent set Theorem 4: independent subsets of a popular-difference set On the size of dissociated bases Theorem 1 (p. 2): the Boolean cube {0,1}^n has a dissociated subset of size (1+o(1)) n log_2 n / log_2 9 Theorem 2 (p. 2): two maximal dissociated subsets of one finite set differ in size by at most a logarithmic factor Theorem 3 (p. 2): in a group of exponent e, every maximal dissociated subset of A has size between r and r log_2 e Integer sets with distinct subset-sums Theorem (1.8) (p. 298): the Atkinson-Negro-Santoro sequence gives a distinct-subset-sum n-set for every n Mean Values of Character Sums Theorem 1: every moment of the maximal character sum is O(phi(q)q^k)Theorem 2: moments of maximal Legendre-symbol sums averaged over primes Integral Polyhedra in Three Space Theorem 1.2: an integral polyhedron in R^n has at most 2^n vertices Theorem 1.3: Howe's theorem on eight-vertex integral polyhedra in R^3 Theorem 1.4: vertices on two adjacent lattice planes Theorem 2.6: a common characteristic plane for a 4 x 3 matrix

Graph