Taylor’s theorem and the symmetric group

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Anytime I see an $n!$ in some formula, my instinct is to look for the symmetric group on $n$ letters coming in somewhere. I have never done this seriously with the $n!$ in Taylor's theorem.

Question: Is there some way to see the $n!$ in Taylor's theorem coming naturally from a symmetry group?

Possible lead:

Here is a definition of $f^{(n)}(a)$ which does not depend on finding earlier derivatives: Let $g: \mathbb{R}^n \rightarrow \mathbb{R}$ be defined by $g(x_1,x_2,x_3, ..., x_n)$ is the lead coefficient of the unique $n^{th}$ degree polynomial passing through $(a, f(a)), (x_1, f(x_1)),(x_2, f(x_2)),...,(x_n, f(x_n))$. Then $f^{(n)}(a)$ is $1/n!$ times the limit of $g(x_1,x_2,x_3, ..., x_n)$ as $(x_1,x_2,x_3, ..., x_n)$ approaches $(a,a,a,...,a)$. Could the $1/n!$ be related to the symmetry of $g$ under exchange of coordinates?

-

6 Answers

There must be many ways to think of this. Here's one:

The symmetric group is involved with homogeneous polynomials of degree $n$ because they correspond to symmetric multilinear functions of $n$ variables, and division by $n!$ appears when recovering the former from the latter. For example, a homogeneous polynomial map $f:V\to W$ of degree $3$ determines a map $F:V\times V\times V\to W$ by $$F(x,y,z)=f(x+y+z)-f(x+y)-f(x+z)-f(y+z) +f(x)+f(y)+f(z)-f(0),$$ and $f(x)$ can be recovered as $$\frac{F(x,x,x)}{3!}.$$

The same formula for $F(x,y,z)$ can be applied to other functions $f(x)$. Applied to a polynomial of degree $<3$ it gives zero. Applied to a polynomial of degree $\le3$ it gives the multilinear function that corresponds to the purely cubic part of $f$. Applied to any function at all it gives a symmetric function of $(x,y,z)$ that vanishes when $x$ or $y$ or $z$ is zero.

The foundation of all differential calculus is the process that takes $f$, subtracts $f(0)$, and then makes the best linear approximation of the result. If you apply this process in all three variables to $f(x+y+z)$, you are first making $F(x,y,z)$ and then (assuming that $f$ was sufficiently smooth) making best linear approximation in all variables. If you then set $x=y=z$ and divide by $3!$, you get the third term in the Taylor series of $f$.

Of course, if you perform the linearizations in the three variables one after another then you see this trilinear map as a derivative of a derivative of a derivative.

The reason I look at it this way is that a homotopical categorical analogue of this plays a big role in my "functor calculus". The analogue there of division by $n!$ is a homotopy orbit spectrum for an action of the symmetric group.

In a little more detail:

