Most of my research lies in the fields of analytic and combinatorial number theory with tools from analysis such as Fourier analysis and ergodic theory. However, I view myself as a problem solver and strive to learn new mathematics and work beyond the intersection of these fields. I have worked in other areas of combinatorics and analytic number theory such as Diophantine approximation, equidistribution theory, probabilistic combinatorics, and applications to computer science. I am particularly interested in the function field setting, in which things are usually nicer and one has extra tools (e.g., GRH, linear algebra, the polynomial method) but extra difficulty also arises (e.g. caused by the totally disconnected topology or the finite characteristic).

My research is currently supported by grant DMS-1702296 from the NSF. In 2017-2018, I was also supported by a Ralph E. Powe Junior Faculty Enhancement Award from Oak Ridge Associated Universities.

The following are my publications and preprints by topics (the local version may differ slightly from the printed version). (

What structures can be found in any finite partitions (or colorings) of
the integers, or better yet, in any dense subset of the integers (that
is, a set of positive relative upper density)? Examples include Roth's
theorem, which says that any dense subset of the integers must contain
a three-term arithmetic progression, and Szemerédi's theorem, a
far-reaching generalization of the former, which says that any dense
subset of the integers must contain a $k$-term arithmetic progression,
for any $k \geq 3$. The primes are of density zero, but do they contain
arbitrarily long arithmetic progressions? An affirmative answer to this
question is the content of the celebrated Green-Tao theorem. Having its
roots in arithmetic Ramsey theory, this field of research has seen
tremendous growth in the past decade. It involves ideas and techniques
from many different areas of mathematics such as number theory (circle
and sieve methods), combinatorics (graphs and hypergraphs), ergodic
theory (multiple recurrence) and (higher order) Fourier analysis.

Thanks to Green and Tao's transference machinery, one can now prove the existence of many additive configurations in the primes. For example, the primes contain polynomial progressions $\{ a, a+P_1(d), a+P_2(d),\ldots,a+P_k(d) \}$, where $P_1, P_2, \ldots, P_k$ are any given polynomials in $\mathbf{Z}[x]$ vanishing at 0 and $d \neq 0$ (a result due to Tao and Ziegler). However, many other configurations remain to be explored. What can we say about the step $d$ of these polynomials? What is the most general class of polynomials (not necessarily vanishing at 0) for which we have the same conclusion? What configurations can we find in higher dimensions?

In [2] I proved a function field analog of the Green-Tao theorem. In joint work with Julia Wolf [10], we extended the above result on polynomial progressions in the primes. In [12] I investigated other configurations pertaining finite partitions of the primes. With Anh Lę, we are currently studying the analog of [10] for multidimensional configurations.

Thanks to Green and Tao's transference machinery, one can now prove the existence of many additive configurations in the primes. For example, the primes contain polynomial progressions $\{ a, a+P_1(d), a+P_2(d),\ldots,a+P_k(d) \}$, where $P_1, P_2, \ldots, P_k$ are any given polynomials in $\mathbf{Z}[x]$ vanishing at 0 and $d \neq 0$ (a result due to Tao and Ziegler). However, many other configurations remain to be explored. What can we say about the step $d$ of these polynomials? What is the most general class of polynomials (not necessarily vanishing at 0) for which we have the same conclusion? What configurations can we find in higher dimensions?

In [2] I proved a function field analog of the Green-Tao theorem. In joint work with Julia Wolf [10], we extended the above result on polynomial progressions in the primes. In [12] I investigated other configurations pertaining finite partitions of the primes. With Anh Lę, we are currently studying the analog of [10] for multidimensional configurations.

[24] Multidimensional configurations
in the primes with shifted prime steps

with A. Lę, preprint.

[summary] [pdf] [journal]

with A. Lę, preprint.

[summary] [pdf] [journal]

The Furstenberg-Katznelson theorem, a multidimensional generalization of Szemerédi's theorem, states that given $v_1, \ldots, v_k \in \mathbf{Z}^d$, any subset of positive upper density of $\mathbf{Z}^d$ contains an affine image of $\{ v_1, \ldots, v_k \}$, that is, a configuration $\{ a + tv_1, \ldots, a+ tv_{k} \}$ where $a \in \mathbf{Z}^d$ and $t \in \mathbf{Z} \setminus \{ 0 \}$. A refinement of Host-Kra-Frantzikinakis says that we can take $t$ to be of the form $p-1$ where $p$ is prime. Regarding configurations in the primes, Tao-Ziegler, Cook-Magyar-Titichetrakun and Fox-Zhao independently proved that any subset of positive upper density of $\mathcal{P}^d$ (where $\mathcal{P}$ is the set of primes) also contains a configuration $a + tv_1, \ldots, a+ tv_{k}$. We prove a refinement of this result, showing that $t$ can be taken to be of the form $p-1$. Our work relies on the weighted Furstenberg correspondence principle of Tao-Ziegler, the argument of Host-Kra-Frantzikinakis, and the paper [10].

[10] Polynomial configurations in the
primes

with J. Wolf, Int. Math. Res. Not. (2014) 2014 (23): 6448--6473.

[summary] [pdf] [journal]

with J. Wolf, Int. Math. Res. Not. (2014) 2014 (23): 6448--6473.

[summary] [pdf] [journal]

The Bergelson-Leibman theorem states that any subset of the integers of positive upper density contains a polynomial configuration $\{ a + P_1(d), \ldots, a + P_k(d) \}$, where $P_1 \ldots, P_k \in \mathbf{Z}[x]$ and $a, d \in \mathbf{Z}, d \neq 0$. Various generalizations of this theorem are known. Wooley and Ziegler showed that the variable m can in fact be taken to be a prime minus 1, and Tao and Ziegler showed that the Bergelson-Leibman theorem holds for subsets of the primes of positive relative upper density. Here we prove a hybrid of the latter two results, namely that the step $d$ in the Tao-Ziegler theorem can be restricted to the set of primes minus 1.

[7] Partition regularity and the primes

C. R. Math. Acad. Sci. Paris 350 (2012), no. 9--10, 439--441.

[summary] [pdf] [journal]

C. R. Math. Acad. Sci. Paris 350 (2012), no. 9--10, 439--441.

[summary] [pdf] [journal]

We show, as a consequence of Green and Tao's program on counting linear patterns in the primes and Deuber's work on partition regularity, that if a system of equations is partition regular over the positive integers, then it is also partition regular over the sets $\{ p - 1 : p \; \mathrm{prime} \}$ as well as $\{ p + 1 : p \; \mathrm{prime} \}$. In particular, if the primes are finitely colored, then for any $k$, there exists a monochromatic arithmetic progression of length $k$ and common difference $d$ such that $d+1$ is prime, and of the same color. This answers a question of Li and Pan.

[2] Green-Tao theorem in
function fields

Acta Arith. 147 (2011), 129--152.

[summary] [pdf] [journal]

Acta Arith. 147 (2011), 129--152.

[summary] [pdf] [journal]

We adapt the proof of the Green-Tao theorem on arithmetic progressions in primes to the setting of polynomials over a finite fields, to show that for every $k$, the irreducible polynomials in $\mathbf{F}_q[t]$ contains configurations of the form $\{f + Pg : \deg(P) < k \}, g \neq 0$. In particular, the monic irreducible polynomials in $\mathbf{F}_q[t]$ contains affine spaces of arbitrarily high dimension.

If $A$ is a subset of a group $G$, then we expect $A-A = \{a-a': a, a'
\in A \}$ to contain nice structures. This reflects the fact that the
convolution of two functions is in general smoother then the individual
functions. An early result in this theme is Steinhaus' theorem, which
says that if $A \subset \mathbf{R}$ has positive Lebesgue measure, then
$A-A$ contains an interval around $0$. It makes sense to study
structures in $A-A$ in any group $G$ (commutative or not).

If $G =\mathbf{Z}$ and $A$ is a dense set, then $A-A$ contains a non-zero square. This is a result due to Furstenberg and Sárközy, now commonly known as Sárközy's theorem. Moreover, $A-A$ contains a number of the form $p-1$, where $p$ is prime. What makes the sets $\{n^2: n \in \mathbf{Z} \}$ and $\{p-1 : p \; \mathrm{ prime}\}$ so special? Note that the sets $\{n^2+1: n \in \mathbf{Z} \}$ and $\{p : p \; \mathrm{ prime}\}$ fail to have this property. What are other sets enjoying this property?

We called sets enjoying this property*intersective*.
It turns
out that intersective sets are the same as *sets of (single)
recurrence*
in ergodic theory. Besides studying them qualitatively (which sets are
intersective?), we can also study them quantitatively: given $N$, how
big can a subset $A$ of $\{1,2,\ldots, N\}$ be, while its difference
set $A-A$ avoids a given set? There are different approaches to
intersective sets, with methods from additive number theory, ergodic
theory and Fourier analysis. Of course, we can define intersective sets
as well in other settings (preferably, arithmetically rich) where there
is an appropriate notion of density, such as $\mathbf{Z}^d$, or a
number field, or a function field.

In joint works with my coauthors Yu-Ru Liu and Craig Spencer [4, 5] we proved qualitatively function field analogs of the intersectivity of the squares and shifted primes mentioned above. In [3], I showed that the difference set of any dense subset of the primes also contains values of certain polynomials (a prime version of the Furstenberg-Sárközy theorem).

If $G=\mathbf{F}_p^n$, a vector space over a finite field, then in analogy with Steinhaus' theorem, one expects $A-A$ to contain a large subspace if $A$ is a dense subset. However, the subspace contained in $A-A$ may not have finite codimension. A theorem of Bogolyubov says that $A+A-A-A$ contains a subspace of finite codimension. This reflects the fact that the more convolutions we take, the smoother the function is. In joint works with my coauthors Pierre-Yves Bienvenu and Zhenchao Ge [20, 22], we study structures in difference sets in vector spaces.

If $G =\mathbf{Z}$ and $A$ is a dense set, then $A-A$ contains a non-zero square. This is a result due to Furstenberg and Sárközy, now commonly known as Sárközy's theorem. Moreover, $A-A$ contains a number of the form $p-1$, where $p$ is prime. What makes the sets $\{n^2: n \in \mathbf{Z} \}$ and $\{p-1 : p \; \mathrm{ prime}\}$ so special? Note that the sets $\{n^2+1: n \in \mathbf{Z} \}$ and $\{p : p \; \mathrm{ prime}\}$ fail to have this property. What are other sets enjoying this property?

We called sets enjoying this property

In joint works with my coauthors Yu-Ru Liu and Craig Spencer [4, 5] we proved qualitatively function field analogs of the intersectivity of the squares and shifted primes mentioned above. In [3], I showed that the difference set of any dense subset of the primes also contains values of certain polynomials (a prime version of the Furstenberg-Sárközy theorem).

If $G=\mathbf{F}_p^n$, a vector space over a finite field, then in analogy with Steinhaus' theorem, one expects $A-A$ to contain a large subspace if $A$ is a dense subset. However, the subspace contained in $A-A$ may not have finite codimension. A theorem of Bogolyubov says that $A+A-A-A$ contains a subspace of finite codimension. This reflects the fact that the more convolutions we take, the smoother the function is. In joint works with my coauthors Pierre-Yves Bienvenu and Zhenchao Ge [20, 22], we study structures in difference sets in vector spaces.

[22] On theorems of Wirsing and
Sanders

with Z. Ge, Acta Arithmetica 189 (2019), no. 4, 381--390.

[summary] [pdf] [journal]

with Z. Ge, Acta Arithmetica 189 (2019), no. 4, 381--390.

[summary] [pdf] [journal]

If $A \subset \mathbf{F}_p^n$ has density $>1/2$, then clearly $A-A = \mathbf{F}_p^n$. What happens when the density of $A$ is $1/2$, or slightly less than $1/2$? Sanders proved that if $A \subset \mathbf{F}_2^n$ has density $\geq 1/2 - c/\sqrt{n}$, then $A-A$ contains a subspace of codimension 1. We generalize Sanders' result to $\mathbf{F}_p^n$ for all $p$, while giving a simpler and elementary proof. Our main tool is an isoperimetric-type inequality, which is inspired by an argument of Wirsing.

[20] A bilinear Bogolyubov theorem

with P-Y. Bienvenu, European Journal of Combinatorics 77, March 2019, 102--113.

[summary] [pdf] [journal]

with P-Y. Bienvenu, European Journal of Combinatorics 77, March 2019, 102--113.

[summary] [pdf] [journal]

We prove a bilinear version of Bogolyubov's theorem for dense
subsets $A$ of $\mathbf{F}_p^n\times\mathbf{F}_p^n$.
If we perform horizontal and vertical sums and differences on $A$, that
is, operations on the second coordinate
when the first one is fixed, or vice versa, then the resulting set
contains a nice structure.
The structure we find is the zero set of a family of bilinear forms
on a Cartesian product of vector subspaces. The codimensions of the
subspaces and the number of bilinear forms
involved are bounded by a function $c(\delta)$
of the density $\delta=|A|/p^{2n}$ only.
The proof uses various tools of additive combinatorics, such as the
(linear) Bogolyubov theorem,
the density increment method, as well as the Balog-Szemerédi-Gowers
and Freiman-Ruzsa theorems.

This result was proved independently by Gowers and Milićević. It has
applications in Gowers-Milićević's work on the quantitative inverse
theorem for the Gowers $U^4$ norm over finite fields. Moreover, a
recent quantitative improvement due to Hosseini-Lovett enabled us to
prove an exponential sum in $\mathbf{F}_q[t]$ in [21], which is better
than the corresponding bound in $\mathbf{Z}$.

[6] Problems and results on
intersective sets

Combinatorial and Additive Number Theory: CANT 2011 and 2012, Springer Proceedings in Mathematics & Statistics (2014).

[summary] [pdf] [book]

Combinatorial and Additive Number Theory: CANT 2011 and 2012, Springer Proceedings in Mathematics & Statistics (2014).

[summary] [pdf] [book]

This is a survey of open problems and results (as of May 2011) on intersective sets in the integers and the analogous notion in the ring of polynomials $\mathbf{F}_q[t]$ over a finite field $\mathbf{F}_q$. It also contains an elegant, algebraic proof of Alon of the following result. If $q$ is prime, then the set of polynomials in $\mathbf{F}_q[t]$, all of whose coefficients are either 0 or 1, is intersective in $\mathbf{F}_q[t]$.

[5] On sets of polynomials
whose difference set contains no squares

with Y-R. Liu, Acta Arith. 161 (2013), 127--143.

[summary] [pdf] [journal]

with Y-R. Liu, Acta Arith. 161 (2013), 127--143.

[summary] [pdf] [journal]

Let $A$ be a subset of the polynomials of degree less than $N$ over a finite field $\mathbf{F}_q$. We show that if the difference set $A-A$ does not contain non-zero squares of polynomials, then $|A| \ll_{q} \frac{(\log N)^7}{N} \cdot q^N$. The same bound also applies when $A-A$ does not contain $k$-th powers, when $k < p$ (where $p$ is the characteristic of the field). The proof does not work when $k \geq p$ because of the limitation of the Weyl differencing process in finite characteristic. In our subsequent work [14] this limitation was overcome.

[4] Difference sets and
the irreducibles in function fields

with C.V Spencer, Bull. Lond. Math. Soc. 43 (2011), no. 2, 347--358.

[summary] [pdf] [journal]

with C.V Spencer, Bull. Lond. Math. Soc. 43 (2011), no. 2, 347--358.

[summary] [pdf] [journal]

Let $A$ be a subset of the polynomials of degree less than $N$ over a finite field $\mathbb{F}_q$. Let $r$ be any non-zero element of $\mathbf{F}_q$. We show that if the difference set $A-A$ does not contain elements of the form $P +r$, where $P$ is a monic, irreducible polynomial, then $|A| \ll_q q^{N - cN/\log N}$, where $c$ is a constant depending on $q$. This bound is better than the best bound in the integers, thanks to improved exponential sum estimates and the Generalized Riemann Hypothesis in $\mathbf{F}_q[t]$.

[3] Intersective polynomials and the
primes

Journal of Number Theory 130 (2010), Issue 8, 1705--1717.

[summary] [pdf] [journal]

Journal of Number Theory 130 (2010), Issue 8, 1705--1717.

[summary] [pdf] [journal]

Intersective polynomials are polynomials in $\mathbf{Z}[x]$ having roots every modulus. For example, $h_1(n)=n^2$ and $h_2(n)=n^2-1$ are intersective polynomials, but $h_3(n)=n^2+1$ is not. Being intersective is a necessary and sufficient condition for the set of values of a polynomial to be intersective. Using Lucier's work on intersective polynomials and the "transference principle" of Green and Tao, we show that for any intersective polynomial $h$, inside any subset of positive relative density of the primes, we can find distinct primes $p_1, p_2$ such that $p_1 - p_2= h(n)$ for some integer $n$. Such a conclusion also holds in the Chen primes (where by a Chen prime we mean a prime number $p$ such that $p + 2$ is the product of at most 2 primes).

Dirichlet's
approximation theorem says that for any $N > 0$ and $\alpha \in
\mathbf{R}$, there is $1 \leq q \leq N$ such that $\| q \alpha \| \leq
\frac{1}{N}$, where $\| \cdot \|$ denotes the distance to the nearest
integer. What if we require $q$ to be in a special set, for example,
the sets of squares, primes, square-free numbers, smooth numbers, etc.?
Under such restrictions, how small can $\| q \alpha \|$ be? When $q$ is
a $k$-th power, this question has been studied since Hardy-Littlewood
and Vinogradov. In joint works with Craig Spencer [8, 12], we replaced
$k$-th powers by the largest possible class of polynomials and showed
that for these polynomials we also have similar Diophantine
inequalities.

Dirichlet's theorem, in a sense, is best possible since there are numbers $\alpha$ (known as*badly approximable*
numbers) which have the property that $n \cdot \| n \alpha \| \geq c$
for all $n \in \mathbf{Z}^+$, for some constant $c > 0$. Can we
do
better than that, namely to find two numbers $\alpha, \beta$ and a
constant $c > 0$ such that $n \cdot \| n \alpha \| \cdot \| n
\beta
\|
\geq c$ for all $n \in \mathbf{Z}^+$? The Littlewood conjecture says
that this is impossible. While counterexamples to the Littlewood
conjecture are unlikely, in [11] Jeff Vaaler and I proved some
Diophantine inequalities involving the fractional parts of linear forms
and found a connection between these inequalities and (a generalization
of) counterexamples to the Littlewood conjecture. In [13] we studied
these counterexamples in the settings of the polynomial ring
$\mathbf{F}[t]$ over a field $\mathbf{F}$ and found that the situation
is quite different when $\mathbf{F}$ is infinite.

