Proc. of the Amer. Math. Soc. 119 (1993), no. 3, 1019-1020.
Small errata: Must add the hypothesis \( d\ne 1, d\ne -1 \).
J. London Math. Soc. (2) 51 (1995), 14-26.
J. Amer. Math. Soc. 9 (1996), 919-940.
Addendum and Corrigendum , J. American Math. Soc. 12 (1999), 1213.
Abstract: We prove that all sufficiently large integers \( n \) have a respresentation \( n = x_2^2 + x_3^3 + \cdots + x_{15}^{15} \), where \( x_2,\ldots,x_{15} \) are positive integers. This is the main result of my Ph.D. thesis.
International Mathematical Research Notices 1995, 155-171.
Abstract: 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 Ramanujan Journal 2, no. 1-2, (1998), 59-66. Reprinted in Analytic and elementary number theory: A tribute to mathematical legend Paul Erdős , (K. Alladi, P. D. T. A. Elliott, A. Granville and G. Tenenbaum, eds.), Springer, 1998.
Note: the PDF version here is the updated 2012 version, with various corrections and simplifications to the original paper.
The Ramanujan Journal 2, no. 1-2. (1998), 67-151. Reprinted in Analytic and elementary number theory: A tribute to mathematical legend Paul Erdős , (K. Alladi, P. D. T. A. Elliott, A. Granville and G. Tenenbaum, eds.), Springer, 1998.
Abstract: A totient is a number in the image of Euler's function \( \phi(n) \). This paper is a comprehensive investigation of the set of totients, solving a number of long-standing open problems. The primary result is a determination of the precise order of growth of \( V(x) \), the number of totients which are at most \( x\). This follows earlier works on the problem going back to 1929 by Pillai, Erdős, Hall, Pomerance and the most recent work of Maier and Pomerance (1988). The formula is rather complex to write down. The proof reveals fine detail about the normal multiplicative structure of a typical totient. We also solve several problems about \( A(m) \), the number of solutions of \( \phi(n)=m \), and \( V_k(x) \), the number of integers \( m\le x \) for which \( A(m)=k \). We show that for every \( k\), either \( V_k(x) \) is identically zero or \( V_k(x) \) has the same order or growth as \( V(x) \), i.e., a positive proportion of totients have multiplicity \( k\) (in fact the latter occurs for all \( k>1 \); see papers No. 7 and 10 below). Moreover, the same results hold if \( \phi \) is replaced by another multiplicative function which has 'similar' behavior at primes, such as the sum of divisors function \( \sigma(n) \). Finally, we study the Carmichael Conjecture (dating to 1907) which states that \( A(m)=1 \) cannot hold for any \( m\). Making use of a large-scale computation, we show that it is true for \( m< 10^{10^{10}} \).
Abstract: Around 1955, W. Sierpiński conjectured 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 \). In this paper, the conjecture is proved. Sierpiński also conjectured that for every \( k>1 \), 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 is proved for all even values of \( k \). The proof includes a novel combinatorial device, plus a sieve whose desired output is products of more than one prime (as opposed to prime numbers themselves). See also the companion paper No. 10 below.
In the book Number Theory in Progress (Zakopane, Poland 1997; Kálmán Györy, Henryk Iwaniec, Jerzy Urbanowicz, eds), de Gruyter (1999), 805-812.
Unpublished. An earlier version was "published" in the Smarandache Notions J. without the author's permission, and subsequently reviewed by Math Reviews.
Annals of Math. 150 (1999), 283-311.
Abstract: Around 1955, W. Sierpiński conjectured that for any positive integer \( k>1 \), 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 was proved for all even values of \( k \) by the author and Konyagin (see paper No. 7 above). In this paper, the conjecture is proved for every \( k \) by a different method. Letting \( A(m) \) denote the number of solutions of \( \phi(x) = m \), the proof uses induction, using a known integer \( m \) with \( A(m)=k \) to construct a number \( m' \) with \( A(m')=k+2 \) (it is similar to a method introduced in paper No. 6 above). One of the main tools is the famous theorem of Chen, used 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.
J. Number Theory 81 (2000), 335-350.
J. London Math. Soc. (2) 61 (2000), 671-680.
Illinois J. of Math. 44 (2000), 633-643.
J. Number Theory 87 (2001), 54-76.
Periodica Math. Hung. 43 (1-2), (2001), 15-29.
Acta Arithmetica 100 (2001), 297-314.
Duke Math. J. 113 (2002), 313-330.
Abstract: Let \( \pi_{q,a}(x) \) denote the number of primes \( \le x \) in the progression \( a \bmod q \). We study subtle inequities in these functions, with \( q \) fixed and variable \( a \) (sometimes called 'prime race problems'). It is known unconditionally for many triples \( (q,a,b) \) that the difference \( \pi_{q,a}(x) - \pi_{q,b}(x) \) changes sign infinitely often, although there may be a pronounced bias toward one sign (first observed by Chebyshev in 1853). Similar results for the comparison of three or more prime counting functions all require the assumption of ERH (extended Riemann Hypothesis for the Dirichlet L-functions modulo \( q \) ). In this paper we show that the assumption of ERH is, in a sense, necessary. That is, we prove, for any quadruple \( (q,a,b,c) \) with \( a,b,c \) co-prime to \( q \), that the existence of certain hypothetical configurations of zeros of Dirichlet L-functions lying off the critical line imply that one of the six possible orderings of the three functions \( \pi_{q,a}(x), \pi_{q,b}(x), \pi_{q,c}(x) \) does not occur at all for large enough \( x \).
Proc. London Math. Soc. 85 (2002), 565-633. List of errata .
Abstract: We give a new upper bound for the Riemann zeta function near the line \( \Re s = 1 \). Specifically, we prove the 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 to zero-free regions for \( \zeta(s) \); see paper No. 19 below. The main new ingredient is the utilization of multidimensional exponential sums over smooth numbers (numbers without large prime factors).
In the book Number Theory for the Millenium (Urbana, IL, 2000) (M. A. Bennett, B. C. Berndt, N. Boston, H. G. Diamond, A. J. Hildebrand and W. Phillip, eds), vol. II (2002), 25-56.
Combinatorica 23 (2) (2003), 263-281.
Acta Arithmetica 110 (2003), no. 4, 259-274
Proceedings of the session in analytic number theory and Diophantine equations (Bonn, January-June 2002), Bonner Mathematische Schiften, Nr. 360 (D. R. Heath-Brown, B. Z. Moroz, editors), Bonn, Germany, 2003, 40 pages.
Canadian Math. Bulletin 47 (3), (2004), 358-368.
Trans. Amer. Math. Soc. 357 (2005), 1663-1674.
Amer. Math. Monthly 111 (2005), 277-278.
Notes: This file corrects a few typos in the published version.
J. reine angew. Math. 579 (2005), 145-158.
Proc. Amer. Math. Soc. 133 (2005), 3463-3468.
Monatshefte Math. 146 (2005), 1-19.
J. Amer. Math. Soc. , 20 (2007), 495-517.
Abstract: A covering system is a finite set of congruence classes, say \( a_j\mod m_j, 1\le j\le k \), whose union is all the integers. Of particular interest are those covering systems with distinct moduli \( m_j \). The concept was invented by Erdős, who has a number of famous problems about them. 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 larger than \(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 \(s\) times, with \(s\) slowly growing as a function of \(N\). These are accomplished using new methods of bounding the density of the union of congruence classes, when the moduli are not pairwise coprime.
Quart. J. Math. Oxford 58 (2007), 187-201.
Funct. Approx. Comm. Math. 37.1 (2007), 119-129.
Stat. Prob. Letters 78 (2008), 84-89.
Monatshefte Math. 153 (2008), 205-216.
Annals of Math. (2) 168 (2008), 367-433.
Abstract: 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)^{\mathcal{E}}(\log\log y)^{3/2}}, \] uniformly for \( 3\le y\le x^{1/2} \), where \(\mathcal{E} = 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)^{\mathcal{E}} (\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 sequel papers devoted to random walk avoidance theory (nos. 31, 33, 42 in this list).
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).
Anatomy of Integers (Jean-Marie De Koninck, Andrew Granville, and Florian Luca, eds), CRM Proc. and Lect. Notes 46 , Amer. Math. Soc., Providence, RI, 2008, 65-80. Updated, simplified version (2012)
Abstract: This is an alternative and simplified proof of a central case of the main theorem of paper No. 34 above, namely the determination of the order of growth of \( H(x,y,2y) \), the number of integers \( n\le x \) that have a divisor in \( (y,2y] \). This paper will be periodically updated, as I or others come up with simplifications.
Math. Proc. Cambridge Phil. Soc. 145 (2008), 27-41.
Acta Arithmetica 133 (2008), 199-208.
Int. J. Number Theory 4 (2008), 819-826.
Math. Annalen 343 (2009), 487-505.
Trans. Amer. Math. Soc. 361 (2009), 2263-2275.
Bull. Austr. Math. Soc. 79 (2009), 455-463.
Prob. Th. Rel. Fields 145 (2009), 269-283.
Bull. London Math. Soc. 41 (2009), 676-682.
Bull. London Math. Soc. 42 (2010), 478-488.
|
Abstract: Do the ranges of Euler's totient function \( \phi \) and the sum-of-divisors function \( \sigma \) have infinite intersection? In 1958, Erdős conjectured that they do. This follows trivially from either of two other famous conjectures, the twin prime conjecture (if \( p\) and \( p+2 \) are both prime, then \( \phi(p+2)=p+1=\sigma(p) \) and the conjecture that there are infinitely many Mersenne primes (if \( 2^p-1 \) is prime, then \( \phi(2^{p+1}) = 2^p = \sigma(2^p-1) \) . Both of these conjectures are out of reach. Numerical evidence indicates that intersections are plentiful, however, in fact below 107 about half of all numbers in the range of \( \phi \) are also in the range of \( \sigma \). In this paper, we prove Erdős conjecture unconditionally. One key tool is an upper bound for the number of constrained prime chains from paper No. 47 (below). |
|
Proc. Amer. Math. Soc. 138 (2010), 4177-4185.
Michigan Math. J. 59 (2010), 313-328.
Geom. Funct. Anal. 20 (2010), 1231-1258.
Abstract: 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 \).
Experim. Math. 19 (2010), 385-398.
INTEGERS (Proceedings of the INTEGERS conference honoring Melvyn Nathanson and Carl Pomerance) 11A (2011), Article 9.
Duke Math. J. 159 (2011), 145-185.
Abstract: 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\).
Proceedings of the 43rd Symposium on the Theory of Computing (STOC '11) (2011), 637-644.
Abstract: This is a summary of the main ideas from the previous paper No. 50. In addition, some new ideas are inserted in a key step which allows one to greatly improve the value of the constant ε appearing in the main theorem (it is still rather tiny, as it depends on a bound in additive combinatorics which is expected to be far from optimal).
Acta Math. Hungarica 133 (2011), 251-271.
International Mathematical Research Notices 2012 , 4051-4061.
Algebra and Number Theory 6 (2012), no. 8, 1669-1696.
Abstract: Computational evidence suggests that a positive proportion of the integers in the range of Euler's function \( \phi(n) \) are also in the range of the sum-of-divisors function \( \sigma(m) \). In fact, up to \( 10^8 \), roughly half of all integers in the range of \( \phi \) are also in the range of \( \sigma \) and vice-versa. This is misleading, however. In this paper, we prove that the intersection of the two ranges has relative density zero inside the range of \( \phi \) and inside the range of \( \sigma \). The proof requires the full structure theory of typical \( \phi- \) and \(\sigma\)-values from paper No. 6 above.
Moscow J. Comb. Number Th. 2 (2012), 297-312.
Ann. Appl. Prob. 23 , (1) (2013), 283-307.
Colloq. Math. 130 (2013), 127-137.
Acta Arithmetica 157 (2013), 381-392.
Quart. J. Math. Oxford 64 (2013), 1091-1098.
Math. Comp. 83 (2014), no. 287, 1447-1476.
International Mathematical Research Notices 2014 (2014), 2955-2971.
Acta Mathematica 213 (2014), 199-236.
Abstract: 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\).
Algebra and Number Theory 8 (2014), 2009-2025.
Notes: A few small typos have been corrected in the version here.
Abstract: We show that the counting function of the range of Carmichael's \(\lambda\)-function is \( x (\log x)^{-\mathcal{E}+o(1)}\), where \( \mathcal{E} = 1 - \frac{1+\log\log 2}{\log 2} = 0.086071332\ldots\) is the same constant appearing in the multiplication table problem (see paper #34 above).
Compositio Math. 151 (2015), 230-252.
in the book Analytic Number Theory, in honor of Helmut Maier's 60th birthday, C. Pomerance and M.Th. Rassias (eds.), Springer-Verlag, 2015, pp. 83-92.
in the book Analytic Number Theory, in honor of Helmut Maier's 60th birthday, C. Pomerance and M.Th. Rassias (eds.), Springer-Verlag, 2015, pp. 93-100.
Annals of Math. 183 (2016), 935-974.
Abstract: 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) states that \[ 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.
Media publicity for this paper:
- Article in Quanta Magazine ; reprinted in Wired.com
- Featured in articles about Erdős (Reflections on Paul Erdős on His Birth Centenary), AMS Notices February 2015 and March 2015
- Article in AMS Notices, May 2017 , by James Maynard describing the result.
- A NUMBERPHILE video, produced by the Mathematical Sciences Research Institute
IMRN 2016 , no. 21, 6713-6731.
Abstract: Adapting methods from my paper The distribution of integers with a divisor in a given interval, we determine the exact order of the number of permutations in \(S_n\) which have a fixed set of size \(k\), uniformly in \(n,k\). We say that \(\sigma\in S_n\) has a fixed set of size \(k\) if there is a subset of \( \{1,\ldots,n\}\) which is left invariant by \(\sigma\). Equivalently, there is a subset of the cycles in \(\sigma\) with sum of lengths equal to \(k\).
Discrete Analysis 2016: 12 , 34 pages.
Duke Math. Journal 166 (2017), no. 8, 1573-1590.
Abstract: Permutations \(\sigma_1,\ldots,\sigma_r\) are said to invariably generate the symmetric group \(S_n\) if any conjugates \(\sigma_1',\ldots,\sigma_r' \) generate \(S_n\). Pemantle, Peres and Rivin showed that with probability at least \( \delta \), a positive absolute constant, four random permutations of \(S_n\) invariably generate \(S_n\). We show that three random permutations do not suffice, that is, the probability that random \(\sigma_1,\sigma_2,\sigma_3\) in \(S_n\) generate \(S_n\) tends to zero as \(n\to\infty\).
Acta Arithmetica 178 (2017), no. 2, 163-180.
Forum Mathematicum 29 (2017), no. 2, 347-355.
Bulletin of the London Math. Soc. 49 , no. 1, (2017), 1-9.
J. Amer. Math. Soc., 31 (2018), no. 1, 65-105.
| Abstract: 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 paper #67 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 No. 67 above. Next, we incorporate a uniform version of the multidimensional prime detecting sieve method of Maynard which was earlier used to show that there are 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. |
|
in the book "Irregularities in the distribution of prime numbers", (J. Pintz, M. Th. Rassias, eds.), Springer, 2018, p. 1-21.
Abstract: Under the assumptions of GRH and LI (linear independence of imaginary parts of Dirichlet L-functions), we show that for any large modulus \(q\) and \( \log q \le r \le q^{1/50} \), there are residues \( a_1,\ldots,a_r \bmod q\) so that some ordering of the prime counting functions \( \pi(x;q,a_i) \) occurs with density at most \( (1/r!)\exp\{ - c r /\log q \} \), and there is another set of residues \( b_1,\ldots,b_r \bmod q \) such that some ordering of the prime counting functions \( \pi(x;q,b_i) \) occurs with density at least \( (1/r!)\exp\{ c r /\log q \} \). Here \( c\) is a positive, absolute constant. As there are \( r! \) orderings of these sets of prime counting functions, this shows an extreme bias towards or away from certain orderings.
Abstract: 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.
Abstract: We show that for any positive integer \(\ell\), the set of integers \(n\) satisfying \( n^\ell | \binom{2n}{n} \) has a positive density. We also determine asymptotically the counting function of \(n\) such that \( (n,\binom{2n}{n})=1 \).
Abstract: 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\).
Abstract: 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, 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.
Abstract:
We show that for any integer irreducible integer valued polynomial \( f(x) \), if \( x \)
is large enough then there is a interval of at least \( (\log x)(\log\log x)^{1/835} \)
consective values of \( n \) from \( [1,x] \) so that \( f(n) \) is composite
for all \( n \) in the interval. This improves the main theorem of paper #80
above, where a similar result was proved bu with exponent \( c(f) \) in place of
1/835, where \( c(f) \) depends on \( f \) and can be exponentially small in
the degree of \( f \).
Abstract:
We develop an analog for shifted primes of the Kubilius model of prime factors of integers.
We prove a total variation distance estimate for the difference between the model and actual
prime factors of shifted primes, and apply it to show that the prime factors of shifted
primes in disjoint sets behave like independent
Poisson variables. As a consequence, we establish a transference principle between the
anatomy of random
integers \( \le x \) and of random shifted primes \( p + a \) with \( p \le x \).
Abstract:
We develop the foundations of a general framework for producing optimal upper and
lower bounds on the sum \( \sum_p a_p \) over primes \( p \), where
\( (a_n) \) is an
arbitrary non-negative sequence supported on \( [1,x] \) and
satisfying Type I and Type II estimates.
Our lower bounds on \( \sum_p a_p \) depend on a new
sieve method, which is non-iterative and uses all of the Type I and Type II information
at once. We also give a complementary general procedure for constructing sequences \(
(a_n) \)
satisfying the Type I and Type II estimates, which in many cases proves that our lower
bounds on \( \sum_p a_p \) are best possible. A key role in both the sieve method and
the construction method is played by the geometry of special subsets
of \( \mathbb{R}^k \).
This allows us to determine precisely the ranges of Type I and Type II estimates for which
an asymptotic for \( \sum_p a_p \) is guaranteed, that a substantial Type II range is always
necessary to guarantee a non-trivial lower bound for \( \sum_p a_p \), and to determine the
optimal bounds in some naturally occurring families of parameters from the literature. We
also demonstrate that the optimal upper and lower bounds for \( \sum_p a_p \) exhibit many
discontinuities with respect to the Type I and Type II ranges, ruling out the possibility of
a particularly simple characerization.
Abstract:
Let \( \delta(p) \) tend to zero arbitrarily slowly as \( p \to \infty \).
We exhibit an explicit set S of
primes p, defined in terms of simple functions of the prime factors of \( p-1 \),
which contains almost all primes and for which
the least primitive root of \( p \) is \( O(p^{1/4-\delta(p)}) \) for all \( p\in S \).