Erdős, Pál On a lemma of Littlewood and Offord. (English) Zbl 0063.01270 Bull. Am. Math. Soc. 51, 898-902 (1945). From the text: Recently, J. E. Littlewood and A. C. Offord [Mat. Sb., N. Ser. 12(54), 277–286 (1943; Zbl 0061.01801)] proved the following lemma: Let \(x_1,x_2,\ldots,x_n\) be complex numbers with \(| x_i|\geq 1\). Consider the sums \(\sum_{k=1}^n \varepsilon_k x_k\), where the \(\varepsilon_k\) are \(\pm 1\). Then the number of the sums \(\sum_{k=1}^n \varepsilon_k x_k\) which fall into a circle of radius \(r\) is not greater than \(cr2^n(\log n)n^{-1/2}\). In the present paper we are going to improve this to \(cr2^nn^{-1/2}\).The case \(x_i = 1\) shows that the result is best possible as far as the order is concerned.From Theorem 1 we immediately obtain the following corollary.Corollary. Let \(r\) be any integer. Then the number of sums \(\sum_{k=1}^n \varepsilon_k x_k\) which fall in the interior of any interval of length \(2r\) is less than \(rC_{n,m}\).Theorem 2. Let the \(x_i\) be complex numbers, \(| x_i|\geq 1\). Then the number of sums \(\sum_{k=1}^n \varepsilon_k x_k\) which fall in the interior of an arbitrary circle of radius \(r\) (\(r\) integer) is less than \(crC_{n,m} < c_1 r2^n n^{-1/2}\).Our corollary to Theorem 1 is not best possible. We prove:Theorem 3. Let \(r\) be any integer, the \(x_i\) real, \(| x_i|\geq 1\). Then the number of sums \(\sum_{k=1}^n \varepsilon_k x_k\) which fall into the interior of any interval of length \(2r\) is not greater than the sum of the \(r\) greatest binomial coefficients (belonging to \(n\)).Clearly by choosing \(x_i = 1\) we see that this theorem is best possible.The same argument as used in Theorem 1 shows that Theorem 3 will be an immediate consequence of the following theorem.Theorem 4. Let \(A_1, A_2, \ldots, A_u\) be subsets of \(n\) elements such that no two subsets \(A_i\) and \(A_j\) satisfy \(A_i\supset A_j\) and \(A_i-A_j\) contains more than \(r-1\) elements. Then \(u\) is not greater than the sum of the \(r\) largest binomial coefficients.Our proof will be very similar to that of E. Sperner [Math. Z. 27, 544–548 (1928; JFM 54.0090.06)].By more complicated arguments we can prove the following theorem.Theorem 5. Let \(A_1, A_2, \ldots, A_u\) be subsets of \(n\) elements such that there does not exist a sequence of \(r+1\) \(A\)’s each containing the previous one. Then \(u\) is not greater than the sum of the \(r\) largest binomial coefficients.This is proved using a lemma on graph theory and a theorem of Menger. Cited in 10 ReviewsCited in 213 Documents MSC: 30B10 Power series (including lacunary series) in one complex variable 30B20 Random power series in one complex variable 60C05 Combinatorial probability 05A05 Permutations, words, matrices Citations:Zbl 0061.01801; JFM 54.0090.06 PDFBibTeX XMLCite \textit{P. Erdős}, Bull. Am. Math. Soc. 51, 898--902 (1945; Zbl 0063.01270) Full Text: DOI Online Encyclopedia of Integer Sequences: Triangle T read by rows: T(n, k) = Sum_{i=1..k} binomial(n, floor((n-k)/2)+i).