DBD2 — success of a kind | Gowers's Weblog

DBD2 — success of a kind

Yesterday, as I was walking to my office in the morning, I planned to write a post in which I was going to say that Polymath9 had basically been a failure, though not a failure I minded about, since it hadn’t had any significant negative consequences. Part of the reason I wanted to say that was that for a few weeks I’ve been thinking about other things, and it seems better to “close” a project publicly than to leave it in a strange limbo.

When I got to my office, those other things I’ve been thinking about (the project with Mohan Ganesalingam on theorem proving) commanded my attention and the post didn’t get written. And then in the evening, with impeccable timing, Pavel Pudlak sent me an email with an observation that shows that one of the statements that I was hoping was false is in fact true: every subset of $\{0,1\}^n$ can be Ramsey lifted to a very simple subset of a not much larger set. (If you have forgotten these definitions, or never read them in the first place, I’ll recap them in a moment.)

How much of a disaster is this? Well, it’s never a disaster to learn that a statement you wanted to go one way in fact goes the other way. It may be disappointing, but it’s much better to know the truth than to waste time chasing a fantasy. Also, there can be far more to it than that. The effect of discovering that your hopes are dashed is often that you readjust your hopes. If you had a subgoal that you now realize is unachievable, but you still believe that the main goal might be achievable, then your options have been narrowed down in a potentially useful way.

Is that the case here? I’ll offer a few preliminary thoughts on that question and see whether they lead to an interesting discussion. If they don’t, that’s fine — my general attitude is that I’m happy to think about all this on my own, but that I’d be even happier to discuss it with other people. The subtitle of this post is supposed to reflect the fact that I have gained something from making my ideas public, in that Pavel’s observation, though simple enough to understand, is one that I might have taken a long, or even infinite, time to make if I had worked entirely privately. So he has potentially saved me a lot of time, and that is one of the main points of mathematics done in the open.

Definitions

The basic idea I was pursuing was that perhaps we can find a property that distinguishes between subsets of $\{0,1\}^n$ (or Boolean functions) of low Boolean complexity and general subsets/functions of the following kind: a low-complexity set/function can be “lifted” from $\{0,1\}^n$ to a larger, but not too much larger, structure inside which it sits more simply. This basic idea was inspired by Martin’s proof that Borel sets are determined. After considering various possible ways of making the above ideas precise, and rejecting some of them when I realized that they couldn’t work, I arrived at the following set of definitions.

Complexity structures

An $n$ -dimensional complexity structure with alphabet $\Gamma$ is a subset $X\subset\Gamma^n$ . (Sometimes it is convenient to define it as a subset of $\Gamma_1\times\dots\times\Gamma_n$ , in which case the definitions have to be modified slightly.) If $X\subset\Gamma^n$ and $Y\subset\Theta^n$ are two $n$ -dimensional complexity structures, then I call a function $\pi:Y\to X$ a map if for every $i$ , $\pi(y)_i$ depends only on $y_i$ . Equivalently, $\pi$ is of the form $\pi(y)=(\pi_1(y_1),\dots,\pi_n(y_n))$ .

A basic $i$ -set in a complexity structure $X\subset\Gamma^n$ is a subset of the form $\{x\in X:x_i\in\Delta\}$ for some $\Delta\subset\Gamma$ . A basic set is any set that is a basic $i$ -set for some $i$ . Note that if $\pi:Y\to X$ is a map and $B\subset X$ is a basic set in $X$ , then $\pi^{-1}(B)$ is a basic set in $Y$ .

The circuit complexity or straight-line complexity of a subset $A$ of a complexity structure $X$ is the minimal $m$ for which there exists a sequence $A_1,A_2,\dots,A_m$ of subsets of $X$ such that every $A_i$ is a basic set or a union or intersection of two sets earlier in the sequence, and $A_m=A$ . If $\pi:Y\to X$ is a map and $A\subset X$ , then the circuit complexity of $\pi^{-1}(A)$ is at most the circuit complexity of $A$ , since $\pi^{-1}$ preserves basic sets and Boolean operations.

