A Note on Polynomial Sequences Modulo Integers

Mohammad Javaheri Department of Mathematics School of Science Siena College Loudonville, NY 12211 USA

                  mjavaheri@siena.edu

Abstract

We study the uniform distribution of the polynomial sequence λ(P) = (⌊P (k)⌋)_{k≥1} modulo integers, where P (x) is a polynomial with real coefficients. In the nonlinear case, we show that λ(P) is uniformly distributed in ℤ if and only if P (x) has at least one irrational coefficient other than the constant term. In the case of even degree, we prove a stronger result: λ(P) intersects every congruence class modulo every integer if and only if P (x) has at least one irrational coefficient other than the constant term.

1 Introduction

A sequence (r_{k})_{k≥1} of real numbers is said to be u.d. mod 1 if for all 0 ≤ a < b < 1 we have

lim_{N→∞} \frac{1}{N} #\{k ∈ \{1, …, N\} : a ≤ \{r_{k}\} ≤ b\} = b − a,

where {r_{k}} denotes the fractional part of r_{k}. An integer sequence (a_{k})_{k≥1} is said to be u.d. mod an integer m ≥ 2 if, for every integer i, one has

lim_{N→∞} \frac{1}{N} # \{k ∈ \{1, …, N\} : a_{k} ≡ i (mod m)\} = \frac{1}{m}.  (1)

A sequence is called u.d. in ℤ if it is u.d. mod m for all m ≥ 2 (or equivalently for all m large enough). Given a sequence (r_{k})_{k≥1} of real numbers, if (r_{k}/m)_{k≥1} is u.d. mod 1 for every m ≥ 2, then (⌊r_{k}⌋)_{k≥1} is u.d. in ℤ [5, Chap. 5]. Therefore, one can derive the following results on u.d. sequences in ℤ using existing results on u.d. sequences mod 1.

Example 1. If P (x) = ∑_{i=0}^{n} a_{i}x^{i} is a real polynomial with at least one irrational coefficient other than a_{0}, then (⌊P (k)⌋)_{k≥1} is u.d. in ℤ; see [5, Chap. 5]. This result follows from the generalization of Weyl’s distribution theorem which was proved by Weyl himself via his differencing method. Weyl’s result was a generalization of Hardy and Littlewood’s result on monomials [4]. We prove the converse of this statement for nonlinear polynomials in Theorems 10 and 11.

Example 2. If f(x) = βx^{α}, where α ∈ (1, ∞)\ℕ and β ∈ (0, 1], then (⌊f(k)⌋)_{k≥1} is u.d. in ℤ. This follows from Weyl’s criterion together with van der Corput inequalities [5, Chap. 1].

Example 3. If P (x) = ±x + c, c ∈ ℝ, then (⌊P (k)⌋)_{k≥1} is clearly u.d. in ℤ. Moreover, if P (x) − P (0) ∈ ℤ[x] and (⌊P (k)⌋)_{k≥1} is u.d. in ℤ, then P (x) = ±x + c for some c ∈ ℝ [10].

Example 4. If f(x) = βα^{x} and β > 0, then the sequence (⌊f(k)⌋)_{k≥1} is u.d. in ℤ for almost all α > 1. This follows from Koksma’s theorem [8].

Niven [10] showed that, given a nonlinear polynomial P (x) ∈ ℤ[x], there exist infinitely many integers m such that (P (k))_{k≥1} is not u.d. mod m. In this paper, our first goal is to extend this result to polynomials with rational coefficients in the following theorem:

Theorem 5. Let P (x) be a polynomial with real coefficients. The sequence (⌊P (k)⌋)_{k≥1} is u.d. in ℤ if and only if P (x) has an irrational coefficient other than the constant term or P (x) = x/l + P (0) for a nonzero integer l.

In the linear case, Theorem 5 follows from Theorem 9, and in the nonlinear case, it follows from Theorem 10 or Theorem 11.