Dirichlet's theorem, in a sense, is best possible since there are numbers $\alpha$ (known as

[13] Multiplicatively badly
approximable matrices
in fields of power series

with J. D. Vaaler, Proc. Amer. Math. Soc. 143 (2015), no. 9, 3791--3800.

[summary] [pdf] [journal]

with J. D. Vaaler, Proc. Amer. Math. Soc. 143 (2015), no. 9, 3791--3800.

[summary] [pdf] [journal]

Multiplicatively badly approximable matrices are a strengthening of the usual notion of badly approximable matrices. We study the analogous notion in the setting of power series over a field, giving a proof of the transference principle in this setting. In contrast to the real case where such matrices are believed to not exist, we show that multiplicatively badly approximable matrices do exist when the field is infinite.

[12] Intersective polynomials and
Diophantine
approximation, II

with C. V. Spencer, Monatsh. Math. 177 (2015), no. 1, 79--99.

[summary] [pdf] [journal]

with C. V. Spencer, Monatsh. Math. 177 (2015), no. 1, 79--99.

[summary] [pdf] [journal]

This is a continuation of our investigation in [8]. We extend our previous work to a system of polynomials evaluated at primes. Again, when some necessary local conditions are met, we also have desired Diophantine inequalities with polynomial savings. The simplest case of our result states that, uniformly in $N$ and $\alpha$, we have $$\min_{\substack{1 \leq p \leq N, \\p \, \mathrm{prime}}} \| (p-1) \alpha \| \ll N^{-1/20}.$$

