Calculating the density of solutions of equations related to the Pólya-Ostrowski group through Markov chains

Abstract

Motivated by a problem in the theory of integer-valued polynomials, we investigate the natural density of the solutions of equations of the form ${\theta }_u{u}_q(n)+{\theta }_w{w}_q(n)+{\theta }_2\frac{n(n+1)}{2}+{\theta }_{1}n+{\theta }_0\equiv 0\mathrm{mod}d$, where $d,q\ge 2$ are fixed integers, ${\theta }_u,{\theta }_w,{\theta }_2,{\theta }_1,{\theta }_0$ are parameters and $u_q$ and $w_q$ are functions related to the $q$-adic valuations of the numbers between 1 and $n$. We show that the number of solutions of this equation in $[0,N)$ satisfies a recurrence relation, with which we can associate to any pair $(d,q)$ a stochastic matrix and a Markov chain. Using this interpretation, we calculate the density for the case ${\theta }_u={\theta }_2=0$ and for the case ${\theta }_u=1$, ${\theta }_w={\theta }_2={\theta }_1=0$ and either $d|q$ or $d$ and $q$ are coprime.

arXiv commentto appear in Acta Arithmetica