ICM2014: Emmanuel Candès on Aug14Thu

ICM2014 — Bhargava laudatio | Gowers's Weblog

Gotta read this



ICM2014 — Bhargava laudatio | Gowers's Weblog

A nice piece on the Fields medal

http://www.nytimes.com/2014/08/10/opinion/sunday/how-math-got-its-nobel-.html?hp&action=click&pgtype=Homepage&module=c-column-top-span-region®ion=c-column-top-span-region&WT.nav=c-column-top-span-region&_r=1

Quillen Notebooks | Clay Mathematics Institute

The Clay institute is making Quillen's notebooks available to the public!





Quillen Notebooks | Clay Mathematics Institute

The unspoken stresses of a research career

http://www.theguardian.com/higher-education-network/blog/2014/apr/05/academics-anonymous-research-stressful-job-depression

WIM Video: The Stable Marriage Problem

How to Fix Issues with MathJax and Blogger Preview

If you used MathJax on blogger you may have noticed that the preview  does not render the LaTex    output.  At the link below  you can find a simple way to fix it.



Clueless Fundatma: Issues with MathJax and Blogger Preview

Random convex polygons I.

It's been a long time since I last posted something here;    busy, not  having  something relevant to say, you name it.    lately I've been  excited by  all things probabilistic. Somehow I find this area fresh. The  fact that I am novice   may contribute to  this excitement.

A few months ago, in the coffee room of our department,  I stumbled   on an older Bulletin A.M.S and, since I did not have anything pressing to do, I opened it  and saw a nice survey by a  Hungarian mathematician   called  Imre Barany.   I was intrigued by the  title of this beautiful survey: Random points and lattice points in convex bodies.     I found many marvelous  questions there, questions that   never came close to my mind.

One of the problems mentioned  in that survey  was a problem posed and  solved by Renyi and Sulanke sometime in the 60s.    Unfortunately, their results were written  in German which for me  is synonym with  Verboten.     I tried to find  an English   source for this paper, and all my Google searches  were fruitless.     Still,  I was very curious how they did it.  So, armed with Google Translate, patience and curiosity I proceeded to read the first of their 3 papers.  What follows is  an exposition of a small part of the first paper.  For more details   you can look in the first paper of Renyi-Sulanke, that is, if you  know enough German to read a math paper.  First the problem. $\newcommand{\bR}{\mathbb{R}}$ $\DeclareMathOperator{\area}{Area}$


 Suppose that $C$ is a compact convex  region in the plane with nonempty interior. Assume  that  the origin is in the interior of $C$ and $\area(C)=1$.   Choose  $n$ points $P_1,\dotsc, P_n\in C$  randomly, independently  and uniformly distributed. (In technical terms,  we choose $n$ independent  $\bR^2$-valued random variables  with probability distribution $I_Cdxdy$, where $I_C$ is the characteristic function of $C$.)  We denote by $\Delta_n=\Delta_n(P_1,\dotsc, P_n)$ the convex hull of this collection of points.  This is a convex polygon and we denote by $V_n=V_n(P_1,\dotsc, P_n)$  its  number of  vertices, by $L_n=L_n(P_1,\dotsc, P_n)$ its perimeter and by $A_n=A_n(P_1,\dotsc, P_n)$ its area.  These are random variables and we denote by$\newcommand{\bE}{\mathbb{E}}$ $\bE(V_n)$, $\bE(L_n)$ and respectively $\bE(A_n)$ their expectations.  Reny and Sulanke asked to describe the behavior of these expectations as $n\to\infty$. $\newcommand{\bP}{\mathbb{P}}$

Surprisingly, the answer depends in a  dramatic fashion on the regularity  of the boundary $\newcommand{\pa}{\partial}$ $\pa C$ of $C$.   Here I only want to investigate the behavior of $\bE(V_n)$, the expected number of vertices of $\Delta_n$   when $\pa C$ is smooth and has positive curvature at every point.   The final answer is the asymptotic relation (\ref{RSv}).


For two points $P,Q\in C$ we denote by $L(P,Q)$ the line determined by them.  Denote by $\bP(P,Q)$ the probability that $(n-2)$  points chosen randomly  from $C$ lie on the side of $L(P,Q)$.  For $i\neq j$ we denote by $E_{ij}$  the event that all the points $P_k$, $k\neq i,j$ lie on the same side of  of $L(P_i,P_j)$.  


The first crucial observation, one that I missed because I am still not thinking as a probabilist,  is that

\begin{equation}
V_n=\sum_{i<j} I_{E_{ij}}.
\end{equation}
In particular,
\[
 \bE(V_n)=\sum_{i<j}\bE( I_{E_{ij}})=  \sum_{i<j}\bP(E_{ij}).
\]
Since the points $\{P_1,\dotsc, P_n\}$ are independent and identically distributed  we deduce that
\[
\bP(E_{ij})=\bP(E_{i'j'}),\;\;\forall i<j,\;\;i'<j'.
\]
We denote by $p_n$ the  common probability of the events $E_{ij}$. Hence
\begin{equation}
\bE(V_n)=\binom{n}{2} p_n.
\end{equation}
To compute $p_n =\bP(E_{12})$ we observe that
\[
 \bP(E_{12}) =\int_C\int_C \bP(P_1,P_2) dP_1dP_2.
\]
 The line $L(P_1,P_2)$ divides   the region $C$ into two regions $R_1, R_2$ with areas $a_1(P_1,P_2)$ and $a_2$.   The probability  that   $n-2$  random independent points from  $C$   lie in $R_1$ is  $a_1(P_1,P_2)^{n-2}$    and  the probability  $n-2$  random independent points from $C$  lie in $R_2$ is $a_2(P_1,P_2)^{n-2}$.  We set
