\documentclass[11pt]{amsart} \usepackage{amsmath,amssymb,amsthm} \usepackage{booktabs} \usepackage[hidelinks]{hyperref} \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \makeatletter \def\@settitle{\begin{center}% \baselineskip14\p@\relax \bfseries\Large \@title \end{center}% } \def\@setauthors{% \begingroup \def\thanks{\protect\thanks@warning}% \trivlist \centering \normalsize \@topsep30\p@\relax \advance\@topsep by -\baselineskip \item\relax \andify\authors \authors \endtrivlist \endgroup } \makeatother % Notation of [DN05]: [z] integer part, {z} fractional part, % x_n, y_n integer and fractional parts, s_n the integers linking them, % A, B the operations ("type A", "type B"). \newcommand{\ip}[1]{[#1]} \newcommand{\fp}[1]{\{#1\}} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\RR}{\mathbb{R}} \newcommand{\cP}{\mathcal{P}} % --------------------------------------------------------------------------- % Terminology table (generated by lean-to-paper; keep stable on re-runs) % % Lean identifier / concept | literature term | source | notation % round (ξ(3/2)^n) = DubC2.xN | nearest integer to z, defined as [z+1/2] | [DN05, §1 Thm 4] | x_n = [ξ(3/2)^n + 1/2] % DubC2.yN (Z32.yFract) | fractional part of ξa^n + ν | [DN05, §2] | y_n = {ξ(3/2)^n + 1/2} % DubC2.sN (Z32.carry) | the integers s_n (c x_{n+1} = b x_n+s_n) | [DN05, §2] | s_n % S(a,ν) | set of possible values of s_n | [DN05, §2] | S(3/2,1/2) % stepA / stepB | operation of type A / type B | [DN05, §2, §3] | A, B % residue maps mod 5 | operation as permutation of residues; | [DN05, §2] | A=(1)(34)(2| % | "(2|" = residue 2 is sent to 0 | | % carry word (AABB)^∞ | periodic sequence of operations | [DN05, §2] | (A^2B^2)^∞ % Avoids ξ n | x_n divisible by no prime of P | [DN05, §2] | -- % {2,5} unavoidable | "unavoidable set" of divisors | [DN05, §1] | P % Z32.not_isEventuallyPeriodic_... | Lemma 2: s_1,s_2,... is not periodic | [DN05, Lemma 2] | -- % Base ξ n / Good ξ n | (no name) y_n in [0,3/8) / [5/54,1/6), | descriptive | -- % | x_n ≡ 1 or 4 (mod 5) | | % IsEventuallyPeriodic | (eventually) periodic | [DN05, Lemma 2] | -- % --------------------------------------------------------------------------- \title[{Unavoidable divisors of $[\xi(3/2)^{n}+1/2]$}]{An unavoidable set of divisors for the nearest integers to $\xi(3/2)^n$} \author{Ralf Stephan} \thanks{Institute for Globally Distributed Open Research and Education (IGDORE) \\ MSC 11B83, 11J71, 11A41 } \hypersetup{ pdftitle={An unavoidable set of divisors for the nearest integers to xi(3/2)\textasciicircum n}, pdfauthor={Ralf Stephan} } \date{\today} \begin{document} \begin{abstract} We prove that for every real $\xi\ne0$ the sequence of nearest integers $[\xi(3/2)^n+1/2]$, $n\in\NN$, contains infinitely many elements divisible by $2$ or by $5$. In particular, for $\xi>0$ infinitely many of these nearest integers are composite. This is the nearest-integer counterpart of the theorem of Forman and Shapiro on $[\xi(3/2)^n]$, for which Dubickas and Novikas give the unavoidable set $\{2,5,7,11\}$; for nearest integers two primes suffice. The proof follows the method of Dubickas and Novikas: if $2$ and $5$ divide only finitely many terms, the sequence of operations is forced to become $(A^2B^2)^\infty$, which is impossible by their Lemma~2. All results are machine-verified in Lean~4. \end{abstract} \maketitle \section{Introduction} Let $\xi$ be a real number and $a>1$ a rational noninteger number. Forman and Shapiro \cite{FS67} proved that $[(3/2)^n]$ and $[(4/3)^n]$ are composite for infinitely many $n$, and Dubickas and Novikas \cite{DN05} sharpened this by exhibiting explicit finite \emph{unavoidable} sets of divisors: by \cite[Thm.~1]{DN05}, for every $\xi>0$ the set $[\xi(3/2)^n]$, $n\in\NN$, contains infinitely many elements divisible by at least one of $2,5,7,11$. Following \cite{DN05} we write $[z+1/2]$ for the nearest integer to $z$. For nearest integers, \cite[Thm.~4]{DN05} treats the cases $a=7$, $5/3$ and $7/5$; the case $a=3/2$ does not appear there, nor in the account of shifted integer parts in \cite[\S1.6]{Nov12}. We settle it. \begin{theorem}\label{thm:main} Let $\xi\ne0$ be a real number. Then the set $[\xi(3/2)^n+1/2]$, $n\in\NN$, contains infinitely many elements divisible by $2$ or $5$. \end{theorem} \begin{corollary}\label{cor:composite} Let $\xi>0$ be a real number. Then the set $[\xi(3/2)^n+1/2]$, $n\in\NN$, contains infinitely many composite numbers. \end{corollary} \begin{proof} Since $\xi(3/2)^n\to\infty$ and $|[z+1/2]-z|\le1/2$, we have $[\xi(3/2)^n+1/2]>5$ for all sufficiently large $n$. Such an element that is divisible by $2$ or $5$ is composite, so the claim follows from Theorem~\ref{thm:main}. \end{proof} Thus $\{2,5\}$ is an unavoidable set for nearest integers at $a=3/2$. It is a proper subset of the set $\{2,5,7,11\}$ of \cite[Thm.~1]{DN05} for integer parts. The reason is visible in Lemma~\ref{lem:ops} below: for the shift $1/2$ the two operations divide $[0,1)$ into two halves, and the intervals in Lemma~\ref{lem:ops} show at once that neither $A^3$ nor $B^3$ can occur. For integer parts ($\nu=0$), by contrast, $B$ can be repeated arbitrarily often. \begin{remark}\label{rem:scope} (i) Theorem~\ref{thm:main} asserts nothing about the gaps between consecutive $n$ with $\gcd([\xi(3/2)^n+1/2],10)>1$. The argument below leaves the periodic pattern $(A^2B^2)^\infty$ to be excluded by Lemma~\ref{lem:dn}. Lemma~\ref{lem:dn} is a statement about the whole tail of the sequence, not about a window of bounded length.\footnote{Computations, which are not part of the formal verification, exhibit values of $\xi$ for which the first $9$, $33$, $129$ and $513$ nearest integers are all prime to $10$.} (ii) Computations, which are not part of the formal verification, suggest that the method cannot be run with fewer primes. With a single prime it fails, and among the pairs $\{2,\ell\}$ with $\ell\le19$ only $\ell=5$ gives a contradiction. \end{remark} \section{Preliminaries} Following \cite[\S2]{DN05} with $a=3/2$ and shift $\nu=1/2$, put, for $n\in\NN$, \[ x_n=[\xi(3/2)^n+1/2],\quad y_n=\{\xi(3/2)^n+1/2\}\in[0,1),\quad s_n=2x_{n+1}-3x_n \] From $\tfrac32(x_n+y_n-\tfrac12)=x_{n+1}+y_{n+1}-\tfrac12$ we obtain \begin{equation}\label{eq:s} s_n=3y_n-2y_{n+1}-\tfrac12 , \end{equation} so $s_n\in S(3/2,1/2)=\{-2,-1,0,1,2\}$. The only external input is Lemma~2 of \cite{DN05}. \begin{lemma}[{Dubickas--Novikas \cite[Lemma~2]{DN05}}]\label{lem:dn} Let $a=b/c>1$ with $b>c>1$ coprime integers, let $\xi\ne0$ and $\nu$ be real, and let $s_n=cx_{n+1}-bx_n$ with $x_n=[\xi a^n+\nu]$. Then the sequence $s_0,s_1,s_2,\dots$ is not eventually periodic. \end{lemma} \begin{remark} In \cite{DN05} the lemma is stated for $\xi>0$. The proof given there uses only $\xi\ne0$, and so does ours. Write $e_n=x_n-\xi a^n=\nu-y_n$. If $s$ has period $\ell$ from some point on, then along each residue class modulo $\ell$ the bounded sequence $e_n$ satisfies an affine recursion with multiplier $a^\ell>1$, so it is constant. Hence $y_n$ is eventually periodic. Then the integers $x_{n+\ell}-x_n=\xi a^n(a^\ell-1)$, for all large $n$, force $\xi=0$ by coprimality of $b$ and $c$, as in \cite[Lemma~1]{DN05}. \end{remark} \begin{lemma}\label{lem:ops} If $x_n$ is odd, then $s_n\in\{-1,1\}$. More precisely, exactly one of the following two operations takes place: \[ \begin{array}{llll} A:\ & x\mapsto (3x-1)/2, & y\mapsto (6y+1)/4, & [0,1/2)\to[1/4,1);\\[2pt] B:\ & x\mapsto (3x+1)/2, & y\mapsto (6y-3)/4, & [1/2,1)\to[0,3/4). \end{array} \] The operation is $A$ (that is, $s_n=-1$) if and only if $y_n<1/2$. \end{lemma} \begin{proof} From $2x_{n+1}=3x_n+s_n$ we get $s_n\equiv x_n\pmod 2$, so $s_n=\pm1$. By \eqref{eq:s}, $s_n=1$ requires $y_n\ge1/2$ (since $y_{n+1}\ge0$) and $s_n=-1$ requires $y_n<1/2$ (since $y_{n+1}<1$). The formulas for $x_{n+1}$ and $y_{n+1}$ follow from the definition of $s_n$ and \eqref{eq:s}. \end{proof} From now on assume, contrary to Theorem~\ref{thm:main}, that there is $N$ such that $x_n$ is divisible neither by $2$ nor by $5$ for every $n\ge N$. Since $2^{-1}\equiv3\pmod5$, the operations act on residues modulo $5$ as $r\mapsto4r+3s$. In the notation of \cite[\S2]{DN05}, where $(k|$ means that residue $k$ is mapped to $0$, \[ A=(1)(34)(2|,\qquad B=(12)(4)(3| \pmod 5. \] Hence the classes $\{1,2\}$ and $\{3,4\}$ are invariant. Since no $x_n$ with $n\ge N$ is divisible by $5$, Lemma~\ref{lem:ops} gives the following window constraints for $n\ge N$: \begin{equation}\label{eq:win} x_n\equiv2\ (\mathrm{mod}\ 5)\ \Longrightarrow\ y_n\ge1/2,\qquad x_n\equiv3\ (\mathrm{mod}\ 5)\ \Longrightarrow\ y_n<1/2 . \end{equation} \section{Proof of Theorem~\ref{thm:main}} The three lemmas below hold under the standing assumption that $x_n$ is prime to $10$ for all $n\ge N$. Each applies to every $n\ge N$. \begin{lemma}\label{lem:funnel} If $y_n<3/8$ and $x_n\equiv1$ or $4\pmod5$, then $5/54\le y_n<1/6$. \end{lemma} \begin{proof} Suppose $1/6\le y_n<3/8$. Then the operation is $A$ and $y_{n+1}\in[1/2,13/16)$, so the next operation is $B$. If $x_n\equiv1$, the residues are $1\to1\to2$ and $y_{n+2}<15/32<1/2$, contradicting \eqref{eq:win}. If $x_n\equiv4$, then $x_{n+1}\equiv3$ while $y_{n+1}\ge1/2$, again contradicting \eqref{eq:win}. Suppose $0\le y_n<5/54$. The operations are forced to be $AAB$, with $y_{n+1}\in[1/4,7/18)$, $y_{n+2}\in[5/8,5/6)$ and $y_{n+3}\in[3/16,1/2)$. If $x_n\equiv1$, the residues are $1\to1\to1\to2$, and $y_{n+3}<1/2$ contradicts \eqref{eq:win}. If $x_n\equiv4$, the residues are $4\to3\to4\to4$. The next operation is then $A$, which gives $x_{n+4}\equiv3$ and $y_{n+4}\ge17/32>1/2$, a contradiction. \end{proof} \begin{lemma}\label{lem:block} If $5/54\le y_n<1/6$ and $x_n\equiv1$ or $4\pmod5$, then the next four operations are $A^2B^2$, that is, $(s_n,s_{n+1},s_{n+2},s_{n+3})=(-1,-1,1,1)$. Moreover $y_{n+4}<3/8$ and $x_{n+4}\equiv x_n\pmod5$. \end{lemma} \begin{proof} By Lemma~\ref{lem:ops} the values $y_{n+1}\in[7/18,1/2)$, $y_{n+2}\in[5/6,1)$, $y_{n+3}\in[1/2,3/4)$ and $y_{n+4}\in[0,3/8)$ are successively forced. The residues run through $1\to1\to1\to2\to1$ or $4\to3\to4\to4\to4$. \end{proof} \begin{lemma}\label{lem:entry} There is $M\ge N$ with $y_M<3/8$ and $x_M\equiv1$ or $4\pmod5$. \end{lemma} \begin{proof} If $x_N\equiv2$ (resp.\ $3$), then \eqref{eq:win} forces the operation $B$ (resp.\ $A$), and $x_{N+1}\equiv1$ (resp.\ $4$). So we may start at a residue $1$ or $4$. From residue $1$ the possible patterns are $B$, $AB$ and $AAB$. Each one reaches residue $2$ with $y<3/4$, and one forced $B$ then lands in $[0,3/8)$ at residue $1$. From residue $4$ the possible patterns are $B$ and $AAB$, the latter because after $A$ the residue $3$ forces another $A$ by \eqref{eq:win}. If this does not already give $y<3/8$, the orbit is at residue $4$ with $y\in[3/8,3/4)$. There $A$ is excluded, since it would lead to residue $3$ with $y\ge13/16$. So one more $B$ lands in $[0,3/8)$ at residue $4$. In every case $M\le N+5$. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] Take $M$ as in Lemma~\ref{lem:entry}. Lemmas~\ref{lem:funnel} and~\ref{lem:block}, applied alternately at $M,M+4,M+8,\dots$, show by induction that the sequence of operations from $M$ on is $(A^2B^2)^\infty$. So $s_n$ is periodic with period $4$ for $n\ge M$, which contradicts Lemma~\ref{lem:dn}. Hence for every $N$ there is $n\ge N$ with $2\mid x_n$ or $5\mid x_n$. \end{proof} \begin{remark} As in \cite[\S\S3--6]{DN05}, the proof combines arithmetic modulo the primes of $\cP$ with interval arithmetic on the fractional parts $y_n$. Here the interaction is unusually tight. Modulo $5$, each operation is forbidden at exactly one residue ($A$ at $2$, $B$ at $3$). Since the operation is a function of $y_n$, each forbidden residue becomes a window constraint \eqref{eq:win} on $y_n$. \end{remark} \appendix \section{Formal verification} \sloppy All statements of this note are proved in Lean~4 with Mathlib in the files \texttt{DubC2/NearestStep.lean}, \texttt{DubC2/ProductState.lean}, \texttt{DubC2/NearestCert.lean} and \texttt{DubC2/Nearest.lean}, with Lemma~\ref{lem:dn} in \texttt{Z32/DubickasWord.lean}, available in the Github repository \texttt{https://github.com/rwst/lean-code}. \begin{thebibliography}{DN05} \bibitem[DN05]{DN05} A.~Dubickas and A.~Novikas, \emph{Integer parts of powers of rational numbers}, Math.\ Z.\ \textbf{251} (2005), 635--648. \bibitem[FS67]{FS67} W.~Forman and H.~N.~Shapiro, \emph{An arithmetic property of certain rational powers}, Comm.\ Pure Appl.\ Math.\ \textbf{20} (1967), 561--573. \bibitem[Nov12]{Nov12} A.~Novikas, \emph{Composite numbers in the sequences of integers}, doctoral dissertation, Vilnius University, 2012. \end{thebibliography} \end{document}