\documentclass[11pt]{article} \usepackage{amssymb,amsmath,amsthm,graphicx,color} \usepackage{tikz} \usepackage{longtable,array} \usepackage[a4paper,margin=1in]{geometry} \usepackage[sort]{natbib} \definecolor{webblue}{rgb}{0, 0, 0.5} \usepackage[colorlinks=true,linkcolor=webblue,urlcolor=webblue, citecolor=webblue,pdfauthor={John F. Rudge}]{hyperref} % Make the DOIs printed by plainnat link to https://doi.org/. \makeatletter \newcommand*{\doi}{\begingroup\catcode`\_=12 \catcode`\%=12 \catcode`\&=12 \doi@link} \newcommand*{\doi@link}[1]{\href{https://doi.org/#1}{doi:~\nolinkurl{#1}}\endgroup} \makeatother \usepackage{aliascnt} \newtheorem{theorem}{Theorem}[section] \newcommand{\sharedthm}[2]{% \newaliascnt{#1}{theorem}% \newtheorem{#1}[#1]{#2}% \aliascntresetthe{#1}% \expandafter\def\csname #1autorefname\endcsname{#2}} \sharedthm{lemma}{Lemma} \sharedthm{proposition}{Proposition} \sharedthm{corollary}{Corollary} \theoremstyle{definition} \sharedthm{definition}{Definition} \theoremstyle{remark} \sharedthm{remark}{Remark} \renewcommand{\sectionautorefname}{Section} \renewcommand{\subsectionautorefname}{Section} \renewcommand{\appendixautorefname}{Appendix} \newcommand{\e}{\mathrm{e}} \newcommand{\id}{\mathrm{id}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\eps}{\epsilon} \title{Globally periodic rational difference equations of arbitrary order} \author{John F. Rudge\thanks{Bullard Laboratories, Department of Earth Sciences, University of Cambridge, UK.\\e-mail: jfr23@cam.ac.uk}} \date{November 4, 2026} \begin{document} \maketitle \begin{abstract} A rational difference equation of order $k$ with nonnegative coefficients is globally periodic if every solution with positive initial data repeats with a common period. Five such equations have long been known, among them the Lyness equation $x_{n+2}=(1+x_{n+1})/x_n$, and a problem of Gasull asks whether every globally periodic equation of this kind is obtained from one of the five by rescaling and unfolding. The answer was known to be yes for $k\in\{1,2,3,4,5,7,9,11\}$. Here I show that it is yes at every order. The proof rests on two ideas. The first is a tropical degeneration: global periodicity forces an associated min-plus recursion to be periodic, and this is refuted, for every choice of coefficients at once, by an unbounded solution of the min-plus recursion linearised along a periodic orbit. The second is the $\sigma$-bump, a linearised solution whose existence reduces to a combinatorial condition on residues modulo $2k$; in the hardest case that condition comes down to a lemma on three-term progressions under unit multipliers modulo $2k$. The proof, including its finite computations, has been formalised in the \textsc{Lean} proof assistant. \end{abstract} \noindent\textbf{Disclaimer:} This manuscript, and the accompanying \textsc{Lean} formalisation of the proof, have been generated by AI. The validity of the proof has been extensively machine-checked, but the proof is not fully understood by the human author. \section{Introduction} \label{sec:intro} A difference equation is \emph{globally periodic} if all of its orbits are periodic with a common period. The celebrated example is the Lyness equation \begin{equation} x_{n+2} = \frac{1+x_{n+1}}{x_n}, \end{equation} every positive solution of which repeats with period $5$ \citep{Lyness1942}. Global periodicity is a fragile property, and equations that have it are rare. In a survey of open problems in low-dimensional dynamics, \citet{Gasull2021} records five globally periodic rational difference equations with nonnegative coefficients, \begin{equation} x_{n+1}=x_n,\quad x_{n+1}=\frac{1}{x_n},\quad x_{n+2}=\frac{x_{n+1}}{x_n},\quad x_{n+2}=\frac{1+x_{n+1}}{x_n},\quad x_{n+3}=\frac{1+x_{n+1}+x_{n+2}}{x_n}, \label{eq:fivefamilies} \end{equation} of periods $1$, $2$, $6$, $5$ and $8$ respectively. The $8$-cycle of the last was found by H.~Todd \citep{Lyness1945,KocicLadasRodrigues1993}. New examples can be made from these in two trivial ways: by \emph{rescaling}, $y_n=\alpha x_n$ with $\alpha>0$, and by \emph{unfolding}: multiplying every index in an equation of order $k$ by an integer $\ell\ge1$ gives an equation of order $\ell k$ whose solutions are the interleavings of $\ell$ solutions of the original one, and which is therefore again globally periodic. Gasull's Problem~11 asks whether there are any others. More precisely, consider the equations of order $k\ge1$, \begin{equation} x_{n+k}=\frac{A_0+A_1x_n+A_2x_{n+1}+\cdots+A_kx_{n+k-1}} {B_0+B_1x_n+B_2x_{n+1}+\cdots+B_kx_{n+k-1}}, \label{eq:family} \end{equation} with $A_i,B_i\ge 0$, $\sum_i A_i>0$ and $\sum_i B_i>0$, acting on positive initial data. (Gasull also assumes $A_1^2+B_1^2\ne0$, so that the equation genuinely involves $x_n$; I do not need this, because global periodicity forces it, as the first step of the proof shows.) Is every globally periodic equation of the form \eqref{eq:family} obtained from one of \eqref{eq:fivefamilies} by rescaling and unfolding? Here I show that the answer is yes at every order. \begin{theorem} \label{thm:main} Let \eqref{eq:family} be globally periodic, that is, suppose there is a $p\ge1$ such that every positive solution satisfies $x_{n+p}=x_n$. Then, up to multiplying the numerator and denominator by a common positive constant, \eqref{eq:family} is one of the following equations, written from the second on with the denominator cleared: \begin{enumerate} \item the shift $x_{n+k}=x_n$; \item $x_{n+k}\,x_n=a$, with $a>0$; \item $k=2m$ and $x_{n+2m}\,x_n=b\,x_{n+m}$, with $b>0$; \item $k=2m$ and $x_{n+2m}\,x_n=b^2+b\,x_{n+m}$, with $b>0$; \item $k=3m$ and $x_{n+3m}\,x_n=b^2+b\,(x_{n+m}+x_{n+2m})$, with $b>0$. \end{enumerate} These are, respectively, the $k$-fold unfoldings of the first two equations of \eqref{eq:fivefamilies} and the $m$-fold unfoldings of the last three, after rescaling; so every globally periodic equation of the form \eqref{eq:family} is equivalent to one of the five equations of \eqref{eq:fivefamilies}. \end{theorem} Conversely, each equation in the list is globally periodic, with periods $k$, $2k$, $6m$, $5m$ and $8m$ respectively, since it is an unfolding of a rescaling of one of \eqref{eq:fivefamilies}; so \autoref{thm:main} is a complete classification. The requirement of a \emph{common} period loses nothing: if every orbit in $(0,\infty)^k$ is periodic, the state map is a continuous bijection, hence a homeomorphism by invariance of domain, and a pointwise periodic homeomorphism of a connected manifold is periodic \citep{Montgomery1937}; often it can even be linearised globally \citep{CimaGasullManosas2012}. (Discontinuous maps can be pointwise periodic without being periodic \citep{CimaGasullManosaManosas2022}.) This remark is not used in the proof. The question has a long history. Essentially the same question was asked by \citet[Research problem~1.24]{GrahamKnuthPatashnik1989}; the generalisation that Graham had in mind for his Problem~1343 in \emph{Mathematics Magazine} asks for equations of much the same form \citep[Remark~1]{KocicLadasRodrigues1993}. A version of the question is posed by \citet[p.~161]{GroveLadas2005}; at order two it is Conjecture~6.5.6 of \citet{KulenovicLadas2000}. After partial results of \citet{KocicLadasRodrigues1993}, order two was settled by \citet{BarbeauGelbordTanny1995}, and \citet{CsornyeiLaczkovich2001} settled, even for complex coefficients, orders two and three and the reciprocal equations $x_{n+k}x_n=c_0+\sum_{j=1}^{k-1}c_jx_{n+j}$ in which every $c_j$ is nonzero (the full support). \citet{CimaGasullManosas2004} reduced the problem to a reciprocal family with palindromic coefficients, and showed, using a continuum of $2$-periodic points at odd order (\autoref{sec:oddk}), that the answer is yes for $k\in\{1,2,3,4,5,7,9,11\}$. The general case has remained open. Different approaches to the global periodicity problem are surveyed by \citet{CimaGasullManosaManosas2016}. Over the complex numbers and with arbitrary coefficients, periodic linear fractional recurrences have been studied from the point of view of birational geometry by \citet{BedfordKim2006,BedfordKim2014} at orders $2$ and $3$, and \citet{BedfordKim2011} show that for every $k$ there are such recurrences of order $k$ and period $4k$; positivity of the coefficients, which is essential here, plays no role there. The proof has two quite different halves. The first is analytic and short. A surjectivity argument, followed by a Lyapunov function and the derivative at a fixed point, shows that a globally periodic equation is either the shift or of the \emph{reciprocal} form \begin{equation} x_{n+k}\,x_n = c_0 + \sum_{j\in S} c_j\,x_{n+j}, \qquad c_0\ge0,\quad c_j > 0 \text{ for } j \in S \subseteq \{1,\dots,k-1\}, \end{equation} and linearising at the interior equilibrium shows that the coefficients are palindromic, $c_j=c_{k-j}$. Throughout, $\theta=1$ if $c_0>0$ and $\theta=0$ if $c_0=0$; most of the arguments treat both values at once. Unfolding then lets me assume that the \emph{support} $S$ is primitive, $\gcd(S\cup\{k\})=1$. When $S$ has at most two elements, the problem reduces to equations of order at most three, which are settled with the min-plus recursion described below (and, at order three with $c_0=0$, with the linearisation), and to a spectral statement about the polynomial $\lambda^k+1-\eps(\lambda^j+\lambda^{k-j})$, which is settled with Kronecker's theorem on algebraic integers whose conjugates all lie on the unit circle. The second half, which is most of the paper, deals with supports of three or more elements, and it is combinatorial. The key observation is that global periodicity survives degeneration. If the initial data are taken to be powers $\delta^{e_i}$ of a small parameter $\delta$, the exponents of the solution follow a piecewise-linear (min-plus) recursion that depends only on the support and on $\theta$. For the Lyness equation, for example, $x_n\approx\delta^{e_n}$ turns $x_{n+2}x_n=1+x_{n+1}$ into $e_{n+2}+e_n=\min(0,e_{n+1})$, and every integer solution of this recursion has period $5$, just as the solutions of the equation do. In general a globally periodic equation forces its min-plus recursion to be periodic. Because all the coefficients are positive, there is no cancellation: each term of the solution behaves like a positive multiple of a power of $\delta$, and these leading coefficients follow a recursion of their own, which must also be periodic; this is what settles orders two and three when $c_0>0$. The passage to a piecewise-linear recursion is the limiting procedure of \citet{TokihiroTTMS1996}, now called ultradiscretisation and familiar from integrable systems \citep{Nobe2008,InoueTakenawa2008,InoueKunibaTakagi2012}; for the full support it was already used by \citet{CsornyeiLaczkovich2001}. Tropical versions also appear in the theory of cluster algebras, where \citet{FominZelevinsky2003} use them to prove the periodicity of Zamolodchikov's $Y$-systems, of which the Lyness equation is the case of type $A_2$; here the information flows the other way, from the equation to its tropical version. For larger supports, global periodicity of an equation is refuted, for \emph{every} choice of positive coefficients at once, by exhibiting an unbounded solution of the \emph{tangent recursion}, the linearisation of the min-plus recursion along a periodic solution. The idea is to perturb a periodic orbit of the min-plus recursion slightly. Only the terms that attain the minimum see the perturbation, so it follows a recursion of the same kind, and if the perturbation can grow without bound, the min-plus recursion, and with it the equation, cannot be periodic. For the supports with at least three elements, the periodic orbits used have, except at order $6$, a minimum that is always negative, so that the constant term never attains it, and both values of $\theta$ are refuted at once. I construct the unbounded tangent solutions explicitly, case by case (\autoref{tab:intro-cases}). Apart from the full support and most supports at odd order, which have tangent solutions of their own, the workhorse is the \emph{$\sigma$-bump}: a linearly growing tangent solution supported on two positions in every block of $k$, whose existence reduces to a purely combinatorial condition on a set of residues modulo $2k$ (\autoref{def:bump}). The hardest case is even order with every element of $S$ odd, where the residues are chosen as a half-arc $\{y: \nu y \bmod 2k \in [0,k)\}$ for a suitable odd multiplier $\nu$, and what is needed is a lemma about three-term arithmetic progressions under unit multipliers modulo $2k$, proved with the geometry of numbers in a plane lattice of determinant $2k$ and Jacobsthal's function. Several steps finish with a finite computation, for instance at small orders where the general arguments do not yet apply; each is stated precisely in the text and listed in \autoref{tab:intro-cases}. Every finite computation is carried out in exact integer arithmetic, and the whole proof, including these computations, has been formalised and kernel-checked in the \textsc{Lean} proof assistant (\autoref{app:lean}). As far as I know, the following ingredients are new: the tangent recursion and the two-scale pinning lemma (\autoref{lem:trop-pinning}), which turn an unbounded solution of the linearised min-plus recursion into a proof that the equation is not periodic; the use of such tangent solutions to refute global periodicity for every choice of coefficients at once; the $\sigma$-bump and its carriers (the parity, band and half-arc carriers); and the theorem on three-term progressions under unit multipliers (\autoref{thm:lemmaA}). Ultradiscretisation itself is not new, nor is the use of the leading coefficients at orders two and three, which goes back to \citet{CsornyeiLaczkovich2001}. I am not aware of an earlier use of the derivative of a min-plus map along a periodic orbit to show that the map is not periodic (``linearised'' means something different in the ultradiscrete literature, namely straight-line motion on a tropical Jacobian). A by-product is a purely tropical statement: for every palindromic support with at least three elements, and either $\theta$, no power of the min-plus map is the identity (\autoref{cor:trop-nonperiodic}). \autoref{sec:reduction} reduces the problem to primitive palindromic supports of the reciprocal form and \autoref{sec:tropical} develops the min-plus machinery and the $\sigma$-bump; Sections~\ref{sec:small}--\ref{sec:lemmaA} treat the cases of \autoref{tab:intro-cases}, \autoref{sec:assembly} puts them together, and the appendices hold the finite range of \autoref{thm:lemmaA} and the bounds on Jacobsthal's function, the most mechanical case checks, and a description of the formalisation. A reader who wants only the shape of the argument can read Sections~\ref{sec:reduction} and~\ref{sec:tropical}, the statements of the main theorems of the later sections, and \autoref{sec:assembly}. \begin{table} \centering \footnotesize \renewcommand{\arraystretch}{1.15} \begin{tabular}{@{}>{\raggedright\arraybackslash}p{0.15\textwidth}% >{\raggedright\arraybackslash}p{0.19\textwidth}% >{\raggedright\arraybackslash}p{0.27\textwidth}% >{\raggedright\arraybackslash}p{0.23\textwidth}% >{\raggedright\arraybackslash}p{0.05\textwidth}@{}} case & mechanism & results used & finite computations & \S\\\hline every support & reduction to \eqref{eq:familya}, palindromy, folding & Theorems~\ref{thm:red-dichotomy}, \ref{thm:red-shift}, \ref{thm:reduction}, \ref{thm:spectral}, \ref{thm:palindromy}; \autoref{lem:unfold} & none & \ref{sec:reduction}\\ $k=2$, $S=\{1\}$ & leading coefficients & \autoref{thm:order2}, from Theorems~\ref{thm:leading} and \ref{thm:P} & none & \ref{sec:small}\\ $k=3$, $S=\{1,2\}$ & leading coefficients; for $c_0=0$, the linearisation & \autoref{thm:order3}, from Theorems~\ref{thm:leading}, \ref{thm:P} and (for $c_0=0$) \ref{thm:spectral} & none & \ref{sec:small}\\ two-term supports $\{j,k-j\}$ & the linearisation and Kronecker's theorem & \autoref{thm:twoterm}, from \autoref{thm:spectral}, Lemmas~\ref{lem:small-newton} and \ref{lem:small-bound} & none & \ref{sec:small}\\ full support, $k\ge4$ & a closed-form tangent solution on the carrier $Q=\{1\}$ & \autoref{thm:fullsupport}, from Lemmas~\ref{lem:fs-carrier} and \ref{lem:fs-ray} and \autoref{thm:tangent} & none & \ref{sec:fullsupport}\\ odd $k$, $X$ not a dilated interval & rays along the alternating orbit & \autoref{thm:odd-nondil}, from \autoref{prop:odd-second}, \autoref{lem:odd-ray}, the lemmas of \autoref{sec:odd-rigid} and \autoref{thm:tangent} & none & \ref{sec:odd-nondil}\\ odd $k$, $X$ a dilated interval & a $\sigma$-bump & Theorems~\ref{thm:odd-rowcarrier} and \ref{thm:sigmabump}, \autoref{lem:odd-fold} & none & \ref{sec:odd-dil}\\ even $k$, some element of $S$ even & $\sigma$-bumps on parity carriers, or on two explicit carriers & \autoref{thm:notallodd}, from Theorems~\ref{thm:nao-evenmin} and \ref{thm:nao-struct} and \autoref{cor:nao-bothfailing}; \autoref{thm:sigmabump} & none & \ref{sec:notallodd}\\ even $k$, all odd, $1\in S$ & $\sigma$-bumps on small explicit carriers & \autoref{prop:allodd-one}; \autoref{thm:sigmabump} & none & \ref{sec:allodd}\\ even $k$, all odd, $1\notin S$, $|L|=1$ & $\sigma$-bumps on half-arc carriers & \autoref{thm:allodd-threeall} (all but five supports); \autoref{thm:sigmabump} & $k\le22$: five carriers of \autoref{tab:allodd-base} & \ref{sec:allodd}\\ even $k$, all odd, $1\notin S$, $|L|\ge2$ & $\sigma$-bumps on half-arc carriers, with \autoref{thm:lemmaA} & \autoref{prop:allodd-e3bump}, \autoref{thm:allodd-e3all}, \autoref{thm:lemmaA}; \autoref{thm:sigmabump} & \autoref{lem:allodd-pf}; $k\le90$ in \autoref{thm:allodd-e3all}; twelve carriers of \autoref{tab:allodd-base}; for \autoref{thm:lemmaA}, the chord table (C1), the chains of \autoref{tab:lemmaA-chains}, the certificate (C2)--(C3) at the $127$ orders $92\le k\le2730$ with three or more odd prime factors, and the checks in Lemmas~\ref{lem:lemmaA-pattern} and \ref{lem:lemmaA-crude} & \ref{sec:allodd}, \ref{sec:lemmaA}\\ $k=6$, $S=\{1,3,5\}$ & a tangent certificate & Propositions~\ref{prop:order6cert} and \ref{prop:trop-cert}; \autoref{thm:tangent} & the certificate of \autoref{prop:order6cert} & \ref{sec:tropical} \end{tabular} \caption{The cases of the proof, the mechanism and results each uses, and the steps that rest on a finite computation (``none'' means that the case is proved by hand for all parameters). Every case uses the reduction of the first row. Except in the rows for $|S|\le2$, $|S|\ge3$, and $S$ is not the full support unless stated; $\theta$ is arbitrary throughout. At odd order $k$, $X$ is the set of halved even elements of $S$ (\autoref{lem:odd-coords}); $L=\{s\in S:2s0$ and $B_0+\sum_{i\ge1}B_i>0$. Note that $A_{i+1}$ and $B_{i+1}$ are the coefficients of $x_{n+i}$, for $0\le i\le k-1$; in particular $A_1$ and $B_1$ multiply the oldest term $x_n$. Write $\Omega=(0,\infty)^k$, and for $u=(u_1,\dots,u_k)\in\Omega$ put \begin{equation} g(u)=\frac{A_0+\sum_{i=1}^kA_iu_i}{B_0+\sum_{i=1}^kB_iu_i}, \qquad F(u)=\bigl(u_2,\dots,u_k,\,g(u)\bigr). \end{equation} For $u\in\Omega$ the numerator and denominator of $g(u)$ are both positive, since each contains a positive coefficient multiplied by a positive number. So $F$ maps $\Omega$ to itself, every positive initial window $(x_0,\dots,x_{k-1})$ extends to a unique positive solution of \eqref{eq:family}, and the window $(x_n,\dots,x_{n+k-1})$ of that solution is $F^{\,n}(x_0,\dots,x_{k-1})$. The equation is \textit{globally $p$-periodic} ($p\ge1$) when every positive solution satisfies $x_{n+p}=x_n$ for all $n$, and this holds precisely when $F^{\,p}=\id$ on $\Omega$. In particular a globally periodic $F$ maps $\Omega$ onto itself. The first step of the reduction, \autoref{thm:red-dichotomy}, uses only this surjectivity; the second, \autoref{thm:red-shift}, uses periodicity itself. \subsection{The dichotomy} The idea is to ask for a preimage of a single one-parameter family of states, $(1,\dots,1,t)$ with $t>0$. That alone forces most of the coefficients to vanish. \begin{theorem}[dichotomy] \label{thm:red-dichotomy} Suppose $F(\Omega)=\Omega$. Then one of the following holds: \begin{enumerate} \item[(a)] $A_1=0$, $B_0=0$ and $B_i=0$ for all $i\ge2$, so that $B_1>0$ and \eqref{eq:family} reads $B_1x_{n+k}x_n=A_0+A_2x_{n+1}+\cdots+A_kx_{n+k-1}$; \item[(b)] $B_1=0$, $A_0=0$ and $A_i=0$ for all $i\ge2$, so that $A_1>0$ and \eqref{eq:family} reads $x_{n+k}=A_1x_n/\bigl(B_0+B_2x_{n+1}+\cdots+B_kx_{n+k-1}\bigr)$. \end{enumerate} \end{theorem} \begin{proof} Fix $t>0$. A preimage of $(1,\dots,1,t)$ under $F$ must have the form $(u,1,\dots,1)$ with $u>0$ and $g(u,1,\dots,1)=t$. Writing $A'=\sum_{i\ge2}A_i$ and $B'=\sum_{i\ge2}B_i$ (both zero when $k=1$), the hypothesis therefore says that for every $t>0$ there is a $u>0$ with \begin{equation} t\,(B_0+B_1u+B')=A_0+A_1u+A'. \label{eq:red-dagger} \end{equation} There are four cases, according to the signs of $A_1$ and $B_1$. If $A_1=B_1=0$, then $u$ drops out of \eqref{eq:red-dagger}, and taking $t=1$ and $t=2$ gives $B_0+B'=A_0+A'=2(B_0+B')$. Hence $B_0+B'=0$, so all the $B_i$ vanish, which is excluded. If $A_1=00$, so $t(B_0+B')0$. Letting $t\to\infty$ gives $B_0+B'\le0$, that is $B_0=0$ and $B_i=0$ for $i\ge2$: this is case (a). If $B_1=00$, so $A_0+A'0$. Letting $t\to0^+$ gives $A_0+A'\le0$, that is $A_0=0$ and $A_i=0$ for $i\ge2$: this is case (b). Finally, suppose $A_1>0$ and $B_1>0$, and put $\lambda=A_1/B_1$. At $t=\lambda$ the terms in $u$ cancel from \eqref{eq:red-dagger}, leaving $\lambda(B_0+B')=A_0+A'$. Subtracting this from \eqref{eq:red-dagger} at $t=\lambda+1$ leaves $(B_0+B')+B_1u=0$ for some $u>0$, which is impossible. In case (a) the denominator is $B_1x_n$, so $B_1>0$; in case (b) the numerator is $A_1x_n$, so $A_1>0$. \end{proof} \subsection{Branch (b) is the shift} Genuine periodicity, rather than surjectivity, now removes the rest of branch (b). Two simple tools are used. The first is a Lyapunov function: the coordinate sum $\Sigma(u)=\sum_iu_i$ changes under one step by \begin{equation} \Sigma(F(u))-\Sigma(u)=g(u)-u_1 , \label{eq:red-lyap} \end{equation} so if $g(u)u_1$ throughout. The second is the derivative at an interior fixed point: if $F^{\,p}=\id$ and $F(u^*)=u^*$, the chain rule gives $DF(u^*)^p=I$. \begin{theorem}[branch (b) is the shift] \label{thm:red-shift} A globally periodic equation of type (b) has $A_1=B_0$ and $B_i=0$ for all $i\ge2$; that is, it is the shift $x_{n+k}=x_n$. \end{theorem} \begin{proof} Let the equation be globally $p$-periodic, so that $F^{\,p}=\id$ on $\Omega$. In type (b), $g(u)=A_1u_1/\bigl(B_0+\sum_{i\ge2}B_iu_i\bigr)$. Write $\beta=\sum_{i\ge2}B_i$. Suppose first that $\beta=0$. Then $B_0>0$ (the denominator is not zero) and $g(u)=(A_1/B_0)u_1$. If $A_1B_0$ then $g(u)>u_1$ throughout; both are excluded by \eqref{eq:red-lyap}. So $A_1=B_0$, which is the conclusion. Suppose next that $\beta>0$ and $A_1\le B_0$. Then for $u\in\Omega$ the denominator exceeds $B_0\ge A_1$, so $g(u)0$, $A_1>B_0$, which must be shown impossible. Here $x^*=(A_1-B_0)/\beta>0$ satisfies $B_0+\beta x^*=A_1$, so the point $u^*=(x^*,\dots,x^*)$ is fixed by $F$. The map $F$ is rational, with a denominator that is positive on the open set $\Omega$, so it is smooth there, and $F^{\,p}=\id$ gives $DF(u^*)^p=D(F^{\,p})(u^*)=I$ by the chain rule. At $u^*$ the denominator of $g$ equals $A_1$, so $\partial g/\partial u_1=1$ and $\partial g/\partial u_i=-x^*B_i/A_1$ for $i\ge2$; thus, with $d_i=B_ix^*/A_1\ge0$, \[ DF(u^*)\,w=\Bigl(w_2,\dots,w_k,\;w_1-\sum_{i\ge2}d_iw_i\Bigr). \] Put $\phi(\lambda)=\lambda^k+\sum_{i\ge2}d_i\lambda^{i-1}$. Then $\phi(0)=0$ and $\phi(1)=1+\beta x^*/A_1>1$, so by the intermediate value theorem there is a $\lambda\in(0,1)$ with $\phi(\lambda)=1$. The vector $v=(1,\lambda,\dots,\lambda^{k-1})$ then satisfies $DF(u^*)\,v=\lambda v$, since the last coordinate of $DF(u^*)\,v$ is $1-\sum_{i\ge2}d_i\lambda^{i-1}=\lambda^k$. Hence $v=DF(u^*)^pv=\lambda^pv$, so $\lambda^p=1$, which is impossible for $0<\lambda<1$. \end{proof} \subsection{The reciprocal form and its normalisation} \begin{theorem}[reduction] \label{thm:reduction} Every globally periodic equation of the form \eqref{eq:family} is either the shift $x_{n+k}=x_n$ (that is, $A_1=B_0>0$ and every other coefficient is zero), or satisfies $A_1=B_0=0$ and $B_i=0$ for $i\ge2$, with $B_1>0$. In the second case, dividing through by $B_1$, its positive solutions are exactly the positive solutions of \begin{equation} x_{n+k}\,x_n=c_0+\sum_{j\in S}c_j\,x_{n+j}, \qquad c_j>0 \text{ for } j\in S\subseteq\{1,\dots,k-1\},\quad c_0\ge0, \label{eq:familya} \end{equation} where \begin{equation} c_0=\frac{A_0}{B_1},\qquad c_j=\frac{A_{j+1}}{B_1}\quad(1\le j\le k-1),\qquad S=\{\,j\in\{1,\dots,k-1\} : A_{j+1}>0\,\}, \label{eq:red-normalise} \end{equation} and $S\ne\emptyset$ or $c_0>0$. \end{theorem} \begin{proof} A globally periodic $F$ maps $\Omega$ onto itself, so \autoref{thm:red-dichotomy} applies. In case (b), \autoref{thm:red-shift} gives the shift. In case (a) the equation is $B_1x_{n+k}x_n=A_0+\sum_{j=1}^{k-1}A_{j+1}x_{n+j}$, and dividing by $B_1>0$ gives \eqref{eq:familya} with the data \eqref{eq:red-normalise}, after dropping the terms with $A_{j+1}=0$. The last condition is the hypothesis that the numerator of \eqref{eq:family} is not identically zero (recall $A_1=0$). \end{proof} From now on an equation of the form \eqref{eq:familya} is described by its \textit{normalised data}: the order $k$, the support $S$ and the coefficients $c_0$ and $c_j$ ($j\in S$); it is convenient to put $c_j=0$ for $j\in\{1,\dots,k-1\}\setminus S$, and $\theta\in\{0,1\}$ records whether $c_0>0$, as in the introduction. The normalisation \eqref{eq:red-normalise} is a division of numerator and denominator by $B_1$, not a change of variable, so the normalised equation has the same solutions as the original one, and global periodicity of the one is global periodicity of the other. When $k=1$ the support is empty and \eqref{eq:familya} is $x_{n+1}x_n=c_0$. \subsection{The linearisation} The reciprocal family always has an interior equilibrium. Write $s=\sum_{j\in S}c_j$. Since $s+c_0>0$, the equation $x^2=c_0+s x$ has exactly one positive root, \begin{equation} x^*=\tfrac12\Bigl(s+\sqrt{s^2+4c_0}\Bigr), \end{equation} and the constant sequence $x_n=x^*$ is a solution of \eqref{eq:familya}. Put \begin{equation} \eps_j=\frac{c_j}{x^*}\quad(1\le j\le k-1), \qquad\text{so that}\qquad \sum_{j=1}^{k-1}\eps_j=\frac{s}{x^*}=1-\frac{c_0}{x^{*2}}\le1, \label{eq:red-ej} \end{equation} with equality exactly when $c_0=0$. The \textit{linearisation} of \eqref{eq:familya} at $x^*$ is the linear recurrence \begin{equation} y_{n+k}+y_n=\sum_{j=1}^{k-1}\eps_j\,y_{n+j}, \label{eq:red-linrec} \end{equation} whose characteristic polynomial is \begin{equation} \chi(\lambda)=\lambda^k+1-\sum_{j=1}^{k-1}\eps_j\,\lambda^j . \label{eq:red-chi} \end{equation} Every initial window $(y_0,\dots,y_{k-1})$ extends to a unique solution of \eqref{eq:red-linrec}, and the window advances by the companion matrix $\Gamma$, \[ \Gamma(w_1,\dots,w_k)=\Bigl(w_2,\dots,w_k,\;-w_1+\sum_{j=1}^{k-1}\eps_jw_{j+1}\Bigr). \] \begin{theorem}[linearisation] \label{thm:spectral} Suppose \eqref{eq:familya} is globally $p$-periodic. Then: \begin{enumerate} \item[(i)] $\Gamma^{\,p}=I$, so every solution of \eqref{eq:red-linrec} is $p$-periodic; \item[(ii)] every complex root $\lambda$ of $\chi$ satisfies $\lambda^p=1$. \end{enumerate} \end{theorem} \begin{proof} (i) By \autoref{thm:reduction} the state map of \eqref{eq:familya} is $F(u)=\bigl(u_2,\dots,u_k,\,g(u)\bigr)$ with $g(u)=\bigl(c_0+\sum_jc_ju_{j+1}\bigr)/u_1$, a rational map whose denominator is positive on $\Omega$, and it fixes $u^*=(x^*,\dots,x^*)$. Using $x^{*2}=c_0+\sum_jc_jx^*$, the partial derivatives of $g$ at $u^*$ are $\partial g/\partial u_1=-x^{*2}/x^{*2}=-1$ and $\partial g/\partial u_{j+1}=c_j/x^*=\eps_j$, so $DF(u^*)=\Gamma$. Since $F^{\,p}=\id$ on the open set $\Omega$, the chain rule gives $\Gamma^{\,p}=D(F^{\,p})(u^*)=I$. (ii) If $\chi(\lambda)=0$, then $v=(1,\lambda,\dots,\lambda^{k-1})$ satisfies $\Gamma v=\lambda v$, since the last coordinate of $\Gamma v$ is $-1+\sum_j\eps_j\lambda^j=\lambda^k$. So $v=\Gamma^{\,p}v=\lambda^pv$, and $\lambda^p=1$. \end{proof} \subsection{Palindromy} The first structural consequence of \autoref{thm:spectral} is that the coefficients are palindromic. The reason is that a linear map of finite order preserves a positive definite quadratic form, so its inverse is its adjoint. Here the form can be written down explicitly: on $p$-periodic sequences the \textit{period sum} \[ \langle u,v\rangle=\sum_{n=0}^{p-1}u_nv_n \] is positive definite, and it is unchanged by shifting both sequences, $\sum_{n0\}$, and the statement about the $A_i$ from \eqref{eq:red-normalise}. \end{proof} \subsection{Known types and primitive supports} The five equations \eqref{eq:fivefamilies} have a simple description in terms of normalised data. Recall that the \textit{$\ell$-fold unfolding} of an equation $x_{n+k'}=f(x_n,x_{n+1},\dots,x_{n+k'-1})$ of order $k'$ is the equation $x_{n+\ell k'}=f(x_n,x_{n+\ell},\dots,x_{n+(k'-1)\ell})$ of order $\ell k'$; its solutions are exactly the sequences whose $\ell$ interleaved subsequences $m\mapsto x_{m\ell+r}$ ($0\le r<\ell$) each solve the original equation. (\citet{Gasull2021} describes this operation without a name, and uses the word \emph{unfold} for the rescaled family $y_n=\alpha x_n$ instead.) \begin{definition} \label{def:red-known} The normalised data $(k,S,c)$ of an equation \eqref{eq:familya} is of \textit{known type} if one of the following holds: \begin{enumerate} \item[(K1)] $S=\emptyset$; \item[(K2)] $k=2m$, $S=\{m\}$, and $c_0=0$ or $c_0=c_m^2$; \item[(K3)] $k=3m$, $S=\{m,2m\}$, $c_m=c_{2m}$ and $c_0=c_m^2$. \end{enumerate} \end{definition} \begin{lemma} \label{lem:red-members} If the normalised data of an equation of type (a) is of known type, then the equation is equivalent, under a rescaling $y_n=x_n/\lambda$ ($\lambda>0$) and an unfolding, to one of the equations \eqref{eq:fivefamilies}. In terms of the coefficients of \eqref{eq:family}, with $m$ as in \autoref{def:red-known}: in case (K1), $A_i=0$ for all $i\ge1$; in case (K2), $A_i=0$ for $i\notin\{0,m+1\}$, and $A_0=0$ or $A_0B_1=A_{m+1}^2$; in case (K3), $A_i=0$ for $i\notin\{0,m+1,2m+1\}$, $A_{m+1}=A_{2m+1}$ and $A_0B_1=A_{m+1}^2$. \end{lemma} \begin{proof} If $x$ solves \eqref{eq:familya}, then $y_n=x_n/\lambda$ solves $y_{n+k}y_n=c_0/\lambda^2+\sum_{j\in S}(c_j/\lambda)\,y_{n+j}$. In case (K1), $c_0>0$ by \autoref{thm:reduction}; with $\lambda=\sqrt{c_0}$ the equation becomes $y_{n+k}=1/y_n$, the $k$-fold unfolding of $y_{n+1}=1/y_n$. In case (K2), $\lambda=c_m$ gives $y_{n+2m}y_n=y_{n+m}$ or $y_{n+2m}y_n=1+y_{n+m}$, the $m$-fold unfoldings of $y_{n+2}=y_{n+1}/y_n$ and of the Lyness equation $y_{n+2}=(1+y_{n+1})/y_n$. In case (K3), $\lambda=c_m$ gives $y_{n+3m}y_n=1+y_{n+m}+y_{n+2m}$, the $m$-fold unfolding of $y_{n+3}=(1+y_{n+1}+y_{n+2})/y_n$. The coefficient conditions follow from \eqref{eq:red-normalise}: $c_0=c_m^2$ reads $A_0/B_1=A_{m+1}^2/B_1^2$. \end{proof} The last step of the reduction removes common factors from the support. If every element of $S$ and $k$ itself are multiples of some $\ell>1$, then the equation only ever couples terms whose indices agree modulo $\ell$, and it splits into $\ell$ independent copies of an equation of order $k/\ell$, as \citet{CimaGasullManosas2004} observe at order four, where they split a solution into its odd and even subsequences. Call $S$ \textit{primitive} (at order $k$) when $\gcd(S\cup\{k\})=1$. \begin{lemma}[folding] \label{lem:unfold} Let \eqref{eq:familya} have normalised data $(k,S,c)$, and let $\ell=\gcd(S\cup\{k\})$ (so $\ell=k$ when $S=\emptyset$). Put $k'=k/\ell$, $S'=\{j/\ell:j\in S\}$, $c'_0=c_0$ and $c'_{j'}=c_{j'\ell}$ for $j'\in S'$. Then: \begin{enumerate} \item[(i)] equation \eqref{eq:familya} is the $\ell$-fold unfolding of the equation \begin{equation} x_{n+k'}\,x_n=c'_0+\sum_{j'\in S'}c'_{j'}\,x_{n+j'} \label{eq:red-folded} \end{equation} of order $k'$, which has the same $\theta$; \item[(ii)] if \eqref{eq:familya} is globally $p$-periodic, then so is \eqref{eq:red-folded}; \item[(iii)] $S'$ is primitive at order $k'$, and if $c_j=c_{k-j}$ for all $j$, then $c'_{j'}=c'_{k'-j'}$ for all $j'$ (in particular $S'$ is palindromic); \item[(iv)] if the data $(k',S',c')$ is of known type, then so is $(k,S,c)$. \end{enumerate} \end{lemma} \begin{proof} (i) Every element of $S$ is a multiple of $\ell$, and so is $k$. Writing $n=m\ell+r$ with $0\le r<\ell$ and $j=j'\ell$, equation \eqref{eq:familya} at $n$ reads \begin{equation*} x_{(m+k')\ell+r}\,x_{m\ell+r}=c'_0+\sum_{j'\in S'}c'_{j'}\,x_{(m+j')\ell+r}, \end{equation*} which is \eqref{eq:red-folded} at $m$ for the subsequence $m\mapsto x_{m\ell+r}$. (ii) Let $z$ be a positive solution of \eqref{eq:red-folded}, and put $x_n=z_{\lfloor n/\ell\rfloor}$. Each subsequence $m\mapsto x_{m\ell+r}$ equals $z$, so by (i) $x$ is a positive solution of \eqref{eq:familya}, and it is therefore $p$-periodic, hence also $p\ell$-periodic. So $z_{m+p}=x_{m\ell+p\ell}=x_{m\ell}=z_m$ for every $m$. (iii) and (iv) are immediate from the definitions: $\gcd(S'\cup\{k'\})=\gcd(S\cup\{k\})/\ell=1$, and for (iv) one replaces $m$ by $m\ell$ in \autoref{def:red-known}. \end{proof} \begin{corollary} \label{cor:red-primitive} Suppose that every globally periodic equation \eqref{eq:familya} whose support $S$ is primitive and whose coefficients satisfy $c_j=c_{k-j}$ for all $j$ has normalised data of known type. Then every globally periodic equation of the form \eqref{eq:family} is either the shift $x_{n+k}=x_n$, or is equivalent, under a rescaling and an unfolding, to one of the equations \eqref{eq:fivefamilies}, with coefficients as in \autoref{lem:red-members}. \end{corollary} \begin{proof} Let \eqref{eq:family} be globally $p$-periodic. By \autoref{thm:reduction} it is either the shift or has the normalised form \eqref{eq:familya}, which is globally $p$-periodic. In the second case, \autoref{thm:palindromy} gives $c_j=c_{k-j}$, and \autoref{lem:unfold} gives a globally $p$-periodic folded equation \eqref{eq:red-folded} with primitive support and palindromic coefficients. By hypothesis its data is of known type, so by \autoref{lem:unfold}(iv) the data of \eqref{eq:familya} is of known type, and \autoref{lem:red-members} finishes the proof. \end{proof} The remaining sections therefore work with a primitive palindromic support $S$, coefficients $c_j=c_{k-j}>0$ on $S$, and either value of $\theta$, and show that global periodicity forces known type. \section{The min-plus map and the \texorpdfstring{$\sigma$}{sigma}-bump} \label{sec:tropical} Throughout this section the equation is \eqref{eq:familya}, with support $S\subseteq\{1,\dots,k-1\}$ and $\theta$ as in the introduction; since the numerator is nonzero, $S\ne\emptyset$ or $\theta=1$. The section sets up the min-plus recursion and its leading coefficients (Theorems~\ref{thm:leading} and~\ref{thm:P}), the tangent solutions that refute periodicity (\autoref{thm:tangent}), and the $\sigma$-bump (\autoref{thm:sigmabump}). It ends with a vocabulary for checking the conditions of a $\sigma$-bump (\autoref{sec:nao-reading}) and the mirror lemma (\autoref{lem:nao-mirror}), both used in the later sections. \subsection{The min-plus recursion and its periodicity} \label{sec:trop-minplus} It is convenient to treat the constant term as a slot. Let \[ S_\theta=S\cup\{0\}\ \text{if}\ \theta=1,\qquad S_\theta=S\ \text{if}\ \theta=0, \] so that $S_\theta\ne\emptyset$. For a sequence $(f_n)_{n\ge0}$ of real numbers, an index $n\ge0$ and a slot $j\in S_\theta$, write \[ v_n(f,j)=\begin{cases}0,&j=0,\\ f_{n+j},&j\in S,\end{cases} \qquad m_n(f)=\min_{j\in S_\theta}v_n(f,j). \] Thus $v_n(f,j)$ is the value read by slot $j$ from the window starting at $n$, and the constant slot always reads $0$. The slots $j\in S$ are called \emph{taps}. \begin{definition} \label{def:trop-minplus} An integer sequence $(e_n)_{n\ge0}$ is a \textit{solution of the min-plus recursion} (for $k$, $S$, $\theta$) if \begin{equation} e_{n+k}+e_n=m_n(e)=\min\Bigl(\{0\ \text{if}\ \theta=1\}\cup\{e_{n+j}:j\in S\}\Bigr) \qquad\text{for all}\ n\ge0. \label{eq:trop-rec} \end{equation} Every integer window $(e_0,\dots,e_{k-1})$ extends uniquely to a solution. The \textit{min-plus map} $T:\Z^k\to\Z^k$ is the corresponding window map, $T(e_0,\dots,e_{k-1})=(e_1,\dots,e_{k-1},\,m_0(e)-e_0)$. The \textit{attaining sets} of a solution $e$ are \[ A_n=A_n(e)=\{\,j\in S_\theta:\ v_n(e,j)=m_n(e)\,\}\qquad(n\ge0); \] ties are allowed, so $A_n$ may have several elements. \end{definition} Each term of the orbit of \eqref{eq:familya} started from $x_i=\delta^{e_i}$ behaves like $C_n\delta^{e_n}$ as $\delta\to0^+$, where the exponents $e_n$ follow the min-plus recursion and the leading coefficients $C_n$ follow a recursion that keeps, in each step of \eqref{eq:familya}, only the terms whose exponent attains the minimum. \begin{theorem}[leading coefficients] \label{thm:leading} Let $e$ be an integer solution of \eqref{eq:trop-rec}. For $\delta>0$ let $x(\delta)=(x_n(\delta))$ be the solution of \eqref{eq:familya} with initial window $x_i(\delta)=\delta^{e_i}$ ($0\le i0$ and \[ \lim_{\delta\to0^+}x_n(\delta)\,\delta^{-e_n}=C_n\qquad\text{for every}\ n\ge0. \] \end{theorem} \begin{proof} First, $x(\delta)$ is a positive solution: the numerator of \eqref{eq:familya} is a sum of nonnegative terms, at least one of them positive. Likewise $C_n>0$ by induction, since $A_n(e)$ is nonempty and every term on the right of \eqref{eq:trop-lead} is a positive coefficient times a positive number. The limit is proved by induction on $n$; for $n0$ gives $x_{n+k}(\delta)\delta^{-e_{n+k}}\to C_{n+k}$. \end{proof} \begin{theorem}[periodicity of the degeneration] \label{thm:P} Suppose the equation \eqref{eq:familya} is globally $p$-periodic. Then every integer solution $e$ of the min-plus recursion \eqref{eq:trop-rec} satisfies $e_{n+p}=e_n$ for all $n\ge0$; equivalently, $T^{\,p}=\id$ on $\Z^k$. Moreover the leading coefficients of \autoref{thm:leading} satisfy $C_{n+p}=C_n$ for all $n\ge0$. \end{theorem} \begin{proof} Let $x(\delta)$ and $C_n$ be as in \autoref{thm:leading}. By periodicity $x_{n+p}(\delta)=x_n(\delta)$ for every $\delta>0$, so \[ \delta^{\,e_{n+p}-e_n} =\frac{x_n(\delta)\,\delta^{-e_n}}{x_{n+p}(\delta)\,\delta^{-e_{n+p}}} \longrightarrow\frac{C_n}{C_{n+p}}\qquad(\delta\to0^+). \] The limit is positive and finite, whereas $\delta^{a}$ tends to $0$ for an integer $a>0$ and to infinity for $a<0$. Hence $e_{n+p}=e_n$, and then the left-hand side is $1$, so $C_{n+p}=C_n$. \end{proof} The first part of \autoref{thm:P} is a condition on $(S,\theta)$ alone; the leading coefficients retain a little information about the $c_j$, which is what is needed at orders $2$ and $3$. Positivity of the coefficients is essential to both theorems: the terms attaining the minimum cannot cancel. For the full support, \citet[Lemma~8]{CsornyeiLaczkovich2001} pass to the same piecewise-linear recursion (with $\max$ in place of $\min$), taking initial data of the form $x^{c_i}$ with exponents $c_i$ that are linearly independent over $\Q$. At orders $2$ and $3$ the recursion for the leading coefficients is the device of \citet[Lemma~5]{CsornyeiLaczkovich2001}, and \autoref{thm:leading} is its general form. \subsection{Tangent solutions} \label{sec:trop-tangent} To use \autoref{thm:P} one needs an integer solution of \eqref{eq:trop-rec} that is not $p$-periodic. Searching for such orbits directly is awkward, because a non-periodic orbit has to be followed for ever. It is much easier to start from a \textit{periodic} orbit and look at how nearby orbits move. Since $T$ is piecewise linear, nearby orbits are governed by a second recursion of the same kind, read only from the slots that attain the minimum. \begin{definition} \label{def:trop-tangent} Let $e$ be an integer solution of \eqref{eq:trop-rec}, with attaining sets $A_n=A_n(e)$. An integer sequence $(d_n)_{n\ge0}$ is a \textit{tangent solution along $e$} if \begin{equation} d_{n+k}+d_n=\min_{j\in A_n}v_n(d,j)\qquad\text{for all}\ n\ge0. \label{eq:trop-tangent} \end{equation} \end{definition} The right-hand side of \eqref{eq:trop-tangent} is the one-sided derivative of the minimum: for small $\tau>0$, $m_n(e+\tau d)=m_n(e)+\tau\min_{j\in A_n}v_n(d,j)$, because slots outside $A_n$ are beaten by a fixed margin. The following lemma, the heart of the method, is the integer version of this observation. \begin{lemma}[two-scale pinning] \label{lem:trop-pinning} Let $e$ be an integer solution of \eqref{eq:trop-rec} and $d$ a tangent solution along $e$. Let $N\ge0$, let $D\ge0$ be an integer with $|d_n|\le D$ for all $n2D$ be an integer. Let $g$ be the integer solution of \eqref{eq:trop-rec} with initial window $g_i=\kappa e_i+d_i$ ($0\le i\kappa M+D$. Hence the minimum over $S_\theta$ is attained inside $A_m$, and \[ m_m(g)=\kappa M+\min_{j\in A_m}v_m(d,j)=\kappa\,(e_{m+k}+e_m)+(d_{m+k}+d_m), \] by \eqref{eq:trop-rec} for $e$ and \eqref{eq:trop-tangent} for $d$. Since $g_{m+k}=m_m(g)-g_m$ and $g_m=\kappa e_m+d_m$, this gives $g_n=\kappa e_n+d_n$. \end{proof} \begin{theorem}[tangent solutions] \label{thm:tangent} Let $T$ be the min-plus map for $(S,\theta)$. \begin{enumerate} \item[(i)] If $T^{\,p}=\id$ on $\Z^k$, then every integer tangent solution $d$ along every integer solution $e$ of \eqref{eq:trop-rec} satisfies $d_{n+p}=d_n$ for all $n\ge0$; in particular it is bounded. \item[(ii)] Consequently, if some integer solution of \eqref{eq:trop-rec} carries an unbounded integer tangent solution, then no power of $T$ is the identity on $\Z^k$, and no equation \eqref{eq:familya} with support $S$ and this $\theta$ is globally periodic, for any choice of positive coefficients and any period. \end{enumerate} \end{theorem} \begin{proof} (i) Fix $n_0\ge0$. Take $N=n_0+p+1$, an integer $D\ge0$ bounding $|d_n|$ for $nk$, so that $y=p-k$; the tap with $p=k$ is deleted. By \eqref{eq:read-antiper}, a surviving tap reads \begin{equation} \mathbf 1[\,y\in Q\,]\ \text{if it is unwrapped},\qquad \mathbf 1[\,y\notin Q\,]\ \text{if it is wrapped}. \label{eq:read-reads} \end{equation} A position $p$, or a residue $y$ with $00$, which is of known type, so there is nothing to prove. \item $S=\{k/2\}$, which is primitive only at $k=2$: the support $S=\{1\}$ of order two (\autoref{thm:order2}). \item $S=\{j,k-j\}$ with $\gcd(j,k)=1$. The case $k=3j$ forces $j=1$, and is the support $\{1,2\}$ of order three (\autoref{thm:order3}); every other case is settled by \autoref{thm:twoterm}. \end{itemize} At orders two and three with $c_0>0$ neither the linearisation nor the min-plus recursion can decide the question: at order two the characteristic polynomial $\lambda^2-\eps_1\lambda+1$ has roots of unity whenever $\eps_1=2\cos(2\pi q/p)$ for integers $q$ and $p\ge1$, and with $\theta=1$ the min-plus recursion is itself periodic, with period $5$ at order two and $8$ at order three \citep[Theorem~9]{CsornyeiLaczkovich2001}. What decides it is the second half of \autoref{thm:P}: once round a cycle of the min-plus recursion the leading coefficients are multiplied by a fixed factor, which must be $1$. \subsection{Order two} At $k=2$ with $S=\{1\}$ the equation \eqref{eq:familya} reads \begin{equation} x_{n+2}x_n=c_0+c_1x_{n+1},\qquad c_1>0,\quad c_0\ge0. \label{eq:small-order2} \end{equation} The substitution $x_n=c_1y_n$ turns it into \begin{equation} y_{n+2}y_n=\alpha+y_{n+1},\qquad \alpha=\frac{c_0}{c_1^2}\ge0, \label{eq:small-lyness} \end{equation} and it preserves positivity and periodicity of solutions. For $\alpha=1$ this is the Lyness equation \citep{Lyness1942}, of period $5$; for $\alpha=0$ it has period $6$. The following theorem is known: \citet{KocicLadasRodrigues1993} showed that the periods $5$ and $6$ occur only for $\alpha=1$ and $\alpha=0$, and the theorem itself was proved by \citet{BarbeauGelbordTanny1995} on the whole real plane, by \citet{CsornyeiLaczkovich2001} with complex coefficients, and by \citet[Theorem~3.1]{CimaGasullManosas2004}. I sketch the proof, which is essentially that of \citet[Lemma~5]{CsornyeiLaczkovich2001} and of a remark of \citet[Section~3]{BarbeauGelbordTanny1995}, because it is the model for order three, where the details are given. The formalisation (\autoref{app:lean}) contains a complete proof along the lines of the sketch. \begin{theorem}[order two] \label{thm:order2} If \eqref{eq:small-order2} is globally periodic, then $c_0=0$ or $c_0=c_1^2$. \end{theorem} \begin{proof}[Sketch of proof] Let $c_0>0$, so that $\alpha>0$ and $\theta=1$. The min-plus recursion $e_{n+2}+e_n=\min(0,e_{n+1})$ started from $(e_0,e_1)=(1,0)$ runs through the $5$-cycle $1,0,-1,-1,0$. Following the leading coefficients \eqref{eq:trop-lead} of \autoref{thm:leading} once round this cycle, with $c_1=1$ and constant term $\alpha$, multiplies $C_{5s+1}$ by $\alpha$: the first two steps give $C_{5s+4}=1/C_{5s+1}$, and at $n=5s+4$ the constant slot alone attains the minimum, so $C_{5s+6}=\alpha/C_{5s+4}=\alpha\,C_{5s+1}$. Hence $C_{5s+1}=\alpha^s$. By \autoref{thm:P} the period $p$ is a multiple of $5$, and $C_{p+1}=C_1$ gives $\alpha^{p/5}=1$, that is $\alpha=1$. \end{proof} \subsection{Order three} At $k=3$ with $S=\{1,2\}$, \autoref{thm:palindromy} gives $c_1=c_2$ for a globally periodic equation, so the equation is \begin{equation} x_{n+3}x_n=c_0+c_1(x_{n+1}+x_{n+2}),\qquad c_1>0,\quad c_0\ge0. \label{eq:small-order3} \end{equation} The substitution $x_n=c_1y_n$ turns it into \begin{equation} y_{n+3}y_n=\alpha+y_{n+1}+y_{n+2},\qquad\alpha=\frac{c_0}{c_1^2}\ge0. \label{eq:small-todd} \end{equation} For $\alpha=1$ this is the period-$8$ equation of \eqref{eq:fivefamilies}. The following theorem is also known. With complex coefficients it follows from Theorems~1 and~4 of \citet{CsornyeiLaczkovich2001}, and with nonnegative coefficients it is the case $m=1$ of \citet[Theorem~4.1]{CimaGasullManosas2004}; \citet{KocicLadasRodrigues1993} had shown that the period $8$ occurs exactly when $c_0=c_1^2$. For $c_0>0$ the proof below is that of \citet[Lemma~5(ii)]{CsornyeiLaczkovich2001}, written in the language of \autoref{thm:leading}. \begin{theorem}[order three] \label{thm:order3} If $x_{n+3}x_n=c_0+c_1x_{n+1}+c_2x_{n+2}$, with $c_1,c_2>0$ and $c_0\ge0$, is globally periodic, then $c_1=c_2$ and $c_0=c_1^2$. In particular $c_0>0$. \end{theorem} \begin{proof} Suppose the equation is globally $p$-periodic with $p\ge1$. By \autoref{thm:palindromy}, $c_1=c_2$, so it has the form \eqref{eq:small-order3}. The two values of $\theta$ are handled separately. First suppose $c_0>0$, so that \eqref{eq:small-todd} is globally $p$-periodic with $\alpha>0$. The argument follows the sketch for order two. The min-plus recursion is $e_{n+3}+e_n=\min(0,e_{n+1},e_{n+2})$, and the solution with initial window $(e_0,e_1,e_2)=(1,0,-1)$ is $8$-periodic, with \[ \begin{array}{c|cccccccc} n\bmod8 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline e_n & 1 & 0 & -1 & -2 & -2 & -1 & 0 & 1\\ A_n & \{2\} & \{2\} & \{1,2\} & \{1\} & \{1\} & \{0,1\} & \{0\} & \{0,2\} \end{array}. \] The period is exactly $8$, so \autoref{thm:P} gives $p=8r$ with $r\ge1$. If $C_{8s}=\xi$, $C_{8s+1}=\eta$ and $C_{8s+2}=\zeta$, the eight steps $n=8s,\dots,8s+7$ of \eqref{eq:trop-lead} give in turn \begin{gather*} C_{8s+3}=\frac{\zeta}{\xi},\quad C_{8s+4}=\frac{\zeta}{\xi\eta},\quad C_{8s+5}=\frac{\eta+1}{\xi\eta},\quad C_{8s+6}=\frac1\eta,\quad C_{8s+7}=\frac{\eta+1}{\zeta},\\ C_{8s+8}=\frac{\xi(\alpha\eta+1)}{\eta+1},\quad C_{8s+9}=\alpha\eta,\quad C_{8s+10}=\alpha\zeta . \end{gather*} For example, at $n=8s+2$ both taps attain, so $C_{8s+5}C_{8s+2}=C_{8s+3}+C_{8s+4}$. Since $C_1=1$, induction gives $C_{8s+1}=\alpha^s$, and \autoref{thm:P} gives $\alpha^r=C_{p+1}=C_1=1$. Hence $\alpha=1$, that is $c_0=c_1^2$. Now suppose $c_0=0$, so the equation is $x_{n+3}x_n=c_1(x_{n+1}+x_{n+2})$. Its positive equilibrium is $x^*=2c_1$, so $\eps_1=\eps_2=\tfrac12$ in \eqref{eq:red-ej}, and the characteristic polynomial of \autoref{thm:spectral} is \[ \chi(\lambda)=\lambda^3-\tfrac12\lambda^2-\tfrac12\lambda+1 =(\lambda+1)\bigl(\lambda^2-\tfrac32\lambda+1\bigr). \] By \autoref{thm:spectral} every root of $\chi$ is a $p$-th root of unity. Let $\lambda$ be a root of the quadratic factor. Its discriminant is negative, so its two roots are $\lambda$ and $\bar\lambda$, and $\lambda\bar\lambda=1$; hence $\lambda+\lambda^{-1}=\tfrac32$. But $\lambda$ is a root of unity, hence an algebraic integer, and so is $\lambda^{-1}$; so $\tfrac32$ would be a rational algebraic integer, that is, an integer. This contradiction shows that $c_0=0$ is impossible. \end{proof} \subsection{Two-term supports} The remaining small supports are the two-term supports $\{j,k-j\}$ at every order. \begin{theorem}[two-term supports] \label{thm:twoterm} Let $1\le j$, $2j2$ and $k\ne3$, so $k\ge4$, and \autoref{lem:small-newton} gives $s_{k-2}=t^{k-2}$ and $s_{k-1}=(k-1)t+t\,s_{k-2}=(k-1)t+t^{k-1}$. From the first, $|t|^{k-2}\le k\le2^{k-2}$ (as $k\ge4$), so $|t|\le2$. From the second, if $t>1$ then $s_{k-1}>(k-1)+1=k$, which is impossible; so $t\le1\le\sqrt2$. \end{proof} The last ingredient is Kronecker's theorem \citep{Kronecker1857}: if $L$ is a number field and $\zeta\in L$ is a nonzero algebraic integer with $|\varphi(\zeta)|\le1$ for every field embedding $\varphi:L\to\C$, then $\zeta$ is a root of unity; for a modern account see \citet[Theorem~1.5.9]{BombieriGubler2006}. \begin{proof}[Proof of \autoref{thm:twoterm}] Suppose that an equation \eqref{eq:familya} with support $S=\{j,k-j\}$ is globally $p$-periodic. By \autoref{thm:palindromy}, $c_j=c_{k-j}$, so $\eps_j=\eps_{k-j}=:\eps$, and \eqref{eq:red-ej} gives $2\eps=\eps_j+\eps_{k-j}\le1$. Thus \[ 0<\eps\le\tfrac12, \] and by \autoref{thm:spectral} every root $\eta_i$ of $\chi_\eps$ is a $p$-th root of unity. The idea of the proof is that $\eps=\zeta+\zeta^{-1}$ for a root of unity $\zeta$. The bound $0<\eps\le\tfrac12$ forces $\zeta$ to have order at least $9$, and then some conjugate of $\eps$ is larger than $\sqrt2$, which \autoref{lem:small-bound} forbids. \emph{Step 1: $\eps$ is $\zeta+\zeta^{-1}$ for a root of unity $\zeta$.} The coefficient of $\lambda^{k-j}$ in $\chi_\eps=\prod_i(\lambda-\eta_i)$ is $-\eps$, and it is also $(-1)^j$ times the $j$-th elementary symmetric function of $\eta_1,\dots,\eta_k$. Roots of unity are algebraic integers, so $\eps$ is an algebraic integer. Let $\zeta$ be a root of $z^2-\eps z+1$; then $\zeta$ is an algebraic integer (a root of a monic polynomial whose coefficients are algebraic integers), $\zeta\ne0$, and $\eps=\zeta+\zeta^{-1}$. Let $L=\Q(\zeta,\eta_1,\dots,\eta_k)$, a number field containing $\eps$. Let $\varphi:L\to\C$ be an embedding. Applying $\varphi$ to the coefficients of $\chi_\eps=\prod_i(\lambda-\eta_i)$ gives $\chi_{\varphi(\eps)}=\prod_i(\lambda-\varphi(\eta_i))$, and each $\varphi(\eta_i)$ is again a $p$-th root of unity, so of modulus $1$. By \autoref{lem:small-bound}, $r=\varphi(\eps)$ is real with $|r|\le2$. Now $\varphi(\zeta)$ is a root of $z^2-rz+1$, a real quadratic with discriminant $r^2-4\le0$; its two roots are therefore complex conjugates (or equal to $\pm1$) with product $1$, so $|\varphi(\zeta)|=1$. By Kronecker's theorem, $\zeta$ is a root of unity. \emph{Step 2: the order of $\zeta$.} Let $n_0$ be the order of $\zeta$. Since $|\zeta|=1$, $\zeta^{-1}=\bar\zeta$, so $\eps=2\cos(2\pi b/n_0)$ for some integer $b$ coprime to $n_0$, and I may take $0\le b\le n_0/2$. Since $\cos$ is decreasing on $[0,\pi]$, with $\cos(5\pi/12)=(\sqrt6-\sqrt2)/4>\tfrac14$ and $\cos(\pi/2)=0$, the condition $0<\eps\le\tfrac12$ forces \[ \frac5{24}<\frac b{n_0}<\frac14, \] that is, $5n_0<24b<6n_0$. If $n_0\le8$ then $24b<48$, so $b=1$ (as $b=0$ is excluded), and $5n_0<24<6n_0$ has no integer solution. Hence $n_0\ge9$. \emph{Step 3: a large conjugate.} The cyclotomic polynomial $\Phi_{n_0}$ is irreducible over $\Q$, so it is the minimal polynomial of $\zeta$, and $\e^{2\pi i/n_0}$ is another of its roots. There is therefore a field embedding of $\Q(\zeta)$ into $\C$ sending $\zeta$ to $\e^{2\pi i/n_0}$, and since $\zeta\in L$ it extends to an embedding $\varphi:L\to\C$. Then \[ \varphi(\eps)=\varphi(\zeta)+\varphi(\zeta)^{-1} =\e^{2\pi i/n_0}+\e^{-2\pi i/n_0}=2\cos(2\pi/n_0), \] and, as in Step 1, \autoref{lem:small-bound} gives $2\cos(2\pi/n_0)\le\sqrt2$. But $n_0\ge9$ gives $0<2\pi/n_0<\pi/4$, so $2\cos(2\pi/n_0)>2\cos(\pi/4)=\sqrt2$. This contradiction proves the theorem. \end{proof} \section{The full support} \label{sec:fullsupport} The full support $S=\{1,\dots,k-1\}$ never carries a $\sigma$-bump. Indeed, (B1) forces $Q=\{\sigma\}$, and then at $i=k-1$ every position $i+j$ with $j\in S$ lies in $\{k,\dots,2k-2\}$, where the only position that can lie outside $P$ is $k+\sigma$, which (B2) excludes. So the full support has to be treated on its own. It is also the classical case: the full-support recursion, in which every term of the window appears in the numerator, was settled, even for complex coefficients, by \citet{CsornyeiLaczkovich2001}. They also passed to its piecewise-linear shadow and showed, by exhibiting a non-periodic real solution at every order other than these, that it is periodic only at order $2$ and, with $c_0>0$, at order $3$ (their Theorems~9--11). The periods of the shadow at order $4$ with $c_0>0$ are determined by \citet{LineroBasNievesRoldan2021}, and, with $c_0>0$, every solution with monotone initial data has period $3k-1$ \citep{GolombCallan1992}. The carrier $Q=\{1\}$ satisfies (B1) with $\sigma=1$ but fails (B2), so the bump is not a tangent solution along it; but every window of the full support meets this carrier, so \autoref{lem:trop-carrier} applies, and here I give a different unbounded tangent solution along its orbit, written down in closed form and checked by hand. \begin{theorem} \label{thm:fullsupport} Let $k\ge4$. No equation \eqref{eq:familya} with full support $S=\{1,\dots,k-1\}$ is globally periodic, for either value of $\theta$ and for any choice of positive coefficients. \end{theorem} The bound $k\ge4$ is sharp: at $k=2$ and $k=3$ the full supports $\{1\}$ and $\{1,2\}$ carry the period-$6$, Lyness and period-$8$ equations of \eqref{eq:fivefamilies}. \subsection{The carrier} \label{sec:fs-carrier} Throughout this section $k\ge4$ and $S=\{1,\dots,k-1\}$. Let $P\subseteq\Z/2k$ be the anti-periodic set coded by $Q=\{1\}$ (\autoref{def:bump}), that is \[ P=\{1,\,k\}\cup\{k+2,k+3,\dots,2k-1\}, \] and let $E$ be its orbit. Write every $n\ge0$ as $n=\ell k+i$ with $\ell\ge0$ and $0\le is=\sum_{j\in S,\,j\text{ even}}c_j$; along it the eigenvalues of the derivative of the second iterate must be constant roots of unity \citep[Proposition~2.6]{CimaGasullManosas2004}, which gives polynomial conditions on the coefficients that they solve at $k=5,7,9,11$. Taking $t-s$ a fixed multiple of $\delta^3$ and letting $\delta\to0^+$ gives the $2$-periodic min-plus solution equal to $0$ at even and $-3$ at odd positions, and the alternating orbit below changes it at two positions in each period $2k$. The mechanism here is different, however: the tangent recursion along the alternating orbit depends only on $S$, so it disposes of every choice of coefficients at once. Throughout, $k=2h+1$ is odd, and residues modulo $k$ are identified with their representatives in $\{0,\dots,k-1\}$; for a residue $n$ and a set $X$ of residues, $n+X$ and $n-X$ denote the translate and the reflection of $X$ taken modulo $k$. The set $X$ always lies in the lower half $\{1,\dots,h\}$, and two elementary facts about such sets are used repeatedly: for $x,y\in X$, \begin{equation} x+y\not\equiv0\pmod k, \qquad\text{and}\qquad -x\equiv k-x\in\{h+1,\dots,2h\}\ \text{lies outside } X\cup\{0\}, \label{eq:odd-half} \end{equation} because $2\le x+y\le 2h-3$. It remains to see that $A_n$ is nonempty. If $n$ is even, $A_n$ consists of the odd taps $j$ with $n+j\not\equiv1$; there are at least two odd taps and at most one of them has $n+j\equiv1\pmod{2k}$. If $n$ is odd, the same argument applies to the even taps, of which there are as many as odd ones. \end{proof} The tangent recursion along $E$ is \begin{equation} d_{n+k}+d_n=\min_{j\in A_n} d_{n+j}\qquad(n\ge0), \label{eq:odd-tangent} \end{equation} and every tap in $A_n$ reads $d$ at an odd position. So the values of $d$ at odd positions should determine everything, and they do. Write $v_t=d_{2t+1}$, and use the coordinates \eqref{eq:odd-coords}. At the odd time $n=2t+1$ the attaining taps are the even ones, $j=2x$, which read $d_{2(t+x)+1}=v_{t+x}$ and are absent when $2(t+x)+1\equiv1\pmod{2k}$, that is when $t+x\equiv0\pmod k$. At the even time $n=2t+1+k$ they are the odd ones, $j=k-2x$, which read $v_{t+k-x}$ and are absent when $t-x\equiv0\pmod k$. This motivates the two \emph{read sets}, of the time $2t+1$ and of the time $2t+1+k$ half a period later, \begin{equation} R_+(t)=\{\,t+x\ :\ x\in X,\ t+x\not\equiv0\,\}, \qquad R_-(t)=\{\,t+k-x\ :\ x\in X,\ t-x\not\equiv0\,\}, \label{eq:odd-reads} \end{equation} with congruences modulo $k$; these are sets of positive integers. Modulo $k$, $R_+(t)$ lies in the translate $t+X$ and $R_-(t)$ in the reflection $t-X$, which explains the signs. Each is nonempty when $|X|\ge2$, since at most one $x\in X$ can satisfy $t\pm x\equiv0$. Note that no read ever lands on a multiple of $k$: the tap that would have done so is exactly the one that is absent. The \emph{reduced recursion} is \begin{equation} v_{t+k}-v_t=\min_{y\in R_-(t)}v_y-\min_{y\in R_+(t)}v_y\qquad(t\ge0). \label{eq:odd-vrec} \end{equation} \begin{proposition}[reduction to the odd positions] \label{prop:odd-second} Let $S$ be palindromic with $|S|\ge3$, with $X$ as in \autoref{lem:odd-coords}. If the reduced recursion \eqref{eq:odd-vrec} has an unbounded integer solution $(v_t)_{t\ge0}$, then no equation \eqref{eq:familya} with support $S$ is globally periodic, for any positive coefficients and either $\theta$. \end{proposition} \begin{proof} Define $d_n$ for $n\ge0$ by $d_{2t+1}=v_t$ at odd positions, and at even positions by \[ d_n=\min_{j\in A_n}d_{n+j}-d_{n+k}\qquad(n\text{ even}); \] the right-hand side involves only odd positions ($n+j$ for odd $j$, and $n+k$), so this is a definition. Then \eqref{eq:odd-tangent} holds at every even $n$ by construction. At an odd time $n=2t+1$ the position $n+k$ is even, so by the definition and the description of the attaining taps above, \[ d_{n+k}=\min_{j\in A_{n+k}}d_{n+k+j}-d_{n+2k}=\min_{y\in R_-(t)}v_y-v_{t+k}, \] and hence $d_{n+k}+d_n=\min_{R_-(t)}v-v_{t+k}+v_t=\min_{R_+(t)}v =\min_{j\in A_n}d_{n+j}$ by \eqref{eq:odd-vrec}. So $d$ is an integer solution of the tangent recursion along the alternating orbit $E$ of \autoref{lem:odd-carrier}, which applies because $|X|\ge2$; and $d$ is unbounded because $v$ is. The conclusion is \autoref{thm:tangent}. \end{proof} \subsection{Rays} \label{sec:odd-rays} The unbounded solutions of the reduced recursion used below are \emph{rays of the reduced recursion}: they satisfy $v_{t+k}=v_t+\Delta(t\bmod k)$ for a fixed function $\Delta$ on $\Z/k$, not identically zero. Only residues modulo $k$ matter for the read sets \eqref{eq:odd-reads}: the residues of $R_+(t)$ and $R_-(t)$ are \begin{equation} \bar R_+(r)=(r+X)\setminus\{0\}, \qquad \bar R_-(r)=(r-X)\setminus\{0\}, \qquad r=t\bmod k, \end{equation} the punctured translate and the punctured reflection of $X$. For a set $U\subseteq\Z/k$, say that $r$ is \emph{reflection-blocked} if $\bar R_-(r)\subseteq U$, and \emph{translate-blocked} if $\bar R_+(r)\subseteq U$. \begin{lemma}[indicator rays] \label{lem:odd-ray} Let $|X|\ge2$ and $U\subseteq\Z/k\setminus\{0\}$, and define $\Delta:\Z/k\to\Z$ by \begin{equation} \Delta(r)=\mathbf 1[\,r\text{ reflection-blocked}\,]-\mathbf 1[\,r\text{ translate-blocked}\,]. \label{eq:odd-raycond} \end{equation} Suppose that $0$ is translate-blocked and not reflection-blocked, that no $r\ne0$ is translate-blocked, and that every reflection-blocked $r$ lies in $U$. Suppose also the \emph{vanishing condition}: every blocked read set, that is $\bar R_-(r)$ for $r$ reflection-blocked and $\bar R_+(r)$ for $r$ translate-blocked, contains a residue at which $\Delta$ vanishes. Then \[ v_t=\mathbf 1_U(t\bmod k)-\mathbf 1[\,t\equiv0\,]+\lfloor t/k\rfloor\,\Delta(t\bmod k)\qquad(t\ge0) \] solves the reduced recursion \eqref{eq:odd-vrec}, and $v_{mk}=-1-m$, so $v$ is unbounded. \end{lemma} \begin{proof} The hypotheses say that $\Delta(0)=-1$, that $\Delta\ge0$ elsewhere, and that $\Delta=0$ outside $U\cup\{0\}$. Clearly $v_{t+k}-v_t=\Delta(t\bmod k)$, and $v_{mk}=-1-m$ because $0\notin U$. Now look at the value of $v$ at a read $y$, whose residue $\rho=y\bmod k$ is never $0$, by \eqref{eq:odd-reads}. If $\rho\notin U$ then $\Delta(\rho)=0$ and $v_y=0$. If $\rho\in U$ then $v_y=1+\lfloor y/k\rfloor\Delta(\rho)\ge1$, with equality when $\Delta(\rho)=0$. Hence the minimum of $v$ over a read set is $0$ if some read lies outside $U$, and is exactly $1$ if all reads lie in $U$, that is, if the read set is blocked; in that case the vanishing condition supplies a read with $\Delta(\rho)=0$. So the right-hand side of \eqref{eq:odd-vrec} is $\mathbf 1[\,r\text{ reflection-blocked}\,]-\mathbf 1[\,r\text{ translate-blocked}\,]$ with $r=t\bmod k$, which is $\Delta(r)$. \end{proof} \begin{remark}[the tangent solution is a ray] \label{rem:odd-ray2k} This remark is not used in the proof of \autoref{thm:oddk}. For a solution $v$ as in \autoref{lem:odd-ray}, the tangent solution $d$ built from $v$ in the proof of \autoref{prop:odd-second} is a ray in the sense of \autoref{def:trop-ray}, with $q=2k$. At odd positions, $d_{2t+1+2k}=v_{t+k}=v_t+\Delta(t\bmod k)$. At an even position $n$, write $n+k=2\tau+1$; there $d_n$ is the minimum of $v$ over a read set, less $d_{n+k}=v_\tau$. By the proof of \autoref{lem:odd-ray}, that minimum is $0$ or $1$ and depends only on the residues read, which do not change when $n$ increases by $2k$; so $d_{n+2k}=d_n-\Delta(\tau\bmod k)$. Thus $d_{n+2k}=d_n+u_n$ with $u$ $2k$-periodic, and $u$ is not identically zero since $\Delta(0)=-1$. \end{remark} The whole difficulty is to choose $U$ so that the blocking hypotheses hold, and for that one needs to know when a punctured translate or reflection of $X$ can lie inside $X$ or a slight enlargement of it. \subsection{Rigidity of translates and reflections} \label{sec:odd-rigid} Say that $X$ is \emph{symmetric about} $j\in\Z/k$ if $j-X\subseteq X$ (equivalently $j-X=X$), and that $W=X\cup\{0\}$ is \emph{symmetric about} $z$ if $z\in X$ and $z-x\in X$ for every $x\in X\setminus\{z\}$ (equivalently $z-W=W$). The first three statements below conclude that $X$ is a dilated interval. \begin{lemma}[translate rigidity] \label{lem:odd-trigid} Let $\emptyset\ne X\subseteq\{1,\dots,h\}$ and $\zeta\not\equiv0\pmod k$. If $\zeta+X\subseteq X\cup\{0\}$ modulo $k$, then $X$ is a dilated interval. \end{lemma} \begin{proof} Take $0<\zetah$. Put $\mu=k-\zeta\in\{1,\dots,h\}$, so that translation by $\zeta$ is $x\mapsto x-\mu$ modulo $k$. For $x\in X$ with $x<\mu$, the residue $x-\mu+k$ lies in $\{h+1,\dots,2h\}$ and is neither $0$ nor in $X$; so every $x\in X$ has $x\ge\mu$ and $x-\mu\in X\cup\{0\}$. By induction every element of $X$ is a multiple of $\mu$, and stepping down from $\max X=M\mu$ by $\mu$ stays inside $X$ until it reaches $0$; so $X=\mu\cdot\{1,\dots,M\}$. \end{proof} \begin{lemma}[translates of a symmetric set] \label{lem:odd-symfail} Let $\emptyset\ne X\subseteq\{1,\dots,h\}$ be symmetric about $j$, and let $\zeta\not\equiv0$. If $\zeta+X\subseteq X\cup\{0,j\}$, then $X$ is a dilated interval. \end{lemma} \begin{proof} The translate can leave $X$ only at $0$ and at $j$. It cannot leave at both: if $x_1+\zeta\equiv0$ and $x_2+\zeta\equiv j$ with $x_1,x_2\in X$, then $y=j-x_2\in X$ and $y\equiv\zeta\equiv-x_1$, against \eqref{eq:odd-half}. If it never leaves at $j$, \autoref{lem:odd-trigid} applies directly. If it leaves only at $j$, reflect: for $y\in X$ put $x=j-y\in X$. Either $x+\zeta\in X$, and then $y-\zeta=j-(x+\zeta)\in X$; or $x+\zeta\equiv j$, and then $y-\zeta\equiv0$. So $-\zeta+X\subseteq X\cup\{0\}$, and \autoref{lem:odd-trigid} applies to $-\zeta$. \end{proof} \begin{lemma}[uniqueness of the centre of $W$] \label{lem:odd-wunique} Let $\emptyset\ne X\subseteq\{1,\dots,h\}$. If $W=X\cup\{0\}$ is symmetric about two distinct residues $z$ and $z'$, then $X$ is a dilated interval. \end{lemma} \begin{proof} Put $\zeta=z'-z\not\equiv0$; I check $\zeta+X\subseteq X\cup\{0\}$ and apply \autoref{lem:odd-trigid}. For $x=z$, $x+\zeta=z'\in X$. For $x\ne z$, $y=z-x$ lies in $X$, and $x+\zeta=z'-y$; this is $0$ if $y=z'$, and lies in $X$ otherwise, by the symmetry of $W$ about $z'$. \end{proof} Finally, reflection blocking against $X$ itself is always a symmetry. \begin{lemma}[reflection blocking] \label{lem:odd-frigid} If $(r-X)\setminus\{0\}\subseteq X$, then $X$ is symmetric about $r$ or $W$ is symmetric about $r$. \end{lemma} \begin{proof} If $r\notin X$ then no $r-x$ vanishes, and $r-X\subseteq X$. If $r\in X$ then $r-x\not\equiv0$ for every $x\in X\setminus\{r\}$, so $r-x\in X$ for all such $x$, which is the symmetry of $W$ about $r$. \end{proof} \subsection{The non-dilated sets} \label{sec:odd-nondil} \begin{theorem}[non-dilated sets] \label{thm:odd-nondil} Let $S$ be palindromic with $|S|\ge3$, and suppose that the set $X$ of \autoref{lem:odd-coords} is not a dilated interval. Then no equation \eqref{eq:familya} with support $S$ is globally periodic, for any positive coefficients and either $\theta$. \end{theorem} \begin{proof} By \autoref{prop:odd-second} and \autoref{lem:odd-ray} it suffices to exhibit $U$ satisfying the hypotheses of \autoref{lem:odd-ray}. Here $|X|\ge2$ by \autoref{lem:odd-coords}. If $X$ is symmetric about some $j$, then $j\ne0$, since $-X$ is disjoint from $X$ by \eqref{eq:odd-half}, and $j\notin X$, since otherwise $0=j-j\in X$; take $U=X\cup\{j\}$. Otherwise take $U=X$. In both cases $0$ is translate-blocked, since $\bar R_+(0)=X$, and no $r\ne0$ is translate-blocked: blocking would mean $r+X\subseteq U\cup\{0\}$, and \autoref{lem:odd-trigid} or \autoref{lem:odd-symfail} would make $X$ a dilated interval. It remains to find the reflection-blocked residues and to check the vanishing condition. \emph{$U=X\cup\{j\}$.} Reflection blocking happens exactly at $r=j$, which lies in $U$. Indeed $\bar R_-(j)=j-X=X\subseteq U$. At $r=0$, $\bar R_-(0)=-X$ has at least two elements, none in $X$, so they cannot all equal $j$. At $r\notin\{0,j\}$, put $\zeta=r-j\not\equiv0$; for $y\in X$, the residue $x=j-y$ lies in $X$ and $y+\zeta=r-x$, so reflection blocking at $r$ would give $\zeta+X\subseteq X\cup\{0,j\}$, and \autoref{lem:odd-symfail} would make $X$ a dilated interval. So $\Delta=\mathbf 1_{\{j\}}-\mathbf 1_{\{0\}}$, and the two blocked read sets are $\bar R_-(j)=X$ and $\bar R_+(0)=X$, on which $\Delta$ vanishes. \emph{$U=X$.} The residue $0$ is not reflection-blocked, since $-X$ is disjoint from $X$. If $r$ is reflection-blocked, \autoref{lem:odd-frigid} makes $X$ or $W$ symmetric about $r$; the first is excluded, so $W$ is symmetric about $r$, which puts $r$ in $X=U$. By \autoref{lem:odd-wunique} there is at most one such $r$. So $\Delta$ vanishes on all of $X$ except at most one point, and $\bar R_+(0)=X$, having at least two elements, contains a zero of $\Delta$. If $z$ is reflection-blocked, then for $x\in X$ with $x\ne z$ the read $z-x\in\bar R_-(z)$ is neither $0$ nor $z$, so $\Delta(z-x)=0$; such an $x$ exists as $|X|\ge2$, so $\bar R_-(z)$ also contains a zero of $\Delta$. This is the vanishing condition. \end{proof} \subsection{Dilated intervals} \label{sec:odd-dil} When $X=\mu\cdot\{1,\dots,M\}$ the support is \begin{equation} S=\{\,2\mu i,\ k-2\mu i\ :\ 1\le i\le M\,\},\qquad 2\mu M\le 2hM$ this is the definition. \item[(ii)] $\gamma$ changes value between $M$ and $M+1$, between $-M-1$ and $-M$, and between $h$ and $h+1\equiv-h$. Indeed $\gamma(M)=0$ and $\gamma(M+1)=1$, $\gamma(-M)=1$ and $\gamma(-M-1)=0$ by (i), and $\gamma(-h)=1-\gamma(h)$ by (i). \item[(iii)] $\gamma$ takes both values on any two consecutive residues of $I_+$, since exactly one of them is $\equiv M+1\pmod 2$, and likewise of $I_-$, by (i). \end{itemize} Also $\gamma(-1)=1\ne0=\gamma(2)$. Going round $\Z/k$, the residues fall into the consecutive arcs $[2,M]$, $I_+$, $I_-$, $[-M,-1]$, followed by the excluded pair $\{0,1\}$ and then $[2,M]$ again. By (ii) and the last remark, $\gamma$ changes value between the last residue of each of the four arcs and the first residue of the next (across the excluded pair, between $-1$ and $2$). So if $\gamma$ is constant on the non-excluded elements of a run $R$ of $M$ consecutive residues, then $R$ meets only one of the four arcs, since an arc of fewer than $k$ residues that meets two of them contains a boundary pair. It cannot lie in $I_\pm$, by (iii), as $M\ge2$; so $R\subseteq[-M,1]$ or $R\subseteq[0,M]$. Suppose now that (F2) fails at $s\ne0$. Then $\gamma$ is constant on the non-excluded elements of both runs. The run $s+\{1,\dots,M\}$ lies in $[-M,1]$ or in $[0,M]$, which forces $s\in[-M-1,1-M]$ or $s\in\{-1,0\}$; the run $s-\{1,\dots,M\}$ likewise forces $s\in\{0,1,2\}$ or $s\in\{M,M+1\}$. All these residues lie in $[-M-1,M+1]$, whose $2M+3\le k$ elements are distinct modulo $k$. The first list lies in $[-M-1,0]$ and the second in $\{0\}\cup[1,M+1]$, so the only residue in both is $0$. This contradicts $s\ne0$. \end{proof} \subsection{Proof of \autoref{thm:oddk}} \label{sec:odd-proof} \begin{proof}[Proof of \autoref{thm:oddk}] Let $k=2h+1$ and $S$ be as in the theorem, and let $X$ be as in \autoref{lem:odd-coords}, so that $|X|\ge2$. If $X$ is not a dilated interval, \autoref{thm:odd-nondil} applies. Otherwise $X=\mu\cdot\{1,\dots,M\}$, and $S$ is \eqref{eq:odd-prog}, with $M=|X|\ge2$ and $2\mu M\le2h$. Every element of $S$ is $2\mu i$ or $k-2\mu i$, so $\gcd(\mu,k)$ divides every element of $S\cup\{k\}$, and primitivity gives $\gcd(\mu,k)=1$. If $\mu=1$ and $M=h$, then $S$ is the full support, which is excluded. If $\mu=1$ and $M\le h-1$, then $2M+3\le k$. If $\mu\ge2$, then $4M\le2\mu Ma$ be silent for $Q_\sigma$. Then $i\equiv a+c\pmod2$ and $i\le b$. \end{lemma} \begin{proof} All elements of $Q_\sigma$ have class $c$. The tap $k-a$ wraps at $i$ (as $i>a$), and its position has residue $i-a$, so by \autoref{lem:nao-parity}(e) $i-a\equiv c$, that is $i\equiv a+c$. If $i>b$, the tap $k-b$ also wraps, and in the same way $i\equiv b+c$; but $b\not\equiv a$. \end{proof} Finally, a containment $C_c(i)$ at an odd index empties an interval of the other class. \begin{lemma}[the gap] \label{lem:nao-gap} Let $i$ be odd with $C_c(i)$, and suppose $S_c\ne\emptyset$. Then $S$ has no element of class $1-c$ in the open interval $(i,\ i+\min S_c)$. \end{lemma} \begin{proof} Let $s\in S$ have class $1-c$ and $s>i$. Then $k-s\in S$ has class $1-c$, $i+(k-s)a$). So $i_1>a$, and \autoref{lem:nao-dichotomy} gives $i_1$ odd and $i_1\le b$. By \autoref{lem:nao-parity}(e) $C_1(i_1)$ holds, and \autoref{lem:nao-gap} gives \begin{equation} S_0\cap(i_1,\ i_1+b)=\emptyset . \label{eq:nao-evengap} \end{equation} Now fix an even $\sigma\in S$. I claim that every index $i$ has a surviving tap reading $1$ for $Q_\sigma$. There are four cases. \emph{$ia$.} Suppose $i$ is silent. By \autoref{lem:nao-dichotomy} $i$ is even and $i\le b$, so $ii_1$, so $x+i$ lies in the interval \eqref{eq:nao-evengap}, a contradiction. This proves the claim. The same claim for the even element $k-\sigma$, with \autoref{lem:nao-parity}(b) and \autoref{lem:nao-mirror}, gives a surviving tap reading $0$ at every index for $Q_\sigma$. With \autoref{lem:nao-parity}(a), $(\sigma,Q_\sigma)$ is a $\sigma$-bump. For the last sentence: either $(\sigma,Q_\sigma)$ is a $\sigma$-bump for some odd $\sigma$, or it fails at $\sigma_1=b$ and then $(a,Q_a)$ is one. \end{proof} \subsection{Odd minimum: where the failures sit} From now on $a=\min S$ is odd and $S_0\ne\emptyset$, so that $b=\min S_0$ in the notation above. Then $aa$, then \autoref{lem:nao-dichotomy} makes $i$ odd with $i\le b$, hence $ia$, then \autoref{lem:nao-dichotomy} makes $i$ even with $i\le b$. \end{proof} So a silent index of the even class sits at the end $i=a$ or in the odd part of the inner range $(a,b)$, and a silent index of the odd class at an odd end $i\le a$ or in the even part of the inner range $(a,b]$. When both classes fail, three of the four pairings are impossible, and the fourth is rigid. \begin{lemma}[no inner failure of the even class] \label{lem:nao-noband} Let $i_0$ be odd with $ai_0$ by the maximality of $x$. It cannot lie in the gap, so $x+i_1\ge i_0+b$, which with $x\le i_0$ forces $i_1=b$. But then $a+b\in S$ in the same way, and $i_00$ if $y+r\in W$ for every $y\in W$ with $y\ne w$. Then, for every $y\in W$, the sequence $y,y+r,y+2r,\dots$ stays in $W$ until it reaches $w$, which it must do because $W$ is bounded by $w$; so $r\mid w-y$, and $y,y+r,\dots,w$ all lie in $W$. \begin{lemma}[two end failures] \label{lem:nao-endend} Let $S$ be primitive, and suppose $C_0(a)$ and $C_1(i_1)$ hold with $i_1$ odd and $i_1\le a$. Then $S$ is the full support. \end{lemma} \begin{proof} Put $r=a+i_1$. Composing the two containments makes each class closed under a step, and the two steps turn out to be the same. \emph{The odd class has step $r$.} Let $y\in S_1$ with $ya$, $b=2a$, and $a\mid k$. Every odd $s\in S$ has $2a\mid k-a-s$ and every even $s\in S$ has $2a\mid k-2a-s$, so $a$ divides every element of $S\cup\{k\}$, and primitivity gives $a=1$. Then $r=2$, and the chain from $a=1$ puts every odd number in $[1,k-1]$ in $S$; and for even $y\in(0,k)$, $y-1\in S$ is odd with $1+(y-1)0$ are odd and differ from $a$ and $a+b$ (since $b\ne2a$), so $Q\cap S=\{a\}$, which is (B1). An odd position lies in $Q$ exactly when it is one of $a$, $3a$, $b-a$; an even position lies in $Q$ exactly when it is free, and in particular every even position in $(0,b)\cup(2a,k)$ lies in $Q$. For (B2) it suffices, at each index $i$, to name two surviving taps among $a$, $b$, $2a$, $a+b$ whose reads differ. The indices fall into twelve ranges, six of even and six of odd indices, cut out by the numbers $a$, $b$, $2a$, $a+b$, $2b$ and $3a$, and in each range the same two taps serve. The table of these taps, and the check that they survive and read different values, are in \autoref{app:checks-bfone}. \end{proof} For $M\ge2$ the carrier is the \emph{band carrier}: $a$ together with every free position strictly between $a$ and $k-a$. \begin{lemma}[the case $M\ge2$] \label{lem:nao-bfshadow} Let $S$ have the structure of \autoref{thm:nao-struct} with $M\ge2$, and let \[ \mathcal B=\{\,y\notin S:\ aa$ the tap $k-a$ reads the position $i-a$, wrapped, and so reads $1$ unless $i-a$ lies in $\mathcal B$; when it does, the gaps of $S$, which are shorter than $a$, supply an element $j$ of $S$ just below $i$, and the tap $k-j$ reads a position below $\mathcal B$. The mirror then gives the reads of $0$. \begin{proof} \begin{itemize} \item[(N1)] For $1\le m\le M$, $mb=k-(2a+(M-m)b)\in S$, by palindromy and the last clause of the structure. \item[(N2)] An odd $y\in[a,k-a]$ with $y-a$ not a multiple of $b$ is free, since $S_1=\{a+mb\}$. \item[(N3)] If $aa$, the tap $k-a$ is wrapped, with residue $y=i-a\in(0,k-a)$. If $y\notin \mathcal B$ and $y\ne z$, it survives and reads $1$. \item If $i>a$ and $i-a=z$, then $z\ne k-a$, so $z=a$ and $i=2a$. The tap $k-b$ is wrapped (as $2a>b$), with residue $2a-b\in(0,a)$, which is neither in $\mathcal B$ nor $z$; so it survives and reads $1$. \item If $i>a$ and $i-a\in \mathcal B$, then $ak$, put $p'=p-k$, which has the parity of $p$ and lies outside $S\cup\{0\}$. Then $p\in P$ iff $p'\notin Q$ iff $H(\nu p'+t_p)=0$ iff $H(\nu p'+t_p+k)=1$, by \eqref{eq:allodd-flip}, and $\nu p'+k\equiv \nu p\pmod{2k}$. \end{proof} The clauses at odd indices read only even positions, and all of these are free except the deleted position $k$. They are settled by the following lemma, whose idea is that the phases of $S$ are spread round the circle $\Z/2k$ too evenly to fit into one half, even after one of them is removed. \begin{lemma}[odd indices] \label{lem:allodd-oddhalf} Let $S$ be all-odd, let $\nu$ be odd and $t\in\{0,k\}$, and suppose that $H_\nu(u)\ne H_\nu(v)$ for some $u,v\in L$. Then, for $\sigma=a$ and $Q=Q(\nu;t)$, the clause at every odd index holds. \end{lemma} \begin{proof} Let $i$ be odd. As noted in \autoref{sec:allodd-parity}, the only deleted tap is $k-i$ (if it lies in $S$), and every other tap $j$ reads a free even position $p=i+j$, whose read is $H(\nu p)=H(\nu i+\nu j)$ by \autoref{lem:allodd-free}. So the clause fails exactly when the phases $\nu j\bmod2k$ of the surviving taps all lie in $\{-\nu i,\dots,-\nu i+k-1\}$ or all in $\{-\nu i+k,\dots,-\nu i+2k-1\}$. First I locate the phases. They are odd, so each lies in $U$ or in $V$, and by \eqref{eq:allodd-sym} the tap $k-j$ has phase $k-\nu j$, which lies in the same half as $\nu j$. Since $H_\nu(u)\ne H_\nu(v)$ both halves occur. Let $x_-$ be the least phase in $U$, attained at the tap $u_0$, and $y_-$ the least in $V$, attained at $v_0$. The taps $k-u_0$ and $k-v_0$ have the phases $k-x_-\in U$ and $3k-y_-\in V$, so $2x_-\le k$ and $2y_-\le3k$. Going round the circle, each of the four phases $x_-\le k-x_-j\ge a$, the tap is deleted exactly when $p=a+k$, that is, when the phase of $p$ is $\alpha+k$. Because $p\mapsto \nu p$ is a bijection, $p$ is an unwrapped pin iff $\nu p\in \Phi$, and a wrapped pin iff $\nu p\in \Phi+k$. So a surviving tap whose position has phase $z$ reads \begin{equation} 0 \text{ if } z\in \Phi;\qquad 1 \text{ if } z\in \Phi+k;\qquad \text{otherwise } H(z+t)=\begin{cases}\mathbf 1[z\in U],&t=0,\\ \mathbf 1[z\in V],&t=k,\end{cases} \label{eq:allodd-evenread} \end{equation} by \autoref{lem:allodd-free}; here $z$ is odd, so it lies in $U$ or in $V$. The phases read at $i$ form the \emph{read set} $\phi+\Phi$, less the point $\alpha+k$ when that point is the phase of a deleted tap. For a residue $\tau$ consider the two conditions \[ C_U(\tau):\ \ (\tau+\Phi)\cap U\subseteq \Phi,\qquad C_V(\tau):\ \ (\tau+\Phi)\cap V\subseteq \Phi. \] \begin{lemma}[failing read sets] \label{lem:allodd-windows} With the notation above, suppose that the clause at the even index $i$ fails. \begin{itemize} \item[(i)] If every surviving tap reads $1$, then $C_U(\phi+k)$ holds when $t=0$, and $C_V(\phi+k)$ when $t=k$. \item[(ii)] If every surviving tap reads $0$, then $C_U(\phi)$ holds when $t=0$, and $C_V(\phi)$ when $t=k$, unless some tap is deleted at $i$ and $\alpha+k$ lies in $U$ (for $t=0$), respectively in $V$ (for $t=k$). \item[(iii)] If some tap is deleted at $i$ and $i\ne2a$, then some surviving tap reads $1$. \end{itemize} \end{lemma} \begin{proof} (i) Take $t=0$. Let $x\in \Phi$ with $z=\phi+x\in V$. If $z$ is the deleted point then $z=\alpha+k\in \Phi+k$. Otherwise $z$ reads $1$; by \eqref{eq:allodd-evenread} it is not in $\Phi$, and since $z\notin U$ it must lie in $\Phi+k$. So $(\phi+\Phi)\cap V\subseteq \Phi+k$, and adding $k$ gives $C_U(\phi+k)$. The case $t=k$ is the same with $U$ and $V$ exchanged. (ii) Take $t=0$. Let $x\in \Phi$ with $z=\phi+x\in U$, and suppose $z$ is not the deleted point; this is automatic unless a tap is deleted and $\alpha+k\in U$. Then $z$ reads $0$, so $z\notin \Phi+k$, and as $z\in U$ \eqref{eq:allodd-evenread} forces $z\in \Phi$. The case $t=k$ is the same. (iii) The deleted tap is $j_0=a+k-i$. The tap $k-a\in S$ reads $i+k-a=k+(k-j_0)$, a wrapped pin, since $k-j_0\in S$. It is deleted only if $k-j_0=a$, that is $i=2a$. So for $i\ne2a$ it reads $1$. \end{proof} Two failures of opposite type, one in $U$ and one in $V$, are incompatible. The reason is that together they force $\Phi$ to contain a whole coset of a subgroup, which a set of the form $\nu S$ cannot do. \begin{lemma}[no coset] \label{lem:allodd-nocoset} Let $\nu$ be a unit modulo $2k$ and $S\subseteq\{1,\dots,k-1\}$. Then $\Phi=\nu S$ contains no coset $c+g\Z/2k\Z$ with $g\mid2k$ and $0\phi'$ I may replace $\Phi$ by $\Phi+k$, and I may therefore also take $\phi\le\phi'$. \emph{Translation into $(0,k)$.} Put $Y_+=\Phi\cap U$ and $Y_-=\{z:z+k\in \Phi\cap V\}$, two nonempty sets of odd integers in $(0,k)$. By $\Phi=k-\Phi$ both are closed under $z\mapsto k-z$ (for $Y_-$: $k-(m+k)\equiv(k-m)+k$). The hypotheses give four rules: \begin{itemize} \item[(G1)] if $p\in Y_+$ and $p+\phi0$, and suppose that for every $p\in\Pi$ there is $p'\in\Pi$ with $p'\equiv p+f\pmod n$. Then $\Pi$ is $\gcd(n,f)$-periodic. Indeed, write $g=\gcd(n,f)$ and choose $y\ge0$ with $yf\equiv g\pmod n$. If $p\in\Pi$, $0k$, put $z=w-k$, so that $-z\equiv k-c\pmod g$. Let $z'=(-z)\bmod \gamma$, which is odd with $090$ there are two routes. Either some $x\in L\setminus\{a\}$ gives (T) through a unit that witnesses the progression $2a-x$, $a$, $x$, provided $x<2a$ or $x-2a\notin S$ (\autoref{lem:allodd-aproute}(i)); or $L$ is the chain $a,3a,\dots,(2m+1)a$, and \autoref{thm:lemmaA}, applied to the rescaled triple $(k;1,2m+3)$, supplies the unit. Triples with $\gcd(a,x,k)>1$ may have no witness, but these are rescaled copies of the $59$ failures at orders up to $90$ listed in \autoref{lem:allodd-pf} (see \autoref{lem:allodd-lift}), and \autoref{lem:allodd-nofail} shows that they cannot block both routes, except for $a=15$ at $k=120$, which is settled by hand. The orders $k\le90$ are a finite check. \begin{definition}[witnesses and admissible triples] \label{def:allodd-adm} Let $k$ be even and let $a,x$ be integers. A unit $\nu$ modulo $2k$ \emph{witnesses} the triple $(k;a,x)$ if \begin{equation} H_\nu(2a-x)=H_\nu(a)\ne H_\nu(x), \label{eq:allodd-ap} \end{equation} and $(k;a,x)$ \emph{has a witness} if some unit does. The triple is \emph{admissible} if $a90$ has a witness}. \begin{lemma}[the progression route] \label{lem:allodd-aproute} Let $S$ be primitive and all-odd with $1\notin S$. \begin{itemize} \item[(i)] Let $x\in L\setminus\{a\}$, and suppose that $x<2a$ or $x-2a\notin S$. Then every unit $\nu$ witnessing $(k;a,x)$ satisfies (T). \item[(ii)] Suppose that $|L|\ge2$ and that every $x\in L\setminus\{a\}$ has $x>2a$ and $x-2a\in S$. Then $\gcd(a,k)=1$, and there is $m\ge1$ with $2(2m+1)a2a$ (equality is excluded by parity), then $2a+j=k-(x-2a)k$ puts $k-y$ in $L$, so $a\mid k-y$ and again $a\mid k$. But $a\ge3$ and $\gcd(a,k)=1$. \end{proof} Up to order $90$ some admissible triples have no witness, and these failures propagate upwards by scaling. \begin{lemma}[small orders] \label{lem:allodd-pf} Let $(n;a,x)$ be admissible with $n\le90$. Then $(n;a,x)$ has a witness unless it is one of the $59$ triples \begin{center} \small \begin{tabular}{r|l} $n$ & $(a,x)$\\\hline 12 & (1,5) (3,5)\\ 16 & (1,5) (1,7) (3,7)\\ 20 & (1,7) (3,5) (7,9)\\ 22 & (1,5) (1,9) (5,7)\\ 24 & (1,5) (1,11) (3,7) (5,7) (5,9) (7,9)\\ 28 & (1,7) (3,13) (7,9)\\ 30 & (1,11) (1,13) (7,13)\\ 36 & (1,7) (1,15) (1,17) (5,11) (5,13) (7,17) (11,15)\\ 40 & (1,5) (1,15) (3,15) (5,17) (7,19) (9,13) (15,19)\\ 42 & (1,5) (1,9) (1,17) (3,19) (5,7) (11,15) (11,19) (13,15)\\ 48 & (3,11) (15,23)\\ 60 & (1,23) (11,13) (13,27) (19,21)\\ 70 & (1,17) (3,25) (9,13) (13,15)\\ 90 & (1,33) (17,21) (19,41) (23,39) \end{tabular} \end{center} Denote this list by $\mathcal F$. \end{lemma} \begin{proof} This is a finite check: for every admissible triple with $n\le90$ not in $\mathcal F$, a search over the units $\nu$ modulo $2n$ finds a witness. \end{proof} \begin{lemma}[lifting] \label{lem:allodd-lift} If $(n;a,x)$ has a witness, then so does $(gn;ga,gx)$ for every $g\ge1$. Consequently, let $k>90$ and let $(k;a,x)$ satisfy every condition of admissibility except perhaps $\gcd(a,x,k)=1$. If $(k;a,x)$ has no witness, then, with $g=\gcd(a,x,k)$, the triple $(k/g;a/g,x/g)$ lies in $\mathcal F$. \end{lemma} \begin{proof} Let $\nu$ be a unit modulo $2n$ witnessing $(n;a,x)$. Reduction $\Z/2gn\to\Z/2n$ maps units onto units, so there is a unit $\nu'$ modulo $2gn$ with $\nu'\equiv \nu\pmod{2n}$. For every integer $y$, $\nu'\,gy\bmod 2gn=g\,(\nu y\bmod2n)$, which is less than $gn$ exactly when $\nu y\bmod 2n90$ this contradicts \autoref{thm:lemmaA}, so $k/g\le90$, and \autoref{lem:allodd-pf} puts the triple in $\mathcal F$. \end{proof} Above order $90$ the lifted failures can still occur, but only in a way that the three-point condition can absorb. \begin{lemma}[failures above order $90$] \label{lem:allodd-nofail} Let $k>90$ be even, and let $S$ be primitive and all-odd with $1\notin S$ and $(k,a)\ne(120,15)$. Suppose that every $x\in L\setminus\{a\}$ for which $(k;a,x)$ has a witness satisfies $x>2a$ and $x-2a\in S$; that is, route (i) of \autoref{lem:allodd-aproute} is available for no $x$. Then $(k;a,x)$ has a witness for every $x\in L\setminus\{a,3a\}$. \end{lemma} \begin{proof} Suppose that $(k;a,x_0)$ has no witness for some $x_0\in L\setminus\{a,3a\}$; I derive a contradiction. Let $\mathcal M$ be the set of orders $n$ such that $(n;a',x')\in\mathcal F$ for some $a',x'$ with $n\mid k$ and $a=(k/n)a'$, and let $\ell=\operatorname{lcm}\mathcal M$. For $y\in L\setminus\{a,3a\}$ write $g_y=\gcd(a,y,k)$. If $(k;a,y)$ has no witness, then \autoref{lem:allodd-lift} gives $(k/g_y;a/g_y,y/g_y)\in\mathcal F$, so $k/g_y\in\mathcal M$. In particular $\mathcal M$ is nonempty (take $y=x_0$). Every element of $\mathcal M$ divides $k$, so $\ell\mid k$; write $k=\ell f$. For every $n\in\mathcal M$, $n\mid\ell$, so $f$ divides $k/n$; hence $f\mid g_y$ whenever $(k;a,y)$ has no witness. In particular $f\mid g_{x_0}\mid a$, so $f$ is odd. I claim that $f$ divides every $y\in L$, by induction on $y$. For $y=a$ this was just shown. For $y\ne a$ there are three cases. If $(k;a,y)$ has a witness, then $y-2a\in L$ by hypothesis, $f\mid y-2a$ by induction, and so $f\mid y$. If it has none and $y=3a$, then $f\mid a\mid y$. If it has none and $y\ne3a$, then $f\mid g_y\mid y$. Since $f$ is odd and divides $k$, it also divides $k/2$ and every $k-y$; so $f$ divides $\gcd(S\cup\{k\})=1$. Hence $\ell=k$. It remains to see that $\ell=k$ is impossible. Each $n\in\mathcal M$ comes from a failure $(n;a',x')\in\mathcal F$ with $a'/n=a/k$, so all the orders in $\mathcal M$ carry failures with one and the same ratio $a'/n$. Inspecting $\mathcal F$, a ratio occurs at two different orders only three times: $3/12=7/28$, $3/24=5/40$ and $1/16=3/48$. So either $\mathcal M$ is a single order, and $\ell\le90$, or $\ell$ divides $\operatorname{lcm}(12,28)=84$, $\operatorname{lcm}(24,40)=120$ or $\operatorname{lcm}(16,48)=48$. As $\ell=k>90$, this leaves $k=120$ with $a/k=1/8$, that is, $a=15$, which is excluded. \end{proof} \begin{theorem}[the three-point condition] \label{thm:allodd-e3all} Let $S$ be primitive and all-odd, with $1\notin S$ and $|L|\ge2$, and not one of the supports listed in \autoref{tab:allodd-base}. Then some unit $\nu$ modulo $2k$ satisfies (T). \end{theorem} \begin{proof} \emph{Orders $k>90$.} If some $x\in L\setminus\{a\}$ has a witness for $(k;a,x)$ and satisfies $x<2a$ or $x-2a\notin S$, \autoref{lem:allodd-aproute}(i) gives (T). Otherwise, if $(k,a)\ne(120,15)$, \autoref{lem:allodd-nofail} applies, and every $x\in L\setminus\{a,3a\}$ has a witness, so it satisfies $x>2a$ and $x-2a\in S$; so does $x=3a$, since $a\in S$. So \autoref{lem:allodd-aproute}(ii) applies. It gives $\gcd(a,k)=1$ and $m\ge1$ with $(2i+1)a\in S$ for $i\le m$, $2(2m+1)a30$ and $x-30\in S$. Let $x\in L\setminus\{15,45\}$ have no witness. By \autoref{lem:allodd-lift}, $(120/g;15/g,x/g)\in\mathcal F$ with $g=\gcd(15,x,120)$, and $g\ne1$ since the orders in $\mathcal F$ are at most $90$. The only entries of $\mathcal F$ of the forms $(40;5,\cdot)$, $(24;3,\cdot)$ and $(8;1,\cdot)$ are $(40;5,17)$ and $(24;3,7)$, so $x\in\{35,51\}$. Every element of $L$ therefore lies in $\{15,35,45,51\}$, by induction: an $x\in L$ with a witness has $x-30\in L$, and $x-30\in\{15,35,45,51\}$ with $x<60$ forces $x=45$. If $35\notin L$, then $3$ divides every element of $L$, hence every element of $S$ (as $k/2=60$ is even, $S=L\cup(k-L)$), contradicting primitivity; so $35\in L$, and in the same way, with $5$ in place of $3$, $51\in L$. Now the unit $\nu=11$ satisfies (T), with residues modulo $240$. First $H_{11}(15)=0$, as $11\cdot15=165$. (Ta) holds with $x=51$, since $11\cdot51\equiv81$. For (Tb), if $45\notin S$ take $j=15$, so that $2a+j=45\notin S$ and $11\cdot45\equiv15$; if $45\in S$ take $j=k-35=85$, so that $2a+j=115\notin S$ (as $590$, with one obvious exception. The proof is by the geometry of numbers. The pairs $(\nu a,\nu e)$, reduced modulo $2k$, are the points of a planar lattice of determinant $2k$, and a lattice point with $\nu$ a unit in one of four open triangles yields a witness. The triangles cover a quarter of the square $[0,2k)^2$, which contains $2k$ lattice points, so one expects about $k/2$ lattice points in them; the difficulty is to make this rigorous for every lattice, including very skewed ones whose points lie on a few widely spaced lines, and to find a unit point. Along a lattice line the multipliers form an arithmetic progression, so Jacobsthal's function $J(n)$ bounds how far one must go along a line to reach a unit. A short vector of the lattice then settles the question: either it is long enough that a whole band of lines crosses the incircle of a triangle, or it is one of finitely many short directions, for which chords inside the triangles are tabulated once and for all. Above order $2730$, elementary bounds on $J(n)$ and this chord table finish the proof (\autoref{sec:lemmaA-tail}). At orders $92\le k\le2730$ with at most two odd prime factors a direct argument applies (\autoref{sec:lemmaA-twoprime}), and at the other orders up to $2730$ a finite certificate does (\autoref{app:lemmaA-finite}). On a first reading one can skip the proofs of the lemmas and \autoref{app:lemmaA-finite}. \subsection{Statement} The functions $H$ and $H_\nu$ are those of \eqref{eq:allodd-eps}, and witnesses and admissible triples are as in \autoref{def:allodd-adm}. For an integer $y$ write $\langle y\rangle\in\{0,\dots,2k-1\}$ for its residue modulo $2k$, so that $H(y)=1$ exactly when $\langle y\rangle90$ has a witness. \end{theorem} Both restrictions are genuine. If $x=3a$ then $2a-x=-a$, and since $\nu a$ is odd it is neither $0$ nor $k$ modulo $2k$, so $H_\nu(-a)= 1-H_\nu(a)$ for every $\nu$. The bound on $k$ cannot simply be dropped either: the triple $(90;1,33)$ satisfies every other condition, but it has no witness, as a direct check of the $48$ units modulo $180$ shows. It is convenient to work with the pair $(a,e)$, $e=x-a$, and to allow any integer pair. Since $2a-x=a-e$ and $x=a+e$, a unit $\nu$ witnesses $(k;A,A+E)$ exactly when \begin{equation} H\bigl(\nu(A-E)\bigr)=H(\nu A)\ne H\bigl(\nu(A+E)\bigr), \label{eq:lemmaA-good} \end{equation} and I shall say that a pair $(A,E)$ of integers \emph{has a witness} if some unit $\nu$ satisfies \eqref{eq:lemmaA-good}. Since $H$ depends only on residues modulo $2k$, this depends only on $A$ and $E$ modulo $2k$. \autoref{thm:lemmaA} states that $(a,x-a)$ has a witness. Throughout the rest of the section $(k;a,x)$ is admissible with $k>90$, unless stated otherwise, and $e=x-a$. Then \begin{equation} a\ \text{odd},\quad e\ \text{even},\quad 0, <20d>), d = 0, ..., 2k - 1; units are the odd d \foreach \d in {0,...,255} { \pgfmathtruncatemacro\X{mod(9*\d,256)} \pgfmathtruncatemacro\Y{mod(20*\d,256)} \ifodd\d \node[pt,fill=black] at (\X,\Y) {}; \else \node[pt,draw=black,fill=white,line width=0.4pt] at (\X,\Y) {}; \fi } % the two unit points of the chord, d = 67 and d = 41 \foreach \P in {(91,60),(113,52)} \draw[orange!85!black,line width=0.7pt] \P circle (4.2); % centre and radius \draw[red!75!black,line width=0.6pt] (101.490,64) -- (128,64); \fill[red!75!black] (101.490,64) circle (1.8); \node[red!75!black,above left=-1pt] at (101.490,64) {$O$}; \node[red!75!black,above=-1pt] at (114.7,64) {$\rho$}; % frame and ticks \draw[line width=0.6pt] (0,0) rectangle (256,256); \foreach \t/\s in {0/0,64/{k/2},128/k,192/{3k/2},256/2k} { \draw (\t,0) -- (\t,-3) node[below] {$\s$}; \draw (0,\t) -- (-3,\t) node[left] {$\s$}; } \node[below=12pt] at (160,0) {$X$}; \node[left=26pt] at (0,160) {$Y$}; % labels \node[lab] at (120,106) {$\Delta_1$}; \node[lab] at (216,74) {$\Delta_2$}; \node[lab] at (8,150) {$\Delta_3$}; \node[lab] at (136,150) {$\Delta_4$}; \node[text=orange!60!black,inner sep=0pt] at (52,86) {$\mathcal L_4$}; \end{tikzpicture} \caption{The geometry of \autoref{lem:lemmaA-region} and \autoref{prop:lemmaA-band}, drawn to scale for $k=128$ and $(a,e)=(9,20)$. The square is $[0,2k]^2$ and the shaded triangles are $\Delta_1,\dots,\Delta_4$. The dots are the $2k$ points $(\langle \nu a\rangle,\langle \nu e\rangle)$ of $\Lambda$ in the square, filled for the unit points ($\nu$ odd) and open for the others. A shortest vector is $v=(11,-4)$, of length $l=\sqrt{137}$, and $w=(a,e)$ has $v\times w=2k$; the grey lines are the lines $\mathcal L_0,\dots,\mathcal L_{14}$, a distance $2k/l\approx21.9$ apart. The circle is the incircle of $\Delta_1$, with centre $O$ and radius $\rho$. The line $\mathcal L_4$ passes within $0.06\,k$ of $O$, and its chord across the disc (thick) contains the points with $\nu=208,67,182,41$; the two unit points among them (circled) show that $(9,20)$ has a witness. Here $g=1$ and $n=2$, and both hypotheses of \autoref{prop:lemmaA-band} hold.} \label{fig:lemmaA-geometry} \end{figure} \begin{lemma}[the target region] \label{lem:lemmaA-region} If $\gcd(\nu,2k)=1$ and $(\langle \nu A\rangle,\langle \nu E\rangle)\in R$, then $\nu$ satisfies \eqref{eq:lemmaA-good}, so $(A,E)$ has a witness. \end{lemma} \begin{proof} Write $X=\langle \nu A\rangle$ and $Y=\langle \nu E\rangle$, so that $H(\nu A)=H(X)$ and $H(\nu(A\pm E))=H(X\pm Y)$. If $(X,Y)\in \Delta_1$ then $k-X0$, or $p=0J(n)$ and $jw+tv\in\Delta+2kz$ for all $t\in(t_0,t_1)$, then $(a,e)$ has a witness. \end{lemma} \begin{proof} The integers $i_0,\dots,i_0+J(n)-1$ with $i_0=\lfloor t_0\rfloor+1$ lie in $(t_0,t_0+J(n)]\subset(t_0,t_1)$. By \autoref{lem:lemmaA-line} one of the points $jw+iv$ with such $i$ is a unit point. It lies in $\Delta+2kz$, and since $\Delta\subset(0,2k)^2$ its residues modulo $2k$ lie in $\Delta\subset R$. Now apply \autoref{lem:lemmaA-labels}(c). \end{proof} \subsection{Two ways to find a chord} The first way uses a band of lines through the incircle of $\Delta_1$, and works when the shortest vector is long. \begin{proposition}[the band] \label{prop:lemmaA-band} With $v=gu$ as in \autoref{lem:lemmaA-frame} and $n$ as in \autoref{lem:lemmaA-line}, suppose that \[ J(g)<0.102\,l\qquad\text{and}\qquad J(n)\,l<0.3604\,k. \] Then $(a,e)$ has a witness. \end{proposition} \begin{proof} Let $D$ be the open disc of radius $\rho$ about the incentre $O$ of $\Delta_1$; it lies in $\Delta_1$. Put $\tau=(v\times O)/2k$, so that $O$ is at signed distance $2k\tau/l$ from $\mathcal L_0$. The $J(g)$ consecutive integers $\lfloor\tau-J(g)/2\rfloor+1,\dots,\lfloor\tau-J(g)/2\rfloor+J(g)$ include one, $j$, prime to $g$, and every one of them satisfies $|j-\tau|\le J(g)/2$. So the distance from $O$ to $\mathcal L_j$ is at most $(2k/l)\,J(g)/2=J(g)k/l<0.102\,k$. The line $\mathcal L_j$ therefore meets $D$ in an open segment of length greater than $2\sqrt{\rho^2-(0.102\,k)^2}$. By \eqref{eq:lemmaA-rho}, $\rho^2=\tfrac14(3-2\sqrt2)k^2>0.04289\,k^2$, and $(0.102\,k)^2=0.010404\,k^2$, so the segment is longer than $2\sqrt{0.03248}\,k>0.3604\,k>J(n)\,l$. In terms of the parameter $t$ of $\mathcal L_j$ (in which the lattice points sit at the integers) the segment has length greater than $J(n)$, and it lies in $\Delta_1$. \autoref{lem:lemmaA-chord} completes the proof. \end{proof} The second way handles the short directions. Its key feature is that the geometry does not depend on $k$, $a$ or $e$ once everything is scaled by $2k$. Scale the triangles: let $\widehat\Delta_i=\Delta_i/2k$, so that \begin{align*} \widehat\Delta_1&=\{(X,Y):\ \tfrac140\}$ with $f$ affine. If, for each of the three functionals, $f\ge0$ at the two points with parameters $s_0$ and $s_1$ and $f>0$ at one of them, then $f>0$ on the open segment between them, because along the segment $f$ is a combination of its two end values with positive weights. These are nine rational sign conditions. \begin{proposition}[a tabulated chord] \label{prop:lemmaA-table} With $v=gu$ as in \autoref{lem:lemmaA-frame} and $n$ as in \autoref{lem:lemmaA-line}, suppose $(g;p,q)$ has a chord witness of length $\psi$ with $2k\psi>J(n)\,g$. Then $(a,e)$ has a witness. \end{proposition} \begin{proof} By \eqref{eq:lemmaA-scaled}, $jw+tv\in\Delta_i+2kz$ for all $t$ in an open interval of length $2k\psi/g>J(n)$. \autoref{lem:lemmaA-chord} applies. \end{proof} When neither proposition applies directly, the lattice can be pinned down completely. Since $gu\in\Lambda$, the pair $(a,e)$ is, up to a unit, one of at most $g^2$ explicit pairs. \begin{lemma}[lattice classes] \label{lem:lemmaA-class} Let $v=gu$ be as in \autoref{lem:lemmaA-frame} and $n_0=2k/g$. There are a unit $\eta$ modulo $2k$ and integers $0\le s,t1$, or for which $2k\mid m(pE-qA)$ for some $0J(n)\,g$, after \eqref{eq:lemmaA-ratio}. The bounds on Jacobsthal's function used below are proved in \autoref{app:lemmaA-jacbounds} (\autoref{cor:lemmaA-jac}). \begin{proposition} \label{prop:lemmaA-tail} Let $k$ be even and satisfy the tail condition \eqref{eq:lemmaA-tailcond} with bound $m=J(2k)$. Then \autoref{thm:lemmaA} holds at the order $k$. The tail condition with $m=J(2k)$ holds for every even $k>2730$. \end{proposition} \begin{proof} For the last statement, write $J=J(2k)$. By \autoref{cor:lemmaA-jac}(a), $17.8\,J^2\le k$. If $J\ge10$ this gives $169.9\,J<178\,J\le17.8\,J^2\le k$, and if $J\le9$ then $169.9\,J<1530169.9\,J$. \emph{Short vectors, $l^2\le6400$.} Then $(g;p,q)\in\mathcal V$ by \autoref{lem:lemmaA-frame}(c) and \autoref{lem:lemmaA-zero}, and \eqref{eq:lemmaA-ratio} gives $2k\psi\ge kg/169.9>Jg\ge J(n)g$, so \autoref{prop:lemmaA-table} applies. \emph{Long vectors, $l>80$.} By \autoref{cor:lemmaA-jac}(b), either $J(g)\le8<0.102\cdot80<0.102\,l$, or $J(g)<0.102\,g\le0.102\,l$. By \autoref{lem:lemmaA-frame}(b), $l^2\le4k/\sqrt3$, so \[ J(n)^2l^2\le\frac{k}{17.8}\cdot\frac{4k}{\sqrt3}<0.12975\,k^2, \] and $J(n)\,l<0.36021\,k$. So \autoref{prop:lemmaA-band} applies. \end{proof} \subsection{Orders with at most two odd primes} \label{sec:lemmaA-twoprime} When $k$ has at most two odd prime factors, \autoref{thm:lemmaA} has a direct proof, with no lattice. It covers $1193$ of the $1320$ orders $92\le k\le2730$, so that the finite certificate is needed only at the $127$ orders with three or more odd prime factors. The idea is that one term of the progression is then a unit; normalising it to $1$ leaves a one-parameter problem, which explicitly located multipliers solve. Throughout, if $c$ is a unit and $\nu$ satisfies \eqref{eq:lemmaA-good} for the pair $(cA,cE)$, then $\nu c$ satisfies it for $(A,E)$; so $(A,E)$ has a witness as soon as $(cA,cE)$ does. \begin{lemma}[two normal forms] \label{lem:lemmaA-normal} Let $k$ be even. \begin{enumerate} \item[(a)] If $m$ is a unit with $0\frac12 , \label{eq:lemmaA-chain} \end{equation} the middle condition for $j=1,\dots,N-1$. The pair $(m_j,i_j)$ serves when $D/k$ lies roughly in the interval $\bigl((2i_j+1)/m_j,\,(2i_j+2)/m_j\bigr)$, where $m_jD$ falls in the window $\bigl((2i_j+1)k,\,(2i_j+2)k\bigr)$; the three conditions say that, with a margin $1/K$, these intervals overlap and together cover $[1/8,1/2]$. \autoref{tab:lemmaA-chains} lists ten chains, one for each pattern of small primes dividing $k$; their conditions \eqref{eq:lemmaA-chain} are checked in exact rational arithmetic. \begin{table} \centering \small \begin{tabular}{llr} case & chain $m_1^{i_1}\,m_2^{i_2}\cdots$ & $K$\\\hline $3,5\nmid k$ & $9^0\,5^0\,3^0$ & $92$\\ $3\mid k$; $5,7,11,13,19\nmid k$ & $11^0\,7^0\,5^0\,19^3\,13^2\,7^1$ & $96$\\ $5\mid k$; $3,7,11\nmid k$ & $9^0\,7^0\,27^3\,11^1\,3^0$ & $100$\\ $15\mid k$ & $11^0\,7^0\,19^2\,11^1\,49^8\,43^7\,31^5\,19^3\,13^2\,7^1$ & $120$\\ $21\mid k$ & $11^0\,19^1\,17^1\,5^0\,19^3\,23^4\,17^3\,11^2$ & $126$\\ $33\mid k$ & $13^0\,25^1\,7^0\,5^0\,13^2\,7^1$ & $132$\\ $39\mid k$ & $11^0\,19^1\,17^1\,5^0\,19^3\,23^4\,17^3\,11^2$ & $156$\\ $57\mid k$ & $11^0\,7^0\,5^0\,29^5\,13^2\,7^1$ & $114$\\ $35\mid k$ & $9^0\,17^1\,23^2\,13^1\,11^1\,3^0$ & $140$\\ $55\mid k$ & $9^0\,7^0\,19^2\,17^2\,3^0$ & $110$ \end{tabular} \caption{The chains used in the proof of \autoref{prop:lemmaA-twoprime}, for even $k\ge92$ with at most two odd prime factors; $m^i$ stands for the pair $(m,i)$. In each case $K$ is the least such order, so $k\ge K$, and every multiplier is a unit.} \label{tab:lemmaA-chains} \end{table} \begin{proposition}[two odd primes] \label{prop:lemmaA-twoprime} Let $k\ge92$ be even, with at most two odd prime factors. Then every admissible triple $(k;a,x)$ has a witness. \end{proposition} \begin{proof} The units modulo $2k$ are the odd integers prime to the odd primes of $k$, of which there are at most two. So if three odd integers are such that no prime factor of $k$ divides two of them, one of them is a unit. Write $e=x-a$, so that \eqref{eq:lemmaA-adm} holds. An odd prime of $k$ dividing two of $a-e$, $a$, $a+e$ divides $a$ and $e$, which \eqref{eq:lemmaA-adm} excludes, so one of these three is a unit. \emph{The case where $a$ is a unit.} Let $\bar a$ be its inverse modulo $2k$ and $D=\langle\bar ae\rangle$, which is even. It suffices to find a witness for $(1,D)$. Since $aD\equiv e$, the values $D=0,2,k-2,k,k+2,2k-2$ would give $e\equiv0,2a,k-2a,k,k+2a,-2a\pmod{2k}$, which \eqref{eq:lemmaA-adm} excludes (as $0k$ and $m(D+1)<2k$, which is \eqref{eq:lemmaA-window} with $i=0$, and $m<2k/5$. The length of $I$ is $k(D-3)/(D^2-1)$, which exceeds $6$: for $D\le11$ because $k\ge92$, and for $D\ge12$ because $k\ge8D$ and $8D(D-3)-6(D^2-1)=2D(D-12)+6>0$. So $I$ contains three consecutive odd integers. Their pairwise differences are $2$ and $4$, so no odd prime divides two of them, and one of them is a unit. If $8D>k$, take the chain of \autoref{tab:lemmaA-chains} for the case of $k$; the cases are exhaustive, and in each the multipliers are units, because $k$ has at most two odd primes. The first multiplier satisfies the left inequality of \eqref{eq:lemmaA-window}, as $m_1D>m_1k/8\ge(2i_1+1)k+m_1k/K\ge(2i_1+1)k+m_1$, since $k\ge K$. If $m_j$ satisfies the left inequality but not the right one, then $D/k\ge(2i_j+2)/m_j-1/k$, and \eqref{eq:lemmaA-chain} gives the left inequality for $m_{j+1}$. The right inequality cannot fail for $m_N$, as $D/k\le1/2$. So some $m_j$ satisfies \eqref{eq:lemmaA-window}. \emph{The case where $a-e$ is a unit.} Let $y=2a-x=a-e$, $\bar y$ its inverse and $A=\langle\bar ya\rangle$. Then $\bar ye\equiv A-1$, so it suffices to find a witness for $(A,A-1)$. It may be assumed that $a$ is not a unit. Let $f=\gcd(A,2k)=\gcd(a,k)$. It is odd and $1q$ and $3\nmid\nu_0$, take $\nu=\nu_0$. If $\nu_0>q$ and $3\mid\nu_0$, take $c=q-3$ and $\nu$ the residue of $c\nu_0$ modulo $M$, so that $\nu A\equiv3c=k-9$. Here $\nu$ is prime to $M$, since a common prime factor of $q-3$ and $q$ divides $3$. As $\nu_0$ is odd, $q\nu_0\equiv q\pmod M$, so $\nu\equiv q-3\nu_0$, and as $q<\nu_0<2q$, $\nu$ is $5q-3\nu_0$ or $7q-3\nu_0$, which is prime to $3$. Then $\langle2(k-9)-\nu\rangle=2k-18-\nu\ge k$, since $\nu2730$, \autoref{prop:lemmaA-tail} applies, and if $k\le2730$, $k$ is one of the $127$ orders of the finite certificate of \autoref{prop:lemmaA-finite} in \autoref{app:lemmaA-finite}. \end{proof} For $92\le k\le2730$ the theorem can also be confirmed directly, independently of the certificate: a direct search over the units $\nu$ modulo $2k$ finds a witness for each of the $100\,435\,222$ admissible triples $(k;a,x)$ in this range. \section{Proof of the main theorem} \label{sec:assembly} By \autoref{cor:red-primitive} it is enough to show the following: if an equation \eqref{eq:familya} is globally periodic, its support $S$ is primitive and its coefficients satisfy $c_j=c_{k-j}$, then its normalised data is of known type (\autoref{def:red-known}). So let such an equation be given. Since $c_j=c_{k-j}$, its support is palindromic. \emph{$|S|\le2$.} By the case analysis at the start of \autoref{sec:small}, either $S=\emptyset$, which is case (K1); or $k=2$ and $S=\{1\}$, where \autoref{thm:order2} gives case (K2); or $k=3$ and $S=\{1,2\}$, where \autoref{thm:order3} gives case (K3); or \autoref{thm:twoterm} shows that the equation is not globally periodic, a contradiction. \emph{$|S|\ge3$.} I show that no such equation is globally periodic, which leaves only the three cases above. If $S$ is the full support $\{1,\dots,k-1\}$, then $k\ge4$ and \autoref{thm:fullsupport} applies. So suppose $S$ is not the full support. If $k$ is odd, \autoref{thm:oddk} applies. If $k=6$ and $S=\{1,3,5\}$, \autoref{prop:order6cert} applies. Otherwise $k$ is even and $(k,S)\ne(6,\{1,3,5\})$, and $S$ carries a $\sigma$-bump: by \autoref{thm:notallodd} if $S$ has an even element, and by \autoref{thm:alloddall} if every element of $S$ is odd. In either case \autoref{thm:sigmabump} shows that no equation with support $S$ is globally periodic. So every globally periodic equation \eqref{eq:familya} with primitive support and palindromic coefficients has normalised data of known type. By \autoref{cor:red-primitive}, a globally periodic equation \eqref{eq:family} is therefore the shift or has the coefficients listed in \autoref{lem:red-members}, and these are exactly the equations listed in \autoref{thm:main}. This completes the proof of \autoref{thm:main}. \qed The argument for supports with three or more elements never uses the coefficients, and it therefore also proves a statement about the min-plus recursion alone, extending the result of \citet{CsornyeiLaczkovich2001} for the full support (\autoref{sec:fullsupport}). \begin{corollary}[the min-plus map is not periodic] \label{cor:trop-nonperiodic} Let $S\subseteq\{1,\dots,k-1\}$ be palindromic with $|S|\ge3$, and let $\theta\in\{0,1\}$. Then no power of the min-plus map $T$ of \autoref{def:trop-minplus} is the identity: for every $p\ge1$ there is an integer window $w\in\Z^k$ with $T^{\,p}(w)\ne w$. \end{corollary} \begin{proof} Suppose first that $S$ is primitive. The proof of \autoref{thm:main} above provides an integer solution $e$ of the min-plus recursion \eqref{eq:trop-rec} for $(k,S,\theta)$ that carries an unbounded integer tangent solution $d$: for the full support by \autoref{lem:fs-carrier} and \autoref{lem:fs-ray}; at odd order by the construction in the proof of \autoref{prop:odd-second}, with the solutions of the reduced recursion given in the proof of \autoref{thm:odd-nondil}, or by a $\sigma$-bump; for $\{1,3,5\}$ at order $6$ by the construction in the proof of \autoref{prop:trop-cert}; and otherwise by a $\sigma$-bump and \autoref{lem:trop-bumptangent}. None of these constructions involves the coefficients $c_j$, so \autoref{thm:tangent}(ii) applies. If $S$ is not primitive, let $\ell=\gcd(S\cup\{k\})$, and let $S'$ and $k'$ be as in \autoref{lem:unfold}; then $S'$ is primitive and palindromic, with $|S'|=|S|\ge3$. As in the proof of \autoref{lem:unfold}(ii), if $z$ is an integer solution of the min-plus recursion for $(k',S',\theta)$, then $x_n=z_{\lfloor n/\ell\rfloor}$ is one for $(k,S,\theta)$. So if $T^{\,p}=\id$, every such $x$ is $p$-periodic, and $z_{m+p}=x_{m\ell+p\ell}=x_{m\ell}=z_m$; that is, the min-plus map for $(k',S',\theta)$ has $p$-th power the identity, against the primitive case. \end{proof} Since $\Z^k\subset\R^k$, the min-plus map is not periodic on $\R^k$ either. Note that the corollary asserts only that $T$ is not periodic. Unlike the theorems of \citeauthor{CsornyeiLaczkovich2001} for the full support, it does not exhibit a single non-periodic orbit, since the window $w$ depends on $p$. The hypothesis $|S|\ge3$ cannot simply be dropped: with $\theta=1$ the min-plus maps for $S=\{1\}$ at order $2$ and $S=\{1,2\}$ at order $3$ are periodic, with periods $5$ and $8$ (\autoref{sec:small}). The corollary leaves the two-term supports $\{j,k-j\}$ open, since the proof of \autoref{thm:main} settles them with the linearisation. For $k=4$ and $S=\{1,3\}$ the tangent certificates (\autoref{def:trop-cert}) with $E=(-1,-1,-1,-1)$ and \begin{align*} \theta=1:&\quad q=11,\ V=(-1,-1,0,-1),\ W=(0,0,1,1),\ (w_t)=1,1,1,3,0,1,3,3,3,3,1,\\ \theta=0:&\quad q=66,\ V=(-1,-1,0,0),\ W=(4,0,0,0),\ (w_t)=1^63^51^63^51^63^61^53^61^53^61^53^5, \end{align*} ($1^6$ stands for six consecutive entries $1$) are valid along the $11$-periodic solution with window $E$, so, by the argument above, no power of the min-plus map for $(4,\{1,3\},\theta)$ is the identity, for either $\theta$. Whether this holds for every two-term support other than $\{m,2m\}$ at order $3m$ with $\theta=1$, where the map is periodic by unfolding the order-$3$ case, and which non-palindromic supports have a periodic min-plus map, I leave open. \section*{Acknowledgements} This proof was AI-generated with fairly limited input from the human author. The models used were Claude Opus 5.5 and Fable 5.1. \appendix \section{The finite range of the progression theorem} \label{app:lemmaA-finite} This appendix completes the proof of \autoref{thm:lemmaA}. It gives the certificate for the $127$ orders $92\le k\le2730$ with at least three odd prime factors, the only ones not covered by \autoref{prop:lemmaA-twoprime} or \autoref{prop:lemmaA-tail}, and proves the two bounds on Jacobsthal's function used in \autoref{sec:lemmaA-tail} for the orders above $2730$. The notation is that of \autoref{sec:lemmaA}. \subsection{The orders up to 2730 with three or more odd primes} By \autoref{lem:lemmaA-frame}(b), (c) and \autoref{lem:lemmaA-zero}, the normalised shortest vector of $\Lambda$ at an order $k\le2730$ gives a triple in $\mathcal V$ with $g\mid2k$ and $3l^4\le16k^2$: indeed $l^4\le16\cdot2730^2/3$ gives $l^2\le6304<6400$, so $l\le80$. Besides the chord table (C1) of \autoref{sec:lemmaA-tail}, the finite certificate has two more parts. \begin{enumerate} \item[(C2)] \emph{Jacobsthal values.} A list of $224$ pairs $(n,m)$ with $J(n)\le m$. Each is checked over one period: for every residue $y$ modulo $n$ some $0\le img$, where $\psi$ is the length of the chord witness in (C1); or \item[(ii)] for each of the $g^2$ pairs $0\le s,t1$, or an $m$ with $0J(n)g$, and \autoref{prop:lemmaA-table} shows that $(a,e)$ has a witness; the conditions on $n$ are those of \autoref{lem:lemmaA-line}. In case (ii), let $(s,t)$ be the class given by \autoref{lem:lemmaA-class}. Its two exclusions are ruled out by that lemma, so the certificate gives a unit $\nu$ showing that $(A,E)$ has a witness, and then so does $(a,e)$, by \autoref{lem:lemmaA-class}. \end{proof} \subsection{Elementary bounds on Jacobsthal's function} \label{app:lemmaA-jacbounds} This subsection proves \autoref{cor:lemmaA-jac}, the two inequalities for Jacobsthal's function used in \autoref{prop:lemmaA-tail}, by a union bound and a progression trick. \begin{lemma} \label{lem:lemmaA-jactools} \begin{enumerate} \item[(a)] Suppose every $m$ consecutive integers include at least $c$ that are prime to $N$, and $\mathcal T$ is a finite set of primes with $\sum_{p\in\mathcal T}\lceil m/p\rceil13$ dividing $n$. Then $B\Pi_r\le n$, and there is an $m$ with $J(n)\le m$ such that \begin{enumerate} \item[(i)] if $B$ is even, $178\,m^2\le10\max\bigl(B\Pi_r,\ B(\lfloor2730/B\rfloor+1)\bigr)$; \item[(ii)] $m\le8$, or $1000\,m<102\,B\Pi_r$. \end{enumerate} \end{lemma} The maximum in (i) is the better of two lower bounds for an order $k$ to which the lemma will be applied: $k\ge B\Pi_r$, and, as $k$ is a multiple of $B$ above $2730$, $k\ge B(\lfloor2730/B\rfloor+1)$. So (i) gives the first inequality of the tail condition, and (ii) gives $J(g)\le8$ or $J(g)<0.102\,g$, as needed for the band. \begin{proof} The $i$-th smallest prime above $13$ is $\varpi_i$, so the primes $p_1<\dots2$, $\omega\#=(\omega-1)\#$; for $\omega=2m+1$, the primes in $(m+1,2m+1]$ all divide $\binom{2m+1}{m}$, which is at most $4^m$ because it and $\binom{2m+1}{m+1}$ are equal and sum to at most $2^{2m+1}$, so $(2m+1)\#\le(m+1)\#\,4^m\le4^{m+1}4^m$. Then $r\ge \omega/2-1\ge31$, $\omega\le2r+2$, $\prod_{i=1}^r(\omega+i)\ge64^r$ and $B\le4^\omega\le16\cdot16^r$, so $178B(r+1)^2\le16^r\cdot2848(r+1)^2\le16^r\cdot10\cdot4^r=10\cdot64^r$, using $2848(r+1)^2\le10\cdot4^r$ for $r\ge8$ (true at $r=8$, and the right side grows faster). The second inequality is then immediate. \end{proof} \begin{corollary} \label{cor:lemmaA-jac} \begin{enumerate} \item[(a)] Every even $k>2730$ satisfies $178\,J(2k)^2\le10k$, that is, $17.8\,J(2k)^2\le k$. \item[(b)] Every $g\ge1$ satisfies $J(g)\le8$ or $1000\,J(g)<102\,g$. \end{enumerate} \end{corollary} \begin{proof} (a) Note $J(2k)=J(k)$. If $\omega(k)\le8$, apply \autoref{lem:lemmaA-pattern} to $n=k$. Then $B$ is even, and $k\ge B\Pi_r$; also $k$ is a multiple of $B$ exceeding $2730$, so $k\ge B(\lfloor2730/B\rfloor+1)$. So $178J(k)^2\le178m^2\le10k$. If $\omega(k)\ge9$, \autoref{lem:lemmaA-crude} gives $178J(k)^2\le178B^2(r+1)^2\le10BR\le10k$. (b) If $\omega(g)\le8$, \autoref{lem:lemmaA-pattern}(ii) gives $J(g)\le m\le8$ or $1000J(g)\le1000m<102B\Pi_r\le102g$. If $\omega(g)\ge9$, \autoref{lem:lemmaA-crude} gives $1000J(g)\le1000B(r+1)<102BR\le102g$. \end{proof} \section{Detailed case checks} \label{app:checks} This appendix contains two elementary case checks that complete proofs in the main text. \subsection{The case \texorpdfstring{$M=1$}{M=1} of the both-failing supports} \label{app:checks-bfone} This completes the proof of \autoref{lem:nao-bfone}, in the notation of that proof and with the description of $Q$ given at its start. At each index $i$ the table names two taps among $a$, $b$, $2a$, $a+b$ whose reads differ, both surviving. It lists them in twelve numbered rows, with the residue of the position each reads (not the position itself, as in the example of \autoref{sec:nao-reading}), a star marking a wrapped tap; reads follow from \eqref{eq:read-reads} and \eqref{eq:read-pins}. \begin{center}\small \begin{tabular}{rlll} & index $i$ & tap reading $1$ & tap reading $0$\\\hline & \multicolumn{3}{l}{\emph{$i$ even}}\\ (1) & $ia+b$, $i\ne2b$ & $a\to^{*} i-a-b\in(0,a)$, odd & $b\to^{*} i-2a\in(0,b)$\\ (6) & $i=2b$ & $a+b\to^{*} 2b-a$, odd & $b\to^{*} 2b-2a\in(0,b)$\\[2pt] & \multicolumn{3}{l}{\emph{$i$ odd}}\\ (7) & $ia+b$, $i\ne3a$ & $b\to^{*} i-2a\in(b-a,b)$, odd & $a\to^{*} i-a-b\in(0,a)$\\ (12) & $i=3a$ & $a+b\to^{*} 2a\in S$ & $a\to^{*} 2a-b\in(0,b)$ \end{tabular} \end{center} Positions not described as odd or as elements of $S$ are even, and every even position named lies in $(0,b)\cup(2a,k)$, so it is free and lies in $Q$. An element of $S$ other than $a$ reads $0$ unwrapped and $1$ wrapped. For the odd positions: among the reads of $1$, the unwrapped odd position is $3a\in Q$ and the wrapped ones ($i-a$, $i-a-b$, $2b-a$, $i-2a$) are not in $\{a,3a,b-a\}$; among the reads of $0$, the unwrapped odd positions ($i+a$, $i+2a$) are not in $\{a,3a,b-a\}$ and the wrapped one is $b-a\in Q$. These memberships are checked with $a0$, and letting $\eps\to0$ gives $G_0^{\,p}=\id$. \item \emph{Order three with $c_0=0$} (\autoref{thm:order3}). Instead of the algebraic-integer step, a root $\lambda$ of $\lambda^2-\tfrac32\lambda+1$ satisfies $\lambda^m=\alpha_m\lambda+\beta_m$ with rational $\alpha_m,\beta_m$ and $2^{m-1}\alpha_m$ an odd integer for $m\ge1$; so $\alpha_m\ne0$ and, as $\lambda$ is not real, $\lambda^m\ne1$. \item \emph{Small orders in \autoref{thm:twoterm}.} Step~2 of the proof (that $n_0\ge9$) is replaced by the same kind of expansion: with $\zeta^2-\eps\zeta+1=0$, $\zeta^r=P_r(\eps)\zeta+Q_r(\eps)$ for polynomials $P_r,Q_r$, and $\zeta^r=1$ would force $P_r(\eps)=0$, which is checked to be impossible for $1\le r\le8$ and $0<\eps\le\frac12$. \item \emph{Odd indices} (\autoref{lem:allodd-oddhalf}). Instead of the argument with the gaps between phases, the formal proof is local: if $H_\nu(u)\ne H_\nu(v)$, then at every odd index the four taps $u$, $k-u$, $v$, $k-v$, less the deleted one, already read both values, which is a case analysis on the residues $\nu i$, $\nu u$ and $\nu v$ modulo $2k$. \item \emph{The band} (\autoref{prop:lemmaA-band}). To stay in rational arithmetic, the incircle of $\Delta_1$ is replaced by a slightly smaller disc inside $\Delta_1$, of radius $0.207\,k$ about a rational point close to the incentre. With the same band half-width $0.102\,k$ its chords are longer than $0.36024\,k$ rather than $0.3604\,k$, and the bound $J(n)\,l<0.36021\,k$ obtained in the proof of \autoref{prop:lemmaA-tail} still suffices. \end{itemize} Every finite computation in the paper is carried out in exact integer arithmetic inside \textsc{Lean}'s kernel by the \texttt{decide} tactic, so no step of the proof relies on compiled code or on an external program. In some the kernel finds the required objects itself by search (or none are needed); in the others they were produced outside \textsc{Lean} and are imported as data, which the kernel only checks: \begin{center} \small \begin{tabular}{@{}>{\raggedright\arraybackslash}p{0.46\textwidth}% >{\raggedright\arraybackslash}p{0.46\textwidth}@{}} found by the kernel & imported as data and checked\\\hline units witnessing the triples of \autoref{lem:allodd-pf} outside $\mathcal F$, and in step~1 of the proof of \autoref{thm:allodd-e3all} outside $F_k$ (search over the units modulo $2n$ or $2k$) & the seventeen carriers of \autoref{tab:allodd-base}\\ the enumeration of lower halves in step~2 of that proof & the certificate of \autoref{prop:order6cert}\\ the ratios of $\mathcal F$ in \autoref{lem:allodd-nofail}, and the entries of $\mathcal F$ used at $k=120$ in \autoref{thm:allodd-e3all} & the list $\mathcal F$ and the sets $F_k$\\ the orders of \autoref{prop:lemmaA-twoprime} (a divisor test), and the per-order check (C3) for \autoref{thm:lemmaA} at the others, which looks up the pairs of (C2) and finds the units $\nu<100$ of alternative (ii) by search & the units satisfying (T) in step~3 of the proof of \autoref{thm:allodd-e3all}\\ the check $9\le\omega\le63$ in \autoref{lem:lemmaA-crude} & the chord table (C1), the Jacobsthal pairs (C2), and the table of \autoref{lem:lemmaA-pattern} \end{tabular} \end{center} The case tables of \autoref{app:checks} and the chains of \autoref{tab:lemmaA-chains} hold for all values of the parameters, and they are formalised as case analyses. \bibliographystyle{plainnat} \begin{thebibliography}{32} \providecommand{\natexlab}[1]{#1} \providecommand{\url}[1]{\texttt{#1}} \expandafter\ifx\csname urlstyle\endcsname\relax \providecommand{\doi}[1]{doi: #1}\else \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi \bibitem[Barbeau et~al.(1995)Barbeau, Gelbord, and Tanny]{BarbeauGelbordTanny1995} E.~J. Barbeau, Boaz Gelbord, and Stephen Tanny. \newblock Periodicities of solutions of the generalized {L}yness recursion. \newblock \emph{Journal of Difference Equations and Applications}, 1\penalty0 (3):\penalty0 291--306, 1995. \newblock \doi{10.1080/10236199508808028}. \bibitem[Bedford and Kim(2006)]{BedfordKim2006} Eric Bedford and Kyounghee Kim. \newblock Periodicities in linear fractional recurrences: degree growth of birational surface maps. \newblock \emph{Michigan Mathematical Journal}, 54\penalty0 (3):\penalty0 647--670, 2006. \newblock \doi{10.1307/mmj/1163789919}. \bibitem[Bedford and Kim(2011)]{BedfordKim2011} Eric Bedford and Kyounghee Kim. \newblock Linear fractional recurrences: periodicities and integrability. \newblock \emph{Annales de la Facult{\'e} des Sciences de Toulouse. Math{\'e}matiques. S{\'e}rie 6}, 20\penalty0 (S2):\penalty0 33--56, 2011. \newblock \doi{10.5802/afst.1304}. \bibitem[Bedford and Kim(2014)]{BedfordKim2014} Eric Bedford and Kyounghee Kim. \newblock Dynamics of (pseudo) automorphisms of 3-space: periodicity versus positive entropy. \newblock \emph{Publicacions Matem{\`a}tiques}, 58:\penalty0 65--119, 2014. \newblock \doi{10.5565/publmat_58114_04}. \bibitem[Bombieri and Gubler(2006)]{BombieriGubler2006} Enrico Bombieri and Walter Gubler. \newblock \emph{Heights in {D}iophantine Geometry}, volume~4 of \emph{New Mathematical Monographs}. \newblock Cambridge University Press, Cambridge, 2006. \newblock \doi{10.1017/CBO9780511542879}. \bibitem[Cima et~al.(2004)Cima, Gasull, and Ma{\~n}osas]{CimaGasullManosas2004} Anna Cima, Armengol Gasull, and Francesc Ma{\~n}osas. \newblock On periodic rational difference equations of order $k$. \newblock \emph{Journal of Difference Equations and Applications}, 10\penalty0 (6):\penalty0 549--559, 2004. \newblock \doi{10.1080/10236190410001667977}. \bibitem[Cima et~al.(2012)Cima, Gasull, and Ma{\~n}osas]{CimaGasullManosas2012} Anna Cima, Armengol Gasull, and Francesc Ma{\~n}osas. \newblock Global linearization of periodic difference equations. \newblock \emph{Discrete and Continuous Dynamical Systems}, 32\penalty0 (5):\penalty0 1575--1595, 2012. \newblock \doi{10.3934/dcds.2012.32.1575}. \bibitem[Cima et~al.(2016)Cima, Gasull, Ma{\~n}osa, and Ma{\~n}osas]{CimaGasullManosaManosas2016} Anna Cima, Armengol Gasull, V{\'\i}ctor Ma{\~n}osa, and Francesc Ma{\~n}osas. \newblock Different approaches to the global periodicity problem. \newblock In \emph{Difference Equations, Discrete Dynamical Systems and Applications}, volume 180 of \emph{Springer Proceedings in Mathematics \& Statistics}, pages 85--106. Springer, 2016. \newblock \doi{10.1007/978-3-662-52927-0_7}. \bibitem[Cima et~al.(2022)Cima, Gasull, Ma{\~n}osa, and Ma{\~n}osas]{CimaGasullManosaManosas2022} Anna Cima, Armengol Gasull, V{\'\i}ctor Ma{\~n}osa, and Francesc Ma{\~n}osas. \newblock Pointwise periodic maps with quantized first integrals. \newblock \emph{Communications in Nonlinear Science and Numerical Simulation}, 108:\penalty0 106150, 2022. \newblock \doi{10.1016/j.cnsns.2021.106150}. \bibitem[Cs{\"o}rnyei and Laczkovich(2001)]{CsornyeiLaczkovich2001} Marianna Cs{\"o}rnyei and Mikl{\'o}s Laczkovich. \newblock Some periodic and non-periodic recursions. \newblock \emph{Monatshefte f{\"u}r Mathematik}, 132\penalty0 (3):\penalty0 215--236, 2001. \newblock \doi{10.1007/s006050170042}. \bibitem[Fomin and Zelevinsky(2003)]{FominZelevinsky2003} Sergey Fomin and Andrei Zelevinsky. \newblock {$Y$}-systems and generalized associahedra. \newblock \emph{Annals of Mathematics}, 158\penalty0 (3):\penalty0 977--1018, 2003. \newblock \doi{10.4007/annals.2003.158.977}. \bibitem[Gasull(2021)]{Gasull2021} Armengol Gasull. \newblock Some open problems in low dimensional dynamical systems. \newblock \emph{SeMA Journal}, 78:\penalty0 233--269, 2021. \newblock \doi{10.1007/s40324-021-00244-3}. \newblock arXiv:2012.02524. \bibitem[Golomb and Callan(1992)]{GolombCallan1992} Michael Golomb and David Callan. \newblock Periodic recursive sequences: Problem {E3437} and solution. \newblock \emph{The American Mathematical Monthly}, 99\penalty0 (9):\penalty0 882--883, 1992. \newblock \doi{10.2307/2324138}. \bibitem[Graham et~al.(1989)Graham, Knuth, and Patashnik]{GrahamKnuthPatashnik1989} Ronald~L. Graham, Donald~E. Knuth, and Oren Patashnik. \newblock \emph{Concrete Mathematics: A Foundation for Computer Science}. \newblock Addison-Wesley, Reading, MA, 1989. \bibitem[Grove and Ladas(2005)]{GroveLadas2005} E.~A. Grove and G.~Ladas. \newblock \emph{Periodicities in Nonlinear Difference Equations}, volume~4 of \emph{Advances in Discrete Mathematics and Applications}. \newblock Chapman \& Hall/CRC, Boca Raton, FL, 2005. \newblock \doi{10.1201/9781420037722}. \bibitem[Inoue and Takenawa(2008)]{InoueTakenawa2008} Rei Inoue and Tomoyuki Takenawa. \newblock Tropical spectral curves and integrable cellular automata. \newblock \emph{International Mathematics Research Notices}, 2008:\penalty0 rnn019, 2008. \newblock \doi{10.1093/imrn/rnn019}. \bibitem[Inoue et~al.(2012)Inoue, Kuniba, and Takagi]{InoueKunibaTakagi2012} Rei Inoue, Atsuo Kuniba, and Taichiro Takagi. \newblock Integrable structure of box-ball systems: crystal, {B}ethe ansatz, ultradiscretization and tropical geometry. \newblock \emph{Journal of Physics A: Mathematical and Theoretical}, 45:\penalty0 073001, 2012. \newblock \doi{10.1088/1751-8113/45/7/073001}. \bibitem[Iwaniec(1978)]{Iwaniec1978} Henryk Iwaniec. \newblock On the problem of {J}acobsthal. \newblock \emph{Demonstratio Mathematica}, 11\penalty0 (1):\penalty0 225--231, 1978. \newblock \doi{10.1515/dema-1978-0121}. \bibitem[Jacobsthal(1960{\natexlab{a}})]{Jacobsthal1960a} Ernst Jacobsthal. \newblock {\"U}ber {S}equenzen ganzer {Z}ahlen, von denen keine zu $n$ teilerfremd ist. {I}. \newblock \emph{Det Kongelige Norske Videnskabers Selskabs Forhandlinger (Trondheim)}, 33:\penalty0 117--124, 1960{\natexlab{a}}. \bibitem[Jacobsthal(1960{\natexlab{b}})]{Jacobsthal1960b} Ernst Jacobsthal. \newblock {\"U}ber {S}equenzen ganzer {Z}ahlen, von denen keine zu $n$ teilerfremd ist. {II}. \newblock \emph{Det Kongelige Norske Videnskabers Selskabs Forhandlinger (Trondheim)}, 33:\penalty0 125--131, 1960{\natexlab{b}}. \bibitem[Jacobsthal(1960{\natexlab{c}})]{Jacobsthal1960c} Ernst Jacobsthal. \newblock {\"U}ber {S}equenzen ganzer {Z}ahlen, von denen keine zu $n$ teilerfremd ist. {III}. \newblock \emph{Det Kongelige Norske Videnskabers Selskabs Forhandlinger (Trondheim)}, 33:\penalty0 132--139, 1960{\natexlab{c}}. \bibitem[Koci{\'c} et~al.(1993)Koci{\'c}, Ladas, and Rodrigues]{KocicLadasRodrigues1993} V.~L. Koci{\'c}, G.~Ladas, and I.~W. Rodrigues. \newblock On rational recursive sequences. \newblock \emph{Journal of Mathematical Analysis and Applications}, 173:\penalty0 127--157, 1993. \newblock \doi{10.1006/jmaa.1993.1057}. \bibitem[Kronecker(1857)]{Kronecker1857} Leopold Kronecker. \newblock Zwei {S}{\"a}tze {\"u}ber {G}leichungen mit ganzzahligen {C}oefficienten. \newblock \emph{Journal f{\"u}r die reine und angewandte Mathematik}, 53:\penalty0 173--175, 1857. \newblock \doi{10.1515/crll.1857.53.173}. \bibitem[Kulenovi{\'c} and Ladas(2000)]{KulenovicLadas2000} M.~R.~S. Kulenovi{\'c} and G.~Ladas. \newblock Open problems and conjectures: On period two solutions of $x_{n+1}=(\alpha+\beta x_n+\gamma x_{n-1})/(a+bx_n+cx_{n-1})$. \newblock \emph{Journal of Difference Equations and Applications}, 6\penalty0 (5):\penalty0 641--646, 2000. \newblock \doi{10.1080/10236190008808249}. \bibitem[Kurshan and Gopinath(1974)]{KurshanGopinath1974} R.~P. Kurshan and B.~Gopinath. \newblock Recursively generated periodic sequences. \newblock \emph{Canadian Journal of Mathematics}, 26\penalty0 (6):\penalty0 1356--1371, 1974. \newblock \doi{10.4153/CJM-1974-129-6}. \bibitem[Linero~Bas and Nieves~Rold{\'a}n(2021)]{LineroBasNievesRoldan2021} Antonio Linero~Bas and Daniel Nieves~Rold{\'a}n. \newblock Periods of a max-type equation. \newblock \emph{Journal of Difference Equations and Applications}, 27\penalty0 (11):\penalty0 1608--1645, 2021. \newblock \doi{10.1080/10236198.2021.2000971}. \bibitem[Lyness(1942)]{Lyness1942} R.~C. Lyness. \newblock Cycles. \newblock \emph{The Mathematical Gazette}, 26\penalty0 (268):\penalty0 62, 1942. \newblock \doi{10.2307/3606036}. \newblock Note 1581. \bibitem[Lyness(1945)]{Lyness1945} R.~C. Lyness. \newblock Cycles. \newblock \emph{The Mathematical Gazette}, 29\penalty0 (287):\penalty0 231--233, 1945. \newblock \doi{10.2307/3609268}. \newblock Note 1847. \bibitem[Montgomery(1937)]{Montgomery1937} Deane Montgomery. \newblock Pointwise periodic homeomorphisms. \newblock \emph{American Journal of Mathematics}, 59\penalty0 (1):\penalty0 118--120, 1937. \newblock \doi{10.2307/2371565}. \bibitem[Nobe(2008)]{Nobe2008} Atsushi Nobe. \newblock Ultradiscrete {QRT} maps and tropical elliptic curves. \newblock \emph{Journal of Physics A: Mathematical and Theoretical}, 41:\penalty0 125205, 2008. \newblock \doi{10.1088/1751-8113/41/12/125205}. \bibitem[Rubi{\'o}-Masseg{\'u} and Ma{\~n}osa(2007)]{RubioMasseguManosa2007} Josep Rubi{\'o}-Masseg{\'u} and V{\'\i}ctor Ma{\~n}osa. \newblock Normal forms for rational difference equations with applications to the global periodicity problem. \newblock \emph{Journal of Mathematical Analysis and Applications}, 332\penalty0 (2):\penalty0 896--918, 2007. \newblock \doi{10.1016/j.jmaa.2006.10.061}. \bibitem[Tokihiro et~al.(1996)Tokihiro, Takahashi, Matsukidaira, and Satsuma]{TokihiroTTMS1996} Tetsuji Tokihiro, Daisuke Takahashi, Junta Matsukidaira, and Junkichi Satsuma. \newblock From soliton equations to integrable cellular automata through a limiting procedure. \newblock \emph{Physical Review Letters}, 76:\penalty0 3247--3250, 1996. \newblock \doi{10.1103/physrevlett.76.3247}. \end{thebibliography} \end{document}