# Elementary+Short+Useful

Imagine your-self in front of a class with very good undergraduates who plan to do mathematics (professionally) in the future. You have 30 minutes after that you do not see these students again. You need to present a theorem which will be 100% useful for them.

What would you do?

For example: 30 min is more than enough to introduce metric spaces, prove existence of partition of unity, and explain how it can be used later.

P.S. Many of you criticized the vague formulation of the question. I agree. I was trying to make it short --- I do not read the questions if they are longer than half a page. Still I think it is a good approximation to what I really wanted to ask. Here is an other formulation of the same question, but it might be even more vague.

Before I liked jewellery-type theorems; those I can put in my pocket and look at it when I want to. Now I like tool-type theorems those which can be used to dig a hole or build a wall. It turnes out that there are jewellery-type and tool-type theorems at the same time. I know few and I want to know more.

-
How many years of undergraduate education do those students have? What can we assume that they know? (It is a big difference between one who's in the second half of her third year and one that just started two months ago.) –  Willie Wong Apr 3 '11 at 18:28
I find it hard to square the "no prerequisites" condition with the "partitions of unity" example. Or are we talking about ideal undergraduate students, who like ideal gases are only an approximation to the reality? –  Yemon Choi Apr 3 '11 at 20:34
In my opinion, the "try to be realistic" injunction (which I approve of in all pedagogical questions; note that a lot of experienced teachers do see some of the more ridiculously ambitious pedagogical suggestions promulgated in some answers here and have a good laugh at the naivete of the authors) is hard to square with the vagueness of the question. The term "very good undergraduate" alone is a currency whose value will rise and fall according to where you go. It is tempting to close the question as "too localized" for this reason, but I'll think about it a bit more... –  Pete L. Clark Apr 3 '11 at 23:03
I too find the partitions of unity example unrealistic. I do think this and some of the examples below could be made to work if one wasn't obliged to give a proof, but perhaps only an intuitive idea, and then explain why it was useful -- sort of like a colloquium talk for undergraduates. –  Todd Trimble Apr 3 '11 at 23:10
Indeed, Anton, you can do all sort of things in 30 minutes... but unless the students already somewhat familiar about the subject you are talking about, it is rather unusual that you can introduce three new objects, two concepts, and a theorem to anyone and as a result get them to understand the significance of anything. –  Mariano Suárez-Alvarez Apr 4 '11 at 17:10

-
+1 for an answer which seems appropriate in every reasonable context I can think of. For instance Keith Conrad spoke about this in the UGA undergraduate math club last year, to great success. –  Pete L. Clark Apr 3 '11 at 23:04
Elsewhere Pete L. Clark said: "Perhaps a moral here: just naming a theorem isn't maximally helpful, because the same theorem could make for both a good talk or a bad talk. Better would be to say a little bit about what you plan to do with it." –  Todd Trimble Jul 30 '11 at 19:17

Introduce generating functions and give couple of applications.

-
+1.  –  Pete L. Clark Apr 3 '11 at 23:10

Singular Value Decomposition, probably one of the most useful and ubiquitous concepts out there. Half the time can be devoted to listing all the synonyms it goes by in various fields such as statistics and finance.

-
I give this a +1 because I wish someone had given me this talk as an undergraduate. To my shame, I am still somewhat fuzzy on the concept! –  Pete L. Clark Apr 4 '11 at 0:10
Also known as the "Singularly Valuable Decomposition": www1.math.american.edu/People/kalman/pdffiles/svd.pdf –  j.c. Apr 4 '11 at 2:05
Principle component analysis (Stats), Schmidt Decomposition (Quantum Computation), multidimensional scaling, Low rank approximation, Multimode factor analysis, "Partison" index (voting) –  Alex R. Apr 8 '11 at 19:59

I would say something far far more elementary than all the other suggestions here (perhaps assuming the audience is in their first semester as undergraduates)

I would define an equivalence relation and an equivalence class and prove that equivalence classes on $X$ define a partition of $X$. (And then spend the remaining 29 minutes talking about their philosophical significance :) )

Its usefulness is of course immense but that doesn't mean we should attribute it solely to its obviousness. In my mind it also encodes so many very deep intuitions that separate high-school from college-level mathematics. To name a few:

