# Message Boards

Answer
(Unmark)

GROUPS:

3

# [WWS21] Geometric constructions in discrete non-integer dimensional spaces

Posted 3 months ago

Standard differential geometry takes place on differentiable manifolds, which have constant, integer dimensions by construction. This is too constricting for the case where you need to deal with a discrete space which can limit to non-integer dimensional space, such as in Wolfram Models. Especial difficulty arises for the tensor formalism of differential geometry, whose indices takes integer values, corresponding to the integer dimensions of the manifold. It is expected that there will be multiple ways to define dot products, which leads to different definitions of orthonormality, which will expectedly have cascading implications for formulating definitions of curvature, tangent spaces and other features from standard differential geometry. This project will construct some definitions of an inner product of vectors in Wolfram Models and explore some of the consequences and features that come from it.
Introduction The concept of vectors is essential for constructing geometric formalisms in any space. Notions from Differential Geometry such as tangent spaces, parallel transport, a connection and more depend on a solid understanding of what vectors are. In a continuous space this is all well established and understood, and even in some discrete settings there have been work on defining and exploring it. The problem, however, comes when working in an arbitrary discrete space, which can also potentially have non-integer dimensions. Considering the scales that most vectors will operate on, and considering that dimension and curvature are statistical features that emerge from larger scale space, care was taken to make no assumption on curvature or dimension. In certain sections where readers might be worried that curvature could interfere, short explanations as to how it is avoided is given where possible. The generality obtained from this approach should also be of great value when studying spaces with fractal, or even varying dimension. The document here is meant as preliminary results, to be taken further in constructing a full theory of geometry on these discrete scales. Throughout various graphs will be used to show the ideas laid out. One that will be used extensively comes directly from the Wolfram Model, and is generated by a rule also used by Gorard. It is convenient since it is easy to visualise, and limits to something analogous to flat 2D space. The reader is however encouraged to substitute in graphs of their own to verify that the results obtained are general. Initializing a graph that will be used repeatedly: wm=ResourceFunction["WolframModel"];htg=ResourceFunction["HypergraphToGraph"];grph=UndirectedGraph[SimpleGraph[htg[wm[{{x,y,y},{z,x,u}}{{y,v,y},{y,z,v},{u,v,v}},{{1,1,1},{1,1,1}},500]["FinalState"]]]] Out[]= Initializing a graph that limits to a fractal dimension: frac=UndirectedGraph[SimpleGraph[htg[wm[{{{1,2,3},{1,4,5}}{{2,3,6},{2,3,6},{5,2,6}}},{{1,1,1},{1,1,1}},500]["FinalState"]]]] Out[]=
Vectors This project will consider three different ways of defining vectors in graphs (and generalizable to hypergraphs and possibly other discrete spaces).
1) Geodesic vectors One way to see vectors is as a geodesic from the origin vertex to a destination vertex, with the length of the vector then also corresponding to the geodesic's length. These vectors are completely described be an ordered set of vertices connected by edges { v i v 2 v f Showing one possible geodesic between two given vertices, unique from other geodesics between the same vertices. p1=FindShortestPath[grph,143,197];p2=FindShortestPath[frac,59,277];HighlightGraph[grph,Join[Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],p1],GraphHighlightStyle"Thick"]HighlightGraph[frac,Join[Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],p2],GraphHighlightStyle"Thick"] Out[]= Out[]=
2)Vertex vectors Here we define vectors by only specifying the origin and terminal vertex, with the length of the vector corresponding to the geodesic length between the vertices, but there is no specification of which geodesic corresponds to the vector. These vectors are completely described by an ordered pair of vertices { v i v f Showing that only the initial and final vertices matter for this definition. HighlightGraph[grph,{143,197},VertexSize4]GraphDistance[grph,143,197]HighlightGraph[frac,{59,277},VertexSize4]GraphDistance[frac,59,277] Out[]= Out[]= 4 Out[]= Out[]= 6
3)Abstract length vertex vectors Abstract length vertex vectors are very similar to normal vertex vectors, except we only take the vertex pair to specify something analogous to direction, with the length of the vector needing to be specified separately. These vectors are completely described by an ordered pair of vertices, and a specified length {{ v i v f n
Dot product Here we will explore possible ways of defining the dot product for the given definitions of vectors
1)Geodesic vectors Given the structure we get from defining vectors as geodesics, it allows us a unique construction of the dot product, analogous to dropping a perpendicular from one vector to the other, and then multiplying the length of the projected vector by the length of the vector projected onto to get the dot product. One problem that is immediately apparent, is that there might be multiple legitimate perpendiculars (of equal length) that would lead to different dot products. Here the convention of picking the one with the largest result is chosen. Represent perpendicular dropped between two vectors, and calculate the dot product between them : p1=FindShortestPath[grph,143,197];p2=FindShortestPath[grph,143,218];p3=FindShortestPath[grph,197,200];HighlightGraph[grph,{Join[Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],p1],Style[Join[Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],p2]],Style[Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}]]},GraphHighlightStyle"Thick"]dt=0;shrt=Infinity;l1=Length[p1]-1;e1=p1[[l1+1]];For[i=Length[p2],i≥1,i--,If[GraphDistance[grph,e1,p2[[i]]]<shrt,shrt=GraphDistance[grph,e1,p2[[i]]];dt=(i-1)*l1;]];Print["The dot product here is:",dt] Out[]= The dot product here is:12 There are some obvious issues to this definition. The most severe is that the dot product between vectors with angle more than 90° between them will be 0. There is also the issue that this dot product does not neccesarily commute, and that it sometimes won't give well behaved answers if the perpendicular is dropped from a long vector to one significantly shorter. A possible remedy for both these issues would be to define that the perpendicular is always dropped to the longer vector, although equal lengthed vectors might still not commute. All of this will be covered in the analysis below.
2)Vertex vectors Here we don't have the nice structure of geodesics to work with, so something a bit more abstract will be necessary. We can use a method analogous to the cosine rule in euclidean geometry, and motivate that it would be valid even in the presence of curvature. c μ a μ b μ c μ μ c a μ b μ μ a μ b ||c 2 || 2 || 2 || a μ μ b μ a b μ 2 g μν μ a ν b 2 || 2 || 2 || a•b= ||a 2 || 2 || 2 || 2 Define a function to compute the dot product between two vertex vectors In[]:= vertexdot[graph_,or_,v1_,v2_]:=(GraphDistance[graph,or,v1]^2+GraphDistance[graph,or,v2]^2-GraphDistance[graph,v1,v2]^2)/2 Represent ' triangle' formed by two vectors, and calculate the dot product between them : v1={143,197};v2={143,218};p1=FindShortestPath[grph,143,197];p2=FindShortestPath[grph,143,218];p3=FindShortestPath[grph,197,218];HighlightGraph[grph,{Join[Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],v1],Join[Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],v2],Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}]},GraphHighlightStyle"Dotted",VertexSize3]Print["The dot product is:",vertexdot[grph,v1[[1]],v1[[2]],v2[[2]]]] Out[]= The dot product is:8 Another possibility arises, in which we can construct something between vertex vectors and geodesic vectors, wherein we identify a vector as the set of all geodesics between two given vertices, where we can take the dot product to be the average of the geodesic dot products between the corresponding sets of geodesics. This can, of course, become extremely computationally expensive for vectors with high geodesic degeneracy, even though they should converge in the limit. It is therefore more of a conceptual tool than a suggestion for a way to practically compute dot products. It also inherits most of the problems of the normal geodesic dot products. We will, however, use this conceptual tool extensively in the section discussing the continuum limits, since it is easy to see how both geodesic- and vertex vectors converge to it. Studying this construction’s characteristic behaviour, therefore, is analogous to studying the behaviour of the other constructions. Showing the multiple possible geodesics possible between two given vertices wm=ResourceFunction["WolframModel"];htg=ResourceFunction["HypergraphToGraph"];rl={{{1,1,2},{1,3,4}}{{4,4,3},{2,5,3},{2,5,3}}};grph2=UndirectedGraph[SimpleGraph[htg[wm[rl,{{1,1,1},{1,1,1}},250]["FinalState"]]]];v1=1;v2=97;pth=FindPath[grph2,v1,v2,GraphDistance[grph2,v1,v2],All];HighlightGraph[grph2,Table[Join[Table[pth[[i]][[j]]pth[[i]][[j+1]],{j,1,Length[pth[[i]]]-1}],pth[[i]]],{i,1,Length[pth]}],VertexSize2] Out[]=
3)Abstract length vertex vectors We can modify the dot product derived for the previous case by distinguishing between graph distance (denoted ||a|| for example) and vector length(denoted l a a•b= l a l b ||a 2 || 2 || 2 || 2||a||||b|| Define a function to compute the dot product between two abstract length vertex vectors In[]:= absdot[graph_,or_,v1_,v2_,l1_,l2_]:=((l1*l2)/(GraphDistance[graph,or,v1]*GraphDistance[graph,or,v2]))*(GraphDistance[graph,or,v1]^2+GraphDistance[graph,or,v2]^2-GraphDistance[graph,v1,v2]^2)/2 Represent the ‘triangle’ formed by two vectors(recall we defined abstract length vectors in terms of the initial and final vertices, as well as an abstract length, denoted {{ v i v f v1={{143,197},8};v2={{143,218},3};p1=FindShortestPath[grph,143,197];p2=FindShortestPath[grph,143,218];p3=FindShortestPath[grph,197,218];HighlightGraph[grph,{Join[Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],v1[[1]]],Join[Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],v2[[1]]],Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}]},GraphHighlightStyle"Dotted",VertexSize3]Print["The dot product is:",absdot[grph,v1[[1]][[1]],v1[[1]][[2]],v2[[1]][[2]],v1[[2]],v2[[2]]]] Out[]= The dot product is:12 The reader is encouraged to edit the code above to see for example that the geodesic vector dot product and the abstract vertex vector dot product will not be equal in the general case.
Features of the respective dot products
1) Geodesic vectors
Commutativity First we can quite easily construct a hypothetical subgraph that shows that the geodesic approach does not commute in general. Construct a counterexample showing that commutativity is not a general property of geodesic vectors: g=Graph[{{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,12},{1,8},{8,9},{9,10},{10,11},{11,12},{12,13},{13,14}}];p1=FindShortestPath[g,1,5];p2=FindShortestPath[g,1,14];p3=FindShortestPath[g,5,12];HighlightGraph[g,{Join[Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],p1],Join[Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],p2],Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}]},GraphHighlightStyle"Thick"] Out[]= Here when the perpendicular is dropped from the red vector onto the yellow vector we get a dot product of 35. If however we consider the perpendicular dropped from the yellow vector onto the red vector, we get a dot product of 16. If we identify the order of multiplication with the direction in which the perpendicular is dropped, this leads to the operation being non-commutative. This also shows a problem where there is a max value of the dot product, which is the square of the length of the vector projected onto. We can make the ad-hoc choice to always project onto the longer vector, which reduces the problem to cases where the vectors are of equal length shown below. Construct a counterexample showing that commutativity is not a general property of geodesic vectors, even with additional constraints: g=Graph[{{1,2},{2,3},{3,4},{4,5},{5,6},{6,7},{7,12},{1,8},{8,9},{9,10},{10,11},{11,12},{12,13},{13,14},{5,15},{15,16},{16,17}}];p1=FindShortestPath[g,1,17];p2=FindShortestPath[g,1,14];p3=FindShortestPath[g,14,17];HighlightGraph[g,{Join[Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],p1],Join[Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],p2],Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}]},GraphHighlightStyle"Thick"] Out[]= Here when the perpendicular is dropped from the red vector onto the yellow vector we get a dot product of 35. If however we consider the perpendicular dropped from the yellow vector onto the red vector, we get a dot product of 28. So there is still ambiguity possible when the vectors are of equal length, which would require more ad-hoc choices to remove.
Scalar multiplication For geodesics on graphs, scalar multiplication is not unique in general. Constructing a graph showing how scalar multiplication is not well behaved: p1={10,18,19};p2={19,20,21};p3={19,20,28};p4={19,27,35};p5={19,27,28};HighlightGraph[ResourceFunction["GeneralizedGridGraph"][{8,8}],{Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}],Table[p4[[i]]p4[[i+1]],{i,1,Length[p4]-1}],Table[p5[[i]]p5[[i+1]],{i,1,Length[p5]-1}]},GraphHighlightStyle"Thick"] Out[]= Here we can see that by multiplying the red geodesic by 2, there are multiple possible geodesics of length 4, that overlaps with the original. Therefore vectors as geodesics aren’t well behaved under scalar multiplication in general. We can also see that the dot product won’t be linear under a choice of scalar multiple, illustrated below, with respect to the brown and cyan geodesics. Constructing an example showing that no result of scalar multiplication gives a satisfactory result in general (with regards to scalar multiplication under a dot product): p1={10,18,19};p2={19,20,21};p3={19,20,28};p4={19,27,35};p5={19,27,28};p6={10,11,12,13,14};p7={10,9,17,25,33};HighlightGraph[ResourceFunction["GeneralizedGridGraph"][{8,8}],{Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}],Table[p4[[i]]p4[[i+1]],{i,1,Length[p4]-1}],Table[p5[[i]]p5[[i+1]],{i,1,Length[p5]-1}],Table[p6[[i]]p6[[i+1]],{i,1,Length[p6]-1}],Table[p7[[i]]p7[[i+1]],{i,1,Length[p7]-1}]},GraphHighlightStyle"Thick"] Out[]= Tabulating the result of the dot products between geodesic vectors: Grid[{{,"Brown","Cyan"},{"Red",4,4},{"Orange",4,16},{"Green",8,12},{"Pink",8,12},{"Yellow",12,0}},Frame->All] Out[]=
As we can see no geodesic extension will in general be double the dot product with a given geodesic vector, therefore geodesic vector dot products don’t respect scalar multiplication in general under any choice of geodesic extension.
Angles>90° It is easy to see that for vectors which are closer to being anti-parallel than parallel, the perpendicular dropped will be along the vector from which it is dropped(which is by definition a geodesic to the origin), such that its projected length will always be 0.
Nonnegative-definite Since the dot product is the scalar multiple of 2 graph distances, which is always nonnegative, leading to a nonnegative-definite dot product, not even only in the case of the dot product with itself.
2) Vertex vectors
Commutativity From the formula derived before we can trivially see a•b= ||a 2 || 2 || 2 || 2 ||b 2 || 2 || 2 || 2
Scalar multiplication The same difficulty of scalar multiplication arises as before, and we can see below that no choice of multiple satisfies what we want in the general case. Constructing a graph showing how scalar multiplication is not well behaved : HighlightGraph[ResourceFunction["GeneralizedGridGraph"][{8,8}],{{10,19},{21},{28},{35},{14},{33}},VertexSize0.3] Out[]= Tabulating the result of the dot products between vertex vectors : Grid[{{,"Brown","Green"},{"Red",2,2},{"Orange",14,-2},{"Pink",8,8},{"Yellow",-2,14}},Frame->All] Out[]=
Angles>90° We can already see that we get a negative result from the dot product where vectors presumably have more than 90° between them above (for the dot product between green and orange, or between brown and yellow for example).
Nonnegative-definite Starting from the formula for a dot product a•a= ||a 2 || 2 || 2 || 2 2 || ||a 2 ||
3)Abstract length vertex vectors
Commutativity It is once again easy to show that a•b= l a l b ||a 2 || 2 || 2 || 2||a||||b|| l b l a ||b 2 || 2 || 2 || 2||b||||a|| l a l b
Scalar multiplication Here is where the strength of the abstract length formulation of vectors. Scalar multiplication here keeps the vertices the same, and only changes the abstract length: (ra)•b=( rl a l b ||a 2 || 2 || 2 || 2||a||||b|| l a l b ||a 2 || 2 || 2 || 2||a||||b||
Angles>90° All the results of the normal vertex vector construction applies here.
Nonnegative-definite We can show that a•a= l a l a ||a 2 || 2 || 2 || 2||a||||a|| 2 l a 2 l a
Summary Tabulating the results obtained above Grid[{{,"Geodesic vectors","Vertex vectors","Abstract length vertex vectors"},{"Commutativity","",✓,✓},{"Scalar multiplication","","",✓},{"Angles>90°","",✓,✓},{"Nonnegative-definite",✓,✓,✓}},FrameAll] Out[]=
General problems with linearity This section is meant to give the reader a brief overview of problems encountered when considering linearity. It is meant to give an idea of why it is not a trivial matter, and requires further work, rather than to give a complete description.
1) Geodesic vectors For geodesic vectors addition quite obviously doesn’t even commute, which immediately casts doubt on its linearity. Even on ‘nice’ graphs where the resultant vector is ‘obvious’ even without a proper definition of parallel transport this problem is easy to show Initializing a graph that will be used repeatedly for visualisation: In[]:= grid=ResourceFunction["GeneralizedGridGraph"][{9,9}]; Showing both the initial geodesic vectors and the possible results of their addition: p1={21,22,31};p2={21,30,39,48};p3={21,22,31,40,49,58};p4={21,30,39,48,49,58};HighlightGraph[grid,{Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}]},GraphHighlightStyle"Thick"]HighlightGraph[grid,{Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}],Table[p4[[i]]p4[[i+1]],{i,1,Length[p4]-1}]},GraphHighlightStyle"Thick"] Out[]= Out[]= Here the order in which we stitch the geodesics in clearly matters. We can try and ignore that for a moment and look at how this case would hold up under a dot product Providing visualisation for the vectors between which a dot product will be taken: p5={21,20,29,38,47,56,65};HighlightGraph[grid,{Table[p3[[i]]p3[[i+1]],{i,1,Length[p3]-1}],Table[p4[[i]]p4[[i+1]],{i,1,Length[p4]-1}],Table[p1[[i]]p1[[i+1]],{i,1,Length[p1]-1}],Table[p2[[i]]p2[[i+1]],{i,1,Length[p2]-1}],Table[p5[[i]]p5[[i+1]],{i,1,Length[p5]-1}]},GraphHighlightStyle"Thick"] Out[]= By dropping perpendiculars onto the green vector we can calculate by hand that the dot product with the purple vector+dot product with the orange vector gives 36. The dot product of both resultant vectors with the green vector would be 30. The reader is welcome to calculate that the disparity is even greater if we were to drop the perpendicular from the green vector.
2) Vertex vectors While I have already shown some problems that arise during scalar multiplication, I noticeably ignored linearity in its entirety. That is simply because there currently exists no rigorous and general way of adding vectors. This problem arises from lack of a general method of parallel transport. This leads to an ambiguity in the ‘direction’ of the resultant vector. The only constraints we can reasonably put for either vertex or geodesic vectors, is that the resultant vector of a+b must be distance ||a|| from the tip of b, and distance ||b|| from the tip of a. There is also no guarantee that such a vertex even exists. Furthermore there is no reason to expect a single resultant vector to act under the dot product as expected for an arbitrary vector to dot it with. Visualising vertex vectors that will be considered when attempting to add them: grid=ResourceFunction["GeneralizedGridGraph"][{9,9}];HighlightGraph[grid,{{21,48},{21,31}},VertexSize0.2] Out[]= Showing the overlap in the requirements we can put on final distance of the resultant vector. st1={};st2={};For[i=1,i≤81,i++,If[GraphDistance[grid,31,i]3,st1=Join[st1,{i}]];If[GraphDistance[grid,48,i]2,st2=Join[st2,{i}]]]HighlightGraph[grid,{st1,st2},VertexSize0.2] Out[]= We can see that there are three vertices that satisfy the results in this case. We can apply our intuition for how parallel transport should work and claim that the right-most of the three should be the resultant, but this is only possible because we are in a well-behave periodic graph. Constructing a general definition for addition of vertex of geodesic vectors on graphs have proven extremely difficult. Even if we take the ‘obvious result’, we can easily show that it fails under linearity with a dot product under our constructions. Below the orange vertex is the resultant vertex obtained previously from ‘summing’ the yellow and red vertex vectors. We can now show that the sum of the dot products between the red- and purple vectors, and the yellow- and purple vectors, is not the same as the dot product between the resultant orange vector and the purple vector. HighlightGraph[grid,{{21,48},{21,31},{21,28},{21,58}},VertexSize0.3]vertexdot[grid,21,48,28]+vertexdot[grid,21,31,28]vertexdot[grid,21,58,28] Out[]= Out[]= 3 Out[]= -1 It is easy to try it for different examples and show there are many cases where a satisfactory resultant simply doesn’t exist for vertex vectors.
3) Abstract length vertex vectors The construction of abstract length vertex vectors makes it fundamentally difficult to define addition. It is analogous to using polar coordinates, where our choice to separate length and direction makes multiplication easy, but addition hard. We can nonetheless attempt to analyse it briefly. We can start of by giving the idea of a mathematical argument that constrains the resultant vector’s abstract length independent of curvature, similarly to the trick used to define dot products: c μ a μ b μ c μ μ c a μ b μ μ a μ b ||c 2 || 2 || 2 || a μ μ b μ a b μ l c 2 l a 2 l b
In the limit There is more than one way of taking a continuum limit of these discrete structures. One way of doing it involves adding vertices in between currently existing ones, and instead of using graph distance, we introduce a notion of a measure, which gives a solid notion of length (from here on referred to as taking an interior limit). The other one involves growing the graph, and considering larger and larger subsets of the graph (from here on referred to as taking the exterior limit). Here I discuss how I expect the vectors and dot products to act in the limit, with reasoning, but not a graph theoretic/empirical proof. Doing that is a potential for further work. The intrinsic and extrinsic limits respectively are visualised below. Import["./limit.png"] Out[]=
1) Geodesic vectors Under the assumption that connecti |