I often, and perhaps slightly confusingly, describe a map $\pi:Y\to X$ as a lift of $X$ . That’s because it’s really $\pi^{-1}$ and its effect on subsets of $X$ that I am interested in.

The shrinking-neighbourhoods game

Let $X\subset\Gamma^n$ be a complexity structure. A coordinate specification is a statement of the form $x_i=\gamma$ for some $i\leq n$ and $\gamma\in\Gamma$ .

Let us assume that $n$ is even and let $m=n/2$ . Then the shrinking-neighbourhoods game is a two-player game played according to the following rules.

Player I starts, and the players alternately make coordinate specifications.
Player I’s specifications must be of coordinates $x_i$ with $i\leq m$ , and Player II’s must be of coordinates $x_j$ with $m+1\leq j\leq n$ .
No coordinate may be specified more than once.
At every stage of the game, there must exist a sequence $x\in X$ that obeys all the specifications made so far.

A subset $A$ of $X$ is I-winning if Player I has a winning strategy for ensuring that after all $n$ coordinates have been specified, the sequence that satisfies those specifications (which is obviously unique) belongs to $A$ . It is II-winning if Player II has a winning strategy for ensuring that the final sequence belongs to $A$ .

Since finite games are determined, if $A$ is any subset of $X$ , then either $A$ is I-winning or $A^c$ is II-winning.

This can be thought of as a kind of Ramsey property, something that I mention only to explain what would otherwise be a rather strange piece of terminology. I say that a map $\pi:Y\to X$ between complexity structures is Ramsey if for every I-winning subset $B$ of $Y$ , $\pi(B)$ is a I-winning subset of $X$ , and for every II-winning subset $B$ of $Y$ , $\pi(B)$ is a II-winning subset of $X$ . In other words, Ramsey maps preserve winning sets and the player that wins.

It is an easy exercise to show that $\pi$ is Ramsey if and only if for every subset $A\subset X$ , if $A$ is I-winning then $\pi^{-1}(A)$ is I-winning and if $A$ is II-winning then $\pi^{-1}(A)$ is II-winning. (This isn’t quite a triviality, however: it uses finite determinacy.) This formulation is often more convenient.

What I hoped was true

I don’t want to be too precise about this, because part of what I hoped was that the correct statement would to some extent emerge from the proof. But roughly what I wanted was the following.

If $A\subset\{0,1\}^n$ is a set with low circuit complexity, then there is a complexity structure $Y$ that is not too large, and a Ramsey map $\pi:Y\to\{0,1\}^n$ , such that $\pi^{-1}(A)$ is simple.
If $A$ is a random set then no such pair $(Y,\pi)$ exists.
There is an NP set $A$ for which no such pair $(Y,\pi)$ exists.

Achieving 1 and 2 together would give a non-trivial example of a property that distinguishes between sets of low circuit complexity and random sets, which is a highly desirable thing to do, given the difficulties associated with the natural-proofs barrier, even if it doesn’t immediately solve the P versus NP problem. And achieving 1 and 3 together would show that P doesn’t equal NP.

However, it was far from clear whether these statements were true under any reasonable interpretation. Perhaps even sets of low circuit complexity require enormous sets $Y$ , or perhaps there is some simple way of lifting arbitrary sets with only a small $Y$ . Either of these possibilities would show that the existence of efficient Ramsey lifts does not distinguish between sets of low circuit complexity and arbitrary sets. What Pavel sent me yesterday was an observation that basically shows that the second difficulty occurs. That is, he showed that one can lift an arbitrary set quite simply.

Before I present his example, I’ll just briefly mention that I had a philosophical reason for thinking that such an example was unlikely to exist, which was that any truly simple example ought to have an infinite counterpart, but in the infinite case it is not true that arbitrary sets can be efficiently lifted. I’ll try to give some sort of indication later of why this argument does not apply to Pavel’s example.

Why what I hoped was true is false

I’ll begin by describing the example in an informal way and then I’ll make it more formal. (Pavel provided both descriptions in his message to me, so I’m not adding anything here.)

