The Cap-Set Problem and Frankl-Rodl Theorem (C)

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here is an open discussion post around Roth theorem (March 2009). Here are two “open discussion” posts on the cap set problem (first, and second) from Gowers’s blog (January 2011). These posts include several interesting Fourier theoretic approaches towards improvement of the Roth-Meshulam bound. The second post describes a startling example by Seva Lev.

Suppose that the maximum size of a cap set in $\Gamma(n)=\{1,2,3\}^n$ is $n/g(n)$.  Here is an obvious fact:

The maximum size of a set $F$ in $G$ with the property that every $x,y\in G$ ($x \ne y$) satisfy $x+y \notin G$ is at most the maximum size of a cap set in $G$

Proof: Indeed the condition for $F$ is stronger than being a cap set. We require for every $x,y \in F$ $x \ne y$ not only that $x+y \notin F$ but even $x+y \notin G$.

Part C.  A more direct relation between Frankl-Rodl’s theorem and the cap set problem and all sorts of fine gradings on subsets of {1,2,…,n}.

In part A we moved from sets avoiding affine lines (cap sets) to sets avoiding “modular lines” and used the Frankl-Rodl theorem to deal with the latter. This may look artificial. Here is a simpler connection between the cap set problem and the Frankl-Rodl theorem.

Around the Cap-Set problem (B)

Part B: Finding special cap sets

This is a second part in a 3-part series about variations on the cap set problem that I studied with Roy Meshulam. (The first post is here.)  I will use here a different notation than in part A to make it compatible with various posts of polymath1 which consider similar objects. We write $\Gamma(n) = \{0,1,2\}^n$ and $\Gamma_{a,b,c}$ denotes all vectors of length $n$ with $a$ 0’s, $b$ 1’s and $c$ 2’s.

An affine line are three vectors $x,y,z$ so that $x_i + y_i + z_i = 0 (mod~3)$ for every $i$. A cap set is a subset of $\Gamma(n)$ without an affine line. The cap set problem asks for the maximum size of a cap set. For information on the cap set problem itself look here.  For questions regarding density of sets avoiding other types of lines look here.

In the first part we considered the case that $n=3m$ and considered “modular lines” , i.e., three vectors  $x,y,z$ so that the number of solutions to $x_i+y_i+z_i=a(mod~3)$  is divisible by $m$ for every $a$. When $n$ is divisible by 9 the Frankl-Rodl theorem implies that a subset of $\Gamma$ with more than $(3-\epsilon)^n$ elements must contain a modular line, and even a modular line with two equal elements. (Question: does the same statement follow from Frankl-Rodl theorem when $n$ is divisible by 3 and not by 9?)

10. Some propositions in the desired direction.

Proposition 6:  Suppose that $n=3m$, and that $m=1 (mod~3)$. If every set of size > $(3-\epsilon)^n$ has a modular line, then every set of size > $(3-\epsilon)^n$ has a modular line which is either an affine  line, or  the number of $i$s such that $x_i + y_i + z_i =a$ is precisely $m$ for $a=0,1,2$.

(So we can get rid of a few “types” of modular lines which are not really affine  lines, but not all of them.)

Proposition 6 follows from the much more transparent  proposition:

Proposition 7:  There are sets of constant density which do not contain a modular line $\{x,y,z\}$ for which the numbers of solutions of $x_i + y_i + z_i =a(mod~3)$ for $a=0,1,2$ is never a permutation of $(0,m,2m)$.

Proof: Consider all vectors where the sum of the coordinates is zero modulo 3. This property is preserved under sums but it does not hold for the sums we are looking at. (All the quantities: 0+m+4m, 0+0 +4m, 0+2m+2m, 0+2m+0, m, 2m are not divisible by 3.)

11. A strong variant form of the problem

Here are innocent-looking variants of Problem 1: (the existence of modular lines)

Problem 6:  How large can a set $F$ in $\Gamma(7m)$  be without three vectors x, y and z such that $|\{i:x_i+y_i+z_i=a\}|=o(mod~m)$  for $a=0,1,2,3,4,5,6$?

Problem 7:  How large can a set F in $\Gamma (7m)$  be without three vectors x, y and z such that $|\{i: x_1+y_i+z_i=a\}| = m$ for every a=0,1,2,3,4,5,6? Continue reading

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?

Polymath1: Success!

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!

Frankl-Rodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A)

Voita Rodl

I would like to tell you about a research project in progress with Roy Meshulam. (We started it in the summer, but then moved to other things;  so far there are interesting insights, and perhaps problems, but not substantial results. Noga Alon contributed an important observation, and Jeff Kahn and Gabor Simonyi helpful comments.)

Roy and I are friends and have been discussing various mathematical problems for decades. In the last few years we have studied together topological Helly-type theorems and have written several papers together. Our most recent success was finding a topological version of a Helly-type theorem by Nina Amenta. This post is on another problem.

As always, and more so in the spirit of Nielsen’s and Gowers’s recent suggestions:  comments, ideas, related problems, lemmas, and discussions  are welcome.  Links or references to earlier works (published and unpublished) are also welcome.  I thought to wait with this story after I discuss the Frankl-Wilson theorem and the Frankl-Rodl theorem in my extremal combinatorics series. But as this project is somewhat related to the density Hales-Jewett project discussed over Gowers’s blog (and even more to this thread at Tao’s blog), I decided to go ahead with it.

Part A: Finding generalized solutions for the cap set problem

1. Modular-lines-free-subsets

