Lewko's blog

Restriction estimates for the paraboloid over finite fields

Posted in Fourier Analysis, math.CA, Paper by Mark Lewko on September 19, 2010

Allison and I recently completed a paper titled Restriction estimates for the paraboloid over finite fields. In this note we obtain some endpoint restriction estimates for the paraboloid over finite fields.

Let S denote a hypersurface in \mathbb{R}^{n} with surface measure d\sigma. The restriction problem for S is to determine for which pairs of (p,q) does there exist an inequality of the form

\displaystyle ||\hat{f}||_{L^{p'}(S,d\sigma)} \leq C ||f||_{L^{q'}(\mathbb{R}^n)}.

We note that the left-hand side is not necessarily well-defined since we have restricted the function \hat{f} to the hypersurface S, a set of measure zero in  \mathbb{R}^{n}. However, if we can establish this inequality for all Schwartz functions f, then the operator that restricts \hat{f} to S (denoted by \hat{f}|_{S}), can be defined whenever f \in L^{q}. In the Euclidean setting, the restriction problem has been extensively studied when S is a sphere, paraboloid, and cone. In particular, it has been observed that restriction estimates are intimately connected to questions about certain partial differential equations as well as problems in geometric measure theory such as the Kakeya conjecture. The restriction conjecture states sufficient conditions on (p,q) for the above inequality to hold. In the case of the sphere and paraboloid, the question is open in dimensions three and higher.

In 2002 Mockenhaupt and Tao initiated the study of the restriction phenomena in the finite field setting. Let us introduce some notation to formally define the problem in this setting. We let F denote a finite field of characteristic p >2. We let S^{1} denote the unit circle in \mathbb{C} and define e: F \rightarrow S^1 to be a non-principal character of F. For example, when F = \mathbb{Z}/p \mathbb{Z}, we can set e(x) := e^{2\pi i x/p}. We will be considering the vector space F^n and its dual space F_*^n. We can think of F^n as endowed with the counting measure dx which assigns mass 1 to each point and F_*^n as endowed with the normalized counting measure d\xi which assigns mass |F|^{-n} to each point (where |F| denotes the size of F, so the total mass is equal to 1 here).

For a complex-valued function f on F^n, we define its Fourier transform \hat{f} on F_*^n by:

\displaystyle \hat{f}(\xi) := \sum_{x \in F^n} f(x) e(-x \cdot \xi).

For a complex-valued function g on F_*^n, we define its inverse Fourier transform g^{\vee} on F^n by:

\displaystyle g^{\vee}(x) := \frac{1}{|F|^n} \sum_{\xi \in F_*^n} g(\xi) e(x\cdot \xi).

It is easy to verify that (\hat{f})^\vee = f and \widehat{(g^{\vee})} = g.

We define the paraboloid \mathcal{P} \subset F_*^n as: \mathcal{P} := \{(\gamma, \gamma \cdot \gamma): \gamma \in F_*^{n-1}\}. This is endowed with the normalized “surface measure” d\sigma which assigns mass |\mathcal{P}|^{-1} to each point in \mathcal{P}. We note that |\mathcal{P}| = |F|^{n-1}.
For a function f: \mathcal{P} \rightarrow \mathbb{C}, we define the function (f d\sigma)^\vee: F^n \rightarrow \mathbb{C} as follows:

\displaystyle (f d\sigma)^\vee (x) := \frac{1}{|\mathcal{P}|} \sum_{\xi \in \mathcal{P}} f(\xi) e(x \cdot \xi).

For a complex-valued function f on F^n and q \in [1, \infty), we define

\displaystyle ||f||_{L^q(F^n, dx)} := \left( \sum_{x \in F^n} |f(x)|^q \right)^{\frac{1}{q}}.

For a complex-valued function f on \mathcal{P}, we similarly define

\displaystyle ||f||_{L^q(\mathcal{P},d\sigma)} := \left( \frac{1}{|\mathcal{P}|} \sum_{\xi \in \mathcal{P}} |f(\xi)|^q \right)^{\frac{1}{q}}.

