Research

I work in the intersection between analysis, combinatorics and number theory: the problems I have worked on have a (sometimes admittedly faint) number theoretic flavour while the techniques I use are usually combinatorial.

In the paragraphs below I aim to motivate and describe some results I have obtained, often in collaboration with others. This is not intended to be a research statement, but rather a gentle introduction. A more detailed account can be found in the introduction of the various papers.

I would like to acknowledge the support of the National Science Foundation via Award 1500984 of the Division of Mathematical Sciences.

 

1. Additive Number Theory

The bulk of my publications fits in this category. My primary interest is to get upper bounds on the growth of sumsets in commutative groups.

Given sets \(A,B\) in the ambient group their sumset $A+B$ is defined as \[A+B = \{a+b : a\in A, b\in B\}.\] Higher sumsets like $A+B_1+B_2$ in the expected way $A+B_1+B_2 = (A+B_1)+B_2.$ When the same set $ B$ is added $ h$ times to $ A$ it is customary to write the resulting sumset as $ A+hB.$

The question of how large $ |A+hB|$ may be is easy as $ |A+hB| \leq |A|\, |hB| \leq |A| \binom{|B|+h-1}{h}.$ It is far more interesting, both from a theoretical point of view and also for application to other problems, to obtain an upper bound in terms of $ |A|$ and the ratio $ \alpha := \frac{|A+B|}{|A|},$ which measures how much $A$ grows under addition by $B.$

The most fundamental result in this direction is due to Helmut Plünnecke who showed over forty years ago that there is a non-empty subset $ \emptyset \neq X \subseteq A $ such that $|X + hB| \leq \alpha^h |X|.$ Imre Ruzsa has used the inequality repeatedly showcasing its strength.

I have studied Plünnecke's inequality and have come up with two new proofs: one that builds on Plünnecke's original graph theoretic argument and another more direct that is presented very eloquently here. I have also worked on the noncommutative setting, where it is not clear whether an analogue of Pünnecke's inequality holds. The important special case when $ A=B$ was settled by Terence Tao, whose proof I subsequently simplified.

Plünnecke's inequality bounds the growth of a suitably chosen subset $ X$ of $ A$ under repeated addition by $ B$. It does not bound the growth of the whole of $ A$. Ruzsa has achieved this and showed $ |A+hB| \leq \alpha^h |A|^{2-1/h}.$ The exponents of $ \alpha$ and $ |A|$ are sharp.

I improved Ruzsa's bound by introducing a further dependence on $ h:$ $$|A+hB| \leq \frac{\alpha^h}{h^2} |A|^{2-1/h}.$$ The key improvement is that the new upper bound is submultiplicative with respect to Cartesian products. This is largely due to the fact that the same set is added repeatedly to $ A$. The dependence on $ h$ can probably be improved. I wouldn't be surprised if the correct bound is of the form $ |A+hB| \leq \alpha^h |A|^{2-1/h} / h^{h+1}.$

Proving a submultiplicative Plünnecke inequality would lead to an improvement in the above problem. It seems likely that the extremal case occurs when $ A = B$ (in this seting the subset $X$ can be taken to be $A$) is a set of distinct generators of a free commutative group. I have no idea how to prove this or even obtain any type of submultiplicative upper bound on $ |X+hB|.$

The case when different sets are added to $A$ is somewhat different. In this case one is looking for an upper bound on $ |A+B_1+\dots+B_h|$ in terms of $ |A|$ and the quantities $ \alpha_i := \frac{|A+B_i|}{|A|}$ for $ i=1,\dots,h.$ Ruzsa's method still applies and gives: $$ |A+B_1+\dots+B_h| \leq \alpha_1\dots\alpha_h |A|^{2-1/h}.$$ In joint work with Brendan Murphy and Eyvi Palsson we managed to improve the bound to $$|A+B_1+\dots+B_h| \leq \frac{c_h}{h} \alpha_1\dots\alpha_h\, |A|^{2-1/h}\,, \mbox{ where $c_h = \left( 1 - \frac{1}{h} \right)^{h-1}$.}$$

Note that $ e^{-1} \leq c_h \leq 1/2$ for all $h\geq 2$ and that $ \frac{c_h}{h}$ behaves roughly like $ \frac{e^{-1}}{h}.$

The bound is best possible as some examples essentially due to Ruzsa demonstrate. To the best of my knowledge this is the only instance of a similar problem where the correct dependence on all the parameters has been determined.

The appearance of $h$ in the numerator has to do with what one might call the ''geometry'' of the problem. Setting $B_i=B$ for all $i=1,\dots,h$ does not yield the bound for $|A+hB|$ stated above. The additional factor of $1/h$ comes from exploiting the fact that the same set is added repeatedly to $A.$
 

2. Sum-product Phenomena in Finite Fields

A question studied in various contexts by Alex Iosevich and his coauthors is becoming one of my favourites. Given a set $A$ in a field, how large can the following set obtained from sums of products of elements of $A$ be \[ AA+AA = \{ab + cd : a,b,c,d \in A\}? \] Note that $AA+AA$ is the set of dot products determined by $A \times A$.

When $A \subseteq \mathbb{F}_q$ is a set in a finite field with $q$ elements, Iosevich and Hart have shown that $|AA+AA| > q/2$ provided that $|A|>q^{2/3}$. An ambitious goal is to improve the exponent of $q$ appearing in the lower bound condition on $|A|$. I have obtained a couple of partial results in this direction.

