Subset sums (Q1090706): Difference between revisions

Let \(f(n,m)\), \(m\geq 1\), denote the maximal cardinality of a subset \(B\) of \(A\) of \(\{\) 1,2,...,n\(\}\) such that no subset \(B\) of \(A\) adds up to \(m\). Erdős and Graham proved that \(f(n,m)\geq (+o(1))n\) for all \(n, m\). Let \(A\) be a subset of residues mod \(n\), with cardinality \(| A| >[1/k+\varepsilon] n\), \(n>n_ 0(k,\varepsilon)\). The author proves that there exists a non-empty subset \(B\) of \(A\), \(| B| \leq k\), with \(\sum_{b\in B}b\equiv 0 \pmod n\), and deduces that \(f(n,2n)=(1/3+o(1))n\), thus settling a problem of Erdős and Graham. He also obtains some near best possible estimates for \(f(n,m)\) when \(n^{1+\varepsilon}\leq m\leq n^ 2/\log^ 2 n\) and conjectures that a stronger result holds.