By adding the least integer operation to the arithmetic operations involved in defining polynomials, we obtain generalized polynomials. For example, f(x) = ⌊⌊a_{1}x^{2} + a_{2}⌋x⌋ + ⌊a_{3}x + a_{4}⌋x^{2} is a generalized polynomial. Halånd [3] studied uniform distribution of generalized polynomials and showed that, under some conditions relating to the independence of coefficients of f(x) over the rationals, the sequence (f(k))_{k≥1} is u.d. mod 1. The second goal of this article is to study the range of the simplest generalized polynomials modulo integers, namely the range of ⌊P (x)⌋ modulo integers, where P (x) is a real polynomial.

Definition 6. We say a polynomial P (x) ∈ ℝ[x] is complete modulo m if, for every integer n, the equation ⌊P (x)⌋ ≡ n (mod m) has a solution x ∈ ℤ. We say P (x) is complete in ℤ if it is complete modulo every integer m (or equivalently modulo all m large enough).

It follows from Example 1 that, if P (x) has at least one irrational coefficient other than the constant term, then P (x) is complete in ℤ. The converse is not true in degree 1 (compare Theorems 9 and 12). However, we will show in the following theorem that, at least in the even degree case, the converse is true.

Theorem 7. Let P (x) be an even-degree polynomial with real coefficients. Then the following statements are equivalent:

i. P (x) is complete modulo all primes large enough.

ii. P (x) has an irrational coefficients other than the constant term.

iii. The sequence (⌊P (k)⌋)_{k≥1} is u.d. in ℤ.

iv. P (x) is complete modulo all integers.

We prove Theorem 7 in Section 3. Finally, in Section 4, we consider polynomials of the form P (x) = ax^{n} + c, where n > 1 and a, c ∈ ℝ. In Theorem 16, we show that P (x) is complete modulo all primes large enough if and only if a ∉ ℚ.

2 u.d. polynomial sequences

In this section, we determine all polynomials P (x) ∈ ℝ[x] for which the sequence (⌊P (k)⌋)_{k≥1} is u.d. in ℤ. Niven [10, Thm. 3.1] showed that the sequence (⌊αk⌋)_{k≥1} is u.d. in ℤ if and only if α is irrational or α = 1/l for some nonzero integer l. By Example 1, the sequence (⌊αk + β⌋)_{k≥1} is u.d. in ℤ for every irrational number α. We will prove in Theorem 9 that if the sequence (⌊αk + β⌋)_{k≥1} is u.d. in ℤ, then either α is irrational or α = 1/l for some nonzero integer l. First, we need a lemma.

Lemma 8. Let a, b ∈ ℤ such that gcd(a, b) = 1 and b > 0. Let β ∈ ℝ. Then the sequence (⌊ak/b + β⌋)_{k≥1} is u.d. mod m if and only if gcd(a, m) = 1.

Proof. First, suppose that the sequence (⌊ak/b + β⌋)_{k≥1} is u.d. mod m. Suppose that d = gcd(a, m) > 1, and we derive a contradiction. Since we have assumed that (⌊ak/b + β⌋)_{k≥1} is u.d. mod m, it follows that the sequence (⌊ak/b + β⌋)_{k≥1} is u.d. mod d [10, Thm. 5.1]. One notes that the sequence (⌊ak/b + β⌋)_{k≥1} modulo d is periodic with period b. Therefore, if the number of solutions of ⌊ak/b + β⌋ ≡ 0 (mod d) with 1 ≤ k ≤ b is given by t, then the number of solutions of ⌊ak/b + β⌋ ≡ 0 (mod d) with 1 ≤ k ≤ sb is given by st, and so

lim_{s→∞} \frac{1}{sb}# \{k ∈ \{1, …, sb\} : ⌊ak/b + β⌋ ≡ 0 (mod d)\} = lim_{s→∞} \frac{st}{sb} = \frac{t}{b}.

On the other hand, this limit must equal 1/d by the definition of u.d. mod d (see equation (1)). It follows that t/b = 1/d, and so d | b. Since d | a and gcd(a, b) = 1, we have a contradiction.

For the converse, suppose that gcd(a, m) = 1. One notes that the sequence (⌊ak/b+β⌋)_{k≥1} is periodic modulo m with period bm. For each 0 ≤ i ≤ m − 1, let T_{i} denote the subset of elements k ∈ {1, …, bm} such that ⌊ak/b + β⌋ ≡ i (mod m). We show that |T_{i}| = b for all 0 ≤ i ≤ m − 1. Fix 0 ≤ i ≤ m − 1, and let T_{i} = {t_{1}, …, t_{r}}. For each 1 ≤ j ≤ r, we have

