On the distribution of sums of residues
HTML articles powered by AMS MathViewer
- by Jerrold R. Griggs PDF
- Bull. Amer. Math. Soc. 28 (1993), 329-333 Request permission
Abstract:
We generalize and solve the ${\bmod \;q}$]> analogue of a problem of Littlewood and Offord, raised by Vaughan and Wooley, concerning the distribution of the ${2^n}$ sums of the form ${\sum _{i = 1}^n{\varepsilon _i}{a_i}}$, where each ${\varepsilon _i}$ is 0 or 1. For all q, n, k we determine the maximum, over all reduced residues ${a_i}$ and all sets P consisting of k arbitrary residues, of the number of these sums that belong to P.References
- Ian Anderson, Combinatorics of finite sets, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1987. MR 892525
- N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskunde (2) 23 (1951), 191–193. MR 0043115
- P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, DOI 10.1090/S0002-9904-1945-08454-7
- P. Frankl and Z. Füredi, Solution of the Littlewood-Offord problem in high dimensions, Ann. of Math. (2) 128 (1988), no. 2, 259–270. MR 960947, DOI 10.2307/1971442
- Curtis Greene and Daniel J. Kleitman, Proof techniques in the theory of finite sets, Studies in combinatorics, MAA Stud. Math., vol. 17, Math. Assoc. America, Washington, D.C., 1978, pp. 22–79. MR 513002
- Jerrold R. Griggs, The Littlewood-Offord problem: tightest packing and an $M$-part Sperner theorem, European J. Combin. 1 (1980), no. 3, 225–234. MR 593993, DOI 10.1016/S0195-6698(80)80006-0
- Jerrold R. Griggs, Saturated chains of subsets and a random walk, J. Combin. Theory Ser. A 47 (1988), no. 2, 262–283. MR 930956, DOI 10.1016/0097-3165(88)90021-0
- Gy. Katona, On a conjecture of Erdős and a stronger form of Sperner’s theorem, Studia Sci. Math. Hungar. 1 (1966), 59–63. MR 205864
- G. O. H. Katona, Families of subsets having no subset containing another one with small difference, Nieuw Arch. Wisk. (3) 20 (1972), 54–67. MR 304182
- Daniel J. Kleitman, On a lemma of Littlewood and Offord on the distribution of certain sums, Math. Z. 90 (1965), 251–259. MR 184865, DOI 10.1007/BF01158565
- Daniel J. Kleitman, On a lemma of Littlewood and Offord on the distributions of linear combinations of vectors, Advances in Math. 5 (1970), 155–157 (1970). MR 265923, DOI 10.1016/0001-8708(70)90038-1
- D. J. Kleitman, Some new results on the Littlewood-Offord problem, J. Combinatorial Theory Ser. A 20 (1976), no. 1, 89–113. MR 392592, DOI 10.1016/0097-3165(76)90080-7
- J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation. III, Rec. Math. [Mat. Sbornik] N.S. 12(54) (1943), 277–286 (English, with Russian summary). MR 0009656
- Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), no. 1, 544–548 (German). MR 1544925, DOI 10.1007/BF01171114
- R. C. Vaughan and T. D. Wooley, On a problem related to one of Littlewood and Offord, Quart. J. Math. Oxford Ser. (2) 42 (1991), no. 167, 379–386. MR 1120998, DOI 10.1093/qmath/42.1.379
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 28 (1993), 329-333
- MSC: Primary 11P83; Secondary 11B50
- DOI: https://doi.org/10.1090/S0273-0979-1993-00382-3
- MathSciNet review: 1183998