TITLE: Categorification of $\pi$?
QUESTION [24 upvotes]: Is there a categorification of $\pi$?
I have to admit that this is a very vague question. Somehow it is motivated by this recent MO question, which made me stare at some digits and somehow forgot my animosity about this branch of mathematics, wondering if there is a connection to the branches I love so much.
$\pi$ is the area of the unit circle, so perhaps we have to categorify the unit circle (using the projective line?) and the area of such an object. Areas are values of integrals, and there are some kind of integrals in category theory (ends), but this is really just a wild guess.
For some great examples of categorification see this list on MO, and for the meaning of categorification see this MO question or that article by Baez/Dolan. Inspired by the answers of Todd Trimble, we may consider a categorified sinus function
$$\sin(X) = \sum_{n \geq 0} (-1)^{\otimes n} X^{\otimes (2n+1)} / (2n+1)!$$
in any complete symmetric monoidal category (if we can make sense of $-1$).
Edit: Perhaps $(-1)$ should be the universal invertible object $\mathcal{L}$ such that the symmetry on $\mathcal{L} \otimes \mathcal{L}$ equals $-1$. In the theory of $k$-linear cocomplete symmetric monoidal categories, this is the category of super vector spaces over $k$, i.e. $\mathbb{Z}/2$-graded vector spaces, with a twisted symmetry. Here, $\mathcal{L}$ is $1$-dimensional concentrated in degree $1$. Thus, we have a sine function for super vector spaces, namely $\sin(V) = \oplus_{n \geq 0} \mathcal{L}^{\otimes n} \otimes V^{\otimes (2n+1)} / \Sigma_{2n+1}$. How does it look like, and can we extract something which resembles $\pi$?

REPLY [12 votes]: One approach to questions of this general nature is to find a groupoid whose groupoid cardinality is equal to the number in question; this is a form of groupoidification.  For example, the groupoid cardinality of the groupoid $\text{FinSet}_0$ of finite sets and bijections is $\sum \frac{1}{n!} = e$, so this is a reasonable categorification of $e$; in fact arguably this is "the" categorification of $e$ and goes a long way towards explaining its prevalence in mathematics.  Similarly, for any finite set $X$, the groupoid cardinality of the groupoid of $X$-colored finite sets and color-preserving bijections is $\sum \frac{|X|^n}{n!} = e^{|X|}$.  Note that this groupoid is the coproduct of $|X|$ copies of $\text{FinSet}_0$; see also this math.SE question.
In a TWF188 John Baez mentions that he looked into the problem of finding a "natural" groupoid whose cardinality is $\pi$, but that he (and possibly some collaborators) weren't able to come up with any nice examples.  So possibly this is the wrong direction to go in the particular case of $\pi$.


TITLE: Show $\int_0^1 \frac{\log(1-x)}{x}dx=-\frac{\pi^2}{6}$
QUESTION [3 upvotes]: It's claimed that $$\int_0^1 \frac{\log(1-x)}{x}dx=-\frac{\pi^2}{6}$$ by first expanding $\frac{\log(1-x)}{x}$ into a power series and then doing term-by-term integration. I want to justify this by Levi's Theorem for Series, that is, if $(f_n)$ is a sequence of $L^1$ functions such that $\sum_{n=0}^{\infty} \int_X \lvert f_n\rvert \,\text{d}\mu \lt \infty$. Then $\sum_{n=0}^{\infty} f_n$ converges a.e. to an $L^1$ function $f$ such that $$\int_X \sum_{j=1}^{\infty} f_k\text{d}\mu=\sum_{k=0}^{\infty}\int_Xf_k\,\text{d}\mu.$$ Note that we are focusing on Lebesgue integration, since the integrand is not defined at $x=0$ or $x=1$. I'm not sure how to show this, possibly by Taylor expansion? Could someone help to show to derive this? Thanks.

REPLY [2 votes]: A more intuitive explanation, and the way to actually derive this integral (something I tried messing around with a while back) is to try long division of $\frac{1}{1-y}$. The motivation for this is to attempt a new solution at the Basel problem.
$$\frac{1}{1-y} = 1 + y + y^2 + y^3 \dots$$
You get an infinite series of $1 + y + y^2 + y^3 \dots$ onto infinity. You integrate both sides to get $$-\ln(1-y) = y + \frac{y^2}{2} + \frac{y^3}{3} + \frac{y^4}{4}\dots \text{ on to infinity }$$
Because they are equivalent functions, the constants of integration ($C$) cancel out on both sides. You want the denominators of the right hand side to match the denominators of the series $\frac{1}{n^2}$, so that you can solve the Basel problem. So you divide both sides by $y$ and integrate once more from $0$ to $1$ to get the series $$\int_0^1\frac{-\ln(1-y)}{y}dy= 1 + 1/4 + 1/9 + 1/16\dots$$ You reverse the bounds of integration to account for the negative sign from earlier, and you get $$\int_1^0\frac{\ln(1-y)}{y}dy= 1 + 1/4 + 1/9 + 1/16\dots=\frac{\pi^2}{6}$$
The same integral with reversed bounds is the negative answer.
$$\int_0^1\frac{\ln(1-y)}{y}dy= -\frac{\pi^2}{6}$$


TITLE: Are the first $n$ digits of $\pi$ equal to the second $n$ digits for some $n\ge1$?
QUESTION [13 upvotes]: Are the first $n$ digits of $\pi$ equal to the second $n$ digits for some $n\ge1$?
$$\pi \stackrel{?}{=}\underbrace{3.1415926\ldots}_{\text{the first }n\text{ digits}}~\underbrace{31415926\ldots}_{\begin{array}{c}\text{the same }n\text{ digits}\\\text{in the same order}\end{array}}~\underbrace{\ldots\ldots\ldots}_{\text{more digits}}$$
If so, is the smallest such $n$ known?

REPLY [9 votes]: It is very unlikely.  If we take the digits of $\pi$ to be "random", the chance of a repeat after $n$ digits is $10^{-n}$.  We can exclude however many digits we know do not repeat.  Say we know it doesn't repeat by one million digits.  Then the chance we have a repeat is less than $$\sum_{i=10^6}^\infty 10^{-i}=\frac {10^{-10^6}}{1-.1}=\frac 1{9\cdot 10^{10^6-1}} $$ which is extremely small.


TITLE: Proof involving Poisson bracket
QUESTION [0 upvotes]: Not being able to understand how each term has been simplified to get from the third step to the fourth step. So how did 1/2m become 1/m and {qj,plpl}pk become {qj,pl}plpk and how did k/4 become k/2 and {pk,(qlql)^2}qj become {pk,(qlql)}(qmqm)qj.
Any help would be much appreciated.

REPLY [1 votes]: The third to fourth line is obtained via the product rule again applied to both pieces:
$$
 \frac{1}{2m} \epsilon_{ijk} \{ q_j, p_l p_l \} p_k
= \frac{1}{2m} \epsilon_{ijk} \{ q_j, p_l \} p_l p_k
+ \frac{1}{2m} \epsilon_{ijk} \{ q_j, p_l \} p_l p_k
= \frac{1}{m}\epsilon_{ijk}\{q_j, p_l \} p_l p_k
$$
Because both are the same statement it doesn't matter which $p_l$ is outside.
The second piece:
\begin{eqnarray*}
\frac{k}{4} \epsilon_{ijk} \{ p_k, (q_l q_l)^2 \} q_j
&=&\frac{k}{4} \epsilon_{ijk} \{ p_k, (q_l q_l)(q_m q_m) \} q_j \\
&=&\frac{k}{4}\left( \epsilon_{ijk} \{ p_k, (q_l q_l) \}(q_m q_m) q_j +
\epsilon_{ijk} \{ p_k, (q_m q_m) \}(q_l q_l) q_j
\right) \\
&=& \frac{k}{4}\left( \epsilon_{ijk} \{ p_k, (q_l q_l) \}(q_m q_m) q_j +
\epsilon_{ijk} \{ p_k, (q_l q_l) \}(q_m q_m) q_j
\right) \\
&=&\frac{k}{4}\left( 2\epsilon_{ijk} \{ p_k, (q_l q_l) \}(q_m q_m) q_j
\right) = \frac{k}{2}\epsilon_{ijk} \{ p_k, (q_l q_l) \}(q_m q_m) q_j
\end{eqnarray*}
This last part follows from the product rule and then the fact that the repeated indices are not unique, just switch the l and m indices with each other in the second sum because they are dummy indices.


TITLE: Is there a closed form for this infinite sum?
QUESTION [1 upvotes]: I am wondering is there a closed form for this infinite sum.
$$R(\beta)=\beta^2\sum_{k=1}^\infty \frac{\sin^2(\pi kn/\beta)}{(k^2-\beta^2)^2},$$
where $n\in\mathbb{N},\beta\in\mathbb{R}.$

REPLY [2 votes]: We may start with the expression obtained using Fourier series for $x\in(-\pi,\pi)$ and $z$ not a positive integer :
$$\tag{1}\cos(x\,z)=\frac{2\,z\sin(\pi z)}{\pi}\;\left(\frac 1{2z^2}-\sum_{k=1}^\infty \;(-1)^k\frac{\cos(k\,x)}{k^2-z^2}\right)$$
that I'll rewrite as :
$$\cos((\pi-a)z)=\frac{2\,z\sin(\pi z)}{\pi}\;\left(\frac 1{2z^2}-\sum_{k=1}^\infty \;(-1)^k\frac{\cos(k\,(\pi-a))}{k^2-z^2}\right)$$
or simply :
$$\tag{2}\frac{\pi}2\frac{\cos((\pi-a)z)}{z\;\sin(\pi z)}=\frac 1{2z^2}-\sum_{k=1}^\infty \;\frac{\cos(k\,a)}{k^2-z^2}$$
Since $\;\displaystyle\sin^2(x)=\frac {1-\cos(2x)}2\;$ and $\;\displaystyle \frac d{dz}\frac 1{k^2-z^2}=\frac {2z}{(k^2-z^2)^2}\;$ we deduce that for :
\begin{align}
R(a,b)&:=2\sum_{k=1}^\infty \frac{\sin^2(k\,a)}{(k^2-b^2)^2}\\
&=\sum_{k=1}^\infty \frac 1{(k^2-b^2)^2}-\sum_{k=1}^\infty \frac {\cos(k\,2a)}{(k^2-b^2)^2}\\
&=\frac 1{2b}\frac d{db}\left[\sum_{k=1}^\infty \frac 1{k^2-b^2}-\sum_{k=1}^\infty \frac {\cos(k\,2a)}{k^2-b^2}\right]\\
&=\frac{\pi}2\frac 1{2b}\frac d{db}\left[-\frac{\cos(\pi b)}{b\;\sin(\pi b)}+\frac{\cos((\pi-2a)b)}{b\;\sin(\pi b)}\right]\\
\end{align}
and thus the wished closed form for $b$ not a positive integer and $\,a\in(0,\pi)\,$ at least :
$$\sum_{k=1}^\infty \frac{\sin^2(k\,a)}{(k^2-b^2)^2}=\frac {\pi}{8\,b^3}\left[\cot(\pi b)+\pi b\csc^2(\pi b)-(1+\pi b\cot(\pi b))\csc(\pi b)\cos((\pi-2a)b)-\\(\pi-2a)b\,\csc(\pi b)\sin((\pi-2a)b)\right]$$
pari/gp scripts used for numerical confirmation :
r(a,b)=2*sumalt(k=0,sin(k*a)^2/(k^2-b^2)^2)
f(a,b)=Pi/(4*b^3)*(1/tan(Pi*b)+Pi*b/sin(Pi*b)^2-(1+Pi*b/tan(Pi*b))/sin(Pi*b)*cos((Pi-2*a)*b)-(Pi-2*a)*b/sin(Pi*b)*sin((Pi-2*a)*b))


