Green Star Formula

[Update, January 5, 2018: In “listening to the cohomology of graphs”, the Green star formula is mentioned.]

It is now almost a year old, the struggle to find a general formula for the Green function values $g(x,y) = L^{-1}(x,y)$, where $L(x,y)$ is the connection matrix of an abstract finite simplicial complex $G$. Remember that $L(x,y)=1$ of the simplices $x$ and $y$ intersect and $L(x,y)=0$ if $x$ and $y$ do not intersect. In the “Gauss Bonnet connection” we got the diagonal entries. We then found more “Green function values”. And November 2017 there was an other attempt in that quest for a Green function formula. The quest is over. The formula uses the “star” St(x) of a simplex x, which is the set of all $y \in G$ which contain $x$. The star makes up the vertices of the unstable sphere $S^+(x)$ in the Barycentric refinement of $G$. Define x+y as the symmetric difference of the sets x and y. This is standard notation as together with the intersection, we have a Boolean ring of sets.

Green Star Formula: $g(x,y) = (-1)^{{\rm dim}(x+y)} \chi( St(x) \cap St(y) )$.

In particular, the Euler characteristic of the star of $x$ is the Green diagonal entry: $\chi(St(x))=g(x,x)$.

[Remark added January 30, 2018: One could also write $(-1)^{{\rm dim}(x+y)} = \omega(x) \omega(y)$, which is a notation we will probably use more. Also, about notation, it make sense to see the star St(x) as the unstable manifold $W^+(x) = \{ y | x \subset y \}$ so that one also can look at $W^-(x) = \{ y | y \subset x \}$. The matrix
$$ M(x,y) = \omega(x) \omega(y) \chi(W^-(x) \cap W^-(y)) $$
is nothing else than a signed version of the connection matrix. It is orthogonally conjugated to the connection matrix $L$. It is nice that the inverse of $L$ is the Green’s function
$$ g(x,y) = \omega(x) \omega(y) \chi(W^+(x) \cap W^+(y)) $$
Thinking in terms of dynamical systems, one also would have to look at “heteroclinic points”, intersections of stable and unstable manifolds. But this is not that interesting as $\chi(W^+(x) \cap W^-(y))$ is $0$ for $x \neq y$ and equal to $\omega(x)$ if $x=y$. All of these intersection values of stable and unstable manifolds can be both interpreted as curvatures or as energy values. It is natural to think of the matrix entries as curvatures as summing up these matrix values always gives a combinatorial invariant, either Euler characteristic or Wu characteristic. [A combinatorial invariant is a quantity which is invariant under Barycentric subdivision (a definition, I found first mentioned in a paper of Bott from 1952. It is an elegant notion as it bypasses topology.)] By the way, also the set of curvature values should now be combinatorial invariants. We had only established that for the diagonal entries of the Green’s function.] As seen here both Euler and Wu characteristic have curvatures also located on the zero-dimensional part of the simplicial complex (just shove things down to zero dimensions!). These are then more familiar curvatures. In the discrete, for graphs, the curvature has already been used by Heesch in the context of graph colorings almost a hundred years ago. The Gauss-Bonnet-Chern formula for graphs (covered here more than 6 years ago) is the Euler chararacteristic case. The general formula (mentioned in the introduction of that article) has already been mentioned earlier by Norman Levitt a reference I had only found later. I call it in the universality paper the “Gauss-Bonnet-Chern-Levitt” formula. But as pointed out in the Wu paper, the formula is very general and leads to Gauss-Bonnet results for any linear or multi-linear valuation. Wu characteristics are examples of multi-linear valuations.

Gauss Bonnet interpretation of Energy:

Summing up intersection values of unstable manifolds gives Euler characteristic (Energy theorem)
Summing up intersection values of stable manifolds gives the Wu characteristic (this is the definition)
Summing up intersection values of stable and unstable manifolds gives the Euler characteristic (this is the definition)


End of remark added. ]

I call it the “Green star formula” because the Green function entries are related to the stars. The theme picture for this section shows our Lemon tree at home, which carries now 10 small green lemmons which are currently our “stars”. The tree had some trouble during the late fall in the rather erratic Massachusetts weather but now happily spends the winter in our warm living room. We take great care of it and even pollinated the flowers by hand using a toothbrush as there are no bees … so much about lemon tree sex … Note that unless the analogue stable star $St^-(x) = \{ y | y \subset x \}$, the star $St(x) = St^+(x) = \{ y \in G | x \subset y \}$ is not a simplicial complex in general. It is a set of sets, all right, but not every subset is there. This was actually the reason, why we looked far to far away most of the time: we were looking for formulas involving sub-simplicial complexes of $G$. It often almost worked, but not quite and our previous blog entries illustrate this. The formula actually makes one believe in the beauty of mathematics as it is a simple formula. To illustrate this, we can write
$$ L(x,y) = \chi(St^-(x) \cap St^-(y)) $$
showing that the matrix entries of $L$ are related to the stable part of simplices (which are simplicial complexes) while the Green function entries refer to the unstable part of simplices (which are not simplicial complexes in general). The Euler characteristic of a set $A$ of subsets of $G$ of course is still defined as $\chi(A) = \sum_{x \in A} \omega(x)$, where $\omega(x)=(-1)^{{\rm dim}(x)}$ with ${\rm dim}(x)=|x|-1$.