• The fact that there is nothing metaphysically 'special' about the relation of equality, which foreshadows the algebraic paradigm-shift towards isomorphisms
• The fact that information about certain properties is better captured when we look at classes of objects satisfying a relation
• That the foundations of analysis are a lot more conceptually flexible (and amenable to reinterpretation or even reinvention) than 'functions and derivatives'.
• The information encoded by the definition of an equivalence relation is absolutely minimal and trivial to understand (which is why most undergraduates, I've found, almost scoff when a lecturer spends time defining it) and yet responsible for profoundly deep intuitions - think of the Grothendieck group.
• It brings out the significance of structuralist thinking at a very early, pre-algebraic stage (this is more personal, but still)
-
Although useful sometimes, I believe equivalence classes are massively overused in contemporary mathematics, and far less useful than equivalence relations. I'm inclined to side with E. Bishop on this point. A lot of people seem to be unhealthily obsessed with putting things into classes when it's really not necessary - just knowing two distinct objects are equivalent is all you really need in many cases. –  Zen Harper Apr 6 '11 at 8:45
Zen, could you elaborate on this? To a befuddled non-constructivist, equivalence classes and equivalence relations are very literally the same thing. Could you explain an example where thinking of the latter is ‘better’, in whatever vague sense, than thinking of the former? –  L Spice Apr 8 '11 at 13:29
@Chuck: I agree that in the case of field extensions it's better to think in terms of isomorphisms rather than equivalence classes of extensions. But there are cases in which taking an equivalence class is the simplest and the most natural thing to do in order to avoid complications: e.g., defining a manifold as a set with an equivalence class of atlases allows you to avoid using an awkward notion of "spaces-with-atlas" and isomorphism between them or "change of atlas". –  Qfwfq Apr 10 '11 at 17:08

The Chinese Remainder Theorem. This is ripe for giving some nice applications, some of which are given in this MO thread (hat tip to Pete Clark; I presume this is the one he meant).

-
Perhaps a moral here: just naming a theorem isn't maximally helpful, because the same theorem could make for both a good talk or a bad talk. Better would be to say a little bit about what you plan to do with it. –  Pete L. Clark Apr 3 '11 at 23:38

Euler's formula $V - E + F = 2$.

-
As an alternative, you could just distribute copies of Proofs and Refutations... –  drvitek Dec 19 '13 at 16:58
-
Quoth Pete Clark: "Perhaps a moral here: just naming a theorem isn't maximally helpful, because the same theorem could make for both a good talk or a bad talk. Better would be to say a little bit about what you plan to do with it." –  Todd Trimble Jul 30 '11 at 14:37
-
… but the Pigeonhole Principle itself is extremely boring (I think); it's all in the applications. Which ones would you demonstrate? –  L Spice Apr 8 '11 at 13:30

Maybe (a suitably weak version of) Brouwer fixed point theorem? For example you can prove the version for smooth maps, or the topological version in low dimensions. And there are so many generalizations of the theorem that it seems the students are bound to run into some version of topological fixed points in the future.

You can even mention, as an application of topological fixed points, Littlewood's proof that there always exists a way to put a rod standing on one end in a train travelling between Kings Cross and Cambridge such that it would not fall over. (In fact, isn't that entire chapter of the Miscellany [Chapter 1, Mathematics with minimum raw material] consisting of answers to your question?)

-

There are plenty of elementary, self-contained examples to choose from, and it has a pithy slogan that's memorable enough even for non-combinatorialists. (Can't construct something explicitly? Then construct it randomly!) Best of all, it has a nice wow factor: While many undergraduates may be familiar with nonconstructive phenomena in mathematics, the fact that we need to resort to such to say things about finite graphs is rather surprising.

-

Newton's method for solving the non-linear (systems of) equations. How to make the presentation depends on the level and interests of the students. It can range from a fast algorithm for finding the square root with high precision to some advanced topics in dynamics.

