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 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).
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 10^{7} 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). |
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\).
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. |