EDP Reflections and Celebrations

The Problem

In 1932, Erdős conjectured:

Erdős Discrepancy Conjecture (EDC)  [Problem 9 here] For any constant , there is an such that the following holds. For any function , there exists an   and a   such that

For any , the set    is an arithmetic progression containing ; we call such a set, a Homogenous Arithmetic Progression (HAP). The conjecture above says that for any red blue coloring of the [n] (={1,2,…,n}), there is some HAP which has a lot more of red than blue (or vice versa).  Given C, we  let n(C) to be the minimum value of n for which the assertion of EDC holds, and  given n we write  D(n) as the minimum value of C for which n(C) ≤ n.

EDC was a  well-known conjecture and it was the subject of the fifth polymath project (making it even more well-known,) that took place in the first half of 2010. (With a few additional threads in August-September 2012.) That D(n) > 3 for n >  1160 (and that D(1160)=3 ) was proved in a 2014 paper  by Boris Konev and Alexei Lisitsa.

The solution

The two defining moments in the life of a mathematical problem is the time it is born and the time it is solved. As you must have heard by now the Erdős discrepancy conjecture  has recently (mid September, 2015) been proved by Terry Tao.  I was very happy with the news, congratulations Terry!!

Reading material

(Video:)  Terence Tao, The Erdős Discrepancy Problem, UCLA Math Colloquium, video by IPAM, Oct 8, 2015. (Thanks to Igor Pak)

(Papers:) The proof of the conjecture was done in two recent papers. The first The logarithmically averaged Chowla and Elliott conjectures for two-point correlations, proves a necessary analytic number theory result related to a classical conjecture of Chowla. The second paper – The Erdős discrepancy problem, shows the derivation of EDC from the number theory result.  The number theoretic paper is based on a new recent breakthrough technique in analytic number theory initiated by Matomaki and Radziwill and further studied by Matomaki, Radzwill, and Tao. I also recommend a very interesting paper Erdős and arithmetic progressions from about a year ago by Gowers: where Tim tells side-by-side the story of Erdős-Turàn problem (leading to Roth-Szemeredi’s theorem), and that of EDP.

(Blog posts:) The proof is described in this blog post by Tao. A similar (somewhat simpler) argument proving EDC based on a number-theoretic conjecture (The Eliott Conjecture) can be found in this very readable blog post by Tao. In 2010 Tim Gowers ran a polymath project devoted to the Erdős discrepancy problem (EDP). A concluding post following Tao’s proof on Gowers’s blog is EDP28. You can also read about the problem and its solution on Lipton and Regan’s blog and in various other places.

(Popular scientific writings:) Quanta magazine (Erica Klarreich) : Nature (Chris Cesare), and various other places.

Erdős’s 1957 Problem paper  

Erdős’s 1957 paper on open problems in number theory, geometry, and analysis is especially interesting. (It is linked above but the link here might be more stable.) It has 15 problems in number theory, 5 problems in Geometry, and 9 problems in analysis. Some of the problems are famous, and quite a few of them were settled,  but some were new to me. It would be nice to go over them and see what their status is.

We will come back to Erdős’s 57 paper at the end.

Our celebration

To celebrate to solution here are a few things I would like to tell you (including something about the Erdős-Szusz discrepancy problem and its solution), as well as more things and problems related to EDP that I am curious about (the red items):

1. The proof; Other proofs? Other applications of the methods?
2. The value:  What is the behavior of D(n)? a) Does the proof give ? What will it take to get ?  b) Find a multiplicative sequence of of length n of  +1 and -1 with discrepancy . (Even better, find an infinite sequence with this property for every n.)
3. Sequences with diminishing correlation to Dirichlet characters. Find a sequence orthogonal to all characters with small discrepancy. Prove a stronger version of the conjecture for such sequences.
4. The hereditary discrepancy of HAP’s
5. Variants:  Random subsets; square free integers;
6. Pseudointegers    Can we understand softly and under greater generality why EDC is true?
7. Pseudo HAP:  A toy problem proposed by several people in polymath5 is to replace the kth HAP by a random set of integers of density 1/k. The EDC and even the $\latex {\sqrt {\log n}$ prediction should still work.
8. Restricted gaps  a) prime powers gaps, b) powers of two and primes gaps; c) small gaps
9. Modular versions
10. What is  the strongest version of a statement saying: Functions with values 0, 1, -1 with diminishing correlations to Dirichlet characters have large discrepancy. 
11. Erdős-Szüsz discrepancy problem and the question about basis. (This I heard from Gadi Kozma).
12.  What is the RH-strength analog of Chowla’s conjecture?

 The proof