The Green star formula is of course proven with Cramer by deleting column x and row y and computing the determinant. It can be done by induction by removing an other simplex z and show that when adding that simplex both sides get multiplied with the same factor $(1-\chi(S(z)))$ by the multiplicative Poincaré-Hopf result which already proved the unimodularity theorem. One has still to check some initial seeds.

Apropos: Sajal Kumar Mukherjee and Sudip Bera recently found a new elegant proof of the unimodularity theorem by seeing directly what happens if a new vertex is added to the simplicial complex. (My own proof has added single cells). Mukherjee and Bera actually found the proof I had been looking for in vain for 9 months in 2016 (interrupted a bit by some experiments in number theory). My own proof of the unimodularity theorem can be found here.

Let us explain how the above formula ties in with the diagonal entry formula $g(x,x) = 1-\chi(S(x))$. We have seen that in general, the unit sphere S(x) is a Zykov sum of the stable and unstable part $S(x) = S^-(x) + S^+(x)$ which is sort of a hyperbolicity. It is explained in the proof of the energy theorem telling that $\sum_{x} \sum_{y} g(x,y)$ of all potential energies between two simplices is the Euler characteristic of $G$. This hyperbolic splitting produced a formula for the “genus” values of the stable and unstable parts: $g(x,x) = 1-\chi(S(x)) = (1-\chi(S^+(x))) (1-\chi(S^-(x)) = (1-\chi(S^+(x)) \omega(x)$. The Green Star formula tells in the case x=y that $g(x,x)= \chi(St(x))$: which is quite memorable:


The self interaction energy of a simplex is the Euler characteristic of its star.

Here is self-contained mathematica code which builds a random simplicial complex, computes the Green function with the Green star formula, then checks that it inverts L. The procedure S is the “star”. SQ abbreviates SubsetQ to keep the length of the code in “poem” size. I like the compact way in which the Mathematica language allows to write code, almost like pseudo code, but which actually runs, unlike Pseudo code. But together with what has been said above, it should be crystal clear what every line does, first build a random set of sets, generate from it a simplicial complex, then compute the stars of each simplex as well as the symmetric difference between the simplices, then build the matrix and check that it inverts the connection matrix L. The EulerChi procedure does not mind to be run on sets of sets which are not simplicial complexes. The reason, I had difficulties finding the formula (I had been using heavy data fitting procedures for example around Thanksgiving 2017 to find something and it was clear already then that intersections of stable and unstable manifolds matter), was that I always had been computed the Euler characteristic of the simplicial closures (any set of sets A defines a simplicial complex, the smallest super set which contains A which is a simplicial complex. This “closure” (implemented by “Generate” in the following Mathematicad lines) is similar of what one uses in topology where one generates a topology from a basis, or in measure theory where one generates a sigma algebrea from a smaller ring of sets). Now, the Euler characteristic of a closure of a set is not the same than the Euler characteristic of the set. For example, for A={{1},{1,2}}, the Euler characteristic is 0, while for its closure {{1},{1,2},{2}}, the Euler characteristic is 1. The evil thing is that for random complexes, especially in low dimensions, it is quite rare that things are different so that the closure formulas were often right but not always.

Generate[A_]:=Delete[Union[Sort[Flatten[Map[Subsets,A],1]]],1]
R[n_,m_]:=Module[{A={},X=Range[n],k},Do[k:=1+Random[Integer,n-1];
  A=Append[A,Union[RandomChoice[X,k]]],{m}];Generate[A]];
G=R[7,20];n=Length[G];SQ=SubsetQ; OmegaComplex[x_]:=-(-1)^Length[x];
EulerChi[GG_]:=Total[Map[OmegaComplex,GG]];
S[x_]:=Module[{u={}},Do[v=G[[k]];If[SQ[v,x],u=Append[u,v]],{k,n}];u];
SymmetricDifference[a_,b_]:=Union[Complement[a, b],Complement[b, a]];
K=Table[SymmetricDifference[G[[k]],G[[l]]],{k,n},{l,n}];
H=Table[Intersection[S[G[[k]]],S[G[[l]]]],{k,n},{l,n}];
h=Table[(-1)^Length[K[[k,l]]] EulerChi[H[[k,l]]],{k,n},{l,n}];
L=Table[If[DisjointQ[G[[k]],G[[l]]],0,1],{k,n},{l,n}];
h.L==IdentityMatrix[n]