×

A lattice point problem and additive number theory. (English) Zbl 0838.11020

Let \(f(n,d)\) denote the minimal number such that every set of \(f(n,d)\) lattice points in a \(d\) dimensional space contains \(n\) points whose centroid (mean) is also a lattice point. Here the estimate \(f(n,d) < (cd \log d)^dn\) is proved, a sharp one for fixed \(d\) and \(n \to \infty\). The proof combines Plünnecke’s ideas, expansion properties of graphs with given eigenvalues, and classical exponential sums to evaluate the eigenvalues of certain Cayley graphs.

MSC:

11B75 Other combinatorial number theory
11P99 Additive number theory; partitions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon: Subset sums,J. Number Theory 27 (1987), 196-205. · Zbl 0622.10042 · doi:10.1016/0022-314X(87)90061-8
[2] N. Alon, andM. Dubiner:Zero-sum sets of prescribed size, in: Combinatorics, Paul Erdös is Eighty, Bolyai Society, Mathematical Studies, Keszthely, Hungary, 1993, 33-50.
[3] N. Alon, R. M. Karp, D. Peleg, andD. B. West: A graph-theoretic game and its application to thek-servers problem,SIAM J. Comp., to appear.
[4] N. Alon, andV. D. Milman: ?1, isoperimetric inequalities for graphs and superconcentrators,J. Comb. Theory, Ser. B,38 (1985), 73-88. · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9
[5] N. Alon, andJ. H. Spencer:The probabilistic method, Wiley, 1991. · Zbl 1333.05001
[6] T. C. Brown andJ. C. Buhler: A density version of a geometric Ramsey theorem,J. Comb. Theory, Ser. A,32 (1982), 20-34. · Zbl 0476.51008 · doi:10.1016/0097-3165(82)90062-0
[7] J. L. Brenner: Problem 6298,Amer. Math. Monthly,89 (1982), 279-280. · doi:10.2307/2320242
[8] P. Erd?s, A. Ginzburg, andA. Ziv: Theorem in the additive number theory,Bull. Research Council Isreal 10F (1961), 41-43.
[9] P. Erd?s andH. Heilbronn: On the addition of residue classes modp, Acta Arith.,9 (1964), 149-159.
[10] P. Frankl, R. L. Graham, andV. Rödl: On subsets of abelian groups with no 3-term arithmetic progression,J. Comb. Theory Ser. A,45 (1987), 157-161. · Zbl 0613.10043 · doi:10.1016/0097-3165(87)90053-7
[11] H. Furstenberg, andY. Katznelson: An ergodic Szemerédi theorem for IP-systems and combinatorial theory,J. d’Analyse Math.,45 (1985), 117-168. · Zbl 0605.28012 · doi:10.1007/BF02792547
[12] H. Harborth: Ein Extremalproblem für Gitterpunkte,J. Reine Angew. Math.,262/263 (1973), 356-360. · Zbl 0268.05008 · doi:10.1515/crll.1973.262-263.356
[13] A. Kemnitz: On a lattice point problem,Ars Combinatoria,16b (1983), 151-160. · Zbl 0539.05008
[14] B. Leeb, andC. Stahlke: A problem on lattice points,Crux Mathematicorum 13 (1987), 104-108.
[15] L. H. Loomis, andH. Whitney: An inequality related to the isoperimetric inequality,Bulletin AMS,55 (1949), 961-962. · Zbl 0035.38302 · doi:10.1090/S0002-9904-1949-09320-5
[16] L. Lovász:Combinatorial Problems and Exercises, North Holland, Amsterdam, 1979, Problem 11.8. · Zbl 0439.05001
[17] J. E. Olson: An addition theorem modulop, J. Comb. Theory 5 (1968), 45-52. · Zbl 0174.05202 · doi:10.1016/S0021-9800(68)80027-4
[18] H. Plünnecke: Eine zahlentheoretische Anwendung der Graphentheorie,J. Reine Angew. Math.,243 (1970), 171-183. · Zbl 0199.36701 · doi:10.1515/crll.1970.243.171
[19] I. Z. Ruzsa: An application of graph theory to additive number theory,Scientia,3 (1989), 97-109. · Zbl 0743.05052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.