-
@L Spice : I call it Dunford because it is the French term. My method is the following : let $P(x)$ be the caracteristic polynomial of a matrix $A$ and let $Q(X):=P(X)/(gcd(P'(X),P(X)))$ (assume $caract(k)=0$ otherwise the formula for $Q(X)$ is more complicated). Consider the sequence defined by $A_0:=A$ and $A_{n+1}:=A_n-Q(A_n)/Q'(A_n)$. Then for all $n \geq log_2(dimension)$, the matrix $A_n$ is the semisimple part of $A$ (the key point is to notice that the semi-simple part is a zero of $Q(X)$ in the vector space $k[A]$). I don't know about your method, so I can't tell if it is the same. –  Auguste Hoang Duc Apr 12 '11 at 8:25

Picard–Lindelöf theorem on existence and uniqueness of solutions to ordinary differential equations, introducing Picard iteration along the way.

-

A short presentation on the Hopf fibration could be very useful as it is such a central example. The idea to make it elementary would be to take a concrete point of view and include lots of pictures.

-

Using Groebner Bases to solve equations. Just use the lexicographic ordering without disucssing theory. Mash generalized polynomial long division and Buchberger's algorithm into one mechanical procedure. 30 minutes is pretty tight, but doable.

-
They are useful, but not 100% guaranteed to be useful. Probably most mathematicians will never use them and have only very vague acquaintance with them. –  Todd Trimble Apr 5 '11 at 12:30
-
I think this is especially true for students interested in any sort of geometry or topology. I can't tell you how many times I've seen "it follows from Arzela-Ascoli that..." in papers and talks. –  BMann Apr 4 '11 at 4:21

Hall Marriage theorem

This is a very useful theorem in combinatorics, analysis, algebra, computational complexity, and more.

-

Borsuk-Ulam theorem. A very useful topological theorem. It is very easy to state and to describe some applications, or alternatively to describe what is involved in a proof.

-
-

Simplicity of the alternating group An for $n\geq 5$, contrasted with its non-simplicity for $n\leq 4$.

-
I must ask, is there a particular reason why you wrote $n > 4$ and $n < 5$ instead of $n \ge 5$ and $n \le 4$? I've always found the former a little bit hard to parse (which could well be a personal failure on my part). –  Willie Wong Apr 3 '11 at 20:58
To minimize LaTeX code... you're right, it was silly. I editted it. –  Daniel Moskovich Apr 3 '11 at 21:54

Lagrange's theorem (order of a sugroup divides the order of the group).

-
This strikes me as having the opposite problem to some of the other ideas: it seems hard to fill up an entire half hour on this. –  Paul Siegel Apr 5 '11 at 17:16
You can use it to prove Fermat's little theorem, mix it with some group action to prove combinatorial results or Cauchy's theorem on the existence of elements of order $p$, etc. –  anonymous Apr 6 '11 at 0:01

Okay, last one from me tonight.

Separating hyperplane theorem and/or the Riesz extension theorem. The finite (or 2) dimensional version is fairly easy to illustrate and not too hard to prove. And of course as an example application you can assume the infinite dimensional version and derive Hahn-Banach Theorem (the version about extending linear functionals). Consider its use in convex and functional analysis, at least some of the students will run into something like this in the future.

-

Min-max principle and spectral theorem as a corollary for real symmetric matrices. I often teach this quickly in my vector analysis course as an example of finding extrema of functions in $\mathbb{R}^n$.

-

The spectral theorem for normal operators.

-

Helly theorem. It is easy to motivate state and prove in 30 minutes. It is very useful in terms of application as a fundamental example of a result in combinatorial geometry.

-

Elementary symmetric polynomials generate the ring of symmetric polynomials.

-

Robinston-Schensted-Knuth algorithm

This is a map between permutations to pairs of standard tableaux. So it immediately gives various wonderful facts. It is elementary, short and useful.

-

Compactness of First Order Logic (using ultraproducts, not as a corollary of completeness; they get Łoś's Theorem for ultraproducts as a freebie.)

-
Hmm, "using ultraproducts"... –  Anton Petrunin Apr 3 '11 at 20:54
I have a lot of reservations about this answer, which will be more or less valid depending upon how you interpret the parameters of the question (which I also think is rather vague). First of all the OP said "100% useful". Now I happen to know and like this exact result enough to have made it the climax of a short course I taught last summer. Nevertheless I have not yet used any form of the Compactness Theorem for anything in my own work (I am an arithmetic geometer), and I think probably the majority of working mathematicians would say the same thing.... –  Pete L. Clark Apr 3 '11 at 22:53
Second, the course I taught consisted of eight two-hour lectures to math graduate students (who were "very good" according to at least one reasonable interpretation of the term). It was not assumed that they had any previous exposure to mathematical logic of any kind, nor any previous exposure to ultrafilters. (And in fact none of them did have any prior experience with these things.) I mentioned the Compactness Theorem in either the second or third lecture, at the time without proof. The proof came in the last lecture, after I introduced ultrafilters from scratch... –  Pete L. Clark Apr 3 '11 at 22:55
And you want to do all of this in half an hour, for undergraduates? I suppose I could compile a nonempty set of undergraduates (Qiaochu Yuan, Akhil Mathew, Zev Chonoles,...) for which this might have a chance of flying, but as a general suggestion this comes off as being much more likely to blow up in one's face. –  Pete L. Clark Apr 3 '11 at 22:58
I think the compactness theorem is useful even if you don't apply it in your work. I think it is the best way to understand what the difference between first order sentences and others is. –  Michael Greinecker Apr 4 '11 at 6:15
-
Are you planning to introduce manifolds and differential forms in 30 min? –  Anton Petrunin Apr 3 '11 at 20:45

The definition of the tensor product and existence/uniqueness/associativity properties.

I know, this is perhaps not a single theorem but in my eyes one of the most useful "elemetary" concepts. Personally, I had two semesters of linear algebra without mentioning the tensor product. And from this I suffered for a long time during my further studies. Now it is my first homework/exercise for students in my lectures (e.g. diff geo).

If the student is really clever, one can even do something like the tensor algebra in these 30 min.

-

Sperner's lemma (Two-dimensional case)

-
I don't know about 100% useful, but since I have seen a striking use for it (in the proof of Monsky's theorem about cutting a rectangle into congruent triangles) I won't object on that account. I note that the OP's suggestions seem more reasonable than some of the answers... –  Pete L. Clark Apr 3 '11 at 23:10