An Open Discussion and Polls: Around Roth’s Theorem

Suppose that R_n is a subset of \{1,2,\dots, n \} of maximum cardinality not containing an arithmetic progression of length 3. Let g(n)=n/|R_n|.

How does g(n) behave? We do not really know. Will it help talking about it? Can we somehow look beyond the horizon and try to guess what the truth is?

Update 1: for the discussion: Here are a few more specific questions that we can wonder about and discuss.

1) Is the robustness of Behrend’s bound an indication that the truth is in this neighborhood.

2) Why arn’t there analogs for Salem-Spencer and Behrend’s constructions for the cup set problem?

3) What type of growth functions can we expect at all as the answer to such problems?

4) Where is the deadlock in improving the upper bounds for AP-free sets?

5) What new kind of examples one should try in order to improve the lower bounds? Are there some directions that were already extensively explored?

6) Can you offer some analogies? Other problems that might be related?

 

Continue reading

A Proposal Regarding Gilad Shalit

Since an agreement for the release of Gilad Shalit in exchange for the release of Hamas prisoners could not be reached, I propose to initiate negotiations (perhaps with Egyptian help) on the improvement of Gilad Shalit’s captivity conditions.

In return for letting Shalit have frequent visits of the red cross,  letter exchange and perhaps also visits by his family, Israel can offer the release  of many dozens of prisoners, such as Hamas Parliament members, and other prisoners not directly involved in violent activities.

מאחר שלא ניתן היה להגיע להסכמה על שחרור גלעד שליט תמורת שחרור אסירים, יש לנסות לפתוח משא ומתן (למשל באמצעות המצרים) רק על שיפור תנאי השבי של גלעד שליט ואפילו להיות מוכנים לשחרר אסירים כמו עשרות חברי הפרלמנט של חמאס שנעצרו  תמורת שיפור תנאי השבי בלבד -מכתבים, ביקורי צלב אדום, ואם ניתן ביקורים של המשפחה

 

Gilad Shalit 

Colorful Caratheodory Revisited

caratheodory-colored

 

Janos Pach wrote me:   “I saw that you several times returned to the colored Caratheodory and Helly theorems and related stuff, so I thought that you may be interested in the enclosed paper by Holmsen, Tverberg and me, in which – to our greatest surprise – we found that the right condition in the colored Caratheodory theorem is not that every color class contains the origin in its convex hull, but that the union of every pair of color classes contains the origin in its convex hull. This already guarantees that one can pick a point of each color so that the simplex induced by them contains the origin. A similar version of the colored Helly theorem holds. Did you know this?”

I did not know it. This is very surprising! The paper of Holmsen, Pach and Tverberg mentions that this extension was discovered independently by  J. L. Arocha, I. B´ar´any, J. Bracho, R. Fabila and L. Montejano.

Let me just mention the colorful Caratheodory agai. (we discussed it among various Helly-type theorems in the post on Tverberg’s theorem.)

The Colorful Caratheodory Theorem: Let S_1, S_2, \dots S_{d+1} be d+1 sets in R^d. Suppose that x \in conv(S_1) \cap conv (S_2) \cap conv (S_3) \cap \dots \cap conv (S_{d+1}). Then there are x_1 \in S_1, x_2 \in S_2, \dots x_{d+1} \in S_{d+1} such that x \in conv (x_1,x_2,\dots,x_{d+1}).

And the strong theorem is:

The Strong Colorful Caratheodory Theorem: Let S_1, S_2, \dots S_{d+1} be d+1 sets in R^d. Suppose that x \in conv(S_i \cup S_j)  for every 1 \le i <j \le d+1. Then there are x_1 \in S_1, x_2 \in S_2, \dots x_{d+1} \in S_{d+1} such that x \in conv (x_1,x_2,\dots,x_{d+1}).

Janos, whom I first met thirty years ago,  and who gave the second-most surprising introduction to a talk I gave, started his email with the following questions:

“Time to time I visit your lively blog on the web, although I am still not quite sure what a blog is… What is wordpress? Do you need to open an account with them in order to post things? Is there a special software they provide online which makes it easy to include pictures etc? How much time does it take to maintain such a site?”

These are excellent questions that may interest others and I promised Janos that I will reply on the blog. So I plan comments on these questions in some later post. Meanwhile any comments from the floor are welcome.

A Beautiful Garden of Hypertrees

We had a series of posts (1,2,3,4) “from Helly to Cayley” on weighted enumeration of Q-acyclic simplicial complexes. The simplest case beyond  Cayley’s theorem were Q-acyclic complexes  with n vertices, {n \choose 2} edges, and {{n-1} \choose {2}} triangles. One example is the six-vertex triangulation of the real projective plane. But here, as in many other places, we are short of examples.

