Powers of 2 in High-Dimensional Lattice Walks

Abstract

Let $W_d(n)$ be the number of $2n$-step walks in ${\mathbb{Z}}^d$ which begin and end at the origin. We study the exponent of $2$ in the prime factorisation of this number; i.e., $w_d(n)={\nu }_2(W_d(n))$. We show that, for each $d$, there is a relationship between $w_d(n)$ and the number $s_2(n)$ of $1$s in the binary expansion of $n$. For example, $w_d(n)=s_2(n)$ if $d$ is odd and $w_d(n)=2s_2(n)$ if ${\nu }_2(d)=1$; while $w_d(n)\ge 3s_2(n)$ if ${\nu }_2(d)=2$. The pattern changes further when ${\nu }_2(d)\ge 3$. However, for each $d$, we give the best analogous estimate of $w_d(n)$ together with a description of all $n$ where equality is attained. The methods we develop apply to a wider range of problems as well, and so might be of independent interest.

arXiv comment20 pages