[seqfan] On the shapes of 3D walks.
Wouter Meeussen
wouter.meeussen at telenet.be
Thu Nov 9 00:58:46 CET 2023
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.
More information about the SeqFan
mailing list