[11] Sums of products of fractional
parts

with J. D. Vaaler, Proc. London Math. Soc. (3) 111 (2015), no. 3, 561--590.

[summary] [pdf] [journal]

with J. D. Vaaler, Proc. London Math. Soc. (3) 111 (2015), no. 3, 561--590.

[summary] [pdf] [journal]

We prove upper and lower bounds for certain sums of products of fractional parts by using majoring and minorizing functions from Fourier analysis. In special cases the upper bounds are sharp if there exist counterexamples to the Littlewood conjecture in Diophantine approximation. A generalization of such counterexamples is known as multiplicatively badly approximable matrices in the literature. We prove a transference principle for multiplicatively badly approximable matrices, namely that if a matrix is multiplicatively badly approximable, then so is its transpose.

[8] Intersective polynomials and
Diophantine
approximation

with C. V. Spencer, Int. Math. Res. Not. (2014) 2014 (5): 1153--1173.

[summary] [pdf] [journal]

with C. V. Spencer, Int. Math. Res. Not. (2014) 2014 (5): 1153--1173.

[summary] [pdf] [journal]

It has been known since Vinogradov
(1927) that for each $k$ there is an exponent $\theta=\theta_k >
0$
such that for every positive integer $N$ and real number $\alpha$,
we have $\min_{1 \leq n \leq N} \| n^k \alpha \| \ll N^{-\theta}$, the
bound being uniform in $\alpha$
and $N$. This has been generalized to a system of polynomials without
constant terms.
In this paper, we observe that the "true" condition to impose on these
polynomials is of local
nature, and prove generalizations of the above results under this
condition.

