text:
\begin{document}

\title[Ultraspherical basis transformation]{Monomial to ultraspherical basis transformation and the zeros of polynomials}

\author[M.~Chasse]{Matthew Chasse}

\address{Department of Mathematics, The Royal Institute of Technology, SE-100 44 Stockholm, Sweden}

\email{chasse@math.hawaii.edu}

\keywords{total positivity, sign regularity, ultraspherical polynomials, orthogonal polynomials, Legendre polynomials}
\subjclass[2010]{ Primary 26C10; Secondary 30C15}

\begin{abstract}
We examine a result of A.~Iserles and E.~B.~Saff, use it to prove a conjecture of S.~Fisk that a linear operator which maps monomials to Legendre polynomials also preserves zeros in the interval $(-1,1)$, and state a more general version of the conjecture for the Jacobi polynomials.
\end{abstract}

\maketitle

\section{Introduction}

Let $P_n^{(\alpha,\beta)}(x)$ represent the $n$-th Jacobi polynomial with parameters $\alpha$ and $\beta$, defined by the generating function \cite[p. 271]{R},

\begin{equation}\label{jacobi-gen}
F(x,t) := \frac{2^{\alpha+\beta}}{\rho(1+t+\rho)^{\beta}(1-t+\rho)^{\alpha}} = \sum_{k=0}^\infty P_{n}^{(\alpha,\beta)}(x) t^n ,
\end{equation}
\\
where $\rho = (1-2xt+t^2)^{1/2}$.
The set $\{P_n^{(\alpha,\alpha)}(x)\}_{n=0}^\infty$, known as the ultraspherical polynomials \cite[p. 276]{R}, is also obtained from the simpler generating function
\\
\begin{equation}\label{Pgen}
G(x,t):=(1-2xt+t^2)^{-\alpha-\frac{1}{2}} = \sum_{n=0}^\infty \frac{(1+2\alpha)_n}{(1+\alpha)_n}P^{(\alpha,\alpha)}_n(x)t^n,
\end{equation}
\\
where $(x)_n = x(x+1)(x+2)\dots(x+n-1)$ is the commonly used \emph{Pochhammer symbol}.  When $\alpha=0$, the ultraspherical polynomials are the classical Legendre polynomials, which we denote by $P_k(x)$ ($P_k(x)=P^{(0,0)}_k(x)$).
We prove the following conjecture from S. Fisk's electronic book \cite{fisk}, which is left as an open problem in the book's appendices.
\begin{conj}{\rm (S. Fisk \cite[p. 724, Question 39]{fisk})}\label{Pconj}
If $f(x)=\sum_{k=0}^n a_k x^k\in\rl[x]$ has all of its zeros in the interval $(-1,1)$ then $T[f](x)=\sum_{k=0}^n a_k P_k(x)$ has all of its zeros in $(-1,1)$.
\end{conj}
The proof of Conjecture \ref{Pconj} is accomplished through a technique of A.~Iserles and E.~B.~Saff.  Many similar transformations involving orthogonal bases have already been established by Iserles, N{\o}rsett, and Saff using the same method in conjunction with other identities \cite{IN1, IN2, IS}.  Our main result is the following.

\begin{theorem}\label{main}
If $f(x)=\sum_{k=0}^n a_k x^k\in\rl[x]$ has all of its zeros in the interval $(-1,1)$ then
\[
T[f](x)=\sum_{k=0}^n a_k \frac{k!}{\Gamma(k+1+\alpha)} P^{(\alpha,\alpha)}_k(x)
\]
 has all of its zeros in $(-1,1)$ for $\alpha>-1$.
\end{theorem}

Conjecture \ref{Pconj} follows from Theorem \ref{main} with $\alpha=0$.  Iserles and Saff already proved that $x^n\to  (n!/\Gamma(n+1+\alpha)) (2n+2\alpha+1)P^{(\alpha,\alpha)}_n(x)$ maps polynomials whose zeros lie in the interval $(-1,1)$ to polynomials whose zeros lie in the interval $[-1,1]$ \cite[Proposition 3]{IS}.  We modify the generating function \eqref{Pgen} with a differential operator and apply the observation in Lemma \ref{open-sets} (below) to change the Iserles--Saff proof into the one we require.

We provide a short proof of the Iserles--Saff theorem in Appendix \ref{biortho-polys}, both for reference and to aid in the discussion, as we state it in a more general form.  The characterization of all linear transformations which preserve the set of polynomials whose zeros lie on an interval is an open problem as mentioned in \cite{IN2}, and stated more formally in \cite{BB1, CC3}.  A successful characterization would hopefully provide simple proofs of Theorem \ref{main} and Theorem \ref{key}.

Total positivity and sign regularity are introduced in Section \ref{section-tp}, along with Theorem \ref{key} of Iserles and Saff.  We also discuss problems which appear difficult with the currently available techniques for establishing sign regularity.
In Section \ref{section-proof}, we prove Theorem \ref{main} and pose a conjecture which extends it (Conjecture \ref{jacobi-trans}).

{\bf Acknowledgements.}  The author thanks Professor P.~Br\"and\'en for his comments and corrections, and Professor G.~Csordas for suggesting the application of the Iserles--Saff theorem to some of Fisk's conjectures.

\section{Total positivity and the Iserles-N{\o}rsett-Saff theorem}\label{section-tp}

In the proof of Conjecture \ref{Pconj}, we rely on the strict sign regularity (Definition \ref{def:ssr}) of a generating function related to the transformation.

\begin{defn}\label{def:ssr}
The kernel function $G:X\times Y\to\rl$ is said to be \emph{strictly sign regular} (SSR) if, given any two increasing m-tuples  $x_1 < x_2 < \ldots < x_m$,  $y_1 < y_2 < \ldots < y_m$, in $X$ and $Y$ respectively,

\beq
\varepsilon(m)\left| \begin{array}{cccc}
G(x_1,y_1) &  G(x_1,y_2) & \ldots & G(x_1,y_m) \\
G(x_2,y_1) & G(x_2,y_2)  & \ldots & G(x_2,y_m)\\
\vdots & \vdots & \ddots & \vdots \\
G(x_m,y_1)  & G(x_m,y_2)  & \ldots & G(x_m,y_m) \end{array} \right|>0.
\label{detcond}
\eeq
for all $m\in\nn$, where $\varepsilon(m)$ is a function of $m$ only and has the range $\{-1,1\}$.  If $\varepsilon(m)=1$, the kernel $G(x,t)$ is said to be \emph{strictly totally positive} (STP), and if equality is allowed \emph{totally positive} (TP)  (see \cite{karlin}).
\end{defn}

A sequence of functions $\phi_0(x), \phi_1(x),\dots, \phi_n(x)$ is said to constitute a \emph{Tchebyshev system} on $a<x<b$ if for any set of real constants $\{c_k\}$, not all zero, $\sum_{k=0}^n c_k\phi_k(x)$ does not vanish more than $n$ times on $a<x<b$ \cite[p.~24]{karlin}.  If every subset of a Tchebyshev system is also a Tchebyshev system, then $\phi_y(x)$ is SSR.

\begin{theorem}[{\cite[p. 18]{karlin}}]\label{factortheorem}
Let $K(x,y)$ be $SSR$ \textup{(}$x\in X$ and $y\in Y$\textup{)}, and suppose $\varphi(x)$ and $\psi(x)$ maintain the same constant sign on $X$ and $Y$, respectively.  Then
\bnum
\item $L(x,y)=\varphi(x)\psi(y)K(x,y)$ is $SSR$.

\item Now suppose $u=\varphi^{-1}(x)$ and $v=\psi^{-1}(x)$ be strictly increasing functions mapping $X$ and $Y$ onto $U$ and $V$, respectively, where $\varphi^{-1}$ and $\psi^{-1}$ are the inverse functions of $\varphi$ and $\psi$, respectively.

Consider
$$ L(u,v) = K[\varphi(u),\psi(x)] \text{ \hspace{ 5mm} } u\in U, v\in V.$$
Then $L(u,v)$ is $SSR$ and with signs $\varepsilon_m(K) = \varepsilon_m(L)$.  If $\phi(u)$ is strictly increasing while $\psi(v)$ is strictly decreasing, then $L(u,v)$ is $SSR$ and $\varepsilon_m(K) = (-1)^{\frac{m(m-1)}{2}}\varepsilon_m(L)$.
\enum
\end{theorem}

\begin{theorem}[Composition Rule]\label{cbtheorem}
Let $K$, $L$ and $M$ be Borel-measurable functions of two variables satisfying
\[
M(x,y) = \int_Z K(x,\eta)L(\eta,y) d\sigma(\eta),
\]
where the integral is assumed to converge absolutely.  Suppose the variables $x$, $y$, and $\eta$ are in subsets of the real line $X$, $Y$, and $Z$ respectively, and $d\sigma(\eta)$ is a sigma finite measure on $Z$.  If both $K$ and $L$ are SSR (STP), then so is $M$ \cite[p. 16]{karlin}.
\end{theorem}