\[
a(P_1,P_2):=\min\bigl\{ a_1(P_1,P_2),\;a_2(P_1,P_2)\}
\]
and we deduce that
\[
\bP(P_1,P_2)= a(P_1,P_2)^{n-2}+\bigl(\;1-a(P_1,P_2)\;\bigr)^{n-2},
\]
\begin{equation}
\bE(V_n)=\binom{n}{2}\int_C\int_C\Bigl\{ \; a(P,Q)^{n-2}+\bigl(\;1-a(P,Q)\;\bigr)^{n-2}\;\bigr\} dPdQ.
\end{equation}
Since $a(P,Q)^{n-2}\leq \frac{1}{2^{n-2}} $,  we deduce that
\begin{equation}
\bE(V_n)\sim \binom{n}{2} \int_C\int_C \bigl(1-a(P,Q)\bigr)^{n-2} dPdQ\;\;\mbox{as $n\to\infty$}.
\label{4}
\end{equation}
To proceed further we need to use a formula from integral geometry.     Renyi and Sulanke refer to another  German source, a book of integral geometry by  Blaschke.  Fortunately, there is a  very good English substitute to Blaschke's book  that contains a myriad of   exotic  formulas. I am referring of course to  Luis  Santalo's   classical monograph   Integral Geometry and Geometric Probability.  (Santalo was Blaschke's student.)

In  Chapter 4, section 1,  Santalo  investigates the   density of pairs of points, more precisely  the  measure $dPdQ$ used in (\ref{4}). More precisely,  he discusses a clever choice of coordinates  that is particularly useful in integral geometry.

The  line $L(P,Q)$ has a normal $\newcommand{\bn}{\boldsymbol{n}}$ $\bn=\bn(p,q)$
\[
 \bn =(\cos \theta,\sin \theta), \;\;\theta\in [0,2\pi],
\]
and it is described by a linear equation.
\[
 x\cos \theta+y\sin \theta = p,\;\;p\geq 0.
\]
Once we  fix a linear isometry $ T: L(P,Q)\to \bR $, we can identify  $P,Q$ with  two points  $t_1,t_2\in \bR$. Note that $|dt_1dt_2|$ and $|t_1-t_2|$ are independent of the choice of $T$.    Santalo  op. cit.  shows that
\[
|dPdQ|=|t_1-t_2|  |dp d\theta dt_1dt_2|.
\]
Now observe that the line  $L(P,Q)$ is determined only by the two parameters $p,\theta$ so we will denote it by $L(p,\theta)$.     Similarly, $a(P,Q)$ depends only on $p$ and $\theta$ and we will denote it by $a(p,\theta)$. We set
\[
p_0(\theta)=\max\{ s;\;\;s\geq 0, s\bn(\theta)\in C\,\bigr\}.
\]
We denote  by $S(p,\theta)$ the segment on $L(p,\theta)$ cut-out by  $C$ and by $\ell(p,\theta)$ its length.
\begin{equation}
\bE(V_n)\sim \binom{n}{2}\int_0^{2\pi}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\left(\int_{S(s,\theta)\times S(s,\theta)} |t_1-t_2|dt_1dt_2\right) dp d\theta.
\end{equation}
Observing that for any $\ell>0$ we have
\[
 \int_{[0,\ell]\times[0,\ell]}|x-y|dxdy=\frac{ \ell^3}{3}
\]
 we deduce
\begin{equation}
\bE(V_n)\sim \frac{1}{3}\binom{n}{2}\int_0^{2\pi}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\ell(s,\theta)^3dp d\theta.
\end{equation}
Now comes the  analytical part.   For each $\theta\in [0,2\pi]$ we set
\[
I_n(\theta):=\frac{1}{3}\binom{n}{2}\int_0^{p_0(\theta)}\bigl(1-a(p,\theta)\;\bigr)^{n-2}\ell(s,\theta)^3dp ,
\]
so that
\[
 \bE(V_n)\sim  \int_0^{2\pi} I_n(\theta) d\theta.
\]
Renyi and Sulanke  find the asymptotics of  $I_n(\theta)$ as $n\to \infty$ by a  disguised version of the  old reliable Laplace method. 

Fix $\theta\in [0,2\pi]$ and set $\newcommand{\ii}{\boldsymbol{i}}$ $\newcommand{\jj}{\boldsymbol{j}}$ $\bn(\theta)=\cos \theta \ii +\sin\theta\jj\in\bR^2$. Since the curvature   of $\pa C$ is  strictly positive there exists a unique point $P(\theta)\in \pa C$ such that the unit outer normal   to $\pa C$ at $P(\theta)$ is  $\bn(\theta)$.

For simplicity  we set $a(p):=a(p,\theta)$.  For  $p\in [0,p_0(\theta)]$ we denote by $A(p)=A(p,\theta)$  the  area of the cap of $C$  determined by the  line $L(p,\theta)$ and the tangent line to $\pa C$ at $P(\theta)$  $x\cos\theta+y\sin\theta=p_0(\theta)$. In  Figure 1 below,  this cap is the yellow region between the green and the red line.

Figure 1: Slicing a convex region in directions perpendicular to $\bn(\theta)$. The circle in red is the osculating circle to the boundary at the unique  point $P(\theta)$ where the unit outer normal is $\bn(\theta)$.

Observe that $ A(p)=a(p)$ as long as $A(p)\leq \frac{1}{2}$.  It could happen that $A(p)> \frac{1}{2}\area(C)=\frac{1}{2}$ for some $p \in [0,p_0(\theta)]$. In any case, the uniform convexity  of $\pa C$ shows that  we can find  $\newcommand{\si}{\sigma}$  $\si_0> 0$  and  $0<c<\frac{1}{2}$ with the following properties.
\begin{equation}
\si_0<\inf_{\theta\in [0,2\pi]} p_0(\theta) .
\end{equation}
\begin{equation}
a(p,\theta)=A(p,\theta),\;\;\forall  p\in [\si_0,p_0(\theta)].
\end{equation}
\begin{equation}
c<a(p,\theta)\leq\frac{1}{2},\;\;\forall  p\in [0,s_0].
\label{low}
\end{equation}
\begin{equation}
\frac{d\ell}{dp}<0\;\;\mbox{on $[\si_0,p_0]$}.
\end{equation}
We have
\[
I_n(\theta)\sim\frac{n^2}{6}\int_0^{p_0(\theta)}\bigl(1-a(p)\,\bigr)^{n-2} \ell(p) dp
\]
\[
=\underbrace{\frac{n^2}{6}\int_0^{\si_0}\bigl(1-a(p)\,\bigr)^{n-2} \ell(p) dp}_{=:I_n^0(\theta)}+\frac{n^2}{6}\underbrace{\int_{\si_0}^{p_0(\theta)}\bigl(1-a(p)\,\bigr)^{n-2} \ell(s) dp}_{=J_n(\theta)}.
\]
The condition (\ref{low})  implies that as $n\to\infty$ we have $I_n^0(\theta)=o(1)$, uniformly in $\theta$.  Thus
\begin{equation}
I_n(\theta)\sim\frac{n^2}{6} J_n(\theta),\;\;n\to\infty.
\end{equation}
We will use   Laplace's method  to   estimate $J_n(\theta)$.      We introduce a new variable $\tau=\tau(p)=p_0(\theta)-p$, $s\in [\si_0, p_0(\theta)]$ so that $\tau\in [0,\tau_0(\theta)]$, $\tau_0(\theta)=p_0(\theta)-\si_0$.   Geometrically, $\tau$ denotes the distance to the tangent line $L(p_0(\theta),\theta)$.

 We will denote by $L(\tau)$ the line  $L(p,\theta)$. Thus, as $\tau$ increases the line $L(\tau)$ moves away from the boundary point $P(\theta)$ and towards the origin.  Similarly, we set $a(\tau)=a(p)=a(p,\theta)$ etc. Hence
\[
J_n(\theta)=\int_0^{\tau_0} \bigl(1-a(\tau))^{n-2}\ell(\tau)^3 d\tau.
\]
Observe first that for  along the interval $[0,\tau_0]$ we have
\[
\frac{d a}{d\tau}=\frac{dA}{d\tau}=\ell(\tau).
\]
The line  $L(\tau)=L(p,\theta)$  intersects the osculating  circle   to $\pa C$ at $P(\theta)$ along a chord of length $\bar{\ell}(\tau)$.     We set $t:=\sqrt{\tau}$. From the definition of the osculating circle we deduce
\[
\ell(t)=\bar{\ell}(t)(1+o(1)),\;\;\frac{d\ell}{dt}=\frac{d\bar{\ell}}{dt}(1+o(1))\;\;\mbox{as $t\to 0$}.
\]
If $r=r_\theta$ denotes the radius of the osculating circle so that $\frac{1}{r_\theta}$ is the curvature of $\pa C$ at $P(\theta)$, then
\[
\bar{\ell}(\tau)= 2\sqrt{r^2-(r-\tau)^2}=2\sqrt{2r\tau-\tau^2}= 2\sqrt{\tau}\sqrt{2r-\tau}=2t\sqrt{2r-t^2}.
\]
Hence
\[
\frac{d\bar{\ell}}{dt}|_{t=0}=2\sqrt{2r}
\]
We denote the $t$-derivative by an upper dot $\dot{}$. Note that
\begin{equation}
\dot{a}=\frac{d\tau}{dt}\frac{da}{d\tau}= 2t\ell(t),\;\;\dot{\ell}(t)=\dot{\ell}(0)+O(t)=2\sqrt{2r}+O(t).
\label{dota}
\end{equation}
We deduce
\begin{equation}
J_n(\theta)=2\int_0^{t_0} \bigl( 1-a(t)\bigr)^{n-2} \ell(t)^3tdt,\;\;t_0=\sqrt{\tau_0}.
\end{equation}
Note that
\[
\ddot{a}(t)=2\ell(t)+2t\dot{\ell}(t),\;\;\frac{d^3a}{dt^3}=4\dot{\ell}(t)+2t\ddot{\ell}(t),
\]
so that
\[
a(0)=\dot{a}(0)=\ddot{a}(0)=0, \;\;\frac{d^3 a}{dt^3}|_{t=0}= 4\dot{\ell}(0)=8\sqrt{2r}.
\]
We deduce
\[
a(t)=\frac{8\sqrt{2r}}{6}t^3+O(t^4)=  \underbrace{\frac{4\sqrt{2r}}{3}}_{=:C(r)}\;\;t^3+O(t^4).
\]
We set
\[
\nu:=(n-2),\;\;  w_\nu(t)=  \bigl( 1-a(t)\bigr)^{\nu} \ell(t)^3t,
\]
\[
\frac{u}{\nu}:=C(r)t^3\iff t=\left(\frac{u}{C(r)\nu}\right)^{\frac{1}{3}}.
\]
Note that
\[
\ell(t)^3=\bigl( 2\sqrt{2r}t+O(t^2)\;\bigr)^3=(6C(r) t)^3 + O(t^4).
\]
Hence
\[
w_\nu(t)dt = \left( 1-\frac{u}{\nu} +O\left(\frac{u}{\nu} \right)^{4/3}\;\right)^\nu \left(\frac{((6C(r))^3}{C(r)\nu} u+ O\left(\frac{u}{\nu}\right)^{4/3}\;\right) \left(\frac{u}{C(r)\nu}\right)^{1/3}\left(\frac{1}{C(r)\nu}\right)^{1/3}\frac{1}{3}u^{-2/3} du
\]
\[
=\frac{(6C(r))^3}{3C(r)^{5/3}\nu^{5/3}}  \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du
\]
\[
=\frac{6^3C(r))^{4/3}}{3\nu^{5/3}} \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du
\]
Hence
\[
J_n(\theta)=\frac{6^3C(r))^{4/3}}{3\nu^{5/3}}\underbrace{\int_0^{u_\nu}  \left( 1-\frac{u}{\nu} +O\left( \frac{u}{\nu} \right)^{4/3}\;\right)^\nu u^{2/3} \left( 1+ O\left(\frac{u^{1/3}}{\nu^{1/3}}\right)\;\right) du}_{=:\hat{J}_\nu},\;\; u_\nu=\nu C(r)t_0^3.
\]
Now observe that
\[
\frac{6^3C(r)^{4/3}}{3}= \underbrace{\frac{1}{3}6^3 \left(4\sqrt{2}{3}\right)^{4/3}}_{=:Z_1}  r^{2/3}.
\]
 and
\[
\lim_{\nu\to\infty} \hat{J}_\nu=\int_0^\infty e^{-u} u^{2/3}=\Gamma(5/3).
\]
Thus
\[
J_n(\theta) \sim Z_1\Gamma(5/3)r^{2/3}\nu^{-5/3}\sim  Z_1\Gamma(5/3)r^{2/3}n^{-5/3},
\]
\[
I_n(\theta) \sim \frac{n^2}{6}J_n(\theta)\sim \frac{Z_1\Gamma(5/3)r^{2/3}}{6} n^{1/3}.
\]
Now observe that the curvature  at the point $P(\theta)$ is $\kappa(\theta)=\frac{1}{r_\theta}$.  hence
\[
I_n(\theta) \sim \frac{n^2}{6}J_n(\theta)\sim \frac{Z_1\Gamma(5/3)\kappa(\theta)^{-2/3}}{6} n^{1/3}
\]
 If we denote by $ds$ the arclength on $\pa C$, then, by definition
