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

May
25
comment n-partite n-clique
I haven't checked, but it seems likely to me that a random graph will be a counterexample: you need a very high edge probability to get an n-clique and I think probably a lot lower to satisfy your conditions with high probability.
May
25
comment n-partite n-clique
FWIW here is a reformulation (I think). Let G be a graph with vertex set the edges of the complete bipartite graph K(n,n). Suppose that each vertex of G is contained in a perfect matching in K(n,n) and is joined to all the other edges in that perfect matching. Prove that G contains an n-clique.
May
25
comment Is anything known about this braid group quotient?
In a very elementary way I observed that when thinking about it. Using the third relation (the one that takes a string and passes it round all the other strings) and applying it to each string in turn, you get not a single twist but a double twist.
May
23
comment Is anything known about this braid group quotient?
Looking again at the paper by Gillette and van Buskirk, I see that (if I understand correctly) my group is the mapping class group but not the spherical braid group: the mapping class group adds an extra relation that allows you to twist the entire bottom of the braid through a full turn. So it's really the mapping class group that I'm interested in, though obviously the two are closely related.
May
23
comment Is anything known about this braid group quotient?
Ian Agol says in a comment below that Mosher showed that mapping class groups are automatic and hence that there is a polynomial-time algorithm for the word problem. Am I missing something here, or does that mean that the problem you mention was solved in 1995 (the date of Mosher's paper)?
May
18
comment Efficient computation of the least fraction with square denominator greater than the square root of 2.
Is it really the very best approximation you want to find, or would you be content with a non-trivially good one? (I'm not saying I have an answer even to that, but it feels quite a lot more feasible.)
May
14
comment Almost orthogonal vectors
Almost a year later I've just seen your comment. I had in mind that each point you put in rules out a spherical cap of spherical radius $\pi/2-\epsilon$. Since this has exponentially small volume, you can just greedily add exponentially many points. I think we must be talking at cross purposes though ...
May
14
comment A Bijection Between the Reals and Infinite Binary Strings
I should add that you need to encode whether the digit is before or after the decimal point.
May
14
comment A Bijection Between the Reals and Infinite Binary Strings
How about just encoding the non-terminating decimal expansion as a sequence of 0s and 1s digit by digit?
May
13
comment Rolling-ball game
I've just tried to find a proof of finiteness by using the pigeonhole principle to say that there are two long bits of path that take the same steps and start in almost exactly the same place with almost exactly the same orientation. It feels promising but I haven't managed to push it through.
May
13
comment Expectation of Gowers norm
Try thinking about the expectation of the $2^k$th power of the norm.
May
11
comment Is anything known about this braid group quotient?
I have seen that survey and I like it very much. Perhaps you can answer another question: is the list of methods for solving the word problem given in that paper essentially complete (in the sense that all methods are small variants of one of the methods mentioned there)?
May
11
comment Probability Problem Involving e
Any reason you go for that rather than the umbrella problem?
May
11
comment Probability Problem Involving e
One thought is generating functions. If you define f(m,n) to be the expected maximum if you start with m whole pills and n half pills, then f(m,n)=(m/n)f(m-1,n+1)+(1-m/n)f(m,n-1), except that when m or n is zero then you have to change the right hand side. Whether that leads to anything useful I don't immediately see.
Apr
21
comment Examples of eventual counterexamples
@Vectornaut, while I think your point is valid, it needs to be adjusted slightly, because the sequence is far from random. For example, in a pattern like that you won't get any primes unless the final digits are odd, and that increases the chance that any individual term is prime, which in turn decreases by quite a bit the chance that 137 terms are composite.
Apr
11
comment Why do Bernoulli numbers arise everywhere?
@Alex, I take it that by "simply connected" you mean "connected in a simple way".
Apr
10
comment Proofs without words
If you look at the picture in detail you can see that you are defining a sequence of continuous functions that converge uniformly. It's also clear from the picture that the image is dense. Therefore the limiting function exists and its image (being dense and compact) is the whole square. Of course, this proof isn't 100% visual but the non-visual part -- the basic facts about uniform convergence and compactness -- can be regarded as background knowledge. So I think it's a nice example.
Apr
2
comment Are the non trivial zeros of Zeta simple?
I don't claim to have read it carefully, but a quick glance through makes me very suspicious: the arguments seem to abstract somehow, and there are quite a lot of computer-generated pictures that look as though they may be intended as substitutes for rigorous proofs. Basically, I can't find the beef anywhere -- for instance, I don't see any sign of hard estimates. Coupling that with GH's comment, I am left thinking I can safely ignore this one unless the experts suddenly get excited about it.
Mar
24
comment Fun question in additive combinatorics
One way of putting Ben's comment when p=2 is to say that it's known that every prime of the form 4m+1 is a sum of two squares. It's easy to see from that that the limit is 2 when p=2. For larger p one would expect the limit to be at least as big, and this is indeed the case.
Mar
24
comment How can there be topological 4-manifolds with no differentiable structure?
I agree with you that after thinking about that example it becomes clearer that being able to smooth things out is not obvious.