Unsolved problems

Gowers.462: Incidentally, it occurs to me that we as a collective are doing what I as an individual mathematician do all the time: have an idea that leads to an interesting avenue to explore, get diverted by some temporarily more exciting idea, and forget about the first one. I think we should probably go through the various threads and collect together all the unsolved questions we can find (even if they are vague ones like, “Can an approach of the following kind work?”) and write them up in a single post. If this were a more massive collaboration, then we could work on the various questions in parallel, and update the post if they got answered, or reformulated, or if new questions arose.

See also a tidy problem page.

High-dimensional Sperner

Kalai.29: There is an analogous for Sperner but with high dimensional combinatorial spaces instead of "lines" but I do not remember the details (Kleitman(?) Katona(?) those are ususal suspects.)

Fourier approach

Kalai.29: A sort of generic attack one can try with Sperner is to look at [math]\displaystyle{ f=1_A }[/math] and express using the Fourier expansion of [math]\displaystyle{ f }[/math] the expression [math]\displaystyle{ \int f(x)f(y)1_{x\lt y} }[/math] where [math]\displaystyle{ x\lt y }[/math] is the partial order (=containment) for 0-1 vectors. Then one may hope that if [math]\displaystyle{ f }[/math] does not have a large Fourier coefficient then the expression above is similar to what we get when [math]\displaystyle{ A }[/math] is random and otherwise we can raise the density for subspaces. (OK, you can try it directly for the [math]\displaystyle{ k=3 }[/math] density HJ problem too but Sperner would be easier;) This is not unrealeted to the regularity philosophy.

Gowers.31: Gil, a quick remark about Fourier expansions and the [math]\displaystyle{ k=3 }[/math] case. I want to explain why I got stuck several years ago when I was trying to develop some kind of Fourier approach. Maybe with your deep knowledge of this kind of thing you can get me unstuck again.

The problem was that the natural Fourier basis in [math]\displaystyle{ [3]^n }[/math] was the basis you get by thinking of [math]\displaystyle{ [3]^n }[/math] as the group [math]\displaystyle{ \mathbb{Z}_3^n }[/math]. And if that’s what you do, then there appear to be examples that do not behave quasirandomly, but which do not have large Fourier coefficients either. For example, suppose that [math]\displaystyle{ n }[/math] is a multiple of 7, and you look at the set [math]\displaystyle{ A }[/math] of all sequences where the numbers of 1s, 2s and 3s are all multiples of 7. If two such sequences lie in a combinatorial line, then the set of variable coordinates for that line must have cardinality that’s a multiple of 7, from which it follows that the third point automatically lies in the line. So this set [math]\displaystyle{ A }[/math] has too many combinatorial lines. But I’m fairly sure — perhaps you can confirm this — that [math]\displaystyle{ A }[/math] has no large Fourier coefficient.

You can use this idea to produce lots more examples. Obviously you can replace 7 by some other small number. But you can also pick some arbitrary subset [math]\displaystyle{ W }[/math] of [math]\displaystyle{ [n] }[/math] and just ask that the numbers of 0s, 1s and 2s inside [math]\displaystyle{ W }[/math] are multiples of 7.

DHJ for dense subsets of a random set

Tao.18: A sufficiently good Varnavides type theorem for DHJ may have a separate application from the one in this project, namely to obtain a “relative” DHJ for dense subsets of a sufficiently pseudorandom subset of [math]\displaystyle{ [3]^n }[/math], much as I did with Ben Green for the primes (and which now has a significantly simpler proof by Gowers and by Reingold-Trevisan-Tulsiani-Vadhan). There are other obstacles though to that task (e.g. understanding the analogue of “dual functions” for Hales-Jewett), and so this is probably a bit off-topic.