The energy theorem tells that the sum over all g(x,y) is the Euler characteristic of a complex G, if g is the Green's function, the inverse of the connection matrix of G. Here is a rehearsal of 10/9/2017 for a talk on 10/10/2017. It was proven here and
generalized here.
I) The notation {(12),(23),(1),(2),(3)} saves curly brackets and commas in {{1,2},{2,3},{1},{2},{3}}.
II) The fact that omega(x) = i(x) is an index was understated a bit. It verifies in full generality that
the Euler characteristic is invariant under Barycentric refinement G -> (V,E)=(G,{(a,b) | a subset b or b subset a}).
This follows also from the eigenvector structure of the explicit Barycentric refinement operator involving Stirling
numbers. III) Integral geometric approaches to Gauss-Bonnet have tradition: the Blaschke-Chern-Banchoff
generation line illustrates this. I asked at various occasions what curvature we get if
P is the normalized volume measure on a compact Riemannian manifold and for every x,
the heat signature function y -> exp(-t L)(x,h) or the potentials y -> g(x,y) for the Green function
is taken. IV) A hyperbolic structure defines a Morse cohomology. Almost by definition, Morse
cohomology for the gradient flow of the dimension is simplicial cohomology of G.
V) The proof of the multiplicative Poincare-Hopf formula needs the valuation argument
that psi(G+x) = 0 if we glue a new cell along a complete complex. This can
be analyzed by looking at the cycle structure of det(L) which is the
Fredholm determinant det(1+A) of the adjacency matrix:
the Fredholm determinant of the adjacency matrix of a complete graph is zero.
VI) The talk mentions Boolean algebra. It is only a Boolean lattice. The fact that the class of subcomplexes
does not form a Boolean algebra is a stumbling block for proving unimodularity algebraically.
VII) In discrete McKean-Singer, str(L^-t))=X(G) only holds for t=1 unlike in the
Hodge case, where it is a manifestation of super symmetry. The multiplicative story does not have supersymmetry.
Actually, the energy is the discrepancy.
VIII) There is more to discrete potential theory: the uniform measure maximizes entropy.
One can look at the minimal energy mass on a subcomplex as in classical potential theory.
Entropy and Euler characteristic are both natural (uniqueness theorems of Shannon for entropy
and Meyer of Euler characteristic). It leads to Helmholtz free energy for which
catastrophic phase transitions (blue-sky and pitchfork bifurcations) occur when changing temperature.
Below is Mathematica code computing the energy and Euler characteristic for
a complex generated by a set A. The example given is the Klein bottle,
a complex of Euler characteristic 0, Fermi characteristic 1 and f-vector (8,24,16). To the
right, is the graph G_{1} whose Whitney complex
is the Barycentric refinement as a complex. We think in the graph.
Almost all textbooks of the 20th century treat graphs as 1-dimensional
simplicial complexes. There is more to them.
Graphs carry many interesting simplicial complex structures.
Historically, in the Petersburg bridge problem which was the birth of graph theory,
Euler introduced graphs as a model of a 2-dimensional CW complex. The point of view
of topological graph theory is to see the 2-dim cells from a graph embedding.
For general networks, a natural Whitney clique complex offers itself, rather than the 1-skeleton which
treats a graph as a one-dimensional "curve". One can think of a simplicial complex structure on a graph
in a similar way as a topological or measure theoretical or order or sheave theoretical structure
on a set. If nothing is given on a graph, the most natural complex, the Whitney complex offers itself.
On the other hand, given a simplicial complex or more generally a CW complex, one has a graph G1: the vertices
of G1 are the sets of G, two vertices are connected, if one is contained in the other.
Talking about a unit sphere in G1
is more intuitive than talking about links or other constructs introduced to the language
of simplicial complexes. The fact that the Barycentric refinement of an arbitrary complex is a
Whitney complex assures that one can focus on graphs.
Omega[x_]:=-(-1)^Length[x]; DJ[a_,b_]:=DisjointQ[a,b];
EulerChi[G_]:=Total[Map[Omega,G]];
FermiPhi[G_]:=Exp[Total[Log[Map[Omega,G]]]];
Generate[A_]:=Delete[Union[Sort[Flatten[Map[Subsets,A],1]]],1]
CL[G_]:=Table[If[DJ[G[[k]],G[[l]]],0,1],{k,Length[G]},{l,Length[G]}];
Energy[G_]:=Total[Flatten[Inverse[CL[G]]]];
A={{2,3,7},{1,2,3},{1,3,5},{1,5,7},{1,4,7},{2,4,6},{1,2,6},{1,6,0},
{1,4,0},{2,4,0},{3,4,7},{3,4,6},{3,5,6},{5,6,0},{2,5,0},{2,5,7}};
G = Union[Map[Sort,Generate[A]]]; L = CL[G];
Print[{Det[L],FermiPhi[G]}]; Print[{Energy[G],EulerChi[G]}];
And here is a tweeted
140 Character code of the Energy computation of the example given in the talk:
Update December 2017: And here is self-contained demo code to
"hear the Euler characteristic".
Generate a random complex G, compute the number Pos of positive eigenvalues
and the number Bos of even dimensional simplices. We also recompute
Euler, Energy, Fermi and Fredholm:
(*"Hear the Euler characteristic of a complex", O.Knill,12/1/2017*)
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[10,12];n=Length[G]; Dim=Map[Length,G]-1;
Fvector=Delete[BinCounts[Dim],1]; Vol=Total[Fvector];
L=Table[If[DisjointQ[G[[k]],G[[l]]],0,1],{k,n},{l,n}];
Pos=Length[Position[Sign[Eigenvalues[1.0*L]],1]];
Bos=Length[Position[Flatten[Map[OddQ,Map[Length,G]]],True]];
Fer=n-Bos; Euler=Bos-Fer; Fred=Det[1.0*L]; Fermi=(-1)^Fer;
Energy=Round[Total[Flatten[Inverse[1.0 L]]]];
Checks={Energy,Fred,Pos,Energy==Euler,Fred==Fermi,Pos==Bos,Vol==n}
Update January 2018: And here is self-contained demo code for the
Green Star formula,
which was found late January 2018,
after,
some,
struggle.
It gives an explicit formula for the Green function g(x,y) in terms of the intersection of the stars of x and y:
(* The Green Star Formula", O.Knill, 1/27/2018 *)
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];
EulerChiComplex[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]]] EulerChiComplex[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]
(* Hydrogen", O.Knill, 2/4/2018, http://arxiv.org/abs/1802.01238 *)
sort[x_]:=Sort[{x[[1]],x[[2]]}]; v=5;e=10; (* size of the graph *)
Gra=RandomGraph[{v,e}]; bracket[x_]:={x}; f={v,e}; q=v+e;
Q=Union[Map[sort,EdgeList[Gra]],Map[bracket,VertexList[Gra]]];
G=Map[bracket,Range[q]]; (* start building Barycentric refinement*)
Do[If[SubsetQ[Q[[k]],Q[[l]]] && k!=l,G=Append[G,{k,l}]],{k,q},{l,q}];
G=Union[Map[Sort,G]]; v=q; n=Length[G];
(* have built now a random Barycentric refined 1-dim complex G *)
Orient[a_,b_]:=Module[{z,c,k=Length[a],l=Length[b]},
If[SubsetQ[a,b] && (k==l+1),z=Complement[a,b][[1]];
c=Prepend[b,z]; Signature[a]*Signature[c],0]];
d=Table[0,{n},{n}]; d=Table[Orient[G[[i]],G[[j]]],{i,n},{j,n}];
Dirac=d+Transpose[d]; H=Dirac.Dirac; (* Hodge Laplacian is built *)
L=Table[If[DisjointQ[G[[k]],G[[l]]],0,1],{k,n},{l,n}];
R=DiagonalMatrix[Table[If[k<=v,(-1)^Length[Q[[k]]],1],{k,n}]];
Total[Flatten[Abs[R.(L-Inverse[L]).R - H]]]
Code included on February 17, 2018. See
this blog entry. There
is still the question how to "hear" the cohomology from the spectrum. The following code
generates a random complex, then computes a basis for all the cohomology groups in 6 lines.
(* "Cohomology in 6 lines", February 16, 2018, Oliver Knill *)
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[10,16];n=Length[G]; Dim=Map[Length,G]-1;f=Delete[BinCounts[Dim],1];
Orient[a_,b_]:=Module[{z,c,k=Length[a],l=Length[b]}, If[SubsetQ[a,b] &&
(k==l+1),z=Complement[a,b][[1]];c=Prepend[b,z];Signature[a]*Signature[c],0]];
d=Table[0,{n},{n}]; d=Table[Orient[G[[i]],G[[j]]],{i,n},{j,n}];
Dirac=d+Transpose[d]; H=Dirac.Dirac; f=Prepend[f,0]; m=Length[f]-1;
U=Table[v=f[[k+1]];Table[u=Sum[f[[l]],{l,k}];H[[u+i,u+j]],{i,v},{j,v}],{k,m}];
Cohomology=Map[NullSpace,U]; Betti=Map[Length,Cohomology]
Here the first preparation board when organizing and outlining the energy talk.
Update from February 7, 2018 (2/7/18, Euler day!). A blackboard
for a talk
Polishing Euler's Gem (youtube) proving in detail that the
Euler characteristic of a d-sphere is (1+(-1)^{d}). There
are also some Slides (youtube)
authored for that talk but not shown. And
preparation
notes (2 pages PDF) giving the proof. The Euler gem formula is
referred to and used at various places in the proof of the energy theorem.
It is important that this result is rock solid and not just
an "evolutionary version of a theorem" in the sense of Lakatos. (By the way, to see the
struggle with this theorem, one should refer to Dieudonné's book on the history of
algebraic topology. Poincaré definitely did not know yet how to prove the general
Euler gem theorem in arbitrary dimensions properly, nor was he able to sort out the (from today standards)
the rather sloppy treatment of "deformation" concept, which was prevalent at the time of
Poincaré. Homotopy theory came later). Even today, where things have been
made rigorous in the continuum, referring to the classical result in topology (as one could certainly do),
would be a categorical betrayal: in order to prove a result in finite combinatorics, one should not
have to refer to a mathematics which is built on a larger (and possibly inconsistent) axiom system.
But it is also a matter of taste and relevant from the point of view of reverse mathematics: we should not really
need the infinity axiom to prove a theorem about finite sets! For a computer scientist it is
also nice and important to work always with the full mathematical structure and not just with
numerical approximations to a continuum theory (even if they are done rigorously).