A few words about the proof. The part of the proof I am less unfamiliar with is the derivation of EDC from the Elliot conjecture (which refers to a slight modification of a conjecture by Eliott) that appeared in a blog post a few days before the full proof. The actual proof gives EDC from a weak “logarithmic averaged” case of the Elliot conjecture which is the subject of this paper, and proves this averaged Elliot conjecture in this paper. For completely multiplicative functions the proof has two ingredients: The first (adapted from polymath5) is to show that completely multiplicative functions which have bounded discrepancy must have diminishing correlation with every Dirichlet character. The second is the new ingredients: The Elliot conjecture asserts that for completely multiplicative functions g which is not correlated with a Dirichlet character, the pairwise correlation between g(x) and g(x+h) are small. If this is the case for most intervals [n], then some l-2 computation shows that the discrepancy cannot be bounded.

In a very wide stroke we do have here a structure vs randomness argument like in Roth/Szemeredi theorems. But the machinery needed for the “no structure” case is quite different.

Solving the problem for completely multiplicative functions is already a big deal. For the full statement there is one more step: Terry Tao found (in polymath5) a reduction from the general question to a certain strong form of the conjecture for completely multiplicative functions with complex norm-one values. The beautiful proof for the reduction relies on “multiplicative” Fourier analysis and it is striking how “little” the proof uses.

Of course, we can ask, as always, for other proofs perhaps with weaker quantitative conclusions but applying in greater generality. Is EDC, in essence, a theorem in analytic number theory, or are there other avenues toward it?  And also, as usual, we can ask if the proof or its various ingredients can be applied to other problems.

The value of D(n):  

D(n) tends to infinity but how fast? It is reasonable to think that D(n) behaves asymptotically like  . (This is suggested, among other reasons, by certain probabilistic heuristics from EDP23.)

Regarding upper bounds we can ask:

a) Find examples where the discrepancy is or even just  is o(log n). (For the best known examples the discrepancy grows like log n).

Regarding lower bounds that Tao’s proof gives we can ask (mainly ask Terry himself):

c) Does Tao’s proof give for some  α > 0? How close does the proof gets to ?

Sequences with diminishing correlation with Dirichlet characters.

One crucial step in the proof is that a completely multiplicative sequence with positive correlation with a Dirichlet character must have unbounded discrepancy.  (For the actual proof the polymath5 argument needed to be extended and strengthened.) The examples with log n discrepancy do have positive correlation with Dirichlet characters. There are two interesting questions when the correlations with Dirichlet characters is negligible.

First  we can ask if having strong diminishing correlation with all Dirichlet’s characters implies stronger lower bound on the discrepancy? My quess is that the answer is largely no.

Question: Find examples which have quickly diminishing correlation with all Dirichlet characters,  on every interval [n], were the discrepancy is still or even polylog (n), or even . (Another way to put it: find a low discrepancy completely multiplicative function which really really does not look like a Dirichlet’s character.)

It is remarked in Tao’s paper that when  f(n) is completely multiplicative, has values {-1,0,1},  has diminishing correlation with all Dirichlet characters and has positive density  ρ of nonzero entries then the discrepancy is going to infinity. Probably there are interesting quantitative versions of this fact left to be explored.

The hereditary discrepancy of HAP’s   

Let be the hereditary discrepancy of the hypergraph of HAPs restricted to {1,2,,…,n}. In the post EDP22 an observation made by Noga Alon and myself  that g(n) is at most , and at least roughly is shown. There were reasons to think that g(n) is polylogarithmically, however:

Theorem (Nikolov and Talwar): .

You can read about it in the paper by Nikolov and Talwar and in this blog post by Talwar. (My description of EDC above is taken from Talwar’s post.)

Variants:

Here are two variants of EDP where in both we restrict ourselves to a dense set of integers.

1) Consider a random subset of integers where each integer is taken with probability p (independently), 0 < p < 1.

2) Consider the subset of square free integers;

It seems  reasonable that for both these variants the discrepancy is unbounded and, in fact, behaves like .

More modest but possibly already difficult tasks would be

a) Prove that in these variants the discrepancy tends to infinity.

b) Find examples where it is ;  Find an algorithm to get (even heuristically) a sequence of small discrepancy.

