Sequences of Reducible {0, 1}–Polynomials Modulo a Prime

Judith Canner Department of Statistics North Carolina State University Raleigh, North Carolina 27695-8203 USA

                   jecanner@ncsu.edu

Lenny Jones and Joseph Purdom Department of Mathematics Shippensburg University Shippensburg, Pennsylvania 17257 USA

                    lkjone@ship.edu
                    jp9506@ship.edu

Abstract

Construct a recursive sequence of polynomials, staring with 1, in the following way. Each new term in the sequence is determined by adding the smallest power of x larger than the degree of the previous term, such that the new polynomial is reducible over the rationals. Filaseta, Finch and Nicol have shown that this sequence is finite. In this paper we investigate variations of this problem over a finite field. In particular, we allow the starting polynomial to be any {0, 1}–polynomial with nonzero constant term, and we allow the exponent on the power of x added at each step to be chosen from the set of multiples of a fixed positive integer k. Among our results, we show that these sequences are always infinite. We develop necessary and sufficient conditions on k and the characteristic p of the field, so that the sequence starting with 1 uses every multiple of k as an exponent in its construction. In addition, we prove for k = 1 and p ≥ 5 that there exists a {0, 1}–polynomial f such that the sequence starting with f uses every positive integer larger than the degree of f as an exponent in its construction.

1 Introduction

The following problem [1] provided the motivation for this paper.

Define a sequence of {0, 1}–polynomials (polynomials all of whose coefficients are either 0 or 1) in ℚ[x] by

f_{1} := 1 and f_{i} := f_{i−1} + x^{n}, for i ≥ 2,

where n is the smallest integer larger than the degree of f_{i−1} such that f_{i−1} + x^{n} is reducible over ℚ. Is this sequence infinite?

The first eight terms of this sequence are given below:

f_{1} = 1 f_{2} = 1 + x^{3} f_{3} = 1 + x^{3} + x^{15} f_{4} = 1 + x^{3} + x^{15} + x^{16} f_{5} = 1 + x^{3} + x^{15} + x^{16} + x^{32} f_{6} = 1 + x^{3} + x^{15} + x^{16} + x^{32} + x^{33} f_{7} = 1 + x^{3} + x^{15} + x^{16} + x^{32} + x^{33} + x^{34} f_{8} = 1 + x^{3} + x^{15} + x^{16} + x^{32} + x^{33} + x^{34} + x^{35}.

Filaseta, Finch and Nicol [1] have proven the somewhat surprising fact that f_{8} + x^{n} is irreducible over ℚ for all n ≥ 36, so that this sequence is actually finite and terminates at f_{8}.

In this paper we consider variations of this problem modulo a prime. Specifically, let p be a prime, let k ≥ 1 be an integer and let f(x) be a polynomial, with f(0) ≢ 0 (mod p). Define a sequence of polynomials in 𝔽_{p}[x], denoted (f, k, p), as follows:

f_{1} := f and f_{i} := f_{i−1} + x^{kn}, for i ≥ 2,

where kn is the smallest integer multiple of k larger than the degree of f_{i−1}, such that f_{i−1} + x^{kn} is reducible over 𝔽_{p}.

We impose the restriction that f(0) ≢ 0 (mod p) to avoid the trivial situation, and we do not require that f be reducible or irreducible over 𝔽_{p}.

Although we show that all sequences (f, k, p) are infinite (see Theorem 4.1), this particular attribute is but one item of interest to us here (see Section 2). Also, while our definition of the sequence (f, k, p) does not require that f be a {0, 1}–polynomial, the predominate focus of this paper is on sequences where f is a {0, 1}–polynomial. The main reason for this is that in many situations of interest, even if f is not a {0, 1}–polynomial, there is a corresponding {0, 1}–polynomial g, such that the sequence (g, k, p) has many of the same properties as the sequence (f, k, p) (see Lemma 4.1).

2 Preliminaries

As one might expect, many patterns emerge modulo a prime that are not present in the characteristic zero situation. Because of the existence of these patterns, we are motivated to define the following:

Definition 2.1. Let p be a prime and let 𝔽_{p^{m}} denote the finite field with p^{m} elements. Let (f, k, p) be a sequence as defined in Section 1, allowing the possibility that f is not necessarily a {0, 1}–polynomial, but as always, f(0) ≢ 0 (mod p).

• We say (f, k, p) has the root pattern [r_{1}, r_{2}, …, r_{t}] in 𝔽_{p^{m}} if r_{i} ∈ 𝔽_{p^{m}} and f_{N+b}(r_{i}) ≡ 0 (mod p) for some positive integer N and all positive integers b ≡ i (mod t).

• We define M to be the set of all positive integer multiples of k greater than the degree of f which are not the degree of any term of (f, k, p).

