Monthly Archives: May 2009

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.

17. Why weaker forms of the Frankl-Rodl Theorem follow from upper bounds on cap sets.

Consider Continue reading

Ehud Friedgut: Murphy’s Law of Breastfeeding Twins


This post is authored by Ehud Friedgut. Congratulations to Keren, Ehud and Michal for the birth of Shiri and Hillel!

Murphy’s law of breastfeeding twins, like all of Murphy’s laws, is supported by strong empirical evidence.

The twins’ feeding rhythm depends on your approach. If you decide to try and synchronize them in order to minimize your hassle and maximize your rest periods then twin A’s hunger will be governed by sine(t) and twin B’s by cosine(t).

If you decide to respect their natural rhythm in hope of falling into a fixed predictable pattern then twin A will follow sine(t) and twin B sine(\phi\times t), where \phi, the golden ratio, is the number hardest to approximate by rationals

The Amitsur-Levitzki Theorem for a Non Mathematician.

Yaacov Levitzki

The purpose of this post is to describe the Amitsur-Levitzki theorem: It is meant for people who are not necessarily mathematicians. Yet they need to know two things. The first is what matrices are. Very briefly, matrices are rectangular arrays of numbers. The second is that two n by n square matrices A and B can be multiplied. We denote their product by A x B and the product is again an n by n matrix. Unlike numbers, the product of matrices need not be commutative.  In other words A x B can be different from B x A.  The Wikipedia article about matrices is a good source.

We can multiply more than two matrices. We can write A x B x C for the product of A, B and C. The order of the matrices is important, but the order in which we perform the multiplication is not. This is because multiplication of matrices is associative,  that is

 (A x B ) x C  = A x (B x C).

Here is the Amitsur Levitzki Theorem for 2 x2 matrices:

For every four 2 x 2 matrices A, B, C, and D

A x B x C x D – B x A x C x D – A x B x D x C + B x A x D x C – A x C x B x D + C x A x B x D  +  A x C x D x B – C x A x D x B + A x D x B x C  – D x A x B x C – A x D x C x B  + D x A x C x B +  C  x D x A x B –   C x D x B x A –  D x C x A x B + D x C x B x A  – B x D x A x C  + B x D x C x A   + D x B x A x C  – D x B x C x A  + B x C x A x D  –  B x C x D x A  –  C x B x A x D + C x B x D x A = 0 .

In other words, we take the sum of the products of the matrices for all 24 possible orderings (permutations) with certain plus or minus signs, and lo and behold, we always get 0.

I will say more about it. But first a few remarks. The Amitsur-Levitzki theorem deals with products of 2k matrices of size k \times k. It is very beautiful and important and when it comes to mathematics, it doesn’t get much better than that. It can be a nice theorem to explain to non mathematicians, but in this case I have especially one non-mathematician in mind. Alex Levitzki – Yaacov Levitzkii’s son.  I promised Alex who is a famous HU biologist and chemist to tell him about his father’s theorem so why not share it with others. Yaacov Levitzki was one of the founding members of my department in Jerusalem. As a young man he came to Göttingen with the idea to study chemistry but attending a lecture by Emmy Noether converted him to mathematics.

The Amitsur Levitzki Theorem: For every 2n matrices of size n by n denoted by A_1,A_2,\dots A_{2n}, we have: 

\sum sgn (\sigma) \prod_{i=1}^{2n} A_{\sigma(i)} =0,

where the sum is taken over all (2n)! orderings (permutations) \sigma of \{1,2,\dots, 2n\} and sgn(\sigma) denotes the sign of the ordering  \sigma. Continue reading

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 is 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

The Thompson Group

Update (july 2009): A detailed posting on the Thompson group appeared on “Geometry and the Imagination,” Danny Calegary’s blog. In spite of two recent preprints one claiming that the Thompson group is amenable and the other claiming the opposite, the problem appears to be open.

We had yesteday, just a day after Independence Day, the annual meeting of the Israeli Mathematical Union and Mati Rubin talked about structures with the property that the automorphism group determines the structure up to isomorphism (even conjugacy). A lovely topic between logic and algebra with relations to many other things. Mati mentioned the Thompson group:

The set of  orientation-preserving piecewise-linear homeomorphisms of the unit interval, where the slopes are powers of two and the places where the slope changes are dyadic rationals.

There are many other presentation of the Thompson group. The wikipedia article looks very nice, and there was a special AIM workshop on it in 2004. There are many problems about the Thompson group, and one famous one is: Is it amenable?

Update (May 5): today Yuval Roichman mentioned that Patrick Dehornoy has used the Thompson group in his work regarding the diameter of the graph of the associahedron. This also brings me to the fascinating issue of coincidences that we should discuss sometime.