Abstract
Forr≧2 letp(n, r) denote the maximum cardinality of a subsetA ofN={1, 2,...,n} such that there are noB⊂A and an integery with\(\mathop \sum \limits_{b \in B} b = y^r \) b=y r. It is shown that for anyε>0 andn>n(ε), (1+o(1))21/(r+1) n (r−1)/(r+1)≦p(n, r)≦n ɛ+2/3 for allr≦5, and that for every fixedr≧6,p(n, r)=(1+o(1))·21/(r+1) n (r−1)/(r+1) asn→∞. Letf(n, m) denote the maximum cardinality of a subsetA ofN such that there is noB⊂A the sum of whose elements ism. It is proved that for 3n 6/3+ɛ≦m≦n 2/20 log2 n andn>n(ε), f(n, m)=[n/s]+s−2, wheres is the smallest integer that does not dividem. A special case of this result establishes a conjecture of Erdős and Graham.
Similar content being viewed by others
References
N. Alon, Subset sums,J. Number Theory,27 (1987), 196–205.
P.Erdős and G.Freiman, On two additive problems,J. Number Theory, to appear.
P.Erdős, Some problems and results on combinatorial number theory,Proc. First China Conference in Combinatorics (1986),to appear.
E.Lipkin, On representation ofr-powers by subset sums,Acta Arithmetica, submitted.
J. Olson, An additive theorem modulop, J. Combinatorial Theory 5 (1968), 45–52.
E. C. Titchmarsh,Introduction to the theory of Fourier integrals, Oxford at the Clarendon Press, London, 1948, p. 177.
Author information
Authors and Affiliations
Additional information
Research supported in part by Allon Fellowship, by a Bat-Sheva de Rothschild Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.