The simplest case of our result is as follows. If $h \in \mathbf{Z}[x]$
is *intersective* (i.e., having roots every modulus),
then we
have an inequality of the form $\min_{1 \leq n \leq N} \| h(n) \alpha
\| \ll N^{-\theta}$, for some $\theta > 0$.

I also work on exponential and character sum estimates in the
integers, finite fields and function fields. In the last two settings
one can usually prove better bounds than in $\mathbf{Z}$, thanks to the
Generalized Riemann Hypothesis.

One topic I am pursuing is exponential estimates for the Möbius function over $\mathbf{F}_q[t]$. This is an instance of the Möbius randomness principle and an analog of the Möbius and Nilsequence conjecture proved by Green and Tao. The analogy is in spirit only, since the two situations are quite different in many aspects. With Pierre-Yves Bienvenu, in [21] we studied Möbius-exponential sums with linear and quadratic phases and proved better bounds than the corresponding bounds in $\mathbf{Z}$.

One topic I am pursuing is exponential estimates for the Möbius function over $\mathbf{F}_q[t]$. This is an instance of the Möbius randomness principle and an analog of the Möbius and Nilsequence conjecture proved by Green and Tao. The analogy is in spirit only, since the two situations are quite different in many aspects. With Pierre-Yves Bienvenu, in [21] we studied Möbius-exponential sums with linear and quadratic phases and proved better bounds than the corresponding bounds in $\mathbf{Z}$.