⌊a(t_{j} + b)/b + β⌋ ≡ a + ⌊at_{j}/b + β⌋ ≡ a + i (mod m).

In other words, the map t_{j} ↦ t_{j} + b is a one-to-one map from T_{i} to T_{a+i}, where t_{j} + b is computed modulo bm and a + i is computed modulo m. It follows that |T_{a+i}| ≥ |T_{i}|, and so |T_{qa+i}| ≥ |T_{i}| for all q ≥ 0, where qa + i is computed modulo bm. Since gcd(a, m) = 1, we conclude that |T_{i′}| ≥ |T_{i}| for all i, i′ = 0, …, m − 1, and so |T_{i}| = b for all i = 0, …, m − 1. Thus, for N = Qbm + R, 0 ≤ R < bm, the number of solutions of ⌊ak/b + β⌋ ≡ i (mod m) is between Qb and (Q + 1)b, which is sufficient to verify the definition of u.d. mod m in (1).

Theorem 9. Let α, β ∈ ℝ. Then the sequence (⌊αk + β⌋)_{k≥1} is u.d. in ℤ if and only if α is irrational or α = 1/l for some nonzero integer l.

Proof. If α is irrational, then the claim follows from Example 1 [10, Thm. 3.2]. If α = 1/l for some nonzero integer l, then the sequence (⌊k/l + β⌋)_{k≥1} is u.d. mod m for every m by Lemma 8. Thus, suppose that α = a/b for integers a, b with gcd(a, b) = 1, |a| > 1, and b > 0. It follows from Lemma 8 that the sequence (⌊ak/b + β⌋)_{k≥1} is not u.d. mod |a|, hence it is not u.d. in ℤ.

Next, we discuss nonlinear polynomials. Niven [10, Thm. 4.1] proved that if P (x) is a nonlinear polynomial with integer coefficients, then there exist infinitely many integers m such that (P (k))_{k≥1} is not u.d. mod m. We prove generalizations of this statement in the next two theorems.

Theorem 10. Let P (x) be a nonlinear polynomial with real coefficients. If P (x) has no irrational coefficients other than the constant term, then there exists infinitely many mutually coprime integers m such that (⌊P (k)⌋)_{k≥1} is not u.d. mod m.

Proof. Let P (x) = ∑_{i=0}^{n} a_{i}x^{i} such that a_{i} = r_{i}/s_{i} ∈ ℚ with gcd(r_{i}, s_{i}) = 1 for all 1 ≤ i ≤ n. Let N be the least common multiple of s_{i}, 1 ≤ i ≤ n, and let Q(x) = N(P (x)−P (0)) ∈ ℤ[x]. Choose an integer a such that Q′(a) has an arbitrarily large prime factor p > 6N (this can be done, since Q′(x) is a nonconstant polynomial). We define f(x) = Q(x) − Q(a). Then f(a) ≡ 0 (mod p^{2}) and f′(a) ≡ 0 (mod p). It follows from Hensel’s Lemma [2, Thm. 3.4.1] that f(a + kp) ≡ f(a) ≡ 0 (mod p^{2}) for all integer values of k. In particular, the equation Q(x) ≡ Q(a) (mod p^{2}) has at least p solutions for x ∈ {1, …, p^{2}}. It follows that, given an integer s ≥ 1, we have |T | ≥ sp, where T denotes the set of solutions x ∈ {1, …, sp^{2}} of Q(x) ≡ Q(a) (mod p^{2}).

We show that the sequence (⌊P (k)⌋)_{k≥1} is not u.d. mod m = p^{2}. On the contrary, suppose that (⌊P (k)⌋)_{k≥1} is u.d. mod p^{2}. It follows from the definition that for each 0 ≤ t < p^{2},

lim_{s→∞} \frac{1}{sp^{2}} |S_{t}| = \frac{1}{p^{2}} ,