• We say (f, k, p) has the factor pattern [g_{1}, g_{2}, …, g_{t}] in 𝔽_{p}[x] if the polynomial g_{i} is a proper divisor of f_{N+b} in 𝔽_{p}[x] for some positive integer N and all positive integers b ≡ i (mod t).

• If the sequence (f, k, p) has the root pattern [r_{1}, r_{2}, …, r_{j}] (respectively, factor pattern [g_{1}, g_{2}, …, g_{j}]), then we say the root pattern (respectively, factor pattern) has period t, if t is the smallest integer such that r_{i} = r_{t+i} (respectively, g_{i} = g_{t+i}) for all i = 1, 2, …, t. Throughout the remainder of this paper, we indicate all root and factor patterns as [r_{1}, r_{2}, …, r_{t}] or [g_{1}, g_{2}, …, g_{t}], where t is the period of the pattern.

We consider the root patterns [r_{i}, r_{i+1}, …, r_{t}, r_{1}, …, r_{i−1}], for any 2 ≤ i ≤ t, to be equivalent to the root pattern [r_{1}, r_{2}, …, r_{t}]. In the event of the occurrence of multiple roots, a sequence (f, k, p) can sometimes have more than one root pattern (see Example 3.4).

Factor patterns and root patterns are related in the following way. Suppose that (f, k, p) has a factor pattern [g_{1}, g_{2}, …, g_{t}] in 𝔽_{p}[x], with δ_{i} the degree of g_{i}, and m=lcm(δ_{1}, δ_{2}, …, δ_{t}). Let g be a polynomial of degree m which is irreducible over 𝔽_{p}. Then (f, k, p) has a root pattern in 𝔽_{p}(α) ≅ 𝔽_{p^{m}}, where g(α) ≡ 0 (mod p). (see Example 3.6). Conversely, if (f, k, p) has a root pattern in 𝔽_{p^{m}}, then (f, k, p) has a factor pattern in 𝔽_{p^{h}}[x] for all h with 1 ≤ h ≤ m.

Although the proofs of some of our results use arguments which involve both root patterns and factor patterns, we choose to state our results only in terms of root patterns. Because of the connection between root patterns and factor patterns, analogous statements can be made in terms of factor patterns. While it seems plausible that when the sequence (f, k, p) has a root pattern in 𝔽_{p}, or a factor pattern in 𝔽_{p}[x], then M is not infinite (Question 5.1), the converse is false (see Example 3.1 and Theorem 4.3).

When M is finite for a sequence (f, k, p), we can use M to construct a polynomial f̂ such that M is empty for the sequence (f̂, k, p). Explicitly, if M = {km_{1}, km_{2}, …, km_{s}} for the sequence (f, k, p), where the degree of f is kd, then let f̂(x) = f(x) + ∑_{j=d+1}^{m_{s}+1} a_{j}x^{kj} be the polynomial of degree k(m_{s} + 1) such that a_{j} = 0 when kj ∈ M, and a_{j} = 1 otherwise. Then M is empty for the sequence (f̂, k, p), since this sequence starts by adding powers of x whose exponents are larger than the elements of M. A similar technique is used in the proofs of Lemma 4.1 and Theorem 4.5. See also Example 4.6.

The first main result of this article is Theorem 4.1, where we see that the situation over 𝔽_{p} is quite different than it is over ℚ, in that no sequence (f, k, p) is ever finite. Next, Theorem 4.2 shows that no root patterns exist in 𝔽_{p} for the sequences (f, k, 2) and (f, k, 3). Then, for the sequences (1, k, p), we establish in Theorem 4.3, necessary and sufficient conditions on k and p so that M is empty, and in these situations we show that no root patterns exist in 𝔽_{p^{m}} for any m. Finally, for p ≥ 5, we prove in Theorem 4.5 that there exists a {0, 1}–polynomial f such that the sequence (f, 1, p) has a root pattern in 𝔽_{p} with M empty.

Throughout this paper we let |a|_{p^{m}} denote the order of a in (𝔽_{p^{m}})^{∗}, the multiplicative group of 𝔽_{p^{m}}, and we let Φ_{n} := Φ_{n}(x) denote the n-th cyclotomic polynomial.

Lemma 2.1, Lemma 2.2 and Lemma 2.3 are stated without proof since they contain information which is well-known.

Lemma 2.1.

• There exists a primitive root modulo m if and only if m = 2, 4, q^{a}, or 2q^{a}, where q is an odd prime and a ≥ 1 is an integer.

• Let q be an odd prime. If α is a primitive root modulo q^{a} for some a ≥ 2, then α is a primitive root modulo q^{a} for all a ≥ 1.

Lemma 2.2.

