158
$\begingroup$

One of the many articles on the Tricki that was planned but has never been written was about making it easier to solve a problem by generalizing it (which initially seems paradoxical because if you generalize something then you are trying to prove a stronger statement). I know that I've run into this phenomenon many times, and sometimes it has been extremely striking just how much simpler the generalized problem is. But now that I try to remember any of those examples I find that I can't. It has recently occurred to me that MO could be an ideal help to the Tricki: if you want to write a Tricki article but lack a supply of good examples, then you can ask for them on MO.

I want to see whether this works by actually doing it, and this article is one that I'd particularly like to write. So if you have a good example up your sleeve (ideally, "good" means both that it illustrates the phenomenon well and that it is reasonably easy for others to understand) and are happy to share it, then I'd be grateful to hear it. I will then base an article on those examples, and I will also put a link from that article to this MO page so that if you think of a superb example then you will get the credit for it there as well as here.

Incidentally, here is the page on this idea as it is so far. It is divided into subpages, which may help you to think of examples.

Added later: In the light of Jonas's comment below (I looked, but not hard enough), perhaps the appropriate thing to do if you come up with a good example is to add it as an answer to the earlier question rather than this one. But I'd also like to leave this question here because I'm interested in the general idea of some kind of symbiosis between the Tricki and MO (even if it's mainly the Tricki benefiting from MO rather than the other way round).

$\endgroup$
7
  • 6
    $\begingroup$ Here's a related question: mathoverflow.net/questions/21214/… $\endgroup$ Sep 26, 2010 at 8:12
  • 5
    $\begingroup$ Here's another related question: mathoverflow.net/questions/31699/… $\endgroup$
    – Tony Huynh
    Sep 26, 2010 at 10:44
  • 2
    $\begingroup$ @Tony -- that's great, and will also be helpful for the Tricki article. $\endgroup$
    – gowers
    Sep 26, 2010 at 11:04
  • $\begingroup$ Cayley's tree counting theorem has several proofs that work like this. The nicest one may be the generating function one, which I added as an answer for the previous MO question. $\endgroup$
    – Peter Shor
    Sep 26, 2010 at 16:47
  • 1
    $\begingroup$ You may be interested in Tom Leinster's post here: golem.ph.utexas.edu/category/2010/03/… where he uses buffon's noodle as a generalization of buffon's needle as an example of a more general problem which is easier to solve. $\endgroup$ Sep 28, 2010 at 22:06

48 Answers 48

1
2
5
$\begingroup$

Bruce Schneier has an online paper called "A Self-Study Course in Block-Cipher Cryptanalysis": http://www.schneier.com/paper-self-study.pdf containing an extensive list of algorithms to cryptanalyze as exercises. By far the easiest exercise is this one:

[Cryptanalyze] a generic cipher that is “closed” (i.e., encrypting with key A and then key B is the same as encrypting with key C, for all keys).

The solution to this exercise would be a lot less obvious had Schneier instead pointed to some particular block cipher that has this property. But because the reader is told nothing about the cipher except that it is closed, he immediately knows exactly what to attack.

$\endgroup$
5
$\begingroup$

A Real Algebraic Geometry Example

Semialgebraic sets are very nice: they are closed under Boolean operations (obvious) and projections (not so obvious, but old result of Tarski-Seidenberg). Semianalytic sets are not so nice, because they're not closed under projections.

What is one to do if one wants to study them nonetheless? Shift the focus to projections of semianalytics instead, a.k.a. subanalytic sets. Those sets are closed under projection by construction, but all of a sudden, the Boolean algebra property is not so clear. But that's where Gabrielov's theorem of the complement comes in: the complement of a subanalytic set is again subanalytic. We now have a nice structure in which reside all the natural geometric operations we may want to do.

$\endgroup$
5
$\begingroup$

Evaluating the integral of a function by determining first its Fourier transform can simplify a problem in some cases. The integral of the sinc function provides a simple example:

$$\frac{\sin(\pi x)}{\pi x} = \int_{-1/2}^{1/2} \exp(2 \pi i x f) \; df = \int_{-\infty}^{\infty} Rect(f) \exp(2 \pi i x f) \; df \; ,$$

so the Fourier transform gives