where S_{t} is the set of x ∈ {1, …, sp^{2}} such that ⌊P (x)⌋ ≡ t (mod p^{2}). In particular, for s large enough, one has

\frac{1}{sp^{2}} |S_{t}| ≤ \frac{2}{p^{2}}  (2)

for all 0 ≤ t < p^{2}. If x ∈ T, then Q(x) = Q(a) + α(x) · p^{2} for some α(x) ∈ ℤ. It follows that

⌊P (x) − P (0)⌋ = ⌊\frac{Q(x)}{N}⌋ = ⌊\frac{Q(a) + α(x) · p^{2}}{N} ⌋ .

We note that ⌊(Q(a) + (β + N)p^{2})/N⌋ ≡ ⌊(Q(a) + βp^{2})/N⌋ (mod p^{2}) for every β ∈ ℤ, hence there are at most N congruence classes modulo p^{2} among the values ⌊P (x) − P (0)⌋. Since |T | ≥ sp > 6sN, it follows that there exists an integer r such that the equation ⌊P (x) − P (0)⌋ ≡ r (mod p^{2}) has more than 6s solutions in the set {1, …, sp^{2}}. Let S be the set of x ∈ T such that ⌊P (x) − P (0)⌋ ≡ r (mod p^{2}). In particular |S| > 6s.

For every x ∈ ℤ, we have ⌊P (x)⌋ = ⌊P (x) − P (0)⌋ + ⌊P (0)⌋ + u for some u ∈ {−1, 0, 1}, and so S ⊆ S_{t_{−1}} ∪ S_{t_{0}} ∪ S_{t_{1}}, where t_{u} = r + ⌊P (0)⌋ + u (computed modulo p^{2}). Therefore,

\frac{1}{sp^{2}} |S_{t_{−1}}| + \frac{1}{sp^{2}} |S_{t_{0}}| + \frac{1}{sp^{2}} |S_{t_{1}}| ≥ \frac{1}{sp^{2}} |S_{t_{−1}} ∪ S_{t_{0}} ∪ S_{t_{1}} | ≥ \frac{1}{sp^{2}} |S| > \frac{6}{p^{2}} ,

which contradicts the inequality (2) as s → ∞.

We now prove a statement that is stronger than the statement of Theorem 10.

Theorem 11. Let P (x) be a nonlinear polynomial with real coefficients. If the sequence (⌊P (k)⌋)_{k≥1} is u.d. mod all primes large enough, then P (x) has at least one irrational coefficient other than the constant term.

Proof. Suppose on the contrary that P (x) = ∑_{i=0}^{n} a_{i}x^{i} such that a_{i} = r_{i}/s_{i} ∈ ℚ with gcd(r_{i}, s_{i}) = 1 for all 1 ≤ i ≤ n. Let N be the least common multiple of s_{i}, 1 ≤ i ≤ n. Since the sequence (⌊P (k)⌋)_{k≥1} is assumed to be u.d. mod all primes large enough, the sequence (N⌊P (k)⌋)_{k≥1} is u.d. mod all primes p large enough. The value N⌊P (k)⌋ is periodic modulo p with period Np. Therefore, it follows from the uniform distribution of (N⌊P (k)⌋)_{k≥1} modulo p that, with U = {0, …, p − 1} × {0, …, N − 1}, we have

#{(t, j) ∈ U : N⌊P (Nt + j)⌋ ≡ i (mod p)} = N,  (3)

for every integer i. Let P_{j}(x) = N⌊P (Nx + j)⌋ ∈ ℤ[x] for 0 ≤ j < N. Choose M large enough so that the polynomials f_{j}(x) = P_{j}(x) + M, 0 ≤ j < N, are all irreducible over ℚ[x] (the existence of M follows from Hilbert’s irreducibility theorem [6, Chap. 9]). Let f(x) = f_{0}(x) ⋯ f_{N−1}(x) and

R = ∏_{0≤i<j<N} Res(f_{i}, f_{j}) ∈ ℤ,