Now we define a restriction inequality to be an inequality of the form

\displaystyle ||\hat{f}||_{L^{p'}(S,d\sigma)} \leq \mathcal{R}(p\rightarrow q) ||f||_{L^{q'}(\mathbb{R}^n)},

where \mathcal{R}(p\rightarrow q) denotes the best constant such that the above inequality holds. By duality, this is equivalent to the following extension estimate:

||(f d\sigma)^\vee||_{L^q(F^n, dx)} \leq \mathcal{R}(p\rightarrow q) ||f||_{L^p(\mathcal{P},d\sigma)}.

We will use the notation X \ll Y to denote that quantity X is at most a constant times quantity Y, where this constant may depend on the dimension n but not on the field size, |F|. For a finite field F, the constant \mathcal{R}(p\rightarrow q) will always be finite. The restriction problem in this setting is to determine for which (p,q) can we upper bound \mathcal{R}(p\rightarrow q) independently of |F| (i.e. for which (p,q) does \mathcal{R}(p \rightarrow q) \ll 1 hold).

Mockenhaupt and Tao solved this problem for the paraboloid in two dimensions.  In three dimensions, we require -1 not be a square in F (without this restriction the parabaloid will contain non-trivial subspaces which lead to trivial counterexamples, but we will not elaborate on this here). For such F, they showed that \mathcal{R}(8/5+\epsilon \rightarrow 4) \ll 1 and \mathcal{R}(2 \rightarrow \frac{18}{5}+\epsilon) \ll 1 for every \epsilon>0. When \epsilon=0, their bounds were polylogarithmic in |F|. Mockenhaupt and Tao’s argument for the \mathcal{R}(8/5 \rightarrow 4) estimate proceeded by first establishing the estimate for characteristic functions. Here one can expand the L^4 norm and reduce the problem to combinatorial estimates. A well-known dyadic pigeonhole argument then allows one to pass back to general functions at the expense of a logarithmic power of |F|. Following a similar approach (but requiring much more delicate Gauss sum estimates), Iosevich and Koh proved that \mathcal{R}(\frac{4n}{3n-2}+ \epsilon \rightarrow 4) \ll 1 and \mathcal{R}(2 \rightarrow \frac{2n^2}{n^2-2n+2} + \epsilon) \ll 1 in higher dimensions (in odd dimensions some additional restrictions on F are required). Again, however, this argument incurred a logarithmic loss at the endpoints from the dyadic pigeonhole argument.

In this note we remove the logarithmic losses mentioned above. Our argument begins by rewriting the L^4 norm as ||(fd\sigma)^{\vee}||_{L^4}=||(fd\sigma)^{\vee}(fd\sigma)^{\vee}||_{L^2}^{1/2}. We then adapt the arguments of the prior papers to the bilinear variant ||(fd\sigma)^{\vee}(gd\sigma)^{\vee}||_{L^2}^{1/2} in the case that f and g are characteristic functions.

To obtain estimates for arbitrary functions f, we can assume that f is non-negative real-valued and decompose f as a linear combination of characteristic functions, where the coefficients are negative powers of two (we can do this without loss of generality by adjusting only the constant of our bound). We can then employ the triangle inequality to upper bound ||(fd\sigma)^{\vee}||_{L^4} by a double sum of terms like ||(\chi_j d\sigma)^{\vee}(\chi_k d\sigma)^{\vee}||_{L^2}^{1/2}, where \chi_i and \chi_j are characteristic functions, weighted by negative powers of two. We then apply our bilinear estimate for characteristic functions to these inner terms and use standard bounds on sums to obtain the final estimates.

Our method yields the following theorems:

Theorem For the paraboloid in 3 dimensions with -1 not a square, we have \mathcal{R}(8/5 \rightarrow 4) \ll 1 and \mathcal{R}(2 \rightarrow \frac{18}{5}) \ll 1.
Theorem For the paraboloid in n dimensions when n \geq 4 is even or when n is odd and |F| = q^m for a prime q congruent to 3 modulo 4 such that m(n-1) is not a multiple of 4, we have \mathcal{R}(\frac{4n}{3n-2} \rightarrow 4) \ll 1 and \mathcal{R}(2 \rightarrow \frac{2n^2}{n^2-2n+2}) \ll 1.

