2025/06/15 by Nikolai Beluhov, Beluhov, Nikolai
Computer Science · Mathematics · #05A05 #05A10 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2506.12789
openalex publication_date 2025/06/15 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
Let Wd(n) be the number of 2n-step walks in ℤd which begin and end at the origin. We study the exponent of 2 in the prime factorisation of this number; i.e., wd(n) = ν2(Wd(n)). We show that, for each d, there is a relationship between wd(n) and the number s2(n) of 1s in the binary expansion of n. For example, wd(n) = s2(n) if d is odd and wd(n) = 2s2(n) if ν2(d) = 1; while wd(n) ≥ 3s2(n) if ν2(d) = 2. The pattern changes further when ν2(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.