where Res(f_{i}, f_{j}) is the resultant of polynomials f_{i} and f_{j}. Since f_{i} and f_{j} as irreducible polynomials in ℚ[x] have no common zeros for all 0 ≤ i < j < N, we must have Res(f_{i}, f_{j}) ≠ 0, and so R ≠ 0. Therefore, for any prime p > p_{0}, Res(f_{i}, f_{j}) ≢ 0 (mod p), where p_{0} is the greatest prime factor of R. In other words, for any prime p > p_{0}, the polynomials f_{j}, 0 ≤ j < N, have no common zeros modulo p. By the Chebotarev density theorem [1, 7], there exist infinitely many primes p such that f(x) splits completely into nN linear factors modulo p. It follows that there exists arbitrarily large p > p_{0} such that f(x) has nN distinct zeros modulo p. Therefore, the number of solutions of N⌊P (Nt + j)⌋ ≡ −M (mod p) is at least nN > N. This is in contradiction with equation (3), and the claim follows.

3 Complete even-degree polynomials

Let P (x) be a polynomial such that P (x) − P (0) ∈ ℚ[x]. Since the sequence (⌊P (k)⌋)_{k≥1} modulo any integer m is periodic, it follows from Definition 6 that the polynomial P (x) is complete modulo m if and only if

lim_{N→∞} \frac{1}{N} # \{k ∈ \{1, …, N\} : ⌊P (k)⌋ ≡ i (mod m)\} > 0,  (4)

for every integer i. Condition (4) is weaker than condition (1). Therefore, if (⌊P (k)⌋)_{k≥1} is u.d. mod m, then P (x) is complete modulo m. The converse is not true for linear polynomials as shown by the following theorem in comparison with Theorem 9.

Theorem 12. The linear polynomial P (x) = αx + β is complete in ℤ if and only if either |α| ∈ (0, 1] or α is irrational.

Proof. If α is irrational, then the claim follows from Theorem 9. Thus, suppose α = a/b where a, b are coprime integers, a ≠ 0, and b > 0. Suppose that P (x) is complete in ℤ, and so the set {⌊αk + β⌋ : k ≥ 1} contains the numbers 0, …, |a| − 1 modulo |a|. Let k = bq + l where 0 ≤ l < b. Then

⌊\frac{a}{b}(bq + l) + β⌋ = aq + ⌊\frac{al}{b} + β⌋ .

Therefore, the b numbers ⌊al/b + β⌋, 0 ≤ l < b, must contain the numbers 0, …, |a| − 1 modulo |a|. In particular b ≥ |a| and so α ∈ [−1, 0) ∪ (0, 1].

For the converse, suppose b ≥ |a|. Then the numbers al/b + β, 0 ≤ l ≤ b are apart by |a/b| ≤ 1, and they stretch from β to a + β. Therefore, the numbers ⌊al/b + β⌋, 0 ≤ l < b, include |a| consecutive integers, say s, …, s + |a| − 1. Given any i, j ∈ ℤ, we show that there exists an integer x such that ⌊ax/b + β⌋ ≡ i (mod j). We choose t ∈ ℤ such that |tj + i − s| > |a| and tj + i − s has the same sign as a. Then, write tj + i − s = aq + u, where q ≥ 1 and u ∈ {0, …, |a| − 1}. Since there exists an integer 0 ≤ l < b such that ⌊al/b + β⌋ = s + u, with x = bq + l, we have ⌊ax/b + β⌋ = aq + ⌊al/b + β⌋ ≡ aq + s + u ≡ i (mod j). It follows that P (x) is complete in ℤ, and the proof is completed.

To prove Theorem 7, we need the following two lemmas.

Lemma 13. Let R(x) be a polynomial with integer coefficients and no real zeros. Then there exist infinitely many primes p such that R(x) has no zeros modulo p.

Proof. Suppose on the contrary that R(x) has a zero modulo all primes large enough. It follows from the Chebotarev density theorem [1, 7] that every element of the Galois group of the splitting field of R(x) has a fixed point in the action on the zeros. In particular, complex conjugation must have a fixed point on the set of the zeros of R(x), which contradicts our assumption that R(x) has no real zeros.