Let $n=3m$. A modular line in $T(n)= \{0,1,2\}^n$ is a set of  three elements $x,y,z$ such that the number of coordinates $i$ for which $x_i + y_i + z_i =a$ is zero modulo $m$ for $a=0,1,2$. (The sum $x_i+y_i+z_i$ is taken modulo 3.)

Problem 1:  How large can a subset $F$ of $T(n)$ be without containing a modular line? Prove that $|F| < (3-\epsilon)^n$, for some constant $\epsilon >0$.

2. Why? avoiding lines (3-term arithmetic progressions) in $Z_3^n$..

The following is a well-known problem:

Problem 2: Find the largest size $f(n)$ of a set $A \subset Z_3^n$ without an arithmetic progression of size 3. In this case an arithmetic progression of size three is simply a sequence of three elements $x, y$ and $z$ such that $x+y+z=0$. In other words, an arithmetic progression is simply an affine line.

This problem was discussed by Frankl, Graham, and Rodl in 1987 (and perhaps was posed even earlier) and they showed that $f(n)=o(3^n)$. Roy Meshulam proved that $f(n) \le 3^n/n$. This is a beautiful and clear application of Roth’s argument (for his famous theorem on the density of sets without 3-term arithmetic progressions,) for the case of subsets of $\{1,2,\dots,n\}$. Ten years ago Roy and I tried quite hard to push this Fourier-theoretic argument and to get a better bound, even slightly, even very slightly. We did not succeed. (And so far, nobody else has; a recent impressive result of Tom Sanders for 3-term arithmetic progressions without a repeated element for subsets of  $Z_4^n$ gives reason for optimism.) Let us write $f(n)=3^n/g(n)$. The best lower bound on $g(n)$ is $n$. There is a construction of Edell showing that $f(n) \ge2.2^n$ and thus the best upper bound for $g(n)$ is more than $1.3^n$. The gap is huge! What is the true value? Terry Tao wrote a lovely post on this problem. A set in $Z_3^n$ without a 3-term arithmetic progression (or alternatively not containing an affine line) is called a cap set.

Let me mention that the set of 0-1 vectors of length $n$ is a very simple example of a cap set of size $2^n$; choosing a set at random works if the size is less than $3^{n/3}$.   Problem 1 is a variation on problem 2.  Continue reading

Mathematics, Science, and Blogs

Michael Nielsen wrote a lovely essay entitled “Doing science online” about  mathematics, science,  and blogs. Michael’s primary example is a post over Terry Tao’s blog about the Navier-Stokes equation and he suggests blogs as a way of scaling up scientific conversation. Michael is writing a book called “The Future of Science.” He is a strong advocate of doing science in the open, and regard these changes as truly revolutionary.  (The term “Science 2.0″ is mentioned in the remarks.)

Michael’s post triggered Tim Gowers to present his thoughts about massive collaboration in mathematics, and this post is also very interesting with interesting follow-up remarks.  Tim Gowers mentioned the n-category cafe as a place where a whole research programme is advanced on a blog. Terry Tao mentioned comments on posts on his open-problems series as having some value. He  mentioned, in particular, the post on Mahler’s conjecture. (Also I think some discussions over Scott Aaronson’s blog had the nature of discussing specific technical math (coming from CS) problems.)

Tim actually proposes an experiment: trying to solve collectively a specific math problem. This would be interesting!!! I suppose we need to give such an effort over a blog a longer than ususal life-span – a few months perhaps. (And maybe not to start with a terribly difficult problem.) (What can be an appropriate control experiment though?)

Ben Webster in “Secret blogging seminar”  mentioned, in this context, earlier interesting related posts about “Working in secret“.

Christian Elsholtz mentioned on Gowers’s blog an intermediate problem (called “Moser’s cube problem”) where you look not for combinatorial lines (where the undetermined coordinates should be 1 in x 2 in y and 3 in z), and not for an affine line (where it should be 1,2,3 in x y and z in any order), but for a line: it can be 1 in x 2 in y and 3 in z or 3 in x 2 in y and 1 in z.

Update: Things are moving fast regarding Gowers’s massive collaboration experiment. He peoposes to study together a new approach to the $k=3$ “density Hales -Jewett theorem”. A background post apears here. Hillel Furstenberg and Izzy Katznelson’s proof of the density Hales-Jewett theorem was a crowning achievement of the ergodic theory method towards Szemeredi’s theorem. Like the case for Furstenberg’s proof of Szemeredi’s theorem itself the case $k=3$ was considerably simpler and had appeared in an earlier paper by Hillel and Izzy. The recent extensions of Szemeredi regularity lemma that led to simpler combinatorial proof of Szemeredi’s theorem did not led so far to simpler proofs for the density Hales-Jewett case. If you look at Tim’s background post let me ask you this: What is the case $k=2$ of the density Hales-Jewett’s theorem? It is something familiar that we talked about!

Here is a particularly silly problem that I suggested at some point along the discussions: How large can a family of subsets of an $n$-element set be without having two sets A and B such that the number of elements in A but not in B is twice the number of elements in B but not in A?

Update: This problem was completely reolved by Imre Leader and Eoin Long, their paper Tilted Sperner families contains also related results and conjectures.

Massive collaboration in art (click the picture for details)

Q: What is the case $k=2$of the density Hales-Jewett’s theorem? A: It is  Sperner’s theorem! (that we discussed in this post.)

I will keep updating about news from Tim’s project. [Last update is from October 21].  More updates: Tim’s project is getting quickly off the ground. A useful wiki was established. More update: It is probably successful