• If p is a prime that divides n, then Φ_{n}(x^{p}) = Φ_{pn}(x).

• Φ_{n}(x^{k}) is irreducible over ℚ if and only if every prime divisor of k divides n.

• Let n and k be relatively prime. Then Φ_{n}(x^{k}) = ∏_{d|k} Φ_{dn}(x).

Lemma 2.3. Let p be a prime, and let g(x) be a polynomial over 𝔽_{p}. If g(x) is irreducible modulo p, then g(x) divides x^{p^{m}} − x, where m is any multiple of the degree of g(x).

In the investigation of the reducibility over ℚ of certain polynomials, it is sometimes fruitful, and more efficient, to first test for divisibility by cyclotomic polynomials [2]. Cyclotomic polynomials also play a role here in determining the reducibility of certain {0, 1}–polynomials over 𝔽_{p}. A slight adjustment is required since cyclotomic polynomials do not always remain irreducible modulo a prime. Theorem 2.2 describes explicitly the factorization of cyclotomic polynomials in 𝔽_{p}[x].

Theorem 2.2. [3] Let p be a prime, and let n = p^{a}m be a positive integer, where p does not divide m. Let b be the smallest positive integer such that p^{b} ≡ 1 (mod m). Then Φ_{n}(x)

factors as the product of \frac{ϕ(m)}{b} incongruent irreducible monic polynomials modulo p, each of degree b, and each raised to the ϕ(p^{a}) power.

We also make use of the following immediate corollary of Theorem 2.2 in the proof of Theorem 4.3.

Corollary 2.1. Let p be a prime, and let n = p^{a}m be a positive integer, where p does not divide m. Then Φ_{n}(x) is irreducible modulo p if and only if p is a primitive root modulo m, and either a = 0, or p = 2 with a = 1.

Although straightforward, Lemma 2.4 provides insight into the basic understanding of root patterns for the sequences (f, k, p).

Lemma 2.4. Let p be a prime, and let r ∈ 𝔽_{p^{m}}, with |r|_{p^{m}} = s ≠ 1. Let k ≥ 1 be an integer, and let a = gcd(s, k). For any polynomial g(x) and any n ≥ 0, define the polynomial h(x) := g(x) + x^{k(n+1)} + x^{k(n+2)} + ⋯ + x^{k(n+b)}, where b = p if a = s, and b = s/a otherwise. Then g(r) ≡ 0 (mod p) if and only if h(r) ≡ 0 (mod p).

Proof. If a = s, then clearly h(r) ≡ g(r) (mod p). Otherwise, we have

h(r) = g(r) + r^{k(n+1)} + r^{k(n+2)} + ⋯ + r^{k(n+b)}

= g(r) + r^{k(n+1)}(1 + r^{k} + (r^{k})^{2} + ⋯ + (r^{k})^{b−1})

= g(r) + r^{k(n+1)} (\frac{(r^{k})^{b} − 1}{r^{k} − 1})

= g(r) + r^{k(n+1)} (\frac{(r^{s})^{k/a} − 1}{r^{k} − 1})

≡ g(r) (mod p),

and the lemma follows.

Before we present our main results, we give some examples of sequences (f, k, p).

3 Examples of Sequences (f, k, p)

In the following examples, a computer was used to determine likely candidates for M, and, with the exception of Example 3.1, Lemma 2.4 was used to verify this evidence by establishing the existence of any root or factor patterns.

Example 3.1. (1, 4, 3)

Although this example is a special case of Theorem 4.3(3), we nevertheless provide a separate analysis here to give the reader an introduction to some of the techniques used in this paper.

We claim that f_{n} = 1 + x^{4} + x^{8} + ⋯ + x^{4(n−1)}, for n ≥ 2. First note that x^{4} + 1 = (x^{2} + x + 2)(x^{2} + 2x + 2) over 𝔽_{3} so that f_{2} = 1 + x^{4}. When n ≡ 0, 1, 3, 5 (mod 6), there exists an odd prime q that divides n, and it is easy to show then that Φ_{q} is a proper divisor of 1 + x^{4} + x^{8} + ⋯ + x^{4(n−1)}. Similarly, when n ≡ 2, 4 (mod 6), with n > 2, we have that Φ_{8} is a proper divisor of 1 + x^{4} + x^{8} + ⋯ + x^{4(n−1)}, establishing the claim, and proving that M is empty. The observation that f_{n} has a zero modulo 3 if and only if n ≡ 0 (mod 3) proves that (1, 4, 3) has no root pattern in 𝔽_{3}.

Example 3.2. (1 + x, 1, 5)

