The polymath blog

November 20, 2009

Proposals (Tim Gowers): Polynomial DHJ, and Littlewood’s problem

Filed under: polymath proposals — Gil Kalai @ 10:06 am

Tim Gowers described two additional proposed polymath projects. One about the first unknown cases of the polynomial Density Hales Jewett problem. Another about the Littelwood’s conjecture.

I will state one problem from each of these posts:

1) (Related to polynomial DHJ) Suppose you have a family \cal F of graphs on n labelled vertices, so that we do not two graphs in the family G,H such that H is a subgraph of G and the edges of G which are not in H form a clique. (A complete graph on 2 or more vertices.) can we conclude that |{\cal F}| =2^{o({{n} \choose {2}}}? (In other words, can we conclude that \cal F contains only a diminishing fraction of all graphs?)

Define the “distance” between two points in the unit cube as the product of the absolute value of the differences in the three coordinates. (See Tim’s remark below.)

2) (Related to Littlewood) Is it possible to find n points in the unit cube [0,1]^3 so that the “distance” between any two of them is at least 1/100000000000000000000n?

A negative answer to Littlewood’s problem will imply a positive answer to problem 2 (with some constant). So the pessimistic saddle thought would be that the answer to Problem 2 is yes without any bearing on Littlewood’s problem.


  1. It is important to clarify that the problem numbered (2) is not itself Littlewood’s problem but rather a related problem. Secondly, the “distance” is not what one might think. In fact, it is not even a distance. We define d(x,y) to be |x_1-y_1||x_2-y_2||x_3-y_3|. (Obviously if we were using the normal Euclidean distance then we could get Cn^3 points and that would be best possible.)

    Also, I find the problem (2) interesting in itself, so am not put off by the possibility that there might exist such a set of points even if the Littlewood conjecture is true. It would even, in a modest way, shed some light on the Littlewood conjecture, since it would demonstrate that the problem was “genuinely number-theoretic”. I say “in a modest way” because I get the impression that the experts more or less take for granted that it is a problem in number theory, so a conclusion of that kind would not change the way people think. But it would also provide some kind of explanation for why the problem is hard.

    Comment by gowers — November 20, 2009 @ 10:13 am | Reply

    • Dear Tim, yes, I overlooked the distance definition for a short time but then realized it cannot be the ususal distance and looked back in the post. I agree that problem (2) is very interesting! (In any direction it might go!)And if the answer is no it may be, as you explained, harder than proving LP but still could be useful.

      Comment by Gil Kalai — November 20, 2009 @ 12:10 pm | Reply

  2. I think I can solve the problem about points in the cube. One starts with this basis (2,1,-2,) (2,-2,1)(1/4,1/2,1/,2) normalize it then scale it down by a factor of 1/n^1/3 then construct it by a factor of two then we should be able to fit about 8n of these points in the cube and the closest we can get two points is where one point difference from another by one coordinate and then the product of the difference of the coordinates will be much larger than 10^-14 n^3 if I am counting the zeros correctly

    Comment by Kristal Cantwell — November 20, 2009 @ 9:10 pm | Reply

  3. The above doesn’t work as I can add vectors to get one coordinate zero making the product zero. I don’t think there is a lattice that is going to work.

    Comment by Kristal Cantwell — November 20, 2009 @ 9:42 pm | Reply

  4. According to a comment by Tim Gowers on his blog the answer to the question about points on the cube is yes. I think this is problem 5 on his blog. Here is a link to the comment with the solution to the problem:

    Comment by Kristal Cantwell — November 25, 2009 @ 5:47 am | Reply

    • The answer to Problem 5 is yes, but that is with the dyadic distance in each coordinate (that is, 2^{-k}, where k is the first place where the two binary expansions differ). For the ordinary Euclidean distance I do not know the answer — that’s Problem 3.

      Comment by gowers — December 2, 2009 @ 9:25 am | Reply

  5. Wow! This can be one particular of the most beneficial blogs We’ve ever arrive across on this subject. Basically Wonderful. I’m also a specialist in this topic so I can understand your effort.

    Comment by space with cheapest Red Bottom Evening — August 12, 2012 @ 7:27 am | Reply

RSS feed for comments on this post. TrackBack URI

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 )

Facebook photo

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

Connecting to %s

Blog at

%d bloggers like this: