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 finite abstract simplicial complex, then computes a basis for all the cohomology groups
in 6 lines. It assumes that G is a simplicial complex and that each set in it is ordered.
[This compares in length with basic computations in a triangle like finding the intersection of
the altitudes in a triangle. See this notebook.]
Code added March 8, 2018. The following code snipped appeared already in the
discrete Atiyah-Singer and Atiyah-Bott blog entry.
It is here a bit shortened and runs on general simplicial complexes rather than only on Whitney complexes of graphs.
For texts, see Isospectral deformation of the Dirac operator or (shortened)
An integrable evolution equation in geometry. The point of these results
is that if we let the Dirac operator of a simplicial complex evolve freely in its isospectral set, we always have a logistic
inflation story. You can try it out and see that space expands at first very fast (Distance is by Connes always accessible
through the Dirac operator and the deformation does not change the Hodge operator H=D^{2} so that classical physics does not change).
It looks a bit like cosmic inflation,
but we are here in pure mathematics (even in its finitist core as we deal with finite set of sets).
Without any further input, space evolves freely in its isospectral set.
The following deformation is the version which allows the operators to become complex so that we get to a discrete wave
(=Schroedinger equation) in the limit rather than a scattering situation. It is a deformation of an elliptic complex.
It is possible to define the evolution even in the larger division algebra:
of quaternions,
the largest associative division algebra. (The algebraic structure of primes in these algebras has some
affinity with the standard model).
(* Inflation through isospectral deformation, 5/2013 til 3/2018 *)
(* see arxiv.org/abs/1306.0060 and arxiv.org/abs/1306.5597 *)
T[A_]:=Module[{n=Length[A]},Table[If[i>=j,0,A[[i,j]]],{i,n},{j,n}]];
UT[{DD_,br_}]:=Module[{D1=T[DD]}, (* Upper triangular block *)
Do[Do[Do[D1[[br[[k]]+i,br[[k]]+j]]=0,{i,br[[k+1]]-br[[k]]}],
{j,br[[k+1]]-br[[k]]}],{k,Length[br]-1}];D1];
RuKu[f_,x_,s_]:=Module[{a,b,c,u,v,w,q},u=s*f[x]; (* Runge Kutta *)
a=x+u/2;v=s*f[a];b=x+v/2;w=s*f[b];c=x+w; q=s*f[c];x+(u+2v+2w+q)/6];
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,12];n=Length[G];fv=Delete[BinCounts[Map[Length,G]],1];
cn=Length[fv];br={0};Do[br=Append[br,Last[br]+fv[[k]]],{k,cn}]
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}];
e=Conjugate[Transpose[d]];DD=d+e; (* Have Dirac operator *)
M=1000; dt=4/M; u={}; (* Deformation with Runge Kutta *)
Do[d=UT[{DD,br}];e=Conjugate[Transpose[d]];
BB=d-e; CC=d+e; MM=CC.CC; b=DD-CC; VV=b.b;
B=BB+1.0*I*b; f[x_]:=B.x-x.B; DD=RuKu[f,1.0 DD,dt];
u=Append[u,Total[Abs[Flatten[Chop[d]]]]],{m,M}];
F[x_]:=If[x==0,0,-Log[Abs[x]]]; (* Plot the size of d *)
v=M*Table[F[u[[k+1]]]-F[u[[k]]],{k,Length[u]-1}]; ListPlot[v]
And here is the code to compute the interaction cohomology groups H^{p}_{k}(G)
for a simplicial complex G: see the
Paper [PDF].
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).