It is sometimes much easier to solve a general problem than a particular one. What are good examples in mathematics that are difficult to solve but solved successfully by solving more general ones?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Strangely this question that got asked later got much more attention mathoverflow.net/questions/40005/…. There are also some "more basic" examples on MSE math.stackexchange.com/questions/899109/…. $\endgroup$– D.R.Commented Apr 23, 2023 at 22:32
Add a comment
|
16 Answers
$\begingroup$
$\endgroup$
5
For what it's worth, here's a trivial one: when explaining induction to students, I sometimes stress that it might be easier to prove a stronger result by induction than a weaker one---you're trying to get more out, but you're putting more in. As a concrete example I note that proving that the sum of the first 100 odd numbers is a square sounds like it might be tricky, proving that the sum of the first $n$ odd numbers is a square for all $n\geq1$ sounds like it might be accessible using induction but in fact it still too weak, and proving that the sum of the first $n$ odd numbers is $n^2$ is really rather easy to prove. In some sense the stronger the statements get, the easier they become.
-
$\begingroup$ The first problem on the first homework in my number theory class last semester had something similar, but it was with finding a bound on something. I don't remember the exact problem, but it ended up being easier to give an upper bound $2-\frac{1}{n}$ instead of just $2$. $\endgroup$ Commented Apr 13, 2010 at 17:01
-
13$\begingroup$ @Harry: Probably it was $\sum_{j=1}^n 1/j^2$. $\endgroup$ Commented Apr 13, 2010 at 17:04
-
-
9$\begingroup$ +1 for the sequence of three statements rather than just two. $\endgroup$– gowersCommented Sep 26, 2010 at 8:41
-
2$\begingroup$ "The sum of the first $n$ odd numbers is $n^2$" is stronger than "the sum of the first $n$ odd numbers is a square", but how is it more general? $\endgroup$– bofCommented May 29, 2022 at 5:29
$\begingroup$
$\endgroup$
2
Another way of proving that something is nonzero is to prove that it is odd. One good example of that idea is the proof of Sperner's lemma
More generally, one can prove that something is nonzero by proving that it is nonzero mod p. That is the idea used in Chevalley-Warning theorem (one proves that the number of solutions is 0 mod p, then proves there is a trivial solution), and in the proof of Cauchy's theorem.
-
1$\begingroup$ Another place where this is used is in Don Zagier's "A one sentence proof that every prime congruent 1 mod 4 is the sum of two squares" $\endgroup$– VincentCommented May 31, 2018 at 9:57
-
2$\begingroup$ Proving that something is odd is stronger than proving that it's nonzero, but how is it more general? $\endgroup$– bofCommented May 29, 2022 at 5:20
$\begingroup$
$\endgroup$
1
Frequently in mathematics the best way to determine the value of a sequence at a particular index is to compute its value at every index, even though the latter seems on the surface like a harder problem.
Here is one of my favorite examples of this phenomenon. Suppose you want to know how many vectors of a particular norm there are in some lattice $L$. On the surface, this seems like a hard problem - it involves figuring out how many times some quadratic form takes some value. One can solve this problem by solving the harder problem of determining the answer for every possible norm by writing down the theta function $$\Theta_L(\tau) = \sum_{v \in L} e^{\pi i \tau \left< v, v \right>}.$$
If $L$ satisfies certain technical properties, $\Theta_L$ is a modular form with respect to some congruence subgroup, and modular forms live in finite-dimensional vector spaces; moreover, a lot is known about how to write down modular forms. For example, the theta function of the $E_8$ lattice is a modular form of weight $4$ and level $1$. The space of such forms is one-dimensional - in fact, it's spanned by an Eisenstein series - and it then follows that $$\Theta_{E_8}(\tau) = 1 + 240 \sum_{n \ge 1} \sigma_3(n) q^n$$
where $q = e^{2\pi i \tau}$. Similar considerations lead to the well-known formulas for the number of ways to represent an integer as the sum of two or four squares.
-
1$\begingroup$ For more on the subject, consider Noam Elkies's beautiful lectures at the 2009 AWS: swc.math.arizona.edu/aws/09/index.html. $\endgroup$– pmoduliCommented Apr 13, 2010 at 22:15
$\begingroup$
$\endgroup$
Cantor proved the existence of transcendental real numbers by proving that most numbers are transcendental. The set of algebraic real numbers is countable.
$\begingroup$
$\endgroup$
3
Some of the previous answers have said that sometimes the easiest way to prove a set it non-empty is to show that it's large or even infinite. A variation on that idea is to show that something exists by showing that the probability of selecting it at random from some larger set is positive. As one of my professors used to say, some things are so hard to find that the best way to look for them is at random.
-
1$\begingroup$ Indeed, entire textbooks have been written on the subject: amazon.com/… $\endgroup$ Commented Apr 13, 2010 at 18:12
-
2$\begingroup$ A nice example of looking at random is in the area of error correcting codes. There is lots of fine theory for generating codes involving all kinds of beautiful mathematics from group theory and algebraic geometry. But it turns out that if you want to get close to the Shannon limit, random codes (subject to some constraints) will do the job just fine: en.wikipedia.org/wiki/Low-density_parity-check_code $\endgroup$ Commented Apr 13, 2010 at 23:19
-
$\begingroup$ While random error correcting codes are great for approaching the Shannon limit, this produces codes that can't be decoded in practice when you get errors. $\endgroup$ Commented Mar 4, 2016 at 16:09
$\begingroup$
$\endgroup$
4
The only way to prove that there's at least one prime in every arithmetic progression is by proving that there are infinitely many primes in every arithmetic progression. This is intuitively a fairly tremendous jump in difficulty to get the initial rather modest result out.
I imagine that most examples of this phenomenon take the form that the question as asked is "more difficult" only in the sense that it's been phrased in such a way as to mask what's "really going on." I think this is probably at the core of hundreds and thousands of problem-solving type puzzles -- the difficulty of the puzzle comes from masking the influence of the governing theorem, which is likely to be easier to see how to prove in its general form than it is to realize which parts of the puzzle are the important ones. In short, puzzles have red herrings, good theorems do not.
-
2$\begingroup$ When we come across a (rearch) problem, sometimes we may not see its full picture. And in each step for a good theorem, we may not need their full generality, but a special case is enough. $\endgroup$– SunniCommented Apr 13, 2010 at 16:09
-
10$\begingroup$ A good example of such a puzzle is this: Let x = sqrt(2) and y = 2+sqrt(2). Let X be the set { floor(nx) | n a positive integer }, and define Y similarly. Prove that X and Y are disjoint, and that their union is the set of positive integers. The not-so-obvious key is that x and y are (positive) irrational numbers satisfying 1/x + 1/y = 1; and in fact the statement holds (and is easier to prove) for all such pairs. $\endgroup$ Commented Apr 13, 2010 at 17:01
-
4$\begingroup$ You can delete the word "known": the two are equivalent, since if there's at least one prime in every arithmetic progression then given an arithmetic progression a mod n, there's a prime congruent to a+n mod n^2, a prime congruent to a+n^2 mod n^3, etc. $\endgroup$ Commented Apr 13, 2010 at 21:04
-
$\begingroup$ Ah, good point. Interesting. $\endgroup$ Commented Apr 13, 2010 at 21:57
$\begingroup$
$\endgroup$
This might not be correct---perhaps someone can confirm---but I was once told (when I was a graduate student) that the way that Leopoldt's conjecture was proved for abelian number fields was as follows: first do the standard reduction to show that Leopoldt is true if certain special values of certain $p$-adic $L$-functions $L(1,\chi)$ are non-zero, and then prove that these numbers are non-zero by showing that they are transcendental! As I say, I don't know for sure if this is true, but my source was pretty reliable. The emphasis was on the observation that (at the time at least), apparently the only way of proving the numbers were non-zero was by showing they were transcendental.
$\begingroup$
$\endgroup$
2
Matijasevic's theorem, that all recursively enumerable sets are diophantine, was needed to prove that the set of primes is diophantine.
-
3$\begingroup$ I don't know about "needed": my understanding is that people simply didn't believe that such things were possible before Matiyasevich's theorem was proven. The actual construction was done explicitly a few years later by Jones et al.: en.wikipedia.org/wiki/… $\endgroup$ Commented Apr 13, 2010 at 21:00
-
2$\begingroup$ Somewhat similar to this answer is this: One asks "is there a regular expression for matching numbers divisible by 7?" and the answer is "Yes. Just prove that any DFA can be converted to a regular expression." $\endgroup$ Commented Dec 3, 2013 at 17:07
$\begingroup$
$\endgroup$
2
Occasionally when trying to prove a certain type of object exists, it is easier to show that the set of those objects is very large.
For instance, it's difficult to give an example of a transcendental number over the rationals. However, it is quite easy to show that the set of algebraic numbers is only countably infinite, so almost every real number is transcendental.
-
3$\begingroup$ A related example: it's not completely trivial to write down a language that can't be recognized by a Turing machine, but there are uncountably many languages and countably many Turing machines. $\endgroup$ Commented Apr 13, 2010 at 18:13
-
4$\begingroup$ Also related, it is difficult to give an example of a continuous real valued function on [0,1] that is not monotone on any interval, but it is not too difficult to prove using the Baire category theorem that almost all functions are like this. $\endgroup$– user4977Commented Apr 14, 2010 at 3:55
$\begingroup$
$\endgroup$
5
It is easier to prove that almost all real numbers are normal than to prove that any particular real number is normal.
Indeed, none of the most natural candidates, such as $\sqrt{2}$, $\pi$ or $e$, has yet been proved normal.
-
$\begingroup$ (John, the original said "almost real numbers". I made the obvious correction.) $\endgroup$ Commented Apr 14, 2010 at 0:05
-
1$\begingroup$ Thanks, François. That will teach me always to proofread, even a single sentence! $\endgroup$ Commented Apr 14, 2010 at 0:11
-
4$\begingroup$ Proving that almost all real numbers are normal does not solve the problem of whether $\sqrt{2}$ is normal, so this isn't really an example of what the question asks for. $\endgroup$– gowersCommented Sep 26, 2010 at 8:38
-
2$\begingroup$ On second thoughts, it does if you regard the problem as being "Prove that there exists a normal number." But then it's not obvious that proving that almost all real numbers are normal is easier than proving that 0.12345678910111213141516... is normal. $\endgroup$– gowersCommented Sep 26, 2010 at 10:22
-
$\begingroup$ Actually 0.12345678910111213141516... is proven normal only in base 10 $\endgroup$ Commented Apr 9, 2011 at 20:22
$\begingroup$
$\endgroup$
The Carlson Lemmas in combinatorics. He told me at the time that he had struggled with the simple and natural way the problem was originally posed, but was able to push through a far more elaborate, stronger, and much less intuitive version.
Timothy J. Carlson
A dual form of Ramsey's theorem, (with S. Simpson) Advances in Mathematics 53 (1984), pp. 265-290.
Some unifying principles in Ramsey theory, Discrete Mathematics Volume 68 , Issue 2-3, (February 1988), Pages: 117 - 169
$\begingroup$
$\endgroup$
Proving the general solution for lambert series is much easier than dealing with specific examples c.f. Apostol - Modular Functions and Dirichlet Series in Number Theory ch. 1 Ex. 14.
$\begingroup$
$\endgroup$
3
I believe Fermat's Last Problem was solved by proving the Modularity Theorem (for the case of semistable elliptic curves), but I don't know the proof enough to say if the problem is just a direct corollary. The Modularity theorem is not in any sense easy anyway, but at least it's been proved successfully. :)
-
$\begingroup$ I wouldn't call the modularity theorem a "generalization" of FLT; it's just a large and diffficult theorem that happens to imply FLT, and this implication is itself a theorem: en.wikipedia.org/wiki/Ribet%27s_theorem . I would reserve the term "generalization" for when the specialization can be obtained by specializing some universal quantifiers. $\endgroup$ Commented Apr 14, 2010 at 17:09
-
$\begingroup$ @Qiaochu: Would you say that ZMT is a generalization of the Nullstellensatz? $\endgroup$ Commented Apr 14, 2010 at 17:27
-
$\begingroup$ @Qiaochu: True. As I said, I didn't know the deduction from Modularity Theorem itself is a theorem. Btw, does MT imply information about solutions of a certain class of equations, or is FLT really one-of-a-kind type of thing? $\endgroup$– elfkingCommented Apr 14, 2010 at 18:16
$\begingroup$
$\endgroup$
The generating function proof of Cayley's theorem counting labeled trees (e.g., the theorem that there are $n^{n-2}$ labeled trees on $n$ vertices) is a good example. In the lecture notes I linked to, the more general question is Theorem 1 and the particular question is Corollary 1.
$\begingroup$
$\endgroup$
There are perhaps many examples found in inequalities because a given inequality with a mass of variables and functions can easily hide "Simple Inequality" of which it is a special case.
$\begingroup$
$\endgroup$
Well I am amazed no one mentioned this yet. But this idea is exactly what makes the Feynman technique of integration effective. You take an integral and you add an additional variable into the expression. This new modified expression can be thought as a family of integral for each value the new variable can take.
You differentiate with the value of the integral w.r.t. the new parameter and do the original integration you had. This would lead you into a differential equation with the new parameter.
You can get the initial value of the DE by choosing a suitable member in the family of integral to evaluate.
Once you have the two informations above you have the parameterized integral as some closed functional form of alpha. Now you choose the value of alpha that returns you to the original integral and youd have solved the question.