We recently learned that in unpublished work Bennett, Carbery, Garrigos, and Wright have also obtained the results in the 3-dimensional case. Their argument proceeds rather differently than ours and it is unclear (at least to me) if their argument can be extended to the higher dimensional settings.

Tagged with: ,

Sets of large doubling and a question of Rudin

Posted in Fourier Analysis, math.CA, math.CO, Paper by Mark Lewko on April 2, 2010

Update (May 2, 2010): After posting this preprint, Stefan Neuwirth informed us that Rudin’s question had been previously answered by Y. Meyers in 1968. It appears that Meyers’ construction doesn’t, however, say anything about the anti-Freiman problem. Indeed Meyers’ set (and all of its subsets) contains a B_{2}[2] set of density 1/4. Hence, the construction of a \Lambda(4) set that doesn’t contain a large B_{2}[2] set still appears to be new. A revised version of the paper has been posted reflecting this information.  Most notably, we have changed the title to “On the Structure of Sets of Large Doubling”.

Allison Lewko and I recently arXiv’ed our paper “Sets of Large Doubling and a Question of Rudin“. The paper (1) answers a question of Rudin regarding the structure of {\Lambda(4)} sets (2) negatively answers a question of O’Bryant about the existence of a certain “anti-Freiman” theorem (3) establishes a variant of the (solved) Erdös-Newman conjecture. I’ll briefly describe each of these results below.

— Structure of {\Lambda(4)} sets —

Before describing the problem we will need some notation. Let {S \subset {\mathbb Z}^d} and define {R_{h}(n)} to be the number of unordered solutions to the equation {x_{1}+\ldots + x_{h}=n} with {x_{1},\ldots,x_{h} \in S}. We say that {S} is a {B_{h}[G]} set if {R_{h}(n) \leq G} for all {n \in Z^d}. There is a similar concept with sums replaced by differences. Since this concept is harder to describe we will only introduce it in the case {h=2}. For {S \subset Z^{d}} we define {R_{2}^{\circ}(n)} to be the number of solutions to the equation {x_{1}-x_{2} = n} with {x_{1},x_{2}\in S}. If {R_{2}^{\circ}(n)\leq G} for all nonzero {n} we say that {S} is a {B_{2}^{\circ}[G]} set.

Let {S} be a subset of the integers {{\mathbb Z}^{d}}, and call {f : \mathbb{T}^{d} \rightarrow {\mathbb C}} an {S}-polynomial if it is a trigonometric polynomial whose Fourier coefficients are supported on {S} (i.e. {\hat{f}(n) = 0} if {n \in {\mathbb Z^{d}} \setminus S}). We say that {S} is a {\Lambda(p)} set (for {p>2}) if

\displaystyle ||f||_{L^p} \leq K_{p}(S) ||f||_{L^{2}} \ \ \ \ \ (1)

holds for all {S}-polynomials where the constant {K_{p}(S)} only depends on {S} and {p}. If {p} is an even integer, we can expand out the {L^{p}} norm in 1. This quickly leads to the following observation: If {S} is a {B_{h}[G]} set then {S} is also an {\Lambda(2h)} set ({h>1}, {h \in Z}). One can also easily show using the triangle inequality that the union of two {\Lambda(p)} sets is also a {\Lambda(p)} set. It follows that the finite union of {B_{h}[G]} sets is a {\Lambda(2h)} set. In 1960 Rudin asked the following natural question: Is every {\Lambda(2h)} set is a finite union of {B_{h}[G]} sets?