First note that 1 + x + x^{2} and 1 + x + x^{3} are irreducible over 𝔽_{5}. But f_{2} = 1 + x + x^{4}, f_{3} = 1 + x + x^{4} + x^{5}, f_{4} = 1 + x + x^{4} + x^{5} + x^{6} and f_{5} = 1 + x + x^{4} + x^{5} + x^{6} + x^{7}, since, modulo 5, they have the respective zeros: 3,4,2,4. Thus, by Lemma 2.4, (1 + x, 1, 5) has the root pattern [3, 4, 2, 4] in 𝔽_{5}, and M = {2, 3} .

Example 3.3. (1, 1, 5)

While this sequence has the same root pattern [3, 4, 2, 4] in 𝔽_{5} as the sequence (1+x, 1, 5) in Example 3.2, we see that the pattern does not emerge as soon in this sequence since here M = {1, 3, 12, 25, 36, 37, 49, 323, 1985, 4054, 5885, 6648} .

Example 3.4. (1, 1, 7)

There are, in fact, two root patterns for this sequence in 𝔽_{7}: [4, 2, 3, 4, 2, 6] and [4, 6, 3, 6, 2, 6]. Here, M = {1, 2, 4, 17, 36, 41}.

Example 3.5. (1 + x, 1, 17)

This sequence has the root pattern [8, 16, 9, 4, 2, 16, 15, 4] in 𝔽_{17}, and M = {2, 5, 8, 11, 24}.

Example 3.6. (1 + x + x^{2} + x^{5} + x^{6} + x^{8} + x^{10}, 1, 3)

This sequence has the root pattern [2, α, 2, α + 1, 2, α, 2, α + 2] in 𝔽_{9}, where α^{2} + 1 = 0. The corresponding factor pattern in 𝔽_{3} is given by [g_{1}, g_{2}, …, g_{8}], where

g_{1} = g_{3} = g_{5} = g_{7} = x − 2
g_{2} = g_{6} = x^{2} + 1
g_{4} = x^{2} + x + 2 and
g_{8} = x^{2} + 2x + 2.

Here, M is empty.

4 Main Results

Theorem 4.1. Every sequence (f, k, p) is infinite.

Proof. For any prime p, positive integer k, and polynomial h(x) ∈ 𝔽_{p}[x], we claim that there exists a positive integer t, with t divisible by k and larger than the degree of h(x), such that h(x) + x^{t} is reducible modulo p.

Suppose that p^{s} is the exact power of p that divides k, and let L = k/p^{s}. Let a = p^{sv}(k−1), where v = 1 if L = 1, and v is the order of p^{s} modulo L, otherwise. Let g(x) be an irreducible factor of h(x) + x^{a+1}, and let m > s be a multiple of the degree of g(x) with p^{m} + a larger than the degree of h(x), such that L divides p^{m} − 1. Note that p^{s} divides p^{m} + a since m > s and v ≥ 1. Also, L divides p^{m} + a by the choices of m and v. Hence, k divides p^{m} + a. By Lemma 2.3, g(x) divides x^{p^{m}} − x. Since g(x) divides h(x) + x^{a+1}, it follows that g(x) divides

h(x) + x^{a+1} + x^{a} (x^{p^{m}} − x) = h(x) + x^{p^{m}+a},

establishing the claim with t = p^{m} + a, and completing the proof of the theorem.

Theorem 4.2. Let p = 2 or 3. Then the sequence (f, k, p) does not have a root pattern in 𝔽_{p}.

Proof. The only possible root patterns are [1], if p = 2, and [1], [2] and [1, 2] if p = 3. Since the arguments are similar for each of these cases, we show only that the root pattern [1, 2] is impossible when p = 3. If [1, 2] is the root pattern for the sequence (f, k, 3), then, for some index i, it follows that

0 ≡ f_{i}(1) ≡ f_{i+2}(1) = f_{i}(1) + 1 + 1 ≡ 2 (mod 3),

which is impossible.

Theorem 4.3.

1. If k = 1, then M is never empty for the sequence (1, k, p) for any prime p.

2. If k = 2, then M is empty for the sequence (1, k, p) if and only if p = 2 or p ≡ 1 (mod 4).

3. If k ≥ 3, then M is empty for the sequence (1, k, p) if and only if k ≠ q^{a}, where a ≥ 1, and q ≥ 3 is a prime such that p is a primitive root modulo q^{2}.

Moreover, in each case that M is empty, the sequence (1, k, p) has no root pattern in 𝔽_{p^{m}} for any m.

Proof. We first establish parts (1), (2) and (3) of the theorem, and then show that when M is empty, the sequence (1, k, p) has no root pattern in 𝔽_{p^{m}} for any m. Throughout the proof, for n ≥ 2, we let g_{n} := g_{n}(x) = 1 + x^{k} + x^{2k} + ⋯ + x^{(n−1)k}.