(Yet another variant of a similar nature would be to consider completely multiplicative functions for the subset of integers involving only primes from a random subset of primes with positive density.)

An algorithm leading (heuristically) to discrepancy was described in polymath5. A better one giving (heuristically) (also to the square free variant) is discussed in this Math Overflow problem.

Pseudo HAP:

A toy problem proposed by several people in polymath5 is to replace the kth HAP by a random set of integers of density 1/k. The EDC and even the prediction should still work (and should be easier!). Maybe Tao’s line of proof  can be applied to this case even without needing the analytic number theory part.

Pseudoprimes and Pseudointegers

One of the pleasant things I learned from polymath4 was a remarkable theorem by Jeff Lagarias on Beurling primes.

Can we understand softly and under greater generality why EDC is true? One direction is to consider pseudointegers. (Sune Kristian Jakobsen proposed and developed it in polymath5.) Pseudointegers (e.g. based on pseudoprimes) are both appealing and frustrating. Beurling primes refers to the following situation. Consider a monotone sequence of real numbers which you declare as pseudoprimes. Let us assume that, just like ordinary primes, all products (with multiplicities) of these real numbers, which we call “pseudointegers” are distinct. Now, you can ask EDP for these psudoprimes and pseudointegers. Of course, people have asked other questions about them:  When will they obey the prime number theorem? or the Riemann hypothesis? This seems a very tempting direction which at the same time is also frustrating since many of the methods disappear.

You can relax the conditions for pseudoprimes: for example, allow to be only infinitesimally larger than (or, in other words, allow them values in some non-Archimedean ordered polynomial ring), you can give up the unique factorization and even allow repetitions for the primes themselves, add weights of various kind, allow complex primes, etc. etc.

There is another way to think about these pseudoprimes and integers. If you map to (the kth prime) and then the pseudointegers are in bijection with the ordinary integers albeit not in an order preserving way. So you get a new ordering on the ordinary integers. The EDP depends just on this ordering.

In polymath5 there were examples where the discrepancy for completely multiplicative assignments of pseudointegers was bounded. But I  could not find it these examples. It is reasonable to think that even for an arbitrary system of pseudointegers, we can find a completely multiplicative function with discrepancy growing like polylog (n). I don’t know if Tao’s reduction extends to pseudointegers, but I did not think much about it.

I am curious also about the hereditary discrepancy for HAP for pseudoprimes. I don’t know when the upper bound of Alon and myself behaves the same as the lower bound obtained by Nikolov and Talwar. (We can pray that the upper bound is always larger than the lower bound.)

Restricted gaps

It was observed in polymath5 that for HAP with prime gaps the discrepancy can be bounded.  It may hold for prime-power gaps, and as Gowers asked even for gaps which are either prime or powers of two.  It is also of interest to what extent, for the quantitative versions of EDC,  we can require that the gaps for the HOP be themselves small.

Modular and other notions of “discrepancy”

There were various other notions of discrepancy for hypergraphs that came from polymath5. One was a modular notion of discrepancy. We let the ground set have arbitrary non-zero weights modulo p and ask if there is always an edge (HAP in our case) whose elements sum to 0 modulo p. We do not know what the situation is for EDP (see this post), and also for Roth’s theorem for general AP (see this post). Gowers introduced yet another extension of discrepancy which again can be adapted to arbitrary discrepancy questions. He asked if we start from an arbitrary finite set K of irrational numbers and assign to every integer an element from K, is it always the case that the partial sums of HAP are dense modulo.

Erdős-Szüsz discrepancy problem

Let S be a set in the unit interval and let α be an irrational number. Now, consider the sequence where iff [nα] mod 1 belongs to S. The question was when is it the case that all partial sums of the sequence are bounded. Erdős and Szüsz conjectured that this is the case if and only if S is a finite union of intervals with endpoints integral multiples of α modulo 1. This was proved by Kesten and later other illuminating proofs were also found.

 What is the RH-strength analog of Chowla’c conjecture?

This is something I am curious about but possibly it is well understood (or meaningless).

(PNT=Prime number theorem; RH=Riemann hypothesis)

More questions from Erdős 1957 paper

Here are a few other problems from Erdős 1957 paper. (This paper is an example of a deep matter discussed in Mathoverflow here. )

Do you know what is the not quite hopeless question at the end?  Half a century later was it solved? (I don’t know)  

And a few fragments to test you, dear readers:

What is this about?

And what is this about?