\begin{theorem}[{\cite[p. 15]{karlin}}]\label{exy}
$$K(x, y)=e^{xy}$$
is STP for $x,y\in\rl$.
\end{theorem}
It is worth noting that a generalization of Theorem \ref{exy} exists for power series in the form $\sum_{k=0}^\infty a_kx^ky^k$ \cite[Part V, \#86]{PSz2}.

Let $\RR^n/S_n$ be $n$-dimensional Euclidean space modulo permutations of the coordinates, e.g. $\RR^2/S_2=\{ \{(x_1,x_2),(x_2,x_1)\} : x_1, x_2\in\RR \}$.  Then, $\RR^n/S_n$ is a metric space when endowed with a Hausdorff distance between equivalence classes,
\[
d(y_1,y_2)= \inf_{a\in y_1, b\in y_2} ||a-b||_{\infty},
\]
for $y_1,y_2\in\RR^2/S_2$, where $||(x_1,\dots,x_n)||_{\infty}=\max\{|x_1|,\dots,|x_n|\}$.  This provides a natural topology for the zeros of polynomials of a fixed degree.  Let $I$ be an open or closed interval, and let $I^n/S_n$ denote the subset of $\RR^n/S_n$ where every component lies in the interval $I$.  The topology on $\RR^n/S_n$ induced by the metric $d(\cdot,\cdot)$ then has open sets which are generated by unions of the ``open intervals'' $(a,b)^n/S_n$, $a,b\in\RR$, $a\le b$.

\begin{lemma}\label{open-sets}
Suppose $T:\RR[x]\to\RR[x]$ is degree preserving, linear, invertible, and maps polynomials whose zeros lie in the interval $(c,d)$ to polynomials whose zeros lie in the interval $[a,b]$. Then $T$ furthermore maps polynomials whose zeros lie in $(c,d)$ to polynomials whose zeros lie in $(a,b)$.
\end{lemma}

\begin{proof}
Let $Q(x)=\sum_{k=0}^nq_kx^k$ be an arbitrary polynomial with zeros in $(c,d)$.
Let the map $\phi:(c,d)^n/S_n\to[a,b]^n/S_n$ be defined by the mapping of the zeros of $Q$ to the zeros of $T[Q]$.  As $T$ is degree preserving and invertible, both $\phi$ and $\phi^{-1}$ are well-defined, and both are continuous by linearity and Hurwitz's theorem.  Therefore, open sets in $(c,d)^n/S_n$ are mapped by $\phi$ to open sets in $[a,b]^n/S_n$, whence the zeros of $T[Q(x)]$ must lie in $(a,b)$, which covers all open sets contained in $[a,b]^n/S_n$.
\end{proof}

Theorem \ref{key} of A.~Iserles and E.~B.~Saff is required for our proof of Conjecture \ref{Pconj}, and a short proof is provided for the reader's convenience in Appendix \ref{biortho-polys}.  The original version of Theorem \ref{key} is sharpened here by using the observation in Lemma \ref{open-sets}, and relaxing the domain basis to a complete Tchebyshev system.

\begin{theorem}[A. Iserles and E. B. Saff \cite{IS}]\label{key}
Let $\{Q_n(x)\}_{n=0}^\infty$ be an orthogonal sequence of polynomials satisfying
\[
\int_{a}^b Q_n(x)Q_m(x) dx = \begin{cases}h_m , & \text{ for } m=n\cr
0, & \text{ for } m\neq n.
\end{cases}
\]
Let $\{R_k\}_{k=0}^\infty$ be a set of polynomials, with $\deg(R_k)=k$ (thus any subset  $\{R_k\}_{k=0}^n$, $n\in\NN$ is a Tchebyshev system on $(c,d)$).
If the generating function $G(x,t)=\sum_{t=0}^\infty \delta_kQ_k(x)R_k(t)$ is SSR for all $x\in(a,b)$ and $t\in(c,d)$, and all the zeros of the polynomial $\sum_{k=0}^nq_kR_k(x)$ are in the interval $(c,d)$, then all the zeros of the polynomial
\[
\sum_{k=0}^n\frac{q_k}{\delta_kh_k}Q_k(x)
\]
are in the interval $(a,b)$.
\end{theorem}

All of the transformations which have been obtained so far with Theorem \ref{key} have $R_k(t)=t^k$.  For other starting bases, showing the kernel
\[
G(x,t)=\sum_{t=0}^\infty \delta_kQ_k(x)R_k(t)
\]
is SSR on some region appears quite difficult. Two papers by J.~Burbea \cite{burbea2,burbea} establish the strict total positivity of several replicating kernels by extending the notion of total positivity and sign regularity to curves in the complex plane, but this approach is very restrictive.  For natural extensions of total positivity to the complex plane, compositions of the type in Theorem \ref{cbtheorem} are generally not possible without unusually convenient phase behavior of the kernels involved.

The lack of tools for determining totally positivity and sign regularity of kernels prevents application of Theorem \ref{key} in some desirable situations.
For example, in \cite{IS}, a comment is made that although the kernel
\[
\frac{1}{(1-2xy+y^2)^{\beta}}
\]
is not strictly totally positive on $(-1,1)\times (-1,1)$ for $\beta<0$, it appears to be strictly sign regular there.
Similarly, if the range of parameters for which \eqref{jacobi-gen} is STP or SSR could be determined, a large number of transformations involving the Jacobi polynomials would follow.

\section{Proof for the ultraspherical polynomial transform}\label{section-proof}

Recall that for $\Re(\alpha)>-1$, $\Re(\beta)>-1$, the Jacobi polynomials satisfy the orthogonality relation \cite[p. 260]{R}

\begin{align}
&\int_{-1}^1 P^{(\alpha,\beta)}_n(x)P^{(\alpha,\beta)}_m(x) (1-x)^\alpha(1+x)^\beta dx = \label{ortho} \\
&\qquad \begin{cases} \displaystyle \frac{2^{1+\alpha+\beta}\Gamma(1+\alpha+n)\Gamma(1+\beta+n)}{(2n+1+\alpha+\beta)n!\Gamma(1+\alpha+\beta+n)}, & \text{ for } m=n\\
\\
 \displaystyle 0, & \text{ for } m\neq n.\nonumber
\end{cases}
\end{align}
From Theorems \ref{cbtheorem} and \ref{exy} one obtains the next lemma.

\begin{lemma}[\cite{IS}]\label{handy}
The function
\[
K(x,y) = \frac{1}{(x+y)^{\beta}},
\]
where $\beta>0$, is STP for $x,y\in(0,\infty)$
\end{lemma}

By simple substitutions with Theorem \ref{factortheorem}, see \cite{IS}, Lemma \ref{handy} is transformed into what we require.

\begin{lemma}\label{legendre-gen-stp}
The function
\[
K(x,y) = \frac{1}{(1-2xy+y^2)^{\beta}},
\]
where $\beta>0$, is STP for $x,y\in(-1,1)$.
\end{lemma}

\begin{proof}[Proof of Theorem \ref{main}]
The series on the right-hand side of  \eqref{Pgen} is known to converge for all $x,t\in(-1,1)$.
Operating on \eqref{Pgen} with $\left(2t\frac{\partial}{\partial t} + 2\alpha + 1 \right)$, we obtain a second generating function which converges for the same range of parameters:
\begin{align*}
G_2(x, t) =& \left(2t\frac{\partial}{\partial t} + 2\alpha + 1 \right)G(x,t)\\
=& \frac{(2\alpha+1)(1-t^2)}{(1-2xt+t^2)^{\alpha+3/2}} \\
=& \sum_{k=0}^\infty (2k+\alpha+1)\frac{(1+2\alpha)_k}{(1+\alpha)_k}P^{(\alpha,\alpha)}_k(x)t^k.
\end{align*}
\noindent
By Theorem \ref{key}, with $\delta_k=2k+2\alpha+1$, and (from \eqref{ortho} with $\alpha=\beta> -1$)
\[
h_k=\frac{2^{1+\alpha}(\Gamma(1+\alpha+n))^2}{k!(2k+2\alpha+1)\Gamma(1+2\alpha+2k)},
\]
it is sufficient to show that $G_2(x,t)$ is SSR for $x,t\in(-1,1)$.  By Theorem \ref{factortheorem}, the factor $(2\alpha+1)(1-t^2)$ can be dropped, and it is sufficient to check that
\[
 \frac{1}{(1-2xt+t^2)^{\alpha+3/2}}
\]
is SSR for $\alpha>-1$, which follows by Lemma \ref{legendre-gen-stp}.
\end{proof}

It is natural to question whether Theorem \ref{main} can be extended to the Jacobi Polynomials. Fisk has posed the following related question.

\begin{question}[{\cite[p. 724, Question 40]{fisk}}]\label{jacobi-fact}
For which $\alpha$ and $\beta$ does the transformation $x^n\to P^{(\alpha,\beta)}_n(x)/n!$ preserve the set of polynomials with only real zeros?
\end{question}

Numerical experiments using polynomials of the form $(x-1)^n(x+1)^m$, $n+m\le14$, suggest the restriction $\alpha,\beta\ge0$ in Question \ref{jacobi-fact}.  As an extension of Conjecture \ref{Pconj} (settled by Theorem \ref{main}) we state the following conjecture, which has been verified using Mathematica for $\alpha,\beta<5$, with $(x-1)^n(x+1)^m$, $n+m\le14$, and a large number of random polynomials of degree less than ten with zeros in the interval $(-1,1)$.

\begin{conjecture}\label{jacobi-trans}
If $\alpha$ and $\beta$ are non-negative integers, then $x^n\to P^{(\alpha,\beta)}_n(x)$ preserves the set of polynomials whose zeros lie only in the interval $(-1,1)$.
\end{conjecture}

\renewcommand\refname{References}


TITLE: Proving a relation is transitive
QUESTION [0 upvotes]: I am trying to understand transitive relations.
I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive.
But for longer sets I am getting confused in finding out if it is transitive.
So if I had a set: $\{(1,1)(1,3)(1,5)(2,2)(2,4)(3,1)(3,3)(3,5)(4,2)(4,4)(5,1)(5,3)(5,5)\}$
For example: I have $\{(1,3)\}$ and $\{(3,5)\}$ which means I need $\{(1,5)\}$ which I do.
But to prove it is transitive would I need $\{(1,1)\}$ having $\{(1,3)(3,1)\}$?
Also how many transitive relations are within that set?

REPLY [1 votes]: Heres a nice theorem which helps in determining whether or not a relation is transitive. Let's define a relation $\mathbf{R}$ on a set $A$. We know that this defines a relation $\mathbf{R}:A \longrightarrow A$. Now, we want to prove that $\mathbf{R}$ is a transitive relation.
Theorem: $\mathbf{R}$ is a transitive relation if and only if $\mathbf{R}^{n} \subseteq \mathbf{R}$ for every positive integer $n$.
$\mathbf{Proof} (\longrightarrow)$:(via mathematical induction)
Suppose $\mathbf{R}$ is a transitive relation. Define the propositional function $P(n)$ such that $P(n)$ implies that $\mathbf{R}^{n} \subseteq \mathbf{R}$. Now we check the base case: $n=1$. Since $\mathbf{R}^{1}=\mathbf{R}$, it follows that $\mathbf{R}^{1} \subseteq \mathbf{R}$ and so $P(1)$ is true. We now must show that if $P(n)$ is true, then $P(n+1)$ is true. In other words, if $\mathbf{R}^{n} \subseteq \mathbf{R}$ then $\mathbf{R}^{n+1} \subseteq \mathbf{R}$. Let $\alpha,\beta \in A$ such that $\alpha$ and $\beta$ are related under $\mathbf{R}^{n+1}$. More compactly, we may write this as $(\alpha, \beta) \in \mathbf{R}^{n+1}$. Recall that $\mathbf{R}^{n+1}$ is the composition of $\mathbf{R}^{n}$ and $\mathbf{R}$; in other words: $\mathbf{R}^{n+1} = \mathbf{R}^{n} \circ \mathbf{R}$. Now, since $(\alpha,\beta) \in \mathbf{R}^{n+1}$, it follows from the definition of a transitive relation that there exists $\theta \in A$ such that $(\alpha,\theta) \in \mathbf{R}$ and $(\theta, \beta) \in \mathbf{R}^{n}$. Since $\mathbf{R}^{n} \subseteq \mathbf{R}$, we know that $(\theta, \beta) \in \mathbf{R}$. Since we defined $\mathbf{R}$ as a transitive relation, it follows that $(\alpha ,\beta) \in \mathbf{R}$. Therefore $\mathbf{R}^{n+1} \subseteq \mathbf{R}$.
$\mathbf{Proof} (\longleftarrow)$:
Let $a,b,c \in \mathbf{R}$ such that $(a,b) \in \mathbf{R}$ and $(b,c) \in \mathbf{R}$. Now can compose $\mathbf{R}$ with itself; in other words, take $\mathbf{R} \circ \mathbf{R}$. If we do so, then $(a,c) \in \mathbf{R} \circ \mathbf{R} = \mathbf{R}^{2}$. By hypothesis,$\mathbf{R}^{2} \subseteq \mathbf{R}$, and thus $(a,c) \in \mathbf{R}$. Therefore $\mathbf{R}$ is transitive.
This completes the proof.
Now you have posed a very insightful question regarding the number of transitive relations on a set. Until now, the only way to compute the number of transitive relations is to find them via brute-force methodology: counting transitive relations is an open problem in combinatorics!
Hope this helped.


TITLE: Understanding the Handshake Problem
QUESTION [2 upvotes]: I need help with this problem. The problem goes like this: In some countries it is customary to shake hands with everybody in the meeting. If there are two people there is 1 handshake, if there are three people there are three handshakes and so on. I know that the formula is $ \dfrac{n(n-1)}{2} $ but how do I get to this solution using a thinking process, specifically how would you solve this? Thanks.

REPLY [0 votes]: There's generalization for undirected graphs
http://en.wikipedia.org/wiki/Handshaking_lemma
Here are few ways you can think about this or ways that can give you more insight.

If there are $n$ people. The first person makes $n - 1$ handshakes, the second $n - 2$ ... the last one $0$
so we have to calculate the sum $n + (n-1) + (n-2) + ... +0$ and well you know this sum.
Matrix representation by Adjacency matrix. In undirected graph the matrix has diagonal symmetry.
Proof at wiki article above.
Mathematical induction thinking. Like for example you construct the graph add one vertex (with only edges connecting vertices that are already) there at the time and see that invariant stated in handshaking lemma stays true.
Writing down some graphs and marking the two ends of each edge (like for example dashes or 1 symbols) can give you more intuition.
You can try to imagine graphs in 3D to give you more insight.
You can play in mind with some graphs and try to count edges.
Add new Guard vertex in the "middle" of the graph and then change every edge in a way that instead of edge (V1)(V2) I have two edges (V1)(Guard) (Guard)(V1) and also I mark these two edges like this

(V1)-V1-----V2-(G)-V1-----V2-(V2)

That way graph becomes planar (the edges doesn't cross) . And you kind of see the same graph structure + it is more clear that each original edge has two ends.

And of course the ways other people mentioned and well there are for sure many more.


TITLE: Is $\gcd(\gcd(a,b),\gcd(c,d)) = \gcd(\gcd(a,c),\gcd(b,d))$ another instance of GCD Associativity?
QUESTION [1 upvotes]: The question is as is in the title:

Is $\gcd\bigg(\gcd(a,b),\gcd(c,d)\bigg) = \gcd\bigg(\gcd(a,c),\gcd(b,d)\bigg)$ another instance of GCD Associativity?

I know that
$$\gcd\bigg(e,\gcd(f,g)\bigg)=\gcd\bigg(\gcd(e,f),g\bigg)=\gcd(e,f,g).$$
I was wondering whether this can be extended to
$$\gcd\bigg(\gcd(a,b),\gcd(c,d)\bigg) = \gcd\bigg(\gcd(a,c),\gcd(b,d)\bigg) = \gcd\bigg(\gcd(a,d),\gcd(b,c)\bigg) = \gcd(a, b, c, d)?$$
I tried checking this closely related question, but it appears that my inquiry is not covered there.

REPLY [0 votes]: All those forms are equal, and equal to $\,\gcd(a,b,c,d)\,$. This follows from piecing together the results quoted below, whose full proofs can be found at the respective links.

$\gcd(a,b)\,$ is commutative, by definition.

$\gcd\,$ is associative, in the sense that $\,\gcd\left(\gcd(a,b),c\right)=\gcd\left(a, \gcd(b,c)\right)\,$, proved for example under $\gcd(a,b,c)=\gcd(\gcd(a,b),c)\,$ [Associative Law for GCD, LCM].

Associativity amounts to being able to "drop the parentheses", proved under How does one actually show from associativity that one can drop parentheses?, and specifically for $\,\gcd\,$ under $\gcd(a_1,a_2,\ldots,a_n) = \gcd(\gcd(\gcd(a_1,a_2),a_3),\ldots.a_n)$ [gcd is associative].

This means the multi-variate $\,\gcd(a_1, a_2, \dots, a_n)\,$ is well-defined and invariant to permutations of variables, so $\gcd\bigg(\gcd(a,b),\gcd(c,d)\bigg)$ $=\gcd(a,b,c,d)$ $= \gcd\bigg(\gcd(a,c),\gcd(b,d)\bigg)=\dots$

[ EDIT ] $\;$ To emphasize the commutativity point in relation to this part of the question:

Is $\gcd\bigg(\gcd(a,b),\gcd(c,d)\bigg) = \gcd\bigg(\gcd(a,c),\gcd(b,d)\bigg)$ another instance of GCD Associativity?

The equality does hold true, indeed, but only because $\,\gcd\,$ is commutative in addition to being associative. If, for example, $\,a,b,c,d\,$ were square matrices of the same size, instead, and $\,\gcd\,$ were replaced with matrix multiplication, the equality $\,(a \cdot b) \cdot (c \cdot d) = (a \cdot c) \cdot (b \cdot d)\,$ would not hold true in general, because matrix multiplication is associative, but is not commutative.

REPLY [0 votes]: One way to define the $\gcd$ is to consider subgroups of $\mathbb Z$. Indeed such a subgroup is of the form $a\mathbb Z$ for some $a\ge0$.
Then the $\gcd$ of $a$ and $b$ is defined to be the unique positive integer satisfying
$$a\mathbb Z + b\mathbb Z = \gcd(a,b)\mathbb Z\,.$$
Since addition is associative and commutative, so is the $\gcd$. Specifically, your examples give
$$\begin{align}(a\mathbb Z + b\mathbb Z) + (c\mathbb Z + d\mathbb Z)
&= (a\mathbb Z + c\mathbb Z)+(b\mathbb Z + d\mathbb Z) \\
&= (a\mathbb Z + d\mathbb Z)+(b\mathbb Z + c\mathbb Z) \\
&= a\mathbb Z + b\mathbb Z+c\mathbb Z + d\mathbb Z\,.\end{align}$$


TITLE: Lie algebra of the bounded continuous functions
QUESTION [0 upvotes]: I can think of the set of bounded, continuous functions from $\mathbb R \to \mathbb R$ as a group, with composition as addition of functions.  In other words, this group has the rule that the composition of two elements in the group, $f(x)$ and $g(x)$, is their point-wise sum $f(x) + g(x)$. Since this set is path connected, the group is continuous, i.e. it is a lie group.
What is the lie algebra of this group?
I am trying to use this approach to find a relationship between Lie theory and Fourier series, but I realize this might not work.  So I have decided to just ask the question in this form.  If anyone knows of any connections between Lie theory and Fourier series however, I am interested to hear about that.
(I realize I may have made some wrong/poorly stated assertions, please point these out in comments)

REPLY [3 votes]: Since your Lie group is infinite dimensional, one has to be careful about what exactly you mean by Lie algebra, and so on.
In any case, your «Lie group of bounded continuous functions $\mathbb R\to\mathbb R$ under composition» is not really a group... You'd have to restrict your attention to the group of homeomorphisms (or something along that line) to actually get a group.
The last sentence of your first paragraph is a bit misguided. You could do much worse that read Warner's book, say, on differentiable manifolds and lie groups, or Lang's, if you like infinite dimensional situations.


TITLE: Why do metals conduct electricity faster than heat?
QUESTION [8 upvotes]: I have read this question:
https://physics.stackexchange.com/a/561125/132371
where cuevobat says:

You will note if you examine the tables on conductors that some metals that are good electrical conductors also conduct heat well for the same reason - heat is also a vibration of electrons and depends on free electrons to easily transmit heat.

This says that (the conduction of) both heat and electricity depend on free electrons.
But we know that metals conduct electricity close to the speed of light.
Now if I have a metal wire, and heat one end of the wire (various ways, for example put it into hot water), the other end will heat up very slowly. Yet if you connect one end of the wire to electricity (outlet), electricity will flow through it and reach the other end (if you connect something to it, like you touch it) with speeds close to the speed of light.
What causes this difference between the speeds of the propagation of those two phenomena (electricity and heat) in metals?
Just to clarify, both depend on free electrons, so why don't both propagate at comparable speeds?
So far, I have two very interesting answers, and we got so far to the point where I see that in the case of:

electricity, the electrons "push" each other, and this transfer of momentum propagates close to the speed of light

heat, the electrons transfer energy (hot electrons colliding with cold electrons), and this is much slower

So now basically, the question comes down to why is transfer of momentum faster then transfer of energy between the free electrons?
Question:

Why do metals conduct electricity faster than heat?

REPLY [7 votes]: In the case of heat transfer, the wire stays electrically neutral, so one electron can only interact with other electrons in it's close vicinity by collisions, but has no effect on electrons far away. So the signal about the increased temperature (i.e. higher thermal velocity) travels by collisions from one electron to the next. In the best case scenario the random collsions happen such that the next electron always travels in the right direction. Then the information about the increased temperature can travel at most with a speed equivalent to the electrons thermal velocity, which is about 100 km/s or 0.3% of the speed of light.
In the case of electricity, you push additional electrons in one side of the wire. This charge surplus will cause an electric field to form which travels at the speed of light. So this electric field can almost instantaneously affect all electrons in the wire, even electrons far away on the other end of the wire. All electrons will start moving in the same direction driven by this electric field.
So in short, heat transfer is analogous to sending a message through a relay race, while electricity transfer is equivalent to cheating in that race by calling the person on the end of the line with your phone and telling him the message.


TITLE: Non atomic ring example
QUESTION [1 upvotes]: Can someone provide me with an example of a ring that is not atomic, that is, there is an element that has no finite factorization in irreducibles?

REPLY [1 votes]: Let $R = \mathbb Q[ x, x^\frac12,x^\frac 1 3\ldots ]$, the ring of polynomials with fractional exponents. Now try factoring $x$ which is not a unit in $R$ because it’s inverse would have to have an exponent of negative degree.


text:
\begin{document}

\begin{abstract}
  A simply connected topological space $X$ has homotopy Lie algebra $\pi_*(\lX) \tensor \Q$. Following Quillen, there is a connected differential graded free Lie algebra (dgL) called a Lie model, which determines the rational homotopy type of $X$, and whose homology is isomorphic to the homotopy Lie algebra. We show that such a Lie model can be replaced with one that has a special property we call \emph{separated}. The homology of a separated dgL has a particular form which lends itself to calculations.

\end{abstract}

\maketitle

\section{Introduction}

All of our topological spaces are assumed to be simply connected, and have finite rational homology in each dimension. For such a space $X$, there exists a differential graded Lie algebra $(\freeL V,d)$, where $\freeL V$ denotes the free graded Lie algebra on the rational vector space $V$, called a \emph{Lie model}, which determines the rational homotopy type of $X$, and whose homology is isomorphic to $\pi_*(\lX) \tensor \Q$, the \emph{(rational) homotopy Lie algebra} of $X$. While this description is pleasing in principle, it is less satisfying when explicit calculations are desired. Here, we want to put a certain structure on a Lie model that will prove conducive to calculation.

Assume that our Lie algebras are finite in each dimension and concentrated in positive dimension. Our assumption on our spaces implies that their Lie models satisfy this assumption. We are particularly interested in dgLs where $V$ can be bigraded as follows: $V_* = \oplus_{i=1}^N V_{i,*}$, such that
\begin{equation} \label{eq:condL}
dV_{i,*} \subset \freeL (\oplus_{j=1}^{i-1} V_{j,*}).
\end{equation}
We will call the first gradation \emph{degree} and the second, usual gradation \emph{dimension}.

Our \emph{separated} condition will say that the attaching map from degree $i+1$ has no effect on the homology coming from degree $\leq i-1$. We need to introduce some notation to make this precise.

Given a Lie algebra $L = (\freeL V,d)$ as above, let
\begin{equation} \label{eq:Li}
L_i = (\freeL V_{\leq i,*}, d).
\end{equation}
Let $ZL_i$ and $BL_i$ denote the cycles and boundaries in $L_i$. There is an induced map
\begin{equation} \label{eq:tilded}
\tilde{d}_i : V_{i,*} \xto{d} Z(L_{i-1}) \onto HL_{i-1}.
\end{equation}
The inclusion $L_i \incl L_{i+1}$ induces inclusions $BL_i \incl
BL_{i+1}$ and $ZL_i \incl ZL_{i+1}$.
Thus there is an induced map $HL_i \to HL_{i+1}$.

We introduce some notation for two Lie subalgebras of $HL_i$ to which we will often refer. Let $HL_i^-$ be the Lie subalgebra of $HL_i$
given by $\im (HL_{i-1} \to HL_i)$, and let $HL_i^+$ be the Lie ideal generated by $\im(\tilde{d}_{i+1}: V_{i+1,*} \to HL_i)$.

\begin{defn} \label{def:separated}
Let $L$ be a dgL satisfying~\eqref{eq:condL}. Say that $L$ is \emph{separated} if for all $i$,
\[ HL_i^+ \cap HL_i^- = 0. \]
\end{defn}

Let $(\freeL W,d)$ and $(\freeL W',d')$ be two dgLs satisfying~\eqref{eq:condL}.
Say that $(\freeL W', d')$ is a bigraded extension of $(\freeL W,d)$ if $W' = W \oplus \bar{W}$ as bigraded $R$-modules and $d'\!\mid_W = d$.

\begin{theorem} \label{thm:sep}
  Let $L$ be a dgL satisfying~\eqref{eq:condL}. Then $L$ has a bigraded extension $L'$ such that $L'$ is separated and the inclusion $L \injects L'$ induces an isomorphism on homology.
\end{theorem}

\begin{corollary}
  Let $X$ be a simply connected space with finite rational homology in each dimension and finite (rational) LS category. Then $X$ has a separated Lie model.
\end{corollary}

Define
\begin{equation} \label{eq:eLi}
  \eL_i = (HL_{i-1} \amalg \freeL V_{i,*}, \tilde{d}_i),
\end{equation}
where $L \amalg L'$ denotes the free product of Lie algebras (i.e., their coproduct), $\tilde{d}_i|_{HL_{i-1}}=0$ and $\tilde{d}_i|_{V_{i,*}}$ is given in \eqref{eq:tilded}.

\begin{theorem} \label{thm:HLvs}
Let $L = (\freeL V,d)$ be a separated dgL. Let
\begin{equation*}
\hat{L}_i = \freeL((H\eL_i)_{1,*})/[\tilde{d}_{i+1}V_{i+1,*}].
\end{equation*}
Then $HL \isom \bigoplus_i \hat{L}_i$ as $\Q$-modules.
In particular, if $L$ is a Lie model for a space $X$, then its homotopy Lie algebra has the form $\pi_*(\lX) \tensor \Q \isom \oplus_i \hat{L}_i$ as rational vector spaces.
\end{theorem}

To state a more precise version of this theorem, which elucidates some of the Lie algebra structure, we need to define some more notation.

Given an increasing filtration $\ldots \subset F_{i-1}M \subset F_iM
\subset F_{i+1}M \subset \ldots$ of an $R$-module $M$, there is an
associated graded $R$-module $\gr(M) = \bigoplus_i \gr_i M$ where
$\gr_i M = F_iM / F_{i-1}M$.
If $M$ has the structure of an algebra or Lie algebra, then there is
an induced algebra or Lie algebra structure on $\gr(M)$.
If $M$ has a separate grading, then $\gr(M)$ is bigraded.
If $M$ has a differential $d$ and $dF_iM \subset F_{i-1}M$ then the filtration is called a differential filtration and there is an induced filtration on $H(M,d)$.

Recall the definition of $L_i$ and $\tilde{d}_{i+1}$ from \eqref{eq:Li} and \eqref{eq:tilded}.
There is an increasing differential filtration $\{F_k L_i\}$ on $L_i = (\freeL(V_{\leq i}), d) \isom (\freeL V_{<i} \amalg \freeL V_i, d)$ given by $F_{-1}L_i = 0$, $F_0L_i = \freeL V_{<i}$, and for $k\geq 0$, $F_{k+1} L_i = F_k L_i + [F_k L_i, V_i]$.  This induces a filtration on $HL_i$ and $HL_i/[\tilde{d}V_{i+1}]$, where we write $L/[V]$ to denote the quotient of $L$ by the Lie ideal generated by $V \subset L$. When we write $\gr(HL_i)$ and $\gr(HL_i/[\tilde{d}V_{i+1}])$ we will always be using this filtration.

There is a short exact sequence $0 \to I \xto{i} L \xto{p} A \to 0$ of Lie algebras that splits (that is, there is a Lie algebra map $j:A \to L$ such that $pj = \id_A$) if and only if $L$ is the semi-direct product of $I$ and $A$, written $L \isom A \rsdp I$. The semi-direct product is isomorphic as modules to $A \oplus I$ and the product of elements in $A$ and $I$ is given by the action of $A$ on $I$. We will show the following.

\begin{theorem} \label{thm:sepThen}
Let $L = (\freeL V, d)$ be a free dgL over $\Q$ which is separated.
Let $L_i$, $\tilde{d}_i$, $\eL_i$, $HL_i^-$ and $HL_i^+$ be as in \eqref{eq:Li}, \eqref{eq:tilded}, \eqref{eq:eLi} and just before Definition~\ref{def:separated}.
Then for all $i$, there are Lie algebra isomorphisms
\begin{gather*}
\gr(HL_i) \isom (H\eL_i)_0 \rsdp \freeL ((H\eL_i)_1), \quad
\gr(HL_{i+1}^-) \isom HL_i^- \rsdp \hat{L}_i,\\
(H\eL_i)_0 \isom HL_{i-1} / [\tilde{d}_iV_{i}] = HL_{i-1}/HL_{i-1}^+ \isom HL_i^-,
\end{gather*}
where $\hat{L}_i = \freeL((H\eL_i)_1)/[\tilde{d}_{i+1}V_{i+1}] = \freeL((H\eL_i)_1)/HL_i^+$, and $HL_i^-$ is a Lie subalgebra of $HL$.
Furthermore, if we can choose a preimage $W_i \subset HL_i$ of $(H\eL_i)_1$ such that $\freeL W_i \subset HL_i$ is a Lie ideal, then $HL_i \isom HL_i^- \rsdp \freeL W_i$.
\end{theorem}

Let $*=X_0 \subset X_1 \subset \ldots \subset X_{n-1} \subset X_n = X$
be a spherical cone decomposition (see
Section~\ref{section:background}) corresponding to a separated Lie
model of $X$. In particular $X = X_{n-1} \cup_f (\bigvee_j D^{n_j+1})$
for some map $f$ from a wedge of spheres. The separated condition
implies that $f$ is \emph{free}~\cite{bubenik:freeAndSemiInert}. Let
$L_{X_i}$ denote the homotopy Lie algebra of $X_i$. Let
$i$ denote the inclusion $X_{n-1} \incl X$. Then there is an induced
map $i_{\#}: L_{X_{n-1}} \to L_X$. In general, this map is neither
injective nor surjective~\cite{halperinLemaireInert}. Let $R(L_X)$ denote the
\emph{radical} of $L_X$. That is, the sum of the solvable ideals of
$L_X$~\cite{fhjlt:radical}.

\begin{corollary}
  Either,
  \begin{enumerate}
  \item \label{cora} $i_{\#}: L_{X_{n-1}} \to L_X$ is surjective,
  \item \label{corb} $\dim(H\eL_n)_1 = 1$, or
  \item \label{corc} $R(L_X) \subset \im(i_{\#})$ and $L_X$ contains
    a free Lie algebra on two generators.
  \end{enumerate}
\end{corollary}

\begin{rem}
  \begin{enumerate}
  \item An equivalent condition to (\ref{cora}) is the condition that $f$ is
    \emph{inert}~\cite{halperinLemaireInert}.
  \item The only example of (\ref{corb}) seems to be $\CP^n$ (see
    Example~\ref{example:cpn}).
  \item It is known that $\dim R(L_X)_{\text{even}} \leq
    n$~\cite{fhjlt:radical}. The Avramov-F{\'e}lix
    conjecture~\cite{avramovFreeLieSubalgebras,fhtCat2} states that
    either $L_X$ is finite dimensional, or $L_X$ contains a free Lie
    algebra on two generators.
  \end{enumerate}
\end{rem}

\begin{proof}
  Applying Theorem~\ref{thm:sepThen}, $\gr(L_X) \isom \im(i_{\#}) \rsdp
  \freeL ((H\eL_n)_1)$. The result follows.
\end{proof}

\begin{example} \label{example:cpn}
We show how the well-known homotopy Lie algebras of $\CP^n$ and $\CP^{\infty}$ can be easily calculated using separated Lie models.

$\CP^{\infty}$ has the Lie model $L = (\freeL \langle v_1, v_2, v_3, \ldots \rangle,d)$ where $v_k$ has dimension $2k-1$ and $dv_k = \frac{1}{2} \sum_{i+j=k}[v_i,v_j]$. The Lie subalgebra $L_i = (\freeL \langle v_1, \ldots, v_n \rangle, d)$ is a Lie model for $\CP^n$.
Then $L_1 = (\freeL \langle v_1 \rangle, 0) = \eL_1$ and $L_2 = (\freeL \langle v_1, v_2 \rangle, d) = \eL_2$ where $dv_2 = \frac{1}{2} [v_1,v_1]$. We remark that for any dgL, $L_2$ is always separated, since $HL_1^- = 0$ and with respect to $L_2$ (not $L$), $HL_2^+ = 0$.
Now $(H\eL_2)_{0,*} = \freeL\langle v_1 \rangle / [v_1, v_1] \isom \hat{L}_1$ and $(H\eL_2)_{1,*} \isom \Q \{ u_2 \}$ where $u_2 = [v_1, v_2]$. By Theorem~\ref{thm:sepThen}, the Lie algebra structure of $HL_2$ is determined by the action of $(H\eL_2)_0$ on $\freeL ((H\eL_2)_{1,*})$ in $H\eL_2$. Since $d[v_2,v_2] = [v_1,[v_1,v_2]]$ in $L_2$, $[v_1,u_2]=0$ in $H\eL_2$. So as Lie algebras, $HL_2 \isom \freeLab \langle v_1, u_2 \rangle$, where $\freeLab$ denotes the free abelian Lie algebra.

Next we will show by induction that $L_n$ is separated, as Lie algebras, $HL_n \isom \freeLab \langle v_1, u_n \rangle$, where $u_n$ has dimension $2n$, and $HL_n^- = \freeLab \langle v_1 \rangle$. By definition $\eL_n \isom (\freeLab \langle v_1, u_{n-1} \rangle \ \amalg \ \freeL \langle v_n \rangle, \tilde{d}_n)$ where $\tilde{d}_n v_1 = \tilde{d}_n u_{n-1} = 0$ and $\tilde{d}_n v_n = u_{n-1}$. So $HL_{n-1}^- \cap HL_{n-1}^+ = \freeLab \langle v_1 \rangle \cap \freeL \langle u_{n-1} \rangle = 0$. Since $(H\eL_n)_0 \isom \freeLab \langle v_1 \rangle$, $(H\eL)_1 \isom \Q \{ [v_1, v_n] \}$ and $[v_1,[v_1,v_n]=0$ by the Jacobi identity, the claim follows.

Finally, this implies that $HL \isom \freeLab \langle v_1 \rangle$.
\end{example}

\begin{example} \label{example:productOfSpheres}
  In the next example we show that the Lie model obtained from the minimal spherical cone decomposition of a product of spheres is separated, and use this to calculate the homotopy Lie algebra for the wedges of spheres of various ``thickness''.

Let $X = \prod_{i=1}^r S^{n_i}$, where $n_i \geq 2$. Let $N = \dim X = \sum_{i=1}^r n_i$.

Let $X_k$ denote the subcomplex of $X$ consisting of

those points in $X$ such that at least $r-k$ of the coordinates are the basepoint.  In particular, $X_1$ is the wedge, and $X_{r-1}$ is the fat wedge. Also, $X_{k+1}$ can be obtained from $X_k$ by attaching a wedge of spheres.
Then,
\begin{equation} \label{eq:prodSpheres}
* = X_0 \subset X_1 \subset  \ldots \subset X_r =X
\end{equation}
is a spherical cone decomposition for $X$. (It is minimal, since the cone length of $X$ is bounded below by the rational LS category of $X$, which is $r$.) In addition, $X_k$ has a
Lie model $L_k = \left( \freeL \left< \oplus_{i=1}^k V_i \right>,
  d\right)$, where $V_i = \Q \{ \alpha_{i,j}\}$ with the
$\alpha_{i,j}$ in one-to-one correspondence with the $i$-fold products
of the spheres $S^{n_{\ell}}$ and the dimension of $\alpha_{i,j}$,
$|\alpha_{i,j}|$, is one less than the dimension of the corresponding
product, and $dV_i \subset \freeL \left< \oplus_{j=1}^{i-1} V_j \right>$.
Let $L_{X_k}$ denote the homotopy Lie algebra of $X_k$. Then $HL_k
\isom L_{X_k}$ and $HUL_k \isom UHL_k \isom UL_{X_k}$ where $U$
denotes the universal enveloping algebra functor.

For a non-negatively graded $\Q$-vector space $M$, let $M(z)$ be the
formal power series $\sum_{i\geq 0} (\dim M_i) z^i$. $M(z)$ is called
the Hilbert series for $M$, and $H_*(\Omega X;\Q)(z) = (UL_X)(z)$ is
called the Poincar\'{e} series for $\Omega X$.  Let $M(z)^{-1}$ denote the
power series $\frac{1}{M(z)}$. Define $A_i(z)$ by
\begin{equation*}
\prod_{i=1}^r \left(1-z^{n_i-1}x\right) = \sum_{i=0}^r A_i(z)x^i.
\end{equation*}
Let $A(z) = \prod_{i=1}^r ( 1-z^{n_i-1}) = \sum_{i=0}^r A_i(z)$, and finally define $B_k(z) = (-z)^{k-1} \sum_{i=k+1}^r A_i(z)$.

\begin{theorem} \label{thm:prodSpheres}
  As Lie algebras, $L_{X_1} \isom \freeL \langle x_1, \ldots, x_r \rangle$, where $|x_i| = n_i-1$, $L_{X} \isom \oplus_{i=1}^r \freeL \langle x_i \rangle$ and for $r\geq 3$, $L_{X_{r-1}} \isom L_X \amalg \freeL \langle u \rangle$ where $|u| = N-2$. Furthermore, for $k\geq 2$, $UL_{X_k}(z)^{-1} = A(z) - B_k(z)$.
\end{theorem}

\begin{proof}
  The first two Lie algebra isomorphisms in the statement of the
  theorem follow directly from the well-known formulas for the
  homotopy Lie algebra of a wedge and a product.

  The remainder of the statement of the theorem is obtained
  inductively.  We assume that $k\geq 2$.  Notice that the inclusion
  $X_1 \incl X$ induces a surjection $L_{X_1} \onto L_X$. So, $L_X
  \isom HL_2^- \incl HL_k^-$. Assume that $L_k$ is separated, which is
  trivial for $k=2$. Then using Theorem~\ref{thm:sepThen} one can show
  that in fact, $HL_k^- \isom L_X$. Thus $HL_k^- \incl L_X$ and hence
  $HL_k^- \cap HL_k^+ = 0$.  Therefore $L_{k+1}$ is separated. Thus,
  the minimal cone decomposition~\eqref{eq:prodSpheres} yields a
  separated Lie model for $X$.

  For $k\geq 2$, the Poincar\'{e} series for $\Omega X_k$ is obtained as
  follows. By Theorem~\ref{thmSepThenStrFree} and \cite[Lemma 3.8 and
  Theorem 3.5]{bubenik:freeAndSemiInert}) we can apply Anick's
  formula~\cite[Theorem 3.7]{anickthesis},

  \begin{equation*}
\begin{split}
  (UL_{X_k})(z)^{-1} &= (U(H\eL_k)_0)(z)^{-1} - [ V_{k+1}(z) +  z[(UL_{X_{k-1}})(z)^{-1} - \\ & \quad (U(H\eL_k)_0)(z)^{-1}]]\\
  &= A(z) + (-z)^{k-1}A_k(z) - z[(UL_{X_{k-1}})(z)^{-1} - A(z)],
\end{split}
\end{equation*}
where the second equality is by Theorem~\ref{thm:sepThen} and since $(UL_X)(z)^{-1} = A(z)$. By
induction, this is equal to $A(z) - B_k(z)$.

The Lie algebra isomorphism for $L_{X_{r-1}}$ follows since the cell
attachment from $X_{r-2}$ to $X_{r-1}$ is
semi-inert~\cite{bubenik:freeAndSemiInert}.
\end{proof}
We remark that the fact that the top-cell attachment of $X$ is
inert~\cite{halperinLemaireInert} is witnessed by $\eL_r =
(L_X \amalg \freeL \langle u,v \rangle, d)$, where $d|_{L_X} = 0$ and
$dv=u$.

  From Theorem~\ref{thm:prodSpheres} it is easy to check that a fat wedge of odd-dimensional spheres has the maximum possible gap in the rational homotopy groups~\cite[Theorem 33.3]{fht:rht} if and only if all the spheres have the same dimension.
\end{example}

\begin{example} \label{example:connectedSum}
  For the final example, we calculate the homotopy Lie algebra of a
  connected sum of products of spheres. For example, a Lie group $M$
  is rationally equivalent to a product of odd spheres (and so $L_M$ is a
  free abelian Lie algebra).

  For $s\geq 2$ and $1\leq i\leq s$, let $M_i$ be simply-connected, of
  dimension $N$ and rationally equivalent to a product of at least
  three spheres (e.g. $SU(n)$, $n\geq 4$).  Let $X = \#_{i=1}^s M_i$.
  Applying the previous example gives:
\begin{theorem}
  As Lie algebras,
\[
L_X \isom \coprod_{i=1}^s L_{M_i} \amalg \freeL \langle u_1, \ldots u_s \rangle / (u_1 + \ldots + u_s),
\]
where $|u_i| = N-2$.
\end{theorem}

\begin{proof}
  By the previous example $M_i$ has a separated Lie model of the form
  $(L_{(i)} \amalg \freeL\langle v_i \rangle, d)$ such that $\eL_{r_i}
  = (L_{M_i}, 0) \amalg (\freeL \langle u_i, v_i \rangle, \tilde{d})$
  with $\tilde{d} v_i = u_i$. Thus $X$ has a separated Lie model
  $(\coprod_{i=1}^s L_{(i)} \amalg \freeL \langle v \rangle, d)$ and
  $\eL_r = (\coprod_{i=1}^s L_{M_i}, 0) \amalg (\freeL \langle u_1,
  \ldots u_s, v \rangle , \tilde{d}v = u_1 + \ldots + u_s)$, where
  $r=\max_i r_i$.
\end{proof}

In particular, $L_X$ contains a free Lie algebra on $2s-1$ generators.
So $X$ satisfies the Avramov--F{\'e}lix
conjecture.
\end{example}

In the appendix we state and prove a generalization of the Schreier property of free Lie algebras: that any Lie subalgebra is also free, which may be of independent interest. This generalization is used in the proof of Theorem~\ref{thm:sepThen}.

\subsection{Acknowledgments}

{I would like to thank Kathryn Hess for many helpful discussions and Greg Lupton and John Oprea for help in rewriting the introduction and suggesting Examples \ref{example:productOfSpheres} and \ref{example:connectedSum}.}

\section{Background} \label{section:background}

In their landmark papers \cite{quillen:rht, sullivan:infinitesimalComputationsInTopology}, Quillen and Sullivan construct algebraic models for rational homotopy theory.  Sullivan constructs a contravariant functor $A_{PL}$ which serves as a fundamental bridge between topology and algebra. For a space $X$, $A_{PL}(X)$ is a commutative cochain algebra which has the property that $H(A_{PL}(X)) \isom H^*(X;\Q)$ as algebras. Quillen gives a construction for a differential graded Lie algebra (dgL) $(\freeL V, d)$, where $\freeL V$ denotes the free Lie algebra on a rational vector space $V$, one of whose properties is that $H(\freeL V,d) \isom \pi_*(\lX) \tensor \Q$. We will follow convention and call this a free dgL even though it is almost always not a free object in the category of \emph{differential} graded Lie algebras.
For an excellent reference on these models and their applications, the reader is referred to~\cite[Parts II and IV]{fht:rht}.

A \emph{quasi-isomorphism} is a morphism which induces an isomorphism in homology.
A \emph{Lie model} for a space $X$ is a differential graded Lie algebra $(L,d)$  equipped with a quasi-isomorphism $m: C^*(L,d) \qi A_{PL}(X)$. Here, $C^*(L,d) = \Hom(C_*(L,d),\Q)$, is the contravariant functor induced by Quillen's functor $C_*$. $C_*(L,d)$ is called the Cartan-Eilenberg-Chevalley construction on $(L,d)$. Quillen's free dgL above is a Lie model. Given a Lie model $(L,d)$ for a space $X$ and a quasi-isomorphism $(L,d) \qi (L',d')$, their is an induced quasi-isomorphism $C^*(L',d') \qi C^*(L,d) \qi A_{PL}(X)$. In particular, a quasi-isomorphic bigraded extension of a Lie model for $X$ is also a Lie model for $X$.

It is the Samelson product on $\pi_*(\lX)$, which corresponds the the Whitehead product under the canonical isomorphism $\pi_*(\lX) \isom \pi_{*+1}(X)$, which gives it the structure of a graded Lie algebra, which we call the \emph{(rational) homotopy Lie algebra}.

A \emph{rational homotopy equivalence} is a continuous map $f:X \to Y$ such that $\pi_*(f) \tensor \Q$ is an isomorphism. Two spaces $X$ and $Y$ are said to have the same \emph{rational homotopy type}, written $X \rht Y$, if they are connected by a sequence of rational homotopy equivalences (in either direction). The \emph{Lusternik Schnirelmann (LS) category} of a space $X$, denoted $\cat(X)$, is the smallest integer $n$ such that $X$ is the union of $n+1$ open subsets, each contractible in $X$. The \emph{rational LS category} of a space $X$, denoted $\catQ(X)$, is the smallest integer $n$ such that there exists a space $Y$ with $\cat(Y) = n$ and $X \rht Y$. So $\catQ(X) \leq \cat(X)$.
A space $X_n$ is said to be a \emph{spherical $n$-cone} if there exists a
sequence of spaces
\begin{equation} \label{eqnXN}
* = X_0 \subset X_1 \subset \ldots \subset X_n
\end{equation}
such that for $k=0\ldots n-1$, $X_{k+1} = X_k \cup_{f_{k+1}} \left( \bigvee_j D_{j,k}^{n_{j}+1} \right)$, where $D^n$ denotes the $n$-dimensional disk and $f_{k+1}:\bigvee_j S^{n_j}_{j,k} \to X_k$ is an attaching map.
A space $X$ is said to have \emph{rational cone length} $n$, written
$\clQ(X) = n$, if $n$ is the smallest number such that $X \rht X_n$
for some spherical $n$-cone $X_n$.
(This is equivalent to the more usual definition of rational cone length, see~\cite[Proposition 28.3]{fht:rht}, for example.)
It is a theorem of Cornea~\cite{cornea:coneLengthAndLScat} that if $\catQ(X) = n$ then $\clQ(X) = n$ or $n+1$.
A CW complex is said to have finite type if it has finitely many cells in each dimension.

A free dgL $(\freeL V,d)$ is said to have \emph{length} $N$ if we can decompose $V_* = \oplus_{i=1}^N V_{i,*}$ such that $dV_{i,*} \subset \freeL (\oplus_{j=1}^{i-1} V_{j,*})$, where $dV_{1,*}=0$. Note that $V$ is now bigraded, though $(\freeL V,d)$ is typically not a bigraded dgL. We will call the first gradation \emph{degree} and the second, usual gradation \emph{dimension}.
For any free dgL $(\freeL V,d)$ of length $N$ there is a spherical $N$-cone $X$ such that $(\freeL V, d)$ is a Quillen model for $X$. We call $(\freeL V,d)$ the cellular Lie model of $X$. Furthermore, any spherical $N$-cone has a cellular Lie model of length $N$. We outline the construction as follows.
For each $n \geq 1$ let the $(n+1)$-cells $D^{n+1}_{\alpha}$ of $X$ correspond to a basis $\{v_{\alpha}\}$ of $V_n$. Let $X_n$ denote the $n$-skeleton of $X$. By induction, $(\freeL V_{<n}, d)$ is a cellular Lie model of $X_n$. The attaching maps $f_{\alpha}: S^n \to X_n$ are given by representatives of $[dv_{\alpha}] \in H_{n-1}(\freeL V_{<n}, d) \isom \pi_{n-1}(\lX_n) \isom \pi_{n}(X_n)$.

A dgL is said to be of \emph{finite type} if it is finite in each dimension. It is said to be \emph{connected} if it is concentrated in strictly positive dimensions. Given two (Lie) algebras $L$ and $L'$, let $L \amalg L'$ denote their free product (i.e., coproduct). We remark that $\freeL V \amalg \freeL V' \isom \freeL (V \oplus V')$.

\section{Replacing dgLs with separated dgLs}

To prove Theorem~\ref{thm:sep}, we will need the following lemmas. Let $\kk$ be a field of characteristic $0$.

\begin{lemma}
Let $W$ be a free $\kk$-module and let $\alpha,\beta \in (\freeL W, d)$
with $d\beta = \alpha$.
Let $W' = W \oplus \kk\{a,b\}$ where $|a|=|\beta|$ and $|b|=|\beta|+1$.
Define $(\freeL W', d')$ by letting $d'$ be an extension of $d$
determined by taking $d'a = \alpha$ and $d'b= a - \beta$.
Then the inclusion $(\freeL W, d) \injects (\freeL W', d')$ is a quasi-isomorphism.
\end{lemma}

\begin{proof}
Consider the following commutative diagram.
\begin{equation*}
  \xymatrix{ (\freeL W, d) \ar[rr]^{\phi} \ar[dr]^{\psi} & & (\freeL (W \oplus     \kk\{a,b\}), d') \\
    & (\freeL (W \oplus \kk\{\hat{a},\hat{b}\}),\hat{d}) \ar[ur]^{\theta} &
  }
\end{equation*}
where $\hat{d}\hat{b} = \hat{a}$, $\phi$ and $\psi$ are injections and $\theta$ is defined on generators as follows: $\theta|_W = \id_W$, $\theta \hat{a} = a-\beta$, and $\theta \hat{b} = b$.
It is easy to check that $\theta$ is a chain map and a dgL isomorphism. Furthermore,
\[
(\freeL (W \oplus \kk\{\hat{a},\hat{b}\}),\hat{d}) \isom
(\freeL W, d) \amalg (\freeL<\hat{a},\hat{b}>,\hat{d}) \simeq (\freeL W, d).
\]
Thus $\psi$ is a quasi-isomorphism. It follows that $\phi$ is one as well.
\end{proof}

\begin{corollary} \label{corExtension}
Let $L = (\freeL W, d)$ with $\{\alpha_j, \beta_j\}_{j \in J} \subset
\freeL W$ where $d\alpha_j = 0$ and $d\beta_j=\alpha_j$.
Taking $\bar{W} = \kk\{a_j, b_j\}_{j \in J}$ with $|a_j| = |\beta_j|$ and
$|b_j| = |\beta_j|+1$,
let $L' = \freeL(W \oplus \bar{W}, d')$ where $d'|_W = d$, $d'a_j =
\alpha_j$, and $d'b_j = a_j - \beta_j$.
Then $L' \simeq L$.
\end{corollary}

Given an $\kk$-module $M$, let $ZM$, $BM$ denote the $\kk$-submodules of
cycles and boundaries.

\begin{lemma} \label{lemmaNAttach}
Let $L = (\freeL W,d)$ and let $V = \{v_j\}_{j \in J} \subset HL_{n}$
with $v_j \neq 0$.
For each $v_j$ choose a representative cycle $\hat{v}_j \in ZL$.
Let $L' = (\freeL W',d')$ where $W' = W \oplus \kk\{a_j,b_j\}_{j \in
J}$, $d'\!\mid_W = d$, $da_j = \hat{v}_j$ and $b_j$ is in dimension $n+2$.
Then $H_{\leq n}L' \isom H_{\leq n}L/V$.
\end{lemma}

\begin{proof}
Since $Z_{\leq n}L' = Z_{\leq n}L$ and $B_{\leq n}L' \isom
B_{\leq n}L \oplus \kk\{da_j\}_{j \in J}$, $H_{\leq n}L' \isom
H_{\leq n}L / V$.
\end{proof}

\begin{lemma} \label{lemmaVS}
Given $\kk$-modules $C \subset A \subset B$ and $D \subset B$, let $p: B
\to B/C$ denote the quotient map.
If $D \cap A \subseteq C$ then $pD \cap pA = 0$.
\end{lemma}

\begin{proof}
Let $x \in pD \cap pA$.
Then there are $y \in D$, and $y' \in A$ such that $py = py' = x$.
Let $z = y - y'$.
Since $pz = 0$, $z \in C \subset A$.
Thus $y = y' + z \in A \cap D \subseteq C$.
Therefore $x = py = 0$.
\end{proof}

The proof of theorem~\ref{thm:sep} will rely on a two-step inductive
procedure given in Proposition~\ref{propSeparated}.
To help with the book-keeping, we introduce the following definitions.
We will use the notation $HL_i^+$ and $HL_i^-$ defined just before Definition~\ref{def:separated}.

\begin{defn}
  Let $(\freeL W, d)$ be a dgL satisfying~\eqref{eq:condL}.  Say that $(\freeL W, d)$ is \emph{$k$-separated} if for all $i<k, \ HL_i^+ \cap HL_i^- =   0$.  Say $(\freeL W, d)$ is \emph{$(k,n)$-separated} if it is $k$-separated and   $H_{<n}L_k^+ \cap H_{<n}L_k^- = 0$.
\end{defn}

Let $\delta_{i,j} = 1$ if $i=j$ and let it be $0$ otherwise.
Let $s$ denote the suspension homomorphism.
That is, $(sM)_k = M_{k-1}$.

\begin{lemma} \label{lemmaSeparated}
Let $L = (\freeL W, d)$ be a dgL of length $N$ that is $(k,n)$-separated.
Let $V$ be the component of $HL_k^+ \cap HL_k^-$ in dimension $n$.

Then there exists a bigraded extension $\hat{L} = (\freeL \hat{W},
\hat{d}) \supset L$ of length $N+\delta_{k+2,N+1}$ with
$\hat{W}_i = W_i$ for $i \neq k, k+2$,
$\hat{W}_k = W_k \oplus \bar{W}$,
$\hat{W}_{k+2} = W_{k+2} \oplus s\bar{W}$,
where $\bar{W}$ is in dimension $n+1$,
such that $L' \simeq L$.
Furthermore
$H_{\leq n}\hat{L}_k \isom H_{ \leq n}L_k / V$, and
\begin{equation} \label{eqnLv0}
H_{\leq n}\hat{L}_k^+ \cap H_{\leq n}\hat{L}_k^- = 0.
\end{equation}
\end{lemma}

\begin{proof}
Let $\{\alpha_j\}_{j \in J}$ be a basis (as an $\kk$-module) for $V$.
Since $\alpha_j \in HL_k^-$, $\alpha_j$ has a preimage
$\alpha'_j \in HL_{k-1}$.
Let $\alpha''_j$ be a representative cycle in $L_{k-1}$ for
$\alpha'_j$.
Since $\alpha_j \in HL_k^+$, there is a $\beta_j \in
L_{k+1}$ such that $d\beta_j = \alpha''_j$.
Let $\{a_j, b_j \}_{j \in J}$ be pairs of elements of bidegree $(k,n+1)$ and
$(k+2,n+2)$ respectively.
Define $\hat{L} = (\freeL \hat{W}, \hat{d}) \supset L$ by letting
$\hat{W}_i = W_i$ for $i \neq k, k+2$, $\hat{W}_k = W_k \oplus
\kk\{a_j\}$ and $\hat{W}_{k+2} = W_{k+2} \oplus \kk\{b_j\}$.
Extend $d$ to $\hat{d}$ by letting $da_j = \alpha''_j$ and $db_j = a_j -
\beta_j$.
Note that $\hat{L}$ has length $N+\delta_{k+2,N+1}$.
By Corollary~\ref{corExtension}, $\hat{L} \simeq L$.

By Lemma~\ref{lemmaNAttach},
\begin{equation} \label{eqnLxn}
(H_{\leq n}\hat{L}_k) \isom (H_{\leq n}L_k) / V.
\end{equation}
In other words, in dimensions $\leq n$ the map from $HL_k$ to
$H\hat{L}_k$ is just the quotient by $V$.
Thus, $H_{\leq n}\hat{L}_k^+ \isom H_{\leq n}L_k^+ / V$, and $H_{\leq n}\hat{L}_k^- \isom H_{\leq n}L_k^- / V$.
Applying Lemma~\ref{lemmaVS} to
$V \subset H_{\leq n}L_k^- \subset H_{\leq n}L_k$
and $H_{\leq n}L_k^+ \subset H_{\leq n}L_k$, one gets that $H_{\leq n}L_k^+ / V \cap H_{\leq n}L_k^- / V = 0$.
\end{proof}

\begin{defn}
Say that a bigraded $\kk$-module $M$ is in the \emph{$(k,n)$-region} if
$W_{*,\leq n} = W_{\geq k+3, *} = W_{k+1, n+1} = W_{k+2,n+1} = 0$.
Let $L = (\freeL W, d)$ be a free dgL.
Say that $L' = (\freeL W',d')$ is a \emph{$(k,n)$-extension} of $L$ if
$W' = W \oplus \bar{W}$ as bigraded modules, where $\bar{W}$ is in the $(k,n)$-region, and $d'|_W = d$.
\end{defn}

\begin{prop} \label{propSeparated}
Let $L = (\freeL W, d)$ of length $N$ that is $(k,n)$-separated.
Let $V$ be the component of
$HL_k^+ \cap HL_k^-$ in dimension $n$.

(a) Then there is an $(k,n)$-extension of $L$,
$L' = (\freeL W',d')$ of length $N+\delta_{k+2,N+1}$ which is
$(k,n+1)$-separated, such that $L' \simeq L$.
Furthermore $H_{\leq n}L'_k \isom H_{\leq n}L_k / V$.

(b) In addition there an $(k,n)$-extension of $L$,
$L'' = (\freeL W'', d'')$ of length $N+\delta_{k+2,N+1}$ which is
$(k+1)$-separated, such that $L'' \simeq L$.
Furthermore $H_{\leq n}L''_k \isom H_{\leq n}L_k / V$, and if
$H_{\leq n}L_{k+1}^+ \cap H_{\leq n}L_{k+1}^- = 0$ then
$H_{\leq n}{L''}_{k+1}^+ \cap H_{\leq n}{L''}_{k+1}^- = 0$.
\end{prop}

\begin{rem}
Recall that $d(W_{k+1}) \subset \freeL(W_{\leq k})$ and that
$HL_k^+$ is the ideal generated by the
images of $W_{k+1}$ by the induced map $W_{k+1} \to HL_k$.
All of the elements in this ideal have preimages in $\freeL (W_{\leq k})$.
$V$ consists of those dimension $n$ elements in this ideal which have
preimages in lower filtration.
\end{rem}

\begin{proof}
We prove the proposition by induction on $k$.
The statement of the proposition is trivial if $k=0$.
We will assume the statement of the proposition is true for $k-1$.

Let $L$, $V$ be as in the statement of the proposition.
By Lemma~\ref{lemmaSeparated}, there exists $\hat{L} = (\freeL \hat{W},
\hat{d}) \supset L$ of length $N+\delta_{k+2,N+1}$ with
$\hat{W}_i = W_i$ for $i \neq k, k+2$,
$\hat{W}_k = W_k \oplus \bar{W}$,
$\hat{W}_{k+2} = W_{k+2} \oplus s\bar{W}$,
where $\bar{W}$ is in dimension $n+1$,
such that $L' \simeq L$.
Furthermore
$H_{\leq n}\hat{L}_k \isom H_{\leq n}L_k / V$, and
\begin{equation} \label{eqnZeroInHat}
H_{\leq n}\hat{L}_k^+ \cap H_{\leq n}\hat{L}_k^- = 0.
\end{equation}

Since $\hat{L}_{k-1} = L_{k-1}$ and $L$ is $k$-separated, $\hat{L}$ is
(at least) $(k-1)$-separated.
Also $H\hat{L}_{k-2} = HL_{k-2}$ and $H\hat{L}_{k-1} = HL_{k-1}$.

Let $\hat{\mathcal L} = H\hat{L}_{k-1}^+ \cap H\hat{L}_{k-1}^-$. Since $L$ is $k$-separated, this equals $[\hat{d} \bar{W}] \cap HL_{k-1}^-$.
Since $\bar{W}$ is $n$-connected, $\mathcal{\hat{L}}$ is
$(n-1)$-connected, but it is not necessarily $n$-connected.
In the non-trivial case, there are elements of $V$ which not only have
preimages in filtration $k-1$ but also have preimages in filtration
$k-2$.
Let $\hat{V} = \mathcal{\hat{L}}_n$.

By induction there exists a $(k-1,n)$-extension $L' = (\freeL V',
d') \supset \hat{L}$ of length $N + \delta_{k+2,N+1}$ that is
$k$-separated such that $L' \simeq \hat{L}$,
and since $H_{\leq n}\hat{L}_k^+ \cap H_{\leq n}\hat{L}_k^- = 0$,
$H_{\leq n}{L'}_k^+ \cap H_{\leq n}{L'}_k^- = 0$.
So $L'$ is a $(k,n)$-extension of $L$ such that $L' \simeq L$.
Furthermore $H_{\leq n}L'_{k+1} \isom H_{\leq n}\hat{L}_{k+1} /
\hat{V} = H_{\leq n}L_{k-1} / \hat{V}$.
This proves part (a) of the statement.

To prove part (b) of the statement we simply iterate part (a).
By iterating (a) we get a sequence of dgLs
\[ L = L^{(0)} \subset L^{(1)} \subset \ldots \subset L^{(i)} \subset
L^{(i+1)} \subset \ldots
\]
where $L^{(i)}$ is $(k,n+i)$-separated,
$L^{(i+1)}$ is a $(k,n+i)$-extension of $L^{(i)}$,
and $L^{(i+1)} \simeq L^{(i)}$.
Furthermore, $H_{\leq n}L^{(i)}_k \isom H_{\leq n}L_k / V$, and if
$H_{\leq n}L_{k+1}^+ \cap H_{\leq n}L_{k+1}^- = 0$ then $H_{\leq n}{L^{(i)}}_{k+1}^+ \cap H_{\leq n}{L^{(i)}}_{k+1}^- = 0$.
Let $L'' = \cup_i L^{(i)}$.
Then $L''$ is a $(k+1)$-separated $(k,n)$-extension of $L$ and $L'' \simeq L$.
Furthermore, $H_{\leq n}L^{(i)}_k \isom H_{\leq n}L_k / V$, and if
$H_{\leq n}L_{k+1}^+ \cap H_{\leq n}L_{k+1}^- = 0$ then $H_{\leq n}{L''}_{k+1}^+ \cap H_{\leq n}{L''}_{k+1}^- = 0$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:sep}]
Since any dgL is $1$-separated,
Theorem~\ref{thm:sep} follows by applying
Proposition~\ref{propSeparated}, $N$ times.
\end{proof}

\section{Properties of separated dgLs}

In this section we will use Theorems \ref{thm:sep} and
\ref{thmSchreier} to prove Theorem~\ref{thm:sepThen}.
We will defer to the appendix the proof of Theorem \ref{thmSchreier}, which is a generalization the well-known result that a Lie subalgebra of a free Lie algebra is also a free Lie algebra. We will use \eqref{eq:Li}, \eqref{eq:tilded}, \eqref{eq:eLi}, and the notation $HL_i^+$ and $HL_i^-$ defined just before Definition~\ref{def:separated}.

\begin{defn}
Let $(\freeL W,d)$ be a free dgL over a field.
Say that $(\freeL W,d)$ is \emph{strongly free} if for all $i$,
$HL_i^+ \subset L_{M_i}$ is a free Lie subalgebra.
\end{defn}

\begin{theorem} \label{thmSepThenStrFree}
Let $L$ be a free dgL over $\Q$ which is separated.
Then $L$ is strongly free and for all $i$, there are Lie algebra isomorphisms
\begin{equation*}
\gr(HL_i) \isom (H\eL_i)_0 \rsdp \freeL ((H\eL_i)_1) \text{, and }
(H\eL_i)_0 \isom HL_{i-1} / [\tilde{d}W_{i}] \isom HL_i^-.
\end{equation*}
\end{theorem}

We will prove Theorem~\ref{thmSepThenStrFree} by induction.
A main part of the induction will use the following theorem, which is
a special case of the main algebraic result from~\cite{bubenik:freeAndSemiInert}.
Note that $U$ denotes the universal enveloping algebra functor.

\begin{theorem}[{\cite[Theorem 3.12]{bubenik:freeAndSemiInert}}] \label{thmHUL}
Over the field $\Q$, let $L' = (L \amalg \freeL V_1, d)$, where $dL \subset L$, $dV_1 \subset L$ and $HUL \isom UL_0$, such that there is an induced map
$d':V_1 \to L_0$.
Let $\eL = (L_0 \amalg \freeL V_1, d')$.
If $[d'V_1] \subset L_0$ is a free Lie algebra,
then as algebras
\[
\gr(HUL') \isom UH\eL \text{, and }
H\eL \isom (H\eL)_0 \rsdp \freeL (H\eL)_1 \text{ and } (H\eL)_0 \isom L_0/[d' V_1]
\]
as Lie algebras.
\end{theorem}
The associated graded structure on $HUL'$ is that induced from the filtration on $L'$ given by $F_{-1}L'=0$, $F_0L' = L$ and $F_{i+1}L' = F_iL' + [V_1,F_iL']$.

\begin{proof}[Proof of Theorem~\ref{thmSepThenStrFree}]
Let $L = (\freeL W, d)$ be a free dgL over $\Q$ which is separated.
Recall that $\tilde{d}_i: W_i \to HL_{i-1}$ and $\eL_i =
(HL_{i-1} \amalg \freeL W_i, \tilde{d}_i)$.

Assume that $L_{i}$ is strongly free, $\gr(HL_i) \isom (H\eL_i)_0 \rsdp
\freeL ((H\eL_i)_1)$, and $(H\eL_i)_0 \isom HL_{i-1} / [\tilde{d}W_i]
\isom HL_i^-$.
This is trivial for $i \leq 1$.

Note that $L_{i+1} = (L_i \amalg \freeL W_{i+1}, d)$.
Both $L_{i+1}$ and $UL_{i+1}$
can be filtered by the `length in $W_{i+1}$' filtration.
That is, let $F_{-1}(L_{i+1}) = 0$, $F_0 L_{i+1} = L_i$, and for
$i\geq 0$, $F_{i+1}(L_{i+1}) = F_i(L_{i+1}) + [F_i(L_{i+1}), W_{i+1}]$.
This induces a similar filtration on $UL_{i+1}$.

By assumption, $\gr(HL_i) \isom HL_i^- \rsdp \freeL ((H\eL_i)_1)$.
Since $L_{i+1}$ is separated, $HL_i^+ \cap
HL_i^- = 0$.
Thus by Theorem~\ref{thmSchreier}, $HL_i^+$ is a free Lie
algebra.
Hence $L_{i+1}$ is strongly free.

Then by Theorem~\ref{thmHUL}, as algebras
\begin{gather*}
\gr(HUL_{i+1}) \isom U \left( (H\eL_{i+1})_0 \rsdp \freeL ((H\eL_{i+1})_1) \right) \text{, and }\\
(H\eL_{i+1})_0 \isom HL_i / [\tilde{d}_{i+1} W_{i+1}].
\end{gather*}

It is a result of Quillen's that $HUL_{i+1} \isom UHL_{i+1}$.
Thus $\gr(HUL_{i+1}) \isom \gr(UHL_{i+1}) \isom U\gr(HL_{i+1})$.
From this it follows that $U\gr(HL_{i+1}) \isom U\left( (H\eL_{i+1})_0 \rsdp \freeL
((H\eL_{i+1})_1) \right)$.

For any Lie algebra $L$, $UL$ has a canonical cocommutative Hopf
algebra structure.
Let $P$ denote the primitive functor.
Over $\Q$, the composition $PU$ is the identity
functor~\cite{milnorMooreHopfAlgebras}.
Therefore $\gr(HL_{i+1}) \isom (H\eL_{i+1})_0 \rsdp \freeL
((H\eL_{i+1})_1)$.

It follows that $HL_{i+1}^- \isom (H\eL_{i+1})_0$.
This finishes the inductive step.
\end{proof}

We will now use Theorem \ref{thmSepThenStrFree} to prove Theorem~\ref{thm:sepThen}.

\begin{proof}[Proof of Theorem~\ref{thm:sepThen}]
Let $L=(\freeL V,d)$ that is separated.
Recall that $L_i = \freeL (V_{\leq i, *})$,
$\tilde{d}:V_i \xto{d} ZL_{i-1} \onto HL_{i-1}$, and $\eL_i =
(HL_i \amalg \freeL V_i, \tilde{d})$.

Let $N_i = (H\eL_i)_1$ and recall that $HL_i$ is filtered by the length in $V_i$ filtration.  By Theorem~\ref{thmSepThenStrFree}, $(\freeL V,d)$ is strongly free and for all $i$, it satisfies $\gr(HL_i) \isom HL_i^- \rsdp \freeL N_i$ where $HL_i^- \isom HL_{i-1} / {[\tilde{d}_iV_i]}$.

Also by Theorem~\ref{thmSepThenStrFree}, $HL_{i+1}^- \isom
HL_i / [\tilde{d}_{i+1}V_{i+1}]$,
which has a filtration induced by the filtration on $HL_i$.
Thus we have the following short exact sequence of filtered,
graded Lie algebras:

\[
0 \to [\tilde{d}_{i+1}V_{i+1}] \to HL_i \to HL_{i+1}^- \to 0,
\]
which induces a short exact sequence of bigraded Lie algebras:
\[
0 \to \gr( [\tilde{d}_{i+1}V_{i+1}] ) \to \gr(HL_i) \to \gr(
HL_{i+1}^- ) \to 0.
\]
Recall that
$\gr(HL_i) \isom HL_i^- \rsdp \freeL N_i$.

Since $(\freeL V,d)$ is separated, it follows that $[\tilde{d}_{i+1}V_{i+1}] \cap HL_i^- =
0$, and thus $\gr([\tilde{d}_{i+1}V_{i+1}]) \subset \freeL N_i$ as Lie algebras.
Since any Lie subalgebra of a free Lie algebra is automatically free,
$\gr([\tilde{d}_{i+1}V_{i+1}]) \isom \freeL K_{i+1}$ for some $\Q$-module
$K_{i+1} \subset \freeL N_i$.
Therefore $\gr(HL_{i+1}^-) \isom HL_i^- \rsdp (\freeL
N_i / \freeL K_{i+1})$ as Lie algebras.

Let $\hat{L}_i = \freeL N_i / \freeL K_{i+1}$.

By Theorem~\ref{thmSepThenStrFree} there is a split short exact sequence of Lie algebras
\[
0 \to \freeL ((H\eL_i)_1) \to \gr(HL_i) \to HL_i^- \to 0
\]
Let $W_i$ be a preimage of $(H\eL_i)_1$ in $HL_i$.
We have a short exact sequence of modules
\[
0 \to \freeL W_i \to HL_i \to HL_i^- \to 0
\]
but this is not necessarily a short exact sequence of Lie algebra since $\freeL W_i$ may not be a Lie ideal. Equivalently, the projection $HL_i \to HL_i^-$ may not be a Lie algebra morphism.
However, if $\freeL W_i$ is a Lie ideal in $HL_i$ then $HL_i \isom HL_i^- \rsdp \freeL W_i$.
\end{proof}

\appendix

\section{A generalized Schreier property}

In this chapter we give a simple criterion which we prove guarantees
that certain Lie subalgebras are free.

It is a well-known fact that any (graded) Lie subalgebra of a (graded)
Lie algebra is a free Lie algebra
\cite{mikhalevSubalgebras, shirshovSubalgebras, mikhalevZolotykh}
This is often referred to as the \emph{Schreier property}.
In this chapter we generalize this result to the following.

\begin{theorem} \label{thmSchreier}
Over a field $\F$, let $L$ be a finite-type graded Lie algebra with filtration
$\{F_k L\}$ such that $\gr(L) \isom L_0 \rsdp \freeL V_1$ as Lie
algebras, where $L_0 = F_0 L$ and $V_1  = F_1 L / F_0 L$.
Let $J \subset L$ be a Lie subalgebra such that $J \cap F_0 L = 0$.
Then $J$ is a free Lie algebra.
\end{theorem}

Before proving this theorem,  we prove the following lemma.

\begin{lemma} \label{lemmaSchreier}
Let $J$ be a finite-type filtered Lie algebra such that $\gr(J)$ is a
free Lie algebra.
Then $J$ is a free Lie algebra.
\end{lemma}

\begin{proof}
By assumption there is an $\F$-module $\bar{W}$ such that $\gr(J)
\isom \freeL \bar{W}$.

Let $\{\bar{w}_i\}_{i \in I} \subset \gr(J)$ be an $\F$-module basis
for $\bar{W}$.
Let $m_i = \deg(\bar{w}_i)$.
That is, $\bar{w}_i \in F_{m_i}J / F_{m_i-1} L$.
For each $\bar{w}_i$ choose a representative $w_i \in F_{m_i} J$.
Let $W = \F\{w_i\}_{i \in I} \subset J$.

Then there is a canonical map $\phi: \freeL W \to J$.
Grade $\freeL W$ by letting $w_i \in W$ be in degree $m_i$.
Then $\phi$ is a map of filtered objects and there is an induced map
$\theta: \freeL W \to \gr(J)$.
However the composite map
\[ \freeL W \xto{\theta} \gr(J) \isomto \freeL \bar{W}
\]
is just the canonical isomorphism $\freeL W \isomto \freeL \bar{W}$.
So $\theta$ is an isomorphism.
Therefore $\phi$ is an isomorphism and $J$ is a free Lie algebra.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thmSchreier}]
The filtration on $L$ filters $J$ by letting
\[ F_k J = J \cap F_k L.
\]
From this definition it follows that the inclusion $J \incl L$ induces
an inclusion $\gr(J) \incl \gr(L)$.

So $\gr(J) \incl \gr(L) \isom L_0 \rsdp \freeL V_1$.
Since $J \cap F_0 L = 0$ it follows that $(\gr J)_0 = 0$ and $\gr(J)
\incl (\gr J)_{\geq 1} \isom \freeL V_1$.
By the Schreier property $\gr(J)$ is a free Lie algebra.
Thus by Lemma~\ref{lemmaSchreier}, $J$ is a free Lie algebra.
\end{proof}

The following corollary is a special case of this theorem.

\begin{corollary} \label{corSchreier}
Over a field $\F$, if $J \subset L_0 \rsdp \freeL (L_1)$ is a Lie
subalgebra such that $J \cap L_0 = 0$ then $J$ is a free Lie algebra.\
\end{corollary}

Note that since $J$ is not necessarily homogeneous with respect to
degree $J \cap L_0 = 0$ does not imply that $J \subset \freeL L_1$.

\newcommand{\etalchar}[1]{$^{#1}$}

config: arxiv


TITLE: Prove that $ n^3 + 5n$ is divisible by 6 for all $n\in \textbf{N}$
QUESTION [1 upvotes]: Prove that $ n^3 + 5n  $ is divisible by 6 for all $ n \in \textbf{N} $.  I provide my proof below.

REPLY [7 votes]: Hint $\displaystyle \ \ n^3\!+5n = n^3\!-\!n+6n = (n\!+\!1)n(n\!-\!1) + 6n = \color{#c00}6{ {n\!+\!1\choose 3}} + \color{#c00}6n\ $ is divisible by $\,\color{#c00}6$
Alternatively show $\,(n\!+\!1)n(n\!-\!1)\,$ is divisible by both $2$ and $3$. Generally a sequence of $\,k\,$ consecutive integers contains a multiple of $\,k\,$ (pigeonholes being remainders mod $\,k).$
More generally $\ 2p\mid n^p-n\ $ for odd primes $p,\,$ since $\ p\mid n^p-n\ $ by little Fermat, and it's divisible by $2$ since $\,n^p$ and $\,n\,$ have equal parity. Even more generally
Theorem $ $ (Korselt's Pseudoprime Criterion) $\ $ For  $\rm\:1 < e,m\in \Bbb N\:$ we have
$$\rm \forall\, n\in\Bbb Z\!:\ m\mid n^e\!-n\ \iff\  m\ \ is\ \  squarefree,\ \  and \ \ p\!-\!1\mid e\!-\!1\ \, for\  all \ primes\ \ p\mid m$$
For a proof see this answer. Your case is $\,\rm\,e,m = 3,6\,$ and, indeed, $2\!-\!1,\,3\!-\!1\mid 3\!-\!1.$


TITLE: Partitions of ℤ/18ℤ
QUESTION [2 upvotes]: I want to partition $ℤ/18ℤ$ into ${0}$, units, irreducibles and reducibles.
I think the units are $1, 5, 7, 11, 13$ and $17$ but not sure if this is even right.

REPLY [1 votes]: You got the units right; now, all the numbers 4,8,16 are reducible since they are powers of 2, which is not a unit, furthermore $2 = 2 \cdot 10$ where neither 2 or 10 are units, hence 2 is reducible too, while $9=3\cdot 3$ and $6=2 \cdot 3$. It remains to check the nature of 3,10,14,15. $14 = 2 \cdot 16$, now, since 3 divides 18, we have that if $3 = a \cdot b$ we can suppose $a =3$, then check by multiplying 3 with all the non-units you can check that this is not possible, therefore 3 is irreducible. In a similar way 15 is seen to be irreducible. At last, $10 = 2 \cdot 14$.


TITLE: Why is $ \sum_{n=0}^{\infty}\frac{x^n}{n!} = e^x$?
QUESTION [8 upvotes]: I am trying to see where this relationship comes from: $\displaystyle \sum_{n=0}^{\infty}\frac{x^n}{n!} = e^x$ Does anyone have any special knowledge that me and my summer math teacher doesn't know about? He went over generating functions a few days ago and I did not know exactly what he was talking about. In the middle of his lecture he wrote this generating function. He explained that in this case $a_{n} = \frac{1}{n!}$ for $\displaystyle \sum_{n=0}^{\infty} a_{n} x^n$.
Is the relationship a definition or can it be derived using $\displaystyle \sum_{n=0}^{\infty} x^n $?

REPLY [4 votes]: Another approach: I imagine you know that
$$\lim_{n \to \infty} (1+x/n)^n = e^x.$$
Expanding by the binomial theorem,
$$(1+x/n)^n = 1+n \frac{x}{n} + \frac{n(n-1)}{2} \frac{x^2}{n^2} + \frac{n(n-1)(n-2)}{3!} \frac{x^3}{n^3} + \cdots$$
$$=1+x+(1-1/n) \frac{x^2}{2}+(1-1/n)(1-2/n) \frac{x^3}{3} + \cdots$$
As $n \to \infty$, the $k$th term goes to $x^k/k!$. One still has to do some work to turn this into a proof, as you can't just assume willy-nilly that the limit of an infinite sum will be the sum of the limits, but it is at least very suggestive, and can be made into a completely correct argument.


text:
\begin{document}

\title{Formulas for sums of powers of integers and their reciprocals}
\author{Levent Karg\i n\thanks{leventkargin48@gmail.com}, Ayhan
Dil\thanks{adil@akdeniz.edu.tr}, M\"{u}m\"{u}n Can\thanks{mcan@akdeniz.edu.tr}\\Department of Mathematics, Akdeniz University, Antalya, Turkey}
\date{}
\maketitle

\begin{abstract}
This paper gives new explicit formulas for sums of powers of integers and
their reciprocals.

\textbf{MSC:} Primary 11B83, Secondary 11B68; 11B73

\textbf{Keywords: }Faulhaber formula, generalized harmonic numbers,
poly-Bernoulli numbers.

\end{abstract}

\markright{Formulas for sums of powers}

\section{Introduction}

For an integer $p>0$, consider the following sum of powers of integers
\begin{equation}
\sum_{k=1}^{n}k^{p}=1^{p}+2^{p}+\cdots+n^{p}. \label{ps}
\end{equation}
These sums have been of interest to mathematicians since antiquity. Over the
years, mathematicians have given formulas for special values of $p$. Johann
Faulhaber (1580-1635) proved that the consecutive powers of integers can be
expressed as a polynomial in $n$ of degrees $\left(  p+1\right)  $ and gave a
calculation formula up to $p=17$. The general form was established with the
discovery of the Bernoulli numbers $B_{n}$ as:
\[
\sum_{k=1}^{n}k^{p}=\frac{1}{p+1}\sum_{k=0}^{p}\left(  -1\right)  ^{k}
\binom{p+1}{k}B_{k}n^{p+1-k}.
\]
After that this formula is named as Faulhaber's formula. More details about
this formula can be found in \cite{Knuth} and the references therein. In 1978,
Gould \cite{G} gave an explicit formula for this sum as
\[
\sum_{k=1}^{n}k^{p}=\sum_{j=0}^{p}j!

\genfrac{\{}{\}}{0pt}{}{p}{j}

\binom{n+1}{j+1}=\sum_{j=0}^{p}\left(  -1\right)  ^{p+j}j!

\genfrac{\{}{\}}{0pt}{}{p}{j}

\binom{n+j}{j}.
\]
Recently, Merca \cite{Merca} expressed this sum in terms of the Stirling
numbers of the first and second kind. In this manner from past to present,
studies are ongoing to give new calculation formulas and also new proofs for
known formulas of this type of sums.

Besides, the sum of reciprocals of powers of the first $n$ natural numbers
corresponds to
\begin{equation}
\sum_{k=1}^{n}\frac{1}{k^{p}}=1+\frac{1}{2^{p}}+\frac{1}{3^{p}}+\cdots
+\frac{1}{n^{p}},\text{ }p>0 \label{psr}
\end{equation}
which is also interesting and has a long history dating back to Leonard Euler.

In another context, the number formed by the sum of (\ref{ps}) and (\ref{psr})
together is called the $n$th generalized harmonic number and denoted by
$H_{n}^{\left(  p\right)  }$, namely
\begin{equation}
H_{n}^{\left(  p\right)  }=\sum_{k=1}^{n}k^{-p},\text{ }p\in\mathbb{Z}.
\label{ghn}
\end{equation}
As can be easily understood from (\ref{ghn}), the case $p<0$ reduces to
(\ref{ps}). When $p>1$ the number $H_{n}^{\left(  p\right)  }$ is the $n$th
partial sum of the famous Riemann zeta function. Its close relationship with
Riemann zeta function makes generalized harmonic numbers valuable in the field
of analytical number theory.

The case $p=1,$ $H_{n}^{\left(  1\right)  }=H_{n}$, is known as harmonic
number which occurs in fundamental equations in many areas from analysis to
discrete mathematics and computer science \cite{GKP,CG}. Harmonic numbers have
various relationships with both Bernoulli and Stirling numbers, we would like
to remind you one of them \cite[p. 424]{CSE}:
\begin{equation}
H_{n+1}=\frac{1}{n!}\sum_{k=0}^{n}\left(  -1\right)  ^{k}

\genfrac{[}{]}{0pt}{}{n+1}{k+1}

B_{k}, \label{2}
\end{equation}
where $

\genfrac{[}{]}{0pt}{}{n}{k}

$ denotes the Stirling numbers of the first kind, the number of permutations
of $n$ elements with $k$ disjoint cycles.

In this paper, two formulas are given for the sum of powers of positive
integers, and a formula for their reciprocals.

In the first result, we present a formula for the generalized harmonic
numbers. Special cases of which correspond to the sums (\ref{ps}) and
(\ref{psr}). Apart from this, it is a general form of (\ref{2}) and answers
the question of which type of Bernoulli numbers are related to the generalized
harmonic numbers.

\begin{theorem}
\label{teo1}For all integers $p$ and non-negative integers $n$, we have
\begin{equation}
H_{n+1}^{\left(  p\right)  }=\sum_{k=1}^{n+1}\frac{1}{k^{p}}=\frac{1}{n!}
\sum_{j=0}^{n}

\genfrac{[}{]}{0pt}{}{n+1}{j+1}

B_{j}^{\left(  p\right)  }. \label{hpb}
\end{equation}

\end{theorem}

Here, $B_{k}^{\left(  p\right)  }$ is the $k$th\ poly-Bernoulli number defined
by \cite[Eq. (1)]{Kaneko}
\begin{equation}
\sum_{k=1}^{\infty}B_{k}^{\left(  p\right)  }\frac{t^{k}}{k!}=\frac
{Li_{p}\left(  1-e^{-t}\right)  }{1-e^{-t}}, \label{pb}
\end{equation}
where $Li_{p}\left(  z\right)  $ is the polylogarithm and has the generating
function
\[
Li_{p}\left(  z\right)  =\sum_{k=1}^{\infty}\frac{z^{k}}{k^{p}}.
\]
The poly-Bernoulli numbers are a generalization of the classical Bernoulli
number with $B_{k}^{\left(  1\right)  }=\left(  -1\right)  ^{k}B_{k}.$ They
have interesting combinatorial interpretations, and also appear in special
values of certain zeta functions.

Now, we present formulas for the sum of powers of integers, first of which is
as a consequence of Theorem \ref{teo1}.

\begin{corollary}
\label{cor}For all non-negative integers $n$ and $p$, we have
\[
\sum_{k=1}^{n}k^{p}=\sum_{j=0}^{p}j!

\genfrac{\{}{\}}{0pt}{}{p+1}{j+1}

\binom{n}{j+1}.
\]

\end{corollary}

\begin{theorem}
\label{teo2}For all positive integers $n$ and $p,$ we have
\[
\sum_{k=1}^{n}k^{p}=\sum_{j=0}^{p}\left(  -1\right)  ^{p+j}j!

\genfrac{\{}{\}}{0pt}{}{p+1}{j+1}

\binom{n+j+1}{j+1}.
\]
\bigskip
\end{theorem}

Here, $

\genfrac{\{}{\}}{0pt}{}{n}{k}

$ is the Stirling numbers of the second kind, count the number of ways to
partition a set of $n$ objects into $k$ non-empty subsets.

\section{Proofs}

\subsection{Proof of Theorem \ref{teo1}}

Substituting $t\rightarrow1-e^{-t\text{ }}$ in the generating function of the
generalized harmonic numbers
\begin{equation}
\sum_{k=0}^{\infty}H_{k}^{\left(  p\right)  }t^{k}=\frac{Li_{p}\left(
t\right)  }{1-t},\text{ }\left\vert t\right\vert <1, \label{gfgh}
\end{equation}
one can easily obtain that
\[
\frac{Li_{p}\left(  1-e^{-t}\right)  }{1-e^{-t}}=\sum_{n=0}^{\infty}\left(
-1\right)  ^{n}H_{n+1}^{\left(  p\right)  }\left(  e^{-t}-1\right)  ^{n}
e^{-t}.
\]
We now utilize the following generating function of the second kind Stirling
numbers \cite[p. 351]{GKP}
\[
\sum_{k=n}^{\infty}

\genfrac{\{}{\}}{0pt}{}{k+1}{n+1}

\frac{z^{k}}{k!}=\frac{\left(  e^{z}-1\right)  ^{n}}{n!}e^{z},
\]
and deduce that
\[
\frac{Li_{p}\left(  1-e^{-t}\right)  }{1-e^{-t}}=\sum_{k=0}^{\infty}\left(
\sum_{n=0}^{k}\left(  -1\right)  ^{k-n}

\genfrac{\{}{\}}{0pt}{}{k+1}{n+1}

n!H_{n+1}^{\left(  p\right)  }\right)  \frac{t^{k}}{k!}.
\]
Considering (\ref{pb}) and equating coefficients of $t^{n}$ give
\[
B_{n}^{\left(  p\right)  }=\sum_{k=0}^{n}\left(  -1\right)  ^{n-k}

\genfrac{\{}{\}}{0pt}{}{n+1}{k+1}

k!H_{k+1}^{\left(  p\right)  }.
\]
Finally, taking $a_{n}=B_{n}^{\left(  p\right)  }$ and $b_{k}=k!H_{k+1}
^{\left(  p\right)  }$ in the well-known Stirling transform \cite[p.
310]{GKP}
\[
a_{n}=\sum_{k=0}^{n}\left(  -1\right)  ^{n-k}

\genfrac{\{}{\}}{0pt}{}{n+1}{k+1}

b_{k}\text{ if and only if }b_{n}=\sum_{k=0}^{n}

\genfrac{[}{]}{0pt}{}{n+1}{k+1}

a_{k}
\]
give the desired result.

\subsection{Proof of Corollary \ref{cor}}

Since $H_{n}^{\left(  -p\right)  }=\sum_{k=1}^{n}k^{p},$ take $-p$ ($p>0$) in
(\ref{hpb}) and then utilize the following identity of poly-Bernoulli numbers
\cite[Theorem 2]{AK}
\[
B_{k}^{\left(  -p\right)  }=\sum_{j=0}^{\min\left\{  k,p\right\}  }\left(
j!\right)  ^{2}

\genfrac{\{}{\}}{0pt}{}{p+1}{j+1}

\genfrac{\{}{\}}{0pt}{}{k+1}{j+1}

.
\]
We find that
\[
\sum_{k=1}^{n+1}k^{p}=\frac{1}{n!}\sum_{j=0}^{n}\left(  j!\right)  ^{2}

\genfrac{\{}{\}}{0pt}{}{p+1}{j+1}

\sum_{k=j}^{n}

\genfrac{[}{]}{0pt}{}{n+1}{k+1}

\genfrac{\{}{\}}{0pt}{}{k+1}{j+1}

.
\]
Hence, thanks to the identity \cite[Theorems 3.7 and 3.11]{NyRa}
\[
\sum_{k=j}^{n}

\genfrac{[}{]}{0pt}{}{n+1}{k+1}

\genfrac{\{}{\}}{0pt}{}{k+1}{j+1}

=\frac{n!}{j!}\binom{n+1}{j+1},
\]
the proof is completed.

\subsection{Proof of Theorem \ref{teo2}}

With the aid of $H_{n}^{\left(  -p\right)  }=\sum_{k=1}^{n}k^{p},$ $p>0,$ we
may consider (\ref{gfgh}) as
\[
\sum_{n=0}^{\infty}\left(  \sum_{k=1}^{n}k^{p}\right)  t^{n}=\frac
{Li_{-p}\left(  t\right)  }{\left(  1-t\right)  }
\]
and use \cite{W}
\[
Li_{-p}\left(  t\right)  =\left(  -1\right)  ^{p+1}\sum_{k=0}^{p}k!

\genfrac{\{}{\}}{0pt}{}{p+1}{k+1}

\left(  \frac{-1}{1-t}\right)  ^{k+1},\text{ }p\geq1
\]
to conclude that
\[
\sum_{n=0}^{\infty}\left(  \sum_{k=1}^{n}k^{p}\right)  t^{n}=\sum
_{n=0}^{\infty}\left(  \sum_{k=0}^{p}\left(  -1\right)  ^{p+k}k!

\genfrac{\{}{\}}{0pt}{}{p+1}{k+1}

\binom{k+1+n}{k+1}\right)  t^{n}
\]
which is what we wanted to prove.


TITLE: Problem on Poisson distribution: Probability that 5th call will arrive between 8:10 to 8:20 am
QUESTION [0 upvotes]: Calls arriving at a telephone exchange follow a Poisson distribution with an average of 3 calls every 10 minutes. If the telephone exchange opens at 8:00 am, what is the probability that the 5th call arrives between 8:10 am to 8:20 am?

Here I am creating two events:
Event A: Number of calls between 8:00 am to 8:20 am is $\geq 5$
Event B: Number of calls between 8:00 am to 8:10 am is $\leq 4$
Then the probability that the 5th call will arrive between 8:10 to 8:20 is $P(A \cap B)$.
Now I have found $P(A)=0.71494$ and $P(B)=0.81526$.
How do I find $P(A \cap B)$?

REPLY [1 votes]: It is easier to handle independent or mutually distinct events so you can multiply or add their probabilities.
Here you have three mutually distinct events, so you can use addition and subtraction

Number of calls between 8:00 am to 8:20 am is $\le 4$: this has probability $1- P(A)$ in your terms
Number of calls between 8:00 am to 8:10 am is $\ge 5$: this has probability $1- P(B)$ in your terms
Fifth call is between 8:10 am and 8:20 am: this has probability $1-(1- P(A))-(1- P(B)) = P(A)+ P(B)-1$ in your terms

In effect the argument is that $$P(A \cup B)= P(A)+P(B) -P(A \cap B)$$ so   $$P(A \cap B)= P(A)+P(B) -P(A \cup B)$$ $$P(A \cap B)= P(A)+P(B) -(1 - P(A^c \cap B^c))$$ and in this case $$P(A^c \cap B^c)=0$$