\[
\frac{d\theta}{ds}=\kappa(\theta)\iff  d\theta=\kappa ds.
\]
Thus
\begin{equation}
\bE(V_n)\sim \int_0^{2\pi} I_n(\theta) d\theta \sim  \frac{Z_1\Gamma(5/3)}{6} n^{1/3}\int_{\pa C} \kappa^{1/3} ds.
\label{RSv}
\end{equation}
This is one of Renyi-Sulanke's result.








Remark.  Before I close, let me mention that  the asymptotics of $\bE(V_n)$ for  $n$ large depends dramatically on  the regulariti of the boundary of $C$. For example, if $C$ itself is a convex polygon with $r$-vertices, then  Renyi-Sulanke show that
\[
\bE(V_n) \sim\frac{2r}{3}\log n.
\]
Compare this with the smooth case  when the convex hull is expected to have many more  vertices $\approx n^{1/3}$.

There are more to say about this  story. As the title indicates, I plan to return to it in a later post.

Open problems in math: a new, free, online journal, needs your help

http://opmath.org/index.php/opm

Great Lakes Geometry Conference

This will be a great event!

Great Lakes Geometry Conference

Why boycotting the assholes at Elsevier should be one of your New Year resolutions

We finally have a confirmation of the reason why Elsevier muzzles the libraries  concerning  the price they have to pay for an Elsevier subscription. Free markets work best when information flows freely. Apparently Elsevier believes that the more we know about their bussines, the more they would stink. Wouldn't it be awesome if some  economist submitted to  an Elsevier journal a research on the anti-market attitudes of  Elsevier, and then have this  rejected. That would be so meta. In any case,  below is Elsevier in its own words (hat tip to Tim Gowers)

http://svpow.com/2013/12/20/elseviers-david-tempest-explains-subscription-contract-confidentiality-clauses/

Academy Fight Song |Thomas Frank | The Baffler

This    is an interesting take of what's going on now in higher education.

Academy Fight Song | Thomas Frank | The Baffler

A Day of Triangulations. A conference around Manolescu's new result

A Day of Triangulations

The Fulton-MacPherson compactification of a configuration space

$\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\bZ}{\mathbb{Z}}$ $\DeclareMathOperator{\Bl}{\boldsymbol{Bl}}$

Suppose that $M$ is a real analytic manifold of dimension $m$. Fix a finite set $L$ of labels. For any subset $S\subset L$ we define the following objects.

•  The manifold $M^S$ consisting of  maps $S\to M$. We will indicate a point in $M^S$ as a collection $x_S:=(x_s)_{s\in S}$,  $x_s\in M$, $\forall s\in S$.
•  The configuration space $M(S)\subset $ consisting of injective maps $S\to M$.
• The  thin diagonal  $\Delta_S\subset M^S$ consisting of the constant maps $S\to M$.

The space of configurations $M(L)$ is an open subset of $M^L$. We want to construct   a certain  completion  $M[L]$ of $M(L)$ as a    manifold with corners.  This completion is known as the  Fulton-MacPherson compactification of $M$.  The completion $M[L]$ is compact when $M$ is compact.  We follow closely the approach   of Axelrod and  Singer, Chern-Simons perturbation theory.II,  J. Diff. Geom., 39(1994), 173-213.


We begin with some simple observations. Observe  that if $S\subset S'$, then we  have a natural projection $\pi_S: M^{S'}\to M^S$ which associates to a map $S'\to S$ its restriction to $S$

$$ M^{S'}\ni x_{S'}\mapsto x_{S}\in M^S. $$

$\newcommand{\hra}{\hookrightarrow}$  We set

$$ \Delta_S^L=\pi_S^{-1}(\Delta_S)\subset M^L.$$

More explicitly, $\Delta_S^L$ consists of the maps $L\to M$ which are constant on $S$. Observe that

$$ M^L\setminus M(L)=\bigcup_{|S|\geq 2} \Delta_S^L. $$

For $x\in M$ and $S\subset M$ we denote by $x^S$ the constant map $S\to\lbrace x\rbrace$ viewed as an element in $M^S$. We can identify $x^S$ with a point in $x\in M$ so

$$ T_{x^S}M^S\cong (T_xM)^S. $$

The thin diagonal  $\Delta_S$ is a submanifold in $M^S$ of codimension $m(|S|-1)$.  We denote by $\newcommand{\eN}{\mathscr{N}}$ $\eN_S$ the normal bundle of the embedding $\Delta_S\hra M^S$.    The  fiber $\eN_S(x)$ of the normal bundle  $\eN_S=T_{x^S}M^S/T_{x^S}\Delta_S$ at a point $x^S$ is the quotient of $(T_xM)^S$ modulo the equivalence relation $\newcommand{\Llra}{\Longleftrightarrow}$

$$ (u_S)_{s\in S}\in (T_xM)^S\sim  (v_S)_{s\in S}\in (T_xM)^S\;\stackrel{def}{\Llra}\; (u_{s_0}-u_{s_1})=v_{s_0}-v_{s_1},\;\;\forall s_0,s_1\in S. $$

We identify $\eN_S(x)$ with the subspace of $Z_S(x)\subset (T_xM)^L$ consisting of vectors $v_L=(v_\ell)_{\ell\in L}$, $v_\ell\in T_xM$ such that

$$v_\ell=0,\;\;\forall \ell\in L\setminus S,\;\; \sum_{s\in S} v_s=0. \tag{1}\label{1}$$

We have a natural $\newcommand{\bsP}{\boldsymbol{P}}$  projector

$$ \bsP_S: (T_x M)^L\to Z_S(x) $$

defined as follows. For a vector $\vec{v}=(v_\ell)_{\ell\in L} \in (T_xM)^L$, we denote by $\newcommand{\bb}{\boldsymbol{b}}$ $\bb_S(\vec{v})\in T_xM$  the barycenter of its  $S$-component

$$\bb_S(\vec{v}):=\frac{1}{|S|}\sum_{s\in S} v_s\in T_x M, $$

and we set

$$\bsP_S(\vec{v}) =(\bar{v}_s)_{s\in S},\;\;\bar{v}_s:=v_s-\bb_S(\vec{v}),\;\;\forall s\in S,\;\;v_\ell=0. $$

Note that  for $u_S\in (T_xM)^S$ we have  $u_S\sim \bsP_S u_S$.

We denote by $\Bl(S,M)$ the radial blowup of $M^S$ along $\Delta_S$.  This is  manifold with boundary whose interior  is naturally identified with $M_*^S:=M^S\setminus \Delta_S$. $\newcommand{\bsS}{\boldsymbol{S}}$  Its  boundary is $\bsS(\eN)$, the "unit" sphere  bundle bundle of $\eN$.    Equivalently  we identify the fiber of $\bsS(\eN)$ at $x^S$ with the quotient

$$  \bsS(\eN(x^S))=\bigl(\; Z_S(x)\setminus 0\; \bigr)/\propto, $$

where

$$ u_S\propto v_S  \Llra \exists c>0:\;\; v_S=c u_S. $$


Following Fulton and MacPherson we will refer to the elements  in $Z_S(x)$ as $S$-screens at $x$.   Up to  a a positive rescaling, an $S$-screen  at $x^S\in \Delta_S$ is a collection of points  $u_S\in (T_xM)^S\setminus 0^S$  with barycenter at the origin.  If we fix a metric $g$ on $M$, then the fiber $\bsS\bigl(\;\eN(x^S)\;\bigr)$ that can be identified with the collection $v_L\in (T_xM)^L$ satisfying (\ref{1}) and



$$ \max_{s\in S}|v_s|=1. \tag{3}\label{3} $$


There is a natural   smooth surjection (blow-down map)

$$\beta_S:\Bl(S,M)\to M^S$$

whose restriction to the interior of $\Bl(S,M)$ $\DeclareMathOperator{\int}{\boldsymbol{int}}$ induces a diffeomorphism to $M^S_*$    We denote by $\beta_S^{-1}$ the inverse

$$\beta_S^{-1}: M_*^S\to \int \Bl(S,M). $$

For $x_S\in M_*^S$ we set $\newcommand{\ve}{{\varepsilon}}$

$$\hat{x}_S:=\beta_S^{-1}(x_S). $$

If

$$[0,\ve)\ni t\mapsto  x_S(t) \in M^S,\;\; x_S(0)=x_0^S\in\Delta_S $$

is a real analytic   path such that $x_S(t)\in M_*^S$ for $t>0$, then the limit $\lim_{t\searrow 0}\hat{x}_S(t)$ can be described as follows.

• Fix  local (real analytic) coordinate near $x_0$ so that the points $x_{s}(t)$ can be  identified with points in a neighborhood of $0\in\bR^m$.
• For $t>0$ denote by $\bb(t)$ the barycenter of the collection $(x_s(t))_{s\in S}\subset\bR^m$, $$\bb(t)=\frac{1}{|S|}\sum_{s\in S} x_s(t). $$
• For $t>0$  and $s\in S$  define  $\bar{x}_s(t) =x_{s}(t)-\bb(t)$,  $m(t)=\max_s|\bar{x}_s(t)|$.

Then $\lim_{t\searrow 0}\hat{x}_S(t)$ can be identified with the vector

$$\lim_{t\searrow 0}\frac{1}{m(t)} \bigl(\;\bar{x}_s(t)_{s_\in S}\;\bigr)\in  \eN(x_0^S). $$

We have a natural map $\newcommand{\eX}{\mathscr{X}}$

$$\gamma: M(L)\to \eX(M,L):=M^L\times\prod_{|S|\geq 2} \Bl(S,M),\;\; M(L)\ni x_L\mapsto \gamma(x_L):=\Bigl(\; x_L;\;\;(\hat{x}_S)_{|S|\geq 2}\;\Bigr)\in  \eX(M,L). $$