$$\int_{-\infty}^{\infty} \frac{\sin(\pi x)}{\pi x} \exp(-2\pi i f x) \; dx = Rect(f)\: ,$$

and evaluating at $f=0$ gives

$$\int_{-\infty}^{\infty} \frac{\sin(\pi x)}{\pi x} \; dx = 1.$$

Similarly, you can evaluate the integral of the square of the sinc function by using the convolution theorem, i.e., by convolving the rectangle function with itself.

$\endgroup$
5
$\begingroup$

In teaching calculus, I found a great example of this phenomenon: differentiation. For instance, consider the function $f(x) = x^x$ (for $x \in (0,\infty)$). I have no idea how to evaluate the limit

$$ f'(2) := \underset{x \to 2}{\lim} \frac{ x^x - 4}{x-2} $$

directly. But you can use logarithmic differentiation to find that $f'(x) = x^x (1+\ln x)$, which implies that

$$f'(2) = 4(1 + \ln 2)~. $$

So it's easier to compute $f'(x)$ and then specialize to $x=2$ than it is to compute $f'(2)$ directly.

I think this is essentially true for all functions, that it's easier to find the function $f'(x)$ than it is to directly compute a given value $f'(a)$.

$\endgroup$
5
$\begingroup$

I see several answers to this question that rely on the fact that it is often easier to prove a stronger result in the case of proofs by induction. This phenomenon is explained in this answer : https://mathoverflow.net/a/69157/120363

A generalisation of this remark is the following: when you want to prove that an object has a property $(A)$, it is sometimes easier to prove that it has a stronger property $(B)$, because $(B)$ has more nice preservation properties than $(A)$. This is exactly what happens in the case of inductions, since sometimes a stronger induction hypothesis passes more easily from the case $n$ to the case $n+1$.

