On a conjecture of Alon (Q841263): Difference between revisions

Let \(n\) be a (large) positive integer and \(m\) another positive integer between \(n\) and \(n^2.\) Erdős and Graham [\textit{P. Erdős}, ``Some problems and results on combinatorial number theory'', Ann. N. Y. Acad. Sci. 576, 132--145 (1989; Zbl 0790.11015)] defined and asked to estimate \(f(n,m),\) the maximal cardinality of a subset \(A\) of \(\{1,2,\dots,n\}\) such that no subset \(B,\) \(B\subseteq A,\) satisfies \(\sum_{b\in B}b=m.\) Let \(s\) be a positive integer not dividing \(m.\) Then any sum of elements of the set \(\{s,2s,\dots,\lfloor{n\over s}\rfloor s\}\) cannot be equal to \(m\) since \(s\) does not divide \(m.\) So \(f(n,m)\geq\lfloor{n\over s}\rfloor\) and, if \(s_0(m)\) is the smallest positive integer not dividing \(n,\) then \(f(n,m)\geq\lfloor{n\over {s_0(m)}}\rfloor.\) \textit{N. Alon} [``Subset sums'', J. Number Theory 27, 196--205 (1987; Zbl 0622.10042)] conjectured that if \(m\) is ``far'' from \(n\) and from \(n^2,\) then \(\lfloor{n\over {s_0(m)}}\rfloor\) is the order of magnitude of \(f(n,m).\) Erdős-Graham, Alon, and Lipkin [\textit{E. Lipkin}, ``On representation of \(r-\)th powers by subset sums'', Acta Arith. 52, No. 4, 353--366 (1989; Zbl 0691.10042)] obtained results towards this direction. In the paper under review, the authors prove Alon's conjecture. The main result is: ``For any constants \(c>0\) and \(\epsilon>0,\) there is a constant \(n_0=n_0(c,\epsilon)\) such that the following holds. If \(n\geq n_0\) and \[ cn(\log n)^{1+\epsilon}\leq m\leq{{n^2}\over{9\log^2n}}, \] then \[ f(n,m)=(1+o(1)){n\over{s_0(m)}} , \] where \(o(1)\) tends to 0, uniformly in \(m\), as \(n\) tends to infinity.'' In the proof, a finite addition theorem (that is, a theorem concerning set addition in \(\{1,2,\dots,n\}\)) of \textit{A. Sárközy} [``Finite addition theorems. II'', J. Number Theory 48, No. 2, 197--218 (1994; Zbl 0808.11011)] is used. The authors apply the same method to prove that if \(A\) is a ``big'' subset of \(\{1,2,\dots,n\}\) such that no subset \(B\) of \(A\) is such that \(\sum_{b\in B}b=m,\) then \(A\) contains a ``big'' arithmetic progression.