To Cheer you up in Difficult Times 8: Nathan Keller and Ohad Klein Proved Tomaszewski’s Conjecture on Randomly Signed Sums

Today we talk about the paper, Proof of Tomaszewski’s Conjecture on Randomly Signed Sums, by Nathan Keller and Ohad Klein.

Consider a unit vector a=(a_1,a_2,\dots, a_n). That is \sum_{i=1}^n a_i^2=1. Consider all (2^n) signed sums \displaystyle \epsilon_1a_1+\epsilon_2a_2+\cdots +\epsilon_n a_n, where each \epsilon_k is either 1 or -1.

Theorem (Keller and Klein (2020) asked by Boguslav Tomaszewski (1986)): For at least 2^{n-1} signed sums \displaystyle |\epsilon_1a_1+\epsilon_2a_2+\cdots +\epsilon_n a_n| \le 1 .

Another way to state the theorem is that the probability of a signed sum to be in the interval [-1, 1] is at least 1/2.

To see that this is best possible consider the case that n=2 and let a_1,a_2 be non zero. For the sum in question to exceed one we need both summands to have the same sign which happens half of the times. There is another example of importance, the vector (\frac{1}{2}, \frac{1}{2}, \frac {1}{2}, \frac{1}{2}). Here 3/8 of the absolute values of signed sums (6 out of 16) are below 1 (in fact, equal to zero), 1/2 equal to 1 and 1/8 exceed 1. Holzman and Kleitman proved in 1992 that the fraction of absolute values of signed sums below 1 is always at least 3/8.

Congratulations to Nathan and Ohad. I will say a little more about the problem below but before that, a few more things.

A few more things

Luca Trevisan posted on his blog In Theory a post “Silver linings” about two cheerful pieces of news. The first one is “Karlin, Klein, and Oveis Gharan have just posted a paper in which, at long last, they improve over the 1.5 approximation ratio for metric TSP which was achieved, in 1974, by Christofides.”

The second  one is about breaking the logarithmic barrier for Roth’s theorem that we wrote about here. This was also discussed by Bill Gasarch on Computational Complexity. In the comment section of my post there is an interesting discussion regarding timetable for future achievements and how surprising they would be.

The third is about Ron Graham, a friend and a mathematical giant who passed away a few days ago. Here is a moving post by Fan Chung, a web page for Ron set by Fan, and a blog post by Dick and Ken on GLL.

The fourth is that there is a nice collection of open problems on Boolean functions that is cited in the paper of Nathan and Ohad:  Y. Filmus, H. Hatami, S. Heilman, E. Mossel, R. O’Donnell, S. Sachdeva, A. Wan, and K. Wimmer, Real analysis in computer science: A collection of open problems.

The fifth is that both our (HUJI) combinatorics seminar and basic notions seminar are running and are recorded. Here are the links. (Hmm, the links are not yet available, I will update.)

Back to the result of Keller and Klein

Daniel Kleitman and Ron Holzman

A quick orientation

If the a_is are all the same, or small, or random, then to compute the probability that the weighted sum is between -1 and 1, we can use some Gaussian approximation and then we will find ourselves in a clash of constants that goes our way. The probability will be close to a constant well above 1/2. So what we need to understand is the case where some a_is are large.

Early papers on the problem

The problem first appeared in the American Math Monthly.  Richard Guy collected several problems  and challenged the readers Any Answers Anent These Analytical Enigmas? (I don’t know what the fate of the other questions is.)  Holzman and Kleitman proved in 1992 that the fraction of absolute values of signed sums below 1 is always at least 3/8, and this is tight. For many years, 3/8 was the record for the original problem, until  the 2017 paper by Ravi Boppana and Ron Holzman: Tomaszewski’s problem on randomly signed sums: Breaking the 3/8 barrier, where a lower bound of 0.406, was proved. The current record 0f 0.46 was proved in the paper Improved Bound for Tomaszewski’s Problem by Vojtěch Dvořák, Peter van Hintum, and Marius Tiba. The new definite result by Nathan and Ohad used some ideas of these early papers.

What is the crux of matters

Let me quote what the authors kindly wrote me:

“The crux of the matter is how to deal with the case of very large coefficients (a_1+a_2>1). We gave a short semi-inductive argument covering this case (this is Section 5 of the paper). The argument is only semi-inductive, as it requires the full assertion of Tomaszewski for any n'<n, and gives only the case (a_1+a_2>1) for n. But this means that if we can handle all other cases by other methods then we will be done.

The semi-inductive argument takes only 3 pages. Handling the other cases takes 72 more pages and requires several new tools, but is closer to things that were done in previous works. (Actually, after we found the 3-page argument, we were quite sure we will be able to finalize the proof; this indeed happened, but took a year).”

Most of the paper deals with the case of small coefficients. This requires several ideas and new tools.

Rademacher sums: Improved Berry-Esseen and local tail inequalities

If all coefficients are “sufficiently small”, then we can
approximate X by a Gaussian and the inequality should follow. However, using the standard Berry-Esseen bound, this holds only if all coefficients are less than 0.16.
Nathan and Ohad showed that for Rademacher sums, namely random variables of the form X=\sum a_i x_i, as discussed in the conjecture, a stronger Berry-Esseen
bound can be obtained, and this bound shows immediately that Tomaszewski’s assertion holds whenever all coefficients are less than 0.31. The stronger bound stems
from a method of Prawitz, presented in the 1972 paper. H. Prawitz, Limits for a distribution, if the characteristic function is given in a finite domain, which appeared in the Scandinavian Actuarial journal.

The second tool is local tail inequalities for Rademacher sums, of the form \Pr[a<X<b] \leq \Pr[c<X<d], where a,b,c,d satisfy certain conditions. Inequalities of this kind were obtained before by Devroye and Lugosi in the 2008 paper:  Local tail bounds for functions of independent random variables.

These local tail inequalities already have some other applications, e.g., to analysis of Boolean functions. They were developed and applied in an earlier paper paper of Keller and Klein: Biased halfspaces, noise sensitivity, and relative Chernoff inequalities. Let me mention my related MO question A variance tail description for continuous probability distributions.

A couple more ingredients

A  stopping time argument. Variants of Tomaszewski’s problem appeared in various fields. The problem was stated independently in a 2002 paper by Ben-Tal, Nemirovski, Roos, Robust solutions of uncertain quadratic and conic-quadratic problems.  A stopping time argument introduced there (for proving a lower bound of 1/3) played a crucial role in subsequent works and the critical semi-inductive argument by Nathan and Ohad.

Refinements of the famous Chebyshev’s inequality.  (Did you know Chebyshev’s full name? Ans: Pafnuty Lvovich Chebyshev.)

Questions and connections that come to mind

Q1: What can be said about families \cal F of signs that can serve as those signs for which  |\epsilon_1a_1+\epsilon_2a_2+\cdots +\epsilon_n a_n| \le 1 , for some vector a.

Q2: What can be said about the complex version or even more generally about high dimensions?

Q3: Are there any relations to Littlewood-Offord type problems?

Q4: Is there any relation to the Komlos Conjecture?

See also this MO question by Luca Trevisan and this one by George Lowther.

Is there a simpler proof?

We can ask about simpler or just different proofs for almost every result we discuss here. But here the statement is so simple…

This entry was posted in Analysis, Combinatorics, Probability and tagged , , . Bookmark the permalink.

11 Responses to To Cheer you up in Difficult Times 8: Nathan Keller and Ohad Klein Proved Tomaszewski’s Conjecture on Randomly Signed Sums

  1. Geoffrey Irving says:

    Isn’t it obvious that the probability is at most 1?

    > Another way to state the theorem is that the probability of a signed sum to be in the interval [-1, 1] is at most 1.

  2. Hi Gil.

    Interesting post – I have been thinking about some similar inequalities…hence my MO post. I haven’t read the linked paper completely yet (it is long!), but have some comments on the general ideas.
    We need to prove P(\lvert X\rvert\le1)\ge1/2. If we instead had the strict inequality P(|X|<1)> 1/2 then things would be much simpler. Once it is verified for any particular a then, by continuity, it would hold in a neighbourhood of this point. By a compactness argument, this reduces to checking a finite number of examples (how finite, is another question). So, the proof can be completed, the only question is how many sample points need to be verified. Things like improvements to Berry-Esseen and other tricks can reduce the number of points that need to be checked, but don't change the fact that we can in principle prove the result.

    Unfortunately, the stronger inequality does not hold. There are some points for which P(|X|<1)<1/2. These are small in number (finite, I think, after arranging a as a decreasing sequence of positive terms). E.g, a=(1,0,…), a=(1,1,1,1)/2. There are even more points at which P(|X|<1)=1/2. It is this set of points which make it difficult. Once you can prove the result on a neighbourhood of these points, then the proof can in principle be completed by a finite check (with some work to try and minimise the checking required). This is, I expect, why the case they mention with a_1+a_2 >1 is so critical. After this it is plain sailing…sort of.

    • Sorry, must have mis-typed formulas, but cannot edit. Can you fix?

      GK: I tried.

      • Thanks. AFter the words “instead had the strict inequality”, then both inequality signs should be strict. P(\lvert X\rvert  1/2 (if that shows correctly). Otherwise, its all as I intended. Thanks!

      • After some testing, the equality after “instead had the strict inequality” should have been typed as P(\lvert X\rvert <1)>1/2. Hope it shows correctly this time…didn’t mean to spam your blog, you can delete my other follow-up responses.

      • Gil Kalai says:

        Thanks for the comment, George. experiment with WordPress latex is welcome.

    • Ohad says:

      Hi George,
      thanks for the insights!

      In section 2.3 in the paper there is an informal discussion about tightness example;
      the a_1 + a_2 > 1 case indeed includes them all.

      Two questions related to the compactness argument, which lacks the quantitative aspects, is regarding the function F(x) = inf_X Pr[X > x], where X ranges over all Rademacher sums of variance 1.
      Holzman asked whether the infimum is actually achieved (i.e., being a minimum)?
      And (in a source I can not recall) it was asked whether F is constant on intervals.
      These two questions seem interesting, and I am not aware of an answer.

      • Hi Ohad,

        Interesting…I mentioned in my MO post that F appears to be constant on intervals. I also suspect that the minimum is always achieved by a equal to one of (1), (1,1)/sqrt(2),(1,1,1)/sqrt(3), (1,1,1,1,1)/sqrt(5), (1,1,1,1,1,1)/sqrt(6), (1,1,1,1,1,1,1)/sqrt(7). Seems like quite a strong statement, but I do not know any counterexamples. I was actually in the middle of writing up a post for my blog conjecturing this…but am not sure what has already been conjectured (or proven).

      • Actually, I was thinking of F defined over non-negative reals (wheras Tomaszewski’s conjecture is concerned with x=-1, with the inequality the way round you have here). Maybe it is piecewise constant also over the entire set of reals?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s