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

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
awarded  Critic
Nov
17
awarded  Supporter
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
17
awarded  Nice Question
Nov
17
awarded  Nice Question
Nov
17
awarded  Student
Nov
17
awarded  Teacher
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
16
asked Can infinity shorten proofs a lot?
Nov
3
answered Memorizing theorems
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
31
asked Are there any interesting examples of random NP-complete problems?
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.
Oct
29
answered Bound on cardinality of a union
Oct
25
answered Minkowski sum of small connected sets