On a lemma of Littlewood and Offord.(English)Zbl 0063.01270
From the text: Recently,J. E. Littlewood andA. 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 ofE. 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.
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 ofE. 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.
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 |