Let $A\subset\{0,1\}^n$ be any set and define an auxiliary game played on $\{0,1\}^n$ as follows. It’s just like the shrinking-neighbourhoods game, except that at some point each player must declare a bit, and the parity of the two bits they declare must be odd if the final sequence belongs to $A$ and even if it doesn’t. (So they must both play consistently with this restriction.)

Suppose that Player I has a winning strategy for the original game for some set $W$ . Then she can win the auxiliary game with payoff set $\pi^{-1}(W)$ as follows. Let $n=2m$ as usual. For her first $m-1$ moves, she simply plays her winning strategy for the original game (ignoring the extra bit that Player II declares if he declares it). Then for her last move, she continues to play the winning strategy, but she also declares her extra bit. If Player II has declared his bit, then she looks at the two possible sequences that can result after Player II’s final move. If they are both in $A$ or both in $A^c$ , then she makes sure that the parity of the two bits is odd in the first case and even in the second. If one sequence is in $A$ and the other in $A^c$ then it does not matter what she chooses for her extra bit. If Player II has not declared his bit, then she can play her extra bit arbitrarily, which will oblige Player II to ensure that the parity of the two bits is equal to 1 if the final sequence is in $A$ and 0 otherwise.

Now suppose that Player II has a winning strategy for $W$ in the original game. In this case the proof is even simpler. He just plays this strategy, ignoring Player I’s extra bit when she plays it, and declares his extra bit right at the end, making sure that the final parity of the two bits correctly reflects whether the sequence is in $A$ .

Finally, note that to tell whether the eventual sequence in the auxiliary game belongs to $\pi^{-1}(A)$ , it is only necessary to look at the two extra bits. So whether or not a point belongs to $\pi^{-1}(A)$ can be determined by just two coordinates of that point (though which coordinates they are can vary from point to point). That makes $\pi^{-1}(A)$ a very simple set (I call it 2-open, since it is a union of “2-basic open” sets), even though the “board” on which the auxiliary game is played is not very large.

Now let me give a precise definition of the complexity structure $Y$ . It consists of all sequences $(y_1,\dots,y_n)$ with the following properties.

For exactly one $i\leq m$ , $y_i\in\{0,1\}^2$ . In this case we will write $y_i=(x_i,a)$ .
For exactly one $j$ with $m+1\leq j\leq n$ , $y_j\in\{0,1\}^2$ . In this case we will write $y_j=(x_j,b)$ .
For all other $k$ we have $y_k\in\{0,1\}$ and write $y_k=x_k$ .
$a\oplus b=1$ if $(x_1,\dots,x_n)\in A$ and 0 otherwise.

So there are six possibilities for each coordinate (since it can be an arbitrary element of $\{0,1\}\cup\{0,1\}^2$ ). Thus, we can regard $Y$ as a subset of $\{0,1,2,3,4,5\}^n$ , which is not that much bigger than $\{0,1\}^n$ .

The map $\pi:Y\to\{0,1\}^n$ does the obvious thing and takes $(y_1,\dots,y_n)$ to $(x_1,\dots,x_n)$ . It is then easy to see that the shrinking-neighbourhoods game in $Y$ with payoff set $\pi^{-1}(A)$ is basically the same as the auxiliary game I described earlier.

Is that the end of the story?

It may be, but I think it would be a mistake to abandon the project immediately without thinking fairly hard about what has gone wrong so far. Is it a sign that nothing even remotely like this idea could work, or is it a sign that the problems are more “local” and that certain definitions should be adjusted? In the latter case, what might a new set of definitions look like?

I’ll try to explain in a future post why I think that it is worth exploring the general strategy of attempting to show that sets of low circuit complexity can be lifted (in some sense yet to be determined) to simple sets (also in some sense yet to be determined). For now, I’d just like to make the general point that there are many aspects of the definitions above that could be changed. For the moment, I still like the definition of a complexity structure, because when I came up with it I felt myself “forced” to it. (It would take a bit of time to remember why this was, however.) I also quite like the idea that the maps we want to consider are ones that preserve some class of sets, since that gives quite a bit of flexibility. We need the class of sets to be fairly complicated, since otherwise there is a danger that verifying that the sets are preserved becomes too easy, which could then mean that the property “can be efficiently lifted” becomes too simple and is ruled out by known complexity barriers. (I’m thinking here not just of the natural-proofs barrier but also of an interesting extension of it due to Rudich.)