The Fulton-MacPherson compactification of $M(V)$ is the closure of $\gamma\bigl(\;M(L)\;\bigr)$ in $\eX(M,L)$.

We want to give a more  explicit description of this  closure.  Observe first that $\eX(M,L)$ and thus any point in the closure of $\gamma(M[L])$ can be approached from within $\gamma(M[L])$ along a real analytic path.  Suppose  that $(0,\ve)\ni t \mapsto x_L(t)$  is a real analytic path such that $\gamma\bigl(\; x_L(t)\;\bigr)$ approaches a  point $\gamma^0\in \eX(M,L)$. The limit point is a collection $( x^*_L,  (y(S))_{|S|\geq 2})\in \eX(M,L)$.



To the point $x^*_L\in M^L$ we associate an equivalence relation on $L$

$$\ell_0\sim_0 \ell_1 \Llra  x^*_{\ell_0}=x^*_{\ell_1}. $$

Denote by $\newcommand{\eC}{\mathscr{C}}$ $\eC_0\subset 2^S$ the collection of equivalence classes  of $\sim_0$ of cardinality $\geq 2$.

The  subsets $S$ of $L$ of cardinality $\geq 2$  are of two types.

1.  The set $S$ is not contained in  any of the equivalence classes in $\eC_0$, i.e., $\exists s_0,s_1\in S$ such that $x^*_{s_0}\neq x^*_{s_1}$. We will refer to such subsets as separating subsets.Then $y_S=\hat{x}_S^*$.
2.  The subset $S$ is contained in an equivalence class $C\in \eC_0$.   In other words  there exists $x^*(C)\in M$ such that $x^*_{s}=x^*(C)\in M$, $\forall s \in C$.  We will refer to such a subset as non-separating.  Then $y(S)$ is an $S$-screen  at $x^*(C)$, $y(S)=\bigl(\;y(S)_s\;\bigr)_{s\in S}$.

Fix an equivalence class $C\in\eC_0$. Here is  how one computes   $y_S$ for $S$ non-separating, $S\subset C$.  The point $x^*(C)^S\in\Delta^S$ is approached along the real analytic path

$$(0,\ve)\ni t\mapsto x_S(t)\in M(S). $$ 

Choose real analytic local coordinates  at $x^*(C)$ so a neighborhood of this point  in $M$  is identified with a neighborhood of $0$ in $\bR^m$.  We have Taylor expansions

$$ x_s(t) = v_s(1) t+v_2(2)t^2+\cdots ,\;\; s\in S. $$

For $k\geq 1$  and $s\in S$ we denote by $[x_s(t)]_k$ the $k$-th jet of $x_s(t)$ at $0$

$$[x_s(t)]_k:=\sum_{j=1}^k v_s(j) t^j. $$

For each   $k\geq 1$ we have an equivalence relation $\sim_k$ on $S$ given by

$$s \sim_k s'\Llra [x_s(t)]_k=[x_{s'}(t)]_k. $$.

We denote by $\sim_0$ the trivial equivalence relation  on $C$ with a single equivalence class $C$. Let $k=k_C(S)$ be the smallest $k$ such that $\sim_k$ is a nontrivial equivalence relation on $S$.  The integer $k_C(S)$ is called the separation order of $S$.  Then  the $S$-screen $y(S)$ is described as the projection

$$y(S)\propto \bsP_S v_S(k),\;\; v_S(k)=\bigl(\; v_s(k)\;\bigr)_{s\in S}. $$

Remark 1.   Suppose $S\subset S'\subset C\in \eC_0$  and $|S|\geq 2$.  Then  $k_C(S) \geq k_C(S')$. Moreover 