Let $V$ and $W$ be model categories in which filtered homotopy coimits commute with finite homotopy limits. Assume that $W$ is stable, meaning that the final object is equivalent to initial object and that homotopy pushout squares are the same as homotopy pullback squares. For example, $W$ might be the category of spectra and $V$ might be spaces or spectra. Consider functors $f:V\to W$ that are homotopy-invariant (preserve weak equivalences). Say that $f$ has degree $\le 1$ if it preserves homotopy pushout squares. Say that it has degree $\le d$ if it takes those $(d+1)$-dimensional square diagrams all of whose $2$-dimensional faces are homotopy pushouts to homotopy pushout cubes, those in which the last object is the homotopy colimit of the others. Call $f$ reduced if it takes the trivial object $\star$ to itself (up to equivalence). Call it linear if it has degree $\le 1$ and is reduced. There is a linearization process that takes a reduced functor and makes the universal linear functor under it: basically $hocolim \Omega^nf\Sigma^n$. This can be easily generalized to make something called $P_1$ (first polynomial approximation) which takes any functor $f$, reduced or not, and makes the universal degree $\le 1$ functor $P_1f$ under it. (If we first reduce $f$ by taking the homotopy fiber of $f\to f(\star)$ and then linearize, it's the same as first doing $P_1$ and then reducing.) It can be further generalized to make something called $P_d$ ($d$th polynomial approximation) which takes any functor $f$ and makes the universal degree $\le d$ functor $P_df$ under it. The homotopy fiber of the canonical map $P_df\to P_{d-1}f$ is always a degree $\le d$ functor such that $P_{d-1}$ of it is trivial. Call such functors homogeneous of degree $d$. When $d=1$ this is the same as linear.

There is the functor of $d$ variables $(X_1,\dots,X_d)\mapsto f(X_1+\dots +X_d)$, where $+$ means (derived) coproduct. This is symmetric in the sense that there are isomorphisms when you permute the inputs, satisfying the obvious identities. Reduce it in all variables simultaneously, by first making a cubical diagram consisting of the objects $f(X_S)$, coproduct of all the $X_i$ for $i\in S$, and then looking at the homotopy fiber of the canonical map from $f(X_1+\dots +X_d)$ to the holim of all the rest. I call this reduced symmetric functor of $d$ variables the $d$th crosseffect of $f$. If we simultaneously linearize it in all variables, we get a symmetric multilinear functor.

If $f$ has degree $\le (d-1)$ then its $d$th crosseffect is contractible. If $f$ is homogeneous of degree $d$ then its $d$th crosseffect is already multilinear, and this way of making a symmetric multilinear functor from a homogeneous degree $d$ functor can be inverted: $f(X)$ is the homotopy orbit object for the action of the $d$th symmetric group on $F(X,\dots ,X)$, where the action on $F(X,\dots ,X)$ is the one that you get from the symmetry on $F(X_1,\dots ,X_d)$.

For general $f$ the multilinearization of the crosseffect is the same symmetric multilinear functor that corresponds in this way to the $d$th homogeneous part of $f$, i.e. to the homotopy fiber of $P_df\to P_{d-1}f$.

Again, by linearizing in one variable at a time you can work out a sense in which the multilinear functor corresponding to the $d$th homogeneous part is in fact an iterated derivative. But in this context it is important to have the option of performing linearization in all variables simultaneously, so to speak, in order that the result should be symmetric in the sense that is required for reconstructing the corresponding homogeneous functor. (Here symmetry is a structure, not a property.)

-

1
1+. It would be great if you elaborate on the last point. I think this will yield a good answer to the question because apparently, you don't just use permutations, but rather the whole group of permutations in a categorified setting for the derivative. – Martin Brandenburg Nov 12 2011 at 17:06
While this idea is awesome, it doesn't seem to explain why one should, in fact, divide by $n!$ there. – Will Sawin Nov 13 2011 at 17:30
Martin: I have now done so. Will: My observation that $n\!$ comes into the formula for recovering a homogeneous polynomial from a symmetric multilinear polynomials is very closely related to point 3 in your answer. The fact that in the categorical version the "division by $n\!$" involves the symmetric group rather than just its order may shed some light on the question, somehow. – Tom Goodwillie Nov 13 2011 at 17:42

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

One way is to use a combinatorial definition of the derivative. Let $A(z) = \sum a_n z^n$ be a power series. In combinatorics, where $A$ is likely to be an ordinary generating function, $a_n$ is likely to count the number of possible combinatorial structures of some kind on an ordered set with $n$ elements. For example when $a_n = 1$ the structure is "being an ordered set," when $a_n = a^n$ the structure is "being an ordered set together with a choice, for each element of the order, of a letter from an alphabet of size $a$," and so forth.

Then a combinatorial definition of the derivative $A'(z) = \sum na_n z^{n-1}$ is as follows: the derivative is an operation that given an $A$-structure produces a new type of structure, an $A'$-structure. An $A'$-structure is "being an ordered set together with an extra element, and an $A$-structure on the new order." This is because for an ordered set with $n$ elements there are $n+1$ possibilities for the extra element and $a_{n+1}$ possibilities for the $A$-structure on the new order.

Then after applying the derivative $k$ times we have added $k$ new elements. If we start from the empty set then there are $k!$ ways to do this, and the set of such ways to do this is naturally a torsor for the symmetric group $S_k$. (A simple example of one benefit of categorification: when you replace numbers by sets, they can support more complicated structures such as group actions.)

One nice property of this definition is that it offers a conceptual interpretation of the Leibniz rule. First, recall that if $A, B$ are two generating functions for $A$-structures and $B$-structures, then an $AB$-structure is a partition of an ordered set into a first segment and a second segment together with an $A$-structure on the first segment and a $B$-structure on the second segment, and the corresponding generating function is the product $AB$. Now, the derivative $(AB)'$ counts the number of ways to add one element to an ordered set and then put an $AB$-structure on the new order. The new element may be either in the first segment or the second segment, and this gives the two terms $A B'$ and $A' B$ in the Leibniz rule.

There is a second, possibly more satisfying, explanation using the theory of combinatorial species and groupoid cardinality. I seem to recall that this explanation was written up by John Baez somewhere in This Week's Finds, but I can't currently find it.

-

3
This is a very nice answer, but also unsatisfying in some way. Trying to pin down what's unsatisfying - is it at all possible to prove that this combinatorial definition of the derivative is the same as the analytic definition without coming close to reproving Taylor's Theorem first? Of course the n! in exponential generating functions comes from the symmetric group - EGFs were chosen because of that, and not vice versa! – Alexander Woo Nov 12 2011 at 6:13

2
Also, I got the impression that Steve didn't want to assume that the power series had to be a generating function (or exponential generating function, as the case may be) of a species. (I even suspect that Steve has seen the species-theoretic (categorified) notion of differentiation.) So I think he wants to interpret the $n!$ in a way which works for arbitrary power series, as addressed in Will's answer. – Todd Trimble Nov 12 2011 at 12:50
@Alexander: well, in this answer I am really only concerned with formal power series, and there the derivative $D$ is uniquely characterized by the properties $D(1) = 0, D(x) = 1$, the Leibniz rule, and continuity with respect to the $z$-adic topology. The analytic content of Taylor's theorem (the first part Will mentions) isn't really relevant to the appearance of factorials. @Todd: one can do this by replacing counting with "weighted counting" (turning each $a_n$ into a formal variable), although I don't know how satisfying this is. – Qiaochu Yuan Nov 12 2011 at 15:38
I was not familiar with this. Are there any places you would recommend for reading a systematic treatment of it? – Phil Isett Nov 12 2011 at 22:46
@Phil: try Bergeron, Labelle, and Leroux's Combinatorial Species and Tree-Like Structures, although I am not sure it covers ordinary, as opposed to exponential, generating functions. (Exponential generating functions describe structures on unordered sets, and there is a second combinatorial definition of the derivative that applies in that case.) I think there is also an informal treatment in Flajolet and Sedgewick's Analytic Combinatorics (freely available here: algo.inria.fr/flajolet/Publications/books.html). – Qiaochu Yuan Nov 13 2011 at 0:21
1. Don't you mean to say that $f^{(n)}(a)$ is $n!$ times the lead coefficient? For instance, take $f=x^n$.

2. The functions $f_k(n)=\frac{n!}{(n-k)!k!}$ satisfy a discrete version of the derivative. $f_k(n)-f_k(n-1)=f_{k-1}(n)$. If we view Taylor's theorem as being about approximating with a very fine version of these functions, we just have to see where and why $k!$ arises in their combinatorics.

3. Fundamentally, we can break Taylor's theorem up into two parts - that functions are approximable by polynomials, which with your definition of $g$ could create an $n!$-free version, and that the $n$th derivative of $x^n$ is $n!$. The first part has no $n!$ in it. The second one doesn't seem very deep, but is very clearly about $S_n$. Take $x \cdot x \cdot x \cdot ... \cdot x$, and differentiate it $n$ times. By the product rule, we have to choose an order to differentiate the $x$s in. Because the second derivative of $x$ is zero, we must avoid repetition. Clearly, this is where your permutations come from.

-

1.  Indeed I did - I goofed. 3. Nice observation!  I think this answers my question at the level I wanted to see an answer. – Steven Gubkin Nov 13 2011 at 16:58

Seems to me the question is just a mighty complicated way to ask "how does $n!$ creep into the $n$-th derivative (analytic or formal) of $x^n$", to which the answer is ob course as Will Sawin noted "through repeated application of the product rule".

I think the question should say Taylor's formula, not Taylor's theorem (and this is true for many uses of Taylor's theorem elsewhere). Taylor did not have any theorem, and what is nowadays called Taylor's theorem (any of the many forms) can be stated without mentioning $n!$ at all, after subtracting off the uninteresting polynomial part (once we've learned about linearity and how to differentiate monomials): "if $f$ is $n$ times differentiable at $a$ with its value and all $n$ derivatives zero at $a$ (and possible additional regularity hypothesis in a neighbourhood of $a$) then (the error term) $f(x)$ satisfies (you favorite estimate or formula) for $x$ in some (specific) neighbourhood of $a$".

And if the question is about relating the coefficients of the Taylor polynomial to the derivatives, then it really boils down to understanding the differentiation of monomials.

-

I think the most obvious way to see the symmetric group appearing is the following. To calculate the difference between $f(x)$ and the constant $f(0)$

$f(x) - f(0) = \int_0^x f'(s_1) ds_1$

Often we do this move because $x$ is small, so we figure that a small change in the input to $f$ will result in the output changing depending on the derivative of $f$. But the same logic goes for $f'$, so applying the same formula to $f'$, we get:

$f(x) = f(0) + f'(0) x + \int_{0 < s_2 < s_1 < x} f''(s_2) ds_2 ds_1$

Note $f'$ may not change significantly from its initial value if $f''$ is under control, but there can be oscillations at the level of the next derivative responsible for $f'$ experiencing a small change -- in this case Taylor expansion usually is not helping us understand the problem. In any case, here we have an integral over the region ${ 0 < s_2 < s_1 < x }$. This is a fundamental domain for the action of $S_2$ on the square ${ 0 < s_1, s_2 < x}$, so if $f''$ is a constant $f''(0)$, you get the volume $x^2 / 2!$ times $f''(0)$.

Even if $f''$ is not constant, you can certainly write $f''(s_2) = f''(0) + \int_0^{s_2} f''(s_3) ds_3$ and get $f''(0) x^2 / 2!$ plus an integral over ${ 0 < s_3 < s_2 < s_1 < x }$, which is again a fundamental domain for the action of $S_3$ therefore has volume $x^3/3!$. Similar considerations apply to the higher order terms.

Normally we replace the use of Fubini's theorem here with an equivalent integration by parts so that we never see iterated integrals. (Fubini's theorem is one way to prove integration by parts, so it really is the same move.)

-

Looking at the answers leaves me with an un-easy feeling. We just made something simple into something very complicated. The understanding produced was borderline nil, because the question was wrong in the first place. Why make a simple thing complicated?

-

4
You are very wrong, even spiritually wrong. Even simple ideas in mathematics can become springboards to deeper understandings, and the fact that these answers haven't produced this understanding in you doesn't mean they don't enlighten anyone else. To pick out one, I'd say Tom Goodwillie's answer reflects great depth of understanding, based on decades of his own research. – Todd Trimble Nov 13 2011 at 12:40
You see my stance, is that these answer actually obscure the understanding. I can read them and understand them, but I still think that what we're doing here is just trying to fit something that doesn't quit fit into what we want it to fit. – nothappy Nov 13 2011 at 12:44

2
@nothappy: I am sorry, but unless you can prove that these answers obscure understanding, and you cannot, this answer is subjective and argumentative. – Todd Trimble Nov 13 2011 at 12:49
@Todd: Same applies to you :-) – nothappy Nov 13 2011 at 12:49

7
@nothappy: It's true that these answers are, in a sense, making something simple more complicated, or at least more subtle. It would be crazy to teach Taylor's theorem to calculus students using such an approach. However, it's important in mathematics to take simple ideas and ask what they mean in a deeper context. This is not always fruitful, but it can lead to richer interconnections and conceptual understanding. People can reasonably disagree about whether they have learned something, based on their background and taste, but it is silly to insist that nobody is learning anything here. – Henry Cohn Nov 13 2011 at 15:15
show 2 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 194, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9457945227622986, "perplexity_flag": "head"}