\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
Sequences of Reducible $\left\{0,1\right\}$--Polynomials Modulo a Prime
}
\vskip 1cm
\large
Judith Canner \\
Department of Statistics \\
North Carolina State University \\
Raleigh, North Carolina 27695-8203 \\
USA\\
\href{mailto:jecanner@ncsu.edu}{\tt jecanner@ncsu.edu}\\
\ \\
Lenny Jones and Joseph Purdom \\
Department of Mathematics \\
Shippensburg University \\
Shippensburg, Pennsylvania 17257 \\
USA\\
\href{mailto:lkjone@ship.edu}{\tt lkjone@ship.edu}\\
\href{mailto:jp9506@ship.edu}{\tt jp9506@ship.edu}\\
\end{center}
\vskip .2 in
\begin{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
$\left\{0,1\right\}$--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\ge 5$ that there exists a $\left\{0,1\right\}$--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.
\end{abstract}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
% \documentclass[12pt,reqno]{article}
%
% \usepackage[usenames]{color}
%
% \usepackage{graphicx}
% \usepackage{amscd}
%
% \usepackage[colorlinks=true,
% linkcolor=webgreen,
% filecolor=webbrown,
% citecolor=webgreen]{hyperref}
%
% \definecolor{webgreen}{rgb}{0,.5,0}
% \definecolor{webbrown}{rgb}{.6,0,0}
%
% \usepackage{color}
% \usepackage{fullpage}
% \usepackage{float}
%
% \usepackage{psfig}
% \usepackage{graphics,amsmath,amssymb}
% \usepackage{amsfonts}
% \usepackage{latexsym}
% \usepackage{epsf}
%
% \usepackage{amsthm}
%
%
% \setlength{\textwidth}{6.5in}
% \setlength{\oddsidemargin}{.1in}
% \setlength{\evensidemargin}{.1in}
% \setlength{\topmargin}{-.5in}
% \setlength{\textheight}{8.9in}
%
% \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
%
% \begin{document}
%
% \begin{center}
% \epsfxsize=4in
% %\leavevmode\epsffile{logo129.eps}
% \end{center}
%
%
% \newtheorem{theorem}{Theorem}[section]
% \newtheorem{lemma}[theorem]{Lemma}
%
% \newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}[theorem]{Question}
% \newtheorem{proposition}[theorem]{Proposition}
% \newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{sch}[theorem]{Scholium}
% \newtheorem{guess}[theorem]{Guess}
\theoremstyle{remark}
\newtheorem*{remark}{Remark} %no numbering for remarks
\newtheorem*{rems}{Remarks}
% %\theoremstyle{remarks}
% \theoremstyle{note}
% \newtheorem*{note}{Note}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
%
% %\theoremstyle{example}
\newtheorem{example}[theorem]{Example}
%
\numberwithin{equation}{section}
\def\ds{\displaystyle}
\def\Z {{\mathbb Z}}
\def\F {{\mathbb F}}
\def\N{{\mathcal N}}
\def\Q {{\mathbb Q}}
\def\T {{\tilde T}}
\def\D {{\mathcal D}}
\def\N {{\mathcal N}}
\def\M {{\mathcal M}}
\def\H {{\mathcal H}}
\def\h {{\mathfrak h}}
\def\l {\left\langle}
\def\r {\right\rangle}
\def\bip{{\mathrm{Bip}}}
\def\k{{\mathbf k}}
\def\n{{\mathbf n}}
\vskip .2in
\renewcommand{\theequation}{\arabic{equation}}
\renewcommand{\theequation}{\arabic{equation}}
\section{Introduction}\label{Intro}
The following problem \cite{1} provided the motivation for this paper.\\
\begin{quote}
{\it Define a sequence of $\left\{ 0,1 \right\}$--polynomials (polynomials all of whose coefficients are either 0 or 1) in $\Q[x]$ by
\[f_{1}:=1 \hspace*{.21in} {\rm and} \hspace*{.21in} f_{i}:=f_{i-1}+x^{n}, \hspace*{.11in} {\rm for} \hspace*{.11in} i\ge 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 $\Q$.
Is this sequence infinite?}\\
\end{quote}
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 \cite{1} have proven the somewhat surprising fact that $f_8+x^n$ is irreducible over $\Q$ for all $n\ge 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\ge 1$ be an integer and let $f(x)$ be a polynomial, with $f(0)\not \equiv 0 \pmod{p}$. Define a sequence of polynomials in $\F_p[x]$, denoted $(f,k,p)$, as follows:
\[f_{1}:=f \hspace*{.21in} {\rm and} \hspace*{.21in} f_{i}:=f_{i-1}+x^{kn}, \hspace*{.11in} {\rm for} \hspace*{.11in} i\ge 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 $\F_p$.
We impose the restriction that $f(0)\not \equiv 0 \pmod{p}$ to avoid the trivial situation, and we do not require that $f$ be reducible or irreducible over $\F_p$.
Although we show that all sequences $(f,k,p)$ are infinite (see Theorem \ref{infinite}), this particular attribute is but one item of interest to us here (see Section \ref{Prelims}). Also, while our definition of the sequence $(f,k,p)$ does not require that $f$ be a $\left\{0,1\right\}$--polynomial, the predominate focus of this paper is on sequences where $f$ is a $\left\{0,1\right\}$--polynomial. The main reason for this is that in many situations of interest, even if $f$ is not a $\left\{0,1\right\}$--polynomial, there is a corresponding $\left\{0,1\right\}$--polynomial $g$, such that the sequence $(g,k,p)$ has many of the same properties as the sequence $(f,k,p)$ (see Lemma \ref{not01to01}).
\section{Preliminaries}\label{Prelims}
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:
\begin{definition}
Let $p$ be a prime and let $\F_{p^m}$ denote the finite field with $p^m$ elements. Let $(f,k,p)$ be a sequence as defined in Section \ref{Intro}, allowing the possibility that $f$ is not necessarily a $\left\{0,1\right\}$--polynomial, but as always, $f(0)\not \equiv 0 \pmod{p}$.
\begin{itemize}
\item We say $(f,k,p)$ has the {\it root pattern} $[r_1,r_2,\dots , r_t]$
in $\F_{p^m}$ if $r_i\in \F_{p^m}$ and
$f_{N+b}(r_i)\equiv 0 \pmod{p}$
for some positive integer $N$ and all
positive integers $b\equiv i\pmod{t}$.
\item 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)$.
\item We say $(f,k,p)$ has the {\it factor pattern}
$[g_1,g_2,\dots , g_t]$ in $\F_p[x]$ if the polynomial $g_i$ is a proper divisor of
$f_{N+b}$ in $\F_p[x]$ for some positive integer $N$ and all positive integers $b\equiv i \pmod{t}$.
\item If the sequence $(f,k,p)$ has the root pattern $[r_1,r_2,\dots , r_j]$ (respectively, factor pattern $[g_1,g_2,\dots , g_j]$), then we say the root pattern (respectively, factor pattern) has {\it 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,\dots , t$. Throughout the remainder of this paper, we indicate all root and factor patterns as $[r_1,r_2,\dots , r_t]$ or $[g_1,g_2,\dots , g_t]$, where $t$ is the period of the pattern.
\end{itemize}
\end{definition}
We consider the root patterns $[r_i,r_{i+1},\dots, r_t,r_1, \dots ,r_{i-1}]$, for any $2\le i \le t$, to be equivalent to the root pattern $[r_1,r_2,\dots ,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 \ref{p=7}).
Factor patterns and root patterns are related in the following way. Suppose that $(f,k,p)$ has a factor pattern $\left[g_1,g_2,\dots ,g_t\right]$ in $\F_p[x]$, with $\delta_i$ the degree of $g_i$, and $m$=lcm($\delta_1,\delta_2,\dots ,\delta_t$). Let $g$ be a polynomial of degree $m$ which is irreducible over $\F_p$. Then $(f,k,p)$ has a root pattern in $\F_p(\alpha)\cong \F_{p^m}$, where $g(\alpha)\equiv 0 \pmod{p}$. (see Example \ref{root pattern extension field}). Conversely, if $(f,k,p)$ has a root pattern in $\F_{p^m}$, then $(f,k,p)$ has a factor pattern in $\F_{p^h}[x]$ for all $h$ with $1\le h \le 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 $\F_p$, or a factor pattern in $\F_p[x]$, then $\M$ is not infinite (Question \ref{rootpatternimpliesnotinfinite}), the converse is false (see Example \ref{(1,4,3)} and Theorem \ref{empty}).
When $\M$ is finite for a sequence $(f,k,p)$, we can use $\M$ to construct a polynomial $\hat{f}$ such that $\M$ is empty for the sequence $(\hat{f},k,p)$. Explicitly, if $\M=\left\{km_1,km_2,\dots ,km_s\right\}$ for the sequence $(f,k,p)$, where the degree of $f$ is $kd$, then let $\hat{f}(x)=f(x)+\sum_{j=d+1}^{m_s+1}a_jx^{kj}$ be the polynomial of degree $k(m_s+1)$ such that $a_j=0$ when $kj\in \M$, and $a_j=1$ otherwise. Then $\M$ is empty for the sequence $(\hat{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 \ref{not01to01} and Theorem \ref{rootpatternpoly}. See also Example \ref{p=7,again}.
The first main result of this article is Theorem \ref{infinite}, where we see that the situation over $\F_p$ is quite different than it is over $\Q$, in that no sequence $(f,k,p)$ is ever finite. Next, Theorem \ref{p=2,3} shows that no root patterns exist in $\F_p$ for the sequences $(f,k,2)$ and $(f,k,3)$. Then, for the sequences $(1,k,p)$, we establish in Theorem \ref{empty}, 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 $\F_{p^m}$ for any $m$. Finally, for $p\ge 5$, we prove in Theorem \ref{rootpatternpoly} that there exists a $\left\{0,1\right\}$--polynomial $f$ such that the sequence $(f,1,p)$ has a root pattern in $\F_p$ with $\M$ empty.
Throughout this paper we let
$|a|_{p^m}$ denote the order of $a$ in $\left( \F_{p^m} \right)^{*}$, the multiplicative group of $\F_{p^m}$, and we let $\Phi_n:=\Phi_n(x)$ denote the $n$-th cyclotomic polynomial.
Lemma \ref{primitiveroots}, Lemma \ref{Cyclo} and Lemma \ref{splitting} are stated without proof since they contain information which is well-known.\\
\begin{lemma}\label{primitiveroots}\text{}
\begin{itemize}
\item 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\ge 1$ is an integer.
\item Let $q$ be an odd prime. If $\alpha$ is a primitive root modulo $q^a$ for some $a\ge 2$, then $\alpha$ is a primitive root modulo $q^a$ for all $a\ge 1$.\\
\end{itemize}
\end{lemma}
\begin{lemma}\label{Cyclo}\text{}
\begin{itemize}
\item If $p$ is a prime that divides $n$, then $\Phi_n(x^p)=\Phi_{pn}(x).$
\item $\Phi_n(x^k)$ is irreducible over $\Q$ if and only if every prime divisor of $k$ divides $n$.
\item Let $n$ and $k$ be relatively prime. Then $\Phi_{n}(x^k)=\prod_{d|k}\Phi_{dn}(x).$\\
\end{itemize}
\end{lemma}
\begin{lemma}\label{splitting}
Let $p$ be a prime, and let $g(x)$ be a polynomial over $\F_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)$.\\
\end{lemma}
In the investigation of the reducibility over $\Q$ of certain polynomials, it is sometimes fruitful, and more efficient, to first test for divisibility by cyclotomic polynomials \cite{2}.
Cyclotomic polynomials also play a role here in determining the reducibility of certain $\{0,1\}$--polynomials over $\F_p$. A slight adjustment is required since cyclotomic polynomials do not always remain irreducible modulo a prime. Theorem \ref{Cyclomodp}
describes explicitly the factorization of cyclotomic polynomials in $\F_p[x]$.
\begin{theorem}\label{Cyclomodp}{\rm \cite{3}}
Let $p$ be a prime, and let $n=p^am$ be a positive integer, where $p$ does not divide $m$. Let $b$ be the smallest positive integer such that $p^b \equiv 1 \pmod{m}$. Then $\Phi_n(x)$ factors as the product of $\ds \frac{\phi(m)}{b}$ incongruent irreducible monic polynomials modulo $p$, each of degree $b$, and each raised to the $\phi(p^a)$ power.
\end{theorem}
We also make use of the following immediate corollary of Theorem \ref{Cyclomodp} in the proof of Theorem \ref{empty}.
\begin{corollary}\label{Cycloreducmodp}
Let $p$ be a prime, and let $n=p^am$ be a positive integer, where $p$ does not divide $m$. Then $\Phi_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$.
\end{corollary}
Although straightforward, Lemma \ref{rootperiod} provides insight into the basic understanding of root patterns for the sequences $(f,k,p)$.
\begin{lemma}\label{rootperiod}
Let $p$ be a prime, and let $r \in \F_{p^m}$, with $|r|_{p^m}=s\ne 1$. Let $k\ge 1$ be an integer, and let $a=\gcd(s,k)$. For any polynomial $g(x)$ and any $n\ge 0$, define the polynomial $h(x):=g(x)+x^{k(n+1)}+x^{k(n+2)}+\dots +x^{k(n+b)}$, where $b=p$ if $a=s$, and $b=s/a$ otherwise. Then $g(r)\equiv 0 \pmod{p}$ if and only if $h(r)\equiv 0 \pmod{p}$.
\end{lemma}
\begin{proof}
If $a=s$, then clearly $h(r)\equiv g(r) \pmod{p}.$ Otherwise, we have\vspace*{.21in}\\
$\ds \begin{array}{rl}
h(r)&= g(r)+r^{k(n+1)}+r^{k(n+2)}+\dots + r^{k(n+b)}\\
&\\
&= g(r)+r^{k(n+1)}(1+r^k+(r^k)^2+\dots + (r^k)^{b-1})\\
&\\
&= g(r)+r^{k(n+1)}\left( \ds \frac{(r^k)^b-1}{r^k-1} \right)\\
&\\
&= g(r)+r^{k(n+1)}\left( \ds \frac{(r^s)^{k/a}-1}{r^k-1} \right)\\
&\\
&\equiv g(r) \pmod{p},\vspace*{.21in}\\
\end{array}$\\ and the lemma follows.
\end{proof}
Before we present our main results, we give some
examples of sequences $(f,k,p)$.
\section{Examples of Sequences $(f,k,p)$}\label{Examples}
In the following examples, a computer was used to determine likely candidates for $\M$, and, with the exception of Example \ref{(1,4,3)}, Lemma \ref{rootperiod} was used to verify this evidence by establishing the existence of any root or factor patterns.
\begin{example}\label{(1,4,3)}
$(1,4,3)$
Although this example is a special case of Theorem \ref{empty}(\ref{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+\dots + x^{4(n-1)}$, for $n\ge 2$. First note that $x^4+1=(x^2+x+2)(x^2+2x+2)$ over $\F_3$ so that $f_2=1+x^4$. When $n\equiv 0,1,3,5 \pmod{6}$, there exists an odd prime $q$ that divides $n$, and it is easy to show then that $\Phi_q$ is a proper divisor of $1+x^4+x^8+\dots + x^{4(n-1)}$. Similarly, when $n\equiv 2,4 \pmod{6}$, with $n>2$, we have that $\Phi_8$ is a proper divisor of $1+x^4+x^8+\dots + 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\equiv 0 \pmod{3}$ proves that $(1,4,3)$ has no root pattern in $\F_{3}$.
\end{example}
\begin{example}\label{(1+x,1,5)}
$(1+x,1,5)$
First note that $1+x+x^2$ and $1+x+x^3$ are irreducible over $\F_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 \ref{rootperiod}, $(1+x,1,5)$ has the root pattern $[3,4,2,4]$ in $\F_5$, and $\M=\left\{ 2,3\right\}.$
\end{example}
\begin{example}
$(1,1,5)$\label{(1,1,5)}
While this sequence has the same root pattern
$\left[3,4,2,4\right]$ in $\F_5$ as the sequence $(1+x,1,5)$ in Example \ref{(1+x,1,5)}, we see that the pattern does not emerge as soon in this sequence since here $\M=\left\{1, 3, 12, 25, 36, 37, 49, 323, 1985, 4054, 5885, 6648\right\}.$
\end{example}
\begin{example}\label{p=7}
$(1,1,7)$
There are, in fact, two root patterns for this sequence in $\F_7$: $[4,2,3,4,2,6]$ and $[4,6,3,6,2,6]$. Here, $\M=\left\{1,2,4,17,36,41\right\}$.
\end{example}
\begin{example}
$(1+x,1,17)$
This sequence has the root pattern $[8,16,9,4,2,16,15,4]$ in $\F_{17}$, and $\M=\left\{2,5,8,11,24\right\}$.
\end{example}
\begin{example}\label{root pattern extension field}
$(1+x+x^2+x^5+x^6+x^8+x^{10},1,3)$
This sequence has the root pattern $[2,\alpha,2,\alpha+1,2,\alpha,2,\alpha+2]$ in $\F_9$, where $\alpha^2+1=0$. The corresponding factor pattern in $\F_3$ is given by
$[g_1,g_2,\dots, g_8]$, where
\begin{center}$\begin{array}{l}
g_1=g_3=g_5=g_7=x-2\vspace*{.11in}\\
g_2=g_6=x^2+1\vspace*{.11in}\\
g_4=x^2+x+2\hspace*{.11in} {\rm and}\vspace*{.11in}\\
g_8=x^2+2x+2.
\end{array}$\\
\end{center} Here, $\M$ is empty.
\end{example}
\section{Main Results}
\begin{theorem}\label{infinite}
Every sequence $(f,k,p)$ is infinite.
\end{theorem}
\begin{proof}
For any prime $p$, positive integer $k$, and polynomial $h(x)\in \F_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\ge 1$. Also, $L$ divides $p^m+a$ by the choices of $m$ and $v$. Hence, $k$ divides $p^m+a$.
By Lemma \ref{splitting}, $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\left(x^{p^m}-x\right)=h(x)+x^{p^m+a},\]
establishing the claim with $t=p^m+a$, and completing the proof of the theorem.
\end{proof}
\begin{theorem}\label{p=2,3}
Let $p=2$ or 3. Then the sequence $(f,k,p)$ does not have a root pattern in $\F_p$.
\end{theorem}
\begin{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\equiv f_i(1)\equiv f_{i+2}(1)=f_i(1)+1+1\equiv 2 \pmod{3},\] which is impossible.
\end{proof}
\begin{theorem}\label{empty}\text{ }
\begin{enumerate}
\item \label{1} If $k=1$, then $\M$ is never empty for the sequence $(1,k,p)$ for any prime $p$.
\item \label{2} If $k=2$, then $\M$ is empty for the sequence $(1,k,p)$ if and only if $p=2$ or $p\equiv 1 \pmod{4}$.
\item \label{3} If $k\ge 3$, then $\M$ is empty for the sequence $(1,k,p)$ if and only if $k\ne q^a$, where $a\ge 1$, and $q\ge 3$ is a prime such that $p$ is a primitive root modulo $q^2$.
\end{enumerate}
Moreover, in each case that $\M$ is empty, the sequence $(1,k,p)$ has no root pattern in $\F_{p^m}$ for any $m$.
\end{theorem}
\begin{proof}
We first establish parts (\ref{1}), (\ref{2}) and (\ref{3}) of the theorem, and then show that when $\M$ is empty, the sequence $(1,k,p)$ has no root pattern in $\F_{p^m}$ for any $m$.
Throughout the proof, for $n\ge 2$, we let $g_n:=g_n(x)=1+x^k+x^{2k}+\dots +x^{(n-1)k}$.
When $k=1$, we have that $1\in \M$, since $1+x$ is irreducible for all primes $p$. So, statement (\ref{1}) of the theorem is obvious.
Making use of the fact that $\Phi_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 \ge 2$, or equivalently, when $g_n(x)$ is reducible over $\F_p$ for all $n\ge 2$. First note that
\[\deg\left(\Phi_n\left(x^k\right)\right)=\phi(n)k\le(n-1)k=\deg \left(g_n\left(x\right)\right).\]
Therefore, since $\Phi_n(x^k)$ divides $g_n(x)$ for all $n\ge 2$, it follows that $g_n(x)$ is reducible over $\Q$, and hence over $\F_p$, except possibly when $n$ is a prime $q$. Also, by Lemma \ref{Cyclo}, $\Phi_q\left(x^k\right)$ is reducible over $\Q$, and hence over $\F_p$, if there exists a prime divisor $r$ of $k$ with $r\ne q$. Thus, for $k\ge 2$, we have that $\M$ is empty when $k\ne q^a$, for some prime $q$ with $a\ge 1$. Consequently, our focus is narrowed to the examination of when $\Phi_q\left(x^{q^a}\right)=\Phi_{q^{a+1}}\left(x\right)$, with $a\ge 1$, is reducible over $\F_p$.
If $k=q=2$, then $a=1$, and $\Phi_{q^{a+1}}\left(x\right)=\Phi_4(x)=x^2+1$, which is easily seen to be reducible over $\F_p$ if and only if $p=2$ or $p\equiv 1 \pmod{4}$. Combining this fact with the above discussion completes the proof of statement (\ref{2}) of the theorem.
When $k=2^a$, with $a\ge 2$, we have immediately, from Lemma \ref{primitiveroots} and Corollary \ref{Cycloreducmodp}, that $\Phi_{2^{a+1}}\left(x\right)$ is reducible over $\F_p$ for all primes $p$. When $k=q^a$, for some prime $q\ge 3$, with $a\ge 1$, we appeal again to Lemma \ref{primitiveroots} and Corollary \ref{Cycloreducmodp} to conclude that $\Phi_{q^{a+1}}\left(x\right)$ is irreducible over $\F_p$ if and only if $p$ is a primitive root modulo $q^2$. Therefore, statement (\ref{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 $\F_{p^m}$ for all $m$. We do this by showing that $(1,k,p)$ has no factor pattern in $\F_p[x]$. Note that under the assumption that $\M$ is empty, we have that $f_n=g_n$ for all $n\ge 2$, so we use the notation $g_n$. Let $q>p$ be prime. For any divisor $d$ of $k$, we can write $dq=p^aqm_d$, where $p$ does not divide $m_d$. Let $b$ be the smallest positive integer such that $p^b\equiv 1 \pmod{qm_d}.$ Since
\[p^b>p^b-1\ge qm_d\ge q,\]
we have that $b>\log\left(q\right)/\log\left(p\right)$. Therefore, from Theorem \ref{Cyclomodp}, each irreducible factor of $\Phi_{dk}(x)$ modulo $p$ has degree larger than $\log\left(q\right)/\log\left(p\right)$, and this is independent of the divisor $d$. Since
\[g_q(x)=\Phi_q\left(x^k\right)=\prod_{d|k}\Phi_{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 $\F_p[x]$.
\end{proof}
The following lemma, which is needed for the proof of Theorem \ref{rootpatternpoly}, indicates in certain situations how a sequence whose terms are not all $\left\{0,1 \right\}$--polynomials can be used to construct a sequence where all terms are $\left\{0,1 \right\}$--polynomials, and such that the two sequences share particular properties.
\begin{lemma}\label{not01to01}
Let $p$ be a prime and let $g(x)=1+\sum_{i=1}^da_ix^i$ be a polynomial of degree $d\le p-1$ that is not a $\left\{0,1\right\}$--polynomial in $\F_p[x]$. Suppose that the sequence $(g,1,p)$ has a root pattern in $\F_p$ and that $\M$ is empty. Then there exists a $\left\{0,1\right\}$--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 $\F_p$, and $\M$ is empty.
\end{lemma}
\begin{proof}
The following two-step algorithm, which incorporates Fermat's Little Theorem, is used to construct $f(x)$.
\begin{enumerate}
\item Replace every non-constant term $a_ix^i$ of $g(x)$ with\\ $\sum_{j=0}^{a_i-1}x^{i+j(p-1)}$. Since $1\le i \le p-1$, we have that no two exponents of the resulting polynomial are the same. That is, this step produces a $\left\{0,1\right\}$--polynomial $g_1(x)$ such that $g_1(x) \equiv g(x) \pmod{p}$ for all $x\in \F_p$, and the degree of $g_1(x)$ is $d_1=\ds \max_{1\le i\le d}\left\{i+(a_i-1)(p-1) \right\}$.
\item 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.$
\end{enumerate}
Then, if the root pattern for the sequence $(g,1,p)$ is $[r_1,r_2,\dots ,r_t]$, this definition of $f(x)$ guarantees that the sequence $(f,1,p)$ has the equivalent root pattern $[r_2,r_3,\dots ,r_t,r_1]$, and that $\M$ is empty. Since $d_1\le 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.$
\end{proof}
We give an example to illustrate Lemma \ref{not01to01}.
\begin{example}\label{exnot01to01} 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 $\F_7$, which begins with the addition of $x^5$. Using Lemma \ref{not01to01}, 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$. %Then, for $r\in \F_p$, we have $f(r)\equiv g(r) \pmod{p}$. Also, the
The sequence $(f,1,7)$, with the equivalent root pattern $[6,4,6,3,6,2]$ in $\F_7$, has $\M$ empty, and is constructed by adding consecutively $x^{36}$, $x^{35}$, $\dots$, instead of, respectively $x^5$, $x^6$, $\dots$, 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}$.
\end{example}
\begin{theorem}\label{rootpatternpoly}
For any prime $p\ge 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 $\F_p$, and $\M$ is empty. Moreover, if $p\equiv 3\pmod{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\equiv 1\pmod{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$.
\end{theorem}
\begin{remark}
The proof of Theorem \ref{rootpatternpoly} is constructive, and although the technique we use to construct $f$ when $p\equiv 3 \pmod{4}$ can be modified slightly to construct $f$ when $p\equiv 1 \pmod{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.
\end{remark}
\begin{proof}
Suppose first that $p\equiv 3\pmod{4}$, and let $q$ be the smallest odd prime factor of $p-1$. Let $\beta \in \F_p$ with $|\beta|_p=2q$. Then
\[|\beta^2|_p=|\beta^4|_p=\dots =|\beta^{2q-2}|_p=q\hspace*{.11in}{\rm and} \hspace*{.11in} |\beta^q|_p=2.\] If we can demonstrate the existence of a polynomial $g(x)=1+\sum_{i=1}^{q+1}a_ix^i$, with $a_{q+1}\not \equiv 0 \pmod{p}$,
satisfying all of the following conditions:
\begin{eqnarray}\label{system}
\hspace*{.61in} g(\beta^q)+(\beta^q)^{q+2}\equiv 0 \pmod{p}\nonumber\\ \nonumber\\
\hspace*{.61in} g(\beta^2)+(\beta^2)^{q+2}+(\beta^2)^{q+3}\equiv 0 \pmod{p}\nonumber\\ \nonumber\\
\hspace*{.61in} g(\beta^4)+(\beta^4)^{q+2}+(\beta^4)^{q+3}+(\beta^4)^{q+4}+(\beta^4)^{q+5}\equiv 0 \pmod{p}\nonumber\\
\hspace*{.61in} \hspace*{.7in}\vdots \hspace*{.7in} \vdots \hspace*{.7in} \vdots \hspace*{.7in} \vdots \hspace*{.7in} \vdots \hspace*{.3in} \\
\hspace*{.61in} g(\beta^{2q-2})+(\beta^{2q-2})^{q+2}+\dots +(\beta^{2q-2})^{3q-1}\equiv 0 \pmod{p}\nonumber\\ \nonumber\\
\hspace*{.61in} g(\beta)+\beta^{q+2}+\beta^{q+3}+\dots +\beta^{3q+1}\equiv 0 \pmod{p},\nonumber \\ \nonumber \end{eqnarray}
then $g(x)$ has the root pattern $[\beta^q,\beta^2,\beta^q,\beta^4,\dots ,\beta^q,\beta^{2q-2},\beta^q,\beta]$ by Lemma \ref{rootperiod}, clearly $\M$ is empty since $a_{q+1}\not \equiv 0 \pmod{p}$, and using Lemma \ref{not01to01}, we can construct the desired polynomial $f(x)$.
The conditions imposed on $g(x)$ in (\ref{system}) give a system of $q+1$ linear equations in the $q+1$ variables $a_1,a_2,\dots ,a_{q+1}$. Thus, to show the existence of a polynomial $g(x)\in \F_p[x]$ satisfying (\ref{system}), it suffices to show that the coefficient matrix
\[A=\left[ \begin{array}{ccccc}
\beta^q & (\beta^q)^2 & (\beta^q)^3 & \dots & (\beta^q)^{q+1}\\
\beta^2 & (\beta^2)^2 & (\beta^2)^3 & \dots & (\beta^2)^{q+1}\\
\beta^4 & (\beta^4)^2 & (\beta^4)^3 & \dots & (\beta^4)^{q+1}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
\beta^{2q-2} & (\beta^{2q-2})^2 & (\beta^{2q-2})^3 & \dots & (\beta^{2q-2})^{q+1}\\
\beta & \beta^2 & \beta^3 & \dots & \beta^{q+1}\\
\end{array} \right]\]
is invertible modulo $p$. To do this, we show that $p$ does not divide $\det(A)$. Factor out the power of $\beta$ in each row that appears in the first column of $A$ to get
that $\det\left( A \right)=\beta^{q^2+1}\det\left( V \right)$, where
\[V=\left[ \begin{array}{ccccc}
1 & \beta^q & (\beta^q)^2 & \dots & (\beta^q)^{q}\\
1 & \beta^2 & (\beta^2)^2 & \dots & (\beta^2)^{q}\\
1 & \beta^4 & (\beta^4)^2 & \dots & (\beta^4)^{q}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & \beta^{2q-2} & (\beta^{2q-2})^2 & \dots & (\beta^{2q-2})^{q}\\
1 & \beta & \beta^2 & \dots & \beta^{q}\\
\end{array} \right].\]
Now, $V$ is a Vandermonde matrix, and its determinant is well-known. Labelling the entries of the second column of $V$ as
\[x_1=\beta^q,\hspace*{.29in}x_i=\beta^{2i-2},\hspace*{.11in}{\rm for}\hspace*{.11in}i=2,3,\dots, q,\hspace*{.29in}{\rm and}\hspace*{.29in}x_{q+1}=\beta,\]
we have that $\det(V)=\ds \prod_{i>j}(x_i-x_j)$. Since $\left| \beta \right|_p=2q$, the $x_i$ are distinct powers of $\beta$ in $\F_p$, so that $\det(V)\not \equiv 0 \pmod{p}$, which proves the existence of a polynomial $g(x)$ satisfying (\ref{system}). There is no guarantee, however, that the polynomial $g(x)$ produced here is such that $a_{q+1}\not \equiv 0 \pmod{p}$, and so it could be that $\M$ is not empty for the sequence $(g,1,p)$. If, in fact, $a_{q+1}\not \equiv 0 \pmod{p},$ then, since $q+1