$$ k_C(S)=k_C(S') \Llra \bsP_Sy_{S'} \neq 0 \Llra y(S)\propto \bsP_S y(S').  $$

The condition $\bsP_S y(S)\neq 0$   signifies that    there exist $s_0,s_1\in S'$ such that

$$ y(S')_{s_0}\neq y(S')_{s_1}. $$

Note that if $S_0,S_1\subset C$, $|S_0|,|S_1|\geq 2$ then

$$ k_C(S_0\cup S_1)\leq \min\bigl\lbrace\; k_C(S_0),k_C(S_1)\;\bigr\rbrace. $$

Recall that we have a  sequence of equivalence relations $\sim_k$ on $C\in \eC_0$. They are finer and finer $\sim_k\prec \sim_{k+1}$, i.e.

$$  s\sim_{k+1}s'\Rightarrow s\sim_k s'. $$

Observe that 

$$ S\subset C,\;\;|S|\geq 2,\;\; k_C(S)>k \Llra   \mbox{$S$ is contained in an equivalence class of $\sim_k$.} \tag{4}\label{4} $$

Equivalently

$$ S\subset C,\;\;|S|\geq 2,\;\; k_C(S)\leq k \Llra \mbox{exist distinct equivalence classes $S_0,S_1$ of $\sim_k$ such that}\;\; S\cap S_0, S\cap S_1\neq \emptyset \tag{4'}\label{4'} $$

Let  $N_C$  denote the smallest  $N$ such that all the equivalence classes of $\sim_N$ consists of single points., i.e.,

$$ s \sim_N  s'\Llra s=s'. $$

Consider $\newcommand{\eS}{\mathscr{S}}$  the collection $\eS_C$ of all the equivalence classes  of cardinality $\geq 2$ of the relations $\sim_k$, $k\geq 0$  on $C$ . This is a nested family of subsets of $C$ i.e., if $S_0, S_1\in\eS_C$, then

$$ S_0\cap S_1 \neq \emptyset  \Llra S_0\subset S_1 \;\;\mbox{or}\;\;S_1\subset S_1. $$

Moreover $C\in \eS_C$.  Observe that if $S_0,S_1\in \eS_C$ and $S_0\subsetneq S_1$, then  $k_C(S_0)> k_C(S_1)$. Using  Remark 1 we deduce

$$ S_0,S_1\in \eS_C,\;\;S_0\subsetneq S_1 \Rightarrow   \bsP_{S_0}y(S_1)=0. \tag{5}\label{5} $$

Suppose  now that $S\subset C$ and $|S|\geq 2$. We set

$$\hat{S}=\bigcap_{S\subset S' \in\eS_C} S'. $$

In other words, $\hat{S}$ is the smallest subset in $\eS_C$ containing $S$. 

Lemma 2.  We have $k_C(S)= k_C(\hat{S})$.  

Proof. Observe first  we have  $k_C(S)\leq k_C(\hat{S})$.  Set $k_0 :=k_C(S)$.

If $k_C(\hat{S})> k_0$,  then (\ref{4}) implies  $\hat{S}$ is contained in an equivalence class of $\sim_{k_0}$. On the other hand $k_C(S)=k_0$   (\ref{4'}) implies   $S_0$ intersects nontrivially two  equivalence classes of $\sim_{k_0}$. This contradicts the condition $S\subset \hat{S}$. qed 

Using  Remark 1 we deduce 

$$  S\subset C,\;\;|S|\geq 2 \Rightarrow y(S)\propto \bsP_S y(\hat{S}). \tag{6}\label{6} $$

The   conditions (\ref{5}), (\ref{6})  describe  some compatibility conditions satisfied  by the screens $y(S)$, $S\subset L$ non-separating.


We can now form the family of subsets of $L$

$$\eS=\bigcup_{C\in\eC_0} \eS_C. $$

This also a nested  family  of subsets of cardinality $\geq 2$. A subset $S\subset L$ of cardinality $\geq  2$ is  called $\eS$-separating  if it is not contained in any of the sets of $\eS$. Otherwise it is called nonseparating.     For any separating set $S$ we denote by  $\hat{S}$ the smallest subset of $\eS$ containg $S$.  The limit point

$$c:=  \Bigl(\;x^*(L),  \bigl(\;y(S)\;\bigr)_{S\subset L,\;|S|\geq 2}\;\Bigr)\in\eX(M,L) $$ satifies the following conditions.

$$  y(S)\in  \beta^{-1}_S\bigl(\;M^S_*\;\bigr),\;\; \mbox{if  $S$ is separating}. \tag{$C_1$} \label{C1} $$

$$  y(S) \;\;\mbox{is an $S$-screen if $S$ is non-separating}. \tag{$C_2$} \label{C2} $$

$$  S_0,S_1\in \eS,\;\;S_0\subset S_1\Rightarrow \bsP_{S_0}y(S_1)=0. \tag{$C_3$}\label{C3} $$

$$    S\;\;\mbox{nonseparating} \Rightarrow  y(S)\propto \bsP_S y(\hat{S}). \tag{$C_4$}\label{C4} $$

Comments. (a) Let us recall that (\ref{C3}) signifies that the components $y(S_1)_s$ $s\in S_0$ are identical.

(b)  Let me say a few words  about the interpretation of the nested family $\eS$. A set  $S$    corresponds to a collection of distinct points in $(x_s)_{s\in S}$  in $M$ that is clustering ner a  point $x^*$. A subset   $S'$  corresponds   to a subcollection  of     the above collection that is clustering at a faster rate.

Running the above arguments in revers  one can  show that a collection

$$ \Bigl(\;x^*(L),  \bigl(\;y(S)\;\bigr)_{S\subset L,\;|S|\geq 2}\;\Bigr)\in\eX(M,L) $$

belongs to the closure of $\gamma\bigl(\;M(L)\;\bigr)$ in $\eX(M, L)$ if and only if there exists a nested collection $\eS$ of subsets of $L$ of cardinality    $\geq 2$   such that satisfying the  compatibility conditions (\ref{C1}-\ref{C4})    are satisfied.          The set $\eS$ is called the  type of the limit point.     For  a nested family $\eS$ of subsets  of $L$ of cardinality  $\geq 2$  we denote  Define  $M^(\eS)$ the collection of points of type $\eS$.


  The stratum $M(\eS)$ has codimension $|\eS|$. This can be seen after a tedious computation  that takes into account a  (\ref{C1}-\ref{C4}) .      To explain introduce a notation. Given $S, S'\in \eS$ we  say that $S$ precedes $S'$ and we write this $S\lessdot S'$, if     $S$ is maximal amomgst the subsets of $\eS$ contained but not equal to $S'$.     Denote by $\eS_{\max}$ the collection of maximal sets in $\eS$.  (The collection $\eS_{\max}$ coincides with the  collection $\eC_0$ in the above discussion.) The, if we recall that $\dim M=m$ and $|L|=n$ we deduce

$$\dim M(\eS)^* =m\left(\; n-\sum_{S\in\eS_{\max}}(|S|-1)\;\right) +\sum_{S\in \eS}\left[\;\;m\left(\;(|S|-1)-\sum_{S'\lessdot  S}\bigl(\;|S'|-1\;\bigr)\right)-1\;\right]$$


To understand this formula let us consider a point

$$ c =\Bigl(\;x^*(L),  \bigl(\;y(S)\;\bigr)_{S\subset L,\;|S|\geq 2}\;\Bigr)\in M(\eS)^*. $$

 The coordinates  of $x^*(L)$  are  described by $nm$ parameters Each $S\in \eS_{\max}$ introduces  the  constraints

$$x^*(L)_{s_1}=x^*(L)_{s_2},\forall s_1,s_2\in S. $$


If $S=\lbrace s_1,\dotsc,s_N\rbrace$ we    see that the above constraints are consequences of the linearly independent ones

$$ x^*(L)_{s_1}-x^*(L)_{s_2}= \cdots =x^*(L)_{s_{N-1}}-x^*(L)_{s_N}=0.  $$

These cut down the number of parameters  required to describe $x^*(L)$  by $m(N-1)=m(|S|-1)$.

Thus  the number of parameters need to describe $x^*(L)$ is

$m\left(\; n-\sum_{S\in\eS_{\max}}(|S|-1)\;\right)$


From (\ref{C3}) and (\ref{C4}) we deduce that the collection

$$  \bigl(\;y(S)\;\bigr)_{S\subset L,\;|S|\geq 2}$$

is uniquely determined by the subcollection

$$   \bigl(\;y(S)\;\bigr)_{S\in\eS} . $$

The screen  $y(S)$ belongs to the unit sphere  $\bsS(\eN(x_S))$ which has  dimension

$$\dim M^S-\dim\delta_S-1= m(|S|-1)-1. $$

Thus we need $m(|S|-1)$ parameters  to describe  the screen   $y(S)$.  However, the condition  (\ref{C3})   shows that any $S'\lessdot S$ induces  $m(|S'|-1)$  linearly independent constraints on these parameters so that $y(S)$  has a total of

$$m\left(\;(|S|-1)-\sum_{S'\lessdot  S}\bigl(\;|S'|-1\;\bigr)\right)-1 $$

degrees of freedom.






We want to describe a  neighborhood of $M(\eS)$ in $M[L]$.   We will achieve this via an explicit map

$$\Psi : M(\eS)\times \bR_{\geq 0}^{\eS} \to M[L] $$

defined as follows. Denote by $\vec{t}=(t_S)_{s\in\eS}$ the coordinates on $\bR^{\eS}_{\geq 0}$. For $S\in \eS$ we set

$$T_S=\prod_{\eS\ni S'\supseteq S} t_{S'}. $$


If

$$c = (x(c), (y(S,c))_{S\in\eS})\in  M(\eS),$$  then

$$\Psi(c, \vec{t})=  \bigl( x_\ell (c,\vec{t})\;\bigr)_{\ell \in L}, $$

where

$$ x_\ell(c,\vec{t})= x(c)_\ell +\sum_{\ell\in S\in \eS}  T_S y(S,c)_\ell.  $$

In the above formula  $y(S)$ is assumed to be a vector of norm $1$ in $Z_S(x_\ell)$.

Let us convince ourselves that for fixed $c_0\in M(\eS)$ there exists a  small neighborhood $U$ of $c_0$ in $M(\eS)$ and a neighborhood $V$ of $0\in\bR^{\eS}_{\geq 0}$   such that $\Psi$ maps $U\times  V_{>0}$ into $M(L)$. Here $V_{>0}-V\cap \bR^{\eS}_{>0}$.

Thus we have to show that if $i,j\in L$, $i\neq j$, then for $c$ close to $c_0$ and $\vec{t}$ close to $0$.

$$ x_i(c,\vec{t})\neq x_j(c,\vec{t}) $$

Note that  a set $S\in\eS$ that contains $i$ is either contained in $S_0$ or contains $S_0$. A similar  fact is true for $j$.  Observe that if $S\supset\neq S_0$ then $y(S,c)_i=y(S,c)j$. Thus
$$ x(c,\vec{t})_i-x(c,\vec{t})_j =\sum_{S\subsetneq S_0} T_S\bigl(\; y(S)_i-y(S)_j\;\bigr)+ T_{S_0}(y(S_0)_i-y(S_0)_j $$

$$  =T_{S_0}\left(\sum_{S\subsetneq S_0} \tau _S\bigl(\; y(S)_i-y(S)_j\;\bigr)+ (y(S_0)_i-y(S_0)_j\;\right), $$

where

$$\tau_S=\prod_{S\subset S'\subset\neq S_0} t_{S'}. $$

The conclusion follows by observing that $y(S)_i\neq y(S)_j$.

We denote by  $M[\eS]$ the closure  of  $M(\eS)$ in $M[L]$. Observe that

$$ M(\eS')\subsetneq M[\eS] \Llra \eS'\supsetneq  \eS. $$

The selected-papers network | Gowers's Weblog

The selected-papers network | Gowers's Weblog

Timeless advise from Gian-Carlo Rota

Most of you may have read  Rota's "Ten lessons I wish I had been taught".  However, if you   were not of drinking age when Rota regaled  us with his wisdom, please check  the link below.


alumni.media.mit.edu/~cahn/life/gian-carlo-rota-10-lessons.html#toc

Remarkable and unexpected progress in prime gap theory

This is a fascinating story about a mathematician "past his prime" taking the math world by surprise.

Yitang Zhang Proves 'Landmark' Theorem in Distribution of Prime Numbers | Simons Foundation

Plagiarism in Romanian academia

This is a piece  that I wrote one my non-mathematical blog and I thought it deserves some   exposure to a mathematical audience.

EpsilonBee: Plagiarism in Romanian academia

The weak Goldbach conjecture is settled.

Quoting Terry  Tao: "Busy day in analytic number theory; Harald Helfgott has complemented his previous paper http://arxiv.org/abs/1205.5252 (obtaining minor arc estimates for the odd Goldbach problem) with major arc estimates, thus finally obtaining an unconditional proof of the odd Goldbach conjecture that every odd number greater than five is the sum of three primes. "

On the pitfalls of "Open Access" publishing

The e-mail below from our library says it all.  (Emphasis is mine.)

"Dear Liviu Nicolaescu,

A request you have placed:

Journal of advanced research in statistics and probability
3  3     2011
Title: On the central limit theorem for $m$-dependent random variables with  unbounded $m$
Author: Shang, Yilun

TN: 685774

has been cancelled by the interlibrary loan staff for the following reason:

We have exhausted all possible sources.

This is so frustraing! [sic]  We haven't been able to find any library that has this journal,  Per the journal's website it is supposed to be Open Access meaning we should be able to get any of the articles online at no charge but their "archive" returns an empty screen with no way ot getting to the older journal issues.   We tried this on different days just to make sure it wasn't a one-day system problem.  We have not been able to find an email address for the author so that we could ask him directly.   We've found a number of other articles by this author on this subject but not this one.   We're just out of options on this one."

A cute application of Burnside's lemma

 I would like to discuss   a cute application of Burnside's lemma to a  question I learned on Mathoverflow.

First let me  present Burnside's lemma.

Burnside's lemma   Let $X$ be a finite set and $G$ a finite group acting on   $X$,
$$ G\times X\to X,\;\; (g,x)\mapsto g\cdot x. $$
Denote by $G\backslash  X$ be the space of orbits of this action. For each $g\in G$ we denote by $X^g$ the set of points in $X$ fixed by $g$
$$X^g:=\lbrace x\in X;\;\;g\cdot x=x\rbrace. $$
Then
$$ |G\backslash X|=\frac{1}{|G|} \sum_{g\in G} |X^g|,  $$
where $|A|$ denotes the cardinality of a set $A$.

Proof.   Look at the set $\newcommand{\bZ}{\mathbb{Z}}$ $\newcommand{\eF}{\mathscr{F}}$
$$ \eF = \bigl\lbrace (g,x)\in G\times X;\;\;g\cdot x= x\bigr\rbrace. $$
It defines a tautological double "fibration"
$$ G\stackrel{\ell}{\longleftarrow} \eF \stackrel{r}{\longrightarrow} X, $$
where the maps $\ell$ and $r$ are induced by  the canonical projections $G\leftarrow G\times X$ and $G\times X\to X$. We deduce

$$ \sum_{g\in G}|\ell^{-1}(g)|=|\eF|=\sum_{x\in X} |r^{-1}(x)|.  $$

Observe that the fiber $\ell^{-1}(g)$ can  be identified with the set $X^g$ so that

\begin{equation}
\sum_{g\in G}|X^g|=\sum_{x\in X} |r^{-1}(x)|. \tag{1} \label{1}
\end{equation}

For any $x\in X$ the fiber $r^{-1}(x)$ can be identified with the stabilizer $G_x$ of $x$,
$$ G_x=\bigl\lbrace g\in G;\;\; g\cdot x =x\bigr\rbrace. $$
If $x, y$ are in the same orbit of $G$ then $|G_x|=|G_y|$. Indeed, if $y=g\cdot x$ then $G_y=gG_xG^{-1}$.  

The function $x\mapsto |r^{-1}(x)|$ is  thus constant along the orbits of $G$ on $X$.   Thus the contribution of a single orbit $G\cdot x_0$ to the sum $\sum_x|r^{-1}(x)|$ is $|G_{x_0}|\cdot |G\cdot x_0|=|G|$. This  shows that

$$ \sum_{x\in X} |r^{-1}(x)|=  |G|\times \mbox{the number of orbits} =|G|\times |G\backslash X|. $$
 The desired conclusion now follows from (\ref{1}). $\Box$

I can now discuss the  problem that prompted this post. It is about certain  planar lattice walks.   The  allowable steps  of this  walk belong to the collection $\newcommand{\eS}{\mathscr{S}}$ $\newcommand{\be}{\boldsymbol{e}}$ $\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\bs}{\boldsymbol{s}}$

$$\eS=\lbrace \pm\be_1,\pm\be_2\rbrace\subset \bR^2,\;\;\be_1=(1,0),\;\;\be_2=(0,1). $$

A  walk   of length $n$ is then an ordered collection of steps
$$\vec{\bs}= (\bs_1,\dotsc, \bs_n)\in\eS^n. $$

The above walk is called admissible if

$$ \bs_j+\bs_{j-1}\neq 0,\;\;\forall  j=2,\dotsc, n. \tag{2}\label{2} $$


We denote by $\newcommand{\eA}{\mathscr{A}}$ $\eA_n$ the set of admissible   walks of length $n$. Since $\bs_1$ can be chosen in four different ways, while  each of  the   following  steps   can be chosen in  three different  ways so as to preserve (\ref{2}) we deduce

$$ |\eA_n|= 4\cdot 3^{n-1}. \tag{3}\label{3} $$

There is however a  symmetry in the story, i.e., a  group acting on $\eA_n$.     $\newcommand{\eO}{\mathscr{\eO}}$  Denote  by $G_0$ the subgroup of $O(2)$ generated by the reflections  $R_0, R_1, R_2$ where

$$R_0\be_1=\be_2,\;\;R_0\be_2=\be_1, $$

$$R_1\be_1=\be_1,\;\;R_1\be_2=-\be_2, $$

$$R_2\be_1=-\be_1,\;\;R_2\be_2=-\be_2. $$

This group has order $8$ and can be identified with the Weyl group of $O(4)$.

The group $G_0$ acts on $\bR^2$ and $\eS\subset \bR^2$ is a $G_0$-invariant subset.  In particular, $G_0$ acts on the set $\eS^n$ of walks of length $n$, and $\eA_n\subset \eS^n$ is $G_0$-invariant.  Observe that if $g\in G_0$ then

$$\eS^g= \begin{cases} \eS, & g=1\\
\{\pm \be_1\} & g=R_1,\\
\{\pm \be_2\}, & g=R_2\\
\emptyset,  & g\neq 1,R_1,R_2.
\end{cases} \tag{4} \label{4} $$

There exists another involution $R_3$ that acts on $\eS^n$. More precisely

$$R_3(\bs_1,\dotsc,\bs_n)=(\bs_n,\dotsc,\bs_1). $$

 Clearly $R_3\eA_n\subset\eA_n$.  We denote by $G$ the  subgroup  of the group of permutations of $\eA_n$ generated by $G_0$ and $R_3$. Since obviously  $R_3$ commutes with all of the reflections $R_0,R_1, R_2$ we deduce that  $G\cong G_0\times (\bZ/2). $

 

We would like to compute the number of orbits  of the action of $G$ on  $\eA_n$.     We denote by $p_n$ this number.    The final answer is contained in the equalities (\ref{odd}) and (\ref{even}) below which show different behaviors depending on whether $n$ is odd or even.   Here are   the details.

For any $\gamma\in G$ we  denote by $\eA_n(\gamma)$ the set of admissible paths of length $n$ fixed by $\gamma$ and we set  $p_n(\gamma):=|\eA_n(\gamma)|$.  From Burnside's lemma we  deduce

$$ p_n=\frac{1}{16} \sum_{\gamma\in G} p_n(\gamma).\tag{5}\label{5} $$

We need to compute the numbers $p_n(g)$.  We distinguish two cases.

A.  $\gamma\in G_0$.   If  $\gamma=1$, then

$$p_n(1)= |\eA_n|. $$

Suppose that  $\gamma\neq 1$. Then $\vec{\bs}\in\eA_n(\gamma)\subset \eS^n$ iff

$$ \gamma\bs_j=\bs_j,\;\;\forall j=1,\dotsc, n. $$

According to  (\ref{4}) the only   nontrivial   elements of $G_0$ that have fixed points when acting on $\eS$ are   $R_1$, $R_2$.  The only admissible paths  of  length $1$ that are $R_j$-invariant, $j=1,2$ are

$$(\be_j,\dotsc,\be_j),\;\;(-\be_j,\dotsc,-\be_j). $$  Hence, if $\gamma\in G_0$, then

$$ p_n(\gamma)=\begin{cases}
|\eA_n|, & \gamma=1\\
2, & \gamma=R_1,R_2,\\
0, & \mbox{otherwise}.
\end{cases} \tag{6}\label{6} $$

B.  $\gamma=(g,R_3)$, $g\in G_0$.

Hence $\newcommand{\Llra}{\Longleftrightarrow}$

$$ \vec{\bs}\in \eA_n(g, R_3)\Llra  R_3\vec{\bs}=g\vec{\bs}. $$

If $h\in G_0$,  $\vec{\bs}\in\eA_n(g,R_3)$ and $\newcommand{\si}{\boldsymbol{\sigma}}$ we set $\vec{\si} = h\vec{\bs}$, then

$$  R_3\vec{\si}= R_3 h \vec{\bs}= h R_3 \vec{\bs}= hg \vec{\bs}= hgh^{-1} \vec{\si}. $$

This shows that

$$|\eA_n(g,R_3)|=|\eA_n(hgh^{-1}, R_3)|,\;\;\forall g,h\in G_0.\tag{7}\label{7} $$

This shows that the  map $G_0\ni g\mapsto |\eA_n(g, R_3)|$ is constant on the conjugacy classes  of $G_0$.  Let us describe these conjugacy classes. It helps to observe that the morphism $\det :O(2)\to\{\pm 1\}$  induces a morphism

$$ \det :G_0\to\{\pm 1\} $$

and this morphism is constant on the conjugacy classes.       There exist two  conjugacy classes of determinant $-1$

$$ C(R_1)=\{ R_1, R_2=-R_1\},\;\; C(R_0)=\{R_0, -R_0\}.$$


The other conjugacy classes  are

$$ C_1=\{1\},\;\; C_{-1}= \{-1\}, \;\; C=\{ J, -J\}, $$

where $J= RR_1$ is the counterclockwise rotation by  $\pi/2$.   Thus  we need to compute the five numbers

$$p_n(\pm 1,R_3), \; p_n(R_1,R_3), \; p_n(R_0,\;  R_3), \; p_n(J, R_3). $$


We discuss them separately. Set $m:=\lfloor (n+1)/2\rfloor$

$\eA_n(1,R_3).$    A walk  $\vec{\bs}\in \eA_n(1,R_3)$ is determined by the initial segment  of length $m$ which could be an arbitrary  walk in $\eA_m$.

For $n$ even, $n=2m$,   a walk $\vec{\bs}\in \eA_n(1,R_3)$ if and only if it has the form

$$\vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,\bs_{m},\bs_{m-1},\dotsc, \bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$

For $n$ odd, $n=2m-1$,  a walk $\vec{\bs}\in \eA_n(1,R_3)$ if and only if it has the form

$$  \vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,\bs_{m-1},\dotsc, \bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$.

Hence

$$ p_n(1, R_3)=  |\eA_m|= 4\cdot 3^{\lfloor(n+1)/2\rfloor -1}. \tag{8}\label{8} $$


$\eA_n(-1,R_3).$        Such a path is again determined by the  initial segment  of length $m$.

For $n$ even, $n=2m$,   if  $\vec{\bs}\in \eA_n(-1,R_3)$, then

$$\vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,-\bs_{m},-\bs_{m-1},\dotsc, -\bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$

Clearly such a path is not admissible. Hence $\eA_m(-1, R_3)=\emptyset$ if $n$ is even.

If $n$ is odd,  $n=2m-1$, and $\vec{\bs}\in\eA_n(-1,R_3)$, then $\bs_m=-\bs_m$.  Not possible!.

 Hence

$$ p_n(-1,R_3)=0,\;\;\forall n. \tag{9}\label{9} $$


$\eA_n(R_1,R_3). $   A path $\vec{\bs}=(\bs_1,\dotsc,\bs_n)\in\eA_n(R_1, R_3)$    is  determined by  initial segment  of length $m$.

For $n$ even, $n=2m$,   if  $\vec{\bs}\in \eA_n(-1,R_3)$, then

$$ \vec{\bs}=(\bs_1,\dotsc, \bs_{m-1},\bs_m,R_1\bs_{m},R_1\bs_{m-1},\dotsc, R_1\bs_1),\;\;(\bs_1,\dotsc,\bs_m)\in\eA_m. $$

Such a path is admissible if and only if $\bs_m+R_1\bs_m\neq 0$, i.e., $\bs_m=\pm\be_1$.  The number of admissible paths  $(\bs_1,\dotsc,\bs_m)$ which end with $\bs_m=\pm\be_1$  is $2\cdot 3^{m-1}$.


For $n$ odd, $n=2m-1$,   if  $\vec{\bs}\in \eA_n(-1,R_3)$, then

$$\vec{\bs}=(\bs_1,\dotsc,\bs_{m-1}\,\bs_m, R_1\bs_{m-1},\dotsc, R_1\bs_1),\;\;\bs_m=R_1\bs_m.$$

 We deduce

$$ p_n(R_1,R_3) =2\cdot 3^{m-1},\;\;m=\lfloor(n+1)/2\rfloor.  \tag{10}\label{10} $$

$\eA_n(R_0,R_3). $   Arguing as above  we deduce that if $(\bs_1,\dotsc,\bs_n)\in\eA(R_0,R_3)$     and  $n$ is odd, then $R_0\bs_m=\bs_m$ which is impossible because $R_0$ does not have fixed points on $\eS$.

For $n$ even, $n=2m$, $\vec{\bs}=(\bs_1,\dotsc,\bs_n)\in \eA_n(R_0,R_3)$ if and only if

$$\vec{\bs}=(\bs_1,\dotsc,\bs_{m-1}\bs_m,R_0\bs_m, R_0\bs_{m-1},\dotsc, R_0\bs_1),\;\; (\bs_1,\dotsc,\bs_m,R_0\bs_m)\in \eA_m. $$

Whatever $\bs_m\in\eS$, we have $\bs_m+R_0\bs_m\neq 0$. We deduce

$$ p_n(R_0, R_3)=\begin{cases}
0, & n=2m-1\\
4\cdot 3^{m-1}, & n=2m.
\end{cases} \tag{11}\label{11} $$


$\eA_n(J,R_3). $  We observe that

$$(\bs_1,\dotsc,\bs_n)\in\eA_n(J, R_3)\Llra (J\bs_n,\dotsc, J\bs_1)=(\bs_1,\dotsc,\bs_n). $$


This implies  $J^2\bs_n=\bs_n$ which is obviously impossible.  Hence

$$ p_n(J, R_3) =0,\;\;\forall n. \tag{12}\label{12} $$

Using (\ref{5})  and (\ref{6}) we deduce

$$ p_n=\frac{1}{16}\Bigl( 4\cdot 3^{n-1}+4 +p_n(1,R_3)+ p_n(-1,R_3)+ 2p_n(R_1,R_3) +2p_n(R_0,R_3) +2p_n(J)\Bigr) $$

$$= \frac{1}{16}\Bigl( 4\cdot 3^{n-1}+4 +p_n(1,R_3)+ 2p_n(R_1,R_3) +2p_n(R_0,R_3) \Bigr). $$

Using  (\ref{8}), (\ref{9}), (\ref{10}), (\ref{11}), (\ref{12})  in the  above  equality we  deduce  the following.

If $n=2m-1$, then

$$ p_n= \frac{1}{16}\Bigl( 4\cdot 3^{n-1} + 4 + 8\cdot 3^{m-1}\Bigr) = \frac{1}{4}\bigl(\,3^{n-1}+2\cdot 3^{m-1}+1\bigr).\tag{$\ast$}\label{odd}$$

If $n=2m$, then

$$ p_n=   \frac{1}{16}\Bigl( 4\cdot 3^{n-1} + 4 + 16\cdot 3^{m-1}\Bigr) =  \frac{1}{4}\bigl(\,3^{n-1}+4\cdot 3^{m-1}+1\bigr). \tag{$\ast\ast$}\label{even}$$

Divided differences

I stumbled on this concept in an beautiful old paper of  Feller.    This seems to be well known to numerical analysts, but since  this construction got me out of a jam I thought it would nice to advertise it.  Most of what follows is from the    Milne Thompson's  classic "The Calculus of Finite Differences".

 To start, suppose $\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\bZ}{\mathbb{Z}}$  that $f:\bR\to \bR$ is a smooth function. For any  pairwise distinct points $x_0, x_1,\dotsc,x_n$ we define recursively

$$ f[x_0] :=f(x_0),\;\; f[x_0,x_1]:=\frac{f(x_1)-f(x_0)}{x_1-x_0}, $$

$$ f[x_0,x_1,\dotsc, x_n] :=\frac{f[x_1,\dotsc,x_n]-f[x_0,\dotsc, x_{n-1}]}{x_n-x_0}=\frac{f[x_0,\dotsc,x_{n-1}]-f[x_1,\dotsc, x_n]}{x_0-x_n}.\tag{R}\label{R} $$

The   quantity $f[x_0,\dotsc, x_n]$ is called the $n$-th divided difference of $f$ at the nodes $x_0,\dotsc, x_n$.  Note that we have

$$  f[x_0,x_1]= \frac{f(x_0)}{x_0-x_1}+\frac{f(x_1)}{x_1-x_0}.$$


Observe that

$$ f[x_1,x_2]- f[x_0,x_1]= \frac{f(x_1)}{x_1-x_2}+\frac{f(x_2)}{x_2-x_1}- \frac{f(x_0)}{x_0-x_1}-\frac{f(x_1)}{x_1-x_0} $$

$$ =\frac{f(x_2)}{x_2-x_1}+\frac{f(x_1)(x_2-x_0)}{(x_1-x_2)(x_1-x_0)} - \frac{f(x_0)}{x_0-x_1}.$$

We deduce

\begin{equation}
 f[x_0,x_1,x_2]=\frac{ f[x_1,x_2]- f[x_0,x_1]}{x_2-x_0}=\frac{f(x_0)}{(x_0-x_1)(x_0-x_2)}+\frac{f(x_1)}{(x_1-x_2)(x_1-x_0)}+ \frac{f(x_2)}{(x_2-x_0)(x_2-x_1)}\tag{I}\label{I}.
\end{equation}

Arguing inductively  we  obtain the following  description

$$ f[x_0, x_1,\dotsc, x_n]=\frac{f(x_0)}{(x_0-x_1)(x_0-x_2)\cdots (x_0-x_n)}+\frac{f(x_1)}{(x_1-x_0)(x_1-x_2)\cdots(x_1-x_n)}+\cdots + \frac{f(x_n)}{(x_n-x_0)\cdots (x_n-x_{n-1})}. $$

This last expression can be given a more symmetric   expression by introducing the polynomial

$$ \Phi_{x_0,\dotsc,x_n}:=\prod_{k=0}^n (x-x_k).$$

We then have

$$\Phi'_{x_0,\dotsc, x_n}(x)=(x-x_1)\cdots (x-x_n)+(x-x_0)(x-x_2)\cdots (x-x_n)+\cdots +(x-x_0)\cdots (x-x_{n-1}),  $$

$$ f[x_0, x_1,\dotsc, x_n]=\sum_{k=0}^n\frac{f(x_k)}{\Phi'_{x_0,\dotsc,x_n}(x_k)}.\tag{1}\label{1} $$

The last  equality  shows  has the following useful consequence.

Proposition 1.  The $n$-th divided difference  $f[x_0,\dotsc, x_n]$  does not change if we permute the nodes $x_0, x_1,\dotsc, x_n$. $\Box$


The equality   (\ref{1}) can be conveniently  rephrased in terms of Vandermonde-like determinants.    Denote by $V(x_0,\dotsc, x_n)$ the $(n+1)\times (n+1)$ matrix

$$ V(x_0, \dotsc, x_n)=\left[
\begin{array}{ccccc}
1 & 1 & 1 &\cdots & 1\\
x_0 & x_1 & x_2 &\cdots & x_n\\
x_0^2 & x_1^2 & x_2^2 & \cdots & x_n^2\\
\vdots &  \vdots & \vdots & \vdots & \vdots\\
x_0^n & x_1^n & x_2^n & \cdots & x_n^n
\end{array}
\right],
$$
and by $V_f(x_0,\dotsc, x_n)$ the $(n+1)\times (n+1)$ matrix

$$ V_f(x_0, \dotsc, x_n)=\left[
\begin{array}{ccccc}
1 & 1 & 1 &\cdots & 1\\
x_0 & x_1 & x_2 &\cdots & x_n\\
x_0^2 & x_1^2 & x_2^2 & \cdots & x_n^2\\
\vdots &  \vdots & \vdots & \vdots & \vdots\\
x_0^{n-1} & x_1^{n-1} & x_2^{n-1} & \cdots & x_n^{n-1}\\
f(x_0) & f(x_1) & f(x_2) & \cdots & f(x_n)
\end{array}
\right].
$$

Expanding along the last row of $V_f(x_0,\dotsc, x_n)$ we obtain  the following   alternate description of the $n$-th divided difference

$$ f[x_0,x_1,\dotsc, x_n]= \frac{\det V_f(x_0,\dotsc, x_n)}{V(x_0,\dotsc, x_n)}. \tag{V} $$

Next, we want to prove that $f[x_0,\dotsc, x_n]$   makes sense  even if the nodes  are not pairwise disjoint.     We need  to make    small technical  digression.

Consider the $n$-simplex

$$  \Delta_n :=\Bigl\{ (t_0,\dotsc, t_n)\in\bR^{n+1}_{\geq 0};\;\;\sum_{k=0}^n t_k=1\Bigr\}. $$

We can   view $\Delta_n$  as the graph of the function

$$ T_n\ni (t_1,\dotsc, t_n)\mapsto t_0=1-(t_1+\cdots +t_n)\in\bR, $$

where
$$ T_n:=\bigr\{ (t_1,\dotsc, t_n)\in\bR^n_{\geq 0};\;\; t_1+t_2+\cdots +t_n\leq 1\bigr\}. $$

If we use $(t_1,\dotsc, t_n)$ as coordinates on  $\Delta_n$, then  we deduce that  $dA_{\Delta_n}$,  the area    density on $\Delta_n$ is given by

$$ |dA_{\Delta_n}(t_1,\dotsc, t_n)|={\sqrt{n+1}} |dt_1\cdots d t_n|. $$

On $T_n$ we can introduce new coordinates

$$ s_1=t_1+\cdots +t_n, \;\; s_2= t_2+\cdots +t_n,\dotsc, s_n=t_n. $$

We observe that

$$ 0\leq s_n\leq \cdots \leq s_1\leq 1,\;\; dt_1\cdots dt_n=ds_1\cdots ds_n, $$

$$ t_1=s_1-s_2,\;\;t_2=s_2-s_3,\dotsc. $$

If $u: \Delta_n\to \bR$ is a continuous function,  then  we can regard it as a function of the  variables $s_1, \dotsc, s_n$ and we have

$$ \int_{\Delta_n} u(t_0,\dotsc, t_n) |dA_{\Delta_n}| = \sqrt{n+1}\int_{0\leq s_n\leq \cdots \leq s_1\leq 1} u(s_1, \dotsc, s_n) ds_1\cdots ds_n  $$

$$ ={\sqrt{n+1}}\int_0^1d s_1 \int_0^{s_1} ds_2  \cdots \int_0^{s_{n-1}} u(s_1,\dotsc, s_n) ds_n.$$

Hence

$$  \int_0^1d s_1 \int_0^{s_1} ds_2  \cdots \int_0^{s_{n-1}} u(s_1,\dotsc, s_n)=\frac{1}{\sqrt{n+1}}\int_{\Delta_n} u(t_0,\dotsc, t_n) |dA|. \tag{2} \label{2}$$

Proposition 2. (Hermite)   For any $n>0$ and  pairwise distinct  points $x_0,\dotsc, x_n\in\bR$ we have

$$ f[x_0,\dotsc, x_n]=\frac{1}{\sqrt{n+1}}\int_{\Delta_n} f^{(n)} (t_0x_0+\cdots +t_n x_n) dA(t_0,\dotsc, t_n). \tag{3} \label{3} $$

Proof.       In  view of (\ref{2}) we see that  (\ref{3})  is equivalent to

$$  f[x_0,\dotsc, x_n]= \int_0^1d s_1 \int_0^{s_1} ds_2  \cdots \int_0^{s_{n-1}} f^{(n)} (y_n) ds_n, \tag{4}\label{4}$$

where

$$ y_n=(1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-1}-s_n)x_{n-1}+ s_n x_n.\tag{5} \label{5} $$


For $n=1$ the right-hand-side of (\ref{4})  becomes

$$ \int_0^1 f'(x_0+t(x_1-x_0)) dt = \frac{1}{x_1-x_0} (f(x_1)-f(x_0))=f[x_0,x_1]. $$

We now proceed inductively  and we observe that

$$\int_0^{s_{n-1}} f^{(n)} (y_n) ds_n = \frac{1}{x_n-x_{n-1}} f^{(n-1)}\bigl(\; (1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-2}-s_{n-1})x_{n-2} +s_{n-1} x_n\;\bigr) $$

$$ -  \frac{1}{x_n-x_{n-1}}   f^{(n-1)}\bigl(\; (1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-2}-s_{n-1})x_{n-2}+s_{n-1} x_{n-1}\;\bigr). $$

Hence

$$ \int_0^1d s_1 \int_0^{s_1} ds_2  \cdots \int_0^{s_{n-1}} f^{(n)} (y_n) ds_n $$

$$= \frac{1}{x_n-x_{n-1}}  \int_0^1d s_1 \int_0^{s_1} ds_2  \cdots \int_0^{s_{n-2}}f^{(n-1)}\bigl(\; (1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-2}-s_{n-1})x_{n-2} +s_{n-1} x_n\;\bigr) ds_{n-1} $$

$$ -  \frac{1}{x_n-x_{n-1}}  \int_0^1d s_1 \int_0^{s_1} ds_2  \cdots \int_0^{s_{n-2}}  f^{(n-1)}\bigl(\; (1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-2}-s_{n-1})x_{n-2}+s_{n-1} x_{n-1}\;\bigr) ds_{n-1} $$