In this paper we show that the answer is no in the case of {\Lambda(4)} sets. In fact, we show a bit more than this. One can easily show that a {B_{2}^{\circ}[G]} set is also a {\Lambda(4)} set. Our first counterexample to Rudin’s question proceeded (essentially) by constructing a {B_{2}^{\circ}[2]} set which wasn’t the finite union of {B_{2}[G]} sets. This however raised the following variant of Rudin’s question: Is every {\Lambda(4)} set the mixed finite union of {B_{2}[G]} and {B_{2}^{\circ}[G]} sets? We show that the answer to this question is no as well. To do this we construct a {B_{2}[G]} set, A, which isn’t a finite union of {B_{2}^{\circ}[G]} sets, and a {B_{2}^{\circ}[G]} set, {B}, which isn’t the finite union of {B_{2}[G]} sets. We then consider the product set {S= A \times B \subset Z^{2}} which one can prove is a {\Lambda(4)} subset of {Z^{2}}. It isn’t hard to deduce from this that {S} is a {\Lambda(4)} subset of {Z^2} that isn’t a mixed finite union of {B_{2}[G]} and {B_{2}^{\circ}[G]} sets. Moreover, one can (essentially) map this example back to {Z} while preserving all of the properties stated above. Generalizing this further, we show that there exists a {\Lambda(4)} set that doesn’t contain (in a sense that can be made precise) a large {B_{2}[G]} or {B_{2}^{\circ}[G]}. This should be compared with a related theorem of Pisier which states that every Sidon set contains a large independent set (it is conjectured that a Sidon set is a finite union of independent sets, however this is open).

We have been unable to extend these results to {\Lambda(2h)} sets for {h>2}. Very generally, part of the issue arises from the fact that the current constructions hinges on the existence of arbitrary large binary codes which can correct strictly more than a {1/2} fraction of errors. To modify this construction (at least in a direct manner) to address the problem for, say, {\Lambda(6)} sets it appears one would need arbitrary large binary codes that can correct strictly more than a {2/3} fraction of errors. However, one can show that such objects do not exist.

— Is there an anti-Freiman theorem? —

 Let {A} be a finite set of integers and denote the sumset of {A} as {A+A = \{a+b : a,b \in A\}}. A trivial inequality is the following

\displaystyle 2|A|-1 \leq |A+A| \leq {|A| \choose 2}.

In fact, it isn’t hard to show that equality only occurs on the left if {A} is an arithmetic progression and only occurs on the right if {A} is a {B_{2}[1]} set. A celebrated theorem of Freiman states that if {|A+A| \approx |A|} then {A} is approximately an arithmetic progression. More precisely, if {A} is a finite set {A \subseteq {\mathbb Z}} satisfying {|A+A| \leq \delta |A|} for some constant {\delta}, then {A} is contained in a generalized arithmetic progression of dimension {d} and size {c |A|} where {c} and {d} depend only on {\delta} and not on {|A|}.

It is natural to ask about the opposite extreme: if {|A+A| \geq \delta |A|^2}, what can one say about the structure of {A} as a function only of {\delta}? A first attempt might be to guess that if {|A+A|\geq \delta |A|^2} for some positive constant {\delta}, then {A} can be decomposed into a union of {k} {B_2[G]} sets where {k} and {G} depend only on {\delta}. This is easily shown to be false. For example, one can start with a {B_2[1]} of {n} elements contained in the interval {[n+1,\infty)} and take its union with the arithmetic progression {[1,n]}. It is easy to see that {|A+A| \geq \frac{1}{10} |A|^2} regardless of {n}. However, the interval {[1,n]} cannot be decomposed as the union of {k} {B_2[G]} sets with {k} and {G} independent of {n}.