1. Suppose $|A|^2 |AA^{-1}| >q^2$. There exists $a,b \in A$ such that $|aA+bA|>q/2$. Here $AA^{-1} =\{ab^{-1}: a,b \in A\}$ is the set of directions determined by $A \times A \subseteq \mathbb{F}_q^2$. This conditional improvement of the Hart and Iosevich result unfortunately tells us nothing about approximate multiplicative subgroups in $\mathbb{F}_q^*$, which in my opinion are extremal.

2. When $|A|> q^{1/2}$ there exist $a,b,c,d \in A$ such that $|(a-b)A + (c-d)A|> q/2$. The $|A| > q^{1/2}$ hypothesis cannot be relaxed at all. When $q=p^2$ is the square of a prime and $A$ is (an isomorphic copy of) $\mathbb{F}_p$, we have $(a-b)A + (c-d)A = A$ for all $a,b,c,d \in A$. Therefore $|(a-b)A + (c-d)A| = |A| = q^{1/2}$.

I have had more luck when the role of addition and multiplication is reversed. For prime $q$ (written as $p$ for clarity) the set $$ (A-A)(A-A) = \{(a-b)(c-d) : a,b,c,d \in A\}$$ contains at least $p/2$ elements under the weaker hypothesis $|A| > p^{5/8}$. To the best of my knowledge this is the only sum-product question in the literature where something as strong is known for sets of cardinality below the $p^{2/3}$ threshold.
 

3. Exponential Sums

There is considerable overlap between sum-product questions in finite fields and exponential sums. A good example, is a result Igor Shparlinski and I have proved on trilinear exponential sums. Let $A \subseteq \mathbb{F}_p$ be a set in the prime order finite field with $p$ elements. Define $$ S_3(A) = \sum_{a,b,c \in A} \exp\left(\frac{2\pi i abc}{p} \right). $$ The modulus of the exponential sum is trivially bounded by $|A|^3$. A classical question is to obtain non-trivial bounds. The best known bound was due to Bourgain and Garaev who have proved $$ |S_3| = O(p^{5/18+o(1)} |A|^{39/16}). $$ We have established the bound $$ |S_3| = O(p^{1/4} |A|^{19/8}), $$ which improvoves the exponent of both $p$ and $|A|$.

I have also worked in harmonic analysis on a problem of slightly different nature. Let $A\subset \mathbb{Z}$ be a finite set. The $ L^1$-norm of the exponential sum $$F_A(t) = \sum_{a\in A} \exp(2\pi i a t)$$ is at least a constant multiple of $ \log|A|$. This was once known as Littlewood's conjecture and was proved independently by Sergei Konyagin and Carruth McGehee, Louis Pigno and Brent Smith. The bound is correct up to a constant when $ A$ is an arithmetic progression centered at zero and $ F_A$ is the Dirichlet kernel $ D_{|A|}$.

It is suspected that an inverse result must hold. For the purpose of this exposition it is best to state it in vague terms: when $ \|F_A\|_1 \leq C \log|A|$ for an absolute constant $C$, then $A$ must have very large intersection with a union of a few arithmetic progressions. Thirty five years after settling Littlewood's conjecture and despite advances by Ben Green and Tom Sanders in the corresponding question for finite groups (where $\|F_A\|_1$ is usually called the algebra norm and may be a constant independent of $ |A|$) the question remains wide open.

I have made partial progress by proving that the $L^1$-norm of the exponential sum of sets that in a technical sense have multidimensional structure is much larger than $ \log|A|$, shading some light on the structure of sets whose exponential sum has nearly minimal $L^1$-norm.

4. Random Graphs

As mentioned above Plünnecke proved his inequality on sumsets by graph theoretic means. He deduced the inequality from a theorem on the growth of a class of layered directed graphs that satisfy a graph theoretic version of the commutativity of addition.

The most obvious way to go about improving Plünnecke's inequality is to try and improve Plünnecke's theorem on layered graphs. This is however not possible. In my PhD thesis I constructed examples of layered graphs where Plünnecke's theorem is attained. A natural question asked by my advisor was whether random examples would also suffice.

In joint work with Guillem Perarnau we answered this question to the affirmative. The question is more or less equivalent to the problem of finding with high probability a matching in an induced subgraph of a random regular bipartite graph.

For fixed positive integers $n$ and $d$, a random $d$-regular bipartite graph $G$ on vertex set $(A,B)$, where $A$ and $B$ are sets of size $n$, is a graph chosen uniformly at random from all bipartite graphs on $(A,B)$ and of constant degree $d.$ We worked on the subgraph $G(X,Y)$ induced on two fixed sets $ X\subseteq A$ and $ Y\subseteq B$, where $A$ and $B$ have size $d$. We were interested in finding the values of $d$ in terms of $n$ for which there is with high probability a matching in the induced subgraph $G(X,Y)$.

Edges in ($G$ and hence also in) $G(X,Y)$ appear with uniform probability $ d/n$, though they do not appear independently. The dependencies nonetheless appear to be small and so in many ways the induced subgraph resembles a random bipartite graph on $ (X,Y)$ where edges appear independently with probability $d/n.$

Paul Erdős and Alfred Rényi have answered the question of finding a matching for random bipartite graphs. Their result suggests that a matching must exist in $ G(X,Y)$ with high probability when $ \frac{d^2}{n}-\log(d)\to +\infty$, while there must be no matching in $G(X,Y)$ with high probability when $ \frac{d^2}{n}-\log(d)\to -\infty.$

We were able to prove this behaviour by modifying the Erdős - Rényi argument. The lack of independence posed obstacles that were overcome with the help of so-called switchings between regular bipartite graphs introduced by Brendan McKay.