A symmetric function is a polynomial or rational function (quotient of polynomials) in n variables which remains invariant no matter how you permute variables (e.g. swap x₁ with x₂). They feature prominently in Galois theory. The elementary symmetric functions appear as the coefficients of a polynomial in n indeterminates (i.e. the coefficients of f(t) = (t - x₁)···(t - x_n) ), and the fundamental theorem of symmetric functions says that any symmetric function can be expressed as a polynomial or rational function of elementary symmetric functions. When the original function isn't symmetric, we can still say something interesting.

Theorem: Let g(x) be any polynomial where x = (x₁, ..., x_n) are n variables, and let s₁, ..., s_n be the elementary symmetric functions in n variables. Then g(x) can be written as a linear combination of monomials

x₁^ν₁ x₂^ν₂ ··· x_n^ν_n

such that ν_i ≤ i - 1 and the coefficients of the monomials are polynomials in the s_i.

This theorem, seemingly due to Emil Artin, is a slight generalisation of the fundamental theorem of symmetric functions. It gives the closest possible expression of any polynomial in terms of symmetric functions no matter if the original polynomial is symmetric or not. Or if you prefer, the fundamental theorm of symmetric functions comes as an easy corollary to this theorem.

The corollary is obvious. Observe that the nature of monomials is such that they can't be symmetrised, because the powers in the monomial have to be nondecreasing by indices. Thus, if the original polynomial g(x) was symmetric, then the only way it can still be symmetric after being written in this form is if the only monomial with nonzero coefficient is the one for which all the ν_i are zero, i.e. the constant term. But then the constant term is a polynomial of elementary symmetric functions, proving the corollary.

The proof is an algorithm for putting g(x) in the desired form.

Proof: Let f_n(t) := (t - x₁)(t - x₂ )···(t - x_n) = tⁿ - s₁t^n-1 + ··· + (-1)ⁿs_n and define recursively

f_{i - 1}(t) := f_i(t)/(t - x_i).

Three things are immediately clear:

• The polynomial f_i(t) has x_i as a root, the other roots being the other x_j with j < i, because it's just f_n(t) with the last n - i linear factors divided away.
• By synthetic division and by the recursive definition, the coefficients of f_i(t) are polynomials in terms of the elementary symmetric functions and the x_j with j > i.
• The degree of f_i(t) is i.

Now for the algorithm to put g(x) in the desired form. Since x₁ is a root of f₁(t), it is possible to express x₁ in terms of the symmetric functions s_i and the rest of the x_i with i > 1. Substitute this expression of x₁ into g(x), and expand out the result, which does not contain any term with x₁ now.

We proceed recursively as follows. Since x₂ is a root of f₂(t), it is possible to express x₂² or any higher power in terms of the symmetric functions s_i and the rest of the x_i with i > 2, with perhaps a few terms of x₂ of degree less than 2. Substitute this expression of x₂² (or higher) into g(x), and expand out the result, which no longer contains any term with x₂² or higher degree.

Continuing in this process of eliminating all third powers of x₃ or higher with f₃(t), all fourth powers of x₄ or higher with f₄(t), we obtain the desired form for g(x).

QED.

Let's work out an example. Unfortunately, the only way to make an interesting enough example involves heavy computations. I will work out some steps of the example, but I will leave most of the boring manipulations to Maxima or to a diligent reader.

Let us consider the symmetric polynomial in 3 variables

g(x) = x₁²x₂ + x₁²x₃ + x₂²x₁ + x₂²x₃ + x₃²x₁ + x₃²x₂

Now, in 3 variables, the f_i(t) from the proof above are

f₃(t) = t³ - s₁t² + s₂t - s₃,
f₂(t) = t² + (x₃ - s₁)t + (s₂ - s₁x₃ + x₃²),
f₁(t) = t - s₁ + x₂ + x₃.

Recall that f₂ and f₁ are obtained by symbolic synthetic division of the polynomial above them and that the remainders are zero. Also, recall at this point that the elementary symmetric functions in three variables are

s₁ = x₁ + x₂ + x₃,
s₂ = x₁x₂ + x₁x₃ + x₂x₃,
s₃ = x₁x₂x₃.