There are two ways one might try to fix this problem: first, we might ask only that {A} contains a {B_2[G]} set of size {\delta' |A|}, where {\delta'} and {G} depend only on {\delta}. (This formulation was posed as an open problem by O’Bryant here). Second, we might ask that {|A'+A'|\geq \delta |A'|^2} hold for all subsets {A' \subseteq A} for the same value of {\delta}. Either of these changes would rule out the trivial counterexample given above. In this paper we show that even applying both of these modifications simultaneously is not enough to make the statement true. We provide a sequence of sets {A \subseteq {\mathbb Z}} where {|A'+A'|\geq \delta |A'|^2} holds for all of their subsets for the same value of {\delta}, but if we try to locate a {B_2[G]} set, {B}, of density {1/k} in {A} then {k} must tend to infinity with the size of {A}. As above, our initial construction of such a sequence of {A}‘s turned out to be {B^\circ_2[2]} sets. This leads us to the even weaker anti-Freiman conjecture:

(Weak Anti-Freiman) Suppose that {A \subseteq {\mathbb Z}} satisfies {|A'+A'|\geq \delta |A'|^2} and {|A'-A'|\geq \delta |A'|^2} for all subsets {A' \subseteq A}. Then {A} contains either a {B_2[G]} set or a {B^\circ_2[G]} set of size {\geq \delta' |A|}, where {G} and {\delta'} depend only on {\delta}.

We conclude by showing that even this weaker conjecture fails. The constructions are the same as those used in the {\Lambda(4)} results above. The two problems are connected by the elementary observation that if {A'} is a subset of a {\Lambda(4)} set {A} then {|A'+A'|\geq \delta |A'|^2} holds where {\delta} only depends on the {\Lambda(4)} constant {K_{4}(A)} of the set {A}.

— A variant of the Erdös-Newman conjecture —

In the early 1980’s Erdös and Newman independently made the following conjecture: For every {G} there exists a {B_{2}[G]} that isn’t a finite union of {B_{2}[G']} sets for any {G'\leq G-1}. This conjecture was later confirmed by Erdös for certain values of {G} using Ramsey theory, and finally resolved completely by Nešetřil and Rödl using Ramsey graphs. One further application of our technique is the following theorem which can be viewed as an analog of the Erdös-Newman problem with the roles of the union size and {G} reversed.

Theorem 1 For every {k >1} there exists a union of k {B_{2}[1]} sets that isn’t a finite union of {k'\leq k-1} {B_{2}[G]} sets for any {G}.

Thin sets of primes and the Goldbach property

Posted in Fourier Analysis, math.NT, Uncategorized by Mark Lewko on November 19, 2009

As is well known, Goldbach conjectured that every even positive integer (greater than 2) is the sum of two primes. While this is a difficult open problem, progress has been made from a number of different directions. Perhaps most notably, Chen has shown that every sufficiently large even positive integer is the sum of a prime and an almost prime (that is an integer that is a product of at most two primes). In another direction, Montgomery and Vaughan have shown that if {E} is the set of positive even integers that cannot be expressed as the sum of two primes then

 \displaystyle |[0,N]\cap E| \leq |N|^{1-\delta}

for some positive constant {\delta>0}. This is stronger than the observation (which was made much earlier) that almost every positive integer can be expressed as the sum of two primes. In this post we’ll be interested in sets of integers with the property that most integers can be expressed as the sum of two elements from the set. To be more precise we’ll say that a set of positive integers {S} has the Goldbach property (GP) if the sumset {S+S} consists of a positive proportion of the integers. From the preceding discussion we have that the set of primes has the GP. (This discussion is closely related to the theory of thin bases.)

A natural first question in investigating such sets would be to ask how thin such a set can be. Simply considering the number of possible distinct sums, the reader can easily verify that a set {S} (of positive integers) with the GP must satisfy

 \displaystyle \liminf_{N\rightarrow\infty} \frac{[0,N]\cap S}{\sqrt{N}} > 0.

This is to say that a set of positive integers with the GP must satisfy {[0,N]\cap S \gg \sqrt{N}} for all large {N}. Recall that the prime number theorem gives us that {|[0,N]\cap\mathcal{P}| \approx N/\ln(N)} for the set of primes {\mathcal{P}}. Thus the primes are much thicker than a set with the GP needs to be (at least from naive combinatorial considerations).

Considering this, one might ask if there is a subset of the primes with the GP but having significantly lower density in the integers. I recently (re)discovered that the answer to this question is yes. In particular we have that

 Theorem 1 There exists a subset of the primes {\mathcal{Q}} such that {\mathcal{Q}+\mathcal{Q}} has positive density in the integers and

\displaystyle \limsup_{N\rightarrow\infty} \frac{[0,N]\cap \mathcal{Q}}{\sqrt{N}} < \infty.


Tagged with: ,

The sharp large sieve inquality

Posted in expository, Fourier Analysis, math.NT, Uncategorized by Mark Lewko on August 31, 2009

This is the first post in a short sequence related to the large sieve inequality and its applications. In this post I will give a proof of the sharp (analytic) large sieve inequality. While the main result of this post is a purely analytic statement, one can quickly obtain a large number of arithmetic consequences from it. The most famous of these is probably a theorem of Brun which states that the sum of the reciprocals of the twin primes converges. I will present this and other arithmetic applications in a following post. This post will focus on proving the sharp (analytic) large sieve inequality. Much of the work in this post could be simplified if we were willing to settle for a less than optimal constant in the inequality. This would have little impact on the the arithmetic applications, but we’ll stick to proving the sharp form of this inequality (mostly for my own benefit). I should point out that there is an alternate approach to this inequality, via Selberg-Buerling extremal functions, which gives an even sharper result.  In particular, using this method one can replace the N+\delta^{-1} in Theorem 1 below by N-1+\delta^{-1}.  We will not pursue this further here, however.  Much of this post will follow this paper of Montgomery, however I have made a few attempts at simplifying the  presentation, most notably I have eliminated the need to use properties of skew-hermitian forms in the proof of the sharp discrete Hilbert transform inequality.


Fefferman’s ball multiplier counterexample

Posted in expository, Fourier Analysis, math.CA by Mark Lewko on August 4, 2009

In the previous post we saw the connection between the ball multiplier {S_{1}} and spherical {L^{p}} convergence of Fourier transforms. Recall that the operator {S_{1}} is defined in {d} dimensions by the relation

\displaystyle \widehat{S_{1}f}(\xi) = \chi_{B}(\xi)\hat{f}(\xi)

where {B} denotes the {d}-dimensional unit ball.  The focus of this post will be to prove the following result

Theorem 1 (Fefferman, 1971) The operator {S_{1}} is not bounded on {L^{p}(\mathbb{R}^d)} if {d>1} and {p\neq2}.



L^{p} convergence of Fourier transforms

Posted in expository, Fourier Analysis, math.CA by Mark Lewko on August 3, 2009

Let {\chi_{B}(x)} denote the characteristic function of the unit ball {B} in {d} dimensions. For a smooth function of rapid decay, say {f}, we can define the linear operator {S_{1}} by the relation

 \displaystyle \widehat{S_{1}f}(\xi) = \chi_{B}(\xi)\hat{f}(\xi)

where {\hat{f}(\xi)} denotes the Fourier transform of {f}, as usual. This operator naturally arises in problems regarding the convergence of Fourier transforms (which we discuss below). A fundamental problem regarding this operator is to determine for which values of {p} and {d} we can extended {S_{1}} to a bounded linear operator on {L^{p}(\mathbb{R}^d)}. The {1}-dimensional case of this problem was settled around 1928 by M. Riesz, however the higher dimensional cases proved to be much more subtle. In 1954 Herz showed that 2d/(d+1) <p< 2d/(d-1) was a necessary condition for the boundedness of S_{1}, and sufficient in the special case of radial functions. It was widely conjectured that these conditions were also sufficient in general (this was known as the disc conjecture). However,  in 1971 Charles Fefferman proved, for {d\geq2}, that {S_{1}} does not extend to a bounded operator on any {L^p} space apart from the trivial case when {p=2} (which follows from Parseval’s identity). Recently, I needed to look at Fefferman’s proof and decided to spend some time trying to figure out what is really going on. I will attempt to give a motivated account of Fefferman’s result, in a two post presentation. In this (the first) post I will describe the motivation for the problem, as well as develop some tools needed in the proof. The problems discussed here were first considered in the context of Fourier series (i.e. functions on the {d}-dimensional torus {\mathbb{T}^d}). It turns out, however, that these problems are slightly easier to address on Euclidean space, and are equivalent thanks to a result of de Leeuw. In light of this, we will work exclusively on {\mathbb{R}^d}. (more…)