CALCULATING THE DENSITY OF SOLUTIONS OF
EQUATIONS RELATED TO THE PÓLYA-OSTROWSKI
GROUP THROUGH MARKOV CHAINS

arXiv:1803.04280v1 [math.NT] 12 Mar 2018

DARIO SPIRITO
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 θu uq (n) + θw wq (n) + θ2 n(n+1)
+ θ1 n + θ0 ≡
2
0 mod d, where d, q ≥ 2 are ﬁxed integers, θu , θw , θ2 , θ1 , θ0 are parameters and uq and wq 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 ) satisﬁes 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 θu = θ2 = 0 and for the case θu = 1,
θw = θ2 = θ1 = 0 and either d|q or d and q are coprime.

1. Introduction
Let q ≥ 2 be a positive integer. Following [1] and [2], we define the
following three functions on N:
(
0
if n = 0
vq (n) :=
k
max{k ∈ N | q divides n} if n > 0;
n
X
X n 
wq (n) :=
vq (i) =
;
k
q
i=0
k≥1
uq (n) :=

n
X

wq (i).

i=0

The functions wq (n) and uq (n) arise naturally during the study of
the Pólya-Ostrowski group Po(D) of a Dedekind domain D, a subgroup
of the class group of D closely related to the ring of integer-valued
polynomials Int(D) over D. In particular, Po(D) is linked with the
module structure of two sequences of D-modules, namely the sequence
of characteristic ideals Jn (D) of D and the sequence of the subsets
Intn (D) of Int(D) formed by the polynomials f ∈ Int(D) of degree
at most n. More precisely, Jn (D) and Intn (D) are free if and only if,
2010 Mathematics Subject Classification. Primary: 11B05. Secondary: 11A07,
11A63, 13F05, 13F20.
Key words and phrases. Distribution modulo d; natural density; integer-valued
polynomials; Pólya-Ostrowski group; Markov chain; q-additive functions.
1

2

DARIO SPIRITO

respectively, wq (n) ≡ 0 mod d and uq (n) ≡ 0 mod d for every q, where
d is the order of the ideal Πq (defined as the product of the maximal
ideals m of D such that |D/m| = q) in the class group of D. See Section
5 for a more detailed explanation.
This ideas led Elliott [2] to study the equations wq (n) ≡ x mod d
and uq (n) ≡ x mod d, where d and x are integers; in particular, he was
interested in the density of the set of solutions, where the (natural)
density of a subset T ⊆ N is the limit
|{n ∈ T | 0 ≤ n < N}|
δ(T ) := lim
N →∞
N
(provided that it exists). Through a mixture of special cases and experimental evidence, he conjectured [2, Conjecture 2.2] that the density of
the solutions always exists and is rational, and that if x = 0 then it is
at least 1/d.
In this paper, we consider the more general equation
n(n + 1)
(1)
θu uq (n) + θw wq (n) + θ2
+ θ1 n + θ0 ≡ 0 mod d,
2
where θu , θw , θ2 , θ1 , θ0 are integer coefficients; this form appears when
trying to express the function uq (aq + λ) in terms of uq (a).
Our starting point is the possibility of expressing the number of solutions of (1) in [0, qN) in terms of the number of solutions in [0, N) of
equations of the same form, but with different coefficients (Proposition
2.3). While we are not able to prove that the density δ(q, d; θu , θw , θ2 , θ1 , θ0 )
of the solutions of (1) exists for every choice of q, d and the coefficients,
we can use this recurrence relation to associate to the equation (1) (for
any fixed q and d) a stochastic matrix P := P (q, d) and a Markov
chain, studying which we can calculate these densities in several cases.
More precisely, fix q and d. Suppose that δ(q, d; θu , θw , θ2 , θ1 , θ0 ) exists
for every choice of θu , θw , θ2 , θ1 , θ0 . We prove that:
• (Theorem 2.6) every δ(q, d; θu , θw , θ2 , θ1 , θ0 ) is rational;
• (Theorem 3.2)
(
1
gcd(ψ, θ, d) if gcd(ψ, θ, d)| gcd(x, d)
d
δ(q, d; 0, ψ, 0, θ, x) =
0
otherwise;
• (Theorem 4.2) if d|q, then (ϕ is the Euler function)
 
d
1 X
;
f ·ϕ
δ(q, d; 1, 0, 0, 0, x) = 2
d
f
f | gcd(x,d)

• (Theorem 4.4) if d and q are coprime and θu is coprime with d,
then
1
δ(q, d; θu , θw , 0, 0, x) = .
d
Section 5 translates the result obtained back to the setting of integervalued polynomials.

DENSITY OF SOLUTIONS AND MARKOV CHAINS

3

2. The general transformation
Our first step is expressing wq (aq + λ) and uq (aq + λ) as a function
of a and λ.
Lemma 2.1. Let q be a positive integer, and let λ ∈ {0, . . . , q − 1}.
Then,
wq (aq + λ) = wq (a) + a
for every a ∈ N.
Proof. Since vq (i) = 0 if i is not a multiple of q, we have
aq+λ

wq (aq + λ) =

X

vq (i) =

i=0

a
X

vq (jq).

j=0

Moreover, vq (jq) = 1 + vq (j), and thus
wq (aq + λ) =

a
X

(1 + vq (j)) = a +

j=0

as claimed.

a
X

vq (j) = a + wq (a),

j=0



Lemma 2.2. Let q be a positive integer, and let λ ∈ {0, . . . , q − 1}.
Then,
q 2 
q
uq (aq + λ) = quq (a) + (λ + 1 − q)wq (a) + a + λ + 1 −
a=
2
2
a(a + 1)
+ (λ + 1 − q)a
= quq (a) + (λ + 1 − q)wq (a) + q
2
for every a ∈ N.
Proof. We start by calculating uq (aq − 1). We have
aq−1

uq (aq − 1) =

X

wq (i) =

i=0

q−1
a−1 X
X

wq (bq + t).

b=0 t=0

Since wq (bq + t) = wq (bq) for every t ∈ {0, . . . , q − 1}, this implies that
uq (aq − 1) =

a−1
X
b=0

qwq (bq) = q

a−1
X
b=0

(wq (b) + b) = quq (a − 1) + q

(a − 1)a
.
2

Hence, using again wq (bq + t) = wq (bq), we have
uq (aq + λ) = uq (aq − 1) + (λ + 1)wq (aq) =
= quq (a − 1) + q (a−1)a
+ (λ + 1)(wq (a) + a) =
2
= q(uq (a) − wq (a)) +

(a−1)aq
2

rearranging which we have our claim.

+ (λ + 1)wq (a) + (λ + 1)a,


4

DARIO SPIRITO

The previous lemmas suggest to consider the more general equation
n(n + 1)
+ θ1 n + θ0 ≡ 0 mod d,
2
as θu , θw , θ2 , θ1 , θ0 vary in Z. Clearly, if θu′ ≡ θu mod d, and analogously
for θw′ , θ2′ , θ1′ and θ0′ , then n is a solution of (2) if and only if it is a
solution of
n(n + 1)
θu′ uq (n) + θw′ wq (n) + θ2′
+ θ1′ n + θ0′ ≡ 0 mod d;
2
for this reason, we will sometimes consider Equation (2) as having the
coefficients θu , θw , θ2 , θ1 , θ0 in Z/dZ; this should not cause confusion.
Note that, if we were using n2 instead of n(n + 1)/2, we may need
to consider also half-integer values of θ2 and θ1 , and the situation may
become troublesome when d is even.
Let now s := (θu , θw , θ2 , θ1 , θ0 ) ∈ Z5 . For any A ∈ N, we denote
by γ(A, q, d; θu , θw , θ2 , θ1 , θ0 ), or by γ(A, q, d; s), the number of natural
numbers n < A that are solution of (2).
(2)

θu uq (n) + θw wq (n) + θ2

Proposition 2.3. Let q, d ≥ 2 be positive integers. For every A ∈ N,
and every s ∈ Z5 , we have
(3)

γ(qA, q, d; s) =

q−1
X

γ(A, q, d; sMλ)

λ=0

where



q λ−q+1 q λ−q+1
0
1
0
1

2

Mλ := 0
0
q λq − q(q−1)
2
0
0
0
q
0
0
0
0
for every λ.


0
0 

λ(λ+1) 

2
λ 
1

Proof. Let s := (θu , θw , θ2 , θ1 , θ0 ). For any λ ∈ {0, . . . , q − 1}, let
γ(λ) (A, q, d; s) be the number of solutions to Equation (2) that are
smaller than A and that are congruent to λ modulo q.
Each row of Mλ is the expansion of uq (n), wq (n), n(n+1)
, n, 1 in terms
2
a(a+1)
of uq (a), wq (a), 2 , a, 1 when n = aq + λ: indeed, for uq and wq
it follows from Lemmas 2.1 and 2.2, and it is obvious for n and 1.
Moreover,

(aq + λ)(aq + λ + 1)
λ(λ + 1)
q2
q2
q2
q
a+
= a2 + a − a + qλ +
2
2
2
2
2
2
which gives the third row of Mλ after rearrangement.
Now aq + λ < Aq if and only if a < A; this means exactly that
γ(λ) (qA, q, d; s) = γ(A, q, d; sMλ ).
Summing over λ we get the claim.



DENSITY OF SOLUTIONS AND MARKOV CHAINS

5

As remarked before the statement of the proposition, we can consider
s to be an element of (Z/dZ)5 instead of Z5 ; in particular, we can
define γ(A, q, d; s) even with s ∈ (Z/dZ)5 , and Proposition 2.3 carries
over without problems, with the only difference that each Mλ must be
considered as a matrix over Z/dZ.
This convention is useful because it makes the space of possible s
finite, and in particular it allows to rearrange Equation (3) in matrix
form. Indeed, for every s, t ∈ (Z/dZ)5 , let µ(s, t) be the number of
λ ∈ {0, . . . , q − 1} such that t = sMλ . Then, for every s ∈ (Z/dZ)5 we
have the finite sum
X
µ(s, t)γ(A, q, d; t)
γ(qA, q, d; s) =
t∈(Z/dZ)5

Let now

γ(A, q, d; s)
,
A
e (A, q, d) be the column vector composed of the e
and let γ
γ (A, q, d; s),
5
as s ranges in (Z/dZ) . Then, the previous equality can be written as
γ (A, q, d; s) :=
e

(4)

e (qA, q, d) = P (q, d)e
γ
γ (A, q, d)

where P (q, d) := (µ(s, t)/q)s,t is a (rational) matrix of order d5 . This
matrix is a stochastic matrix, i.e., each entry is nonnegative and the
sum of each of its row is 1: indeed, the sum of µ(s, t), as s is fixed and
t varies, must be q, since for each λ there is a t such that t = sMλ .
We introduce the following definition.
Definition 2.4. Let q, d ≥ 2 be positive integers. The density of solutions for s ∈ Z5 (or s ∈ (Z/dZ)5 ) with respect to q and d is
γ(N, q, d; s)
δ(q, d; s) := lim e
γ (N, q, d; s) = lim
,
N →∞
N →∞
N
provided that the limit exists; if q and d are clear from the context,
we also write δ(s) for δ(q, d; s). The column vector (δ(s))s is called the
vector of densities of the solutions of Equation (2) and is denoted by
δ(q, d) (or simply δ).
Fix now the first four coefficients θu , θw , θ2 , θ1 . If the density δ(q, d; θu , θw , θ2 , θ1 , x)
exists for every x ∈ Z, we say that the function
n(n + 1)
f : n 7→ θu uq (n) + θw wq (n) + θ2
+ θ1 n
2
has a limit distribution modulo d (and we call the assignment x 7→
δ(q, d; θu , θw , θ2 , θ1 , x) the limit distribution). If the densities are all
equal (and so are equal to 1/d), we say that f is uniformly distributed
modulo d (see e.g. [9]).
Lemma 2.5. Let M be a square matrix of order n over C; suppose that
each eigenvalue λ of M satisfies |λ| = 1, λ 6= 1. If v is a vector such
that M k v has a limit when k → ∞, then v = 0.

6

DARIO SPIRITO

Proof. By conjugation, we can suppose that M = (mij )i,j is an upper
triangular matrix.
Suppose v = (v1 , . . . , vn ) 6= 0, and let t be the biggest i such that
vi 6= 0. Then, the t-th component of M k v is equal to mktt vt ; in particular,
mktt vt has a limit as k → ∞. However, mtt is an eigenvalue of M, and
thus it is a complex number of norm 1 different from 1; hence, mktt does
not have a limit. This would imply vt = 0, against our choice of t. The
claim is proved.

Theorem 2.6. Let q, d ≥ 2 be positive integers. If the vector of densities δ(q, d) exists, then it is a right eigenvector of P (q, d) with eigenvalue 1, and all its entries are rational.
e k be the column vector whose entries are
Proof. For every k ∈ N, let γ
k
γ (q , q, d; s), as s ranges in (Z/dZ)5 . Then, (4) becomes
e
ek = P γ
e k−1 = P k γ
e0.
γ

e k has a limit for k → ∞ then it must be δ := δ(q, d); in
Clearly, if γ
particular, the first equality of the previous equation becomes
δ = P δ,

and thus δ is an eigenvector of P with eigenvalue 1.
e 0 has a limit as k →
Moreover, the existence of δ implies that P k γ
∞. Being P := P (q, d) a stochastic matrix with rational entries, the
algebraic and geometric multiplicities of its eigenvalue 1 coincide (see
e.g. [4, Section 9.4, Fact 1(b)] or [8, p.696]), and we can find a rational
matrix A such that A−1 P A is a block matrix


I 0 0
N := A−1 P A = 0 R 0  ,
0 0 Q

where I is the identity matrix, the eigenvalues of R have norm 1 but are
different from 1 and the norm of each eigenvalue of Q is smaller than
e 0 −→ δ can we rewritten as N k (A−1 γ
e 0 ) −→ A−1 δ.
1. The limit P k γ
e 0 ; then,
Let v := A−1 γ
  


I 0
0
v1
v1
N k v = 0 Rk 0  v2  = Rk v2  ,
v3
0 0 Qk
Qk v3

where v1 , v2 and v3 are subvectors of v of appropriate length. The
existence of the limit implies that both Rk v2 and Qk v3 have limit
as k → ∞. Since R satisfies the hypothesis of Lemma 2.5, we have
v2 = 0; on the other hand, by construction, Qk −→ 0 [8, p.617], and
thus Qk v3 −→ 0.
e 0 have rational entries (since γ(1, q, d; s) is either 1
Both A and γ
or 0). Hence, v has rational entries, and by the previous reasoning so
does the limit of N k v, i.e., A−1 δ; therefore, δ has rational entries, as
claimed.


DENSITY OF SOLUTIONS AND MARKOV CHAINS

7

The fact that the entries are rational supports part of [2, Conjecture
2.2(1)].
As observed before Definition 2.4, P := P (q, d) is a stochastic matrix:
hence, we can interpret it in a probabilistic way. A (discrete) Markov
chain M is a family of random variables {Xn }n∈N , whose range is a
finite set S := {s1 , . . . , sk } (called the state space of M), such that

P (Xn+1 = tn+1 |Xn = tn , Xn−1 = tn−1 , . . . , X0 = t0 ) = P (Xn+1 = tn+1 |Xn = tn )

for all n and all t1 , . . . , tn+1 ∈ S. If, furthermore, the probability
P (Xn+1 = tn+1 |Xn = tn ) of going from tn to tn+1 does not depend on n,
then M is said to be time-homogeneous, and the matrix M := (mij )i,j ,
where mij := P (Xn+1 = sj |Xn = si ), is a stochastic matrix, called the
transition matrix of M.
Conversely, to every stochastic matrix M = (mij )i,j of order k is
associated a discrete, time-homogeneous Markov chain M on a state
space S = {s1 , . . . , sk } of cardinality k, such that P (Xn+1 = sj |Xn =
si ) = mij for all n, that is, such that M is the transition matrix of M.
When M and M are linked in this way, we call M the Markov chain
represented by M. See e.g. [8, Section 8.4] for further details.
When M = P (q, d), we denote the Markov chain arising in this way
by C(q, d); more explicitly, C(q, d) is the Markov chain such that the
probability of going from state s to state t is µ(s, t)/q.
Let M be a Markov chain with state space X, and let i, j ∈ X. We
say that j is reachable from i (or that i leads to j) if there is a k ∈ N
such that P (Xn+k = j|Xn = i) > 0, that is, if the probability of going
from i to j in k steps is positive. We say that i and j are communicating
(and we write i ↔ j) if i is reachable from j and j is reachable from
i. The relation “↔” is an equivalence relation; if C is an equivalence
class, we say that C is ergodic if, when i ∈ C and j is reachable from
i, then also j ∈ C, that is, if one the chain arrives in C then it cannot
leave C; equivalently, if P (Xn+k = l|Xn = i) = 0 for all l ∈
/ C and all
k ∈ N. A state is ergodic if the equivalence class it belongs to is an
ergodic class.

Proposition 2.7. Let P be a stochastic matrix, and let v := (v1 , . . . , vn )⊺
be such that v = P v. If i and j belong to the same ergodic class, then
vi = vj .
Proof. This is essentially a consequence of the Perron-Frobenius theorem (see e.g. [4, Section 9.2, Fact 5] or [8, Chapter 8]). Let C1 , . . . , Ct be
the ergodic classes of the Markov chain associated to P . By [4, Section
9.4, Fact 1(g)], the space V of right eigenvectors of P with eigenvalue
1 has dimension t, and there is a basis u := {uC1 , . . . , uCt } of V such
that, if a is an ergodic state and Ck is its equivalence class, then the
a-th component of uCl is 1 if l = k and 0 otherwise. In particular, if
both i, j ∈ Ck and v ∈ V , then vi and vj are equal to the coefficients

of uCk along the basis u of V . In particular, vi = vj .

8

DARIO SPIRITO

3. The case θu = θ2 = 0
A function f : N −→ R is said to be q-additive if f (0) = 0 and
X
X
f (n) =
f (aq,j (n)q j ) for n =
aq,j (n)q j ,
j≥0

j≥0

where aq,j (n) ∈ {0, . . . , q−1} are the digits of n in base q. The prototype
of q-additive functions is the sum of digits of n in base q, which we
denote by sq (n).
By [1, Exercise II.8 and Lemma II.4], we can write
wq (n) :=

n − sq (n)
;
q−1

thus, for every ψ, θ ∈ Z, the function
ψwq (n) + θn =

θ(q − 1) + ψ
ψ
·n−
· sq (n);
q−1
q−1

is q-additive. On the other hand, note that uq (n) is not q-additive, since
(for example) uq (q + 1) = 2 6= 1 = uq (q) + uq (1). This point of view
yields the following, the second part of which is another partial answer
to [2, Corollary 2.2(1)].
Theorem 3.1. Let d, q ≥ 2 be positive integers. Then:
(a) for every θw , θ1 , θ0 ∈ Z, the density δ(q, d; 0, θw , 0, θ1 , θ0 ) exists;
(b) if d|q n for some n, then the vector of densities δ(q, d) exists.
Proof. (a) By [11, Theorem 1.1], every q-additive function with integer
values has a limit distribution modulo d, for every d; in particular, so
does θw wq (n) + θ1 n, and the density δ(q, d; 0, θw , 0, θ1 , θ0 ) exists.
(b) Let λ1 , . . . , λn ∈ {0, . . . , q − 1}, and let s ∈ (Z/dZ)5 . Applying
repeatedly Proposition 2.3, we have
q−1
X
γ(q n N, q, d; s)
1 γ(N, q, d; sMλ1 · · · Mλn )
=
.
n
q N
qn
N
λ ,...,λ =0
1

n

The first and the third column of Mλ1 · · · Mλn (as integer matrices) are
divisible by q n ; hence, they are 0 when reduced modulo d. It follows
that the first and the third component of sMλ1 · · · Mλn are always 0.
Therefore, by the previous point, for each summand of the right hand
side the limit (as N → ∞) exists; it follows that so does the limit of
the left hand side, i.e., the density δ(q, d; s) exists.

The first part of the previous theorem is especially useful since, if we
are interested in the distribution of the function wq , we don’t need to
consider θu or θ2 ; that is, we can study the Markov chain limited to the
subset of (Z/dZ)5 where θu = θ2 = 0. The next result calculates these
densities.

DENSITY OF SOLUTIONS AND MARKOV CHAINS

9

Theorem 3.2. Let q, d ≥ 2 be positive integers, and let ψ ∈ Z, ψ 6= 0.
Then,
(
1
gcd(ψ, θ, d) if gcd(ψ, θ, d)| gcd(x, d)
δ(q, d; 0, ψ, 0, θ, x) = d
0
otherwise
for every x ∈ Z.
Proof. By Theorem 3.1(a) the density exists.
We first note that, if gcd(ψ, θ, d) does not divide gcd(x, d), then the
equation ψwq (n) + θn + x ≡ 0 mod d cannot have solutions, so the
density is 0.
Suppose that g := gcd(ψ, θ, d) divides gcd(x, d). In this case, ψwq (n)+
θn+x ≡ 0 mod d is equivalent to ψg wq (n)+ gθ n+ xg ≡ 0 mod gd ; therefore,


d
ψ
θ x
γ(A, q, d; 0, ψ, 0, θ, x) = γ A, q, ; 0, , 0, ,
.
g
g
g g

Moreover, gcd(ψ/g, θ/g, d/g) = 1; hence, it is enough to prove the claim
in the case gcd(ψ, θ, d) = 1.
The set X := {(0, ψ, 0, θ, x) : ψ, θ, x ∈ Z/dZ} is invariant by multiplication on the right by the Mλ ; hence, the Markov chain C(q, d)
restricts to a chain C ′ (q, d) on X, which can also be defined as the
Markov chain having the transition matrix Q := (µ′ (s, t)/q), where
µ′ (s, t) is the number of λ such that sNλ = t and


1 1 0
Nλ := 0 q λ
0 0 1

is just the submatrix of Mλ relative to θw , θ1 and θ0 .
Let k ≥ 1. Consider the stochastic matrix Qk ; then, the entry relative to s, t is µk (s, t)/q k , where µk (s, t) is the number of k-tuples
(λ1 , . . . , λk ) such that sMλ1 · · · Mλk = t. Consider the Markov chain
Ck′ (q, d) represented by Qk : then, the probability of going from s to t
is equal to µk (s, t)/q k , which is equal to the probability of going from
s to t in k steps in C ′ (q, d).
We claim that, for k ≥ 1,

⊺
ψ

ψ θ x Nλ1 · · · Nλk = q k θ + q k−1ψ + q k−2ψ + · · · + qψ + ψ  ,
x + Pk (λ1 , . . . , λk , ψ, θ, q)
where

Pk (λ1 , . . . , λk , ψ, θ, q) := λ1 θ+λ2 (qθ+ψ)+· · ·+λk (q k−1 θ+q k−2ψ+· · ·+ψ).
Indeed, this is clear for k = 1 and follows easily by induction for arbitrary k.
Consider the succession ak (θ) := q k θ + q k−1ψ + q k−2 ψ + · · · + qψ + ψ,
and suppose there is a k > 1 such that ak (θ) ≡ θ mod d. Then, for any

10

DARIO SPIRITO

ψ and θ, the subset X(ψ, θ) := {(ψ, θ, x) : x ∈ Z/dZ} of X is invariant
by Ck′ (q, d), and thus we can restrict the Markov chain to X(ψ, θ); we
claim that this chain is irreducible, i.e., that any state can be reached
from any state.
The probability of going from (ψ, θ, x) to (ψ, θ, y) is nonzero if and
only if there are λ1 , . . . , λk such that y − x = Pk (λ1 , . . . , λk , q, ψ, θ, q);
hence, x and y are communicating if and only if they belong to the same
coset of the subgroup G of Z/dZ generated by Pk (λ1 , . . . , λk , ψ, θ, q),
as λ1 , . . . , λk vary in 0, . . . , q − 1.
The group G contains both θ and ψ, since Pk (1, 0, . . . , 0) = θ and
Pk (0, 1, 0, . . . , 0) = qθ + ψ. Since gcd(ψ, θ, d) = 1, this implies that G =
Z/dZ, and thus any state can be reached from any x. By Proposition
2.7, δ(0, ψ, 0, θ, x) = δ(0, ψ, 0, θ, y) for all x, y. However,
d−1
X

δ(0, ψ, 0, θ, x) = 1;

x=0

hence, δ(0, ψ, 0, θ, x) = 1/d for all x, as claimed.
Suppose now that ak (θ) 6≡ θ mod d for every k. Even in this case,
there must be m < m′ such that am (θ) ≡ am′ (θ) mod d; since ai+j (θ) =
ai (aj (θ)) for every i, j, θ, this means that ak (am (θ)) ≡ am (θ) mod d,
where k := m′ −m. By the previous part of the proof, δ(0, ψ, 0, am(θ), x) =
1/d for every x ∈ Z. Since the set of the densities δ(0, ψ, 0, θ, x) is an
eigenvector of Qm , we have
X µm (s, t)
δ(s) =
δ(t).
m
q
t∈X

Now µm ((0, ψ, 0, θ, x), (0, ψ ′, 0, θ′ , x)) = 0 unless ψ ′ = ψ and θ′ = am (θ);
hence, if s := (0, ψ, 0, θ, x) we have
δ(s) =

d−1
X
µm (s, (0, ψ, 0, am(θ), y))
y=0

qm

δ(0, ψ, 0, am(θ), y).

By the previous part of the proof, each δ(0, ψ, 0, am(θ), y) is equal to
1/d; since the sum of all µm (s, t) is q m , this means that δ(0, ψ, 0, θ, x) =
1/d, as claimed.

Corollary 3.3. Let q, d ≥ 2 be positive integers. For every θ, the map
n 7→ wq (n) + θn is uniformly distributed.
Proof. It is enough to consider the case ψ = 1 in the previous theorem.


We remark that in some cases we can also prove the existence of the
limit without using the theory of q-additive functions.
Proposition 3.4. Let q ≥ 2 be a positive integer and x, θ ∈ Z. If θ is
coprime with q, or if q|θ, then the map n 7→ wq (n) + θn is uniformly
distributed modulo q.

DENSITY OF SOLUTIONS AND MARKOV CHAINS

11

Proof. Suppose first that θ is coprime with q. In each block {qa, . . . , qa+
q −1}, wq (n) is constant; hence, the equation wq (n)+θn ≡ x mod q has
a unique solution, namely n = qa + r with r ≡ θ−1 (x − wq (qa)) mod q.
Hence, the number of solutions of wq (n) + θn ≡ x mod q in [0, . . . , N)
is N/d + O(1); i.e., γ(N, q, q; 0, 1, 0, θ, x) = N/d + O(1). Dividing by N,
the limit on the right hand side exists and is equal to 1/d; hence, the
same applies to the left hand side.
For q|θ (and it is enough to consider θ = 0), we note that
γ(N, q, q; 0, 1, 0, 0, x)
γ(N/q, q, q; 0, 1, 0, 1, x)
=q
+ O(1)
N
N
and the right hand side goes to 1/d by the previous reasoning. The
claim is proved.

4. The case s = (1, 0, 0, 0, x)
The methods used in the proof of Theorem 3.2 can also be applied
to study the full equation (2); in particular, we shall be interested in
the equation with (θu , θw , θ2 , θ1 , θ0 ) = (1, 0, 0, 0, x) =: sx . We are not
able to obtain a full picture of the situation, so we will concentrate on
two special cases. Before analyzing them, we note that we can obtain
a lower limit for the density of the solutions.
Proposition 4.1. Let d, q be positive integers and let x ∈ Z. Then,
γ(N, q, d; sx )
ϕ(d) j q k
lim inf
,
≥
N →∞
N
dq d

where ϕ is the Euler function.

Proof. Consider the blocks {aq, aq + 1, . . . , aq + q − 1} of q consecutive
natural numbers, starting from a multiple of q. In any block, the map
n 7→ wq (n) is constant, and thus the map n 7→ uq (n) is of constant
difference; in particular,
uq (aq + r) = uq (aq) + rwq (aq).
If wq (aq) is coprime with d, then uq (aq) + rwq (aq) passes through every
residue class modulo d, as d goes from 0 to d − 1; hence, the equation
uq (n) ≡ x mod d has at least ⌊q/d⌋ solutions into each block {aq, aq +
1, . . . , aq + q − 1}.
Let now N be an integer, and divide {1, . . . , N} into blocks of length
q. By Corollary 3.3, in approximately ϕ(d)/d of these blocks wq (n) is
coprime with d; hence,
N ϕ(d) j q k
γ(N, q, d; 1, 0, 0, 0, x) ≥
+ O(1).
q d
d
Dividing by N and taking the limit inferior we get our claim.



12

DARIO SPIRITO

This result is far from being completely satisfying (for example, it
says nothing when q < d). However, it sometimes hits what is actually
the real density, as the following theorem shows.
Theorem 4.2. Let d, q ≥ 2 be positive integers, and suppose that d|q.
Then, for every x ∈ Z,
 
1 X
d
δ(q, d; 1, 0, 0, 0, x) = 2
.
f ·ϕ
d
f
f | gcd(x,d)

This result can be seen as a generalization of [2, Proposition 3.4].
Proof. Let sx := (1, 0, 0, 0, x), with x ∈ Z/dZ; by Theorem 3.1(b), the
density δ(q, d; sx ) exists. We have sx Mλ = (0, λ + 1, 0, λ + 1, x); hence,
applying Theorem 3.2, we have
1 X gcd(λ, d)
δ(q, d; sx ) =
.
q λ=1,...,q
d
λ| gcd(d,x)

However, since d|q, the summand for λ is equal to the summand for
λ + d. Hence, the previous formula is equal to
 
1 X
d
1q X f
,
|{t ∈ {1, . . . , d} : gcd(t, d) = f }| = 2
f ·ϕ
qd
d
d
f
f | gcd(x,d)

f | gcd(x,d)

as claimed.



ϕ(d)
Remark 4.3. If gcd(d, x) = 1, then the theorem gives δ(q, d; s) = 2 ,
d
exactly the limit inferior obtained in Proposition 4.1.
The second case we consider is when d and q are coprime; it can be
seen as a generalization of [2, Proposition 3.6], albeit with a stronger
hypothesis (since we need that all the densities exist). We denote by
U(Z/dZ) the set of units of Z/dZ.
Theorem 4.4. Let q, d ≥ 2 be coprime positive integers. Suppose that,
for every s ∈ Z5 , the density δ(q, d; s) = δ(s) exists. Then, for every
θw , x ∈ Z/dZ and each θu ∈ U(Z/dZ), we have

1
δ(q, d; θu , θw , 0, 0, x) = .
d
In particular, the map n 7→ uq (n) is uniformly distributed modulo d.

Proof. The proof is similar to the proof of Theorem 3.2. Note first that
we can suppose θu = 1, since γ(N, q, d; s) = γ(N, q, d; us) for every
u ∈ U(Z/dZ). Since all the limits exist, by Theorem 2.6 the density
vector δ is a right eigenvector of the transition matrix of the Markov
chain C(q, d).

DENSITY OF SOLUTIONS AND MARKOV CHAINS

13

We calculate explicitly the inverse of M0−1 as a matrix with rational
entries:


0
q q(q − 1) −1 − q−1
2
0
q2
0
−q
0

1 
−1
q−1
.
M0 = 2 
0
0
1
0


2
q 
0
0
0
q
0
0
0
0
0
q2

Hence, we have

M1 M0−1

M12 M0−2

and

M22 M0−2





1
0

=
0
0
0


1 q+1
0
1

=
0
0
0
0
0
0

1 2(q + 1)
0
1


0
= 0
0
0
0
0

1
1
0
0
0

0
0
1
0
0

0
0
1
1
0

0
0
0
0
1 q+1
0
1
0
0


0
0

1
,
1
1

2
1





(q+1)(q+2) 

2

q+1 
1


0
0
q+6

0
0
2

1 2(q + 1) (q + 1)(2q + 3)
.
0
1
2(q + 1) 
0
0
1

In particular, M1 M0−1 , M12 M0−2 and M22 M0−2 have all integer coefficients, and so they can always be reduced modulo d.
Consider now the matrices Mλ modulo d. Each determinant is equal
to q 4 ; since q and d are coprime, it follows that they are all invertible
modulo d, and that their inverse is the reduction modulo d of their
rational inverses. Moreover, since GL5 (Z/dZ) is a finite group, each
Mλ has a finite order hλ ; hence, each state of Markov chain C(q, d) is
ergodic. Indeed, if t is reachable from s, then t = sMλ1 · · · Mλk for some
λ1 , . . . , λk ; but then
hλ −1

s = tMλk k

h

· · · Mλ1λ1

−1

so s is reachable from t.
We claim that, for every a and x, the tuples (1, a, 0, 0, x) and (1, b, 0, 0, x)
are communicating.
For every θw and every x, we have the three equalities


1 θw 0 0 x M1 M0−1 = 1 θw + 1 0 0 x ,


1 0 0 0 x M12 M0−2 = 1 q + 1 0 0 x + 2

14

and

DARIO SPIRITO



1 0 0 0 x M22 M0−2 = 1 2(q + 1) 0 0 x + q + 6 .

Since q ≥ 2, we can always use M0 and M1 : hence, the first equality
implies that, for every x, the 5-tuples (1, a, 0, 0, x) and (1, b, 0, 0, x) are
communicating, while the first and the second imply that (1, 0, 0, 0, x)
and (1, a, 0, 0, x + 2) are communicating for every a and every x (in
particular, a = 0).
If d is odd, this implies that (1, 0, 0, 0, x) ↔ (1, 0, 0, 0, y) for every
x, y ∈ Z/dZ, and thus that (1, a, 0, 0, x) and (1, b, 0, 0, y) are communicating whatever a and b are.
If d is even, then q ≥ 3 (since gcd(d, q) = 1): hence, we can also use
M2 , obtaining that (1, 0, 0, 0, x) ↔ (1, 2(q + 1), 0, 0, x + q + 6), and so
(1, 0, 0, 0, x) ↔ (1, a, 0, 0, x + q + 6) for every a. Hence, (1, 0, 0, 0, x) is
communicating with
(1, a, 0, 0, x + 2z1 + (q + 6)z2 )
for every choice of z1 , z2 ∈ N. However, q is odd, and thus gcd(2, q +
6, d) = 1: hence, 2z1 +(q+6)z2 can be equal to any s ∈ Z/dZ. Therefore,
(1, 0, 0, 0, x) ↔ (1, a, 0, 0, y) for every a and y, as claimed.
Therefore, for every d, we have δ(1, a, 0, 0, x) = δ(1, b, 0, 0, y) for each
a, b, x, y. However,
d−1
X
δ(1, θw , 0, 0, x) = 1;
x=0

hence, for every a and every x we have δ(1, a, 0, 0, x) = 1/d, as claimed.

5. Algebraic interpretation

Let D be an integral domain with quotient field K. The set of integervalued polynomials on D is
Int(D) := {f ∈ K[X] | f (D) ⊆ D}.
The set Int(D) is always an integral domain contained between D[X]
and K[X]. There are two sequences of D-modules associated to Int(D):
the first is formed by the characteristic ideals Jn := Jn (D), defined as
the union of (0) with the leading coefficients of the polynomials of
Int(D) of degree n; the second contains the modules of the form
Intn (D) := {f ∈ Int(D) | deg f ≤ n}.
If D is a Dedekind domain, these two sequences are linked by the
relation [1, Corollary II.3.6]
(5)

Intn (D) ≃

n
M
k=0

Jk ≃ D n ⊕

n
Y

k=0

Jk .

DENSITY OF SOLUTIONS AND MARKOV CHAINS

15

For any maximal ideal m of D, let N(m) be the norm of m, that is,
the cardinality of D/m; for any q ∈ N, let Πq be the product of the
maximal ideals of norm q. The subgroup of the class group generated
by the Πq is called the Pólya-Ostrowski group of D, and is denoted by
Po(D). Several papers studied Po(D) when D is an integral extension
of Z, with special focus on looking for which D the group Po(D) is
trivial (in this case, the quotient field K of D is said to be a Pólya
field ) [12, 7, 3]: this happens if and only if Int(D) has a regular basis,
i.e., a basis {f0 , f1 , . . . , } over D such that deg fi = i for every i. For
example, every cyclotomic extension of Q is a Pólya field [1, Proposition
II.4.3].
The (classes of the) characteristic ideals of D naturally belong to
Po(D), and by [1, Proposition II.3.9] we have
Jn =

n
Y

q (n)
Π−w
.
q

q=2

On the other hand, the modules Intn (D) does not belong, by themselves, to Po(D), for the trivial reason that they are not fractional
ideals of D. However, by (5), we can write Intn (D) as the direct sum
dn (D), where
D n ⊕ Int
dn (D) :=
Int

n
Y

Jn (D)

k=1

is a fractional ideal of D; by construction, the isomorphism class of
dn (D) belongs to Po(D). Moreover, since D is a Dedekind domain,
Int
dn (D) is a projective module of rank 1, and thus Intn (D) is free if
Int
dn (D) is free [6, Theorem 4.11]. Applying again (5), we
and only if Int
see that
n
Y
d
Intn (D) ≃
Πq−uq (n)
q=2

for every n ∈ N.
Therefore, we have two maps N −→ Po(D) given by
dn (D)],
n 7→ [Jn (D)] and n 7→ [Int

dn (D) are isomorphic to a
and studying how many times Jn (D) and Int
specific module is essentially equivalent to studying the limit distribution of these maps in Po(D). Elliott [2] conjectured that the density
of natural numbers such that Intn (D) is free exists and is rational,
and moreover that it is always at least 1/|Po(D)|. He also makes several conjectures for more specific cases, mostly expressed in terms of
multisets.
Suppose now that there is a unique q such that Πq is not a principal
ideal of D, and let d := |Po(D)|. Then, Po(D) ≃ Z/dZ is a cyclic group

16

DARIO SPIRITO

and [Πq ] is a generator; moreover,
q (n) mod d
Jn ≃ Π−w
q

dn (D) ≃ Π−uq (n) mod d .
and Int
q

dn (D)]
Therefore, the distribution of the maps n 7→ [Jn (D)] and n 7→ [Int
in Po(D) is determined by the distribution of n 7→ wq (n) and n 7→ uq (n)
modulo d, and we can simply translate the results in Sections 3 and 4 to
this context; the definitions of limit distribution and of being uniformly
distributed in Po(D) is analogous to the ones after Definition 2.4.
Proposition 5.1. Let D be a Dedekind domain, and suppose that Πn
is nonprincipal only for n = q; let d := |Po(D)|.
(a) The map n 7→ [Jn (D)] is uniformly distributed in Po(D).
(b) If, for every s, the density δ(q, d; s) exists, then for every g ∈
dn (D)] = g is rational.
Po(D) the density of n such that [Int
(c) If d|q, the density of n such that Intn (D) ≃ Πxq ⊕ D n is equal to
 
1 X
d
.
fϕ
2
d
f
f | gcd(x,d)

(d) If q and d are coprime and, for every s ∈ Z5 , the density
dn (D)] is uniformly disδ(q, d; s) exists, then the map n 7→ [Int
tributed in Po(D).

Proof. The four statements are the translation, respectively, of Corollary 3.3, Theorem 2.6, Theorem 4.2 and Theorem 4.4.


Suppose D is the ring of integers of a number field K. Some examples
in which D satisfies the hypotheses of the previous proposition are
given in [2, Examples 7.3 and 7.4]. Other examples can be constructed
using [1, proof of Proposition II.4.2]: if K is Galois over Q, then Πq
is principal for every q = pr such that p is not ramified in K. Since
p is ramified if and only if it divides the discriminant [10, Chapter II,
Corollary 2.12], Proposition 5.1 can be applied if the discriminant of
K is a prime power. Unfortunately, the simplest cases in which this
√
happens (the quadratic fields K = Q( p), where |p| is a prime and
p ≡ 1 mod 4, and the cyclotomic extensions K = Q(ζp ) for p prime)
are also Pólya fields [1, Proposition II.4.3 and Corollary II.4.5], and
thus Po(D) is actually trivial; other examples where the discriminant
is a prime power (with unknown Pólya-Ostrowski group) are collected
in [5].
When there is more than one Πq which is nonprincipal, it is necessary
to study the density of the n that are simultaneous solution to the
equations
(i) n(n + 1)
(i)
(i)
θu(i) uqi (n) + θw(i) wqi (n) + θ2
+ θ1 n + θ0 ≡ 0 mod di
2
for i ∈ {1, . . . , k}, where q1 , . . . , qk and d1 , . . . , dk are arbitrary integers
(and q1 , . . . , qk are pairwise different). This is essentially a problem in

DENSITY OF SOLUTIONS AND MARKOV CHAINS

17

determining how much these equations are correlated; it is reasonable
to think that (under the obvious hypothesis that at least one between
(i)
(i)
θu and θw is nonzero modulo di , for each i) such equations are actually
independent, so that the density of the solutions of all the equations
is determined by the densities of the solutions of the single equations.
The major obstruction seems to be the problem of understanding the
behaviour of uq1 (aq2 + λ) and wq1 (aq2 + λ) when q1 6= q2 .
Acknowledgements
The author wishes to thank Francesco Pappalardi and the referee for
their suggestions.
References
[1] Paul-Jean Cahen and Jean-Luc Chabert. Integer-Valued Polynomials, volume 48 of Mathematical Surveys and Monographs. American Mathematical
Society, Providence, RI, 1997.
[2] Jesse Elliott. The probability that Intn (D) is free. In Marco Fontana, Sophie Frisch, and Sarah Glaz, editors, Commutative Algebra, pages 133–151.
Springer, New York, 2014. Recent advances in commutative rings, integervalued polynomials, and polynomial functions.
[3] Bahar Heidaryan and Ali Rajaei. Biquadratic Pólya ﬁelds with only one quadratic Pólya subﬁeld. J. Number Theory, 143:279–285, 2014.
[4] Leslie Hogben, editor. Handbook of Linear Algebra. Discrete Mathematics and
its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2007.
Associate editors: Richard Brualdi, Anne Greenbaum and Roy Mathias.
[5] John W. Jones and David P. Roberts. Number ﬁelds ramiﬁed at one prime. In
Algorithmic Number Theory, volume 5011 of Lecture Notes in Comput. Sci.,
pages 226–239. Springer, Berlin, 2008.
[6] T. Y. Lam. Serre’s Problem on Projective Modules. Springer Monographs in
Mathematics. Springer-Verlag, Berlin, 2006.
[7] Amandine Leriche. Cubic, quartic and sextic Pólya ﬁelds. J. Number Theory,
133(1):59–71, 2013.
[8] Carl Meyer. Matrix Analysis and Applied Linear Algebra. Society for Industrial
and Applied Mathematics (SIAM), Philadelphia, PA, 2000.
[9] Wladyslaw Narkiewicz. Uniform Distribution of Sequences of Integers in
Residue Classes, volume 1087 of Lecture Notes in Mathematics. SpringerVerlag, Berlin, 1984.
[10] Jürgen Neukirch. Algebraic Number Theory, volume 322 of Grundlehren der
Mathematischen Wissenschaften [Fundamental Principles of Mathematical
Sciences]. Springer-Verlag, Berlin, 1999. Translated from the 1992 German
original and with a note by Norbert Schappacher, With a foreword by G.
Harder.
[11] Manfred Peter and Jürgen Spilker. Value distribution of g-additive functions.
Manuscripta Math., 105(4):519–536, 2001.
[12] H. Zantema. Integer valued polynomials over a number ﬁeld. Manuscripta
Math., 40(2-3):155–203, 1982.
E-mail address: spirito@mat.uniroma3.it
Dipartimento di Matematica e Fisica, Università degli Studi “Roma
Tre”, Roma, Italy