When k = 1, we have that 1 ∈ M, since 1+x is irreducible for all primes p. So, statement (1) of the theorem is obvious.

Making use of the fact that Φ_{n}(x^{k}) divides g_{n}(x), we prove statements (2) and (3) of the theorem by determining exactly when f_{n} = g_{n} for all n ≥ 2, or equivalently, when g_{n}(x) is reducible over 𝔽_{p} for all n ≥ 2. First note that

deg (Φ_{n} (x^{k})) = ϕ(n)k ≤ (n − 1)k = deg (g_{n} (x)) .

Therefore, since Φ_{n}(x^{k}) divides g_{n}(x) for all n ≥ 2, it follows that g_{n}(x) is reducible over ℚ, and hence over 𝔽_{p}, except possibly when n is a prime q. Also, by Lemma 2.2, Φ_{q} (x^{k}) is reducible over ℚ, and hence over 𝔽_{p}, if there exists a prime divisor r of k with r ≠ q. Thus, for k ≥ 2, we have that M is empty when k ≠ q^{a}, for some prime q with a ≥ 1. Consequently, our focus is narrowed to the examination of when Φ_{q} (x^{q^{a}}) = Φ_{q^{a+1}} (x), with a ≥ 1, is reducible over 𝔽_{p}.

If k = q = 2, then a = 1, and Φ_{q^{a+1}} (x) = Φ_{4}(x) = x^{2} + 1, which is easily seen to be reducible over 𝔽_{p} if and only if p = 2 or p ≡ 1 (mod 4). Combining this fact with the above discussion completes the proof of statement (2) of the theorem.

When k = 2^{a}, with a ≥ 2, we have immediately, from Lemma 2.1 and Corollary 2.1, that Φ_{2^{a+1}} (x) is reducible over 𝔽_{p} for all primes p. When k = q^{a}, for some prime q ≥ 3, with a ≥ 1, we appeal again to Lemma 2.1 and Corollary 2.1 to conclude that Φ_{q^{a+1}} (x) is irreducible over 𝔽_{p} if and only if p is a primitive root modulo q^{2}. Therefore, statement (3) of the theorem has been established.

We now show that when M is empty, the sequence (1, k, p) has no root pattern in 𝔽_{p^{m}} for all m. We do this by showing that (1, k, p) has no factor pattern in 𝔽_{p}[x]. Note that under the assumption that M is empty, we have that f_{n} = g_{n} for all n ≥ 2, so we use the notation g_{n}. Let q > p be prime. For any divisor d of k, we can write dq = p^{a}qm_{d}, where p does not divide m_{d}. Let b be the smallest positive integer such that p^{b} ≡ 1 (mod qm_{d}). Since

p^{b} > p^{b} − 1 ≥ qm_{d} ≥ q,

we have that b > log (q) / log (p). Therefore, from Theorem 2.2, each irreducible factor of Φ_{dk}(x) modulo p has degree larger than log (q) / log (p), and this is independent of the divisor d. Since

g_{q}(x) = Φ_{q} (x^{k}) = ∏_{d|k} Φ_{dq}(x),

it follows that, as q approaches infinity, the minimum degree of an irreducible factor of g_{q} also approaches infinity, proving the impossibility of the existence of a factor pattern for (1, k, p) in 𝔽_{p}[x].

The following lemma, which is needed for the proof of Theorem 4.5, indicates in certain situations how a sequence whose terms are not all {0, 1}–polynomials can be used to construct a sequence where all terms are {0, 1}–polynomials, and such that the two sequences share particular properties.

Lemma 4.1. Let p be a prime and let g(x) = 1+∑_{i=1}^{d} a_{i}x^{i} be a polynomial of degree d ≤ p−1 that is not a {0, 1}–polynomial in 𝔽_{p}[x]. Suppose that the sequence (g, 1, p) has a root pattern in 𝔽_{p} and that M is empty. Then there exists a {0, 1}–polynomial f(x) of degree at most p^{2} − 3p + d + 3, such that the sequence (f, 1, p) has a root pattern equivalent to (g, 1, p) in 𝔽_{p}, and M is empty.

Proof. The following two-step algorithm, which incorporates Fermat’s Little Theorem, is used to construct f(x).

1. Replace every non-constant term a_{i}x^{i} of g(x) with ∑_{j=0}^{a_{i}−1} x^{i+j(p−1)}. Since 1 ≤ i ≤ p − 1, we have that no two exponents of the resulting polynomial are the same. That is, this step produces a {0, 1}–polynomial g_{1}(x) such that g_{1}(x) ≡ g(x) (mod p) for all x ∈ 𝔽_{p}, and the degree of g_{1}(x) is

d_{1} = max_{1≤i≤d} {i + (a_{i} − 1)(p − 1)}.

