Find all walks that visit all natural numbers exactly $l$ times, and are formed by repeating a finite sequence of steps

65 Views Asked by At

I am interested in integer "walks" $x_n\in\mathbb{Z}$, $n\geq0$, on the grid of integers with the following properties:

Given integer parameters $l\geq1,\ \ s_0,s_1,...,s_{d-1}$, :

  1. The "steps" are $x_n=x_{n-1}+s_k$, where $k\in\mathbb{Z}_{d}\ $, $k=n\ \text{mod} \ d$.

  2. Denote by $v[k,n]$ the number of "visits" at integer $k$ after $n$ steps of the walk. That is, $v[k,n]=\vert \{m | m\leq n\ , x_m=k \} \vert$. Then $x_n$ must obey $\underset{n\rightarrow\infty}\lim v[k,n]=l$ for all $k\in\mathbb{N}=\{0,1,...\}$

In words, I am interested in walks obtained by repeatedly taking steps whose size and direction are from a finite sequence, looped-over again and again; and the walk needs to visit all non-negative integers exactly $l$ times. Notice that I don't restrict the initial location $x_0$ (it could be any number in $\mathbb{Z}$).

I also define $u[k]$ to be the number of steps taken, from the first visit to $k$ to the last visit to $k$: $u[k]=n_2-n_1$, where $v[k,n_1]=1,\ v[k,n_2]=l,\ x_{n_1}=x_{n_2}=k$.

My question: given integers $l\geq 1,d\geq 1, S\geq 1, U\geq 0$, is there a simple known way to find (=generate), or at least count, all starting positions $x_0$ and sequences $s_0,s_1,...,s_{d-1}$ of length $d$ that give rise to a walk with the above properties, with the restrictions $\forall k \in \mathbb{Z}_d\ |s_k|\leq S$ and $\forall k\in\mathbb{N}\ \ u[k]\leq U$?

To answer the question, I tried to look into lattice paths, but I think they use a different formalism.


EDIT1: I think that this is a necessary condition: $l=\frac{d}{\sum_{i=0}^{d-1} s_i} $

1

There are 1 best solutions below

0
On

Let me add the restriction that $d$ be a small as possible to obtain the same path. I.e., there is no divisor $d'$ of $d$ such that $s_k = s_{k - d'}$ for all $k \ge d'$. Otherwise, you can generate "new" patterns that work simply by repeating shorter working patterns several times.

Let $T = \sum_{k\in \Bbb Z_d} s_k$. If $T \le 0$, then you will only ever visit a finite number of positive integers, so we can assume $T > 0$.

If all of the $s_k \ge 0$, then you once you leave a number, you will never return. So the only possible solutions are $$ d = l, x_0 \le 0, s_k =\begin{cases}0,&\quad k < d-1\\1,&\quad k = d-1\end{cases}$$ (If $x_0$ is sufficiently negative, the $1$ entry can also occur earlier in the $s_k$ list, but there can only be a single $1$ and the rest $0$.)

So assume there are negative $s_k$ and let $m = \left|\sum_{s_k < 0} s_k\right|$. After first visiting any particular integer $x$, in $\left\lceil\frac mT\right\rceil$ additional rounds (i.e., repetitions of the entire $s_k$ sequence), the action will have moved away from $x$ and will no longer be able to return to it or any point below it. So in this case, it is a matter of examining $\left\lceil\frac mT\right\rceil$ repetitions of the pattern to see if it visits the first $m$ points $l$ times. For a given $S, U$, there are only a finite number of patterns possible, so they can each be tested.