15,454 reputation
1188143
bio website gowers.wordpress.com
location
age
visits member for 4 years, 11 months
seen Mar 16 at 23:40
Mathematics professor at Cambridge

Jul
8
comment Nonexistence of an approximately distance-preserving map between discrete cubes
You're right about projection on to the first $n-1$ coordinates. Actually, the case that I'm really interested in is $n/2$ dimensions. In an hour or so I'll modify the question accordingly.
Jun
22
comment Are there very strongly pseudorandom permutations?
I think I've now found a construction that does what I want.
Jun
20
comment Are there any good websites for hosting discussions of mathematical papers?
I think you can make contributions by registering directly with the site, and anybody can read it. But Google Plus is a particularly convenient way of contributing, since all you have to do is write a normal post and add the #spnetwork hashtag. In due course other social networks will be added, but Google Plus has the advantage that public posts are genuinely public.
Jun
20
comment Are there very strongly pseudorandom permutations?
Actually, scratch that -- I miscalculated the information-theoretic bound, which gives that exponentially many would be needed.
Jun
19
comment Are there very strongly pseudorandom permutations?
I now think it may be possible to do something by composing polynomially many Feistel permutations.
Jun
19
comment Are there very strongly pseudorandom permutations?
Yes. I was vague about it, but the precise requirement I would like is that $k$ should be at most a polynomial function of $n$ (or perhaps a very slightly superpolynomial function).
Jun
18
comment Are there very strongly pseudorandom permutations?
Good point -- thanks for the tip.
Jun
18
comment Are there very strongly pseudorandom permutations?
I have now found a source that seems to suggest that the Luby-Rackoff construction won't give hardness greater than $2^n$. So it looks as though a different idea would be needed. But maybe there are some different ideas out there.
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.