2. Define f(x) to be g_{1}(x) + x^{d+1+c(p−1)}, where c is the smallest positive integer such that d + 1 + c(p − 1) > d_{1}.

Then, if the root pattern for the sequence (g, 1, p) is [r_{1}, r_{2}, …, r_{t}], this definition of f(x) guarantees that the sequence (f, 1, p) has the equivalent root pattern [r_{2}, r_{3}, …, r_{t}, r_{1}], and that M is empty. Since d_{1} ≤ d + (p − 2)(p − 1), it follows that the degree of f(x) is at most d + 1 + (p − 2)(p − 1) = p^{2} − 3p + d + 3.

We give an example to illustrate Lemma 4.1.

Example 4.4. Let p = 7, k = 1 and g(x) = 6x^{4} + 4x^{3} + 6x^{2} + 2x + 1. Then (g, 1, 7) has the root pattern [2, 6, 4, 6, 3, 6] in 𝔽_{7}, which begins with the addition of x^{5}. Using Lemma 4.1, we get f(x) = x^{35} + x^{34} + x^{32} + x^{28} + x^{26} + x^{22} + x^{21} + x^{20} + x^{16} + x^{15} + x^{14} + x^{10} + x^{9} + x^{8} + x^{7} + x^{4} + x^{3} + x^{2} + x + 1. The sequence (f, 1, 7), with the equivalent root pattern [6, 4, 6, 3, 6, 2] in 𝔽_{7}, has M empty, and is constructed by adding consecutively x^{36}, x^{35}, …, instead of, respectively x^{5}, x^{6}, …, for the sequence (g, 1, 7). Note that the sequence (f − x^{35}, 1, 7) has M empty, and has the exact same root pattern as (g, 1, 7), beginning with the addition of x^{35}.

Theorem 4.5. For any prime p ≥ 5, there exists a {0, 1}–polynomial f(x), with f(0) = 1, such that the sequence (f, 1, p) has a root pattern in 𝔽_{p}, and M is empty. Moreover, if p ≡ 3 (mod 4), then f can be found whose degree is at most p^{2} − 3p + q + 5, where q is the smallest odd prime factor of p − 1, and the period of the root pattern is 2q; while if p ≡ 1 (mod 4), then f can be found such that the degree of f is at most 2p − 6, and the period of the root pattern is 4.

Remark. The proof of Theorem 4.5 is constructive, and although the technique we use to construct f when p ≡ 3 (mod 4) can be modified slightly to construct f when p ≡ 1 (mod 4), we use a different approach in the latter case since the alternative approach has two distinct advantages. The first advantage is that the construction of the polynomial f requires fewer computations, while the second advantage is that the upper bound on the degree of f is significantly less.

Proof. Suppose first that p ≡ 3 (mod 4), and let q be the smallest odd prime factor of p − 1. Let β ∈ 𝔽_{p} with |β|_{p} = 2q. Then

|β^{2}|_{p} = |β^{4}|_{p} = ⋯ = |β^{2q−2}|_{p} = q and |β^{q}|_{p} = 2.

If we can demonstrate the existence of a polynomial g(x) = 1 + ∑_{i=1}^{q+1} a_{i}x^{i}, with a_{q+1} ≢ 0 (mod p), satisfying all of the following conditions:

g(β^{q}) + (β^{q})^{q+2} ≡ 0 (mod p)
g(β^{2}) + (β^{2})^{q+2} + (β^{2})^{q+3} ≡ 0 (mod p)
g(β^{4}) + (β^{4})^{q+2} + (β^{4})^{q+3} + (β^{4})^{q+4} + (β^{4})^{q+5} ≡ 0 (mod p)
⋮  ⋮  ⋮  ⋮  ⋮  (1)
g(β^{2q−2}) + (β^{2q−2})^{q+2} + ⋯ + (β^{2q−2})^{3q−1} ≡ 0 (mod p)
g(β) + β^{q+2} + β^{q+3} + ⋯ + β^{3q+1} ≡ 0 (mod p),

then g(x) has the root pattern [β^{q}, β^{2}, β^{q}, β^{4}, …, β^{q}, β^{2q−2}, β^{q}, β] by Lemma 2.4, clearly M is empty since a_{q+1} ≢ 0 (mod p), and using Lemma 4.1, we can construct the desired polynomial f(x).

The conditions imposed on g(x) in (1) give a system of q + 1 linear equations in the q + 1 variables a_{1}, a_{2}, …, a_{q+1}. Thus, to show the existence of a polynomial g(x) ∈ 𝔽_{p}[x] satisfying (1), it suffices to show that the coefficient matrix

