gowers
Reputation
17,107
Next privilege 20,000 Rep.
Access 'trusted user' tools
 Jun 13 comment Are there any very hard unknots? I drew the "quotient" knot and the picture has been sitting on my desk for about a month. At first it looked hard to simplify, but then I saw that one could make a "hole" in the middle and take a chunk of knot and pass it up through the hole and back down again. This kind of global untwisting would, I think, have to be part of any unknotting procedure of the kind I fantasize about. At some point I might make the knot out of string and see whether I can indeed untie it fairly straightforwardly starting with that move. May 9 comment Are there any very hard unknots? Thank you for this example. It's quite interesting as it is in some sense a "product" of smaller knots. I tried replacing the bundles of strands (most of the time four strands) by a single strand and obtained a picture of a knot that I can't instantly see to be the unknot, though I did find a local way of reducing the number of crossings. If this "quotient" knot is not the unknot, then it's a very interesting example. Mar 29 comment What can be proved about the Ramanujan conjecture using elementary means? I don't mind complex analysis, but I'm wondering whether a "non-structural" proof is possible. Without saying precisely what I mean by that, I would say that modular forms are on the wrong side of the boundary. Mar 29 comment What can be proved about the Ramanujan conjecture using elementary means? Ah, I see the point now. OK, I'll go back and add a condition. Mar 29 comment What can be proved about the Ramanujan conjecture using elementary means? I'm taking $1-q^{a_r}$, and not $1+(-q)^{a_r}$. Oct 26 comment Believing the Conjectures Going back to your hypothetical Tsirelson story, I still don't see what Maximize adds to it. Why not just say that if you've tried hard to prove a conjecture, it becomes more reasonable to doubt it, regardless of what that conjecture looks like? (This doesn't apply to all conjectures: for example, our failure to prove the twin prime conjecture doesn't suggest that it might be false, since there are good heuristic reasons to expect both that it is true and that it is hard to prove.) Oct 26 comment Believing the Conjectures This discussion, which I find very interesting by the way, leaves me with the feeling that I don't understand very well what the rules of thumb are really saying and what their purpose is. I agree about Banach space theory: in some ways it is a very structureless subject, because any old bunch of functionals can be used to define a norm (as long as you've got enough of them that you don't have just a seminorm), but from time to time it springs surprises -- the almost negligible constraints nevertheless interestingly restrict what you can do. Oct 26 comment Believing the Conjectures The general point I'm making here is that in this context it's the mathematics that tells us to what extent Maximize is an appropriate principle, rather than the principle that is guiding our mathematical expectations. Oct 26 comment Believing the Conjectures Is Tsirelson's space an example of the success of Maximize? Again, I have my doubts. Before his example, it was reasonable to try to prove that every space did contain $c_0$ or $\ell_p$ -- all known spaces did, sometimes for quite non-trivial reasons. I would contend that it was only after (i) a failure, despite considerable efforts, to prove positive theorems and (ii) Tsirelson's example that it became reasonable to believe quite strongly that if you can't easily prove something about a general Banach space, then it is probably false. And there have been counterexamples to that principle ... Oct 26 comment Believing the Conjectures As for Maximize, I find it unhelpful in this context, since it is not clear what is "likely to occur". For example, it is still open whether there exists an infinite-dimensional Banach space such that every operator defined on it is a multiple of the identity plus a nuclear operator. I feel as though the answer could go either way, and no principle like Maximize is going to alter that perception. On the other hand, the existence of examples with comparable properties, such as Argyros and Haydon's construction where "nuclear" is replaced by "compact", does have an impact. Oct 26 comment Believing the Conjectures The fact that there ought to be a separable example is too trivial to count as a success of Reflection, since if there is any example at all, you can take a separable subspace of it and then you've got a separable example. Sep 8 comment Is every distance-regular graph vertex-transitive? Yes, but the hypercubes are vertex transitive, as are most of the obvious families. Sep 6 comment A combination of two well-known complexity problems @joro, what you're asking is in a sense what's in the back of my mind when I asked the original question: hard instances of graph isomorphism are rather delicate, so can they be combined with a condition about containing Hamilton cycles? If they can't, then the answer to my question is that you can indeed distinguish between the two situations. Sep 6 comment A combination of two well-known complexity problems @Suvrit, if you were to take two typical hard instances for the Hamilton cycle problem, one that contains a Hamilton cycle and one that doesn't, then it is very likely that it will be easy to tell that they are non-isomorphic. (For example, their degree sequences are likely to differ.) In the other direction, if you have two graphs of large minimal degree that are a difficult case for graph isomorphism, they will both contain Hamilton cycles. I'm not sure whether this is answering your question though. Sep 6 comment A combination of two well-known complexity problems @Gerhard "I'm sure it's the latter" Paseman, it's only half the latter. I know what zero-knowledge proofs are, but don't immediately see how they answer the question. Could you spell it out? Sep 6 comment A combination of two well-known complexity problems @Richard Stanley -- that's why I insist that they are both hard, though obviously if graph isomorphism is hard then so are NP-complete problems so I could have just said "assuming that graph isomorphism is hard". Sep 5 comment A combination of two well-known complexity problems A quick remark: one can of course ask the same question for many other NP-complete problems -- I'd be just as interested, for example, in the same question but with "clique of size m" instead of "Hamilton cycle". Apr 3 comment Almost orthogonal vectors Looking at this almost a further year later, I'm still confused by Bill's remark, because what I wrote in the previous comment seems (i) correct and (ii) the standard volume argument that he discusses. Can anyone shed light on this? Mar 31 comment What are the Applications of Hypergraphs Here are two partial explanations for why algorithms based on hypergraphs are less common than algorithms based on graphs. 1. Some polynomial-time algorithms for graphs turn into NP-complete problems when you try to generalize them to hypergraphs (e.g., finding a perfect matching). 2. We often use graphs to model symmetric binary relations, and symmetric binary relations appear much more frequently than symmetric ternary relations (and beyond). Mar 31 comment functions satisfying “one-one iff onto” Does $f$ have to be continuous, or something like that? Otherwise, the result seems to be trivially false because you can mess about with the map on a set of measure zero.