[seqfan] On the shapes of 3D walks.

[Wouter Meeussen]

On the shapes of 3D walks.

reason for this post:
** to check with knowledgeable people wether this endeavour is worthwile,
** if so, get pointers to existing open-source literature like 
https://arxiv.org/pdf/0811.2899.pdf
** get suggestions to improve data structures and reduce inherent 
arbitrariness

Intro & definitions.

I restrict myself to forward 3D walks on a diamond net.
'forward' excludes retracing the previous step backwards, also called 
'non-reverse' walks.
The coordination number of the diamond net is 4, so the 'forward' 
branching involves a 3-way choice at each step.
All walks of length n can thus be generated by the integers 0 .. -1+3^n.
Since we want the least significant-digit-first ordering, we will 
reverse the base-3 digit string so that extra zero's are added after the 
significant digits, not in front of them.

Each walk starts at {0,0,0} with 'zero-th' step North-Up to {1,0,1}, and 
from there all 3^n continuations are generated. The 3 other choices of 
'zeroth' step would give equivalent results.
The diamond net is generated by steps North-West-South-East and either 
Up or Down:

     nu    nd    wu    wd    su    sd    eu    ed        increment
nu    0    1    1    0    0    0    1    0    ->    {1,0,1}
nd    1    0    0    1    0    0    0    1    ->    {1,0,-1}
wu    1    0    0    1    1    0    0    0    ->    {0,-1,1}
wd    0    1    1    0    0    1    0    0    ->    {0,-1,-1}
su    0    0    1    0    0    1    1    0    ->    {-1,0,1}
sd    0    0    0    1    1    0    0    1    ->    {-1,0,-1}
eu    1    0    0    0    1    0    0    1    ->    {0,1,1}
ed    0    1    0    0    0    1    1    0    ->    {0,1,-1}


So the zero-th step is choosen as 'nu' {0,0,0} to {1,0,1} and can be 
followed by nd=+{1,0,-1}, wu=+{0,-1,1} or eu=+{0,1,1}. After a step 
'nu', first line in the table, we generate the next step as:
ternary 0 with 'nd', ternary 1 with 'wu' and ternary 2 with 'eu'.

This fixes an arbitrary link between the integers 0 .. -1+3^n and the 
resulting walk. We could just as well choose a different ordering.
It is as yet unclear if a more elegant or standardised link would be 
informative.

Example: the integer 7, (12 in base 3 reversed), as a 2 step walk gives:
{{0,0,0},{1,0,1},{1,1,2},{0,1,3}}
and as (120 in base 3 reversed) as a 3 step walk gives:
{{0,0,0},{1,0,1},{1,1,2},{0,1,3},{-1,1,2}}.
Remark that a n-step walk produces n+2 lattice points since the first 
two are fixed.


Shape of a 3D-walk:

walks with the same principal moments of inertia, alias the eigenvalues 
of the moments of inertia matrix, and the same distance from start to 
finish are supposed to have shapes that can be superimposed by 
translation, rotation or reflection. (This might need some extra 
restrictions). If this is not always true then there might be 
non-congruent walks reported under one shape.


Counting:

No  OEIS hits.
The method of counting digs down into succesive levels of detail.
First off, the count of different shapes vs. number of steps:

non-intersecting shapes:
  {2,4,10,24,68,186,534,1498,4410,12614,37256,106963}
all shapes :
  {2,4,10,24,70,192,563,1589,4779,13780,41695,121237}
self-intersecting shapes:
  {0,0,0,0,6,30,138,546,2136,7728,27648,95304}
first intersection at n=5 since the 7-th point coincides with the first.

Next level of detail:
The (non-intersecting) paths of length n are gathered into 'shapes' by 
the combination of start-end distance and principal moment of inertia, 
and shapes are gathered into families by their multiplicities, each 
family containing all shapes that occur m times. This multiplicity is 
equivalent to the number of symmetric variants of a single shape.
Finally, family sizes are reported for each multiplicity.

for n=1 to 7, non-intersecting shapes:
{{1,1},{2,1}},
{{1,1},{2,2},{4,1}}
{{1,1},{2,5},{4,4}}
{{1,1},{2,7},{4,15},{6,1}}
{{1,1},{2,16},{4,51}}
{{1,1},{2,25},{4,158},{8,2}}
{{1,1},{2,46},{4,485},{8,2}}

read this as:
for n=2, 2 steps, 4 points,
of the 9 walks,
1 shape occurs once,
2 shapes occur twice,
4 shapes occur once,
adding to
1*1+2*2+4*1 = 9 = 3^2

for n=1 to 7, including self-intersecting shapes, we see a difference 
from n=5 onwards:
{{1,1},{2,1}}
{{1,1},{2,2},{4,1}}
{{1,1},{2,5},{4,4}}
{{1,1},{2,7},{4,15},{6,1}}
{{1,1},{2,17},{4,52}}
{{1,1},{2,26},{4,161},{8,4}}
{{1,1},{2,53},{4,498},{8,11}}

Deeper level of detail :
in the table below, up to 3 family members are reported for each family, 
using the format:
{distance to last point, integer k that generates the walk, family size}

for n=7, non-intersecting:
{64,0,1}    x        x
{4,171,2}    {4,980,2}    {8,345,2}
{4,193,4}    {4,263,4}    {4,407,4}
{6,1040,8}    {24,260,8}    x

for n=7, all walks:
{64,0,1}    x        x
{0,303,2}    {0,830,2}    {0,929,2}
{0,194,4}    {0,386,4}    {0,524,4}
{4,47,8}    {4,105,8}    {6,141,8}

Deepest level:
similar as the above, but complete for all family members. This contains 
each shape exactly once. Two files of about 3 Mb.