Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've wasted a few days trying to prove Thue's lemma with no success! The proof is absolutely easy if you just count. What 'red flags' are useful to give you a warning that counting might be more productive than other approaches?

I can start with one point, but it's more of a conceptual one and requires you to see the theorem in a bigger context: If you know that you cannot prove an existential effectively then counting is probably going to be involved. (You might notice that effective solution would imply fast algorithm for factoring or similar).

share|cite|improve this question
I don't actually know what proof of Thue's lemma you're referring to; could you elaborate? – Qiaochu Yuan Nov 1 '10 at 17:47
@Qiaochu Yuan, It is from Pete L Clark's document – anon Nov 1 '10 at 18:41
Your question is probably appropriate for the nearly-in-beta-SE…. Check out the proposal and commit to it if you're interested. Then we can get it off the ground and get the site in beta! – Xoque55 Mar 3 '14 at 4:49

The short answer, in my opinion, is that counting is one of the first things you should try when you approach a problem and it looks even remotely possible to use. If counting doesn't work, then you should try all your other tools.

share|cite|improve this answer
Even attempting a rough count is a good idea when their even if their is no chance that it will solve the problem. At the very least, it will give you an idea of what the size of the problem is. – Baby Dragon Sep 28 '12 at 1:55

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.