Since f₁(x₁) = 0, f₂(x₂) = 0 and f₃(x₃) = 0, we obtain that

x₁ = s₁ - x₂ - x₃,
x₂² = s₁x₂ + s₁x₃ - s₂ - x₂x₃ - x₃²,
x₃³ = s₁x₃² - s₂x₃ + s₃.

So, the algorithm now says to replace this expression for x₁ into g(x), which after expanding everything out becomes

3x₂x₃² - s₁x₃² + 3x₂²x₃ - 4s₁x₂ x₃ + s₁²x₃ - s₁x₂² + s₁²x₂.

Note that we have succeeded in eliminating x₁ from this expression. Now we do the same with x₂², to obtain

-3x₃³ + 3s₁x₃² - 3s₂x₃ + s₁s₂.

Finally we replace x₃³ by its own expression to conclude that

g(x) = s₁s₂ - 3s₃,

which is the expression of g(x) in terms of elementary symmetric functions that we sought.

No joke — there's a semi-serious proof involved here. We're looking for the smallest number that could easily be mistaken for prime but in fact is not. How do we find it? Well, since it's not prime, let's look for its prime factors.

• The number can't be a multiple of two — even numbers are too easy to spot.
• The number can't be a multiple of three — there's an easy test for that.
• The number can't be a multiple of five — thanks to our base ten number system, it's too easy to find those.
• Seven? Sure, why not? Multiples of seven don't look special at all. But we need more than one prime factor -- everybody knows that 49 is seven squared.
• The other factor can't be eleven — 7 x 11 = 77, obviously not prime. Multiples of 11, especially low ones, are fairly obvious.
• But what about thirteen? 7 x 13 = 91. That...looks prime.

So there you have it. A rigorous proof that the smallest number that looks prime but isn't is 91. Use this to impress your friends and shame your enemies at cocktail parties.

But what about the smallest number that can't be described in fewer than 15 words?

Sewing without Calculus

Buffon's needle is deeply unsatisfying: a question with only a passing relationship to circles (the needle can fall in any orientation -- but there's still the small matter of lateral motion!) ends up connected to π. Why?

The standard proof -- above in devout's writeup, with integrals -- does little to explain the mysterious appearance of π. Calculation is often like that.

Geometric measure theory offers a "clean" proof, one that almost does explain where π comes from. And it goes like this.

1. We are interested in the probability "p_L" that a needle of length L, randomly dropped on a surface ruled with lines at interval 1 from each other, will intersect a line. Suppose L≤1. Then almost always the needle can intersect at most 1 line, so either it intersects 1 line (with probability p_L) or it intersects 0 lines (with probability 1-p_L). Thus we may take the expectation to get the probability:

   p_L = e(L) = E(number of intersections of a needle of length L with a line)

2. Suppose we connect 2 needles of lengths L and M at their edge (not necessarily in a straight line -- we're interested in a crooked needle). Since expectation is linear, the expected number of intersections of our crooked needle with a line is

   e(L+M) = e(L) + e(M)

   (Note that our notation e(L+M) ignores the shape of the needle, as the RHS does not depend on this shape!). Naturally, we can do this for any number of needles glued at their ends. So e is a linear function, and e(t)=ct for some constant c.
3. We wish to find c -- then we will be able to determine e(L) and, especially, e(1).
4. By using our favourite convergence theorem on expectation (e.g., the monotone convergence theorem) we see that for any curve with length L, if we drop it at random, the expected number of intersections with a line will be e(L)=cL.
5. OK, so let's pick a particularly easy curve. Take the circle of diameter 1. Its perimeter is π, so the expected number of intersections of a circle of diameter 1 with a surface ruled with lines at interval 1 is e(π)=cπ. On the other hand, no matter how we drop this circle, it always intersects exactly 2 lines! So e(π)=2, and therefore c=2/π, as required.

QED.

---

The proof above is based on what appears in the introduction to

• Daniel A Klain and Gian-Carlo Rota, Introduction to Geometric Probability, Lezioni Lincee, published Cambridge University Press 1997.

Naturally, that book goes considerably further -- and generally in more algebraic directions.