[21] Linear and quadratic uniformity
of the Möbius function over $\mathbf{F}_q[t]$

with P-Y. Bienvenu, Mathematika 65 (2019), Issue 3, 505--529.

[summary] [pdf] [journal]

with P-Y. Bienvenu, Mathematika 65 (2019), Issue 3, 505--529.

[summary] [pdf] [journal]

We examine correlations of the Möbius function over
$\mathbf{F}_q[t]$ with linear or quadratic phases,
that is, averages of the form
$$\dfrac{1}{q^n}\sum_{\textrm{deg} f < n} \mu(f)\chi(Q(f))
$$
for an additive character $\chi$ over $\mathbf{F}_q$ and
a polynomial $Q\in\mathbf{F}_q[x_0,\ldots,x_{n-1}]$ of degree at most 2
in the coefficients $x_0,\ldots,
x_{n-1}$ of $f=\displaystyle \sum_{i < n}x_i t^i$.

Like in the integers, it is
reasonable to expect that, due to the random-like behaviour of
$\mu$,
such sums should exhibit considerable cancellation.
In this paper we show that the correlation above is bounded by
$O_\epsilon \left( q^{(-\frac{1}{4}+\epsilon)n} \right)$ for any
$\epsilon > 0$ if $Q$ is linear
and $O \left( q^{-n^c} \right)$ for some absolute constant $c
>0$ if $Q$ is quadratic.
Our argument relies on a
bilinear version of the Bogolyubov theorem in additive combinatorics
(see the paper [20]).

In both linear and quadratic cases, our bound is better than the bounds
in $\mathbf{Z}$, which correspond to $O_A \left( n^{-A}\right)$ for any
$A >0$.

[19] A note on a chacracter sum in
finite fields

with A. Bhowmick and Y-R. Liu, Finite Fields and Their Applications 46 (2017), 247--254.

[summary] [pdf] [journal]

with A. Bhowmick and Y-R. Liu, Finite Fields and Their Applications 46 (2017), 247--254.

[summary] [pdf] [journal]

Continuing the work in [16] and answering a question of
Shparlinski, we prove yet another bound for short character sums in
the ring $\mathbf{F}_q[t]$. Specifically, if $Q \in \mathbf{F}_q[t]$ is
a
polynomial of degree $n$, $\chi$ is a multiplicative character modulo
$Q$, and $A_d$
is the set of all polynomials in $\mathbb{F}_q[t]$ of degree $d$, then
we have
$$
\left| \sum_{f \in A_d} \chi(f) \right| \leq q^{\dfrac{d}{2}
+ \dfrac{d
\log \log n}{\log n} + O_q \left( \dfrac{n}{\log^2 n} \right)}. $$
In [21] we generalized this to more general characters, namely
characters of *arithmetically distributed relations*
introduced by Hayes.

Besides intersective sets, I am interested in other similar sets having
both arithmetic and combinatorial
flavors. These are *van
der Corput* and *Glasner*
sets. In turn, these notions have deep connections with
equidistribution theory, exponential sums and harmonic analysis of
measures.

The classical van der Corput difference theorem says that if a sequence $(u_n)_{n=1}^\infty \subset \mathbf{T}:=\mathbf{R}/\mathbf{Z}$ has the property that the sequence $(u_{n+h}-u_{n})_{n=1}^{\infty}$ is equidistributed in $\mathbf{T}$, for each $h > 0$, then $(u_n)_{n=1}^\infty$ is also equidistributed itself. It turns out that in order for $(u_n)_{n=1}^\infty$ to be equidistributed, it suffices to "check" the equidistribution of $(u_{n+h}-u_{h})_{n=1}^{\infty}$, where $h$ belongs to certain subsets of $\mathbf{Z}^{+}$. Such sets are called van der Corput. The sets $\{n^2: n \in \mathbf{Z} \}$ and $\{p-1 : p \; \mathrm{ prime}\}$ are examples of van der Corput sets. Any van der Corput set is intersective, but the converse is not true, a result due to Bourgain.