Lemma 14. Let Q(x) be a polynomial of even degree with integer coefficients, and let A_{0}, …, A_{N−1} ∈ ℤ. Then, there exist an arbitrarily large prime p and an integer m such that Q(x) + A_{i} ≢ m (mod p) for all x ∈ ℤ and i ∈ {0, …, N − 1}.

Proof. Choose M ∈ ℤ so that Q(x) + M + A_{i} has no real zeros for all 0 ≤ i < N. We let

R(x) = (Q(x) + M + A_{0}) ⋯ (Q(x) + M + A_{N−1}).

Then R(x) has no real zeros. By Lemma 13, there exists an arbitrarily large prime p such that R(x) ≢ 0 (mod p) for all x ∈ ℤ. It follows that Q(x) + A_{i} ≠ −M for all x ∈ ℤ and i ∈ {0, …, N − 1}.

We are now ready to prove Theorem 7.

Proof. Let P (x) = ∑_{i=0}^{n} a_{i}x^{i} such that a_{i} = r_{i}/s_{i} ∈ ℚ with gcd(r_{i}, s_{i}) = 1 for all 1 ≤ i ≤ n. Let N be the least common multiple of s_{i}, 1 ≤ i ≤ n. One has

⌊P (Nk + j)⌋ = ⌊P (j)⌋ + ∑_{i=1}^{n} \frac{r_{i}}{s_{i}} ((Nk + j)^{i} − j^{i}).

And so

N⌊P (Nk + j)⌋ = N⌊P (j)⌋ + N ∑_{i=1}^{n} \frac{r_{i}}{s_{i}} ((Nk + j)^{i} − j^{i}).

= N⌊P (j)⌋ − ∑_{i=1}^{n} r_{i} \frac{N}{s_{i}} j^{i} + Q(Nk + j)

= A_{j} + Q(Nk + j),  (5)

where Q(x) = N(P (x) − P (0)) ∈ ℤ[x] and A_{j} ∈ ℤ depending on j and P (x), 0 ≤ j < N. By Lemma 14, there exist an arbitrarily large prime p > N and an integer m such that Q(x) + A_{j} ≢ m (mod p) for all x ∈ ℤ and j ∈ {0, …, N − 1}. We claim that P (x) is not complete modulo p. On the contrary, suppose there exists an integer x such that ⌊P (x)⌋ ≡ K (mod p), where K is such that NK ≡ m (mod p). But then, writing x = Nk + j with 0 ≤ j < N, we have Q(Nk + j) + A_{j} ≡ N⌊P (Nk + j)⌋ ≡ NK ≡ m (mod p). This is a contradiction, and so (i) implies (ii). The implication (ii) ⇒ (iii) was discussed in Example 1. The implications (iii) ⇒ (iv) and (iv) ⇒ (i) are straightforward, and the proof of Theorem 7 is completed.

4 Complete monomials

Let p be a prime and n be a positive integer that divides p − 1. An nth power character modulo p is any homomorphism χ : ℤ_{p}^{∗} → ℂ that is onto the group of nth roots of unity. By a theorem of A. Brauer [11], given n, l ≥ 1, there exists a constant z(n, l) such that for every prime p > z(n, l) and any nth power character χ modulo p, there exists an integer t such that

χ(t) = χ(t + 1) = ⋯ = χ(t + l − 1).  (6)

A number x is an nth power residue modulo p, if there exists y such that x ≡ y^{n} (mod p). If χ is an nth power character modulo p and x is an nth power residue modulo p, then χ(x) = χ(y^{n}) = (χ(y))^{n} = 1. Therefore, to show that a number z is not an nth power residue modulo p, it is sufficient to find an nth power character modulo p such that χ(z) ≠ 1. We use this fact in the proof of the following lemma.

Lemma 15. For any positive integer l, there exist infinitely many primes p such that all of the numbers t, t + 1, …, t + l − 1 are nth power non-residues modulo p for some positive integer t.

Proof. We can assume, without loss of generality, that n is prime and l ≥ 4. By a result of Mills [9, Thm. 3], for every m ≥ 1, there exist infinitely many primes p with an nth power character χ modulo p such that

χ(2) ≠ 1, ∀2 ≤ i ≤ m : χ(p_{i}) = 1,