Nati Linial,  Roy Meshulam and Mishael Rosenthal wrote a paper with very surprising examples of Q-acyclic simplicial complexes called “sum complexes”. The basic idea is very simple: The vertices are \{1,2,\dots , n\}. Next you pick three numbers a,b and c and consider all the triples i,j,k so that i+j+k is either a or b or c. And let’s assume that n is a prime.

So how many triangles do we have? A fraction of 3/n of all possible triangles which is what we want ({{n-1} \choose {2}}).

If the three numbers form an arithmetic progression then the resulting simplicial complex is collapsible. In all other cases it is not collapsible. The proof that it is Q-acyclic uses a result of Chebotarëv on Fourier analysis. (So what does Fourier analysis have to do with computing homology? You will have to read the paper!) The paper considers the situation in all dimensions.

What about such combinatorial constructions for Q-homology spheres?

Extremal Combinatorics on Permutations

 

We talked about extremal problems for set systems: collections of subsets of an n element sets, – Sperner’s theorem, the Erdos-Ko-Rado theorem, and quite a few more. (See here, here and here.) What happens when we consider collections of permutations rather than collection of sets? Not so much is known on extremal problems for families of permutations.

David Ellis, Ehud Friedgut, and Haran Pilpel have recently proved an old conjecture of Deza and Frankl regarding an analog for permutations of the Erdos-Ko-Rado Theorem. They showed that for every k if n is sufficiently large, any family of permutations on an n-element set such that every two permutations in the family agree in at least k places, contains at most (n-k)! permutations.

The proof uses spectral methods and representations of the symmetric group.

Polymath1: Success!

15

 polymath” based on internet image search

And here is a link to the current draft of the paper.

Update:  March 26, the name of the post originally entitled “Polymath1: Probable Success!” was now updated to “Polymath1: Success!” It is now becoming clear that there are  three (perhaps four) new emerging proofs of DHJ. (April 2: See this post by Terry Tao. As this update was also based on briefly talking with Terry,  Terry’s new post gives a better description on the state of affairs and relations between the different proofs.)

The proof directly emerged from the project indeed looks conceptually different and simpler than all other proofs, and may indeed lead to the simplest known proof for Szemeredi’s theorem. (But for this we will have to wait for the details.) In addition, there is a new Ergodic proof by Tim Austin, which was partially inspired by and which used (among several other ingredients developed by Austin) some ideas and  results discovered in the polymath project. Both the original  ergodic proof and Austin’s proof were (at least roughly) “combinatorialized”. 

In what sense was it a massive open collaboration? It is true that in the crucial phases of polymath, the phases where two concrete strategies for proofs were considered, the number of pivotal participants was not large. But there was an initial phase were probably more than a hundred mathematicians took part as observers and as commentators. The comments in this early phase played some role in the later developments but what is more important is that this stage have led to the (emerging) selection of the team that developed the proof. Among the hundreds, those who felt they have ideas that can be crucial, or methods that could be helpful, and were smart or lucky to be correct,  and had the persistence to follow these ideas and how these ideas can be combined with other ideas, became the pivotal players. The team that played the game was not so large, but the main massive ingredient of the project which accounts for its accessive mathematical power was in the “draft”. The team emerged from a massive number of participants. (So if you believe there were 10 pivotal players out of a hundred, think about the emergence of the team among {{100} \choose {10}}  possible (but, of course, not equally plausible) teams, as a point were  polymath had extra power.) 

Two related posts: Tim Gowers raised inthis post  interesting questions regarding the possibility of projects were the actual number of provers will be massive. Here on my blog we have a post  with an “open discussion”  on what are the correct bounds for Roth type problems.  The emphasis is on “small-talk discussion” and not on actual “hard-nose researching”.

We took the opportunity to spend three days of “Purim” visiting northern Israel. Coming back I saw two new posts on Tim Gowers’s blog entitled “Problem solved probably” and “polymath1 and open collaborative mathematics.” It appears that “polymath1” has led to a new proof for the density version of Hales-Jewett’s theorem for k=3 which was the original central goal! Also it looks like the open collaboration mode (while not being a massive collaboration) was indeed useful.

Perhaps the most important thing is to make sure that a complete proof for the k=3 case is indeed in place (as these famous problems sometimes “fight back,” as Erdos used to say).  The outline is described here. If everything is OK as Tim and other participants expect, there are already some discussions or even plans about an extension to the general k case. This seems to be the next major step in the project.  There are also other fruits from the various threads of the polymath1 project. Overall, this looks very exciting! The mathematical result is a first-rate achievement, and the mode of cooperation is novel, interesting and appears genuinely useful.

Let me quote what Tim writes about it: “Better still, it looks very much as though the argument here will generalize straightforwardly to give the full density Hales-Jewett theorem. We are actively working on this and I expect it to be done within a week or so. (Work in progress can be found on the polymath1 wiki.) Better even than that, it seems that the resulting proof will be the simplest known proof of Szemerédi’s theorem.” sababa!

Do Politicians Act Rationally?