$$  \frac{1}{x_n-x_{n-1}}f[x_0,\dotsc,x_{n-2},x_{n}]-  \frac{1}{x_n-x_{n-1}}f[x_0,\dotsc, x_{n-2}, x_{n-1}] $$

$$ =  \frac{1}{x_n-x_{n-1}}f[x_0,\dotsc,x_{n-2},x_{n}]-  \frac{1}{x_n-x_{n-1}}f[x_{n-1}, x_0,\dotsc, x_{n-2}] $$

$$= f[x_{n-1}, x_0,\dotsc, x_{n-2}, x_{n}]= f[x_0,x_1,\dotsc, x_{n-1}, x_n].\;\;\Box $$

For fixed $f$, the $n$-th divided difference $f[x_0,\dotsc,x_n]$  defines a smooth  real valued function  on the confinguration space $\newcommand{\eC}{\mathscr{C}}$

$$ \eC_{n+1}=\bigl\lbrace\; (x_0,\dotsc, x_n)\in\bR^{n+1};\;\;x_i\neq x_j,\;\;\forall i\neq j\;\bigr\rbrace. $$


The above result shows that   this function admits a smooth extension to $\bR^{n+1}$.  This extension is unique since $\eC_{n+1}$ is dense in $\bR^{n+1}$.