Looking for a class of sets might seem a hopelessly complicated task, but there are several constraints on what the class of sets can be like for the proof to work. One important one is that it should be definable in any complexity structure. So it needs to be defined in a way that isn’t too specific to $\{0,1\}^n$ . It might be worth making precise what this restriction actually means.

Why doesn’t the example have an infinite analogue?

The rough idea here is that in Pavel’s example it is possible to provide the extra information (that is, the extra bits in the auxiliary game) right at the end of the game. In an infinite game there is no such thing as “right at the end of the game”: whenever you play, you’re still very near the beginning. This difference has caused me difficulties in the past, and I think it is worth focusing on again. Is there some natural way of ruling out this postponing of the extra information?

One crude idea is to rule it out by … ruling it out. For example, we could define a set to be $k$ -winning for Player I/II if there is a winning strategy for Player I/II such that after her/his first $k$ moves the outcome of the game is already decided. There is probably some serious drawback with such a simple-minded approach, but it is worth finding that drawback. I have given very little thought to it, so there may be something very obviously bad about it. One small point is that if, as I think is likely to be necessary, a proof that low-complexity sets can be lifted is inductive in nature, then we will want a composition of simplifying lifts to be a simplifying lift. So we would want our lifts to be such that $k$ -winning sets lift to $k$ -winning sets for the same player (and not just that winning sets lift to winning sets). So we would preserve the $k$ -winning sets we’ve already created, and attempt to create some new ones.

I think that one of the reasons Polymath9 hasn’t taken off is that I presented too much material all at once. (I did try to make it clear that it wasn’t necessary to wade through it all, but even so I can see that it might have been off-putting.) In an effort to avoid that mistake this time, I’m going to resist the temptation to think further about how to respond to Pavel’s lift and go ahead and put up this post. If I do have further ideas, I’ll post them as comments.

This entry was posted on January 9, 2014 at 12:54 pm and is filed under complexity, polymath9. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

14 Responses to “DBD2 — success of a kind”

Gil Kalai Says:
January 9, 2014 at 6:31 pm | Reply
This is a nice developement. Kudos to Pavel Pudlak. Of course, we are testing simultaneously both the mathematical suggestions (BDB in this case) and the polymathing idea. Wouldnt it be preferable in this case to move to a more traditional form of working or collaborating? (E.g., discussing it further with Pavel.)
- gowers Says:
  January 9, 2014 at 10:13 pm
  That is a possibility that has already occurred to me and that I am considering seriously (not that I’ve asked Pavel yet what he thinks about the idea). But if anybody else has been thinking about these ideas and would like to be involved in some future more traditional collaboration, I don’t want to exclude people. Also, I still like the idea of occasionally posting if there are any interesting developments, whether or not they are sufficiently concrete to be publishable.
gowers Says:
January 10, 2014 at 10:58 am | Reply
This is a brief comment to say that at least for the moment I feel that Pavel’s observation is telling me that I’ve got my definitions wrong rather than that the entire approach is doomed. It’s entirely possible that I’ll change my mind about this, but let me at least try to explain why I think it. I’ve partly done so already in the post above.

Throughout the project, I’ve been trying to keep the analogies with Martin’s theorem as close as possible. Perhaps it would be helpful if I explained why I abandoned one obvious idea, which is to have a game where Player I picks the first coordinate, Player II the second, and so on. (Instead, the players get to pick any unpicked coordinates in their halves.) Then we have a game tree where the nodes are labelled by sequences $(x_1,\dots,x_k)$ .

Let’s stick with the case where we have all 01-sequences of length $n$ , so the tree is just a binary tree. Then the set $\{x:x_n=0\}$ corresponds to a set of leaves of this tree that contains exactly one leaf out of each pair of the form $(x_1,\dots,x_{n-1},0),(x_1,\dots,x_{n-1},1)$ . Now we want that set to be “simple” in some sense (the sense being something like that it lifts to a very simple set in a not too much larger tree). But the problem with this is that if our definition of “simple” is invariant under automorphisms of the tree, then the simplicity of this set would imply the simplicity of a huge number of other sets: indeed, all sets $A$ such that if $x\in A$ then $x\oplus e_n\notin A$ . And from such sets you can make all sets with just a few Boolean operations.

