| Employment | |
| 1987, 1988 (summers) | Software development at the NASA Ames Research Center , in support of the SIRTF project (later renamed the Spitzer Space Telescope ) |
|---|---|
| 1994-1995 | Member, Institute For Advanced Study, Princeton. |
| 1995-1998 | R. H. Bing Instructor (postdoc), University of Texas, Austin |
| 1998-2001 | Assistant Professor, University of South Carolina, Columbia |
| 2001-present | University of Illinois at Urbana-Champaign. Professor since 2009 |
| 2009-2010 | Member, Institute For Advanced Study, Princeton |
| 2017 | Research Member, Mathematical Sciences Research Institute, Berkeley |
| 2019 | Visiting Fellow, Magdalen College, Oxford |
| Graduate Students | |
| George Shakan | Ph.D., 2019 |
|---|---|
| Kyle Pratt | Ph.D., 2019 |
| Xianchang Meng | Ph.D. 2017 |
| Joseph Vandehey | Ph.D. 2013 (co-advised with Florin Boca) |
| Jason Sneed | Ph.D. 2010 |
| Dimitrios Koukoulopoulos | Ph.D. 2010 |
| Sun Kim | Ph.D. 2010 (co-advised with Bruce Berndt) |
| Yong Hu | Ph.D. 2007 |
| John Riggott | M.S. 1999 |
| Postdocs mentored | |
| Kunjakanan Nath | 2021-present |
|---|---|
| Xiannan Li | 2011-2013 |
| Youness Lamzouri | 2010-2012 |
| Paul Pollack | 2008-2011 |
| Emre Alkan | 2003-2006 |
| Research Highlights | |
| Link to all of my papers | New estimates for mean values of Weyl sums (1995) | We invent a new method for extracting more efficiently a bound on the \(2s\)-moment of a degree-\(k\) Weyl sum using bounds on Vinogradov's Mean Value. Consequences include large improvements in the known range of validity of the asymptotic formula in Waring's problem. |
|---|---|
| The distribution of totients (1998) | This paper solves several Erdős problems concerning the behavior
of Euler's totient function φ(n). The principal result is a
determination of the order of growth of
of \( V(x) \), the counting function of the image of \( \phi(n) \),
a problem
Erdős considered in a famous 1935 paper.
The order of magnitude is
\[
\frac{x}{\log x}\exp \left[ C_1 (\log\log\log x-\log\log\log\log x)^2
+ C_2\log\log\log x+C_3\log\log\log\log x\right],
\]
for explicitly given constants \( C_1,C_2,C_3 \).
We also show that, for all \(k\), if there is a totient (integer in the image of \(\phi\) ) with exactly \(k\) preimages, then a positive proportion \( c_k V(x) \) of all totients have this property, with \( c_k>0 \) depending on \(k\). (See the next two entries). Moreover, the same results hold if \( \phi \) is replaced by any multiplicative function which has 'similar' behavior at primes, such as the sum of divisors function \( \sigma(n) \). |
| On two conjecture of Sierpinski concerning the arithmetic functions σ and φ (1999) , with Sergei Konyagin | This paper solves a conjecture of W. Sierpiński, posed around 1955 (See A. Schinzel, Elem. Math. 11 (1956), 75-78), that for any positive integer \(k\), there is a number \(m\) so that the equation \(\sigma(x)=m\) has exactly \(k\) solutions \(x\). Here \(\sigma\) is the sum of the positive divisors of \(x\). Sierpiński also conjectured that for every \(k\ge 2\), there is a number \(m\) so that the equation \(\phi(x)=m\) has exactly \(k\) solutions \(x\), where \(\phi\) is Euler's 'totient' function. Here, this conjecture is proved for all even values of k. |
| The number of solutions of φ(n)=x (1999) | This paper solves a conjecture of W. Sierpiński from 1955, that for any positive integer \(k\ge 2\), there is a number \(m\) so that the equation \( \phi(x)=m \) has exactly \(k\) solutions \(x\), where \(\phi\) is Euler's 'totient' function. This conjecture had been previously deduced from Dickson's prime k-tuples conjecture in 1961 by Schinzel, and proved for all even values of \(k\) by the author and Konyagin (see above). In this paper we employ a different method, utilizing the famous theorem of Chen in the following form: for each fixed, even positive integer \(m\), there are at least \(cx/(\log x)^2\) primes \(p\le x\) so that \( (p-1)/m \) is prime or the product of two primes (the proof utilizes both possible conclusions). |
| Vinogradov's integral and bounds for the Riemann zeta function (2002) | We introduce a new method of bounding the Riemann zeta function, based on multidimensional exponential sums over smooth numbers (numbers without large prime factors), and provide the new upper bound \( \zeta(\sigma+it)| \le A|t|^{B(1-\sigma)^{3/2}} \), with \( A=76.2 \) and \( B=4.45 \), valid for \( 1/2 \le \sigma \le 1 \) and \( |t| \ge 1 \). Previously, such a bound was known with \( B=18.8 \) (the value of \( B \) is far more important in applications). Applications include improvements to error terms in the divisor problems, and numerical improvements in the zero-free region for \( \zeta(s) \) (see Zero-free regions for the Riemann zeta function (2002) ) and the error term in the Prime Number Theorem. These remain World Records (as of April, 2018). |
| Sieving by large integers, and covering systems of congruences (2007), with Michael Filaseta, Sergei Konyagin, Carl Pomerance and Gang Yu |
A covering system is a finite set of congruence classes
\( a_j\mod m_j \), \( 1\le j\le k \),
whose union is all the integers.
In this paper, we prove a conjecture of Erdős and Ron
Graham, that for any \( K>1 \), if \( N\) is sufficiently large then there
does not exists a covering system with distinct moduli from
the interval \( (N,KN] \). We also prove a conjecture of Erdős and
John Selfridge, that for any \( K>1 \), if \( N\) is sufficiently large then
there does not exists a covering system with distinct moduli \( > N \)
whose sum of reciprocals is less than \(K\).
In fact, in each of these theorems, the quantity \(K\) may grow as
a function of \( N\) (almost linearly), and each modulus may be be repeated
a small number of times (also slowly growing as a function of \( N\).
(The methods of this paper were later adapted and extended by Bob Hough to solve the famous Minimum modulus covering conjecture of Erdős .) |
| The distribution of integers with a divisor in a given interval (2008) |
This paper solves several central problems of Erdős about the
distribution of divisors of integers.
Let \(H(x,y,z)\) denote the number of integers \(n\le x\) that have a divisor between \(y\) and \(z\).
The main theorem in this paper is a
determination of the exact order of growth of \(H(x,y,z)\) for all \(x,y,z\).
(that is, bounding \(H(x,y,z)\) between two constant multiples of an explicit smooth function
of \(x,y,z\) ). This caps off a program begun by Besicovich in the 1930s, and
earlier estimates of Erdős, Tenenbaum and others. In particular,
in the important special case \( z=2y\), \( H(x,y,2y) \) has order
\[
\frac{x}{(\log y)^{\lambda}(\log\log y)^{3/2}},
\]
uniformly for \( 3\le y\le x^{1/2} \),
where \(\lambda = 1-(1+\log\log 2)/\log 2=0.086071332...\)
One application is the solution of the Erdős "multiplication table problem" (posed in 1955): let \(A(N)\) be the number of distinct entries in an \(N\) by \(N\) multiplication table. Then \(A(N)\) lies between two constant multiples of \[ \frac{N^2}{(\log N)^\lambda (\log\log N)^{3/2}} \] We also determine the order of \(H_r(x,y,z)\), the number of integers \(n\le x\) that have exactly \( r\) divisors between \(y\) and \(z\), in a wide range of the parameters, including the central case \( z=2y \). In this case, we show that for every \( r \ge 1 \), \( H_r(x,y,2y) \) has the same order as \( H(x,y,2y) \), disproving a 1960 conjecture of Erdős. A key tool in the proofs is a new avoidance bound for random walks. The new bounds for random walks was generalized and strengthened in two sequel papers devoted to random walk avoidance theory. The techniques of this paper were also used to provide tight bounds on the probability that a random permutation on n letters has a fixed set of a given size: Permutations fixing a k-set (2016). |
| Common values of the arithmetic functions φ and σ (2010) , with Florian Luca and Carl Pomerance | We prove a 1958 conjecture of Erdős, which states that the ranges of Euler's totient function \( \phi(n) \) and the sum-of-divisors function \( \sigma(n) \) have infinite intersection. Despite ample numerical evidence for the conjecture, this conjecture had only previously been deduced from other (hard) unsolved problems such as the twin prime conjecture and the conjeture that there are infinitely many Mersenne primes. A key innovation in the proof is an upper bound for the number of constrained prime chains from the paper below. |
| Prime chains and Pratt trees (2010) , with Sergei Konyagin and Florian Luca | A prime chain is a sequence \( p_1, p_2, \ldots, p_k \) of primes such that \( p_j | (p_{j+1}-1) \) for each \( j\le k-1 \). We introduce a number of new methods for counting prime chains with various constraints, primarily with the length \( k \) unconstrained. For example, the number of prime chains starting at a given prime \( p \) and ending at a prime less than \( xp \) is, for any \( \varepsilon>0 \), at most \( C(\varepsilon) x^{1+\varepsilon} \) for some constant \( C(\varepsilon) \) ; this bound has an application to common values of the functions \( \phi(n) \) and \( \sigma(n) \) (See above). We also study the distribution of Pratt trees , the tree structure formed by all of the prime chains ending at a given prime \( p \) (and related to the Pratt certificate of primality). We prove the first nontrivial bounds on the height of the Pratt tree, valid for almost all primes \( p\), and also develop a sophisticated stochastic model of the Pratt trees based on branching random walks. This model leads us to conjecture various behaviors of the Pratt trees, in particular that the heights have a tight probability distribution with mean close to \( e \log \log p \). |
| Explicit constructions of RIP matrices and related problems (2011) , with Jean Bourgain, Stephen J. Dilworth, Sergei Konyagin and Denka Kutzarova |
We break a natural barrier in the explicit construction of matrices
useful in compressed sensing.
Let \( \Phi \) be an \( N \times n \) matrix.
Given parameters \( k \) and \( \delta \), if
\[
(1-\delta) \| \mathbf{x} \| \le \| \Phi \mathbf{x} \| \le (1+\delta) \| \mathbf{x} \|\]
for any vector \( \mathbf{x}\in \mathbb{C}^N \) with at most \( k\)
nonzero coefficients, the matrix
\( \Phi \) is said to satisfy the Restricted Isometry Property (RIP) of
order \( k\) and constant \( \delta \).
If the entries of \( \Phi \) are chosen randomly, then with high probability,
\( \Phi \) will satisfy the RIP property if order \( k > cn/\log N. \)
All known explicit constructions do much worse, only producing
the RIP property of order \( k = O(n^{1/2}) \) due to the
use of coherence (requiring the columns to have pairwise small
inner products). In this paper, we construct a new type of matrix that provably satisfies the RIP property with larger order.
Specifically, for some specific \( \varepsilon>0 \), large \( N \)
and any \( n \) satisfying
\( N^{1-\varepsilon} \le n\le N \), we construct RIP matrices
of order \( k = n^{1/2+\varepsilon} \) and constant
\( \delta= n^{-\varepsilon} \).
Key ingredients in our proof are new
estimates for sumsets in product sets and for exponential sums
over sets possessing special additive structure.
In the same paper, we also give a construction of sets of \( n\) complex numbers whose \( k\)-th moments are uniformly small for \( 1\le k\le N \) (Turán's power sum problem), which improves upon known explicit constructions when \( N\) is very large compared to \( n\). |
| On Vinogradov's mean value theorem: strongly diagonal behaviour via efficient congruencing (2014) , with Trevor D. Wooley | I. M. Vinogradov introduced in the 1930s the quantity \( J_{s,k}(N) \), which counts the integer solutions of the system of equations \( \sum_{i=1}^s (x_i^j-y_i^j)=0 \quad (1\le j\le k) \), where \( 1\le x_i,y_i \le N \) for all \( i\) Estimates for the number of solutions are particularly useful in Diophantine problems such as Waring's problem, and have also led to the best known zero-free region for the Riemann zeta function (see above). The Main Conjecture for Vinogradov's system states that \[ J_{s,k}(N) \ll_\epsilon N^\epsilon (N^s + N^{2s-k(k+1)/2}). \] In 2011, Wooley introduced a new, powerful method known as efficient congruencing which led to a proof of this conjecture for \( s \ge k^2 \). In the "small s" range, that is \( s\le \frac12 k(k+1) \), it is conjectured that the "diagonal" solutions (solutions with \(x_1,\ldots,x_s \) a permutation of \(y_1,\ldots,y_s\) ) dominate and consequently that \( J_{s,k}(X) \ll_\epsilon X^{s+\epsilon} \). Until recently this was know only in the trivial case \( s \le k\) and for \( s=k+1 \) . In this paper, we develop a variant of the efficient congruencing method to prove this conjecture in the much wider range \(1\le s\le \frac14 (k+1)^2\). |
| Large gaps between consecutive prime numbers (2016) , with Ben Green, Sergei Konyagin and Terence Tao | We give the first qualitative improvement in 75 years for bounds for large gaps between consecutive primes. Let \( G(x) \) denote the largest gap between consecutive prime numbers which are less than \(x \). A famous lower bound of Rankin from 1938 (itself an improvement upon earlier results of Westzynthius and Erdős) is \[ G(x) \ge c \frac{\log x \log\log x \log\log\log\log x}{(\log\log\log x)^2} \] for some positive constant \(c \). In the next 75 years, only the constant \( c \) was improved, the best result being that of Pintz from 1997 that \( c=2e^{\gamma}-o(1) \). Because the above limit was the natural limitation of a certain circle of ideas, Erdős offered a prize of $10,000 to prove that the constant \(c\) could be taken arbitrarily large (that is, for every \( c\) the above bound holds if \( x\) is sufficiently large in terms of \( c\) ). In this paper, we solve this conjecture. The proof uses a novel probabilistic construction, together with ideas stemming from the recent breakthroughs of Green and Tao for counting solutions of linear equations over primes. |
| Long gaps between consecutive prime numbers (2018) , with Ben Green, Sergei Konyagin, James Maynard and Terence Tao | In this paper, we make a quantitative improvement to the lower bound for \( G(x) \), the largest gap between consecutive primes less than \(x \), see the paper above. We prove that for some constant \( c\) and large \( x\), \[ G(x) \ge c \frac{\log x \log\log x \log\log\log\log x}{\log\log\log x} \] improving the previous bound by a factor of \( \log\log\log x \). There are three main ingredients in the proof. First, we utilize the probabilistic constructions from the earlier paper above. Next, we incorporate a uniform version of the multidimensional prime detecting sieve method of Maynard (used with great acclaim in detecting bounded gaps containing many primes). thirdly, we prove a generalization of a hypergraph covering theorem of Pippenger and Spencer, which allows for an essentially optimal means of translating such estimates into a result on large gaps between primes. |
| Long gaps in sieved sets, 2019+ . Kevin Ford, Sergei Konyagin, James Maynard, Carl Pomerance and Terence Tao | We create a new method for detecting large gaps in sequences of integers where an average of one residue class per prime has been omitted (sifted out). As a consequence, we deduce that for any irreducible polynomial \( f: \mathbb{Z}\to\mathbb{Z} \) with positive leading coefficient, if \(x\) is large then there are strings of \( (\log x)(\log\log x)^c \) consecutive values of \( n \in [1,x] \) for which \( f(n) \) is composite. Here \(c\) is a positive quantity depending only on the degree of \(f\). Previously, only gaps of size \( \gg \log x \) were known to exist, following a simple argument. |
| Equal sums in random sets and the concentration of divisors, 2019+ . Kevin Ford, Ben Green and Dimitris Koukoulopoulos | Let \(A\subset \mathbb{N}\) be a random set, where \(n\) is included in \(A\) with probability \(1/n\). We study the problem of determining for which intervals \( [X,Y] \), the subset \( A \cap [X,Y] \) will have \(k\) equal subset sums. We apply our theorems to prove new lower bounds on the maximum concentration of divisors of integers, of permutations and of polynomials over a finite field. In particular, we disprove a conjecture of Maier and Tenenbaum from 2009 about the normal order of the Erdős-Hooley function \( \Delta(n)\), which is the maximum number of divisors of \(n\) lying in any interval \( (u,eu] \) of logarithmic length 1, by showing that \( \Delta(n) \ge (\log\log n)^{B+o(1)} \) for almost all \(n\), where \(B\) is a specific constant which is about 0.35332. Our analysis of the subset sum problem involves linear algebra on the \(k\)-dimensional unit cube \( \{0,1\}^k \) and an optimisation problem over measures on \( \{0,1\}^k \). We believe that our results are asymptotically sharp, that is, that \( \Delta(n)=(\log\log n)^{B+o(1)} \) for almost all \(n\). |
| Long gaps in sieved sets, 2019+ . Bill Banks, Kevin Ford, and Terence Tao | We introduce a new model of the primes consisting of integers that survive the sieving process when a random residue class is selected for every prime modulus below a specific bound. This differs fundamentally from the well-known model of Cramer and the refined model of Granville. From a rigorous analysis of this model, we obtain heuristic upper and lower bounds for the size of the largest prime gap in the interval \( [1,x]\). Our results are stated in terms of the extremal bounds in the interval sieve problem. In particular, if the true order of the interval sieve problem is smaller than expected (this occurs, e.g., if Siegel zeros of Dirichlet L-functions exist), we predict that the largest gap between primes below \(x\) grows faster than \( c\log^2 x \) for any positive \(c\). The same methods also allow us to rigorously relate the validity of a uniform version of the Hardy-Littlewood conjectures for an arbitrary set (such as the actual primes) to lower bounds for the largest gaps within that set. |
| Honors and Awards | |
| Paul Erdos $10,000 prize for my work on prime gaps | 2016 |
|---|---|
| Three papers with Featured Reviews in
Mathematical Reviews , #6, #10 and #18 in my Publication List |
1998-2002 |
| supported by NSF Individual grants 2000-present. | 2000-present |
| Senior Personnel on an NSF RTG grant, "Research in Combinatorics", $1,788,257. | 2020-2025 |
| Conference grants. 2007--09 (NSA, NSF. Co-PIs
B. Berndt, H. Diamond, M. Filaseta), 2014--15 (NSF, Co-PI B. Berndt), 2019 (NSF, NSA, Co-PI). |
2007-2019 |
| Fellow of the American Mathematical Society | 2013 |
| Professional Activity | |
| Editor of the London Mathematical Society Journal and bulletin. | 2022-present |
|---|---|
| Editor of the journal Research in Number Theory. | 2020-present |
| SASTRA Ramanujan Prize selection committee. | 2019-2020 |
| Collaborating editor, Problem section of the American Mathematical Monthly. | 2000-2005 |
| On the Board of Directors, Number Theory Foundation. | 2008-present |
| Co-organizer, Illinois Number Theory Conferences | 2007, 2009, 2014, 2015, 2019. |
| Selected Invitations | |
|
International
Number Theory Conference dedicated to Professor Andrzej Schinzel on the occasion of his 60th birthday, Zakopane, Poland. |
1997 |
|---|---|
|
Invited plenary lecture, The Millennial Conference on Number Theory, University of Illinois. |
2000 |
| Research in Pairs program, Mathematisches Forschungsinstitut Oberwolfach, Germany. 3 weeks. | 2002 |
| Moscow Lomonosov State University, Russia. seminar. | 2003 |
| Elementare und Analytische Zahlentheorie; Mathematisches Forschungsinstitut Oberwolfach, Germany. | 2003 |
| Theory of the Riemann Zeta and Allied Functions, Mathematisches Forschungsinstitut Oberwolfach, Germany. | 2004 |
| Workshop Gaps between primes, American Institute of Math., Palo Alto, Calif. | 2005 |
| 1-month invitation to the Universite Bordeaux 1, Bordeaux, France. | 2006 |
| Principal lecturer at the workshop Anatomy of Integers, CRM, University of Montreal, Canada. Series of three 1-hour lectures. |
2006 |
| Analytic Number Theory, Mathematisches Forschungsinstitut Oberwolfach, Germany. | 2008 |
| Univ. Paris 7, seminars. | 2008, 2009 |
| Integers Conference, Carrollton, GA. (invited 1-hour plenary lecture) | 2009 |
| Dartmouth College, Colloquium. | 2009 |
| University of Pennsylvania, Colloquium. | 2010 |
| Journees Arithmetique, Vilnius, Lithuania. Invited plenary lecture. | 2011 |
| Invited Address, AMS meeting, University of Iowa. | 2011 |
| 43rd ACM Symposium on Theory of Computing (STOC '11), San Jose, California. | 2011 |
| Workshop (concentration week) on Greedy
Algorithms in Banach spaces and Compressed Sensing, Texas A&M University, invited plenary lecturer (3 lectures). |
2011 |
| Erdos Centennial, Budapest, Hungary | 2013 |
| Analytic Number Theory, Mathematisches Forschungsinstitut Oberwolfach, Germany. | 2013 |
| University of Bristol (2 weeks). | 2014 |
| Oxford University (3 weeks). | 2014 |
| Steklov Institute of Mathematics, Moscow, Russia (11 days) | 2015 |
|
Mathematical Sciences Research Institute , Special program on Analytic Number Theory, 10 weeks. |
2017 |
| Kansas State Univ., Dressler Lecture (invited lecture series). | 2017 |
| Simons-CRM Professor, Montreal, Canada. 3 weeks. | 2018 |
| Visiting Fellow, Magdalen College, Oxford, 3 months. | 2019 |
| Mittag-Leffler Institute, Stockholm. Programme in number theory, 3 months. | 2021 |
| University of Oxford. 2 weeks. | 2022 |
| Institute For Advanced Study, Princeton. 2 weeks. | 2022 |