Distinct consecutive r-differences

Junxian Li, a fellow graduate student at UIUC, and I just uploaded our paper On distinct consecutive r-differences to the arXiv.

Our goal is to show for finite A \subset \mathbb{R} with special structure |A+A| \gg |A|^{1 + \delta} for some positive \delta (here we adopt Vinogradov’s notation). Note that |A+A| = 2|A| -1 for arithmetic progressions, so we really need to make assumptions about the structure of A.

Motivated by a paper of Solymosi, we introduce the notion of distinct consecutive r-differences. We say A \subset \mathbb{R} has distinct consecutive r-differences if (a_{i+1} - a_i , \ldots , a_{i+r} - a_{i +r -1}) are distinct for 1 \leq i \leq |A|-r.

Assume A has distinct consecutive r-differences. We show that for any finite B \subset \mathbb{R}, one has |A+B| \gg |A||B|^{1/(r+1)} and that this inequality is sharp in such generality. We wonder if one can improve upon this if B= A and ask what is the largest \theta_r such that |A+A| \gg |A|^{1 + \theta_r/(r+1)}. The above result implies \theta_r \geq 1, while in our paper we use de Bruijn sequences to show \theta_r \leq 2.

When A has additive structure, the results from our paper suggest that A should have few distinct consecutive r-differences. We investigate two of these cases show that these A have very few distinct consecutive differences. In the process, we generalize Steinhaus’ 3-gap theorem as well as a result of Slater concerning return times of irrational numbers under the multiplication map of the Torus.


Getting a lower bound for an L1 norm using higher moments

I would like to discuss a principle that came up in this recent talk of Adam Harper as well as my own research with Burak Erdogan.

Let f : \Omega \to \mathbb{C} be a function on some measure space with measure \mu (for instance \Omega = [0,1] or a finite set).

Often one is interested in finding lower bounds for the L^1 norm of f, that is \int_{\Omega} |f| d\mu, but has no way to directly estimate it. As a toy example, we can consider g_N: \mathbb{R} / \mathbb{Z} \to \mathbb{C} via g_N(x) = \sum_{1 \leq n \leq N} e(x n^2). Estimating the L^1 norm directly seems hard.

But sometimes, we are able to estimate higher L^p norms of f. This is useful to our original problem, since an application of Holder’s inequality reveals that a lower bound on the L^2 norm and an upper bound on the L^4 norm gives a lower bound on the L^1. To see this, note \int |f|^2 \leq (\int |f|^4 )^{1/3} (\int |f|)^{2/3}.

We can apply this idea to our original example. Parseval’s identity gives that \int |g_N|^2 = N, while orthogonality and the divisor bound give that \int |g_N|^4 \lesssim_{\epsilon} N^{2 + \epsilon}. This gives \int |f| \gtrsim_{\epsilon} N^{1/2 - \epsilon} and is expected by the heuristic that a typical exponential sum should be about square root of the length of the sum.

My intuition is the following. Suppose the measure space is a probability space. Then \int |f| \leq (\int |f|^2)^{1/2}. We are basically trying to reverse this inequality. Equality holds when f is constant, that is f is not too concentrated. The upper bound on the L^4 norm of f implies that indeed f is not too concentrated.

We mention that there is nothing too special about the exponents 2 and 4 chosen for the above discussion (although they are convenient for the specific example I chose).

Gaps in prime-like sets

This post was inspired by a question of Trevor Wooley after a talk of James Maynard at MSRI. He asked what was known for lower bounds of large gaps between integers that have a representation as the sum of two squares. We assume some familiarity with the large gaps between primes problem.

A theorem of Fermat asserts that an integer, n is represented by the sum of two squares if and only if all the prime factors of n equivalent to 3 modulo 4 appear with an even power.

For technical simplicity, we consider the set of integers that simply have no prime factors equivalent to 3 modulo 4, but one may extend the considerations below to the original question.

The size of such a set is proportional to x / \log^{1/2} x. Thus the average gap is \asymp \log^{1/2} x and so the average gap is at least this big.

Surprisingly, there is an easy argument that yields a gap of size \gg \log x. We sketch it here. For each prime p \leq \log x equivalent to 3 modulo 4, choose a residue class a_p \pmod p. Using a greedy algorithm to choose the a_p, we may sieve out the integers in \{1 , \ldots , y\} for y \ll \log x. By the Chinese remainder theorem, there is a t \leq x such that t = - a_p \pmod p for all the relevant p. Thus t+1 , \ldots , t+y all contain a prime factor equivalent to 3 modulo 4, as desired.

What should one expect? Adopting the Cramer model, we expect that there should be gaps of size at least \asymp \log^{3/2 - \epsilon} x. We give a rough sketch as to why one should expect this. Let S = \{ n \leq x : p|n \implies p \neq 3 \pmod 4\}. We suppose that an integer is chosen random with probability q = 1 / \log^{1/2} x. Then the probability that n+1 , \ldots , n_h \notin S is (1- q)^h which is well approximated by e^{-qh}. If h \asymp (\log x) / q, then this is around the number of choices for n. One can see the Cramer model worked out more carefully here.