It was because of that observation that I felt forced to abandon the tree approach. In the infinite case, you can get away with trees because every coordinate is only finitely far along and therefore “very near the beginning”. But that phenomenon has no analogue in the finite case. The shrinking-neighbourhoods game felt like the minimal modification I could make to the tree set-up that would ensure that all the sets $\{x:x_i=0\}$ were simple.

I’ll continue this discussion in a new comment (the idea being to try to keep to one observation per comment).
- gowers Says:
  January 10, 2014 at 12:00 pm
  Now let’s consider a big difference between the lifts Martin defined (and some that I have defined in the finite case) and the lift that Pavel defines. Suppose we play the auxiliary game and take $A$ itself as the payoff set. One might expect, given that $\pi^{-1}(A)$ is substantially simpler than $A$ , that the strategy for the player who wins to be much simpler for $\pi^{-1}(A)$ than it is for $A$ . And indeed that is the case for Martin’s lifts. But it is not at all the case for Pavel’s lift: the game is pretty well unaltered. (I don’t quite mean that: if one of the players declares the extra bit early on, then the other player can quickly force the outcome of the game, but assuming “sensible” play, the extra bits have no real effect on how the game is played.)
  
  This is an example of a curious phenomenon that can occur in complexity spaces: that a set may be “topologically simple” but “strategically complicated”. I don’t have a good example to hand, so let me settle for an explanation of why I believe it should be reasonably easy to construct one. Consider the set $x_1=x_2=0$ in some complexity structure $X\subset\{0,1\}^n$ . One might think that there was a blindingly obvious strategy for Player I, which is simply to play the move $x_1=0$ and then the move $x_2=0$ . But what if there are no sequences in $X$ with $x_1=x_2=0$ and $x_{m+1}=0$ ? Then starting with the move $x_1=0$ would be a mistake, since Player II could respond with $x_{m+1}=0$ .
  
  But can’t Player II do that anyway? No, not necessarily, since there might be no sequences with $x_{m+1}=0$ and $x_3=0$ . In that case, Player I might have a winning strategy, but only if she begins with the move $x_3=0$ .
  
  I think that’s enough to demonstrate that there is a disconnect between topological simplicity and simplicity from the point of view of the shrinking-neighbourhoods game.
  
  Since that probably counts as a single unit of observation, I’ll post it and again continue in a separate comment.
- gowers Says:
  January 10, 2014 at 12:23 pm
  Before leaping in and trying to guess a definition of “strategically simple” it might be a good idea to think about the complexity of strategies for 2-open games played in $\{0,1\}^n$ . That is, we are given a set of specifications of the form $(x_i,x_j)=(\epsilon_i,\epsilon_j)$ , and Player I is trying to end up with a sequence $x$ for which at least one of these specifications holds, while Player II is trying to stop her. Are there sets of pairs for which it is very difficult to decide who wins the game? My guess is yes, but that is just a guess at this stage.