The volume of the connected region

$$ S_n=\bigl\lbrace (s_1,\dotsc, s_n)\in\bR^n;\;\;0\leq s_n\leq \cdot \leq s_1\leq 1\;\bigr\rbrace  $$
is $\frac{1}{n!}$. Invoking  Proposition 2 we deduce that for any $x_0,\dotsc, x_n\in \bR$ there exists $\xi\in [\min x_j,\max x_k]$ such that
$$ f[x_0,\dotsc, x_n]=\frac{1}{n!} f^{(n)}(\xi). $$
In particular, this implies that
$$ f[\,\underbrace{x,\dotsc,x}_{n+1}\,]=\frac{1}{n!} f^{(n)}(x).\tag{6} \label{6} $$
The recurrence relation (\ref{R}) extends by continuity to any nodes $x_0,\dotsc, x_n$ not necessarily distinct.   Given the sequence of  nodes $x_0,\dotsc, x_n,\dotsc $ we  defined following  Feller  the sequence of polynomials $F_n(x)$

$$ F_n(x):=\sum_{k=0}^n f[x_0,\dotsc, x_k] (x-x_0)\cdots (x-x_{k-1}). $$


Observe  that

$$ F_0(x)= f(x_0),\;\; F_1(x)= F_0(x)+f[x_0,x_1)(x-x_0), ...$$

