Combinatorics – Why Are Numbers Counting Ever-Closer Lattice Paths So Round?

co.combinatoricsgraph theory

Let $u(i,j)$ denote the number of lattice paths from the origin to a fixed terminal point $(i,j)$ subject only to the condition that each successive lattice point on the path is closer to $(i,j)$ than its predecessor. For example, $u(1,1) = 5$ counts the one-step path $(0,0) \to (1,1)$ and the 4 two-step paths with lone interior point (1,0), (0,1), (2,1), and (1,2) respectively, each of which points is just 1 unit from (1,1) while the origin is at distance $\sqrt{2}$. By symmetry, $u(i,j)=u(j,i)$ and $u(i,j)=u(\pm i, \pm j)$. So we may assume $0\le j \le i$.

The numbers $u(i,j)$ grow rapidly but have only small prime factors. For example,
$u(15,4)=269124680144389687575008665117965469864474632630636414714548567937\\
47381916046142578125
=3^{114}\ 5^{19}\ 13^6\ 17^9.$

Any explanations? Have these paths been considered in the literature?

Here is Mathematica code to generate $u(i,j)$.

addListToListOfLists[ls_,lol_] := (ls + #1 &) /@ lol

SelectLatticePtsInDiskCenteredAtO[radius_] := Module[{m},
  Flatten[Table[m = Ceiling[Sqrt[radius^2 - i^2]] - 1; 
    Table[{i,j}, {j,-m,m}], {i,-Floor[radius],Floor[radius]}], 1] ]

SelectLatticePtsInDiskCenteredAtij[{i_,j_}, radius_] := 
 addListToListOfLists[{i,j}, 
  SelectLatticePtsInDiskCenteredAtO[radius]]

u[i_,j_] := u[{i,j}];
u[{0,0}] = 1;
u[{i_,j_}] /; j > i := u[{i,j}] = u[{j,i}];
u[{i_,j_}] /; i < 0 := u[{i,j}] = u[{-i,j}];
u[{i_,j_}] /; j < 0 := u[{i,j}] = u[{i,-j}];
u[{i_,j_}] /; 0 <= j <= i := u[{i,j}] = 
  Module[{cntFromNewOrigin,radius},
  radius = Norm[{i,j}];
  cntFromNewOrigin[newOrigin_] := u[{i,j} - newOrigin];
  Apply[Plus, Map[cntFromNewOrigin, 
     SelectLatticePtsInDiskCenteredAtij[{i,j}, radius]]]]

In[918]:= Table[ u[{i,j}],{i,0,3},{j,0,i}]

Out[918]= {{1}, {1, 5}, {25, 125, 1125}, {5625, 28125, 253125, 
  102515625}}

Best Answer

For any $k\in\mathbb N$ let $a_k$ be the number of points on the circle of radius $\sqrt{k}$ (this number may be zero). For any path as in question and for any $k$ between $1$ and $i^2+j^2-1$, there is going to be either none or exactly one of the points on the circle of radius $\sqrt{k}$ around $(i,j)$. As the sequence of points determines the path, this tells us that the number of possible such paths is $$\prod_{k=1}^{i^2+j^2-1}(1+a_k).$$ This is a product of comparatively large number of factors, each of which is small: we easily see $a_k<4k$, but in fact we have tighter bounds, for instance $a_k\leq 4d(k)$ where $d$ is the divisor counting function (follows e.g. from this result), which is $O(k^c)$ for all $c>0$. As all these factors are small, they can only have small prime factors, explaining your observation.

Related Question