On a conjecture of Alon
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.
- On representation of r-th powers by subset sums
- Squares in sumsets
- Subset sums
- Publication:3484902
- A construction for sets of integers with distinct subset sums
- Difference sets and shifted primes
- scientific article; zbMATH DE number 3721037
- On sums of subsets of a set of integers
- scientific article; zbMATH DE number 3342002
- On subset sums of \(r\)-sets
- A Structural Approach to Subset-Sum Problems
- Classification theorems for sumsets modulo a prime
- Finite addition theorems. I
- Finite addition theorems. II
- Finite and infinite arithmetic progressions in sumsets
- scientific article; zbMATH DE number 4177149 (Why is no real title available?)
- scientific article; zbMATH DE number 97087 (Why is no real title available?)
- scientific article; zbMATH DE number 568794 (Why is no real title available?)
- Integer Sum Sets Containing Long Arithmetic Progressions
- Long arithmetic progressions in sum-sets and the number x-sum-free sets
- Long arithmetic progressions in sumsets: Thresholds and bounds
- On Certain Sets of Integers
- On representation of r-th powers by subset sums
- On sums of subsets of a set of integers
- On two additive problems
- Subset sums
- Subset sums modulo a prime
This page was built for publication: On a conjecture of Alon
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q841263)