If $X \subset \mathbf{T}$ is any infinite sequence, then there is an integer $h > 0$ such that the dilation $hX = \{hx: x \in X \}$ intersects every interval of prescribed length. Again, the same is true if $h$ is restricted to be in special subsets of $\mathbf{Z}^{+}$. Such sets are called Glasner. The sets $\{n^2: n \in \mathbf{Z} \}$ and $\{p : p \; \mathrm{ prime}\}$ are examples of Glasner sets.

Clearly, we can ask for the same phenomena in very general settings. What if we replace $\mathbf{T}$ by other (not necessarily abelian) compact groups? What if we index the elements of our sequence by another group, instead of $\mathbf{Z}$? With coauthors Yu-Ru Liu and Michael Kelly, we study such questions in [9, 14, 18].

The classical van der Corput difference theorem says that if a sequence $(u_n)_{n=1}^\infty \subset \mathbf{T}:=\mathbf{R}/\mathbf{Z}$ has the property that the sequence $(u_{n+h}-u_{n})_{n=1}^{\infty}$ is equidistributed in $\mathbf{T}$, for each $h > 0$, then $(u_n)_{n=1}^\infty$ is also equidistributed itself. It turns out that in order for $(u_n)_{n=1}^\infty$ to be equidistributed, it suffices to "check" the equidistribution of $(u_{n+h}-u_{h})_{n=1}^{\infty}$, where $h$ belongs to certain subsets of $\mathbf{Z}^{+}$. Such sets are called van der Corput. The sets $\{n^2: n \in \mathbf{Z} \}$ and $\{p-1 : p \; \mathrm{ prime}\}$ are examples of van der Corput sets. Any van der Corput set is intersective, but the converse is not true, a result due to Bourgain.

If $X \subset \mathbf{T}$ is any infinite sequence, then there is an integer $h > 0$ such that the dilation $hX = \{hx: x \in X \}$ intersects every interval of prescribed length. Again, the same is true if $h$ is restricted to be in special subsets of $\mathbf{Z}^{+}$. Such sets are called Glasner. The sets $\{n^2: n \in \mathbf{Z} \}$ and $\{p : p \; \mathrm{ prime}\}$ are examples of Glasner sets.

Clearly, we can ask for the same phenomena in very general settings. What if we replace $\mathbf{T}$ by other (not necessarily abelian) compact groups? What if we index the elements of our sequence by another group, instead of $\mathbf{Z}$? With coauthors Yu-Ru Liu and Michael Kelly, we study such questions in [9, 14, 18].

[18] Van der Corput sets with respect
to compact
groups

with M. Kelly, Arch. Math. (Basel) 110 (2018), no. 4, 343--349.

[summary] [pdf] [journal]

with M. Kelly, Arch. Math. (Basel) 110 (2018), no. 4, 343--349.

[summary] [pdf] [journal]

Let $G$ be a (Hausdorff, not necessarily abelian) compact
group.
Motivated by
van
der Corput's difference theorem, we say that a set $H \subset
\mathbf{Z}^+$ is $G$-vdC if the following is true. If a sequence
$(u_n)_{n=1}^\infty \subset G$ has the property that the sequence
$(u_{n+h}u_{n}^{-1})_{n=1}^{\infty}$ is equidistributed in $G$, for
each $h \in H$, then $(u_n)_{n=1}^\infty$ is also equidistributed in
$G$. Thus the usual van der Corput sets are $\mathbf{T}$-vdC sets. We
show that if $H$ is $\mathbf{T}$-vdC, then it is $G$-vdC for any
compact $G$.

We also show that if $G$ is second-countable, then
$G$-vdC sets are intersective. Thus for a second-countable compact
group $G$, the class of $G$-vdC sets lies in between the classes of
$\mathbf{T}$-vdC sets and intersective sets. It is quite conceivable
that for a group $G$ genuinely different from $\mathbf{T}$, say
$G=\mathbf{Z}_2$, both inclusions are strict. Even if one of the
inclusons are strict, this would provide an alternative proof to
Bourgain's result that not all intersective sets are $\mathbf{T}$-vdC.

[14] Equidistribution
of polynomial sequences in function fields, with applications

with Y-R. Liu, preprint.

[summary] [pdf] [journal]

with Y-R. Liu, preprint.

[summary] [pdf] [journal]

We study a function field analog of Weyl's equidistribution theorem of polynomial sequences. In contrast to the real case, the distribution of polynomial sequences in this setting is not well understood. This is due to the failure of the Weyl differencing process in finite characteristic, a barrier known to Carlitz (1952). Our result overcomes this difficulty, and we prove the equidistribution of polynomial sequences subject to a mild condition (without restriction on the degree). We then apply our equidistribution result to combinatorial problems regarding van der Corput, Glasner and intersective sets in function fields.

[9] Uniform dilations in
higher dimensions

with M. Kelly, J. London Math. Soc. (2013) 88 (3): 925--940.

[summary] [pdf] [journal]

with M. Kelly, J. London Math. Soc. (2013) 88 (3): 925--940.

[summary] [pdf] [journal]