Fix q and a coprime to q. Now we consider the set S = \{n \leq x : p|n \implies p \equiv a \mod q\}. The Cramer model, as above, suggests that there should be gaps between elements of S that are \leq x of size \log^{1 + 1/\phi (q) - \epsilon } x. Nevertheless we may utilize the trivial bound above to obtain gaps of size \log x. Thus, for these S, we can come arbitrarily close (i.e. an arbitrarily small power of log) to the lower bounds associated to Cramer’s conjecture.

Note for primes, we are nowhere near Cramer’s conjecture. Ford, Green, Konyagin, Maynard, and Tao have the best lower bound. Things look worse for upper bounds, as no one knows how to improve upon a power of x for the primes or any of the sets mentioned in this post (even if one assumes the Riemann hypothesis).

A question about triangles

Is a triangle uniquely determined by its area, perimeter, and sum of the reciprocals of its angles?

This is an open question, though it is supported by numerical evidence. This question is related to the inverse spectral problem of the Laplace operator in spectral geometry. In particular, the area, perimeter, and sums of the reciprocals of the angles are the first three eigenvalues of the Laplace operator. Note that a triangle, up to congruence, is determined by three pieces of information (for instance, the SSS theorem from high school geometry), which is why it makes sense to require at least three eigenvalues. We remark that all of the eigenvalues of the Laplace operator uniquely determine a triangle

On the other hand, right triangles are determined by two pieces of information (say the two legs). Thus one might guess that a right triangle is determined by the first two eigenvalues of the Laplace operator. Indeed, this is the case as we outline below that the area and perimeter of a triangle determine a right triangle.

{\bf Proposition.} Suppose T is a right triangle with area A and perimeter P. Then the two legs of the triangle are the solutions of the quadratic polynomial -2P x^2 + (P^2 + 4A) x - 4AP = 0.

{\it Proof.} Let x,y,z be the side lengths of T, where z is the hypotenuse. Then xy = 2A ,  x + y + z = P , x^2 + y^2 = z^2. The proposition follows from a modest computation. \spadesuit

For fun, one can check the solutions quadratic polynomial in the above proposition are invariant under the map x \mapsto 2A / x.

An introduction to Vinogradov’s mean value theorem

VMT-Intro: pdf file containing the post

A link to a talk I gave on the topic. The talk is much more elementary than the blog post.


Vinogradov’s mean value theorem (recently proved by Bourgain, Demeter and Guth) is a beautiful problem in the intersection of number theory and harmonic analysis.

As a problem in number theory, the mean value theorem requests to show most of the solutions to a certain system of Diophantine equations of the form f_j(\vec{x}) = f_j(\vec{y}) for some integral polynomials f_1 , \ldots , f_k are of the form \vec{x} = \vec{y}. As a problem in harmonic analysis, the mean value theorem requests for an upper bound for the L^p norm of a certain function. These two problems turn out to be equivalent, as explained in the pdf linked at the top of the post, thanks to Fourier analytic identities.

One goal in the above pdf is to understand the nature of the so called “critical exponent.” Interpolation reveals that Vinogradov’s mean value theorem follows from an L^{k(k+1)} bound of a certain function. While a first step to understanding this critical exponent is interpolation, consideration of the major arcs gives proper insight into why k(k+1) appears.

In the final section, I attempt to explain how the mean value theorem can be interpreted as a stronger form of orthogonality of certain complex exponentials. For a vector n \in \mathbb{Z}^k, we define e_n : \mathbb{R}^k / \mathbb{Z}^k \to \mathbb{C} via e_n(\alpha) : = e^{2 \pi i n \cdot \alpha}. Then Vinogradov’s mean value theorem can be interpreted as showing \{e_{(j , \ldots , j^k)}\}_{1 \leq j \leq N} are stronger than orthogonal (k \geq 2, not true for k =1). We make this somewhat precise in the above pdf, adopting a probabilistic perspective.

I’d like to thank Chris Gartland, a fellow graduate student, for helping me formulate the ideas in the last section. For instance, it was his idea to utilize equation 5.

I’d also like to thank Junxian Li, a fellow graduate student in number theory, for very useful discussions regarding the major arcs.

Lastly, anyone at UIUC interested in hearing more about Vinogradov’s mean value theorem (for instance Bourgain, Demeter and Guth’s recent result or classical number theoretic methods), please get in touch with me. My email can be found here, or you can visit my office in Altgeld 169.


A lower bound for the least prime in an arithmetic progression

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.




A genus calculation for quotients of upper half plane


In the above pdf, we calculate the genus of some Riemann surfaces, quotients of the upper half plane by \Gamma_0(p), where p is some prime.

The idea is to project the Riemann surface to \hat{\mathbb{C}} and to apply the Riemann Hurwitz formula to this map.  I include a picture that allows one to visualize the this projection map, which is basically just an appropriate folding of parts of the complex plane.

This post arose after making these calculations one afternoon with Ravi Donepudi, a fellow number theory student here at UIUC. Also, I would like to thank Junxian Li (also in UIUC number theory) for providing the picture and useful discussions.