gowers
Reputation
16,912
Next privilege 20,000 Rep.
Access 'trusted user' tools
Badges
17 107 153
Newest
Impact
~1.1m people reached

• 0 helpful flags
• 394 votes cast

# 373 Comments

 Dec 1 comment k-pseudorandom measures The problem there is that the sets we are looking at are so sparse that the U^k norm of any function is dominated by the degenerate cubes and so tells you nothing. Also, the control of one norm by another is often OK in the dense case but breaks down if you are sitting inside a sparse random set (because the constant depends on the sparsity of the random set). Nov 29 comment k-pseudorandom measures It's not true that we removed the correlation condition -- that question is still open. What we did was look at functions bounded by random as opposed to pseudorandom measures, and we obtained best possible results by considering a specially constructued norm rather than the $U^k$ norm. The paper will be posted on the arXiv soon. Nov 21 comment Can infinity shorten proofs a lot? Not the latter as I go by my middle name. Happy to make the change but have not managed to find where I can do it. (Please excuse my utter incompetence.) Nov 20 comment Continued fractions using all natural integers I think you're right -- and indeed I was worried that something like that would happen. So it seems that the quotients have to grow rather fast to make the number transcendental. Nov 18 comment Can infinity shorten proofs a lot? I'm not sure I count induction either. It seems to me that one is not relying on infinity in a serious way to sum the first million cubes: one is saying, "If it's valid for 1 then it's valid for 2, and if it's valid for 2 then it's valid for 3, and ... and if it's valid for 999999 then it's valid for 1000000." That is a ridiculously long proof, but induction allows one to shorten it by giving a rule for when it's OK to put in the "..." (A more formal way of making the point is that the axiom of infinity isn't part of first-order Peano arithmetic.) Nov 17 comment Can infinity shorten proofs a lot? You can get the inequality quite easily I think. The log of n! is the sum of log m from 1 to n, which is at least the integral from 1 to n of log x, which is nlogn-n. Done. Nov 16 comment Can infinity shorten proofs a lot? That's a good example, but I think it may already form part of the presentation (when they talk about infinite sets and the work of Cantor). I'll check though. Nov 16 comment Can infinity shorten proofs a lot? Ultimately what's wanted is a very nice demonstration for the non-mathematician of why infinity is useful even if all you care about is finitary results. Nov 2 comment Are there any interesting examples of random NP-complete problems? Hmm, I'm wondering now if there's a boring answer, which is to take a problem that is hard on average and randomly restrict it in some natural way to a small class of instances. If that works, then maybe the question is interesting only in particular cases and not as a general question. Nov 2 comment Are there any interesting examples of random NP-complete problems? I think that is indeed what I meant (if I understand you correctly). As for my motivation, I just asked it out of curiosity. Nov 2 comment Are there any interesting examples of random NP-complete problems? I'm not asking for an instance of a problem to be NP complete. Let me go back to my example: I choose a random set X of clauses; I define SAT_X to be the problem, "Given Y subset X, are the clauses in Y simultaneously satisfiable?" So that is a problem (as opposed to a problem instance) that depends on X. If X is a random set of clauses that only just fails to be satisfiable, then it seems to me that SAT_X could, with high probability, be NP-complete, but I have no idea how to prove it because it looks hard to simulate a Turing machine if you don't have access to all clauses. Oct 31 comment Are there any interesting examples of random NP-complete problems? It's a little bit difficult to say exactly what I mean, which is why I tried to illustrate with an example. What I want is an interesting class of functions in NP such that if you choose a random one then with high probability it is NP-complete. I'm not 100% clear in my mind what counts as interesting though. But Harrison is right -- I am not asking about problems that are hard on average. Oct 29 comment Minkowski sum of small connected sets As David Speyer points out, the Minkowski sum is a singleton in this case. My only reason for making this comment is to say that I came up with exactly the same "counterexample" myself at one point, and even started writing an answer based on it. But then I realized my mistake.