Another wonderful (in my opinion!) example of this phenomenon is the following. Say that a quasi-ordering (i.e. a reflexive, transitive binary relation) is a well quasi-ordering (wqo) if it has no infinite strictly decreasing sequences and no infinite antichains. This is an important notion in combinatorics, complexity, etc., but it has little preservation properties. In the middle of the 20th century, there were several open and seemingly very difficult problem about this notion. For instance:

  1. Is the class of countable linear orderings well-quasi-ordered by the embeddability relation? (Known as Fraïssé's conjecture.)
  2. Is the class of countable trees well-quasi-ordered by the minor relation?

In the late 60's - 70's, a stronger notion than wqo, the notion of better quasi-ordering (bqo), was defined and studied by Nash-Williams. The definition of a bqo is quite scary, to say so. And, for applications of the theory (to combinatorics, complexity, etc.), knowing that a particular quasi-ordering is bqo is not more useful that knowing that it is wqo. What's the point of this notion, then? The point is that the bqo property is closed under much more interesting operations than the wqo property. So in general, it is much easier to prove that a particular ordering is bqo rather than wqo. This notion was successfuly used by Nash-Williams to prove conjecture 2., and a few years later by Laver to prove conjecture 1.

To give you an idea, this is the definition of bqo: a quasi-ordering $(Q, \leqslant)$ is bqo if for every borel mapping $f\colon [\mathbb{N}]^\infty \to Q$ with countable image (where $[\mathbb{N}]^\infty$ is the set of infinite subsets of $\mathbb{N}$ with its usual Polish topology), there exists $M \in [\mathbb{N}]^\infty$ such that $f(M) \leqslant f(M \setminus \min(M))$. It's easy to prove that every bqo is wqo, however this definition is quite awful, isn't it?

$\endgroup$
2
  • 1
    $\begingroup$ I thought the proof of Fraïssé's conjecture was due to Laver. $\endgroup$ Feb 14, 2019 at 22:46
  • $\begingroup$ @AndreasBlass Woops you are right, since I listed the conjectures in the reverse chronological order I made a mistake. I edit. $\endgroup$ Feb 14, 2019 at 23:13
4
$\begingroup$

Quantum topology is much easier for knotted tori in R4 than for knots in R3. The former is a generalization of the latter, because for any knot you can take the boundary of a tubular neighbourhood of the inclusion of the knot into R4, which is a knotted torus.
The reason that the more general problem is easier is that the projectivization (homomorphic expansion) of the space of knotted tori in R4 gives rise to a space of diagrams $\mathcal{A}$ containing oriented chords. The homomorphic expansion of the space of knots, on the other hand, gives rise to a space of diagrams in which the chords are not oriented. Oriented, based trees are much simpler combinatorial objects that unoriented, unbased trees. In particular, the Drinfeld associator, which is the most painful aspect of quantum topology of knots, vanishes in $\mathcal{A}$.
The upshot of the generalization is that the universal finite-type invariant for knotted tori in R4 is the Alexander polynomial, which is a homological invariant, and which is immeasurably simpler then the universal finite type invariant for knots, the Kontsevich invariant.
In fact, a further generalization, allowing "trivalent vertices" in the knotted tori (where two tubes fuse into one) simplifies the algebra yet further and allows the proof of theorems relating the value of the Alexander polynomial of such an object with its cablings. Again, this is motivated by the algebra- we expand the class of topological objects under consideration in order to create an associated graded space which looks as much as possible like a quantized Lie (bi)algebra, from where our invariants are going to come, and which we are supposed to know how to handle.
Dror Bar-Natan discussed this, and related ideas, in a series of talks in Montpellier.

Added: This doesn't obviously solve a problem. It's a non-obvious example of a problem being easier for a more general class of objects; and you can hope to use insights gained from the easier problem to attack the harder, less general problem.

$\endgroup$
4
$\begingroup$

The LLL algorithm to factor polynomials with integer coefficients. Previously people had been fussing with Hensel lifting and tons of other methods that (imo) were far too complicated. (For a good reference on LLL and factoring polynomials, also see Yap's excellent book and his chapter on lattice reduction ).

LLL solved the more general problem of finding short (or 'short enough') vectors on integer lattices in higher dimensional spaces. This was then used to to encode the problem of factoring polynomials with integer coefficients in it. As an added bonus, the lattice reduction techniques presented also solved the simultaneous Diophantine approximation problem, but that somehow doesn't seem as striking as integer polynomial factorization.

$\endgroup$
4
$\begingroup$

In the computation of spectral measures for self-similar groups, one has a sequence of matrices and one wants a recursion for the characteristic polynomial. Usually one gets a recursion for some multivariable polynomial obtained by adding new parameters and then specializes the parameters to obtain the characteristic polynomial. This happens in Grigorchuk and Zuk's computation of the spectral measure of the lamplighters group.

$\endgroup$
4
$\begingroup$

Using residue theorem to compute integrals over real line intervals is an example of solving a problem by considering it in a more general setting: usually, the integrand is complexified and a closed contour is built by attaching a semicircle to the interval [-a,a].Then the integral over the contour is computed using the residue theorem and the original integral is obtained as the limit of contour integrals. This works e.g. for the function $$\int_{-\infty}^{+\infty}\frac{e^{itx}}{x^2+1}dx$$ In some cases the contour gets more complicated, to avoid branch points, as when computing $$\int_0^{\infty}\frac{dx}{x^a+1}, \quad a>1$$ Sometimes the integral over an interval is replaced by an integral over the unit circle, e.g., for $$\int_0^{\pi}\frac{d\theta}{a+\cos \theta}, \quad a>1$$ (here one also uses the equality $\cos z = (1/2)(z+1/z))$. Ahlfors's text in complex analysis explains this method in more detail. (Some other texts seem to have just a haphazard collection of examples following the statement and proof of residue theorem.)

This is not so much of proving a stronger result first, but rather making a problem tractable at all by using a more general approach (replacing real functions with complex ones and computing residues instead of actually integrating over the contours).

$\endgroup$
1
  • 1
    $\begingroup$ Your latest edit sums up my view of your post: it's a nice example, but does not quite fit with the original question. $\endgroup$ Jul 1, 2011 at 15:41
4
$\begingroup$

An av-subgraph of graph $G$ is a subgraph that includes all of the vertices of $G$. Proving that the number of av-subgraphs of a complete graph with $N$ vertices is $2^{N(N+1)/2}$ is harder than proving the number of av-subgraphs of a graph with $E$ edges is $2^E$.

$\endgroup$
3
$\begingroup$

I have some examples, but I might have more words of warning than examples. Example 1. Let's say you have just the axioms for the real numbers, and you want to establish that $2$ is not zero, but all you know is that $1$ is not zero (perhaps because you want to divide by 2 for whatever reason). Knowing that there is a field with $2$ elements where $2= 0$, you discover you have no choice but to prove 2 is positive, even though it's not what you were going for. (This is an example where taking on a more general point of view does not give you something different to prove instead, but limits the approaches to what you're trying to prove.)

So in order to prove 2 is positive, it suffices to prove 1 is positive. And here it somehow just makes sense to prove that the square of any nonzero number is positive -- from this point of view 1 is positive "because it's a square".

Here's another example from real analysis. You want to prove things about the cube root function from first principles. Like the fact that it's well-defined, continuous, differentiable, concave, etc. Typically one approaches by proving general theorems about smooth, increasing functions, and applies these general theorems to the function x^3 to learn about its inverse.

So while this seems like the kind of example you're going for, I personally don't like the example only because it suggests this is the "right" way to go. Often when one takes a "generalize" approach solving the problem can become easier, especially if you already know the general facts which end up doing the job. But for this example, defining the cube root is just a bit easier than using the general intermediate value theorem since you can define it as $f(x) = \sup \{ t : t^3 \leq x \}$ and prove directly that $f(x)^3 = x$.

Moreover, it's also a good example to use the implicit definition to prove things directly for this function just because it makes manipulations concrete. For example, since $f(x+h)^3 = x + h$, we have

$ (f(x+h)^3 - f(x)^3) = h $

is also equal to

$ (f(x+h) - f(x)) \cdot \int_0^1 3 (s f(x+h) + (1-s) f(x))^2 ds $

If you look at this expression for a little while, you will be able to deduce things like monotonicity, uniform continuity on any interval $[\epsilon, \infty)$, differentiability on such intervals, concavity, so on. The point is that even when general technology works, it can be quite instructive to use "general methods", but execute them on explicit examples.

You might argue that these direct proofs are the most insightful, but one is more likely to first find a general proof (especially if the appropriate general apparatus already exists), and then the direct proofs can only be found later indeed because they require a more direct understanding of the specific problem. I personally use the cube root of 7 (which nobody can name) in calculus lectures to motivate the concept of continuity, so I agree here it's a very natural use of the concept to define the cube root.

Differential equations have, I think, a lot of examples. If you want to learn something about the exponential function and your point of view is that it is the unique solution to $\frac{df}{dx} = f$ (or $\frac{df}{dx} = i f )$ with data $f(0) = 1$, then in order to give a differential equation-type analysis to prove the basic properties (which is fun) you will often have to consider the same differential equation with more general data (and in particular prove uniqueness of the $0$ solution). In fact, you may be tempted to consider more general ODE's like $\frac{df}{dx} = F(x, f)$ because this point of view can inspire some of the techniques. It also helps greatly (say if you want to prove $e^{it}$ is periodic) to just know what a vector field is and have that point of view.

I think the problem is that the general theorems can easily end up being forced to consider cases which are more complicated than the problem at hand. Even if you find a proof, that doesn't necessarily mean you should settle for it. If you look at the function $f(x) = 1/k$ where $k$ is the smallest positive integer such that $kx \in {\mathbb Z}$, and you want to show $f$ is Riemann integrable, you can of course prove a theorem that characterizes Riemann integrable functions in terms of the measure of their sets of discontinuity. Of course, if you know this theorem off the top of your head, it is "easy" to prove $f$ is Riemann integrable. But this proof is inefficient because it invokes a theorem that takes care of the nastiest examples of Riemann integrable functions (which this $f$ is not).

One more example: it's very easy to find a faulty proof of the chain rule if your point of view is not general enough. The first thing many people try to do to analyze the difference quotients for $f(g(x))$ is to multiply and divide by $g(x+h) - g(x)$. But then you get into these hairy problems where the number by which you divide may be zero. If you want to find the correct proof, you should take the point of view that the chain rule is a statement which should be true for maps between Euclidean spaces of any dimension. It just says the linearization of the composition is the composition of the linearizations. With this point of view in mind, you should not dare to try dividing, because dividing by $g(x+h) - g(x)$ does not even make sense in this generality.

Here's another: prove that $\int_{\mathbb R} e^{i \xi x} e^{- x^4 } dx$ is bounded by $\frac{C}{(1 + |\xi|)^2}$. Somehow you have to recognize the key features of $e^{-x^4}$ are that it will cancel against something very oscillatory because it is so smooth. Similar example problem: prove the decay for large $\xi$ of $\int_{\mathbb R} \log(1 + .5 \sin(\xi x) ) e^{- x^4 } dx$. It seems like this "look for a more general setting" trick really needs to be drilled into you for it to work because... it may require some imagination or experience to know what the right general setting is.

What some examples show is that finding the proof may be much more difficult, maybe impossible, without a willingness to work in this direction.

$\endgroup$
3
$\begingroup$

Here is a riddle which proves to be extremely hard: Imagine a finite assembly in which some people happen to be friends (friendship is a symmetric relation but not transitive and you are not your own friend). Now it happens that anytime two persons have the same number of friends, they do not have any common friend. The conclusion to be proved is that there is at least one person that has one and only one friend.

A proper generalization of the conclusion makes the riddle almost trivial.

$\endgroup$
1
  • 1
    $\begingroup$ The empty friendship relation is a counterexample. $\endgroup$ May 1, 2018 at 23:56
2
$\begingroup$

When I saw the recent question Kasteleyn's formula for domino tilings generalized?, I had the idea of generalizing it by introducing an additional variable. I didn't manage to solve the generalized question yet, but working on it, it suddenly occurred to me a couple of days later that the additional variable provided in fact an easy answer of the initial question.

$\endgroup$
2
$\begingroup$

The Heine–Cantor Theorem: Proving it for real functions on a bounded interval is messy. But proving it for continuous functions on a compact metric space, is short, neat and easy.

$\endgroup$
4
  • 4
    $\begingroup$ mathwonk had edited this question into the text, now removed: doesn't that leave the task of proving a finite interval of the real line is compact? $\endgroup$
    – Todd Trimble
    May 8, 2019 at 10:46
  • $\begingroup$ @ToddTrimble: for a totally ordered field, the Heine-Borel property is equivalent to Dedekind completeness... so you can just choose your definition so that this task is trivial. :-) $\endgroup$ Jun 1, 2023 at 16:09
  • $\begingroup$ @WillieWong In case it wasn't clear: that wasn't my question, it was mathwonk's. If you look at the edit history, it should be clear what's going on. :-) $\endgroup$
    – Todd Trimble
    Jun 1, 2023 at 16:41
  • $\begingroup$ @ToddTrimble: ah, thanks for the clarification. I actually had no idea what the first clause in your comment meant until your response just now. $\endgroup$ Jun 1, 2023 at 17:30
1
$\begingroup$

A result from the present site illustrates this nicely. The task is to prove the very challenging inequality $$\left(\frac{x^n+1}{x^{n-1}+1}\right)^n+\left(\frac{x+1}{2}\right)^n\geqslant x^n+1$$for $x>0$, where $n$ is any natural number. The first step is to generalize it to$$\begin{equation} \left(\frac{x^a+1}{x^{a-1}+1}\right)^{a+b-1}+\left(\frac{x^b+1}{x^{b-1}+1}\right)^{a+b-1}\geqslant x^{a+b-1}+1, \end{equation}$$where $a$ and $b$ are arbitrary real numbers $\geqslant1$. Thereafter, a series of ingenious substitutions, along with yet more generalizations, enable a proof by relatively elementary mathematics.

$\endgroup$
0
$\begingroup$

I am amazed by this idea, since to me the fundamental principle of problem solving is to make the problem easier, and i always assumed this meant making it more special. It is true that proving a theorem is easier by ignoring irrelevant facets, but these are only known after solving the problem. I find it is more productive in discovering which facets are relevant to do various examples, gradually trying to generalize the argument. Even Deligne proved the Weil conjectures first for K3 surfaces.

$\endgroup$
3
  • 4
    $\begingroup$ True, but what if when one makes the problem more special, the extra information is competelly irrelevant for the problem, and more it is also missleading. Very simple example (probably not the best): Let $a,b,c >0$. Prove that $\sin(a) + \sin(b)+ \sin(c) \leq \frac{a^3+b^3+c^3}{abc} \,.$ This problem has two obvious trivial generalisations, and in both of them it becomes pretty clear that it is irrelevant that the $a,b,c$ on left/rigth sides of the inequalities are the same, but many students could be misslead by this fact on the wrong path. $\endgroup$
    – Nick S
    Sep 28, 2010 at 18:59
  • $\begingroup$ I agree it is possible to find an overly special solution to a special case, but in my experience it does not happen that often and the opposite happens more. A little example is the Torelli theorem for curves of genus 4 by intersecting the tangent quadric and the osculating cubic at the unique pair of conjugate double points of the theta divisor. Then the idea of intersecting all the tangent quadrics at all double points in higher genera is not too great a stretch. I agree that there are people who more easily grapple with more general versions of a problem but I am not one of them. $\endgroup$
    – roy smith
    Oct 31, 2010 at 21:14
  • 1
    $\begingroup$ I suspect there is some confusion here between the relative ease of proving a theorem in a more general setting and actually thinking up the idea. I have always found it easier to think of a solution in a more special case, but then once the problem is understood, it is easier to separate out the crucial parts, and give them in a general setting. Mumford told me even Grothendieck worked this way. He would begin from a simple idea, and reflect on it until he had placed it in its most general possible setting. There is also the dichotomy between conjecturing a solution and proving it. $\endgroup$
    – roy smith
    Nov 18, 2010 at 16:33
0
$\begingroup$

I have had to use something similar in order to complete a proof by induction.

I had a sequence $\{a_n\}$ defined by induction $a_{k+1}=f(a_k)$ and I needed to show a property linking $a_n$ and $a_{n+1}$, say $p(a_n,a_{n+1})$ for every $n$.

Now, says I suppose the property true for $a_n$ and try to show it for $a_{n+1}$, I get $p(a_{n+1},a_{n+2}) = p(f(a_{n}),a_{n+2})$, but you can never hope to use the induction hypothesis there, since there is nothing linking $a_n$ and $a_{n+2}$. The way I got around this was to instead show the property $p(a_n,a_{n+k})$ for every k.

$\endgroup$
-1
$\begingroup$

The FARMER and THE HORSE DRING AT THE RIVER : a folklore problem.

A farmer together with his horse (at point A) must go home (at point B). Points A and B are on the same side of a river (a line D) . The horse must be led to the river to drink ( anywhere on the river is possible). PROBLEM : Find X on D that minimize their walk back home = d(A,X)+d(X,B)

SOLUTION : Ask the same problem in 3D space : D is still a line and A,B are still points.
    a) Special cases: If A (resp B) is on the river the solution is trivially X=A (resp.X=B).
    b) Fact : (A,D) (resp (B,D)) defines a half plane Pa (resp. Pb)
    Now think of Pa,Pb as the two sides of a book partly open ( spine touching the table) where D is the spine of the book , and A,B are on left and right page of it.
    Open the book flat on the table : clearly drawing a straight line between A and B is minimal and the intersection of the line with D (the spine) is the point X wanted.
    There is a special case where the book is closed at start ( Pa=Pb i.e. zero partly open) yet you may still open it flat , this is the original problem.
REMARK : If not careful you may produce a wrong demonstration when missing that Pa=Pb is possible and need to look at the half plane as a double one folded on itself. 

**QUESTION** : Find a 4-dimensional version of this? 

A small remark for the general question: the more specific the problem is, the more data you have to deal with, so combinatorialy it means more options for proof hence larger space for search. Yet a specific problem might not be 'representative' enough of the general one which might well be harder to solve.

$\endgroup$
2
  • $\begingroup$ This is not an exampled of a generalization. Also, the argument doesn't need 3D. $\endgroup$
    – Michael
    Jun 1, 2023 at 18:03
  • $\begingroup$ @Michael . Sorry there was some implicit part. Of course the starting problem can be solved ( not so easily if you are 12 years old) but the solution looks like a trick, whereas the 3D with a simple deformation flows much better. $\endgroup$ Jun 2, 2023 at 19:56
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.