Powers of 2 in High-Dimensional Lattice Walks

Let Wd(n) be the number of $2n$-step walks in Zᵈ which begin and end at the origin. We study the exponent of $2$ in the prime factorisation of this number; i.e., wd(n) = ν₂(Wd(n)). We show that, for each d, there is a relationship between wd(n) and the number s₂(n) of $1$s in the binary expansion of n. For example, wd(n) = s₂(n) if d is odd and wd(n) = 2s₂(n) if ν₂(d) = 1; while wd(n) ≥ 3s₂(n) if ν₂(d) = 2. The pattern changes further when ν₂(d) ≥ 3. However, for each d, we give the best analogous estimate of wd(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.