\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \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} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}} \def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}} \DeclareMathOperator{\Res}{Res} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A Note on Polynomial Sequences \\ \vskip .1in Modulo Integers } \vskip 1cm \large Mohammad Javaheri\\ Department of Mathematics\\ School of Science\\ Siena College \\ Loudonville, NY 12211 \\ USA \\ \href{mailto:mjavaheri@siena.edu}{\tt mjavaheri@siena.edu} \\ \end{center} \vskip .2 in \begin{abstract} We study the uniform distribution of the polynomial sequence $\lambda(P)=(\lfloor P(k) \rfloor )_{k\geq 1}$ modulo integers, where $P(x)$ is a polynomial with real coefficients. In the nonlinear case, we show that $\lambda(P)$ is uniformly distributed in $\mathbb{Z}$ 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: $\lambda(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. \end{abstract} \section{Introduction} A sequence $(r_k)_{k\geq 1}$ of real numbers is said to be \textit{u.d.\ mod $1$} if for all $0\leq a0$, then the sequence $( \lfloor f(k)\rfloor )_{k\geq 1}$ is u.d.\ in $\mathbb{Z}$ for almost all $\alpha>1$. This follows from Koksma's theorem \cite{Leveque}. \end{example} Niven \cite{niven} showed that, given a nonlinear polynomial $P(x) \in \mathbb{Z}[x]$, there exist infinitely many integers $m$ such that $(P(k) )_{k\geq 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: \begin{theorem}\label{all2} Let $P(x)$ be a polynomial with real coefficients. The sequence $(\lfloor P(k) \rfloor )_{k\geq 1}$ is u.d.\ in $\mathbb{Z}$ 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$. \end{theorem} In the linear case, Theorem \ref{all2} follows from Theorem \ref{linear2}, and in the nonlinear case, it follows from Theorem \ref{nonlinear3} or Theorem \ref{nonlinear2}. By adding the least integer operation to the arithmetic operations involved in defining polynomials, we obtain {\it generalized polynomials}. For example, $f(x)=\lfloor \lfloor a_1x^2+a_2 \rfloor x \rfloor + \lfloor a_3x+a_4 \rfloor x^2$ is a generalized polynomial. Hal\r{a}nd \cite{udgp} 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\geq 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 $\lfloor P(x) \rfloor$ modulo integers, where $P(x)$ is a real polynomial. \begin{definition}\label{defcomplete} We say a polynomial $P(x) \in \mathbb{R}[x]$ is {\it complete} modulo $m$ if, for every integer $n$, the equation $\lfloor P(x) \rfloor \equiv n$ (mod $m$) has a solution $x\in \mathbb{Z}$. We say $P(x)$ is complete in $\mathbb{Z}$ if it is complete modulo every integer $m$ (or equivalently modulo all $m$ large enough). \end{definition} It follows from Example \ref{weylpol} that, if $P(x)$ has at least one irrational coefficient other than the constant term, then $P(x)$ is complete in $\mathbb{Z}$. The converse is not true in degree 1 (compare Theorems \ref{linear2} and \ref{linear3}). However, we will show in the following theorem that, at least in the even degree case, the converse is true. \begin{theorem}\label{gppmain} Let $P(x)$ be an even-degree polynomial with real coefficients. Then the following statements are equivalent: \begin{itemize} \item[i.] $P(x)$ is complete modulo all primes large enough. \item[ii.] $P(x)$ has an irrational coefficients other than the constant term. \item[iii.] The sequence $(\lfloor P(k) \rfloor )_{k\geq 1}$ is u.d.\ in $\mathbb{Z}$. \item[iv.] $P(x)$ is complete modulo all integers. \end{itemize} \end{theorem} We prove Theorem \ref{gppmain} in Section \ref{compevendeg}. Finally, in Section \ref{compmonom}, we consider polynomials of the form $P(x)=ax^n+c$, where $n>1$ and $a, c \in \mathbb{R}$. In Theorem \ref{mon}, we show that $P(x)$ is complete modulo all primes large enough if and only if $a\notin \mathbb{Q}$. \section{u.d.\ polynomial sequences }\label{udpolyseq} In this section, we determine all polynomials $P(x) \in \mathbb{R}[x]$ for which the sequence $( \lfloor P(k) \rfloor )_{k\geq 1}$ is u.d.\ in $\mathbb{Z}$. Niven \cite[Thm.\ 3.1]{niven} showed that the sequence $( \lfloor \alpha k \rfloor )_{k\geq 1}$ is u.d.\ in $\mathbb{Z}$ if and only if $\alpha$ is irrational or $\alpha=1/l$ for some nonzero integer $l$. By Example \ref{weylpol}, the sequence $( \lfloor \alpha k+ \beta \rfloor )_{k\geq 1}$ is u.d.\ in $\mathbb{Z}$ for every irrational number $\alpha$. We will prove in Theorem \ref{linear2} that if the sequence $(\lfloor \alpha k+ \beta \rfloor )_{k\geq 1}$ is u.d.\ in $\mathbb{Z}$, then either $\alpha$ is irrational or $\alpha=1/l$ for some nonzero integer $l$. First, we need a lemma. \begin{lemma}\label{abm} Let $a,b \in \mathbb{Z}$ such that $\gcd(a,b)=1$ and $b>0$. Let $\beta \in \mathbb{R}$. Then the sequence $(\lfloor ak/b+\beta \rfloor )_{k\geq 1}$ is u.d.\ mod $m$ if and only if $\gcd(a,m)=1$. \end{lemma} \begin{proof} First, suppose that the sequence $(\lfloor ak/b+\beta \rfloor )_{k \geq 1}$ is u.d.\ mod $m$. Suppose that $d=\gcd(a,m)>1$, and we derive a contradiction. Since we have assumed that $( \lfloor ak/b+\beta \rfloor )_{k\geq 1}$ is u.d.\ mod $m$, it follows that the sequence $(\lfloor ak/b+\beta \rfloor )_{k\geq 1}$ is u.d.\ mod $d$ \cite[Thm.\ 5.1]{niven}. One notes that the sequence $( \lfloor ak/b+\beta \rfloor )_{k\geq 1}$ modulo $d$ is periodic with period $b$. Therefore, if the number of solutions of $\lfloor ak/b+\beta \rfloor \equiv 0$ (mod $d$) with $1\leq k \leq b$ is given by $t$, then the number of solutions of $\lfloor ak/b+\beta \rfloor \equiv 0$ (mod $d$) with $1\leq k \leq sb$ is given by $st$, and so $$\lim_{s \rightarrow \infty}\dfrac{1}{sb} \# \left \{ k \in \{1,\ldots, sb\}: \lfloor ak/b+\beta \rfloor \equiv \modd{0} {d} \right \} =\lim_{s \rightarrow \infty}\dfrac{st}{sb}=\dfrac{t}{b}.$$ On the other hand, this limit must equal $1/d$ by the definition of u.d.\ mod $d$ (see equation \eqref{defud}). It follows that $t/b=1/d$, and so $d \mid b$. Since $d \mid a$ and $\gcd(a,b)=1$, we have a contradiction. For the converse, suppose that $\gcd(a,m)=1$. One notes that the sequence $(\lfloor ak/b+\beta \rfloor )_{k\geq 1}$ is periodic modulo $m$ with period $bm$. For each $0\leq i \leq m-1$, let $T_i$ denote the subset of elements $k \in \{1,\ldots, bm\}$ such that $\lfloor ak/b+\beta \rfloor \equiv i$ (mod $m$). We show that $|T_i|=b$ for all $0\leq i \leq m-1$. Fix $0 \leq i \leq m-1$, and let $T_i=\{t_1,\ldots, t_r\}$. For each $1\leq j \leq r$, we have $$\lfloor a(t_j+b)/b+\beta \rfloor \equiv a+ \lfloor at_j/b+\beta \rfloor \equiv \modd{a+i} {m}.$$ In other words, the map $t_j \mapsto 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}| \geq |T_i|$, and so $|T_{qa+i}| \geq |T_i|$ for all $q \geq 0$, where $qa+i$ is computed modulo $bm$. Since $\gcd(a,m)=1$, we conclude that $|T_{i'}| \geq |T_i|$ for all $i,i'=0,\ldots, m-1$, and so $|T_i|=b$ for all $i=0,\ldots, m-1$. Thus, for $N=Qbm+R$, $0\leq R1$, and $b>0$. It follows from Lemma \ref{abm} that the sequence $( \lfloor ak/b+\beta \rfloor )_{k\geq 1}$ is not u.d.\ mod $|a|$, hence it is not u.d.\ in $\mathbb{Z}$. \end{proof} Next, we discuss nonlinear polynomials. Niven \cite[Thm.\ 4.1]{niven} proved that if $P(x)$ is a nonlinear polynomial with integer coefficients, then there exist infinitely many integers $m$ such that $(P(k))_{k\geq 1}$ is not u.d.\ mod $m$. We prove generalizations of this statement in the next two theorems. \begin{theorem}\label{nonlinear3} 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 $(\lfloor P(k) \rfloor )_{k \geq 1}$ is not u.d.\ mod $m$. \end{theorem} \begin{proof} Let $P(x)=\sum_{i=0}^n a_ix^i$ such that $a_i=r_i/s_i \in \mathbb{Q}$ with $\gcd(r_i,s_i)=1$ for all $1\leq i \leq n$. Let $N$ be the least common multiple of $s_i$, $1\leq i \leq n$, and let $Q(x)=N(P(x)-P(0)) \in \mathbb{Z}[x]$. Choose an integer $a$ such that $Q^\prime(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) \equiv 0$ (mod $p^2$) and $f^\prime(a) \equiv 0$ (mod $p$). It follows from Hensel's Lemma \cite[Thm.\ 3.4.1]{Gouvea} that $f(a+kp) \equiv f(a) \equiv 0$ (mod $p^2$) for all integer values of $k$. In particular, the equation $Q(x) \equiv Q(a)$ (mod $p^2$) has at least $p$ solutions for $x\in \{1,\ldots, p^2\}$. It follows that, given an integer $s\geq 1$, we have $|T|\geq sp$, where $T$ denotes the set of solutions $x \in \{1,\ldots, sp^2\}$ of $Q(x) \equiv Q(a)$ (mod $p^2$). We show that the sequence $(\lfloor P(k) \rfloor )_{k\geq 1}$ is not u.d.\ mod $m=p^{2}$. On the contrary, suppose that $(\lfloor P(k) \rfloor )_{k\geq 1}$ is u.d.\ mod $p^2$. It follows from the definition that for each $0 \leq t < p^2$, $$\lim_{s \rightarrow \infty}\dfrac{1}{sp^2} |S_t|=\dfrac{1}{p^2},$$ where $S_t$ is the set of $x\in \{1,\ldots, sp^2\}$ such that $\lfloor P(x) \rfloor \equiv t$ (mod $p^2$). In particular, for $s$ large enough, one has \begin{equation}\label{lims2} \dfrac{1}{sp^2}|S_t|\leq \dfrac{2}{p^2} \end{equation} for all $0\leq t 6sN$, it follows that there exists an integer $r$ such that the equation $\lfloor P(x)-P(0) \rfloor \equiv r$ (mod $p^2$) has more than $6s$ solutions in the set $\{1,\ldots, sp^2\}$. Let $S$ be the set of $x\in T$ such that $\lfloor P(x)-P(0) \rfloor \equiv r$ (mod $p^2$). In particular $|S|>6s$. For every $x\in \mathbb{Z}$, we have $\lfloor P(x) \rfloor = \lfloor P(x)-P(0) \rfloor+\lfloor P(0) \rfloor +u$ for some $u \in \{-1,0,1\}$, and so $ S \subseteq S_{t_{-1}} \cup S_{t_0} \cup S_{t_1}$, where $t_u=r+\lfloor P(0) \rfloor +u$ (computed modulo $p^2$). Therefore, $$\dfrac{1}{sp^2}|S_{t_{-1}}|+\dfrac{1}{sp^2}|S_{t_0}|+\dfrac{1}{sp^2}|S_{t_1}| \geq \dfrac{1}{sp^2} \left |S_{t_{-1}} \cup S_{t_0} \cup S_{t_1} \right | \geq \dfrac{1}{sp^2} \left |S \right | >\dfrac{6}{p^2},$$ which contradicts the inequality \eqref{lims2} as $s \rightarrow \infty$. \end{proof} We now prove a statement that is stronger than the statement of Theorem \ref{nonlinear3}. \begin{theorem}\label{nonlinear2} Let $P(x)$ be a nonlinear polynomial with real coefficients. If the sequence $(\lfloor P(k) \rfloor )_{k\geq 1}$ is u.d.\ mod all primes large enough, then $P(x)$ has at least one irrational coefficient other than the constant term. \end{theorem} \begin{proof} Suppose on the contrary that $P(x)=\sum_{i=0}^n a_ix^i$ such that $a_i=r_i/s_i \in \mathbb{Q}$ with $\gcd(r_i,s_i)=1$ for all $1\leq i \leq n$. Let $N$ be the least common multiple of $s_i$, $1\leq i \leq n$. Since the sequence $(\lfloor P(k) \rfloor )_{k\geq 1}$ is assumed to be u.d.\ mod all primes large enough, the sequence $( N \lfloor P(k) \rfloor )_{k\geq 1}$ is u.d.\ mod all primes $p$ large enough. The value $N \lfloor P(k) \rfloor$ is periodic modulo $p$ with period $Np$. Therefore, it follows from the uniform distribution of $( N \lfloor P(k) \rfloor )_{k\geq 1}$ modulo $p$ that, with ${\mathcal U}=\{0,\ldots, p-1\} \times \{0,\ldots, N-1\}$, we have \begin{equation}\label{countN} \#\{(t,j) \in {\mathcal U}: N \lfloor P(Nt+j) \rfloor \equiv \modd{i} {p} \}=N, \end{equation} for every integer $i$. Let $P_j(x)=N \lfloor P(Nx+j) \rfloor \in \mathbb{Z}[x]$ for $0\leq j p_0$, $\Res(f_i, f_j) \not \equiv 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\leq jp_0$ such that $f(x)$ has $nN$ distinct zeros modulo $p$. Therefore, the number of solutions of $N \lfloor P(Nt+j) \rfloor \equiv -M$ (mod $p$) is at least $nN>N$. This is in contradiction with equation \eqref{countN}, and the claim follows. \end{proof} \section{Complete even-degree polynomials}\label{compevendeg} Let $P(x)$ be a polynomial such that $P(x)-P(0) \in \mathbb{Q}[x]$. Since the sequence $(\lfloor P(k) \rfloor)_{k\geq 1}$ modulo any integer $m$ is periodic, it follows from Definition \ref{defcomplete} that the polynomial $P(x)$ is complete modulo $m$ if and only if \begin{equation}\label{defgpp} \lim_{N \rightarrow \infty}\dfrac{1}{N} \# \left \{ k \in \{1,\ldots, N\}: \lfloor P(k) \rfloor \equiv \modd{i} {m} \right \} >0, \end{equation} for every integer $i$. Condition \eqref{defgpp} is weaker than condition \eqref{defud}. Therefore, if $(\lfloor P(k) \rfloor )_{k\geq 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 \ref{linear2}. \begin{theorem}\label{linear3} The linear polynomial $P(x)=\alpha x+ \beta$ is complete in $\mathbb{Z}$ if and only if either $| \alpha | \in (0,1]$ or $\alpha$ is irrational. \end{theorem} \begin{proof} If $\alpha$ is irrational, then the claim follows from Theorem \ref{linear2}. Thus, suppose $\alpha=a/b$ where $a,b$ are coprime integers, $a\neq 0$, and $b>0$. Suppose that $P(x)$ is complete in $\mathbb{Z}$, and so the set $\{\lfloor \alpha k + \beta \rfloor: k\geq 1\}$ contains the numbers $0,\ldots, |a|-1$ modulo $|a|$. Let $k=bq+l$ where $0\leq l |a|$ and $tj+i-s$ has the same sign as $a$. Then, write $tj+i-s=aq+u$, where $q\geq 1$ and $u \in \{0,\ldots, |a|-1\}$. Since there exists an integer $0 \leq l N$ and an integer $m$ such that $Q(x)+A_j \not \equiv m$ (mod $p$) for all $x\in \mathbb{Z}$ and $j \in \{0,\ldots, N-1\}$. We claim that $P(x)$ is not complete modulo $p$. On the contrary, suppose there exists an integer $x$ such that $\lfloor P(x)\rfloor \equiv K$ (mod $p$), where $K$ is such that $NK \equiv m$ (mod $p$). But then, writing $x=Nk+j$ with $0\leq j z(n,l)$ and any $n$th power character $\chi$ modulo $p$, there exists an integer $t$ such that \begin{equation}\label{xi} \chi(t)=\chi(t+1)=\cdots =\chi(t+l-1). \end{equation} A number $x$ is an $n$th power residue modulo $p$, if there exists $y$ such that $x \equiv y^n$ (mod $p$). If $\chi$ is an $n$th power character modulo $p$ and $x$ is an $n$th power residue modulo $p$, then $\chi(x)=\chi(y^n)=(\chi(y))^n=1$. Therefore, to show that a number $z$ is not an $n$th power residue modulo $p$, it is sufficient to find an $n$th power character modulo $p$ such that $\chi(z) \neq 1$. We use this fact in the proof of the following lemma. \begin{lemma}\label{last} For any positive integer $l$, there exist infinitely many primes $p$ such that all of the numbers $t,t+1,\ldots, t+l-1$ are $n$th power non-residues modulo $p$ for some positive integer $t$. \end{lemma} \begin{proof} We can assume, without loss of generality, that $n$ is prime and $l\geq 4$. By a result of Mills \cite[Thm.\ 3]{Mills}, for every $m\geq 1$, there exist infinitely many primes $p$ with an $n$th power character $\chi$ modulo $p$ such that $$\chi(2)\neq 1, ~\forall 2 \leq i\leq m:~\chi(p_i)=1,$$ where $p_i$ is the $i$th prime. Let $t$ be defined by \eqref{xi}. 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 \in \{0,\ldots, l-1\}$ such that $t+i-1=2(2d+1)$ for some integer $d$. Then $$\chi(2(2d+1))=\chi(2)\chi(2d+1) \neq 1.$$ It then follows from equation \eqref{xi} that $\chi(t)=\chi(t+1)=\cdots=\chi(t+l-1) \neq 1$ i.e., none of the values $t,t+1,\ldots, t+l-1$, are $n$th power residues modulo $p$. \end{proof} \begin{theorem}\label{mon} Let $P(x)=ax^n+c$, where $a\in \mathbb{Q}$ and $c\in \mathbb{R}$. If $n>1$, then $P(x)$ is not complete modulo all primes large enough, hence $(\lfloor P(k) \rfloor )_{k\geq 1}$ is not u.d.\ in $\mathbb{Z}$. \end{theorem} \begin{proof} Let $a=M/N$, where $M$ and $N$ are integers and $M>0$. Let $Q(x)=Mx^n$ and $A_0,\ldots, A_{N-1}$ be given by equation \eqref{np}. On the contrary, suppose $P(x)$ is complete modulo all primes $p$ large enough. By Lemma \ref{last}, 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 $n$th power residue modulo $p$ for any $0\leq j