A = [ \begin{matrix}β^{q} & (β^{q})^{2} & (β^{q})^{3} & … & (β^{q})^{q+1} \\ β^{2} & (β^{2})^{2} & (β^{2})^{3} & … & (β^{2})^{q+1} \\ β^{4} & (β^{4})^{2} & (β^{4})^{3} & … & (β^{4})^{q+1} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ β^{2q−2} & (β^{2q−2})^{2} & (β^{2q−2})^{3} & … & (β^{2q−2})^{q+1} \\ β & β^{2} & β^{3} & … & β^{q+1} \end{matrix} ]

is invertible modulo p. To do this, we show that p does not divide det(A). Factor out the power of β in each row that appears in the first column of A to get that det (A) = β^{q^{2}+1} det (V), where

V = [ \begin{matrix}1 & β^{q} & (β^{q})^{2} & … & (β^{q})^{q} \\ 1 & β^{2} & (β^{2})^{2} & … & (β^{2})^{q} \\ 1 & β^{4} & (β^{4})^{2} & … & (β^{4})^{q} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & β^{2q−2} & (β^{2q−2})^{2} & … & (β^{2q−2})^{q} \\ 1 & β & β^{2} & … & β^{q} \end{matrix} ] .

Now, V is a Vandermonde matrix, and its determinant is well-known. Labelling the entries of the second column of V as

x_{1} = β^{q}, x_{i} = β^{2i−2}, for i = 2, 3, …, q, and x_{q+1} = β,

we have that det(V) = ∏_{i>j}(x_{i} − x_{j}). Since |β|_{p} = 2q, the x_{i} are distinct powers of β in

𝔽_{p}, so that det(V) ≢ 0 (mod p), which proves the existence of a polynomial g(x) satisfying (1). There is no guarantee, however, that the polynomial g(x) produced here is such that a_{q+1} ≢ 0 (mod p), and so it could be that M is not empty for the sequence (g, 1, p). If, in fact, a_{q+1} ≢ 0 (mod p), then, since q + 1 < p − 1, we can invoke Lemma 4.1 on g(x) to produce a polynomial f(x) of degree at most p^{2} − 3p + q + 4 such that the sequence (f, 1, p) has the root pattern [β^{2}, β^{q}, β^{4}, …, β^{q}, β^{2q−2}, β^{q}, β, β^{q}] with M empty. On the other hand, if a_{q+1} ≡ 0 (mod p), we let h(x) = g(x) + x^{q+2}. Then the sequence (h, 1, p) has the root pattern [β^{2}, β^{q}, β^{4}, …, β^{q}, β^{2q−2}, β^{q}, β, β^{q}] with M empty. Since q + 2 < p − 1, Lemma 4.1 can be applied to h(x) which yields a polynomial f(x) of degree at most p^{2} − 3p + q + 5, such that the sequence (f, 1, p) has the root pattern [β^{q}, β^{4}, …, β^{q}, β^{2q−2}, β^{q}, β, β^{q}, β^{2},] with M empty, completing the proof of the theorem when p ≡ 3 (mod 4).

Now suppose that p ≡ 1 (mod 4). Let r ∈ 𝔽_{p} with |r|_{p} = 4. Since r ≢ −1 (mod p), there exists a with 2 ≤ a ≤ p − 1 such that a(r + 1) ≡ 1 (mod p). Then the following facts are easily derived, and we make use of them in the remainder of the proof:

|r^{3}|_{p} = 4, r^{2} ≡ (r^{3})^{2} ≡ −1 (mod p),

(2)

r^{3} ≡ r^{−1} ≡ −r ≡ a(r^{3} + 1) (mod p).

Define the polynomial f of degree 4a − 4 as

f := f(x) = x^{4a−4} + (x + 1) ∑_{k=0}^{a−2} x^{4k}.

Then, using (2) together with the fact that |r|_{p} = 4, we have that f(r) ≡ 1 − r (mod p), f(r^{2}) ≡ 1 (mod p), f(r^{3}) ≡ 0 (mod p), and consequently,

f(r^{2}) + (r^{2})^{4a−3} ≡ 1 + (−1)^{4a−3} ≡ 0 (mod p),

f(r) + r^{4a−3} + r^{4a−2} ≡ (1 − r) + (r)^{−3} + (r)^{−2} ≡ (1 − r) + r + (−1) ≡ 0 (mod p) and

f(r^{3}) + (r^{3})^{4a−3} + (r^{3})^{4a−2} + (r^{3})^{4a−1} + (r^{3})^{4a} ≡ 0 + (−r)^{4a−3} + (−r)^{4a−2} + (−r)^{4a−1} + 1

≡ −r^{−3} + r^{−2} − r^{−1} + 1 ≡ −r + (−1) − (−r) + 1 ≡ 0 (mod p).