- gowers Says:
  January 10, 2014 at 2:44 pm
  Let’s consider the question just above in the case where all the specifications that define the payoff set $A$ are ones where $1\leq i\leq m$ and $m+1\leq j\leq n$ . Then we can think of the game as follows. Each move that Player I makes determines a condition that Player II must satisfy, which will be a specification of certain coordinates between $m+1$ and $n$ . For instance, if two of the sets that define $A$ are $x_1=x_m=0$ and $x_1=x_{m+1}=0$ , then the move $x_1=0$ for Player I tells Player II that he must ensure that $x_m=x_{m+1}=1$ to have any chance of winning. For each $1\leq i\leq m$ and each $\epsilon\in\{0,1\}$ , let $C_{i,\epsilon}$ be the condition imposed on Player II by Player I playing the move $x_i=\epsilon$ . Then for each $i$ Player I can choose to impose the condition $C_{i,0}$ or the condition $C_{i,1}$ .
  
  Note that if there exist distinct $i_1,\dots,i_k$ and bits $\epsilon_1,\dots,\epsilon_k$ such that the conditions $C_{{i_j},\epsilon_j}$ are inconsistent, then Player I trivially has a winning strategy.
  
  However, the converse is far from true, which is what makes the game potentially interesting. Even if Player I does not have a set of incompatible conditions like that, she may be able to exploit what Player II does. For example, if $A$ is the set of all sequences $x$ such that $x_1=x_{m+1}$ or $x_1=x_{m+2}$ , then Player I cannot find an inconsistent set of conditions using different $x_i$ , but can win the game by waiting until Player II chooses either $x_{m+1}$ or $x_{m+2}$ and only then playing $x_1$ .
  
  Hmm, that was quite a useful example actually, since it shows that a set can be very simple indeed (it depends on just three coordinates) but that the player with a winning strategy may not be able to force a win until very near the end of the game. Here Player I has a winning strategy but if Player II waits until his last two moves before playing either of $x_{m+1}$ or $x_{m+2}$ , then Player I can’t get to the point where the outcome is decided until her final move. This seems to kill off the idea I had above about $k$ -winning sets. If a set as simple as this one, which lives in a complexity structure as simple as $\{0,1\}^n$ , is not $k$ -winning for any $k<m$ , then that does seem to suggest that $k$ -winningness for small $k$ is not a very good definition of simplicity.
gowers Says:
January 10, 2014 at 6:00 pm | Reply
In the post I said that a sensible definition of simplicity for subsets of $\{0,1\}^n$ would probably have to apply more or less unchanged to general complexity structures. But what does that mean? What kinds of systems of subsets of $\{0,1\}^n$ does it allow?

Here are two examples of definitions that carry over easily. The first is circuit complexity. We define a basic set to be a set that depends on just one coordinate, and then the circuit complexity of an arbitrary set $A$ is the length of the shortest sequence that ends with $A$ and has the property that every set in the sequence is a basic set or a union or intersection of two earlier sets in the sequence.

The second definition is that of a I-winning set. The shrinking-neighbourhoods game makes sense in any complexity structure and picks out a class of sets.

What do these two classes of sets have in common? Maybe it would help to give an example of a definition of a class of sets that does not generalize. Maybe one possibility would be the collection of subsets of $\{0,1\}^n$ of cardinality at least $2^{n-1}$ . That doesn’t feel like the kind of class I’m interested in, but why doesn’t “has cardinality at least half that of $X$ ” count as a valid definition? I don’t see an obvious answer to this question.

Or do I? Maybe a condition is that in some sense coordinates should not be special. So if you have a complexity structure like $\{0,1\}^n$ with lots of symmetry, then the definition of simplicity should be invariant under the maps $x\mapsto x\oplus e_i$ . (That is, if a set is simple and you change the $i$ th coordinate of each element, then the resulting set is still simple.)
- gowers Says:
  January 11, 2014 at 9:18 pm
  A condition that seems to be desirable but maybe not sufficient is as follows. We are looking for a definition of the form “ $A$ is a simple subset of $X$ if and only if $P(A,X)$ .” Now $X$ is a subset of some set $\Gamma^n$ . So we could insist that the property $P$ is invariant under automorphisms of $\Gamma$ . (The automorphisms I am thinking of are ones of the form $(x_1,\dots,x_n)\mapsto(\pi_1(x_1),\dots,\pi_n(x_n))$ , where each $\pi_i$ is a permutation of $\Gamma$ , and also ones of the form $(x_1,\dots,x_n)\mapsto(x_{\sigma(1)},\dots,x_{\sigma(n)})$ , and also compositions of those two types.) That is, if $\phi$ is an automorphism of $\Gamma^n$ and $A$ is a simple subset of $X$ , then $\phi(A)$ should be a simple subset of $\phi(X)$ .
vznvzn Says:
January 11, 2014 at 4:53 pm | Reply
bummer, yet still progress. it is better to have ventured a conjecture than to have never ventured one at all. think conway may have said something like “the 1st rule of conjectures is that they must be outrageous”. alas am still attempting to find that quote somewhere.
hey, math/science is trial and error at heart. hypothesize, test, prove, repeat. wash, lather, rinse, repeat.
as they say “it all comes out in the wash eventually”.