A theorem of Glasner says that if $X$ is an infinite subset of the torus $\mathbf{T}$, then for any $\epsilon > 0$, there exists an integer n such that the dilation $nX$ is $\epsilon$-dense in $\mathbf{T}$ (i.e, it intersects any interval of length $2 \epsilon$ in $\mathbf{T}$. Alon and Peres provided a general framework for this problem, and showed quantitatively that one can restrict the dilation to be of the form $f(n)X$ where $f \in \mathbf{Z}[x]$ is not constant. Building upon the work of Alon and Peres, we study this phenomenon in higher dimensions. Let $A(x)$ be an $L \times N$ matrix whose entries are in $\mathbf{Z}[x]$, and $X$ be an infinite subset of $\mathbf{T}^N$. Contrarily to the case $N = L = 1$, it's not always true that there is an integer $n$ such that $A(n)X$ is $\epsilon$-dense in a translate of a subtorus of $\mathbf{T}^L$. We give a necessary and sufficient condition for matrices $A$ for which this is true. We also prove an effective version of the result.

and applications to computer science [introduction]

I enjoy studying various problems in number theory and combinatorics
whose statements are easy to understand.
In [1], with Javier Cilleruelo, we studied gaps between products of a
sequence, which is related to a question posed by Sárközy. In [17],
with Victor Lambert and Alain Plagne, we studied and extended the
notion of
additive bases (a notion put forward by Erdős and Graham) to the
setting of general abelian groups. In the follow-up work [25], with
Pierre-Yves Bienvenu and Benjamin Girard, we extended the methods and
results further.

In [23], with Zhenchao Ge, we studied*essential components*,
a notion studied since Khinchin, Landau, Erdős and Linnik.

Thanks to my former colleagues Abhishek Bhowmick and David Zuckerman at UT Austin, recently I have become interested in applying results in analytic number theory and additive combinatorics to problems in theoretical computer science.

Given a source (i.e., a string of random bits) that produces weak randomness (i.e., the bits are biased or correlated), can we extract from it many (or even one) bits that are (nearly) perfectly random? This is the purpose of*randomness extractors*. In general
this
is impossible, but it is possible to do so if our source is structured.
For example, it may be uniformly distributed on some (unknown) affine
subspace in a vector space. Since extractors can be formulated in terms
of the Fourier transform, exponential and character sum estimates can
be used to produce deterministic extractors. In joint work with
Abhishek Bhowmick,
Ariel Gabizon and David Zuckerman [15], we construct a deterministic
extractor for a
fairly general class of sources over a vector space that is inspired by
additive combinatorics and encompasses many familiar additive objects.

In [16], with Abhishek Bhowmick we use character sums over function fields to study the problem of generating primitive elements of a finite field. In [19] we prove yet another character sum estimate which may be useful in some applications.

In [23], with Zhenchao Ge, we studied

Thanks to my former colleagues Abhishek Bhowmick and David Zuckerman at UT Austin, recently I have become interested in applying results in analytic number theory and additive combinatorics to problems in theoretical computer science.

Given a source (i.e., a string of random bits) that produces weak randomness (i.e., the bits are biased or correlated), can we extract from it many (or even one) bits that are (nearly) perfectly random? This is the purpose of

In [16], with Abhishek Bhowmick we use character sums over function fields to study the problem of generating primitive elements of a finite field. In [19] we prove yet another character sum estimate which may be useful in some applications.

[25] On additive bases in infinite abelian
semigroups

with P.-Y. Bienvenu and B. Girard, preprint.

[summary] [pdf] [journal]

with P.-Y. Bienvenu and B. Girard, preprint.

[summary] [pdf] [journal]

In [17], it is apparent that current techniques to study
Erdős-Graham-type questions have limitations and are not applicable to
all groups. In this follow-up to [17], we develop new arguments and
techniques and prove results that are valid for a class of semigroups
which we term *translatable semigroups*. These include
all infinite abelian
groups, as well as $\mathbb{N}$. In particular, we show finiteness of
$X_G(h)$ for all groups
$G$, which was an open question in [17]. We study a question of
Nathanson regarding removing many (instead of one) elements from an
additive basis. A result of Deschamp-Farhi says that any additive basis
of $\mathbb{N}$ has finitely many essential subsets. We generalize this
result to all translatable semigroups, using a different argument. One
of our new tools is invariant means from
functional analysis.

[23] Essential components in vector
spaces in finite fields

with Z. Ge, preprint.

[summary] [pdf] [journal]

with Z. Ge, preprint.

[summary] [pdf] [journal]

A set $H \subset \mathbf{N}$ is said to be an *essential
component* if $\underline{d}(A+H) > \underline{d}(A)$
for any $A \subset \mathbf{N}$ with $0 < \underline{d}(A)
< 1$, where $\underline{d}$ denotes the lower asymptotic
density. Let $H(x) = | \{ 1 \leq n \leq x : n \in H \}|$ denote the
counting function of $H$. If $H$ is an
essential component, how small can $H(x)$ be? This problem was posed in
the 1930s and studied by
Khinchin, Landau, Erdős, Linnik, among others. It was solved by Ruzsa,
who
showed that for any $c<0$, $H(x) = O( \log^{1+c} x )$ is
possible, but $H(x) = O( \log^{1+o(1)} x )$ is impossible.

We study the analog of this problem in the setting of
$\mathbf{F}_{p}[t]$, where $p$ is prime (though we are only concerned
with the the group structure). Let $G_n = \{ f \in \mathbf{F}_{p}[t]:
\textrm{deg} f < n \}$. For a set $A \subset \mathbf{F}_{p}[t]$,
write $A_n = A \cap G_n$, and define the lower asymptotic density
$\underline{d}(A)$ of
$A$ as $\underline{\textrm{lim}}_{n \rightarrow
\infty}\frac{|A_n|}{p^n}$. A set $H \subset \mathbf{F}_{p}[t]$ is said
to be an *essential
component* if $\underline{\textrm{lim}}_{n \rightarrow
\infty}\frac{|A_n + H_n|}{p^n} > \underline{d}(A)$
for any $A \subset \mathbf{F}_p[t]$ with $0 < \underline{d}(A)
< 1$. We
show that for any $c>0$ there is an essential component $H$ such
that $|H_n| = O(n^{1+c})$. On the other hand, if $|H_n| =
O(n^{1+o(1)})$, then for any $0 < \delta < 1$, there is a
set $A \subset \mathbf{F}_p[t]$ such that $\underline{d}(A) =
\underline{\textrm{lim}}_{n \rightarrow \infty}\dfrac{|A_n +
H_n|}{p^n} = \delta$. This result is more precise than what is known in
the integers.

[17] Additive bases in groups

with V. Lambert and A. Plagne, Israel J. Math. 217 (2017), no. 1, 383--411.

[summary] [pdf] [journal]

with V. Lambert and A. Plagne, Israel J. Math. 217 (2017), no. 1, 383--411.

[summary] [pdf] [journal]

Let $\mathbf{N}$ be the set of all nonnegative integers. A set $A \subset \mathbf{N}$ is called a basis of $\mathbf{N}$ if every sufficiently large integer is a sum of $h$ elements from $A$, for some $h$. The smallest such $h$ is called the order of $A$. For example, the squares form a basis of order 4 and the primes form a basis, conjecturally of order 3, of $\mathbf{N}$. Erdős and Graham asked the following questions. If $A$ is a basis of $\mathbf{N}$ and $a \in A$, when is $A \setminus \{ a \}$ still a basis? It turns out that this is the case for all $a \in A$ with a finite number of exceptions. If $A \setminus \{ a \}$ is still a basis, what can we say about its order? These questions and related questions have been extensively studied. In this paper, we address these questions in the more general setting of an abelian group in place of $\mathbb{N}$ and find that in some cases the answer is quite different.

[16] On primitive elements in finite
fields of low
characteristic

with A. Bhowmick, Finite Fields and Their Applications 35 (2015) 64--77.

[summary] [pdf] [journal ]

with A. Bhowmick, Finite Fields and Their Applications 35 (2015) 64--77.

[summary] [pdf] [journal ]

Deterministically outputting a primitive element of a finite field is a notoriously hard problem. We discuss the problem of constructing a small subset of a finite field that is guaranteed to contain primitive elements. Consider a finite field $\mathbf{F}_{q^n}$, where $q$ is small and $n$ is large. Elements in $\mathbf{F}_{q^n}$ can be regarded as polynomials in $\mathbf{F}_{q}[t]$ with degree less than $n$. We show that the set of all polynomials in $\mathbf{F}_{q}[t]$ of small degree (logarithmic in $n$) contains the expected number of primitive elements in $\mathbf{F}_{q^n}$. While smaller sets have been constructed before, our result gives a probabilistic algorithm to output a primitive element that has similar success probability to the naive algorithm, while improving on both the amount of randomness and run time. Our result follows from a bound for short character sums in function fields, which is better than what is known (conditionally under GRH) in the integer case and is of independent interest.

[15] Deterministic extractors for
additive sources

with A. Bhowmick, A. Gabizon and D. Zuckerman, ITCS (Innovations in Theoretical Computer Science) 2015.

[summary] [pdf] [conference]

with A. Bhowmick, A. Gabizon and D. Zuckerman, ITCS (Innovations in Theoretical Computer Science) 2015.

[summary] [pdf] [conference]

We propose a new model of a weakly random source that admits
randomness extraction. Our
model of additive sources includes such natural sources as uniform
distributions on arithmetic
progressions (APs), generalized arithmetic progressions (GAPs), and
Bohr sets, each of which
generalizes affine sources. We give an explicit extractor for additive
sources with linear minentropy
over both $\mathbf{Z}_p$ and $\mathbf{Z}_p^n$, for large prime $p$,
although our results over $\mathbf{Z}_p^n$ require that the
source further satisfy a list-decodability condition. As a corollary,
we obtain explicit extractors
for APs, GAPs, and Bohr sources with linear min-entropy, although again
our results over $\mathbf{Z}_p^n$ require the list-decodability
condition.

We further explore special cases of additive sources. We improve
previous constructions of
line sources (affine sources of dimension 1), requiring a field of size
linear in $n$, rather than
$\Omega(n^2)$ by Gabizon and Raz. This beats even the non-explicit
bound of $\Theta(n \log n)$ obtained by
the probabilistic method. We then generalize this result to APs and
GAPs.

[1] On a question
of Sárközy on gaps of product sequences

with J. Cilleruelo, Israel J. Math. 179 (2010), 285--295.

[summary] [pdf] [journal]

with J. Cilleruelo, Israel J. Math. 179 (2010), 285--295.

[summary] [pdf] [journal]

Motivated by a question of Sárközy, we study the gaps in the product sequence $B = A \cdot A = \{b_1 < b_2 < ...\}$ of all products $a_i \cdot a_j$ with $a_i, a_j \in A$ when $A \subset \mathbf{Z}^+$ has upper Banach density $\alpha > 0$. We prove that there are infinitely many gaps $b_{n+1} - b_n \ll \alpha^{-3}$ and that for $t \geq 2$ there are infinitely many $t$-gaps $b_{n+t} - b_n \ll t^2 \alpha^{-3}$. Furthermore we prove that these estimates are best possible (up to implicit constants). We also discuss a related question about the cardinality of the quotient set $A/A = \{a_i/a_j : a_i, a_j \in A\}$ when $A \subset \{ 1,.., N \}$ and $|A| = \alpha N$.