On the distribution of sums of residues

Griggs, Jerrold R.

doi:10.1090/S0273-0979-1993-00382-3

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