# 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 jewelry-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 turns out that there are jewelry-type and tool-type theorems at the same time. I know a 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).

-
This certainly meets the criterion of 100% useful, but at least here at UGA this is part of the standard curriculum (in abstract algebra), so I'm not sure it needs to be discussed in a talk. If it were, I would imagine that some of the students would know it and some wouldn't, which is not ideal. – Pete L. Clark Apr 3 '11 at 23:12
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... – dvitek Dec 19 '13 at 16:58

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.

-
-
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?)

-

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.

-

Having come across this question by searching within the mathematics-education tag, I will try to answer it from the perspective of someone in the field of Mathematics Education.

Theorem: $n^2 - n$ is even for all natural numbers $n$.

It is quite possible that very good undergraduates (I am imagining freshmen) will laugh at seeing such a "theorem" written on the board; it is almost certain that professional mathematicians will scoff. Nevertheless, this is a talk that I have given in the past to graduate students in Math Education who wish to teach secondary school mathematics in the future. Under some reasonable interpretation of the parameters given in this question, I should think these two groups alike enough to outline the talk here.

After writing the theorem on the board, I then write down a collection of headers, each of which is intended as suggesting a method of proof. Once the headers are written out, I give the students three minutes to prove the theorem using one method that they are sure they can carry out, and to attempt a proof using another method they are less sure of. Below I will write the headers, followed parenthetically by the sort of remark I might say aloud as I write them down, and then a brief indication of the proof.

Cases: (Probably you don't need more than two) The cases I am thinking of are even and odd; check what happens when $n = 2k$ and then check what happens when $n = 2k+1$.

High School Algebra: (Factoring) Write $n^2 - n = (n-1)n$ as the product of consecutive integers, hence once of them must be even; so the product is even.

Number Theory: (This might not mean so much to you all as freshmen; we'll return to it later!)

Arithmetic: (I'm thinking of adding up a certain arithmetic sequence) Consider the sum of the first $n-1$ natural numbers; this gives some natural number $k = (n-1)n/2$. Multiplying both sides by $2$, we find that $n^2 - n = (n-1)n = 2k$ is even.

Geometry: (How would you represent $n^2$ with a geometrical picture?) Consider an $n \times n$ array of squares; remove the $n$ squares along the diagonal. The number of squares remaining is $n^2 - n$ and one sees symmetrically that they have been split into two groups of equal size. Hence the total is even.

Combinatorics: (I'm thinking of forming two person committees...) The number of two person committees in a group of $n$ people is some integer $k = (n-1)n/2$. Cf. Arithmetic.

Mathematical Induction: (For students familiar with induction, you might give this a shot) The base case is clear; suppose $k^2 - k$ is even and note $(k+1)^2 - (k+1) = k^2 + k = (k^2 - k) + 2k$ is the sum of two even numbers, and hence even.

The point of the above is to demonstrate that even a seemingly simple statement can be proved in a number of different ways. Such a demonstration, more than any particular theorem, is likely to be useful for all students (as specified by the OP). I usually have students discuss their answers and then use the theorem we've proved to talk about something else that ought to be useful for everyone: generalization.

The proofs above made frequent use of the following fact: $(n-1)n = n^2 - n$.

How would you generalize the following statements?

Statement A: If $n \in \mathbb{N}$, then $2$ divides $(n-1)n$.

Statement B: If $n \in \mathbb{N}$, then $2$ divides $n^2 - n$.

The former statement suggests (in my mind) that $k$ divides $k$ consecutive numbers; the latter statement suggests (in my mind) that $k$ divides $n^k - n$.

Consider when $k = 3$.

Then the statements become:

Statement A: If $n \in \mathbb{N}$, then $3$ divides $(n-1)n(n+1)$.

Statement B: If $n \in \mathbb{N}$, then $3$ divides $n^3 - n$.

Not only are these statements true, they coincide: $(n-1)n(n+1) = n^3 - n$.

This overlap breaks down for $n>3$, though, and we find that only A is true for $n=4$. (Perhaps a good point at which to mention how a single counterexample can disprove a for all statement.)

From here, the talk suggests that A is a good segue into modular arithmetic, while B practically begs us to find the $k$ for which it holds. Of course, we can answer this question using Number Theory (as mentioned early on!) and, more precisely, by appealing to Fermat's Little Theorem.

I believe the talk outlined above, with its messages about the possibility of finding multiple proofs and the interesting directions in which a simple proposition can be generalized, is a practical and doable thirty minute talk for first-year students in mathematics. I have done nothing close to applying Groebner bases or making use of ultraproducts, but I have tried to heed the OP's request to be realistic.

-
Nice lecture :) – Anton Petrunin Dec 19 '13 at 3:56
This is a great answer indeed. – Giuseppe Negro Feb 2 at 23:19

Hall Marriage theorem

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

-

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
-

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.

-

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.

-

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

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.

-

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.

-

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.

-

The isoperimetric inequality.

• Ubiquitous in geometry.
• Among the easier examples of variational problems.
• Can be used to illustrate why we need rigorous proofs of things that are "obvioius".
-
"Can be used to illustrate why we need rigorous proofs of things that are "obvious"." I don't see how this is an example for this - an illustration of need of rigor would be a situation where "obvious intuition" turns out to be wrong. Even if you accept the isoperimetric inequality without proof, as "obvious", nothing bad happens. – Marcin Kotowski Apr 10 '11 at 9:54
-
Are you planning to introduce manifolds and differential forms in 30 min? – Anton Petrunin Apr 3 '11 at 20:45
Definitely a challenge. But that doesn't necessarily mean that it cannot be met. I must admit though that my suggestion is based more on how much I would have appreciated such a talk as an undergraduate, rather than on experience with its practicality. – Igor Khavkine Apr 4 '11 at 1:19

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