where p_{i} is the ith prime. Let t be defined by (6). We can choose t > 1 by adding multiples of p if necessary. Choose an integer m large enough so that p_{m} > t + l − 1. Choose i ∈ {0, …, l − 1} such that t + i − 1 = 2(2d + 1) for some integer d. Then

χ(2(2d + 1)) = χ(2)χ(2d + 1) ≠ 1.

It then follows from equation (6) that χ(t) = χ(t + 1) = ⋯ = χ(t + l − 1) ≠ 1 i.e., none of the values t, t + 1, …, t + l − 1, are nth power residues modulo p.

Theorem 16. Let P (x) = ax^{n} + c, where a ∈ ℚ and c ∈ ℝ. If n > 1, then P (x) is not complete modulo all primes large enough, hence (⌊P (k)⌋)_{k≥1} is not u.d. in ℤ.

Proof. Let a = M/N, where M and N are integers and M > 0. Let Q(x) = Mx^{n} and A_{0}, …, A_{N−1} be given by equation (5). On the contrary, suppose P (x) is complete modulo all primes p large enough. By Lemma 15, for l = 1 + max_{i} M^{n−1}A_{i} − min_{i} M^{n−1}A_{i}, there exists an arbitrarily large prime p > |MN| and an integer t such that t + j is not an nth power residue modulo p for any 0 ≤ j < l.

Let K = t + max_{i} M^{n−1}A_{i}, and choose L such that M^{n−1}L ≡ K (mod p). Since P (x) is complete modulo p, there exists an integer x such that N⌊P (x)⌋ ≡ L (mod p). Writing x = Nk + j with 0 ≤ j < N, we have

M^{n−1}(Q(x) + A_{j}) ≡ M^{n−1}N⌊P (x)⌋ ≡ M^{n−1}L ≡ K (mod p).

Since t ≤ K − M^{n−1}A_{j} < t + l and K − M^{n−1}A_{j} ≡ M^{n−1}Q(x) ≡ (Mx)^{n} (mod p) is an nth power residue modulo p, we have a contradiction, and the claim follows.

Remark 17. In light of the proofs of Theorems 7 and 16, one can generalize Theorem 7 to all nonlinear polynomials if the following statement is true: Given a nonlinear polynomial P (x) with integer coefficients and a positive integer l, there exist an arbitrarily large prime p and a positive integer k such that P (x) ≢ k + i (mod p) for all i = 0, …, l − 1.

5 Acknowledgment

I would like to thank Siena College for providing a sabbatical leave during which this work was completed. I would also like to thank the referee for many useful comments and suggestions.

References

[1] M. D. Fried and M. Jarden, Field Arithmetic, Third Edition, Springer-Verlag, 2008.

[2] F. Q. Gouvêa, p-adic Numbers: an Introduction, Second Edition, Springer-Verlag, 1997.

[3] I. J. Halånd, Uniform distribution of generalized polynomials, J. Number Theory 45 (1993), 327–366.

[4] G. H. Hardy and J. E. Littlewood, Some problems of Diophantine approximation: part I. The fractional part of n^{k}θ, Acta Math. 37 (1914), 155–191.

[5] L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, Wiley, 1974.

[6] S. Lang, Fundamentals of Diophantine Geometry, Springer, 1983.

[7] H. W. Lenstra, Jr. and P. Stevenhagen, Chebotarev and his density theorem, Math. Intelligencer 18 (1996), 26–37.

[8] W. J. LeVeque, Note on a theorem of Koksma, Porc. Amer. Math. Soc. 1 (1950), 380– 383.

[9] W. H. Mills, Characters with preassigned values, Canad. J. Math. 15 (1963), 169–171.

[10] I. Niven, Uniform distribution of sequences of integers, Trans. Amer. Math. Soc. 98 (1961), 52–61.

[11] J. R. Rabung and J. H. Jordan, Consecutive power residues or nonresidues, Math. Comp. 24 (1970), 737–740.

2010 Mathematics Subject Classification: Primary 11K36. Keywords: uniform distribution, polynomial sequence.

Received September 11 2018; revised version received December 16 2018. Published in Journal of Integer Sequences, December 17 2018.

Return to Journal of Integer Sequences home page.