Category Archives: Number Theory

A lower bound for the least prime in an arithmetic progression

Number Theory,

Junxian Li, Kyle Pratt, and I recently uploaded our paper A lower bound for the least prime in an arithmetic progression to the arXiv.

Here is a file where the heuristics considered in section 2 of the paper are developed in a slightly simpler situation.

Given a positive integer k and a \ell coprime to k, define p(k , \ell) to be the smallest prime equivalent to \ell modulo k. We are interested in the worst case behavior, that is P(k) := \max_{(\ell , k) = 1} p(k , \ell). Thus P(5) = 19 and P(12) = 13. In particular we are interested in lower bounds for P(k) for large k. An elementary observation, due to Pomerance, in Theorem 1 shows roughly that to find lower bounds for P(k), it is enough to find lower bounds for the Jacobsthal function (the roughly will be explained below). For an integer m, the Jacobsthal function, g(m), is the largest difference between consecutive integers coprime to m.

In recent work on Long gaps between primes by Ford, Green, Konyagin, Maynard, and Tao, they improve upon lower bounds for g(m) where m is the product of the first u primes (they also mention the connection to the least prime problem; indeed it was Kevin Ford who originally introduced us to the problem). The key difference in the current problem is that we seek lower bounds for g(m) where m is the product of the first u primes that are coprime to k. Our main new idea is to modify these sieve weights of Maynard used in the work of Ford, Green, Konyagin, Maynard, and Tao. We outline our approach in section 4 of our paper.

We finish by taking some time here to discuss smooth number estimates, which is perhaps the most important input to our work as well as all previous work on large gaps between primes (Westzynthius, in 1931, was the first to realize this connection). For x \geq y \geq 1, let \Psi(x,y) be the number of integers \leq x whose prime factors are all \leq y. Thus \Psi(x,2) is the number of powers of 2 that are at most x and \Psi(x , 3) is the number of integers of the form 2^a 3^b \leq x. Estimating \Psi(x,2) is straightforward and for y is fixed, one can obtain an asymptotic for \Psi(x,y) by counting lattice points in a simplex, as I describe in this previous blog post.

For our current problem, it is crucial that we are allowed to let y depend on x. The important fact is that \Psi(x,y) is much smaller than expected (by sieve theory heuristics). Rankin, in 1938, in his work on gaps between primes (see also: these set of notes) improved upon smooth number estimates to obtain better lower bounds for large gaps between primes. Westzynthius’ strategy, along with Rankin’s estimates, are still the starting points for current methods of constructing large gaps between primes.

 

 

 

Gauss Sums and Hausdorff-Young

Harmonic Analysis, Number Theory, ,

GaussSums-Hausdorff Young

Let 1 \leq p \leq 2. The classical Hausdorff-Young inequality asserts that for any f \in L^p(\mathbb{T}), there is a A_p (equal to 1 in the present case) such that ||\hat{f}||_{p/(p-1)} \leq A_p||f||_p. There are examples that show one cannot allow p > 2. In the above pdf, we provide a construction, motivated from number theory, that shows p > 2 is impossible in the Hausdorff-Young inequality. One can think of this as a pseudo-random approach, as opposed to the random approach employed by, for instance, an application of Khintchine’s inequality.

We will first prove a discrete analog. For those a bit rusty, you are invited to check out my notes on the discrete Fourier transform.

I’d like to thank to of my fellow graduate students, Derek Jung and Xiao Li, for pointing out some mistakes in a previous version. I would also like to thank Sergei Konyagin for making me aware of the Shapiro-Rudin polynomials.

Lastly, I have not seen this example in the literature. If you have seen it, please let me know.

Counting lattice points

Number Theory

LatticePoints

The above pdf contains some notes I wrote up on using (for the most part) elementary methods to count lattice points in dilates of the unit ball of \ell_p(\mathbb{R}^d). There are some connections to the Dirichlet kernel, Waring’s problem, smooth number estimates, and probability.

Motivated by a nice talk in the graduate student analysis seminar provided by Hadrian Quan, I make a quick connection to a particular case of Weyl’s law.