Geodesic paths and their daughters (on a rectangular grid)

Posted by: Gary Ernest Davis on: November 30, 2010

In: Uncategorized
Comment!

0 Shares

Walks on a grid

On the rectangular grid shown below we can imagine walking from the red spot to a yellow spot, by taking unit steps up, down, left or right, to adjacent spots:

There are many ways to walk from the red spot to the purple spot shown below, but only 2 of those paths – the ones show in color – are shortest paths:

All other paths from the red spot to the purple spot take more than two steps.

Geodesic paths and their daughters

We call a shortest path from the red spot to a yellow spot a geodesic.

The length of a geodesic is the number of yellow spots it passes through.

The geodesics shown aboveÂ in color have length 2.

I want to think about the idea of a geodesic having offspring.

Suppose a geodesic goes from the red dot to yellow dot 1, then to yellow dot 2, and to yellow dot 3:

This geodesic, which we will name $\gamma$ (Greek “gamma”) has length 3: it passes through 3 yellow dots.

It is also a part of 2 geodesics of length 4, namely those geodesics that after reaching yellow spot 3, go to yellow spot A, or to yellow spot B.

These length 4 geodesics we call daughters of the geodesic $\gamma$ : they are geodesics of length one greater than $\gamma$ and they consist of the path $\gamma$ plus one extra step.

The geodesic $\gamma$ has 2 daughters, and this is typical of most geodesics.

However, some geodesics have 3 daughters. These are the geodesics that travel directly up, or directly down, or directly left, or directly right, from the red spot:

The blue geodesic (of length 2) has 3 daughters (of length 3).

A recurrence for the number of geodesics of a given length

Let’s call a geodesic of type A if it has 2 daughters, and of type B if it has 3 daughters.

Let $A(n)$ denote the number of geodesics of type A that have length $n$ , and let $B(n)$ denote the number of geodesics of type B that have length $n$ .

There are 4 geodesics of length 1, all of which are of type B.

So $A(1)=0 \textrm{ and } B(1)=4$ .

A geodesic of type A of length $n$ has 2 daughters, both of which are of type A, and of length $n+1$ .

A geodesic of type B of length $n$ has 3 daughters, all of length $n+1$ ,Â two of which are of type A and the other of which is of type B.

So, $B(n+1)=B(n) \textrm{ and } A(n+1)=2A(n)+ 2B(n)$ .

This means $B(n)=4 \textrm{ for all } n \textrm { and } A(n+1)=2A(n)+ 8$

The recurrence $A(n+1)=2A(n)+8$ together with the initial condition $A(1)=0$ allows us to calculate how many geodesics there are of type A of length $n$ , for any $n$ .

The total number of geodesics of length $n$ we denote by $\Gamma(n)$ , so $\Gamma(n)=A(n)+B(n)=A(n)+4$ .

From the recurrence for $A(n)$ and the fact that $A(n)=\Gamma(n)-4$ we get the same recurrence for $\Gamma(n)$ as for $A(n)$ , but with a different initial condition:

$\Gamma(n+1)=2\Gamma(n)+2\Gamma(n-1), \Gamma(1)=4$ .

A spreadsheet can calculate the values of $\Gamma(n)$ for small $n$ from the recurrence formula:

n	Gamma(n)	Gamma(n)/Gamma(n-1)
1	4
2	12	3
3	28	2.333333333
4	60	2.142857143
5	124	2.066666667
6	252	2.032258065
7	508	2.015873016
8	1020	2.007874016
9	2044	2.003921569
10	4092	2.001956947
11	8188	2.000977517
12	16380	2.00048852
13	32764	2.0002442
14	65532	2.000122085
15	131068	2.000061039
16	262140	2.000030519
17	524284	2.000015259
18	1048572	2.000007629
19	2097148	2.000003815
20	4194300	2.000001907
21	8388604	2.000000954
22	16777212	2.000000477
23	33554428	2.000000238
24	67108860	2.000000119
25	134217724	2.00000006

How the number of geodesics grows as the length increases

Also shown in this table is the ratio $\frac{\Gamma(n)}{\Gamma(n-1)}$ .

This ratio seems to approach 2 as $n$ increases.

This numerical evidence suggests that the total number of geodesics of length $n$ is increasing exponentially, by a multiplication factor of about 2.

To see why $\frac{\Gamma}{\Gamma(n-1)}$ approaches a limit as $n$ increases, as distinct from observing from a table that it seems to, we use the fact that $\Gamma(n)=2\Gamma(n-1)+4$ so $\frac{\Gamma(n}{\Gamma(n-1)}=2+\frac{4}{\Gamma(n)}$ .

Because $\Gamma(n)$ increases without bound, we see that $\frac{\Gamma(n)}{\Gamma(n-1)}\approx 2$ for large $n$ , as the numerical evidence suggested.