Well, I wrote an article (in Hebrew) about it in the Newspaper Haaretz. An English translation appeared in the English edition. Here is an appetizer:

During World War II, many fighter planes returned from bombing missions in Japan full of bullet holes. The decision was made to reinforce the planes, and their natural tendency was to bolster the hardest-hit sections in the body of the plane. However, the mathematician George Dantzig suggested that it was precisely the parts that were hit less that needed to be armored. Was he right?

Months after all the commentators described Hillary Clinton’s chances as so slim she was bound to lose her campaign for the Democratic presidential nomination, she continued to fight for her candidacy, saying she believed she would win and keeping up her attack on her rival. Did she act rationally? And did Benjamin Netanyahu and Tzipi Livni act rationally when each declared victory on election night? Did Meretz supporters who voted for Kadima act rationally? Is there an election method in which it would be rational for all voters to vote in accordance with their genuine preferences?

My conclusion is:

Continue reading

Noise Sensitivity Lecture and Tales

 

A lecture about Noise sensitivity

Several of my recent research projects are related to noise, and noise was also a topic of a recent somewhat philosophical post.   My oldest and perhaps most respectable noise-related project was the work with Itai Benjamini and Oded Schramm on noise sensitivity of Boolean functions. Recently I gave lectures at several places about noise sensitivity and noise stability of Boolean functions, starting with the definition of these terms and their Fourier description,  then the result of Itai, Oded and myself that the crossing event of planar critical percolation is noise-sensitive, and ending with two recent breakthrough results. One is the work by Garban, Pete, and Schramm   that described the scaling limit of the spectral distribution for the crossing event in critical percolation. The second is  the “majority is stablest” theorem of Mossel, O’Donnell, and Oleszkiewicz and the connections to hardness of approximation.

A fun way to explain noise sensitivity (especially after the 2000 US election) is in terms of the probability that small mistakes in counting the votes in an election will change the outcome. Here we assume that there are two candidates, that every voter votes with probability 1/2 for each candidate (independently) and that when we count every ballot there is a small probability t that the voter intention is reversed.

Noise sensitivity is one of the reasons to reject the HEX voting rule; but perhaps not the main one :) . (Noise stability/sensitivity and the related notion of influence play some role in the recent polymath1 project.)

Here is the power point presentation. I hope to blog at a later time about analysis of Boolean functions and about noise sensitivity and noise stability. 

Meanwhile let me just give a few general comments and tales: 

Some noise sensitivity tales:

1. We started working on noise sensitivity in 1995 and at that time Itai was expecting a son, so a friend lent him a pager. When we wrote the paper Alon was already 4 years old.

bks

2. The paper by Boris Tsirelson and Anatoly Vershik (that also describes work spanning many years) contains a similar notion. Their motivation was entirely different.  One difficulty in translating the two formulations is that “Boolean function” (or rather “a sequence of Boolean functions + some uniformity condition” ) in our work  is translated to “noise” in Tsirelson’s terminology. And “noise sensitive” is translated to “black” or “non-Fock” or “non-classical” in their work. 

3. After the 2000 elections Itai Benjamini and Elchanan Mossel wrote a popular piece about the relevance of this work for elections. Mathematician and writer Barry Cipra wrote a lovely  small article about it. (Looking at it now I find it very impressive how Barry put so much information in a vivid way in such a short article.)

Here is one paragraph from Cipra’s article:

“Three researchers—Itai Benjamini and Oded Schramm, both of Microsoft Research, and Gil Kalai of the Hebrew University in Jerusalem—have turned the question around: How close does a race have to be in order for errors in counting to have a non-negligible chance of reversing the outcome? Their analysis indicates that a simple, nationwide popular vote would be more stable against mistakes than the beleaguered Electoral College system. Indeed, they find, straightforward majority vote is more stable than any other voting method.” Continue reading

The Mystery Beeping Riddle

 

 

We came back from the airport with our daughter who has just landed after a four-month trip to India. The car was making a strange beep every so often.

Maybe it is an indicator signal that should have turned off automatically? No, this possibility was quickly eliminated.

Can it be the radio? We made sure the radio was off but the beeps continued.

I looked in the car manual. The only slightly similar symptom described there was a beeping indicating that the air bags are out of order and the air bag light warning signal is also out of order. Was this the reason? In this case there would be a 5-second beep every minute. But our beeps were once every 5 minutes and each beep was for one second. Was there some mistake in the translation of the manual to Hebrew?

I called the garage. Yes, they told me, if I bring the car they can check out what is wrong and fix it. No, they have not encountered this problem before. No, it is not dangerous to drive the car back to Jerusalem. And no, they were not familiar with translation problems in the manual.

Another breakthrough idea! Maybe the beeping came from a mobile phone in the car. Some mobile phones tend to beep when the battery is low or when there is an unread message. We turned off the two mobile phones in the car. This looked promising, Continue reading