Extensions to the method of multiplicities, with applications to kakeya sets and mergers

Abstract

We extend the "method of multiplicities" to get the following results, of interest in combinatorics and randomness extraction. (i) We show that every Kakeya set in (Formula presented.), the n-dimensional vector space over the finite field on q elements, must be of size at least qn/2n. This bound is tight to within a 2 + o(1) factor for every n as q → ∞. (ii) We give improved "randomness mergers": Mergers are seeded functions that take as input ℓ (possibly correlated) random variables in {0, 1}N and a short random seed and output a single random variable in {0, 1}N that is statistically close to having entropy (1 δ)·N when one of the ℓ input variables is distributed uniformly. The seed we require is only (1/δ) · log ℓ-bits long, which significantly improves upon previous construction of mergers. (iii) We give improved randomness extractors, based on our improved mergers. Specifically, we show how to construct randomness extractors that use logarithmic length seeds while extracting 1 o(1) fraction of the min-entropy of the source. Previous results could extract only a constant fraction of the entropy while maintaining logarithmic seed length. The "method of multiplicitie" was used in prior work to analyze combinatorial parameters of "algebraically nice" subsets of vector spaces over finite fields. The method works by constructing somewhat low-degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involves using the "algebraic niceness" to show that the interpolating polynomial also vanishes on some points outside the subset. It then uses simple bounds on the number of zeroes of low-degree polynomials to bound the combinatorial parameter of interest. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses. To develop the extended method of multiplicities, we provide a number of basic technical results about multiplicity of zeroes of polynomials that may be of general use. For instance, we strengthen the Schwartz. Zippel lemma to show that the expected multiplicity of zeroes of a nonzero degree d polynomial at a random point in Sn, for any finite subset S of the underlying field, is at most d/|S| (a fact that does not seem to have been noticed in the CS literature before).