text:
\begin{document}

\bibliographystyle{elsart-num-sort}
\title{The M\"{o}bius Function\\ of a\\ Restricted Composition Poset}

\author{Adam M. Goyt\footnote{This work was partially done while the author was visiting DIMACS.}\\ Department of Mathematics\\ Minnesota State University Moorhead\\ 1104 7th Avenue South\\ Moorhead, Minnesota 56563\\ goytadam@mnstate.edu\\www.mnstate.edu/goytadam}

\maketitle

\noindent Key Words: automaton, composition, generating function, M\"{o}bius function, shellability, subword order

\medskip

\noindent AMS classifications: 06A07, 68R15, 52B22

\begin{abstract}

We study a poset of compositions restricted by part size under a partial ordering introduced by Bj\"{o}rner and Stanley.  We show that our composition poset $C_{d+1}$ is isomorphic to the poset of words $A_d^*$.  This allows us to use techniques developed by Bj\"{o}rner to study the M\"{o}bius function of $C_{d+1}$.  We use counting arguments and shellability as avenues for proving that the M\"{o}bius function is $\mu(u,w)=(-1)^{|u|+|w|}{w\choose u}_{dn}$, where ${w\choose u}_{dn}$ is the number of $d$-normal embeddings of $u$ in $w$.  We then prove that the formal power series whose coefficients are given by the zeta and the M\"{o}bius functions are both rational.  Following in the footsteps of Bj\"{o}rner and Reutenauer and Bj\"{o}rner and Sagan, we rely on definitions to prove rationality in one case, and in another case we use finite-state automata.

\end{abstract}

\section{Introduction}

A composition $\alpha$ is an element $(\alpha_1,\alpha_2,\dots,\alpha_k)\in \mathbb{P}^k$, where $\mathbb{P}=\{1,2,3,\dots\}$ is the set of positive integers.  The {\it length} of a composition $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$ is $\ell(\alpha)=k$, and the {\it norm}, $|\alpha|=n$, is $n$ if $\sum_{i=1}^k\alpha_i=n$.  The $\alpha_i$ are called {\it parts}.  If $|\alpha|=n$, then we say that $\alpha$ is a composition of $n$.  Define $C_n$ to be the set of all compositions of $n$ and let $$C=\bigcup_n C_n.$$

We are interested in studying a particular partial ordering on a set of restricted compositions.  Before we define this set, let us briefly remind the reader of some basic terminology of partially ordered sets (posets).  A {\it poset} is a set $P$ with relation $\leq$, which is reflexive, antisymmetric, and transitive. A poset $P$ is finite (infinite), if $P$ is finite (infinite), and $P$ is {\it locally finite} if for any $x,z\in P$ the set $[x,z]=\{y:x\leq y\leq z\}$ is finite.  We call the set $[x,z]$ an {\it interval} of $P$.  A {\it subposet} of $P$ is a set $Q\subseteq P$ under the same partial ordering as $P$.  Finally, two posets $P$ and $Q$ are isomorphic if there is a bijection $\phi:P\rightarrow Q$ such that for $x,y\in P$, $x\leq y$ if and only if $\phi(x)\leq \phi(y)$.

The partial ordering on $C$ that we are interested in was introduced by Bj\"{o}rner and Stanley\footnote{Bj\"{o}rner and Stanley's paper, where they introduced this partial ordering, has since been withdrawn from the arXiv.} to produce a composition analogue of Young's Lattice.  For more information on Young's Lattice, we refer the reader to~\cite{RStanleyVol1,RStanleyVol2}.  To define the poset $C$ we need only define its covering relation $\alpha \covb \beta$.  In a poset an element $y$ {\it covers} an element $x$, $y\covr x$, if $y>x$ and there is no $z$ with $y>z>x$.  In $C$ we say that $\beta\covr\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$ if $\beta$ is of one of the two following forms:
\begin{eqnarray*}\beta&=&(\alpha_1,\alpha_2,\dots,\alpha_{i-1},\alpha_i+1,\alpha_{i+1},\dots,\alpha_k)\\
\beta&=&(\alpha_1,\alpha_2,\dots,\alpha_{i-1},\alpha_i+1-h,h,\alpha_{i+1},\dots,\alpha_k),\\
\end{eqnarray*} where $h\leq \alpha_i$.

We will consider the poset $C_d$, which is the subposet of $C$ consisting of compositions $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$ with $\alpha_i\leq d$ for $1\leq i\leq k$.  $C_d$ is the set of compositions, which have part sizes at most $d$.  We will show that this poset is isomorphic to a poset of words in order to determine the M\"{o}bius function of our poset.

Let $A^*$ be the free monoid under concatenation of $A=\{a,b\}$.  We think of $A^*$ as the set of all words that can be created from the {\it alphabet} $A$.  The identity in $A^*$ is the empty word $\epsilon$.    We say that the length of a word $u=u_1u_2\dots u_k$ is $|u|=k$.  Let  $u=u_1u_2\dots u_k$ and $w=w_1w_2\dots w_\ell$ be words in $A^*$.  We make $A^*$ into a poset by letting $u\leq w$ if there exist $i_1\leq i_2\leq\dots\leq i_k$ such that $u_j=w_{i_j}$ for $1\leq j\leq k$.  We call the set $\iota=\{i_1,i_2\dots,i_k\}$ an {\it embedding} of $u$ in $w$ and let $w_\iota=w_{i_1}w_{i_2}\dots w_{i_k}$.  If $\iota$ is an embedding of $u$ in $w$, then we say that $w_j$ is {\it supported} by $u$ in $\iota$ if $j\in\iota$.  For example, the word $abaab$ is a subword of $w=aabbababb$, since $w_2w_3w_5w_7w_8=abaab$, and $w_3$ is supported in this embedding.

Now, let $\phi:\mathbb{P}\rightarrow A^*$ be given by $\phi(k)=a\underbrace{bb\dots b}_{k-1}$.  Given any composition in $C$, $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)$, let $\phi(\alpha)=\phi(\alpha_1)\phi(\alpha_2)\cdots\phi(\alpha_k)$ omitting the initial $a$ from $\phi(\alpha_1)$.  It is not hard to see that $\phi:C\rightarrow A^*$ is a bijection.

\begin{thm} The map $\phi$ is an isomorphism of $A^*$ and $C$ as partially ordered sets. \end{thm}

\noindent {\bf Proof:} Since we have already established $\phi$ as a bijection between $A^*$ and ${\bf C}$, it is enough to show that $\phi$ preserves the partial orderings.

Let $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_k)\covb\beta=(\beta_1,\beta_2,\dots,\beta_\ell)\in C$.  If $\ell=k$ then, for some $j$, $\beta_j=\alpha_j+1$ and $\beta_i=\alpha_i$ for $i\not=j$.  In this case $\phi(\beta)$ is obtained from $\phi(\alpha)$ by inserting a $b$ into $\phi(\alpha)$ anywhere between the ${j-1}^{st}$ and $j^{th}$ occurrence of an $a$.  Thus, $\phi(\alpha)$ is a subword of $\phi(\beta)$.

If $\ell=k+1$ then $\beta_j=\alpha_j+1-h$ for some $h\leq \alpha_j$, $\beta_{j+1}=h$ and $\beta_i=\alpha_i$ for $i\not=j$ or $j+1$.  In this case $\phi(\beta)$ is obtained from $\phi(\alpha)$ by inserting an $a$ between the $(j-1)^{st}$ and $j^{th}$ occurrence of an $a$, so that $h-1$ $b$'s follow the inserted $a$.

Thus $\beta\covr\alpha\Rightarrow\phi(\beta)\covr\phi(\alpha)$.  The converse is proved similarly.  $\square$

\medskip

Let $A^*_d$ be the subposet of $A^*$ consisting of all words that do not have $d+1$ consecutive $b$'s.  Notice that $\phi$ restricts to an isomorphism between $C_{d+1}$, as defined above, and the subposet, $A^*_d$.  Much is known about partially ordered sets on words and subword order, so it will be convenient to work with the poset $A^*_d$ to understand the poset $C_{d+1}$.

In the next two sections we determine the M\"{o}bius function of $C_{d+1}$ using a strictly combinatorial argument and then using shellability.  The proofs in Sections 2 and 3 are adaptations of similar proof given by Bj\"{o}rner.  In Section 4 we show that the zeta function and M\"{o}bius function are rational.  Finally, in the last section we determine a generating function in commuting variables for the zeta function and the M\"{o}bius function that emphasizes the connection with the poset $C_{d+1}$.