Hence, (f, 1, p) has the root pattern [r^{2}, r, r^{2}, r^{3}] = [p − 1, r, p − 1, p − r] by Lemma 2.4, and M is empty.

We now show that f can be found with degree at most 2p − 6. Since r ≢ 1 (mod p), there exists b, with 2 ≤ b ≤ p − 1, such that b(−r + 1) ≡ 1 (mod p). Then b(r + 1) ≡ r (mod p) from (2). Since a(r + 1) ≡ 1 (mod p), we have a(−r + 1) ≡ −r (mod p) from (2), and thus

−r + 1 ≡ a(−r + 1) + 1 ≡ a(−r + 1) + a(r + 1) ≡ 2a (mod p).  (3)

Similarly,

r + 1 ≡ b(r + 1) + 1 ≡ b(r + 1) + b(−r + 1) ≡ 2b (mod p).  (4)

Combining (3) and (4), we have

a + b ≡ 1 (mod p).  (5)

Also, from either (3) or (4), we have

2ab ≡ (−r + 1)b ≡ 1 (mod p).  (6)

Since 2 ≤ a, b ≤ p−1, if both a and b are greater than or equal to \frac{p + 1}{2}, then (5) implies that

a = b = \frac{p + 1}{2}. But then, from (6), we have 1 ≡ 2ab ≡ 2 (\frac{p + 1}{2})^{2} (mod p), so that 2 ≡ 1

(mod p), which is impossible. Hence, at least one of a and b is smaller than \frac{p + 1}{2}. Therefore,

we can choose r such that a ≤ \frac{p − 1}{2}. Then the degree of f is 4a−4 ≤ 4 (\frac{p − 1}{2})−4 = 2p−6,

which completes the proof of the theorem.

We give two examples which illustrate Theorem 4.5.

Example 4.6. When p = 7, letting β = 3, the proof of the first part of Theorem 4.5 yields the polynomial g(x) = 4x^{4} + 3x^{3} + 5x^{2} + 6x + 1, which in turn produces f(x) = x^{31} +x^{26} +x^{25} +x^{22} +x^{20} +x^{19} +x^{16} +x^{15} +x^{14} +x^{13} +x^{10} +x^{9} +x^{8} +x^{7} +x^{4} +x^{3} +x^{2} +x+1, and (f, 1, 7) has the root pattern [6, 2, 6, 4, 6, 3] in 𝔽_{7}. Observe that this polynomial is quite different from the polynomial in Example 4.4, and the polynomial f̂(x) = x^{42} + x^{40} + x^{39} + x^{38} + x^{37} + x^{35} + ⋯ + x^{18} + x^{16} + … x^{5} + x^{3} + 1 constructed from Example 3.4 using the technique described in Section 2. However, for all three of these polynomials, M is empty, and their root patterns are equivalent.

Example 4.7. When p = 13, the proof of the second part of Theorem 4.5 produces the polynomial f(x) = x^{8} + x^{5} + x^{4} + x + 1, and (f, 1, 13) has the root pattern [12, 8, 12, 5] in 𝔽_{13}.

5 Some Open Questions

Computer evidence has led us to pose the following questions.

Question 5.1. If the sequence (f, k, p) has a root pattern in 𝔽_{p^{m}} for some m, then must M be finite or empty?

Question 5.2. Which of the sequences (1, 1, p) have M finite?

Question 5.3. If we fix any one or two of the parameters f, k and p, can we always find infinitely many values for the other parameter(s) such that the sequence (f, k, p) has M nonempty and finite?

6 Acknowledgments

The authors thank Michael Filaseta for suggesting the approach used in the proof of Theorem 4.1. The authors also thank the referee for the valuable suggestions.

References

[1] Michael Filaseta, Carrie Finch and Charles Nicol, On three questions concerning {0, 1}– polynomials, J. Théorie Nombres Bordeaux, to appear.

[2] M. Filaseta and A. Schinzel, On testing the divisibility of lacunary polynomials by cyclotomic polynomials, Math. Comp. 73 (2004), 957–965.

[3] W. J. Guerrier, The factorization of the cyclotomic polynomials mod p, Amer. Math. Monthly 75 (1968) 46.

[4] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th edition, Oxford University Press, 1979.

[5] Ramanujachary Kumanduri and Cristina Romero, Number Theory with Computer Applications, Prentice Hall, 1998.

[6] Melvyn B. Nathanson, Elementary Methods in Number Theory, Springer-Verlag, New York, 2000.

2000 Mathematics Subject Classification: Primary 11R09, 11A07; Secondary 11T06, 11C08, 11B50, 11B83. Keywords: polynomials; reducible; finite field.

Received December 19 2005; revised version received July 19 2006. Published in Journal of Integer Sequences, July 19 2006 .

Return to Journal of Integer Sequences home page.