Define

$$ R_n(x)= f[x,x_0,\dotsc, x_n](x-x_0)\cdots (x-x_n). $$

Observe that

$$ R_0(x)=f(x)-f(x_0), $$

$$ R_{n}(x) =\bigl(f[x,x_0,\dotsc, x_{n-1}]- f[x_0,\dotsc, x_n]\bigr)(x-x_0)\dotsc (x-x_{n-1})= R_{n-1}(x) +\bigl(\, F_{n-1}(x)-F_n(x)\,\bigr)$$


We deduce that

$$ R_n(x) = R_0(x) + F_0(x)-F_n(x) $$

which translates  into Newton's interpolation formula

$$ f(x) = F_n(x) + R_n(x)$$

$$ = f(x_0)+f[x_0,x_1](x-x_0)+\cdots +f[x_0,x_1,\dotsc,x_n](x-x_0)\cdots (x-x_{n-1})+ f[x,x_0,\dotsc, x_n](x-x_0)\cdots (x-x_n). \tag{N} $$

Banff group shot

Graduate Student Conference at Notre Dame

11th Graduate Student Topology & Geometry Conference

A mathematician's lament

This is an oldie but goldie.


www.maa.org/devlin/LockhartsLament.pdf

Pierre Deligne wins the 2013 Abel Prize | Gowers's Weblog

Pierre Deligne wins the 2013 Abel Prize | Gowers's Weblog

Manolescu's new result on the triangulation conjecture

Ciprian Manolescu has a new paper on the archive  http://arxiv.org/abs/1303.2354

There he settles the longstanding  triangulation conjecture: in any dimension $n>3$ there exist nontriangulable compact topological manifolds. The approach is  the one opened in the  1980 by the Gaweski-Stern  Annals paper where they pointed out the relationship between this  conjecture and the existence of homology 3-spheres with Rochlin invariant  1 and having order two in the homology cobordism group.

This  new result of Manolescu is  big news indeed, provided that the details of the proof turn out  OK. As for the method, he goes back to his, not so distant, youth.

The work of Endre Szemerédi | Gowers's Weblog

The work of Endre Szemerédi | Gowers's Weblog

Whither Polymath? | Gowers's Weblog

Whither Polymath? | Gowers's Weblog

Calabifest - 28th Geometry Festival