/-
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
$f(n)$ is the largest $k$ such that every set $A\subset\mathbb{R}$ with $n$ elements has a
dissociated subset with at least $k$ elements. The set of such $k$ contains $0$ (take the empty
subset) and is bounded by $n$, so sSup is a true maximum. The set $A$ may contain $0$, which
can never belong to a dissociated set. For $n = 0$ the value is $0$.
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$?
This is the first part, a problem of Erdős [Er65, p. 188]. We read "estimate" as an asymptotic
equivalence $f(n)\sim$ answer n. The order of magnitude $\log n$ is easy (see
erdos_963.variants.greedy and the example $a_i=i$ in [Er65, p. 188]), so the question is the
constant.
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$?
This is the second part. Erdős [Er65, p. 188] asks whether the bound $\lfloor\log_3 n\rfloor$ can
be improved to $\lfloor\log_2 n\rfloor$. We state it for all $n\geq 1$, with
$\lfloor\log_2 n\rfloor$ written as Nat.log 2 n.
As on the problem page, $A$ is any set of reals. [Er65] speaks of "given numbers" and uses the
example $a_i=i$. Allowing negative numbers makes the question harder. A dissociated set never
contains both $x$ and $-x$, and changing signs keeps a set dissociated. So the largest dissociated
subsets of $A$ and of ${\lvert a\rvert : a\in A,\ a\neq 0}$ have the same size, and the sets
${\pm a : a\in S}$ (with $0$ added for odd $n$) show that $f(2m)=f(2m+1)$ is the least size of a
largest dissociated subset of a set of $m$ positive reals. Hence this statement asks for
$\lfloor\log_2 m\rfloor+1$ for $m$ positive reals. The question for positive reals with
$\lfloor\log_2\lvert A\rvert\rfloor$, one less, is erdos_963.variants.positive; it follows from
this statement.
Erdős noted that the greedy algorithm showed $f(n)\geq \lfloor \log_3 n\rfloor$
[Er65, p. 188].
@[categoryresearchsolved,AMS511]theoremerdos_963.variants.greedy(n:ℕ):Nat.log3n≤fn:=byn:ℕ⊢ Nat.log3n≤fnclassicalrefinele_ffunAhA↦?_n:ℕA:FinsetℝhA:A.card=n⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B-- Take a maximal dissociated subset `B` of `A`.obtain⟨B,hB⟩:=(A.powerset.filterfunB:Finsetℝ↦AddDissociated(B:Setℝ)).exists_maximal⟨∅,Finset.mem_filter.2⟨Finset.empty_mem_powerset_,byn:ℕA:FinsetℝhA:A.card=n⊢ AddDissociated↑∅n:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x∈{B∈A.powerset|AddDissociated↑B})B⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑BsimpAll goals completed! 🐙n:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x∈{B∈A.powerset|AddDissociated↑B})B⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B⟩⟩n:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x∈{B∈A.powerset|AddDissociated↑B})B⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bsimponly[Finset.mem_filter,Finset.mem_powerset]athBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)B⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B-- Every element of `A` is a signed sum of `B`.havehAB:A⊆signedSumsB:=byn:ℕ⊢ Nat.log3n≤fnn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bintroahan:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈A⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bby_caseshaB:a∈Bposn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∈B⊢ a∈signedSumsBnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉B⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B·posn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∈B⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bsimpausingsum_sub_sum_mem_signedSums(Finset.empty_subsetB)(Finset.singleton_subset_iff.2haB)All goals completed! 🐙n:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bobtain⟨t,u,ht,hu,htu,hne,hsum⟩:=not_addDissociated_iff_exists_disjoint.1funh↦hB.not_gt⟨Finset.insert_subset_iff.2⟨ha,hB.1.1⟩,h⟩<|Finset.ssubset_inserthaBnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:↑t⊆↑(insertaB)hu:↑u⊆↑(insertaB)htu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,a⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Brw[Finset.coe_subsetnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,a⊢ a∈signedSumsBnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,a⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B]aththunegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,a⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bby_caseshat:a∈tposn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∈t⊢ a∈signedSumsBnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉t⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B·posn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∈t⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bexactmem_signedSums_of_memhthuhtuhsumhatAll goals completed! 🐙n:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bby_caseshau:a∈uposn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∈u⊢ a∈signedSumsBnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∉u⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B·posn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆insertaBhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∈u⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bexactmem_signedSums_of_memhuhthtu.symmhsum.symmhauAll goals completed! 🐙n:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Brw[Finset.subset_insert_iff_of_notMemhatnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆Bhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∉u⊢ a∈signedSumsBnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆Bhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∉u⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B]athtnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆Bhu:u⊆insertaBhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∉u⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Brw[Finset.subset_insert_iff_of_notMemhaunegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆Bhu:u⊆Bhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∉u⊢ a∈signedSumsBnegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆Bhu:u⊆Bhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∉u⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑B]athunegn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)Ba:ℝha:a∈AhaB:a∉Bt:Finsetℝu:Finsetℝht:t⊆Bhu:u⊆Bhtu:Disjointtuhne:t≠uhsum:∑a∈t,a=∑a∈u,ahat:a∉thau:a∉u⊢ a∈signedSumsBn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bexactabsurd(hB.1.2(Finset.coe_subset.2ht)(Finset.coe_subset.2hu)hsum)hnen:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Bn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ ∃B⊆A,Nat.log3n≤B.card∧AddDissociated↑Brefine⟨B,hB.1.1,?_,hB.1.2⟩n:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ Nat.log3n≤B.cardcalcNat.log3n=Nat.log3A.card:=byn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ Nat.log3n=Nat.log3A.cardrw[hAn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ Nat.log3n=Nat.log3nAll goals completed! 🐙]All goals completed! 🐙_≤Nat.log3(3^B.card):=Nat.log_mono_right((Finset.card_le_cardhAB).trans(card_signedSums_leB))_=B.card:=Nat.log_pow(byn:ℕA:FinsetℝhA:A.card=nB:FinsetℝhB:Maximal(funx↦x⊆A∧AddDissociated↑x)BhAB:A⊆signedSumsB⊢ 1<3norm_numAll goals completed! 🐙)_
The second part for sets of positive reals, with $\lfloor\log_2\lvert A\rvert\rfloor$ as in
[Er65, p. 188] and its example $a_i=i$: every set $A$ of positive reals has a dissociated subset
with at least $\lfloor\log_2 \lvert A\rvert\rfloor$ elements.