\section{The M\"{o}bius Function of $C_d$}

In this section we will provide a combinatorial proof that the M\"{o}bius function, $\mu$, satisfies $\mu(u,w)=(-1)^{|u|+|w|}{w\choose u}_{dn}$, where ${w\choose u}_{dn}$ is the number of $d$-normal embeddings of $u$ in $w$.

We remind the reader that the M\"{o}bius function of a poset is the unique function satisfying the following.
\begin{itemize}
\item $\mu(x,x)=1$
\item $\sum_{x\leq z\leq y}\mu(z,y)=0$
\item $\mu(x,y)=0$ for $x\nleq y$
\end{itemize}

To describe the M\"{o}bius function of $A^*_d$ we will need the concepts of $d$-normal embedding and right-most embedding.  We will call a set $[r,s]$ a {\it run} if $w_r=w_{r+1}=\dots=w_s$.  Let the {\it repetition set} of $w$ be $R(w)=\{j:w_j=w_{j-1}\}$.  An embedding $\iota=\{i_1,i_2,\dots,i_k\}$ of $u$ in $w$ is called {\it $d$-normal} if (a) $R(w)\subseteq\{i_1,i_2,\dots,i_k\}$, and (b) for any run of $d$ $b$'s not at the beginning of $u$ with the first $b$ in this run corresponding to $w_{i_j}$ in the embedding, we must have $w_{i_j-1}=a$ and $i_j-1\in\iota$.  Let ${w\choose u}_{dn}$ be the number of $d$-normal embeddings of $u$ in $w$.  The {\it right-most embedding} of $u$ in $w$ is the unique embedding $\{j_1,j_2\dots j_r\}$ such that for any other embedding $\{i_1,i_2\dots i_r\}$ of $u$ in $w$ we have that $i_\ell\leq j_\ell$, for each $1\leq \ell\leq r$.

\begin{thm} For any words $u,w\in A^*_d$, $$\mu(u,w)=(-1)^{|w|+|u|}{w\choose u}_{dn}.$$\end{thm}

\noindent {\bf Proof:} This proof is essentially the same as the proof of Theorem 3.1 from~\cite{Bjornerfactor}.  We will show that the function $f(u,w)=(-1)^{|w|+|u|}{w\choose u}_{dn}$ satisfies the three conditions above and hence, must be $\mu$.

Clearly, $f(u,u)=1$, and $f(u,w)=0$ for $u\nleq w$.  It remains to show that\\ $\sum_{u\leq v\leq w}f(v,w)=0$ for any $v\leq w$.

Suppose that $|w|=n$ and $|u|=k$.  Let $N$ be the set of embeddings $\iota$ such that $\iota$ is a $d$-normal embedding of $w_\iota$ in $w$, and $u\leq w_\iota$.  Let $N_e=\{\iota\in N:|\iota|\mathrm{\:is\:even}\}$ and $N_o=\{\iota\in N:|\iota|\mathrm{\:is\:odd}\}$.  Then $$\sum_{u\leq v\leq w}f(v,w)=(-1)^n(\#N_e-\#N_o).$$  A bijection between $N_e$ and $N_o$ will complete the proof.

 For each embedding $\iota\in N$ let $\iota_f$ be the minimal element of $[n]$ such that $\iota_f$ is not in the right-most embedding of $u$ in $w_\iota$.  Define $\psi:N\rightarrow N$ by $$\psi(\iota)=\left\{\begin{array}{ll} \iota\cup\{\iota_f\}&\mathrm{if\:}\iota_f\notin\iota,\\ \iota-\{\iota_f\}&\mathrm{if\:}\iota_f\in\iota.\end{array}\right.$$

We show that $\psi$ is well-defined.  If $\iota_f\notin\iota$ then, since $R(w)\subseteq\iota$, we must have $R(w)\subseteq\iota\cup\{\iota_f\}$.  If $\iota_f\in\iota$ then we want to show that $\iota_f\notin R(w)$.  If $\iota_f\in R(w)$ then $w_{\iota_f}=w_{\iota_f-1}$.  Also $\iota_f-1$ must be in the right-most embedding of $u$ in $w_\iota$.  This is impossible by the definition of right-most embedding.

We must show that $w_{\psi(\iota)}$ is still an element of $A^*_d$.  If $\psi$ removes an $a$ creating a run of $b$'s of length $d+1$  in $w_{\psi(\iota)}$ then the first $b$ in the run of $b$'s immediately preceding $a$ cannot be in the right-most embedding of $u$ in $w_{\iota}$.  Thus, the $a$ would never have been removed by $\psi$.

If $\psi$ inserts a $b$ creating a run of $b$'s of length $d+1$ in $w_{\psi(\iota)}$ then $w_{\iota}$ has a run of $b$'s of length $d$.  Let the first $b$ of this run be in position $i_t$.  Clearly $i_t\not=1$.  Since $\iota$ is a $d$-normal embedding of $w_{\iota}$ in $w$, we must have $w_{i_t-1}=a$ and $i_t-1\in{\iota}$ rendering the creation of this run impossible.

Since $\psi$ is its own inverse and changes the parity of $|\iota|$, the proof is complete. $\square$

\section{Shellability and the M\"{o}bius Function}

We now give an alternate proof that $\mu(u,w)=(-1)^{|w|+|u|}{w \choose u}_{dn}$ by showing that $A^*_d$ is dual CL-shellable.  Throughout this section we assume familiarity with lexicographical shellability.  The same labeling that Bj\"{o}rner used in~\cite{Bjornersubword} to determine the M\"{o}bius function of $A^*$ will work for our poset $A^*_d$.

Let $[u,w]$ be an interval of $A^*$ and each maximal chain $c=(u=x_1,x_2,\dots,x_k=w)$ in $[u,w]$ be assigned a label $\ell(m)=(\ell_1(m),\ell_2(m),\dots,\ell_k(m))$ as follows.  Label the edge $(x_{k-1},x_k,c)$ by $\ell(x_{k-1},x_k,c)=i_1$, where $i_1$ is the smallest element of $[k]$ such that $[k]-\{i_1\}$ is an embedding of $x_{k-1}$ in $x_{k}$.  Label the edge $(x_{k-2},x_{k-1},c)$ by $\ell(x_{k-2},x_{k-1},c)=i_2$, where $i_2$ is the least element of $[k]-\{i_1\}$ such that $[k]-\{i_1,i_2\}$ is an embedding of $x_{k-2}$ in $x_k$.  Repeat this process for the remaining edges.  It is clear that if two maximal chains have the same first $s$ edges then the labels on these edges will be the same.  Figure 1 shows a chain-edge labeling for $[abb,aabbab]$.

\begin{thm}[Bj\"{o}rner] The map $\ell:A^*\rightarrow \mathbb{Z}$ described above is a  dual CL-labeling for each interval of $A^*$.  \end{thm}

In Bj\"{o}rners proof, \cite{Bjornersubword}, he shows that the unique ascending maximal chain is the one corresponding to the right-most embedding of $u$ in $w$.  Let $\{i_1,i_2,\dots,i_k\}$ be the rightmost embedding of $u$ in $w$, then the ascending maximal chain is the maximal chain labeled by the elements of $[n]-\{i_1,i_2,\dots,i_k\}$ from smallest to largest.  The unique ascending chain in Figure 1 is $$abbaba\stackrel{1}{-}abbab\stackrel{3}{-}abab\stackrel{5}{-}abb.$$  It is also clear that since we are working with the right-most embedding, this chain must have the lexicographically smallest possible entries.

\medskip

\vspace{.5in}

\begin{pspicture}(-5,-5)(5,5)
\rput[l](-5,5){\bf Figure 1}
\rput[t](0,4.5){$aabbab$}
\rput[t](-4.5,2){$aabbb$}
\rput[t](-1.5,2){$aabba$}
\rput[t](1.5,2){$abbab$}
\rput[t](4.5,2){$aabab$}
\rput[t](-4.5,-2){$abbb$}
\rput[t](-1.5,-2){$aabb$}
\rput[t](1.5,-2){$abba$}
\rput[t](4.5,-2){$abab$}
\rput[t](0,-4.5){$abb$}
\psline(0,4.2)(-4.5,2)
\psline(0,4.2)(-1.5,2)
\psline(0,4.2)(1.5,2)
\psline(0,4.2)(4.5,2)
\psline(-4.5,1.7)(-4.5,-2)
\psline(-4.5,1.7)(-1.5,-2)
\psline(-1.5,1.7)(-1.5,-2)
\psline(-1.5,1.7)(1.5,-2)
\psline(1.5,1.7)(-4.5,-2)
\psline(1.5,1.7)(1.5,-2)
\psline(1.5,1.7)(4.5,-2)
\psline(4.5,1.7)(-1.5,-2)
\psline(4.5,1.7)(4.5,-2)
\psline(-4.5,-2.3)(0,-4.5)
\psline(-1.5,-2.3)(0,-4.5)
\psline(1.5,-2.3)(0,-4.5)
\psline(4.5,-2.3)(0,-4.5)
\rput[t](-3.2,3){5}
\rput[t](-1.2,3){6}
\rput[t](1.2,3){1}
\rput[t](3.2,3){3}
\rput[t](-4.7,0){1}
\rput[t](-3.3,0){3}
\rput[t](-3.7,-1){5}
\rput[t](-1.7,1){5}
\rput[t](-0.3,0){1}
\rput[t](1.2,0.5){6}
\rput[t](3.7,1){5}
\rput[t](4.8,0){1}
\rput[t](3.1,-0.5){3}
\rput[t](-3.2,-3){3}
\rput[t](-1.2,-3){1}
\rput[t](1.2,-3){5}
\rput[t](3.2,-3){5}
\end{pspicture}

\vspace{.5in}

Each maximal chain of an interval $[u,w]$ in $A^*_d$ is also a maximal chain of the same interval in $A^*$.  For $u,w\in A^*_d$, we will denote by $[u,w]_d$ the interval $[u,w]$ in $A^*$ restricted to $A^*_d$.  We will label the edges of $A^*_d$ in exactly the same way as we did for $A^*$.

\begin{thm} The map $\ell_d:A^*_d\rightarrow \mathbb{Z}$ is a dual CL-labeling for each interval of $A^*_d$, and hence $A^*_d$ is CL-shellable.  \end{thm}

\noindent {\bf Proof:}  We already know that there is exactly one descending maximal chain, $m_0$, in the labeling of an interval $[u,w]$ in $A^*$, and that $m_0$ corresponds to the right-most embedding of $u$ in $w$.  This means that there is at most one descending maximal chain among those in the interval $[u,w]_d$.  We must show that this chain is indeed in $[u,w]_d$.  Unless a chain from $[u,w]$ passes through an element with a run of $b$'s of length at least $d+1$, that chain is in $[u,w]_d$.

Suppose that the unique ascending maximal chain for $[u,w]$ passes through an element with a run of $b$'s of length at least $d+1$ and hence is not in $[u,w]_d$.  At some step in the labeling of this chain we must have $x_i\covr x_{i-1}$, where $x_i$ does not have a run of $b$'s of length at least $d+1$, but $x_{i-1}$ does.  This may only happen if an $a$ that was separating those $b$'s in $x_i$ is removed in this step.  Since this chain corresponds to the right-most embedding of $u$ in $w$ and $u$ and $w$ do not have a run of $b$'s of length at least $d+1$, the $a$ removed could not have been the left-most removable element.   $\square$

\begin{cor}  For words $u$ and $w$ in $A^*_d$ we have $\mu(u,w)=(-1)^{|w|-|u|}{w\choose u}_{dn}$.  \end{cor}

\noindent {\bf Proof:}  It suffices to show that the number of descending chains in $[u,w]$ is the same as the number of $d$-normal embeddings of $u$ in $w$.

Suppose $\iota=\{i_1,i_2\dots, i_k\}$ is an embedding of $u$ in $w$ such that there is a maximal chain $m$ with $[n]-\{\ell_1(m),\ell_2(m),\dots,\ell_{n-k}(m)\}=\iota$.  Then $m$ is descending if $m$ is obtained by deleting the entries $w_j$, $j\in [n]-\iota$, from right to left.  The only way that this is possible is if for each $j\in[n]-\iota$, we have that $w_j\not=w_{j-1}$.  This implies that $\{i_1,i_2,\dots ,i_k\}$ is a $d$-normal embedding of $u$ in $w$.

Similarly, if $\iota =\{i_1,i_2,\dots,i_k\}$ is a $d$-normal embedding of $u$ in $w$ then there is a descending maximal chain corresponding to $\iota$ given by deleting the elements $w_j$, $j\in[n]-\iota$, from right to left.   $\square$

\section{Rationality}

We now consider the formal power series algebra $\mathbb{Z}\left\langle\left\langle A\right\rangle\right\rangle$ in the noncommuting variables of $A$ over $\mathbb{Z}$.  Every $f\in\mathbb{Z}\left\langle \left\langle A\right\rangle\right\rangle$ is of the form $$f=\sum_{w\in A^*}c_ww,$$ where $c_w\in\mathbb{Z}$.  We let $f^*=\epsilon+f+f^2+\dots=(\epsilon-f)^{-1}$ for any series $f\in\mathbb{Z}\left\langle \left\langle A\right\rangle\right\rangle$ with no constant term.  Let $f^+=f^*-\epsilon$.  A series $f\in\mathbb{Z}\left\langle \left\langle A\right\rangle\right\rangle$ is called rational if it can be constructed from a finite number of monomials under a finite number of the usual algebraic operations in $\mathbb{Z}\left\langle \left\langle A\right\rangle\right\rangle$ and the $*$ operation.  Clearly, $f^+$ is rational if $f^*$ is.

We may also consider series of the form $f=\sum_{u\leq w}c_{(u,w)}u\otimes w$ where $u\otimes w$ just represents the ordered pair $(u,w)\in A^*\times A^*$.  Rationality of such a series is defined similarly.

In~\cite{BjornerReutenauer}, Bj\"{o}rner and Reutenauer showed that the following four series are rational:
\begin{eqnarray*}
Z(u)&=&\sum_{w\in A^*}\zeta(u,w)w,\\
M(u)&=&\sum_{w\in A^*}\mu(u,w)w,\\
Z_\otimes&=&\sum_{w\in A^*}\zeta(u,w)u\otimes w, \mbox{ and}\\
M_\otimes&=&\sum_{w\in A^*}\mu(u,w)u\otimes w.\\
\end{eqnarray*}

In this section we will use methods similar to those used by Bj\"{o}rner and Sagan~\cite{SagBjorncomposet} to do the same for the series $Z_d(u)$, $M_d(u)$, $Z^d_\otimes$, and $M^d_\otimes$, where these series are defined exactly the same way as those above replacing $A^*$ by $A^*_d$ in each.  In the remainder of this section we will assume that $d=3$.  The reason that we let $d=3$ is to avoid cumbersome formulas and definitions.  Everything that is used to prove these facts for $d=3$ has an obvious generalization.

We begin with $Z_3(u)$ and $M_3(u)$.  A function $f:S^*\rightarrow T^*$ where $S$ and $T$ are finite sets is {\it multiplicative} if for $u=u_1u_2\dots u_m\in S^*$, we have that $f(u)=f(u_1)f(u_2)\cdots f(u_m)$.  Let $A_3=\{a,ab,abb,abbb\}$.  Let $B=\epsilon+b+bb+bbb$, and notice that $B(A_3)^*=A_3^*$.  Each word $u\in A_3^*$ can be broken uniquely into its maximal runs of $a$'s and $b$'s.  Define the multiplicative function $$z:A_3^*\rightarrow\mathbb{Z}\left\langle \left\langle A_3\right\rangle\right\rangle,$$ by

\begin{eqnarray*}
z(a^k)&=&(aB)^{k-1}a,\\
z(b)&=&(B-\epsilon)a^*,\\
z(bb)&=&(B-\epsilon)a^+ba^*+(B-b-\epsilon)a^*,\mbox{ and}\\
z(bbb)&=&(B-\epsilon)a^+ba^*ba^*+(B-b-\epsilon)a^+ba^*+bbba^*.\\
\end{eqnarray*}

If a run of $a$'s is at the end of the word then let $z(a^k)=(A_3)^k$ for this run of $a$'s.  Let $p_z(u)$ be the {\it prefix} of $Z(u)$ where, $$p_z(u)=\left\{\begin{array}{ll}A_3^*&u\:\mathrm{begins\:with\:}a,\\
(A_3^*a+\epsilon)&u\:\mathrm{begins\:with\:}b.\\ \end{array}\right.$$

Define the multiplicative function $$m:A_3^*\rightarrow\mathbb{Z}\left\langle \left\langle A_3\right\rangle\right\rangle,$$ by

\begin{eqnarray*}
m(a^k)&=&(ab)^*(\epsilon-a)a\left[(\epsilon-b(ab)^*(\epsilon-a))a\right]^{k-1}\\
m(b)&=&\left(\epsilon-b(ab)^*(\epsilon-a)\right)b,\\
m(bb)&=&\left(\epsilon-b(ab)^*(\epsilon-a)\right)b(ab)^*(\epsilon-a)b,\mbox{ and}\\
m(bbb)&=&b\left((ab)^*(\epsilon-a)b\right)^2.\\
\end{eqnarray*}

Let $p_m(u)$ be the {\it prefix} of $M(u)$ where, $$p_m(u)=\left\{\begin{array}{ll}(\epsilon-b)&\mbox{if }u\:\mathrm{begins\:with\:}a,\\
(\epsilon-a)&\mbox{if }u\:\mathrm{begins\:with\:}\:b,\:\mathrm{or}\:bb,\\
(\epsilon+b(ab)^*a)&\mbox{if }u\:\mathrm{begins\:with\:}bbb.\\ \end{array}\right.$$

Let $s_m(u)$ be the {\it suffix} of $M(u)$ where,
$$s_m(u)=\left\{\begin{array}{ll}(ba)^*(\epsilon-b)&\mbox{if }u\:\mbox{ends in } a,\\
(ab)^*(\epsilon-a)&\mbox{if }u\:\mbox{ends in }b.\end{array}\right.$$

\begin{lem} For any $u\in A^*_3$ we have that $$Z_3(u)=p_z(u)z(u),$$ and $$M_3(u)=p_m(u)m(u)s_m(u).$$
\end{lem}

\noindent {\bf Proof:}  We begin by proving the statement for $Z_3(u)$.  We must show that the functions $p_z$ and $z$ will produce each word that contains $u$ exactly once.  This is done by showing that for $w\geq u$, $z(u)$ produces the right-most embedding of $u$ in $w$.  We will explain how this works for $z(a^k)$ and $z(b^\ell)$, how $z(a^k)$ interacts with $z(b^{\ell})$ and how the prefix works.

The last $a$ in the run $a^k$ is given by the $a$ at the end of $z(a^k)$.  This is clearly under the right-most possible $a$ if we just focus on $z(a^k)$.  The preceding $k-1$ $a$'s are each followed by $B=\epsilon+b+bb+bbb$, so that each word produced by $z(a^k)$ contains $a^k$ exactly once.  Notice that any word produced by $z(a^k)$ begins with a supported $a$ and ends with a supported $a$.

We now turn our focus to $z(b^\ell)$.  We'll discuss $z(bb)$ as the others are similar.  The first term in $z(bb)$ produces words where the two supported $b$'s are separate, achieved by the $a^+$.  Now, at the beginning of each term in $z(bb)$ we can have a run of $b$'s.  The last $b$ (first term) and the last two $b$'s (second term) are the supported $b$'s.  Finally at the end of each term we have $a^*$ because we can follow our last supported $b$ by as many $a$'s as we like and still maintain a right-most embedding.

The series $z(a^k)$ and $z(b^\ell)$ interact in the following way.  The last $a$ in $z(a^k)$ is always supported, so if a run of $b$'s follows a run of $a$'s in $u$ then a right-most embedding is still maintained.  The last supported $b$ in $z(b^\ell)$ is followed by $a^*$, so if a run of $a$'s follows a run of $b$'s in $u$ then we still maintain a right most embedding.  It's worth mentioning that we haven't violated the fact that we may only have runs of $b$'s of length at most three.

We may essentially place any word from $A_3^*$ at the beginning of any word created by $z$.  We do this with the prefix $p_z(u)$.  If $u$ begins with $a$ we don't have to worry about avoiding a run of three $b$'s.  If $u$ begins with $b$ we do.  It's not hard to see that $p_z(u)$ handles these cases appropriately.

We will give a similar explanation for $M_3(u)$.  We must show that $p_m(u)m(u)s_m(u)$ will produce the word $w$ exactly $(-1)^{|w|-|u|}{w\choose u}_{3n}$ times.  First we explain $m(u)$.

The supported $a$'s in the words produced by $m(a^k)$ appear before the left square bracket and the right square bracket.  Before the first supported $a$ we may have a run of alternating $a$'s and $b$'s given by $(ab)^*$.  This run may end in $a$ or $b$ given by $\epsilon-a$.  The $a$ is negative in this term to represent the fact that the parity of $u$ and the word produced $w$ is different if $a$ is placed before the first supported $a$.  A similar argument explains the factor in preceding each of the remaining $k-1$ $a$'s.  Notice that in this case a run of alternating $a$'s and $b$'s must begin with $b$.  This is to maintain appropriately supported repetition sets forcing the embedding to be 3-normal.

Now, we turn our focus to $m(bbb)$.  The first $b$ and the $b$ preceding the last right parenthesis are the supported $b$'s in any word produced by $m(bbb)$.  Notice that there is nothing preceding the first supported $b$.  This forces the letter preceding the first supported $b$ to be a supported $a$ if $bbb$ is not at the beginning of $u$.  The first supported $b$ can be followed by a run of alternating $a$'s and $b$'s.  The cases $m(b)$ and $m(bb)$ have similar explanations.

The prefix and suffix for $m$ merely produce a run of alternating $a$'s and $b$'s at the beginning or end of the produced word taking care of supported repetition sets and preventing any word from being produced more than required.

From our description any word produced by $p_m(u)m(u)s_m(u)$ must give a unique 3-normal embedding of $u$.  This shows that $M_3(u)=p_m(u)m(u)s_m(u)$. $\square$

\medskip

The fact that $p_z(u)$, $z(u)$, $p_m(u)$, $m(u)$, and $s_m(u)$ are rational for each $u\in A_3^*$ proves the following theorem.

\begin{thm}  The series $Z_3(u)$ and $M_3(u)$ are rational.  $\square$ \end{thm}

The techniques used above to prove the rationality of $Z_3(u)$ and $M_3(u)$ are a bit cumbersome.  We will use finite state automata to prove that $Z_{\otimes}^3$ and $M_{\otimes}^3$ are rational.

Let $S$ be an alphabet.  A {\it finite state automaton} is a digraph $D$, with vertex set $V$ and arc set $E$, allowing loops and multi-arcs.  There are unique vertices $\alpha$ and $\omega$, where $\alpha$ is the initial vertex and $\omega$ is the final vertex.  Each arc $e\in E$ is labeled by a monomial $f(e)\in\mathbb{Z}\left\langle \left\langle S\right\rangle\right\rangle$.  A finite walk $W$ with arcs $e_1,e_2,\dots,e_k$ is given the monomial label $$f(W)=\prod_{i=1}^k f(e_i).$$  The series {\it accepted} by $D$ is $$f(D)=\sum_Wf(W),$$ where the sum is over all walks in $D$ from $\alpha$ to $\omega$.

If $e_1,\dots e_j$ are all arcs from one vertex to another, replacing them by a single arc $e$ and labeling this arc $$\sum_{i=1}^j f(e_i)$$ does not change the series accepted by $D$.  For simplification we will use this procedure.

It is a well-known fact that a series is rational if and only if it is accepted by a finite state automaton~\cite{BerstelReutenauer}.  We will construct finite state automata accepting $Z_{\otimes}^3$ and $M_{\otimes}^3$ to prove the following theorem for $d=3$.  The pattern in the automata will be obvious and generalizable.

\begin{thm}  For any $d$, $Z_{\otimes}^d$ and $M_{\otimes}^d$ are rational.\end{thm}

\noindent {\bf Proof:}  The automata in Figures 2 and 3 are for $Z_{\otimes}^3$ and $M_{\otimes}^3$ respectively.  We will use them to explain why these automata work and how they are generalizable to any $d$.  For clarity we left some arcs off of the diagrams.  In Figure 2, there is an arc labeled $\epsilon\otimes\epsilon$ from each node to $\omega$.  In Figure 3, there is an arc labeled $\epsilon\otimes\epsilon$ from each of $\alpha_1$, $\alpha_2$, $\alpha_3$, $\beta_2$, $\beta_3$, $\beta_4$, $\gamma_5$, $\gamma_6$, $\gamma_7$, $\delta_8$, $\delta_9$, and $\delta_{10}$ to $\omega$.  There is also an arc labeled $a\otimes a$ from each of $\beta_2$, $\beta_3$, $\beta_4$, $\gamma_5$, $\gamma_6$, $\gamma_7$, $\delta_8$, $\delta_9$, and $\delta_{10}$ to each of $\alpha_3$, $\beta_1$, $\gamma_1$, and $\delta_1$.  Also in Figure 3, we separated the nodes $\alpha$, $\alpha_1$ and $\alpha_2$ from the rest of the diagram for clarity.

We claim that for any $u=u_1u_2\dots u_k\leq w=w_1w_2\dots w_n$ there is a unique walk from $\alpha$ to $\omega$ in the automaton for $Z_{\otimes}^3$ labeled $u\otimes w$.  Consider the right-most embedding $\iota=\{i_1,i_2,\dots,i_k\}$ of $u$ in $w$.  We'll build $u\otimes w$ from this embedding.  The first $i_1-1$ letters in $w$ are not supported, so this portion of $w$ is constructed using the nodes $\alpha$, $\alpha_1$, $\alpha_2$, and $\alpha_3$.  Notice that any word in $A_3^*$ can be built uniquely by using the nodes $\alpha$, $\alpha_1$, $\alpha_2$, and $\alpha_3$.  Now, if $u_1=a$ and $w_{i_1}$ is preceded by an $a$ then we must go along the arc from $\alpha$ to $\alpha_4$.  If $w_{i_1}$ is preceded by a run of $b$'s then we must go along the arc from $\alpha$ to $\gamma_1$, construct this run of $b$'s and then go to $\alpha_4$.  If $u_1=b$ and $w_{i_1}$ is preceded by an $a$ then at this point the walk goes along the arc from $\alpha$ to $\beta_1$.  If $u_1=b$ and $w_{i_1}$ is preceded by a run of $b$'s then the walk must go along the arc from $\alpha$ to $\gamma_1$, build up the preceding run of unsupported $b$'s and then go on to either $\beta_2$ or $\beta_3$ from $\gamma_1$ or $\gamma_2$.

Now, there is no way to get back to the $\alpha$, $\alpha_1$, $\alpha_2$, and $\alpha_3$ part of the digraph.  Notice that if $u_1=a$ then to construct the unsupported part of $w$ between $w_{i_1}$ and $w_{i_2}$ we can only construct a run of $b$'s given by the cycle $\gamma_1\rightarrow\gamma_2\rightarrow\gamma_3\rightarrow\alpha_4$.  If $u_1=b$ then the unsupported part of $w$ between $w_{i_1}$ and $w_{i_2}$ can only be a run of $a$'s given by the loops labeled $\epsilon\otimes a$ at each of $\beta_1$, $\beta_2$ and $\beta_3$.  This is forcing the embedding $\iota$ to be the right-most embedding.  The construction continues as above for the remainder of $u\otimes w$.

It is important to note here that the complication of the diagram develops from the fact that we must be careful to avoid producing a run of more than three $b$'s in $u$ or $w$.  The portion of the digraph involving $\beta_1$, $\beta_2$ and $\beta_3$ controls the supported $b$'s in $w$, and the portion involving $\gamma_1$, $\gamma_2$ and $\gamma_3$ controls the unsupported $b$'s.

\vspace{.25in}

\begin{picture}(400,450)

\put(200,400){\circle{20}}
\put(120,400){\circle{20}}
\put(280,400){\circle{20}}
\put(195,400){$\alpha_2$}
\put(115,400){$\alpha_3$}
\put(275,400){$\alpha_1$}
\put(270,400){\vector(-1,0){60}}
\put(190,400){\vector(-1,0){60}}
\put(130,395){\vector(2,-3){57}}
\put(270,395){\vector(-2,-3){57}}
\put(200,390){\vector(0,-1){78}}
\put(213,300){\vector(2,3){59}}
\put(150,405){$\epsilon\otimes b$}
\put(230,405){$\epsilon\otimes b$}
\put(190,340){\rotatebox{90}{$\epsilon\otimes a$}}
\put(134,365){\rotatebox{305}{$\epsilon\otimes a$}}
\put(224,345){\rotatebox{55}{$\epsilon\otimes a$}}
\put(244,335){\rotatebox{55}{$\epsilon\otimes b$}}

\put(200,300){\circle{25}}
\put(195,297){{\large $\alpha$}}
\put(190,145){\circle{20}}
\put(185,142){$\alpha_4$}
\put(50,180){\circle{20}}
\put(350,180){\circle{20}}
\put(100,50){\circle{20}}
\put(300,50){\circle{20}}
\put(275,140){\circle{20}}
\put(45,175){$\beta_1$}
\put(345,175){$\gamma_2$}
\put(270,135){$\gamma_3$}
\put(95,45){$\beta_2$}
\put(295,45){$\beta_3$}
\put(300,230){\circle{20}}
\put(295,225){$\gamma_1$}
\put(190,290){\vector(-4,-3){135}}
\put(50,170){\vector(1,-2){55}}
\put(110,50){\vector(1,0){180}}
\put(345,170){\vector(-1,-3){37}}
\put(305,220){\vector(1,-1){33}}
\put(212,298){\vector(4,-3){80}}
\put(60,180){\vector(4,-1){115}}
\put(175,144){\vector(-4,1){115}}
\put(195,290){\vector(0,-1){135}}
\put(105,60){\vector(1,1){75}}
\put(290,50){\vector(-1,1){90}}
\put(265,140){\vector(-1,0){60}}
\put(340,180){\vector(-2,-1){60}}
\put(200,145){\vector(1,1){85}}
\put(288,225){\vector(-1,-1){85}}
\put(340,183){\line(-2,1){62}}
\put(245,173){\rotatebox{45}{$a\otimes a$}}

\put(188,295){\line(-1,0){30}}
\put(158,305){\vector(1,0){30}}
\put(158,300){\oval(10,10)[l]}

\put(310,30){\oval(35,30)[bl]}
\put(310,30){\oval(35,30)[r]}
\put(292.5,30){\vector(0,1){10}}

\put(90,30){\oval(35,30)[br]}
\put(90,30){\oval(35,30)[l]}
\put(107.5,30){\vector(0,1){10}}

\put(35,165){\oval(30,30)[br]}
\put(35,165){\oval(30,30)[l]}
\put(50,165){\vector(0,1){5}}

\put(185,136){\line(0,-1){30}}
\put(195,106){\vector(0,1){30}}
\put(190,106){\oval(10,10)[b]}

\put(310,230){\line(1,0){80}}
\put(390,230){\line(0,-1){230}}
\put(390,0){\line(-1,0){240}}
\put(150,0){\vector(-1,1){40}}

\put(126,298){$\epsilon\otimes a$}

\put(315,220){\rotatebox{310}{$\epsilon\otimes b$}}
\put(200,5){$b\otimes b$}
\put(300,5){$\epsilon\otimes a$}
\put(250,280){\rotatebox{320}{$\epsilon\otimes b$}}
\put(200,230){\rotatebox{270}{$a\otimes a$}}
\put(230,185){\rotatebox{55}{$\epsilon\otimes b$}}
\put(220,145){$a\otimes a$}
\put(295,162){\rotatebox{28}{$\epsilon\otimes b$}}
\put(315,110){\rotatebox{78}{$b\otimes b$}}
\put(177,93){$a\otimes a$}
\put(200,55){$b\otimes b$}
\put(100,230){\rotatebox{42}{$b\otimes b$}}
\put(75,5){$\epsilon\otimes a$}
\put(110,150){\rotatebox{345}{$b\otimes b$}}
\put(110,170){\rotatebox{345}{$a\otimes a$}}
\put(20,140){$\epsilon\otimes a$}
\put(238,90){\rotatebox{315}{$a\otimes a$}}
\put(78,120){\rotatebox{295}{$b\otimes b$}}
\put(130,100){\rotatebox{45}{$a\otimes a$}}
\put(0,450){{\bf Figure 2: $Z_{\otimes}^3$}}

\end{picture}

\vspace{.5in}

\begin{picture} (500,700)

\put(0,700){{\bf Figure 3: $M_{\otimes}^3$}}
\put(100,490){\circle{20}}
\put(200,490){\circle{20}}
\put(195,490){$\alpha_3$}
\put(95,490){$\alpha_4$}
\put(50,400){\circle{20}}
\put(160,400){\circle{20}}
\put(335,400){\circle{20}}
\put(45,400){$\beta_1$}
\put(155,400){$\gamma_1$}
\put(330,400){$\delta_1$}
\put(50,300){\circle{20}}
\put(50,200){\circle{20}}
\put(50,100){\circle{20}}
\put(45,300){$\beta_2$}
\put(45,200){$\beta_3$}
\put(45,100){$\beta_4$}
\put(130,300){\circle{20}}
\put(190,300){\circle{20}}
\put(130,200){\circle{20}}
\put(190,200){\circle{20}}
\put(130,100){\circle{20}}
\put(190,100){\circle{20}}
\put(125,300){$\gamma_2$}
\put(125,200){$\gamma_3$}
\put(125,100){$\gamma_4$}
\put(185,300){$\gamma_5$}
\put(185,200){$\gamma_6$}
\put(185,100){$\gamma_7$}
\put(260,300){\circle{20}}
\put(260,200){\circle{20}}
\put(260,100){\circle{20}}
\put(335,300){\circle{20}}
\put(335,200){\circle{20}}
\put(335,100){\circle{20}}
\put(405,300){\circle{20}}
\put(405,200){\circle{20}}
\put(405,100){\circle{20}}
\put(255,300){$\delta_2$}
\put(255,200){$\delta_3$}
\put(255,100){$\delta_4$}
\put(330,300){$\delta_5$}
\put(330,200){$\delta_6$}
\put(330,100){$\delta_7$}
\put(400,300){$\delta_8$}
\put(400,200){$\delta_9$}
\put(400,100){$\delta_{10}$}
\put(210,510){\oval(35,30)[tl]}
\put(210,510){\oval(35,30)[r]}
\put(192.5,510){\vector(0,-1){10}}
\put(190,495){\vector(-1,0){80}}
\put(110,485){\vector(1,0){78}}
\put(140,500){$-\epsilon\otimes b$}
\put(140,475){$-\epsilon\otimes a$}
\put(90,490){\vector(-1,-2){40}}
\put(200,480){\vector(-1,-2){35}}
\put(110,480){\vector(2,-3){45}}
\put(202,480){\vector(3,-2){120}}
\put(50,390){\vector(0,-1){80}}
\put(50,290){\vector(0,-1){80}}
\put(45,190){\vector(0,-1){80}}
\put(55,110){\vector(0,1){80}}
\put(155,390){\vector(-1,-3){25}}
\put(165,390){\vector(1,-3){25}}
\put(130,290){\vector(0,-1){80}}
\put(125,190){\vector(0,-1){80}}
\put(135,110){\vector(0,1){80}}
\put(190,290){\vector(0,-1){80}}
\put(185,190){\vector(0,-1){80}}
\put(195,110){\vector(0,1){80}}
\put(330,390){\vector(-2,-3){59}}
\put(335,390){\vector(0,-1){80}}
\put(340,390){\vector(2,-3){57}}
\put(260,290){\vector(0,-1){80}}
\put(255,190){\vector(0,-1){80}}
\put(265,110){\vector(0,1){80}}
\put(335,290){\vector(0,-1){80}}
\put(330,190){\vector(0,-1){80}}
\put(340,110){\vector(0,1){80}}
\put(405,290){\vector(0,-1){80}}
\put(400,190){\vector(0,-1){80}}
\put(410,110){\vector(0,1){80}}
\put(160,248){\vector(2,3){27}}
\put(140,100){\line(1,0){20}}
\put(160,100){\line(0,1){148}}
\put(140,200){\line(1,0){20}}
\put(270,200){\line(1,0){20}}
\put(270,100){\line(1,0){20}}
\put(290,100){\line(0,1){150}}
\put(290,250){\vector(1,1){40}}
\put(345,200){\line(1,0){20}}
\put(345,100){\line(1,0){20}}
\put(365,100){\line(0,1){150}}
\put(365,250){\vector(1,1){40}}
\put(250,200){\line(-1,0){20}}
\put(250,100){\line(-1,0){20}}
\put(230,200){\line(0,-1){120}}
\put(230,80){\line(1,0){205}}
\put(435,80){\line(0,1){170}}
\put(435,250){\vector(-3,4){30}}
\put(200,530){$a\otimes a$}
\put(40,335){\rotatebox{90}{$b\otimes b$}}
\put(40,235){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(35,135){\rotatebox{90}{$-\epsilon\otimes b$}}
\put(55,135){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(48,430){\rotatebox{65}{$a\otimes a+\epsilon\otimes\epsilon$}}
\put(125,345){\rotatebox{65}{$b\otimes b$}}
\put(180,360){\rotatebox{295}{$bb\otimes bb$}}
\put(120,235){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(115,135){\rotatebox{90}{$-\epsilon\otimes b$}}
\put(135,135){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(160,185){\rotatebox{90}{$b\otimes b$}}
\put(192,235){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(175,135){\rotatebox{90}{$-\epsilon\otimes b$}}
\put(200,135){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(105,465){\rotatebox{305}{$a\otimes a+\epsilon\otimes\epsilon$}}
\put(182,435){\rotatebox{65}{$\epsilon\otimes \epsilon$}}
\put(250,450){\rotatebox{330}{$a\otimes (a-ba)$}}
\put(275,330){\rotatebox{60}{$b\otimes b$}}
\put(325,330){\rotatebox{90}{$bb\otimes bb$}}
\put(365,360){\rotatebox{305}{$bbb\otimes bbb$}}
\put(250,235){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(245,135){\rotatebox{90}{$-\epsilon\otimes b$}}
\put(268,135){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(320,70){$bb\otimes bb$}
\put(290,190){\rotatebox{90}{$b\otimes b$}}
\put(325,235){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(320,135){\rotatebox{90}{$-\epsilon\otimes b$}}
\put(340,135){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(395,235){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(390,135){\rotatebox{90}{$-\epsilon\otimes b$}}
\put(410,135){\rotatebox{90}{$-\epsilon\otimes a$}}
\put(370,190){\rotatebox{90}{$b\otimes b$}}
\put(190,495){\line(-1,1){20}}
\put(170,515){\line(-1,0){125}}
\put(45,515){\vector(0,-1){105}}
\put(80,520){$\epsilon\otimes\epsilon$}

\put(315,610){\circle{20}}
\put(310,610){$\alpha_3$}
\put(345,610){\circle{20}}
\put(340,610){$\beta_2$}
\put(375,610){\circle{20}}
\put(370,610){$\gamma_2$}
\put(405,610){\circle{20}}
\put(400,610){$\gamma_5$}
\put(425,685){\circle{25}}
\put(420,683){{\large $\alpha_2$}}
\put(445,610){\circle{20}}
\put(440,610){$\delta_2$}
\put(475,610){\circle{20}}
\put(470,610){$\delta_5$}
\put(413,685){\line(-1,0){98}}
\put(437,685){\line(1,0){38}}
\put(315,685){\vector(0,-1){65}}
\put(345,685){\vector(0,-1){65}}
\put(375,685){\vector(0,-1){65}}
\put(405,685){\vector(0,-1){65}}
\put(445,685){\vector(0,-1){65}}
\put(475,685){\vector(0,-1){65}}
\put(302,630){\rotatebox{90}{$a\otimes a$}}
\put(332,630){\rotatebox{90}{$b\otimes b$}}
\put(362,630){\rotatebox{90}{$b\otimes b$}}
\put(392,630){\rotatebox{90}{$bb\otimes bb$}}
\put(432,630){\rotatebox{90}{$b\otimes b$}}
\put(462,630){\rotatebox{90}{$bb\otimes bb$}}

\put(65,610){\circle{20}}
\put(60,610){$\alpha_3$}
\put(95,610){\circle{20}}
\put(90,610){$\beta_2$}
\put(125,610){\circle{20}}
\put(120,610){$\gamma_2$}
\put(155,610){\circle{20}}
\put(150,610){$\gamma_5$}
\put(175,685){\circle{25}}
\put(170,683){{\large $\alpha_1$}}
\put(195,610){\circle{20}}
\put(190,610){$\delta_2$}
\put(225,610){\circle{20}}
\put(220,610){$\delta_5$}
\put(255,610){\circle{20}}
\put(250,610){$\delta_8$}
\put(163,685){\line(-1,0){98}}
\put(187,685){\line(1,0){68}}
\put(65,685){\vector(0,-1){65}}
\put(95,685){\vector(0,-1){65}}
\put(125,685){\vector(0,-1){65}}
\put(155,685){\vector(0,-1){65}}
\put(195,685){\vector(0,-1){65}}
\put(225,685){\vector(0,-1){65}}
\put(255,685){\vector(0,-1){65}}
\put(52,630){\rotatebox{90}{$a\otimes a$}}
\put(82,630){\rotatebox{90}{$b\otimes b$}}
\put(112,630){\rotatebox{90}{$b\otimes b$}}
\put(142,630){\rotatebox{90}{$bb\otimes bb$}}
\put(182,630){\rotatebox{90}{$b\otimes b$}}
\put(212,630){\rotatebox{90}{$bb\otimes bb$}}
\put(242,630){\rotatebox{90}{$bbb\otimes bbb$}}

\put(15,675){\circle{25}}
\put(10,675){{\large$\alpha$}}
\put(15,662){\vector(0,-1){72}}
\put(15,580){\circle{20}}
\put(10,580){$\alpha_1$}
\put(15,515){\circle{20}}
\put(10,515){$\alpha_2$}
\put(12,570){\vector(0,-1){45}}
\put(18,525){\vector(0,1){45}}
\put(2,600){\rotatebox{90}{$\epsilon\otimes (\epsilon-a)$}}
\put(0,530){\rotatebox{90}{$-\epsilon\otimes b$ }}
\put(19,530){\rotatebox{90}{$-\epsilon\otimes a$ }}

\end{picture}

Our comments above about the automaton forcing $\iota$ to be the right-most embedding proves that each $u\otimes w$ is produced by a unique walk, and hence the automaton accepts $Z_{\otimes}^3$.  To generalize this to any $Z_{\otimes}^d$, we would merely extend the $\alpha$, $\beta$, and $\gamma$ portions of the digraph appropriately.

We turn our focus to the automaton for $M_\otimes^3$.  We claim that there are ${w\choose u}_{3n}$ walks each of which produces $(-1)^{|w|+|u|}u\otimes w$.  Each word begins with a run of alternating unsupported $a$'s and $b$'s.  This is represented by the $\alpha$, $\alpha_1$, $\alpha_2$ portion of the automaton.  Once this run has been constructed the walk must move on to its first supported letter.  If the first supported letter is an $a$ then the walk goes from $\alpha_1$ or $\alpha_2$ to $\alpha_3$.  If the first supported letter is a $b$ then the walk goes from $\alpha_1$ or $\alpha_2$ into the $\beta$, $\gamma$ or $\delta$ portions of the automaton.  Notice that there is no directed edge from $\alpha_2$ to $\delta_8$.  This is to prevent a string of four $b$'s.

Once the walk leaves the $\alpha$, $\alpha_1$, $\alpha_2$ portion of the automaton it cannot return there.  The $\alpha_3$ and $\alpha_4$ portion of the automaton handles runs of supported $a$'s and runs of alternating unsupported $a$'s and $b$'s.

Now, the three legs of the diagram labeled with $\beta$'s, $\gamma$'s and $\delta$'s respectively, are controlling the three possibilities for a run of $b$'s in $u$.  If $u$ has a run of three $b$'s, the walk producing $u\otimes w$ must pass through the $\delta$ part of the diagram.  Unless the run of three $b$'s produced by $\delta$ is at the beginnins of $u$, the edge from $\alpha_3$ to
$\delta_1$ is labeled with a supported $a$ to ensure a 3-normal embedding.  Each of the three different legs of the $\delta$ portion of the diagram represents a supported $b$.  So once the walk is on any of the nodes $\delta_8$, $\delta_9$, or $\delta_{10}$ all three $b$'s in $u$ have been produced.  Notice that in this section between any two supported $b$'s there can be a run of alternating $a$'s and $b$'s, given by the exchange between the bottom two nodes of each leg.  Also, each arc going into $\delta_1$ is labeled with a supported $a$ immediately preceding the portion of the word to be produce.  This again is assuring that the embedding of any walk is 3-normal.

The portion marked with $\beta$'s controls situations where $u$ has a run of just one $b$ and the portion marked with $\gamma$'s takes care of two $b$'s.  This shows that every walk from $\alpha$ to $\omega$ in this automaton produces $u\otimes w$ according to a 3-normal embedding.  Thus, each 3-normal embedding $\iota$ of $u$ in $w$ is given by a unique walk from $\alpha$ to $\omega$.

Finally, notice that anytime a letter in a label on an arc is unsupported the sign of the monomial label changes.  This takes care of the sign of $\mu(u,w)$.  It's not hard to see from this explanation of the diagram that there are exactly ${w\choose u}_{3n}$ walks producing $(-1)^{|w|+|u|}u\otimes w$.  $\square$

\section{Generating Functions in Commuting Variables}

The generating functions above are quite beautiful and are rational, but they don't emphasize the connection between words in $A^*_d$ and the compositions in $C_d$.  To see how this all ties together we will use what we know from the previous section to produce generating functions in commuting variables for $\zeta$ and $\mu$.  This will allow us to consider the generating functions in terms of the norm of $\alpha$, $|\alpha|$.  If $n_k$ is the number of $k$'s in $\alpha$ then we may redefine $|\alpha|=\sum_{k\geq1}n_kk$.  Let $\alpha\leftrightarrow u$, then the {\it type} of $\alpha$ is $\tau(\alpha)=(n_1,n_2,\dots,n_n,r)$, where $r$ is the number of runs of $a$'s in $u$.

Each time $k$ appears in $u$ replace $k$ by $x^k$, where $x$ is a commuting variable.  Then we obtain the norm generating functions $$Z_d(\alpha;x)=\sum_{\alpha\leq \beta}x^{|\beta|}$$ and $$M_d(\alpha;x)=\sum_{\alpha\leq\beta}\mu(\alpha,\beta)x^{|\beta|}.$$

To avoid cumbersome formulas and because these generalize simply to any $d$ we will focus on the case when $d=3$.  If $\alpha\in C_4$ corresponds to $u\in A_3^*$ then any $a$ that is not immediately followed by a $b$ represents a 1 from $\alpha$ and $b$, $bb$, and $bbb$ represent 2,3, and 4 respectively.  Let $[k]_x$ be the polynomial $1+x+\dots+x^{k-1}$.

Let $p_z(u;x)$ and $z(u;x)$ be the formal power series in $\mathbb{Z}\left\langle \left\langle x\right\rangle\right\rangle$ obtained from $z(u)$ and $p_z(u)$ respectively by replacing each letter in $p_z(u)$ and $z(u)$ by $x$ and multiplying the whole word by $x$.  We have that $Z_3(u;x)=xp_z(u;x)z(u;x)$.  Defining $p_m(u;x)$, $m(u;x)$ and $s_m(u;x)$ in a similar way gives us that $M_3(u;x)=xp_m(u;x)m(u;x)s_m(u;x)$.  Note the $x$ at the beginning of these takes care of the fact that we dropped the initial $a$ from $\phi(\alpha)$.

Suppose $u$ has type $\tau(u)=(n_1,n_2,n_3,n_4,r)$ then Lemma 4.1 gives us that $Z_3(u;x)$ is one of the following rational functions.  The first two correspond to $u$ beginning with $a$ and the last two correspond to $u$ beginning with $b$.  The first and third correspond to $u$ ending with $a$ and the second and fourth correspond to $u$ ending with $b$.

\begin{enumerate}
 \item $x\left(\frac{[4]_x}{1-x[4]_x}\right)\left(x([4]_x\right)^{n_1-r+1}\left(\frac{x[3]_x}{1-x}\right)^{n_2}\left(\frac{x^3[3]_x}{(1-x)^2}+\frac{x^2[2]_x}{1-x}\right)^{n_3}\left(\frac{x^4[3]_x}{(1-x)^3}+\frac{x^4[2]_x}{(1-x)^2}+\frac{x^3}{1-x}\right)^{n_4}$

\item $x\left(\frac{[4]_x}{1-x[4]_x}\right)\left(x[4]_x\right)^{n_1-r}\left(\frac{x[3]_x}{1-x}\right)^{n_2}\left(\frac{x^3[3]_x}{(1-x)^2}+\frac{x^2[2]_x}{1-x}\right)^{n_3}\left(\frac{x^4[3]_x}{(1-x)^3}+\frac{x^4[2]_x}{(1-x)^2}+\frac{x^3}{1-x}\right)^{n_4}$

\item $x\left(\frac{x[4]_x}{1-x[4]_x}+1\right)\left(x([4]_x\right)^{n_1-r+1}\left(\frac{x[3]_x}{1-x}\right)^{n_2}\left(\frac{x^3[3]_x}{(1-x)^2}+\frac{x^2[2]_x}{1-x}\right)^{n_3}\left(\frac{x^4[3]_x}{(1-x)^3}+\frac{x^4[2]_x}{(1-x)^2}+\frac{x^3}{1-x}\right)^{n_4}$

\item $x\left(\frac{x[4]_x}{1-x[4]_x}+1\right)\left(x[4]_x\right)^{n_1-r}\left(\frac{x[3]_x}{1-x}\right)^{n_2}\left(\frac{x^3[3]_x}{(1-x)^2}+\frac{x^2[2]_x}{1-x}\right)^{n_3}\left(\frac{x^4[3]_x}{(1-x)^3}+\frac{x^4[2]_x}{(1-x)^2}+\frac{x^3}{1-x}\right)^{n_4}$

\end{enumerate}
Again, if $u$ has type $\tau(u)=(n_1,n_2,n_3,n_4,r)$ then $M_3(u;x)$ is one of the following.  The first two correspond to $u$ beginning with $a$, $b$, or $bb$ and the last two corresponds to those $u$ beginning with $bbb$.  The first and third correspond to $u$ ending with $a$ and the second and fourth correspond to $u$ ending with $b$.

\begin{enumerate}

\item $x(1-x)\left(\frac{1}{(1+x)^r}\right)\left(1-\frac{x}{1+x}\right)^{n_1-r}x^{n_1-r+1}\left(1-\frac{x}{1+x}\right)^{n_2}\left(\frac{x^2}{1+x}(1-\frac{x}{1+x})\right)^{n_3}\left(\frac{x^3}{(1+x)^2}\right)^{n_4}\frac{1}{1+x}$

\item $x(1-x)\left(\frac{1}{(1+x)^r}\right)\left(1-\frac{x}{1+x}\right)^{n_1-r}x^{n_1-r}\left(1-\frac{x}{1+x}\right)^{n_2}\left(\frac{x^2}{1+x}(1-\frac{x}{1+x})\right)^{n_3}\left(\frac{x^3}{(1+x)^2}\right)^{n_4}\frac{1}{1+x}$

\item $x\left(1+\frac{x^2}{1-x^2}\right)\left(\frac{1}{(1+x)^r}\right)\left(1-\frac{x}{1+x}\right)^{n_1-r}x^{n_1-r+1}\left(1-\frac{x}{1+x}\right)^{n_2}\left(\frac{x^2}{1+x}(1-\frac{x}{1+x})\right)^{n_3}\left(\frac{x^3}{(1+x)^2}\right)^{n_4}\frac{1}{1+x}$

\item $x\left(1+\frac{x^2}{1-x^2}\right)\left(\frac{1}{(1+x)^r}\right)\left(1-\frac{x}{1+x}\right)^{n_1-r}x^{n_1-r}\left(1-\frac{x}{1+x}\right)^{n_2}\left(\frac{x^2}{1+x}(1-\frac{x}{1+x})\right)^{n_3}\left(\frac{x^3}{(1+x)^2}\right)^{n_4}\frac{1}{1+x}$
\end{enumerate}

The following theorem is now an immediate consequence of Lemma 4.1.

\begin{thm}  The norm generating functions $Z_3(u;x)$ and $M_3(u;x)$ for $u$ with type $\tau(u)=(n_1,n_2,n_3,n_4,r)$ are as stated above.  $\square$ \end{thm}

The author did not get a chance to explore whether there were nice generating functions for powers of $\zeta$.  These would be interesting because $\zeta^m(u,w)$ is the number of chains of length $m$ beginning with $u$ and ending with $w$.

We would to thank Anders Bj\"{o}rner and Richard Stanley without whose prior work this paper would not have been possible.

\bibliography{Bib}
\end{document}

config: arxiv


TITLE: Weird identity for the divergence theorem / Divergence theorem for matrices
QUESTION [0 upvotes]: Our students were tasked, using the divergence theorem $ \int_V \nabla \cdot \vec{F} \mathrm{d}^3 r = \int_{\partial V} \vec{F} \cdot \mathrm{d}\vec{a} $, to show that for any bounded, connected subset V of $\mathbb{R}^3$ with surface $\partial V$ the following identity holds:
$$\int_V \vec{r} \mathrm{d}^3r = \frac{1}{4} \int_{\partial V} \vec{r} \left( \vec{r} \cdot \mathrm{d}\vec{a} \right)$$
where
$$ \vec{r} = \begin{pmatrix}
x_1\\x_2\\x_3\\
\end{pmatrix}$$
Now, the sample solution considered the i-th component of the right hand side (using Einstein sum convention):
$$ \left( \frac{1}{4} \int_{\partial V} \vec{r} \left( \vec{r} \cdot \mathrm{d}\vec{a} \right) \right)_i = \frac{1}{4} \int_{\partial V} r_i r_j \mathrm{d}a_j = \frac{1}{4} \int_{\partial V} (r_i r_j) \mathrm{d}a_j \stackrel{Div. theorem}{=} \frac{1}{4} \int_V \partial_j (r_i r_j) \mathrm{d}^3r = \frac{1}{4} \int_V (\delta_{ij} r_j + 3r_i) \mathrm{d}^3r = \left(  \int_V \vec{r} \mathrm{d}^3r \right)_i  $$
On the other hand, many students used a corollary of the divergence theorem for gradient fields $ \int_V \nabla \phi \mathrm{d}^3 r = \int_{\partial V} \phi\mathrm{d}\vec{a} $ by realizing that for $\phi = \frac{1}{2} \left( x_1^2 + x_2^2 +x_3^2 \right) = \frac{1}{2} r^2 = \frac{1}{2} \left( \vec{r} \cdot \vec{r} \right) $ we find
$$ \int_V \vec{r} \mathrm{d}^3 r = \int_V \nabla \phi \mathrm{d}^3 r =  \int_{\partial V} \phi\mathrm{d}\vec{a} = \frac{1}{2} \int_{\partial V} \left( \vec{r} \cdot \vec{r} \right) \mathrm{d}\vec{a} $$
Now, if both identities are correct, then $$\frac{1}{4} \int_{\partial V} \vec{r} \left( \vec{r} \cdot \mathrm{d}\vec{a} \right) = \frac{1}{2} \int_{\partial V} \left( \vec{r} \cdot \vec{r} \right) \mathrm{d}\vec{a}$$
which looks temptingly similar. However, nobody was able to prove this relation and it is (to me) far from trivial to see why this relation should hold.
Can anybody either show where a mistake is hidden or prove that the last identity is correct?
I realize that the sample solution effectively applies the divergence theorem to the outer product of $\vec{r}$ with itself: $$\frac{1}{4} \int_{\partial V} \vec{r} \left( \vec{r} \cdot \mathrm{d}\vec{a} \right) = \frac{1}{4} \int_{\partial V} \vec{r} \otimes \vec{r} \cdot \mathrm{d}\vec{a} = \frac{1}{4} \int_{\partial V} \vec{r}
\, \vec{r}^T \cdot \mathrm{d}\vec{a} \stackrel{Div. theorem}{=} \frac{1}{4} \int_V  \nabla \cdot \left( \vec{r}
\, \vec{r}^T \right) \mathrm{d}^3r $$
which I find very curious. I did not know you could apply the divergence theorem to matrix-like objects, however, for every example we constructed we always found that the identitiy of the problem was correct.

REPLY [0 votes]: Notice for any constant vector $\vec{k}$, we have
$$\begin{align}
\nabla \times ( r^2 (\vec{k} \times \vec{r}) )
&= \nabla r^2 \times (\vec{k} \times \vec{r} ) +
r^2 \nabla \times( \vec{k} \times \vec{r} )\\
&= 2 \vec{r} \times (\vec{k} \times \vec{r} )
+ r^2 ((\nabla \cdot \vec{r}) \vec{k} - \color{red}{(\vec{k} \cdot \nabla  )\vec{r}})\\
&= 2 (r^2 \vec{k} - (\vec{k}\cdot \vec{r})\vec{r}) + (3-\color{red}{1})r^2 \vec{k}\\
&= 4 r^2 \vec{k} - 2(\vec{k}\cdot\vec{r})\vec{r}
\end{align}
$$
Divide by $8$, integrate over any surface $S$ and apply Stoke's theorem, we obtain
$$\begin{align} \vec{k} \cdot \left[ \frac12 \int_S r^2 d\vec{a} - \frac14 \int_S \vec{r} (\vec{r}\cdot d\vec{a})\right]
= & \frac18 \int_S( 4r^2 \vec{k} - 2(\vec{k}\cdot\vec{r})\vec{r}) \cdot d\vec{a}\\
= & \frac18 \int_S (\nabla \times ( r^2(\vec{k} \times \vec{r}))\cdot d\vec{a}\\
= & \frac18 \int_{\partial S} r^2(\vec{k} \times \vec{r})\cdot d\vec{r}
\end{align}
$$
When $S = \partial V$ is the boundary of some region $V$, the boundary of $S$ will be empty. This means the leftmost integral over $\partial S = \emptyset$ vanishes. As a result,
$$\vec{k} \cdot \left[ \frac12 \int_{\partial V} r^2 d\vec{a} - \frac14 \int_{\partial V} \vec{r} (\vec{r}\cdot d\vec{a})\right] = 0$$
Since this is true for all constant vector $\vec{k}$, what's inside the square bracket vanishes and
$$\frac12 \int_{\partial V} r^2 d\vec{a} = \frac14 \int_{\partial V} \vec{r} (\vec{r}\cdot d\vec{a})$$


TITLE: Diffeomorphic smooth structures on a topological manifold doesn‘t necessarily imply that the identity is a diffeomorphism
QUESTION [2 upvotes]: Let $M$ be a topological manifold. I can equip  $M$ with a smooth atlas $\mathscr{A}$ and a smooth atlas $\mathscr{B}$. If there exists a diffeomorphism $f$ between the two resulting smooth manifolds, it doesn‘t necessarily follow that the identity is a diffeomorphism. (This would imply that $\mathscr{A}\cup\mathscr{B}$ is a smooth atlas and I know counterexamples.)
But the composition of two diffeomorphisms is again a diffeomorphism and we have $\;\text{id}_M=f^{-1}\circ f$. Where am I thinking wrong?

REPLY [7 votes]: If $f : (M, \mathscr{A}) \to (M, \mathscr{B})$ is a diffeomorphism, then $f^{-1} : (M, \mathscr{B}) \to (M, \mathscr{A})$ is a diffeomorphism and hence $\operatorname{id}_M = f^{-1}\circ f : (M, \mathscr{A}) \to (M, \mathscr{A})$ is a diffeomorphism. However, that tells us nothing about whether $\operatorname{id}_M : (M, \mathscr{A}) \to (M, \mathscr{B})$ is a diffeomorphism or not.


TITLE: On the continuity of map $\Gamma$
QUESTION [2 upvotes]: Let $M$ be the space of right continuous functions $\ell: \mathbb R_+\to [0,1]$ that are non increasing s.t. $\ell(0)=0$. Define the map $\Gamma : M\to M$ by $\Gamma[\ell](t):=\mathbb P[\tau^{\ell}>t]$ for all $\ell \in M$ and $t\ge 0$, where  $\tau^{\ell}:=\inf\{t\ge 0: X^{\ell}_t\le 0\}$ and
$$X^{\ell}_t:=1+t+\int_0^t\frac{1}{1+\ell(s)}dW_s,\quad \forall t\ge 0.$$
Here $(W_t)_{t\ge 0}$ denotes a Brownian motion. Let $M$ be endowed with the topology as follow: $\ell^n$ converges to $\ell$ in $M$ iff $\lim_{n\to\infty}\ell^n(t)=\ell(t)$ for all points of continuity of $\ell$. Can we prove the continuity of $\Gamma$ with respect to this topology?
Remark : To prove $\{\inf_{0\le s\le t}X^{\ell}_s\le 0\}=\{\inf_{0\le s\le t}X^{\ell}_s< 0\}$, it suffices to use Lévy's characterization. More precisely, we can write $X^{\ell}_t=1+t+B_{\langle X^{\ell}\rangle_t}\equiv 1+t+B_{L(t)}$, where $B$ denotes a Brownian motion and $L(t):=\int_0^t ds/(1+\ell(s))^2$. Therefore
$$\inf_{0\le s\le t}X^{\ell}_t = \inf_{0\le u\le L(t)}\{1+L^{-1}(u)+B_t\},$$
which implies the desired result as $\inf_{0\le u\le L(t)}\{1+L^{-1}(u)+B_t\}$ admits a density.

REPLY [4 votes]: I believe we can. Let $\ell_n \to \ell$ in your topology, and fix $t_0 \in \mathbb R_+$. We show that $\Gamma(\ell_n)(t_0) \to \Gamma(\ell)(t_0)$. We work over the interval $[0, T]$ with $T > t_0$.
Step 1: We first note that $\ell_n$ converges to $\ell$ in measure.
Indeed, let $\varepsilon > 0$ be arbitrary. As $\ell$ is nonincreasing,  $\ell$ contains only jump discontinuities and for any $n > 0$, there exist only finitely many jumps with magnitude greater than $\frac{\varepsilon}{2^j}$. Cover these jumps with finitely many closed intervals $C_i^j$ of total length less than $\frac{\varepsilon}{2^j}$. Divide the complement into intervals $D_i^j$  on which $\ell$ varies by no more than $\frac{\varepsilon}{2^j}$, and consider the partition $\mathcal P_j ;= C_i^j \cup D_i^j$. Applying the pointwise convergence of $\ell_n$ to $\ell$ near the endpoints of the $C_i^n$ and the monotonicity of $\ell_n$ and $\ell$ now allows us to conclude.
Step 2: We show that $X^{\ell_n} \to X^{\ell}$ uniformly in probability.
Namely, that $$P(\sup_{s \in [0, T]} | X_t^{\ell_n} - X_t^{\ell}|
 \geq  \frac{1}{2^k}) \to 0.$$
To see this, note that we can write
$$X^{\ell}_t:=1+t+\int_0^t\frac{1}{1+\ell(s)} + g_n(s) \ dW_s \, \quad \forall t\ge 0.$$
with $g_n := \frac{1}{1 + \ell_n(s)} -  \frac{1}{1 + \ell(s)} \to 0$ in $L^2$. Whereby the aforementioned convergence follows from the convergence in measure of $\ell_n$ to $\ell$.
Note that $X_s^{\ell_n} - X_s^{\ell}$ is a martingale, and that $X_T^{\ell_n} - X_T^{\ell}$ is Gaussian with mean $0$, and variance $||g_n||_{L^2}$.
And so by Doob’s (sub)martingale inequality and symmetry of the Gaussian distribution, we have
$$P(\sup_{s \in [0, T]} | X_s^{\ell_n} - X_s^{\ell}|
 \geq  \frac{1}{2^k}) \leq 2^{k+1} E[(X_T^{\ell_n} - X_T^{\ell})^+] \to 0,$$
as $n \to \infty$.
Step 3: Conclusion.
Let $\varepsilon > 0$ be arbitrary. We note that by continuity of $X_n^{\ell}$ we can write the event $\{\tau^{\ell} > t\}$ as $$\bigcup_{k \in \mathbb N} A_k := \bigcup_{k \in \mathbb N} \{X_s \geq \frac{1}{k}, \ \forall s \in [0,t_0]\}.$$
By continuity from below, we have that for some $k_0 \in \mathbb N$ that $P(A_{k_0}) > P(\{\tau^{\ell} > t\}) - \frac{\varepsilon}{2}$.
Since $X^{\ell_n} \to X^{\ell}$ uniformly in probability, for all large enough $n$, we have
$$P(\sup_{s \in [0, T]} | X_s^{\ell_n} - X_s^{\ell}|
 \geq \frac{1}{2k_0}) < \frac{\varepsilon}{2},$$
so that for all $n > N$ we have
$$\Gamma(\ell_n)(t_0) = P(\{\tau^{\ell_n} > t_0\}) > P(A_{k_0} \cup \{\sup_{s \in [0, T]} | X_s^{\ell_n} - X_s^{\ell}| >   \frac{1}{2k_0}  \}^c) > P(\{\tau^{\ell} > t_0\}) - \varepsilon$$
For the reverse inequality, we argue similarly - we note that, up to $P$-null sets, we can write the event $\{\tau^{\ell} \leq t_0\}$ as
$$\bigcup_{i \in \mathbb N} \{\inf_{s \in [0, t_0)}\ X_s^{\ell} \leq -\frac{1}{i}\},$$
In order for the above representation to hold, we need to show that $\{\inf_{0\le s\le t}X^{\ell}_s\le 0\}=\{\inf_{0\le s\le t}X^{\ell}_s< 0\}$, up to a $P$-null set.
For this, it suffices to use Lévy's characterization. More precisely, we can write $X^{\ell}_t=1+t+B_{\langle X^{\ell}\rangle_t}\equiv 1+t+B_{L(t)}$, where $B$ denotes a Brownian motion and $L(t):=\int_0^t ds/(1+\ell(s))^2$. Therefore
$$\inf_{0\le s\le t}X^{\ell}_t = \inf_{0\le u\le L(t)}\{1+L^{-1}(u)+B_t\},$$
which implies the desired result as $\inf_{0\le u\le L(t)}\{1+L^{-1}(u)+B_t\}$ admits a density.
Thus with a similar calculation, we obtain $$\Gamma(\ell_n)(t) < P(\{\tau^{\ell} < t_0\}) + \varepsilon$$
for all large enough $n$.
Since $\varepsilon$ was arbitrary, we conclude that $\Gamma(\ell_n)(t_0) \to \Gamma(\ell)(t_0)$, as was to be shown.


TITLE: Splitting an evaluated complete graph
QUESTION [7 upvotes]: Suppose we are given a positive integer $k$. Let $K_k$ denote the complete (undirected and simple) graph with vertices $1, 2, \dots, k$. The set of edges of $K_k$ is the set $E_k = \{ \{ x,y \} \mid \ 1 \leq x < y \leq k\}$.
A valuation of $K_k$ is a function $\omega: E_k \rightarrow \mathbb Z$. A splitting of $K_k$ is a partition $\{ 1, 2, \dots, k \} = A \cup B$ of the vertices of $K_k$ into two nonempty sets $A$ and $B$.
Given a valuation $\omega$ of $K_k$ and a positive integer $n$, we call a splitting $A \cup B$ of $K_k$ $n$-valid, if the number $$\sum_{(x,y) \in A \times B}  \omega(\{ x,y \})$$ is divisible by $n$.
Using Ramsey's theorem, one can prove that for every positive integer $n$, there exists a positive integer $k$ such that the following condition holds:
For any valuation $\omega$ of $K_k$, there is a splitting of $K_k$ that is $n$-valid.
If there exists at least one, there has to exist a smallest $k$ satisfying the above condition which we denote by $\eta(n)$.
Using the Combinatorial Nullstellensatz from N. Alon, one can show that $\eta(p) = 2p$ for odd primes $p$.
I now want to know if $\eta(n) = 2n$ is true for every integer $n \geq 3$.

REPLY [2 votes]: The answer is NO, at least for $n=4$. I show here that $\eta(4) \leq 7$. So
let $\omega$ be a valuation on $K_7$ ; we will show that it is $4$-valid.
First, we need some notation :  for $A \cup B$ a nontrivial partition
of $V=\lbrace 1,2,3, \ldots ,7\rbrace$, let
$$
s(A,B)=\\sum_{(x,y) \in A \times B}  \omega(\{ x,y \}), \ f(A)=s(A,V\setminus A).
$$
We can now write some useful relations :
$$
f( i,j)=f(i)+f(j)-2\omega(i,j),
f(i,j,k)=f(i)+f(j)+f(k)-2(\omega(i,j)+\omega(i,k)+\omega(j,k))
$$
(where, for simplicity, we write $f(i)$ instead of $f(\lbrace i \rbrace)$,
$f(i,j)$ instead of $f(\lbrace i,j \rbrace)$, etc).
Assume, by contradiction, that $\omega$ is not $n$-valid. Then the values
of $f$ are all $1,2$ or $3$ modulo $4$. For convencience's sake, we now
take $\omega$ and $f$ to take values in $\frac{\mathbb Z}{4\mathbb Z}$.
By easy double-counting, the sum $f(1)+f(2)+f(3)+ \ldots +f(7)$ is even
(this is twice the sum of all the values of $\omega$), so that at least one
$f(i)$ is even. Then $f(i)=2$. So the set $X=\lbrace  i\in [1...7] | f(i)=2 \rbrace$
is not empty.
For any $i,j$ in $X$, we have $f(i,j)=4-2\omega(i,j)$, hence
$\omega(i,j)=1$ or $3$ and $2\omega(i,j)=2$ in both cases. If $X$ contained
more than two elements, we could find $i \lt  j \lt k$ in $X$ and compute
$f(i,j,k)=f(i)+f(j)+f(k)-2(\omega(i,j)+\omega(i,k)+\omega(j,k))=2+2+2-2-2-2=0$,
a contradiction. So $|X| \leq 2$.
Similarly, we show that the set $Y=\lbrace  i\in [1...7] | f(i)=1 \rbrace$
contains at most two elements. Reasoning as before, we have
$2\omega(i,j)=0$ for any $i \lt j$ in $Y$. Recall that some $x$ in
$[1...7]$ satisfies $f(x)=2$. We have
$f(x,i,j)=-2(\omega(x,i)+\omega(x,j))$. By the pigeon-hole principle,
if we had $|Y| \gt 2$ we cound find $i \lt j$ in $Y$ such that
$\omega(x,i)=\omega(x,j)$, hence $f(x,i,j)=0$, a contradiction. So $|Y| \leq 2$.
Using the symmetry $x \mapsto -x$ in $\frac{\mathbb Z}{4\mathbb Z}$,
we see that $|Y'| \leq 2$ where $Y'=\lbrace  i\in [1...7] | f(i)=3 \rbrace$.
So, we have shown that on $[1..7]$, $f$ takes each of its three values
($1,2$ or $3$ mod $4$) at most twice. This contradicts the pigeonhole principle
and finishes the proof.


TITLE: At what points is given function differenciable?
QUESTION [0 upvotes]: Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be defined by:
$$ f(x) =
\begin{cases}
x^2,  & x\in \mathbb{Q} \\
-x^2, & x\in \mathbb{R} \setminus \mathbb{Q}\\
\end{cases}$$
At what points is $f$ differentiable

REPLY [1 votes]: Hint 1: If $f$ is differentiable at $x=a$ then $a$ is continuous at $x=a$. This will lead to a single potential value of $a$ where the function could be differentiable.
Hint 2: At any point where $f$ could be differentiable, us the definition of the derivative to check if $f$ is differentiable or not.