if anyone around here gets totally frustrated/desperate and youve hit bottom & are finally willing to try anything, plz let me know, Ive had an idea relating to hypergraph decompositions vs P vs NP lying around for over a yr, no expert feedback so far. (& frankly think it might even tie in somewhat with the generalization of szemeredi’s thm to hypergraphs…) it has many elements of circumstantial evidence pointing in its favor, would be happy to discuss at length with anyone interested & esp those with strong math bkg, long/intense attn span/perseverence & huge/”outrageous” ambitions.
gowers Says:
January 12, 2014 at 4:44 pm | Reply
Pavel has just emailed me with a further observation, which I reproduce here with his permission. The rest of this comment comes directly from his email.

—————————————-

I thought about modifying the concept of Ramsey lift so that the small lifts with the parity construction is avoided. One idea is not to have a fixed division of coordinates between the players, but to allow all possible divisions into two equal size parts. Another is to allow players to play any coordinates. It seems that this could eliminate the parity construction because if bits in two coordinates can determine the function, in some division the two coordinates may be used by the same player to his/her advantage. Since allowing any division substantially restricts the class of available lifts, I tried to modify your doubly exponential construction of a “universal” lift. I succeeded to modify it so that every subset of $X$ is lifted to a 2-open set, but later I realized that it is also possible to do a single exponential lift in a different way. The new trick seems to be robust and thus may also exclude other conjectures.

The idea is that in the lift $Y$ one of the players has to play the entire string $x$ , but if the player plays $x$ before the last move, the other player may cancel $x$ by playing a string that he prefers.

Here is a formal definition.

$y\in Y$ iff

1. there exist $x\in X$ , $i\in[n]$ and $a\in C_3$ (the group of order 3) such that $y_i=(x,a)$ and $y_j=x_j$ for $j\neq i$ ,

2. or there exist $i\neq j$ such that $y_i=(x',a)$ , $y_j=(x,a+1)$ , $x'_i=x_i$ , and $y_k=x_k$ for $k\neq i,j$ .

The projection $\pi$ sends $y$ to $x$ . Since for every $y\in\pi^{-1}(x)$ , $x$ is uniquely determined by two coordinates of $y$ , the lift of any subset of $X$ is 2-open.

Let $W\subseteq X$ be a winning set for one of the players. The player who has a winning strategy can play the same strategy in $Y$ until the other player plays a move of the form $y_i=(x',a)$ . If this is not the last move, the player with the winning strategy picks any $j\neq i$ and any $x\in W$ consistent with the previous moves and plays $y_j=(x,a+1)$ .

A natural question is why not to allow players to play just $f(x)$ instead of $x$ . This does not work because even if a player may choose the value of $f(x)$ as he wishes, it may restrict him so much that he will not be able to win. While playing $x$ restricts him even more, it also restricts the other player.
- Jason Dyer Says:
  February 27, 2014 at 7:12 pm
  Did this move to email collaboration?
  
  As far my own contribution to Polymath9 being stalled, I have to apologize; I was hit by my day job pretty hard. I only just now had the time to work through this post. I will duly try to break Pavel’s definition.
Polymath 9 | Euclidean Ramsey Theory Says:
January 19, 2014 at 10:51 pm | Reply
[…] It could possibly continue if the method could be modified to avoid the counterexample. at https://gowers.wordpress.com/2014/01/09/dbd2-success-of-a-kind/ is a post discussing this. Meanwhile Polymath 8 has spawned a new project Polymath 8b. […]
Jason Dyer Says:
February 27, 2014 at 7:30 pm | Reply
If you open up to “either player can move on any coordinate” aren’t you able to get a situation equivalent to various other games — for example, Hex? (Note: Determining if a particular position in Hex is winning is PSPACE complete.)
- Jason Dyer Says:
  February 28, 2014 at 3:16 pm
  Subsidiary query: most games encompass PSPACE-complete problems, not NP. Could it be more likely your construction could resolve P vs. PSPACE (also an open problem if I remember right?) more easily than P vs. NP?