# Learning Agility and Adaptive Legged Locomotion via Curricular Hindsight
Reinforcement Learning

Sicen Li, Yiming Pang, Panju Bai, Zhaojin Liu, Jiawei Li, Shihao Hu, Liquan
Wang, and Gang Wang* This work was supported in part by the National Natural
Science Foundation of Heilongjiang Province (Grant No.YQ2020E028).
(Corresponding author: Gang Wang.) Sicen Li, Yiming Pang, Panju Bai, Shihao
Hu, Zhaojin Liu, and Liquan Wang are with College of Mechanical and Electrical
Engineering, Harbin Engineering University, Harbin 150001, China: {ihuhuhu,
pangyiming, baipanju, jhjsb, liuzhaojin<EMAIL_ADDRESS>Jiawei Li
and Gang Wang are with College of Shipbuilding Engineering, Harbin Engineering
University, Harbin 150001, China: {ljw1996<EMAIL_ADDRESS>All
authors are with the Science and Technology on Underwater Vehicle Laboratory,
Harbin Engineering University, Harbin Engineering University, Harbin 150001,
China.

###### Abstract

Agile and adaptive maneuvers such as fall recovery, high-speed turning, and
sprinting in the wild are challenging for legged systems. We propose a
Curricular Hindsight Reinforcement Learning (CHRL) that learns an end-to-end
tracking controller that achieves powerful agility and adaptation for the
legged robot. The two key components are (I) a novel automatic curriculum
strategy on task difficulty and (ii) a Hindsight Experience Replay strategy
adapted to legged locomotion tasks. We demonstrated successful agile and
adaptive locomotion on a real quadruped robot that performed fall recovery
autonomously, coherent trotting, sustained outdoor speeds up to 3.45 m/s, and
tuning speeds up to 3.2 rad/s. This system produces adaptive behaviours
responding to changing situations and unexpected disturbances on natural
terrains like grass and dirt.

###### Index Terms:

Quadruped robot, reinforcement learning, curriculum learning, hindsight
experience replay

##  I Introduction

Legged systems can execute agile motions by leveraging their ability to reach
appropriate and disjoint support contacts, enabling outstanding mobility in
complex and unstructured environments[1]. This ability makes them a popular
choice for tasks such as inspection, monitoring, search, rescue, or
transporting goods in complex, unstructured environments[2].

However, until now, legged robots could not match the performance of animals
in traversing real-world terrains[3]. In nature, legged animals such as
cheetahs and hunting dogs can make small radius turns at high speed running or
recover quickly from a fall with little or no slowing down while chasing prey.
Animals naturally learn to process a wide range of sensory information and
respond adaptively in unexpected situations, even when exteroception is
completely limited. This ability requires motion controllers capable of
recovering from unexpected perturbations, adapting to system and environmental
dynamics changes, and executing safe and reliable motion relying solely on
proprioception.

Endowing legged robots with this ability is a grand challenge in robotics.
Conventional control theories often must be revised to deal with these
problems effectively. As a promising alternative, model-free deep
reinforcement learning (RL) algorithms autonomously solve complex and high-
dimensional legged locomotion problems and do not assume prior knowledge of
environmental dynamics.

Under the privileged learning framework, previous work has solved motion tasks
such as fast running[4], locomotion over uneven terrain[5], and mountain
climbing[3]. However, existing motion controllers can still not respond
appropriately and adaptively when various accidents lead to motion
interruptions, such as collisions with obstacles or falls caused by stepping
into potholes.

In this paper, our goal is to construct a system that can traverse terrains
agility and adaptively at an extensive range of commands. Akin to prior work,
we found that the policy can be successfully learned when the robot runs with
a narrow range of commands and external disturbances. However, when increasing
the range of commands or disturbances, the policy propensity to converge to
inferior solutions or even diverge as the reward is sparse. The training
process can progressively address complex tasks by implementing curriculum
learning, but manual curriculum design may also fail due to the difficulty of
evaluating learning progress and task difficulty. This paper presents
Curricular Hindsight Reinforcement Learning (CHRL) to solve this problem by
introducing a novel automatic curriculum strategy to automatically assess the
learning progress of the policy and control task difficulty. CHRL periodically
evaluates the policy’s performance and automatically adjusts the curriculum
parameters to ramp up task difficulty, including command ranges, reward
coefficients, and environment difficulty.

However, adjusting the environment parameters and command ranges destroys the
consistency of the state distribution between the environment and the replay
buffer, which is disastrous for off-policy RL. This work solved this problem
by adapting Hindsight Experience Replay (HER)[6] to quadrupedal locomotion
tasks to match the existing replay buffer to the current curriculum. Presented
HER modifies the commands of past experiences and recalculates rewards,
additionally utilizing past experiences, thus increasing the learning
efficiency. The proposed policy yields significant performance improvements in
learning agility and adaptive high-speed locomotion.

When zero-shot deployed in the real world on uneven outdoor terrain covered
with grass, our learned policy sustained a top forward velocity of 3.45 m/s
and spinning angular velocity of 3.2 rad/s. The policy also shows strong
robustness and adaptability in unstructured environments. When the robot hits
an obstacle or steps on an unseen pit and falls, the learned policy shows the
capability of failure-resilient running and critical recovery within one
second. The robot spontaneously resisted unpredictable external disturbances
in indoor tests and demonstrated unique motor skills. These results are
reported qualitatively, and corresponding videos highlight the adaptive
responses that emerge from end-to-end learning.

The main contributions of this paper include:

  * •

A novel automatic curriculum strategy enables the discovery of behaviors that
are challenging to learn directly using reinforcement learning.

  * •

We adapt Hindsight Experience Replay to legged locomotion tasks, allowing
sample efficient learning and improving performance.

  * •

The learned controller can be deployed directly to the real world and performs
agility and adaptively in various environments.

##  II Related Works

Model-based Control. Dynamic locomotion over unknown and challenging terrain
requires careful motion planning and precise motion and force control[7]. The
primary approach in the legged locomotion community uses model-based
mathematical optimization to solve these problems, such as Model-Predictive
Control (MPC)[8], Quadratic Programming[9], and Trajectory Optimisation[10].
The possible contact configurations in legged locomotion greatly expand the
search space of trajectories, making the computational cost of optimal
planning much higher and making it challenging to meet real-time
requirements[11]. Modular controller design breaks the control problem into
smaller submodules, each based on template dynamics or heuristics. However,
these methods are difficult to apply to rough terrain. Combining all models
and constraints (whole robot model, contact model, environmental constraints)
for optimization through nonlinear MPC[12] and whole-body optimization[13] can
alleviate this problem but is computationally expensive.

Reinforcement learning for quadrupedal locomotion. Instead of tedious manual
controller engineering, the Reinforcement learning (RL) technique
automatically synthesizes a controller for the desired task by optimizing the
controller’s objective function[14]. ANYmal[15, 16] is capable of energy-
efficiently following high-level body velocity commands with a max speed of
1.5 m/s, and recovering from falling even in complex configurations. Extending
this approach, [3] developed a controller to integrate exteroceptive and
proprioceptive perception for legged locomotion, and completed an hour-long
hike in the Alps in the time recommended for human hikers. However, the
mechanical design of the ANYmal robot is thought to limit it from running at
higher speeds. [4] present an end-to-end learned controller that achieves
record agility for the MIT Mini Cheetah, sustaining speeds up to 3.9 m/s on
flat ground and 3.4 m/s on grassland. [17] demonstrated high-speed locomotion
capabilities on deformable terrains. The robot could run on soft beach sand at
3.03 m/s, although the feet were completely buried in the sand during the
stance phase. Compared to previous work, our proposed controller not only
realizes high-speed and agile motion on uneven terrains, but also can
adaptively handle unexpected events and external disturbances.

Curriculum learning. Prior works have shown that a curriculum on environments
can significantly improve learning performance and efficiency using
reinforcement learning. [18] used a fixed-schedule curriculum on forward
linear velocity only. A Grid Adaptive Curriculum Update Rule is proposed [4]
to track a more extensive range of velocities. [3, 19] applied a curriculum on
terrains to learn highly robust walking controllers on non-flat ground. [20]
utilized a game-inspired curriculum to ensure progressive locomotion policy
learning over rugged terrains. Compared to previous work, our approach adjusts
command, reward coefficients, and environment difficulty in stages, allowing
for finer control of curriculum difficulty. The combination of curriculum
learning and HER also further enhances learning efficiency.

Hindsight Experience Replay. Hindsight Experience Replay (HER) has paved a
promising path toward increasing the efficiency of goal-conditioned tasks with
sparse rewards[6]. Several variants have been proposed to enhance HER, such as
curriculum learning to maximize the diversity of the achieved goals[21],
providing demonstrations[22], generating more valuable desired goals[23], and
curiosity-driven exploration[24]. Legged locomotion tasks can be viewed as a
particular variant of goal-conditioned tasks due to the presence of control
commands. This work adapts HER to legged locomotion tasks and proves its
effectiveness.

##  III Method

Our goal is to learn a policy that takes sensory data and velocity commands as
input and gives as output joint desired positions. The command
$\mathbf{c}^{cmd}_{t}$ includes the linear velocity $\mathbf{v}^{cmd}_{t}$ and
its yaw direction $\mathbf{d}^{cmd}_{t}$.

The policy is trained in simulation and then performs zero-shot sim-to-real
deployment. The controller is trained via privileged learning, which consists
of two stages:

First, a teacher policy $\pi_{\theta}^{teacher}$ with parameters $\theta$ is
trained via reinforcement learning with full access to privileged information
that includes the ground-truth state of the environment. Proposed method
Curricular Hindsight Reinforcement Learning (CHRL) works in this stage and
improves the performance of the teacher policy. Second, a student policy
$\pi_{\phi}^{student}$ is trained via imitation learning to predict the
teacher’s optimal action given only partial and noisy observations of the
environment. Then, the student policy is deployed on the robot without any
fine-tuning.

###  III-A Training environment

We use pybullet[25] as our simulator to build the training environment. A
procedural terrain generation system is developed to generate diverse sets of
trajectories. Four parallel agents collect five million simulated time steps
for policy training, which spends less than 6 hours of wall-clock time using a
single NVIDIA RTX 3090 GPU.

###  III-B Hardware

The robot used in this work stands 35 cm tall and weighs 15 kg. The robot
boasts 18 degrees of freedom (DoFs) with 12 actuated joints, each capable of
delivering a maximum torque of 33.5 Nm and six generalized coordinates for the
floating base. Our neural network controller runs at 66 Hz on an onboard
NVIDIA Jetson AGX Orin computer. The robot is equipped with an Inertial
Measurement Unit (IMU) and joint encoders.

###  III-C Control Architecture

Action space. The action $\mathbf{a}_{t}$ is a 12-dimensional desired joint
position vector. A PD controller is used to calculate torque
$\boldsymbol{\tau}=Kp(\hat{\mathbf{q}}-\mathbf{q})+Kd(\hat{\dot{\mathbf{q}}}-\dot{\mathbf{q}})$,
$Kp$ and $Kd$ are manually specified gains, which are set to 27.5 and 0.5
respectively. The target joint velocities $\hat{\dot{\mathbf{q}}}$ are set to
0.

Student Observation Space. The robot’s joint encoders provide joint angles
$\mathbf{q}_{t}\in\mathbb{R}^{12}$ and velocities
$\dot{\mathbf{q}}_{t}\in\mathbb{R}^{12}$.
$\mathbf{g}_{t}^{\text{ori}}\in\mathbb{R}^{3}$ and
$\omega_{t}^{\text{ori}}\in\mathbb{R}^{3}$ denote the orientation and angular
velocities measured using the IMU. $\pi_{\phi}^{student}$ takes as input a
history of previous observations and actions denoted by $\mathbf{o}_{t-H:t}$
where
$\mathbf{o}_{t}=\left[\mathbf{q}_{t},\dot{\mathbf{q}}_{t},\mathbf{g}_{t}^{\text{ori}},\omega_{t}^{\text{ori}},\mathbf{a}_{t-1}\right]$.
The input to $\pi_{\phi}^{student}$ is
$\mathbf{x}_{t}=(\mathbf{o}_{t-H:t},\mathbf{c}_{t})$, where $\mathbf{c}_{t}$
is specified by a human operator through remote control during deployment,
$H=100$.

Teacher Observation Space. The teacher observation is defined as
$\mathbf{s}_{t}=(\mathbf{o}_{t-H:t},\mathbf{c}_{t},\mathbf{p}_{t-H:t})$, where
$H=4$. $\mathbf{p}_{t}$ is the privileged state which contains the body
velocity $\mathbf{v}_{t}\in\mathbb{R}^{3}$, the binary foot contact indicator
vector $\mathbf{f}^{t}\in\mathbb{R}^{4}$, the relative position in the world
frame $\mathbf{p}_{t}\in\mathbb{R}^{3}$, friction coefficient of feet, and
payload mass.

Reward Function. The reward function encourages the agent to move forward and
penalizes it for jerky and inefficient motions. We denote joint torques as
$\boldsymbol{\tau}_{t}\in\mathbb{R}^{12}$, the acceleration of the base in the
base frame of the robot as $\ddot{a}_{t}\in\mathbb{R}^{3}$, the velocity of
the feet as $\mathbf{v}_{t}^{f}\in\mathbb{R}^{4}$, and the total mechanical
power of the robot as $\mathbb{W}_{t}$. The details of the reward function:

  * •

Linear Velocity:
$\exp\left\\{-0.5\left(\mathbf{v}_{t}^{cmd}-\mathbf{v}^{x}_{t}\right)^{2}\right\\}$

  * •

Linear Velocity Penalties: $-0.4\mathbf{v}^{y}_{t}-0.4\mathbf{v}^{z}_{t}$

  * •

Orientation Tracking:
$\exp\left\\{-0.5\left(\mathbf{d}_{t}^{cmd}-\mathbf{g}_{t}^{\mathrm{ori}}\right)^{2}\right\\}$

  * •

Height Constraint:
$-\lvert\mathbf{p}^{z}_{t}-\mathbf{p}^{\mathrm{target}}_{t}\rvert$

  * •

Angle Velocity Penalties: $-\left\|\omega_{t}^{\text{ori}}\right\|^{2}$

  * •

Self-collision Penalties: $-\mathbf{1}_{\mathrm{selfcollision}}$

  * •

Joint Torque Penalties: $-\left\|\boldsymbol{\tau}_{t}\right\|^{2}$

  * •

Base Acceleration Penalties: $-\left\|\ddot{a}_{t}\right\|^{2}$

  * •

Energy: $-\mathbb{W}_{t}$

  * •

Foot Slip:
$-\left\|\operatorname{diag}\left(\mathbf{f}^{t}\right)\cdot\mathbf{v}_{t}^{f}\right\|^{2}$

The reward at time $t$ is defined as the sum of the quantities with the
scaling factor of each term being 3.0, 1.0, 3.0, 10, 0.21, 2.0, 0.018, 0.1,
0.012, and 0.3.

###  III-D Policy Optimization

Teacher Policy. The teacher policy $\pi_{\theta}^{teacher}$ is modeled as an
MLP, which consists of two MLP components: a state encoder $g_{\theta_{e}}$
and the main network $\pi_{\theta_{m}}$, such that
$\mathbf{a}_{t}=\pi_{\theta_{m}}\left(\mathbf{z}_{t}\right)$ where
$\mathbf{z}_{t}=g_{\theta_{e}}\left(\mathbf{s}_{t}\right)$ is a latent
representation. Each module is parameterized as a neural network with $256$
hidden nodes respectively and rectified linear units (ReLU)[26] between each
layer. We optimize the teacher parameters together using REDQ[27].

Student Policy. We use the same training environment as for the teacher
policy, but add additional noise to the student observation
$\mathbf{o}_{t}^{noise}=n(\mathbf{o}_{t})$ where $n(\mathbf{o}_{t})$ is a
Gaussian noise model applied to the observation. The student policy uses a
temporal convolutional network (TCN) [28] encoder $g_{\phi_{e}}$ to solve the
Partially Observable Markov Decision Process (POMDP). The student action
$\hat{\mathbf{a}}_{t}=\pi_{\phi_{m}}(\hat{\mathbf{z}}_{t})$ where
$\hat{\mathbf{z}}_{t}=g_{\phi_{e}}\left(\mathbf{o}_{t}^{noise}\right)$. The
student policy is trained via supervised learning. The loss function is
defined as

$\displaystyle\mathcal{L}=(\hat{\mathbf{a}}_{t}-\mathbf{a}_{t})^{2}+(\hat{\mathbf{z}}_{t}-\mathbf{z}_{t})^{2}.$
(1)

We employ the dataset aggregation strategy (DAgger)[29]. Training data are
generated by rolling out trajectories according to the student policy. The
weights of all networks are initialized with Kaiming Uniform
Initialization[30], and the biases are zero-initialized. All parameters are
updated by the Adam optimizer [31] with a fixed learning rate $3\times
10^{-4}$.

###  III-E Domain Randomization

Domain randomization encourages the policy to learn a single behavior that
works across all the randomized parameters to cross the sim-to-real gap. We
apply external force and torque to the robot’s body, introduce slippage by
setting the friction coefficients of the feet to a low value, and randomize
the robot’s dynamics parameters[32, 3]. Before each training episode, we
randomly select a set of physical parameters (Table I) to initiate the
simulation.

TABLE I: Ranges of the randomized parameters. Term | Min | Max | Unit
---|---|---|---
Contact friction | 0.4 | 1.25 | -
Payload mass | -1.0 | 5.0 | kg
Robot mass bias | 85% | 115% | -
Motor friction | 0 | 0.05 | Nm
Control frequency | 60 | 70 | Hz
Latency | 0 | 40 | ms
IMU bias | -0.05 | 0.05 | rad
IMU noise (std) | 0 | 0.05 | rad
Motor encoder bias | -0.08 | 0.08 | rad
External disturbance force | 0 | 15 | N
External disturbance torque | 0 | 5 | Nm
Gravity direction shift | 0 | 15 | degree

###  III-F Automatic Curriculum Strategy

Similar to previous work, our approach implements a training curriculum that
progressively modifies the distribution of environmental parameters, thus
enabling policies to improve motor skills and continuously adapt to new
environments.

Some works use a curriculum where the commands are updated on a fixed schedule
$\mathbb{C}^{k}$, as a function of the timing variable $k$. The schedule
$\mathbb{C}^{k}$ consists of two parts, the distribution $p_{x}^{k}$ of the
random variable $x$ (such as domain randomization parameters and commands) and
$r_{c}^{k}$ for the curriculum coefficient $c$ (such as reward factors).

The update rule $f$ takes the form $\mathbb{C}^{k+1}\longleftarrow
f(\mathbb{C}^{k})$. However, a fixed schedule requires manual tuning. If the
environment, rewards, or learning settings are modified, the schedule will
likely need to be re-turned, which will be costly in terms of time. Rather
than advancing the curriculum on a fixed schedule, we automatically update the
curriculum using a command-based rule.

Unlike previous works, our approach is not limited to the use of commands or
terrain but can take advantage of more environmental parameters, such as
reward coefficients and domain randomization parameters, to control the task’s
difficulty at a finer granularity. Table II shows the parameters used in our
experiences.

TABLE II: Range of curriculum parameters. | Start | End | Unit
---|---|---|---
Reward factor |  |  |
| Angle Velocity | 0 | 0.21 | -
| Joint Torque Penalties | 0 | 0.018 | -
| Base Acceleration Penalties | 0 | 0.1 | -
| Energy | 0 | 0.012 | -
| Foot Slip | 0 | 0.3 | -
Domain Randomization |  |  |
| Contact friction | $[1.25,1.25]$ | $[0.4,1.25]$ | -
| Payload mass | $[-1.0,-1.0]$ | $[-1.0,5.0]$ | kg
| External disturbance force | $[0,0]$ | $[0,15]$ | N
| External disturbance torque | $[0,0]$ | $[0,5]$ | Nm
| Gravity direction shift | $[0,0]$ | $[0,15]$ | degree
Terrians |  |  |
| Height fields range | $[0,0]$ | $[-2.5,2.5]$ | cm
Commands |  |  |
| linear velocities | $[0,0.8]$ | $[0,3.5]$ | m/s
| Direction of velocities | $[-0.5,0.5]$ | $[-\pi,\pi]$ | rad

In this work, we apply a tabular Curriculum Update Rule. First, we manually
set the number of curriculums $N$ to uniformly split the curriculum parameters
(Table II) from start to end into $p_{x}^{1}\dots p_{x}^{N}$ and
$r_{c}^{1}\dots r_{c}^{N}$. At episode $k$, the curriculum parameters for the
agent and environment are sampled from the joint distribution $p_{x}^{n}$, and
the reward factor is replaced with $r_{c}^{n}$. If the agent succeeds in this
region of the curriculum space, we would like to increase the difficulty by
updating the tabular curriculum from $p_{x}^{n}$ and $r_{c}^{n}$ to
$p_{x}^{n+1}$ and $r_{c}^{n+1}$:

$\displaystyle
p_{x}^{n},r_{c}^{n}\leftarrow\left\\{\begin{array}[]{ll}p_{x}^{n+1},r_{c}^{n+1}&\epsilon_{k}\left[\mathbf{v}^{\mathrm{cmd}}\right]<\epsilon_{0}\text{
and }\epsilon_{k}\left[\mathbf{d}^{\mathrm{cmd}}\right]<\epsilon_{1}\\\
p_{x}^{n},r_{c}^{n}&\text{ otherwise }\end{array}\right.$ (2)

where

$\displaystyle\epsilon_{k}\left[\mathbf{v}^{\mathrm{cmd}}\right]=\mathbb{E}_{\mathbf{v}_{t}^{\mathrm{cmd}},\boldsymbol{d}_{t}^{\mathrm{cmd}}}\sqrt{\mathbb{E}_{t}\left(\mathbf{v}_{t}^{\mathrm{cmd}}-\mathbf{v}_{t}^{x}\right)^{2}},$
(3)
$\displaystyle\epsilon_{k}\left[\mathbf{d}^{\mathrm{cmd}}\right]=\mathbb{E}_{\mathbf{v}_{t}^{\mathrm{cmd}},\boldsymbol{d}_{t}^{\mathrm{cmd}}}\sqrt{\mathbb{E}_{t}\left(\mathbf{d}_{t}^{\mathrm{cmd}}-\mathbf{g}_{t}^{\mathrm{ori}}\right)^{2}},$

$\mathbf{v}_{t}^{\mathrm{cmd}}$ and $\mathbf{d}_{t}^{\mathrm{cmd}}$ are the
linear velocity of the robot and its yaw direction measured at time $t$. The
average tracking error $\epsilon_{k}\left[\mathbf{v}^{\mathrm{cmd}}\right]$
and $\epsilon_{k}\left[\mathbf{d}^{\mathrm{cmd}}\right]$ over trials with the
current policy is defined as the main evaluation metric.

Measuring both of these metrics individually does not effectively reflect the
performance of the controller, so we need a performance metric that measures
both commands. We construct a composite metric that captures the diversity of
commands that the controller can execute within a certain maximum error
tolerance:

$\displaystyle\epsilon_{k}\left[\mathbf{v}^{\mathrm{cmd}}\right]<\epsilon_{0}\text{
and }\epsilon_{k}\left[\mathbf{d}^{\mathrm{cmd}}\right]<\epsilon_{1}$ (4)

The proposed automatic Curriculum strategy cyclical evaluates the learned
policy and automatically controls curriculum difficulty based on evaluation
results. The evaluation procedure will be initiated for every 100,000 samples
collected by the agent. Ten evaluation processes were run in parallel, each
lasting 10 seconds and randomly sampling new commands every 2 seconds. In all
experiences, we set $\epsilon_{0}=0.15$, $\epsilon_{1}=0.25$, and the number
of curriculums $N=10$.

Figure 1: Command tracking test results in simulation.

###  III-G Hindsight Experience Replay for Legged Locomotion

Algorithm 1 Curricular Hindsight Reinforcement Learning

1:Initialize an off-policy RL algorithm $\mathbb{A}$, a reward function $r$,
replay buffer $\mathcal{B}$, an curriculm schedule $\mathbb{C}$, training
environment $\mathbb{E}$.

2:for each iteration do

3: if $\mathbb{C}$ need update then

4: Evaluate and get $\epsilon_{k}\left[\mathbf{v}^{\mathrm{cmd}}\right]\text{
and }\epsilon_{k}\left[\mathbf{d}^{\mathrm{cmd}}\right]$ (3)

5: Update $\mathbb{C}$ according to rule (2)

6: Update parameters of environment $\mathbb{E}$ with $\mathbb{C}$

7: Get a state $\mathbf{s}_{t}$ from $\mathbb{E}$ and sample a command
$\mathbf{c}_{t}^{cmd}$

8: Execute an action
$\mathbf{a}_{t}\sim\pi_{\theta}^{teacher}\left(\cdot\mid\mathbf{s}_{t},\mathbf{c}_{t}^{cmd}\right)$

9: Observe reward $r_{t}$, new state $\mathbf{s}_{t+1}$ and robot state
$\mathbf{s}^{robot}_{t+1}$ (5)

10: // Storing phase

11: Store transition tuple:

12:
$\mathcal{B}\leftarrow\mathcal{B}\cup\left(\mathbf{s}_{t},\mathbf{a}_{t},r_{t},\mathbf{s}_{t+1},\mathbf{c}_{t}^{cmd},\mathbf{s}^{robot}_{t+1}\right)$

13: // training phase

14: Sample random minibatch $B$ from $\mathcal{B}$:

15:
$\\{\mathbf{s}_{j},\mathbf{a}_{j},r_{j},\mathbf{s}_{j+1},\mathbf{c}_{j}^{cmd},\mathbf{s}^{robot}_{j+1}\\}_{j=1}^{B}$

16: Resample command
$\mathbf{c}_{j}^{cmd}\longleftarrow\mathbf{c}_{new}^{cmd}$(6)

17: Recalculate $r_{j}$ with $c_{j}^{cmd}$ and $\mathbb{C}$

18: Perform one step of optimization using $\mathbb{A}$ and minibatch $B$

Hindsight Experience Replay (HER)[6] allows the algorithm to reuse existing
samples and can be combined with any off-policy RL algorithm. However, the
original HER algorithm is only suitable for some goal-conditioned tasks with
sparse and binary rewards. We have made some improvements to HER to
accommodate legged locomotion tasks.

Firstly, we sample a new goal for each transition during the training phase
instead of choosing a different goal for a trajectory during the storing
phase. Second, due to the need to recalculate rewards, more information about
the state of the robot
($\mathbb{W},\ddot{a},\omega^{\text{ori}},\tau,\mathbf{f},\mathbf{v},\mathbf{g}^{\mathrm{ori}}$)
is added in each transition. Then the transition $\mathbf{T}_{t}$ transition
becomes

$\displaystyle\mathbf{T}_{t}=\left(\mathbf{s}_{t},\mathbf{a}_{t},r_{t},\mathbf{s}_{t+1},\mathbf{c}_{t}^{cmd},\mathbf{s}^{robot}_{t+1}\right),$
(5)
$\displaystyle\mathbf{s}^{robot}_{t+1}\doteq\\{\mathbb{W}_{t+1},\ddot{a}_{t+1},\omega_{t+1}^{\text{ori}},\tau_{t+1},\mathbf{f}^{t+1},\mathbf{v}_{t+1},\mathbf{g}_{t+1}^{\mathrm{ori}}\\}$

Third, the original HER samples the goal achieved in the episode’s final
state. This is inefficient as policies for similar commands in locomotion
tasks tend to be similar. For a transition with command $\mathbf{c}_{t}^{cmd}$
consisted with the linear velocity $\mathbf{v}^{cmd}_{t}$ and its yaw
direction $\mathbf{d}^{cmd}_{t}$. We sample new command
$\mathbf{c}_{new}^{cmd}$ by adding neighboring regions to the sampling
distribution:

$\displaystyle\mathbf{c}_{new}^{cmd}\doteq\\{\mathbf{v}^{cmd}_{new},\mathbf{d}^{cmd}_{new}\\},$
(6)
$\displaystyle\mathbf{v}^{cmd}_{new}\sim\mathcal{U}[\mathbf{v}^{cmd}_{t}-0.3,\mathbf{v}^{cmd}_{t}+0.3],$
$\displaystyle\mathbf{d}^{cmd}_{new}\sim\mathcal{U}[\mathbf{d}^{cmd}_{t}-0.5,\mathbf{d}^{cmd}_{t}+0.5].$

All new commands sampled will be limited to the range of the current
curriculum. Then $r_{t}$ is recalculated with $\mathbf{s}^{robot}_{t+1}$
according to Section III-C.

This approach may be seen as a form of data augmentation as samples generated
by the policy of a specific command are shared within neighboring policies.
Combined with the automatic curriculum strategy in Section III-F, we present
Curricular Hindsight Reinforcement Learning (CHRL). The pseudocode for CHRL is
shown in Algorithm 1.

##  IV Results

###  IV-A Command Tracking Test

Figure 2: Real Robot Deployment Experiments. (a) Running on grassland. (b)
Walking on wet dirt ground. (c) Indoor walking through different ground
conditions.

Firstly, the control performance was evaluated in forward running under random
commands in simulation. In our experiments, we resampled commands and sent
them to the robot with a probability of 1/150 (every 2.25 seconds on average)
and resampled environmental variables with the same probability. Fig. 1 shows
the command tracking accuracy of the policy in the simulation.

The robot can move steadily and well in the desired direction in rough
terrain. Even if the velocity command changes during direction correction, the
controller can track both commands well. Note that the observed velocity
oscillation around the commanded velocity is a well-known phenomenon in legged
systems, including humans [33]. Regarding the average speed, the learned
policy has an error of less than 5% on the simulated robot.

We also performed experiences with real robots, including speed tracking tests
at 0.8 m/s indoors and a maximum of 3.5 m/s outdoors. The outdoor terrain
presented multiple challenges not present in indoor running, including
variations in ground height, friction, and terrain deformation. With these
variations, the robot must actuate its joints differently to achieve high
velocities that are different from those achieved on flat, rigid terrain with
high friction, such as a treadmill or paved road. We estimated the robot’s
locomotion speed by measuring the time it took to pass through a 5-meter-long
section of the road and performed multiple sets of repetitive tests. In the
indoor 0.8 m/s speed test, we recorded a 5 m walking time of 6.17 s, with an
average speed of 0.81 m/s. In contrast, we recorded an outdoor 5-meter sprint
time of 1.45 seconds with an average speed of 3.45 m/s. The results show that
the robot can track speed commands consistently and accurately in unknown
scenarios, both indoors and outdoors.

As shown in Fig. 2, we evaluated the yaw tracking control of the controller in
an outdoor grass environment. In the test, the robot’s desired direction
command and velocity command were randomly sent by the human operator. Our
experiments observed a maximum yaw speed of 3.2 rad/s for the robot, followed
by a safe stop. Even with continuous slewing motion at larger velocity
commands (3 m/s), the robot remained stable while turning, demonstrating the
submissive interactions and robustness learned by the agent.

The robot could track commands robustly in different ground conditions with
different hardness, friction, and obstacles (Fig. 2). The learned motor skills
were stable across the different ground conditions, and the robot continued to
trot steadily in all three conditions. The trained policy exhibited compliant
interaction behaviors to handle physical interactions and impacts. In testing,
when a large foot slip occurred, the robot could recover quickly, even running
near maximum speed. If the command was suddenly set to zero during operation,
the robot assumed a stable posture and quickly stopped moving.

###  IV-B Fall Recovery and Response to Unexpected Disturbances

Figure 3: Indoor walking with unexpected disturbance. The robot was suddenly
kicked when it was walking indoors, causing it to lose its balance. The
controller controlled the legs to support the body and restore balance in one
second. Figure 4: Outdoor running accident. The robot ran on grassland with
command 3m/s when it stepped on an unknown deep pit, causing it to trip and
fall. The controller utilized forward inertia to roll the body and control the
legs in an impact-resistant stance to protect the robot, followed by a quick
return to running. Figure 5: Outdoor fall recovery test. In the test, we
deliberately controlled the robot to hit a tree on a dirt floor, and due to
the tree’s obstruction, the robot could not move forward and fell. The robot
actively contacted the ground with its legs to support its body and held it
upright.

Due to the uncertainties in unforeseen situations, locomotion failures are
likely to occur. We illustrate these challenges in robotic locomotion using
field tests (Fig. 4 and 5) and adaptive behaviors that are robust to
uncertainty (Fig. 3).

During the outdoor tests, we found that the robot also experienced many
unexpected accidents, which resulted in unintended contact of the robot’s body
with the environment. In the indoor tests, we actively applied an external
disturbance to the robot during its walking to destabilize its movement and
observe its reaction after losing balance. Typically, robots fall within a
second of losing their balance, and the window of time to prevent a fall is
about 0.2 - 0.5 seconds. The proposed controller is observed to have different
adaptive behaviors for the above unexpected scenarios, which generate dynamic
locomotions and complex leg coordination for immediate recovery from failures.

In these unexpected scenarios, our robots autonomously coordinate different
locomotion patterns to mitigate disturbances and prevent or recover from
failures without human assistance. These behaviors are extremely similar to
the behavior of biological systems (such as cats, dogs, and humans), which
shows higher versatility and intelligence: the ability to deal with constantly
changing and complex situations.

We classified learned response behaviors into three strategies:

  * •

Natural rolling using semi-passive motion (Fig. 4). Natural rolling is the
behavior of a robot that uses its inertia and gravity to tumble.

  * •

Active righting and tumbling (Fig. 5). Active righting is a policy in which
the robot actively uses its legs and elbows to propel itself and generate
momentum to flip into a prone position.

  * •

Stepping. Fig. 3 shows an example of stepping, where coordination and
switching of the support legs are required to regain balance in the event of a
loss of stability of the current motion due to an external disturbance. This
multi-touch switching occurs naturally using a learning-based policy.

Compared to a manually designed fall recovery controller with a fixed pattern,
our learned controller can recover from various fall situations by responding
to dynamic changes using online feedback. In contrast, a manual controller can
only cope with a narrow range of situations.

###  IV-C Analysis of Skill Adaptation

Figure 6: Two-dimensional t-SNE embedding of the representations in the last
hidden layer of the student networks. (a) Embedding under different commands.
(b) Embedding under different robot payloads (kg) and ground friction.

We analyzed the features learned by the policies separately using
t-distributed Stochastic Neighbour Embedding (t-SNE), thus investigating how
skills are adapted and distributed in the network. The t-SNE algorithm is a
dimensionality reduction technique used to embed high-dimensional data into a
low-dimensional space and to visualize it. Similar features in the output of
the student network will appear with high probability in the same neighborhood
of the clustered points (Fig. 6) and vice versa.

A two-dimensional projection of the student network features by t-SNE
visualizes the neighborhoods and clusters of the samples. In Fig. 6(a), t-SNE
analyses of student network features under different commands show that the
agent learns unique skills and patterns for different commands, revealing a
diversity of skills after course training. If the commands are very similar,
the network reuses certain patterns and features to some extent but also fine-
tunes for these minor differences.

We also use t-SNE to compare policy features with different payloads and
friction coefficients. As shown in Fig. 6(b), the features under different
environmental variables are far away from each other, meaning that the student
policy can clearly recognize subtle environmental changes and respond
appropriately.

###  IV-D Comparative Evaluation

Figure 7: (a) Learning curves for different curriculum strategies. The
horizontal axis indicates the number of time steps. The vertical axis shows
the average reward over time steps within an episode. The shaded areas denote
one standard deviation over four runs. (c-d) The measured torques of the right
leg during forward running (around 3.0 m/s) for different curriculum
strategies. Figure 8: Velocity tracking test and CoT test results averaged
over four runs.

We compare the performance with the following baselines:

  * •

The grid adaptive curriculum from Margolis et al. (2022)[4], which increases
the difficulty by adding neighboring regions to the command sampling
distribution.

  * •

An adaptive curriculum from Miki et al. (2022)[3], which adjusts terrain
difficulty using an adaptive method and changes elements such as reward or
applied disturbances using a logistic function.

CHRL consists of curriculum learning and HER, but their contribution to
controller performance still needs to be clarified. We also removed some of
these components to compare their performance.

Fig. 7(a) shows the learning curves. In contrast to a policy without a
curriculum, the learning efficiency and performance of the policy can be
significantly improved regardless of the kind of curriculum learning strategy.
CHRL consistently performs better and learns significantly faster than other
baselines. The measured torques from each joint, while the robot ran at the
average speed nearest 3 m/s, are shown in Fig. 7(b-d). CHRL has a smoother
torque variation, which contributes to its high reward.

In Fig. 8(a), we find that the velocity tracking error of the policy increases
dramatically when the velocity command is greater than 3 m/s without CHRL.
This suggests that the curriculum is a crucial approach for learning high-
speed locomotions. Other benchmarks can track high-speed motion commands
stably, but have larger tracking errors than CHRL when tracking low-speed
commands from 1.0 m/s to 2.0 m/s.

Fig. 8(b) presents the CoTs versus average velocities for baselines. The
dimensionless cost of transport (CoT)[28] is calculated to compare the
efficiency of the controllers. The mechanical CoT is define as $\sum_{12\text{
actuators }}[\boldsymbol{\tau}\dot{\mathbf{q}}]^{+}/(\mathbf{m}g\mathbf{v})$,
where $\mathbf{m}g$ is the total weight. CHRL recorded slightly lower CoTs
than controllers trained with baselines. The presented controller is more
energy efficient than the RL controller for ANYmal[28] with a log mechanical
CoT of about -0.4.

##  V Conclusions

We propose a framework for end-to-end training controller: Curricular
Hindsight Reinforcement Learning (CHRL). We fully trained the neural network
controller in simulation end-to-end with this framework. Since our controller
uses only the most basic sensing, we can implement it on a low-cost robot. It
is also relatively easy for others to test and improve our methods.
Experimental and simulation results outline the main contributions of CHRL in
learning various adaptive behaviors from experts, adapting to changing
environments, and robustness to uncertainty. The experimental results show
that CHRL achieves multi-modal locomotion with agility and fast response to
different situations and perturbations, smooth transitions between standing
balance, trotting, turning, and recovery from a fall. CHRL also enables the
ability to achieve high-performance omnidirectional locomotion at high speeds.
As a learning-based approach, CHRL uses computational intelligence and shows
advantages in generating adaptive behaviors over traditional approaches that
rely purely on explicit manual programming. However, while increasing the
complexity of the task, physical simulation training may introduce some
limitations. As the task becomes more complex, differences between the
simulation and the real world may accumulate and become problematic. Based on
the results of CHRL, future work will investigate learning algorithms that can
safely refine motor skills on real hardware for more complex multi-modal
tasks.

## References

  * [1] S. Gangapurwala, L. Campanaro, and I. Havoutis, “Learning low-frequency motion control for robust and dynamic robot locomotion,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 5085–5091.
  * [2] A. L. Mitchell, W. Merkt, M. Geisert, S. Gangapurwala, M. Engelcke, O. P. Jones, I. Havoutis, and I. Posner, “Next steps: Learning a disentangled gait representation for versatile quadruped locomotion,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 10 564–10 570.
  * [3] T. Miki, J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter, “Learning robust perceptive locomotion for quadrupedal robots in the wild,” _Science Robotics_ , vol. 7, no. 62, p. eabk2822, 2022.
  * [4] G. B. Margolis, G. Yang, K. Paigwar, T. Chen, and P. Agrawal, “Rapid locomotion via reinforcement learning,” _arXiv preprint arXiv:2205.02824_ , 2022.
  * [5] A. Kumar, Z. Fu, D. Pathak, and J. Malik, “Rma: Rapid motor adaptation for legged robots,” _arXiv preprint arXiv:2107.04034_ , 2021.
  * [6] M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, O. Pieter Abbeel, and W. Zaremba, “Hindsight experience replay,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [7] J. Humphreys, J. Li, Y. Wan, H. Gao, and C. Zhou, “Bio-inspired gait transitions for quadruped locomotion,” _IEEE Robotics and Automation Letters_ , 2023.
  * [8] F. Farshidian, E. Jelavic, A. Satapathy, M. Giftthaler, and J. Buchli, “Real-time motion planning of legged robots: A model predictive control approach,” in _2017 IEEE-RAS 17th International Conference on Humanoid Robotics (Humanoids)_. IEEE, 2017, pp. 577–584.
  * [9] V. R. Kamidi, J. Kim, R. T. Fawcett, A. D. Ames, and K. A. Hamed, “Distributed quadratic programming-based nonlinear controllers for periodic gaits on legged robots,” _IEEE Control Systems Letters_ , vol. 6, pp. 2509–2514, 2022.
  * [10] R. Buchanan, T. Bandyopadhyay, M. Bjelonic, L. Wellhausen, M. Hutter, and N. Kottege, “Walking posture adaptation for legged robot navigation in confined spaces,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 2, pp. 2148–2155, 2019.
  * [11] Y. Ma, F. Farshidian, T. Miki, J. Lee, and M. Hutter, “Combining learning-based locomotion policy with model-based manipulation for legged mobile manipulators,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 2377–2384, 2022.
  * [12] N. Rathod, A. Bratta, M. Focchi, M. Zanon, O. Villarreal, C. Semini, and A. Bemporad, “Model predictive control with environment adaptation for legged locomotion,” _IEEE Access_ , vol. 9, pp. 145 710–145 727, 2021.
  * [13] B. Henze, A. Dietrich, and C. Ott, “An approach to combine balancing with hierarchical whole-body control for legged humanoid robots,” _IEEE Robotics and Automation Letters_ , vol. 1, no. 2, pp. 700–707, 2015.
  * [14] J. Wu, G. Xin, C. Qi, and Y. Xue, “Learning robust and agile legged locomotion using adversarial motion priors,” _IEEE Robotics and Automation Letters_ , 2023.
  * [15] J. Hwangbo, J. Lee, A. Dosovitskiy, D. Bellicoso, V. Tsounis, V. Koltun, and M. Hutter, “Learning agile and dynamic motor skills for legged robots,” _Science Robotics_ , vol. 4, no. 26, p. eaau5872, 2019.
  * [16] D. Hoeller, N. Rudin, D. Sako, and M. Hutter, “Anymal parkour: Learning agile navigation for quadrupedal robots,” _arXiv preprint arXiv:2306.14874_ , 2023.
  * [17] S. Choi, G. Ji, J. Park, H. Kim, J. Mun, J. H. Lee, and J. Hwangbo, “Learning quadrupedal locomotion on deformable terrain,” _Science Robotics_ , vol. 8, no. 74, p. eade2256, 2023.
  * [18] G. Ji, J. Mun, H. Kim, and J. Hwangbo, “Concurrent training of a control policy and a state estimator for dynamic and robust legged locomotion,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 4630–4637, 2022.
  * [19] N. Rudin, D. Hoeller, P. Reist, and M. Hutter, “Learning to walk in minutes using massively parallel deep reinforcement learning,” in _Conference on Robot Learning_. PMLR, 2022, pp. 91–100.
  * [20] I. M. A. Nahrendra, B. Yu, and H. Myung, “Dreamwaq: Learning robust quadrupedal locomotion with implicit terrain imagination via deep reinforcement learning,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 5078–5084.
  * [21] M. Fang, T. Zhou, Y. Du, L. Han, and Z. Zhang, “Curriculum-guided hindsight experience replay,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [22] A. Nair, B. McGrew, M. Andrychowicz, W. Zaremba, and P. Abbeel, “Overcoming exploration in reinforcement learning with demonstrations,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 6292–6299.
  * [23] C. Han, Z. Peng, Y. Liu, J. Tang, Y. Yu, and Z. Zhou, “Overfitting-avoiding goal-guided exploration for hard-exploration multi-goal reinforcement learning,” _Neurocomputing_ , vol. 525, pp. 76–87, 2023.
  * [24] B. Li, T. Lu, J. Li, N. Lu, Y. Cai, and S. Wang, “Acder: Augmented curiosity-driven experience replay,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_ , 2020, pp. 4218–4224.
  * [25] E. Coumans and Y. Bai, “Pybullet, a python module for physics simulation for games, robotics and machine learning,” http://pybullet.org, 2016–2021.
  * [26] V. Nair and G. E. Hinton, “Rectified linear units improve restricted boltzmann machines,” in _Icml_ , 2010.
  * [27] X. Chen, C. Wang, Z. Zhou, and K. W. Ross, “Randomized ensembled double q-learning: Learning fast without a model,” in _International Conference on Learning Representations_ , 2020.
  * [28] J. Lee, J. Hwangbo, L. Wellhausen, V. Koltun, and M. Hutter, “Learning quadrupedal locomotion over challenging terrain,” _Science robotics_ , vol. 5, no. 47, p. eabc5986, 2020.
  * [29] S. Ross, G. Gordon, and D. Bagnell, “A reduction of imitation learning and structured prediction to no-regret online learning,” in _Proceedings of the fourteenth international conference on artificial intelligence and statistics_. JMLR Workshop and Conference Proceedings, 2011, pp. 627–635.
  * [30] K. He, X. Zhang, S. Ren, and J. Sun, “Delving deep into rectifiers: Surpassing human-level performance on imagenet classification,” in _Proceedings of the IEEE international conference on computer vision_ , 2015, pp. 1026–1034.
  * [31] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [32] J. Tan, T. Zhang, E. Coumans, A. Iscen, Y. Bai, D. Hafner, S. Bohez, and V. Vanhoucke, “Sim-to-real: Learning agile locomotion for quadruped robots,” _arXiv preprint arXiv:1804.10332_ , 2018.
  * [33] D. A. Winter, _Biomechanics and motor control of human gait: normal, elderly and pathological_ , 1991.


NILPOTENT POLYNOMIALS OVER $\mathbb{Z}$
Sayak Sengupta
Department of Mathematics and Statistics, Binghamton University - SUNY,
Binghamton, New York, USA
<EMAIL_ADDRESS>

Abstract

For a polynomial $u(x)$ in $\mathbb{Z}[x]$ and $r\in\mathbb{Z}$, we consider
the orbit of $u$ at $r$ denoted and defined by
$\mathcal{O}_{u}(r):=\\{u^{(n)}(r)~{}|~{}n\in\mathbb{N}\\}$. Here we study
polynomials for which $0$ is in the orbit for a given $r$. We provide here a
complete classification of these polynomials when $|r|\leq 4$, with $|r|\leq
1$ already done in [2]. The central goal of this paper is to study the
following questions: (i) relationship between the integers $r$ and $m$, for a
polynomial $u$ in $N_{r,m}$ (see Definition 1.1); (ii) classification of the
polynomials with nilpotency index $|r|$ (see Definition 1.1) for large enough
$|r|$, and (iii) integer sequences with a generating polynomial (see
Definition 4.6).

##  1 Introduction

In [2], given an integer $r$, we considered the polynomials $u$ for which $0$
is not in the orbit of $u$ at $r$, but modulo every prime $p$, there is a
$m_{p}\in\mathbb{N}$ such that $p|u^{(m_{p})}(r)$. It turns out that these
polynomials can only be linear, and they have been completely classified in
[2]. In this paper we study the polynomials $u$ at $r$ where $0$ is in the
orbit. We will call these polynomials nilpotent at $r$ (see definitions and
notation below). We will focus on only positive integers $r$, as one can
obtain the same for negative integers $r$ by using Fact 2.4 (see Section 2).
In [2], such polynomials were classified for $r=0$ and $r=\pm 1$. In this
paper, we provide classification of nilpotent polynomials for $r=2,3,$ and
$4$, which can be found in Theorems 3.2, 3.4, and 3.5. The classification of
such polynomials for arbitrary $r$’s is perhaps impossible. However, we do
prove some partial and qualitative results, and we provide some inductive
technique through which one can classify such polynomials at a given positive
integer $r$ ($>1$) when the classification of nilpotent polynomials at
$1,\ldots,r-1$ are known.

We also prove that the largest $m$, say $m_{\text{max}}$, for which $N_{r,m}$
is non-empty is

$m_{\text{max}}(r)=\left\\{\begin{array}[]{l}2,\ if\ r=0\\\ 3,\ if\ |r|=1\\\
4,\ if\ |r|=2\\\ |r|,\ if|r|\geq 3\end{array}\right.$

(see notation in Section 1.1). Also, we provide a complete classification of
bounded integer sequences with a generating integer polynomial (see Definition
4.6 and Corollary 4.11).

We now make the following definitions.

###  1.1 Definitions, Notation, and Terminology

Throughout this paper, $\mathbb{N}$ is the set of all positive integers, for a
polynomial $u$, $u^{(0)}(x)=x$, and for each $n\in\mathbb{N}$

$u^{(n)}(x):=\underbrace{(u\circ u\circ\cdots\circ u)}_{n\text{ times}}(x),$

is the $n$th iteration of $u$.

######  Definition 1.1.

Given an integer $r$, we call a polynomial $u$ nilpotent at $r$, if there is
an $n\in\mathbb{N}$ so that $u^{(n)}(r)=0$, i.e., $0\in\mathcal{O}_{u}(r)$. We
call the smallest of such $n$’s the index/index of nilpotency of $u$ at $r$.
By convention, the zero polynomial is nilpotent at every $r$ with index 1.

We fix the following notation:
$N_{r,i}^{d}:=\\{u~{}|~{}u\textup{ is nilpotent at }r\textup{ of index
}i\textup{ and degree }d\\},~{}N_{r,i}:=\sqcup_{d=0}^{\infty}N_{r,i}^{d}~{},$
and $N_{r}:=\sqcup_{i=1}^{\infty}N_{r,i}~{}.$
Also, for a given integer $r\geq 2$ and a polynomial $u$, we define

$C_{r}:=\text{max}\\{s\in\mathbb{N}\cup\\{0\\}~{}|~{}r\geq s!-s-1\\},$ (1.1)

$\text{and }u_{i}(r):=u^{(i+1)}(r)-u^{(i)}(r),~{}i\in\mathbb{N}\cup\\{0\\}.$
(1.2)

It is immediate that $u_{i}(r)|u_{j}(r)$ for every $i<j$, whenever
$u_{j}(r)\neq 0$. The usefulness of $C_{r}$ will be apparent in Lemma 2.1, and
it plays a crucial role in the techniques of most of the proofs in this paper.

The following are some examples of nilpotent, and non-nilpotent polynomials:

###  1.2 Some Examples

  * •

Let $r\in\mathbb{Z}$. For each non-zero $q(x)\in\mathbb{Z}[x]$, $(x-r)q(x)\in
N_{r,1}$.

  * •

Let $u(x)=-x^{3}+9x^{2}-25x+25$. Then $u(2)=3,u(3)=4,u(4)=5,\text{ and
}u(5)=0$, i.e., $u\in N_{2,4}^{3}$.

  * •

Let $u(x)=x^{3}-6x^{2}+12x-7$. Then $u(3)=2,u(2)=1,\text{ and }u(1)=0$, i.e.,
$u\in N_{3,3}$.

  * •

Let $u(x)=x^{2}-4x$. Then $u(3)=-3$, and $u(-3)=21$. As $u(x)-x>0$ on
$(5,\infty)$, it follows that $0\not\in\mathcal{O}_{u}(3)$, i.e., $u$ is not
nilpotent at $3$.

The next three facts follow directly from Theorem 4.1, Corollary 4.2, and
Theorem 4.4, respectively, of [2]. These facts will be used extensively
throughout the paper, and so they are reproduced here for the reader’s
convenience.

######  Fact 1.2 (cf. [2], Theorem 4.1).

The following is the list of all polynomials in $N_{1}$:

  1. (a)

$(x-1)p(x)$ with $p(x)\in\mathbb{Z}[x]$ (Nilpotent of nilpotency index 1),

  2. (b)

$-2x+4+p(x)(x-1)(x-2)$ with $p(x)\in\mathbb{Z}[x]$ (Nilpotent of nilpotency
index 2), and

  3. (c)

$-2x^{2}+7x-3+p(x)(x-1)(x-2)(x-3)$ with $p(x)\in\mathbb{Z}[x]$ (Nilpotent of
nilpotency index 3).

######  Fact 1.3 (cf. [2], Corollary 4.2).

The following is the list of all polynomials in $N_{-1}$:

  1. (a)

$(x+1)p(x)$ with $p(x)\in\mathbb{Z}[x]$ (Nilpotent of nilpotency index 1),

  2. (b)

$-2x-4+p(x)(x+1)(x+2)$ with $p(x)\in\mathbb{Z}[x]$ (Nilpotent of nilpotency
index 2), and

  3. (c)

$2x^{2}+7x+3+p(x)(x+1)(x+2)(x+3)$ with $p(x)\in\mathbb{Z}[x]$ (Nilpotent of
nilpotency index 3).

######  Fact 1.4 (cf. [2], Corollary 4.4).

The following is the list of all polynomials in $N_{0}$:

  1. (a)

$xp(x)$ with $p(x)\in\mathbb{Z}[x]\setminus\\{0\\}$ (Nilpotent of nilpotency
index 1), and

  2. (b)

$(x-a)(xp(x)-1)$, $a\in\mathbb{Z}\setminus\\{0\\}$ and $p(x)\in\mathbb{Z}[x]$
(Nilpotent of nilpotency index 2).

The paper consists of three main results.

######  Theorem 1.5 (cf. Theorems 3.2 and 3.4, and Corollaries 3.5 and 4.2).

For a given integer $r$, and $u$ nilpotent at $r$, one has that nilpotency
index of $u$ at $r$ is at most $|r|+2$. Moreover, if $|r|\geq 3$, then the
nilpotency index of $u$ is at most $|r|$.

######  Theorem 1.6 (cf. Theorem 4.3, and Corollary 4.4).

For a given integer $r$ with $|r|\geq 4$, and $u$ nilpotent at $r$ of
nilpotency index $r$, one has that $u(x)$ must be of the form
$(x-1)+(x-1)\cdots(x-r)p(x)$ for some polynomial $p(x)$.

######  Theorem 1.7 (cf. Definitions 4.5 and 4.6, and Theorems 4.9 and 4.10).

The classification of all infinitely nilpotent sequences, and the
classification of all bounded integer sequences having a generating polynomial
over the integers.

To prove Theorems 1.5 and 1.6 we use induction on $r$, and $r=4$ serves as the
base case for the induction. Thus it was necessary to include the
classifications of nilpotent polynomials for $r=3\text{ and }4$, $r\in\\{0,\pm
1\\}$ being already available (from Facts 1.2, 1.3, and 1.4). For the proofs
of Theorems 3.2, 3.4, and 3.5, in addition to using Facts 1.2, 1.3, and 1.4,
we have also used Lemma 2.1, which is stated and proved in Section 2.

This paper consists of 4 sections. Sections 2 and 3 are dedicated to
developing the background for stating and proving the main results. Section 4
consists of the main results, and it is divided into two subsections; in
Section 4.1 we study the relation between $r$ and $m$ for a polynomial $u$ in
$N_{r,m}$, and in Section 4.2 we study integer sequences having generating
integer polynomials (see Definition 4.6). The interested reader can look at
the work of Borisov in [1] (see Example 1 of [1]), from which the study of
classification of the polynomials that was defined in [2] commenced.

We end this section with a discussion on a few open problems. Given positive
integers $r\text{ and }m$, $u\in N_{r,m}$, and $k\in\mathbb{N}$ satisfying the
condition (2.3), we have, from Lemma 2.1, that $k\leq C_{r}$. One notices that
the bound on $k$ cannot be improved in general: for every given $k\geq 3$, and
$r=k!-k-1$, consider $u(x)=(x+1)-(x-r)\cdots(x-r-k+1)$. This is a polynomial
of degree $k$ satisfying (2.3), and $u(r+k)=(r+k+1)-k!=0$, i.e.,
$u^{(k+1)}(r)=0$, i.e., $u(x)\in N_{r,k+1}^{k}$. Now suppose that $r$ is not
in $\\{s!-s-1~{}|~{}s\geq 3\\}$. We ask the following two questions:

  1. Q1.

Can the bound for $k$ be improved?

  2. Q2.

Is it possible to get a universal bound for $k$ that does not depend on $r$?

Also, we ask: If $r$ is large enough, and $m>r/2$, then does it follow that
$u\in N_{r,r}$ (cf. Theorem 1.5)? One can check from Theorem 3.5 that this is
true for $r=4$. Knowing that one can rephrase the above question: If $r\geq
4$, and $m>r/2$, then does it follow that $u\in N_{r,r}$?

##  2 The Main Tools

We begin this section with a lemma which, albeit being simple, has deep impact
on the techniques of most of the proofs of this paper.

######  Lemma 2.1.

Let $r,m$ be positive integers, $r\neq 1$ and $u\in N_{r,m}$ such that

$u(r)=r+1,\ldots,u(r+k-1)=r+k,\text{ however, }u(r+k)\neq r+k+1,$ (2.3)

for some non-negative integer $k$, then $k\leq C_{r}$, where $C_{r}$ is as in
(1.1).

###### Proof.

One notices that (2.3) implies that the polynomial $u(x)-x-1$ has zeros at
$r,\ldots r+k-1$, and so $u(x)$ must be of the form
$u(x)=(x+1)+(x-r)\ldots(x-r-k+1)g(x)$, for some non-zero polynomial $g(x)$
over $\mathbb{Z}$. Then $u(r+k)=(r+k+1)+k!g(r+k)$. Since $u(r+k)\neq r+k+1$,
$g(r+k)$ must be non-zero.

$\displaystyle\text{Then }|u_{k}(r)|=|u^{(k+1)}(r)-u^{(k)}(r)|$
$\displaystyle=|u(r+k)-(r+k)|$ $\displaystyle=|(r+k+1)-(r+k)+k!g(r+k)|$
$\displaystyle=|1+k!g(r+k)|$ $\displaystyle\geq k!-1,\text{ where
}u_{i}(r)\text{ is as in }(1.2).$

As $u_{i}(r)|u_{j}(r)$, whenever $i\leq j$, one has

$-(r+k)=\sum\limits_{i=k}^{m-1}u_{i}(r)\equiv 0\pmod{u_{k}(r)}.$

This means $u_{k}(r)|r+k$, so that $r+k\geq k!-1$, i.e., $k\leq C_{r}$.∎

The next lemma is an interesting consequence of Lagrange’s Interpolation
Theorem. Its statement and proof is due to A. Borisov.

######  Lemma 2.2.

Let $n\in\mathbb{N}$, and $r_{0},\ldots,r_{n}$ be integers. Also, let
$p(x)\in\mathbb{Q}[x]$ be such that $\deg(p)\leq n-1$, and $p(r_{i})=r_{i+1}$
for each $i\in\\{0,\ldots,n-1\\}$. If there is a polynomial $q(x)$ over
$\mathbb{Z}$ such that $q(r_{i})=p(r_{i})$ for each $i\in\\{0,\ldots,n-1\\}$,
then $p(x)\in\mathbb{Z}[x]$.

###### Proof.

The condition on $q$ implies that there must be some polynomial
$f(x)=a_{0}+\cdots+a_{d}x^{d}\in\mathbb{Q}[x]$ such that

$q(x)=p(x)+(x-r_{0})\cdots(x-r_{n-1})f(x).$

One notices readily that it is enough to show that $f(x)\in\mathbb{Z}[x]$.
Suppose, if possible, that $f(x)\in\mathbb{Q}[x]\setminus\mathbb{Z}[x]$. Let
$m$ be the least integer of the set $\\{0\ldots,d\\}$ such that $a_{m}$ is not
in $\mathbb{Z}$. Then one has that the coefficient of $x^{n+m}$ in
$(x-r_{0})\cdots(x-r_{n-1})f(x)$ is not in $\mathbb{Z}$, and as $\deg p<n$,
one obtains that the coefficient of $x^{n+m}$ in
$(x-r_{0})\cdots(x-r_{n-1})f(x)$ is equal to the coefficient of $x^{n+m}$ in
$q(x)$, i.e., $q(x)\not\in\mathbb{Z}[x]$, which is absurd. ∎

The next fact will be useful in the proofs of Theorems 3.2, 3.4 and 3.5.

######  Fact 2.3.

If $f$ is a polynomial over $\mathbb{Z}$, then $f(a/b)$ cannot be of the form
$c/d$ if $P(b)\not\supset P(d)$, where given an integer $a$, $P(a)$ is the set
of all prime numbers diving $a$.

The following fact gives a one-to-one correspondence between the sets
$N_{r,m}$ and $N_{-r,m}$, and this makes it enough to consider the set
$N_{r,m}$ for non-negative $r$’s.

######  Fact 2.4 (cf. Fact 3.1 of [2]).

Let $u(x)$ be a polynomial of degree $d$ and let
$r\in\mathbb{Z}\setminus\\{0\\}$. Define $v(x):=-u(-x)$. Then

$u(x)\in N_{r,n}^{d}\iff v(x)\in N_{-r,n}^{d}.$

###### Proof.

Since $v(-x)=-u(x)$, one sees by induction that $v^{(n)}(-r)=-u^{(n)}(r)$,
from which the fact follows. ∎

Now we describe the idea of reduction of polynomials that was mentioned in the
introduction. Let $r\in\mathbb{N}$, and $u=u(x)$ in $\mathbb{Z}[x]$ of degree
$d$. Then for any divisor $q$ of $\gcd(r,u(r))$ one can define

$v=v(x):=\frac{1}{q}u(qx).$

Note that $v$ is a polynomial over $\mathbb{Z}$ of the same degree as that of
$u$, and $qv\left(\frac{r}{q}\right)=u(r)$. By induction, it readily follows
that $qv^{(n)}\left(\frac{r}{q}\right)=u^{(n)}(r)\text{ for
all}~{}n\in\mathbb{N}$. Now one immediately sees that $u(x)$ is nilpotent at
$r$ if and only if $v(x)$ is nilpotent at $\frac{r}{q}$. This means one can
reduce any polynomial $u(x)$ in $N_{r,i}^{d}$ to a polynomial $v(x)$ in
$N_{\frac{r}{q},i}^{d}$. We will call the polynomial $v$ the reduction of $u$
from $r$ to $\frac{r}{q}$.

##  3 The Classification of Polynomials in $N_{r}$, for $|r|\in\\{2,3,4\\}$

In this section we will prove the necessary groundwork which is needed to
prove the main results in the next section. We first make the following
definition.

######  Definition 3.1.

Let $u\in N_{r,m}$ for some integer $r$ and some positive integer $m$. We say
that $\\{r,u(r),\ldots,u^{(m-1)}(r),0\\}$ is the finite sequence associated to
$u$ at $r$.

We now classify the polynomials of $N_{2}$.

######  Theorem 3.2.

The following is the list of all polynomials in $N_{2}$:

  1. (1)

$(x-2)p(x)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 1 with the associated
finite sequence $\\{2,0\\}$).

  2. (2)

$(x-1)^{2}+p(x)(x-1)(x-2)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with
the associated finite sequence $\\{2,1,0\\}$).

  3. (3)

$-2x+8+p(x)(x-2)(x-4)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with the
associated finite sequence $\\{2,4,0\\}$).

  4. (4)

$(3-x)(x+1)+p(x)(x-2)(x-3)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with
the associated finite sequence $\\{2,3,0\\}$).

  5. (5)

$-x^{2}+7x-6+p(x)(x-2)(x-4)(x-6)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index
3 with the associated finite sequence $\\{2,4,6,0\\}$).

  6. (6)

$(5-x)(x^{2}-4x+5)+p(x)(x-2)(x-3)(x-4)(x-5)$, $p(x)\in\mathbb{Z}[x]$
(Nilpotent of index 4 with the associated finite sequence $\\{2,3,4,5,0\\}$).

###### Proof.

Let $u$ be a non-zero polynomial in $N_{2,m}$ for some $m\in\mathbb{N}$. That
means for any $k$ satisfying (2.3) one obtains by Lemma 2.1 that $0\leq k\leq
C_{2}=3$. Also, let $u_{i}(2)$’s be as in (1.2).

Case 1. Let $k=0$. That means $u(2)\neq 3$. Since
$-2=\sum\limits_{i=0}^{m-1}u_{i}(2)\equiv 0\pmod{u_{0}(2)}$, one has
$u_{0}(2)|2$. Then $u_{0}(2)\in\\{-1,\pm 2\\}$.

If $u_{0}(2)=-1$, then $u(2)=1$ and so it follows from the list in Fact 1.2
that $u$ must be of the form $(x-1)p(x)$, for some polynomial $p(x)$ with
$p(2)=1$.

If $u_{0}(2)=-2$, then $u(2)=0$, i.e., $u(x)=(x-2)p(x)$, for some non-zero
polynomial $p(x)$.

If $u_{0}(2)=2$, then $u(2)=4$. Let $v$ be the reduction of $u$ from $2$ to
$1$. Then $v\in N_{1,m}$ and $v(1)=2$. Then it follows from Fact 1.2 that $v$
must be of one of the following forms:

  * •

$v(x)=-2x+4+p(x)(x-1)(x-2)$ for some polynomial $p(x)$ (see Fact 1.2(b)), in
which case
$u(x)=2v\left(\frac{x}{2}\right)=-2x+8+\frac{1}{2}p\left(\frac{x}{2}\right)(x-2)(x-4)$
with the condition that
$\frac{1}{2}p\left(\frac{x}{2}\right)\in\mathbb{Z}[x]$.

  * •

$v(x)=-2x^{2}+7x-3+p(x)(x-1)(x-2)(x-3)$ for some polynomial $p(x)$ (see Fact
1.2(c)), in which case
$u(x)=2v\left(\frac{x}{2}\right)=-x^{2}+7x-6+\frac{1}{4}p\left(\frac{x}{2}\right)(x-2)(x-4)(x-6)$,
with the condition that
$\frac{1}{4}p\left(\frac{x}{2}\right)\in\mathbb{Z}[x]$.

Case 2. Let $k=1$. That means $u(2)=3$ and $u(3)\neq 4$. Since
$-3=\sum\limits_{i=1}^{m-1}u_{i}(2)\equiv 0\pmod{u_{1}(2)}$, one has
$u_{1}(2)|3$. As $u$ is nilpotent at 2 and $u(3)\neq 4$, one immediately sees
that $u_{1}(2)=\\{\pm 3\\}$.

If $u_{1}(2)=-3$, then $u(3)=0$, and so $u(x)$ is of the form $(x-3)p(x)$, for
some $p(x)\in\mathbb{Z}[x]$ with $p(2)=-3$.

If $u_{1}(2)=3$, then $u(3)=6$. Let $v$ be the reduction of $u$ from $3$ to
$1$. Then $v\in N_{1,m}$, $v\left(\frac{2}{3}\right)=1$, and $v(1)=2$. One can
use the conditions on $v$ and Facts 1.2, and 2.3, to check that no such $v$
with integer coefficients is possible.

Case 3. Let $k=2$. That means $u(2)=3,~{}u(3)=4$, and $u(4)\neq 5$. Then
$u_{2}(2)|4$, i.e., $u_{2}(2)\in\\{2,\pm 4\\}$, i.e., $u(4)\in\\{0,6,8\\}$,
i.e., in particular, $u(0)$ is even, which is false as $u(2)=3$.

Case 4. Let $k=3$. That means $u(2)=3,~{}u(3)=4,~{}u(4)=5,$ and $u(5)\neq 6$.
Then $u_{3}(2)|5$, and one sees that $u_{3}(2)\in\\{\pm 5\\}$.

If $u_{3}(2)=-5$, then $u(5)=0$, i.e., $u(x)=(x-5)p(x)$, for some
$p(x)\in\mathbb{Z}[x]$, with $p(2)=-1,~{}p(3)=-2$ and $p(4)=-5$.

If $u_{3}(2)=5$, then $u(5)=10$. Let $v$ be the reduction of $u$ from $5$ to
$1$. Then $v\in N_{1,m}$,
$v\left(\frac{2}{5}\right)=\frac{3}{5},v\left(\frac{3}{5}\right)=\frac{4}{5}$,
and $v(1)=2$. Similar to Case 2, one can check that no such $v$ having integer
coefficients can exist. ∎

We will use the classification of polynomials in $N_{-2}$ later in Theorem
4.10, and so the following corollary, which follows directly from Theorem 3.2
and Fact 2.4, is announced here for convenience.

######  Corollary 3.3.

The following is the list of all polynomials in $N_{-2}$:

  1. (1)

$(x+2)p(x)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 1 with the associated
finite sequence $\\{-2,0\\}$).

  2. (2)

$(x+1)(x+3)+p(x)(x+1)(x+2)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with
the associated finite sequence $\\{-2,-1,0\\}$).

  3. (3)

$-2x-8+p(x)(x+2)(x+4)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with the
associated finite sequence $\\{-2,-4,0\\}$).

  4. (4)

$(x+3)(x-1)+p(x)(x+2)(x+3)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with
the associated finite sequence $\\{-2,-3,0\\}$).

  5. (5)

$x^{2}+7x+6+p(x)(x+2)(x+4)(x+6)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 3
with the associated finite sequence $\\{-2,-4,-6,0\\}$).

  6. (6)

$-(x+5)(x^{2}+4x+5)+p(x)(x+2)(x+3)(x+4)(x+5)$, $p(x)\in\mathbb{Z}[x]$
(Nilpotent of index 4 with the associated finite sequence
$\\{-2,-3,-4,-5,0\\}$).

Now that we have classified the polynomials in $N_{2}$, we can classify the
polynomials of $N_{3}$.

######  Theorem 3.4.

The following is the list of all polynomials in $N_{3}$:

  1. (1)

$(x-3)p(x)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 1 with the associated
finite sequence $\\{3,0\\}$).

  2. (2)

$(x-1)(x-2)+p(x)(x-2)(x-3)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with
the associated finite sequence $\\{3,2,0\\}$).

  3. (3)

$-2x+12+p(x)(x-3)(x-6)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with the
associated finite sequence $\\{3,6,0\\}$).

  4. (4)

$(4-x)(x+1)+p(x)(x-3)(x-4)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with
the associated finite sequence $\\{3,4,0\\}$).

  5. (5)

$(x-1)+p(x)(x-1)(x-2)(x-3)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 3 with
the associated finite sequence $\\{3,2,1,0\\}$).

  6. (6)

$(2-x)(3x-13)+p(x)(x-2)(x-3)(x-4)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index
3 with the associated finite sequence $\\{3,4,2,0\\}$).

  7. (7)

$(5-x)(3x-7)+p(x)(x-3)(x-4)(x-5)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index
3 with the associated finite sequence $\\{3,4,5,0\\}$).

  8. (8)

$-2x+8+p(x)(x-2)(x-3)(x-4)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 3 with
the associated finite sequence $\\{3,2,4,0\\}$).

###### Proof.

Let $u$ be a non-zero polynomial in $N_{3,m}$, for some $m\in\mathbb{N}$. That
means for any $k$ satisfying (2.3) one obtains by Lemma 2.1 that $0\leq k\leq
C_{3}=3$. Also, let $u_{i}(3)$’s be as in (1.2).

Case 1. Let $k=0$. That means $u(3)\neq 4$. Since
$-3=\sum\limits_{i=0}^{m-1}u_{i}(3)\equiv 0\pmod{u_{0}(3)}$, one has
$u_{0}(3)|3$. i.e., $u_{0}(3)\in\\{-1,\pm 3\\}$, as $u_{0}(3)$ cannot be 1.

If $u_{0}(3)=-1$, then $u(3)=2$, i.e., $u\in N_{2,m-1}$. It follows from the
list in Theorem 3.2 that $u$ must be of one of the following forms:

  * •

$u(x)=(x-2)p(x)$, with $p(3)=2$ (see Theorem 3.2(1)).

  * •

$u(x)=(x-1)^{2}+p(x)(x-1)(x-2)$, with $p(3)=-1$ (see Theorem 3.2(2)).

  * •

$u(x)=-2x+8+p(x)(x-2)(x-4)$, with $p(3)=0$ (see Theorem 3.2(3)).

If $u_{0}(3)=-3$, then $u(3)=0$, i.e., $u(x)=(x-3)p(x)$, for some non-zero
polynomial $p(x)$.

If $u_{0}(3)=3$, then $u(3)=6$. Let $v$ be the reduction of $u$ from $3$ to
$1$. So $v(1)=2$ and $v\in N_{1,m}.$ Now from Fact 1.2, $v$ must be of one of
the following forms:

  * •

$v(x)=-2x+4+p(x)(x-1)(x-2)$ for some polynomial $p(x)$ (see Fact 1.2(b)), in
which case $u(x)=-2x+12+\frac{1}{3}p\left(\frac{x}{3}\right)(x-3)(x-6)$ with
the condition that $\frac{1}{3}p\left(\frac{x}{3}\right)$ is a polynomial over
$\mathbb{Z}$.

  * •

$v(x)=-2x^{2}+7x-3+p(x)(x-1)(x-2)(x-3)$ for some polynomial $p(x)$ (see Fact
1.2(c)), in which case
$u(x)=-\frac{2}{3}x^{2}+7x-9+\frac{1}{9}p\left(\frac{x}{3}\right)(x-3)(x-6)(x-9)$.
However, this cannot be a polynomial over $\mathbb{Z}$ for any choice of an
integer polynomial $p(x)$, and that follows from Lemma 2.2.

Case 2. Let $k=1$. That means $u(3)=4$, and $u(4)\neq 5$. Then one has
$u_{1}(3)|4$. i.e., $u_{1}(3)\in\\{\pm 2,\pm 4\\}$. (Note that $u_{1}(3)$
cannot be $\pm 1$, as that would imply $u(4)=3$ in which case it cannot be
nilpotent, or $u(4)=5$, which is not possible in Case 2.) If $u_{1}(3)=-2$,
then $u(4)=2$, i.e., $u\in N_{2,m-1}$. From the list in Theorem 3.2 one sees
that $u$ must be of the form $(x-2)p(x)$, with $p(3)=4,p(4)=1$.

If $u_{1}(3)=2$, then $u(4)=6$. Let $v$ be the reduction of $u$ from $4$ to
$2$. Then $v\left(\frac{3}{2}\right)=2,v(2)=3$, and $v\in N_{2,m-1}$. Using
the list in Theorem 3.2 and Fact 2.3, one can check that no such polynomial
$v$ with integer coefficients can exist.

If $u_{1}(3)=-4$, then $u(4)=0,$ i.e., $u(x)=(x-4)p(x)$ with $p(3)=-4$.

If $u_{1}(3)=4,$ then $u(4)=8$. Let $v$ be the reduction of $u$ from $4$ to
$1$. Then $v\in N_{2,m-1}$, and also $v(2)=2$, which is impossible.

Case 3. Let $k=2$. That means $u(3)=4,~{}u(4)=5$, but $u(5)\neq 6$. Then one
has $u_{2}(3)|5$. i.e., $u_{2}(3)\in\\{\pm 5\\}$. (Note that $u_{2}(3)$ cannot
be $\pm 1$.)

If $u_{2}(3)=-5$, then $u(5)=0$, i.e., $u(x)=(x-5)p(x)$ with
$p(3)=-2,p(4)=-5$.

If $u_{2}(3)=5$, then $u(5)=10$. Let $v$ be the reduction of $u$ from $5$ to
$1$. Then
$v\left(\frac{3}{5}\right)=\frac{4}{5},v\left(\frac{4}{5}\right)=1,v(1)=2$ and
$v\in N_{1,m-2}$. Using Facts 1.2, and 2.3, one can check that no such $v$ is
possible with integer coefficients.

Case 4. Let $k=3$. That means $u(3)=4,u(4)=5,u(5)=6$, but $u(6)\neq 7$. Using
similar arguments as in Case 3, we can reject all the possibilities that arise
here. ∎

Finally, we are ready to classify the polynomials of $N_{4}$.

######  Theorem 3.5.

The following is the list of all polynomials in $N_{4}$:

  1. (1)

$(x-4)p(x)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 1 with the associated
finite sequence $\\{4,0\\}$).

  2. (2)

$(x-1)(x-3)+p(x)(x-3)(x-4)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with
the associated finite sequence $\\{4,3,0\\}$).

  3. (3)

$-\frac{x^{2}}{2}+2x+6+\frac{1}{2}p\left(\frac{x}{2}\right)(x-4)(x-6)$, where
$p(x)\in\mathbb{Z}[x]$ is such that all such polynomials are over $\mathbb{Z}$
(Nilpotent of index 2 with the associated finite sequence $\\{4,6,0\\}$).

  4. (4)

$\frac{x^{2}}{2}-2x+2+\frac{1}{2}p\left(\frac{x}{2}\right)(x-2)(x-4)$, where
$p(x)\in\mathbb{Z}[x]$ is such that all such polynomials are over $\mathbb{Z}$
(Nilpotent of index 2 with the associated finite sequence $\\{4,2,0\\}$).

  5. (5)

$-2x+16+p(x)(x-4)(x-8)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with the
associated finite sequence $\\{4,8,0\\}$).

  6. (6)

$(x+1)(x-5)+p(x)(x-4)(x-5)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 2 with
the associated finite sequence $\\{4,5,0\\}$).

  7. (7)

$(x-1)+p(x)(x-1)(x-2)(x-3)(x-4)$, $p(x)\in\mathbb{Z}[x]$ (Nilpotent of index 4
with the associated finite sequence $\\{4,3,2,1,0\\}$).

###### Proof.

Let $u$ be a non-zero polynomial in $N_{4,m}$, for some $m\in\mathbb{N}$. That
means for any $k$ satisfying (2.3) one obtains by Lemma 2.1 that $0\leq k\leq
C_{4}=3$. Also, let $u_{i}(4)$’s be as in (1.2).

Case 1. Let $k=0$. That means $u(4)\neq 5$. Since
$-4=\sum\limits_{i=0}^{m-1}u_{i}(4)\equiv 0\pmod{u_{0}(4)}$, one has
$u_{0}(4)|4$. i.e., $u_{0}(4)\in\\{-1,\pm 2,\pm 4\\}$, as $u_{0}(4)$ cannot be
1.

If $u_{0}(4)=-1$, then $u(4)=3$, i.e., $u\in N_{3,m-1}$. It follows from the
list in Theorem 3.4 that $u$ must be of one of the following forms:

  * •

$u(x)=(x-3)p(x)$ for some polynomial $p(x)$ with $p(4)=3$ (see Theorem
3.4(1)).

  * •

$u(x)=(x-1)+p(x)(x-1)(x-2)(x-3)$ for some polynomial $p(x)$ with $p(4)=0$ (see
Theorem 3.4(2)).

If $u_{0}(4)=2$, then $u(4)=6$. Let $v$ be the reduction of $u$ from $4$ to
$2$. Then $v(2)=3$ and $v\in N_{2,m}$. Looking at the list in Theorem 3.2, $v$
must be of one of the following forms:

  * •

$v(x)=(3-x)(x+1)+p(x)(x-2)(x-3)$ for some polynomial $p(x)$. Then
$u(x)=2v\left(\frac{x}{2}\right)=-\frac{x^{2}}{2}+2x+6+\frac{1}{2}p\left(\frac{x}{2}\right)(x-4)(x-6)$.

  * •

$v(x)=(5-x)(x^{2}-4x+5)+p(x)(x-2)(x-3)(x-4)(x-5)$ for some polynomial $p(x)$.
However, then one has
$u(x)=2v\left(\frac{x}{2}\right)=\frac{1}{4}(10-x)(x^{2}-8x+20)+\frac{1}{8}p\left(\frac{x}{2}\right)(x-4)(x-6)(x-8)(x-10)$,
which, by Lemma 2.2, cannot be a polynomial over $\mathbb{Z}$ for any choice
of integer polynomial $p(x)$.

If $u_{0}(4)=-2$, then $u(4)=2$. Let $v$ be the reduction of $u$ from $4$ to
$2$. Then $v(2)=1$ and $v\in N_{2,m}.$ From Theorem 3.2 it follows that $v$
must be of the form $(x-1)^{2}+p(x)(x-1)(x-2)$ for some polynomial $p(x)$ (see
Theorem 3.2(2)), and then
$u(x)=2v\left(\frac{x}{2}\right)=\frac{x^{2}}{2}-2x+2+\frac{1}{2}p\left(\frac{x}{2}\right)(x-2)(x-4)$.

If $u_{0}(4)=4$, then $u(4)=8$. Let $v$ be the reduction of $u$ from $4$ to
$1$. Then $v(1)=2$ and $v\in N_{1,m}.$ From the list in Fact 1.2 it follows
that $v$ must be of one of the following forms:

  * •

$v(x)=-2x+4+p(x)(x-1)(x-2)$, i.e.,
$u(x)=-2x+16+\frac{1}{4}p\left(\frac{x}{4}\right)(x-4)(x-8)$.

  * •

$v(x)=-2x^{2}+7x-3+p(x)(x-1)(x-2)(x-3)$, i.e.,
$u(x)=-\frac{1}{2}x^{2}+7x-12+\frac{1}{16}p\left(\frac{x}{4}\right)(x-4)(x-8)(x-12)$.
However, this cannot be a polynomial over $\mathbb{Z}$ for any choice of an
integer polynomial $p(x)$, which follows from Lemma 2.2.

If $u_{0}(4)=-4$, then $u(4)=0$, i.e., $u(x)=(x-4)p(x)$, for some non-zero
$p(x)$.

Case 2. Let $k=1$. That means $u(4)=5,~{}u(5)\neq 6$. Then one has
$u_{1}(4)|5$. i.e., $u_{1}(4)\in\\{\pm 5\\}$. (Note that $u_{1}(4)$ cannot be
$\pm 1$, as that would imply $u(5)=4$, in which case it cannot be nilpotent,
or $u(5)=6$, which is not possible in this case.)

If $u_{1}(4)=-5$, then $u(5)=0$, i.e., $u(x)=(x-5)p(x)$, with $p(4)=-5$.

If $u_{1}(4)=5$, then $u(5)=10$. Let $v$ be the reduction of $u$ from $5$ to
$1$. Then $v(1)=2,v\left(\frac{4}{5}\right)=1$, and $v\in N_{1,m-1}.$ One can
use list in Facts 1.2 and 2.3 to check that such a $v$ with integer
coefficients cannot exist.

Case 3. Let $k=2$. That means $u(4)=5,~{}u(5)=6$, but $u(6)\neq 7$. Then one
has $u_{2}(4)|6$. i.e., $u_{2}(4)\in\\{\pm 2,\pm 3,\pm 6\\}$. (Note that
$u_{2}(4)$ cannot be $\pm 1$.) Also, $u_{2}(4)$ cannot be even, as that would
imply $u(6)$ is even, i.e., $u(0)$ is even, and that cannot happen as $u(4)$
is odd. Thus $u_{2}(4)\not\in\\{\pm 2,\pm 6\\}$. That means $u_{2}(3)\in\\{\pm
3\\}$.

If $u_{2}(4)=-3$, then $u(6)=3$. Let $v$ be the reduction of $u$ from $6$ to
$2$. Then
$v\left(\frac{4}{3}\right)=\frac{5}{3},v\left(\frac{5}{3}\right)=2,v(2)=1$,
and $v\in N_{1,m-2}$. Using the list in Fact 1.2 and Fact 2.3, one can check
that no such $v$ with integer coefficients can exist.

If $u_{2}(4)=3$, then $u(6)=12$. Let $v$ be the reduction of $u$ from $6$ to
$1$. Then
$v\left(\frac{4}{3}\right)=\frac{5}{3},v\left(\frac{5}{3}\right)=2,v(2)=3$ and
$v\in N_{2,m-2}$. Using the list in Theorem 3.2 and Fact 2.3, one can check
that no such $v$ with integer coefficients can exist.

Case 4. Let $k=3$. That means $u(4)=5,u(5)=6,u(6)=7$, but $u(7)\neq 8$. Using
similar arguments as in Case 3, we can reject all the possibilities that arise
here. ∎

The classification of the polynomials in $N_{-3}$ and $N_{-4}$ follows from
Theorems 3.4, 3.5, and Fact 2.4.

##  4 The Main Results

We state and prove the main results in this section.

###  4.1 Relation Between the Integers $r$ and $m$ in $N_{r,m}$

We start with the first main result.

######  Theorem 4.1.

Let $r$ be an integer greater than 3 and $u\in N_{r,m}$. Then $m\leq r$, i.e.,
in other words, $N_{r}=\sqcup_{i=1}^{r}N_{r,i}$.

###### Proof.

We will use induction on $r$. The base case follows from Theorem 3.5. Let $r$
be an integer greater than or equal to 4, and that the statement is true for
every integer $q$ satisfying $4\leq q\leq r$. We want to prove that the
statement is true for $r+1$, i.e., if $u\in N_{r+1,m}$, then $r+1\geq m$. Then
by Lemma 2.1, the $k$, for which (2.3) holds, must be between 0 and $C_{r+1}$,
where $C_{r+1}$ is as in (1.1). Let $u_{i}(r+1)$’s be as in (1.2).

First suppose that $k=0$, i.e., $u(r+1)\neq r+2$. Then
$-(r+1)=\sum\limits_{i=0}^{m-1}u_{i}(r+1)\equiv 0\pmod{u_{0}(r+1)},$ i.e.,
$u_{0}(r+1)|r+1$. The $u_{0}(r+1)$, of course, cannot be $1$. If
$u_{0}(r+1)=-1$, then $u(r+1)=r$, so that $u\in N_{r,m-1}$. Then by induction
hypothesis, we get $m-1\leq r,$ i.e., $m\leq r+1$. Now suppose that
$u_{0}(r+1)$ is a non-trivial divisor of $r+1$. Define
$v(x):=\frac{1}{|u_{0}(r+1)|}u(|u_{0}(r+1)|x)$. Then $v\in
N_{\frac{r+1}{|u_{0}(r+1)|},m}$, and also $\frac{r+1}{|u_{0}(r+1)|}<r+1$. If
$\frac{r+1}{|u_{0}(r+1)|}\geq 4$, then $m\leq\frac{r+1}{|u_{0}(r+1)|}<r+1$.
Otherwise $\frac{r+1}{|u_{0}(r+1)|}\in\\{1,2,3\\}$. If
$\frac{r+1}{|u_{0}(r+1)|}=1$, then by Fact 1.1 one has $m\leq 3<r+1$.
Similarly, one treats the possibilities $\frac{r+1}{|u_{0}(r+1)|}=2$, and
$\frac{r+1}{|u_{0}(r+1)|}=3$ using Theorems 3.2 and 3.4, respectively.

Now, let us suppose that $1\leq k\leq C_{r+1}$. Then
$u(x)=(x+1)+(x-r-1)\cdots(x-r-k)g(x)$, for some polynomial $g(x)$ with
$g(r+k+1)\neq 0$, and $u_{k}(r+1)\neq\pm 1$, as otherwise, $u(r+k+1)=r+k+2$ or
$r+k$, which, in the first case, goes against the definition of $k$, and in
the second case, give a non-nilpotent polynomial at $r+1$. Also
$-(r+k+1)=\sum\limits_{i=k}^{m-1}u_{i}(r+1)\equiv 0\pmod{u_{k}(r+1)},$ i.e.,
$u_{k}(r+1)|r+k+1$. Let $p\in P(u_{k}(r+1))$. Then $p$ must also divide
$r+k+1$ and $u(0)$. Note that
$|u_{k}(r+1)|=|u(r+k+1)-(r+k+1)|=|(r+k+2)+k!g(r+k+1)-(r+k+1)|=|1+k!g(r+k+1)|$,
i.e., $p|1+k!g(r+k+1)$. Since $p|r+k+1$, one deduces that $p|1+k!g(0)$. So, in
particular, one has $|u_{k}(r+1)|>k$. Define
$v(x)=\frac{1}{|u_{k}(r+1)|}u(|u_{k}(r+1)|x)$, then $v\in
N_{\frac{r+k+1}{|u_{k}(r+1)|},m-k}$, with
$\frac{r+k+1}{|u_{k}(r+1)|}=\frac{r}{|u_{k}(r+1)|}+\frac{k+1}{|u_{k}(r+1)|}<r+1$.
One immediately sees that if $r\geq 6$, then, in particular, one has $k\leq
C_{r}\leq\frac{r}{2}$. This will be useful in case 2 below.

Case 1. Let $r=4$ and $1\leq k\leq C_{5}=3$. First suppose that
$\frac{r+k+1}{|u_{k}(5)|}=\frac{5+k}{|u_{k}(5)|}\in\\{1,2,3\\}$. Note that $k$
cannot be 3 here, as otherwise $|u_{k}(5)|\in\\{4,8\\}$, and that implies
$u(5)=6,u(6)=7,u(7)=8,u(8)\in\\{0,4,12,16\\}$; however,
$2|u(8)-u(6)\in\\{-7,-3,5,9\\}$, which is false. That means $k\in\\{1,2\\}$.
If $\frac{5+k}{|u_{k}(5)|}=1$, then Fact 1.1 one obtains $m-k\leq 3$, i.e.,
$m\leq k+3\leq 5=r+1$. Similarly, one treats the possibilities
$\frac{5+k}{|u_{k}(5)|}=2$, and $\frac{5+k}{|u_{k}(5)|}=3$ using Theorems 3.2
and 3.4, respectively.

Now suppose that $4\leq\frac{5+k}{|u_{k}(5)|}~{}(<5)$, i.e.,
$\frac{5+k}{|u_{k}(5)|}=4$. Then $k$ must be 3, i.e., $|u_{k}(5)|=2$. That
means $u(5)=6,u(6)=7,u(7)=8,u(8)=10$; however, $2|u(8)-u(6)=3$, which is
false. So this cannot happen.

Case 2. Let $r\geq 5$ and $1\leq k\leq C_{r+1}$. First suppose that
$\frac{r+k+1}{|u_{k}(r+1)|}\in\\{1,2,3\\}$. If $\frac{r+k+1}{|u_{k}(r+1)|}=1$,
then by Fact 1.1 one has $m-k\leq 3$, i.e., $m\leq k+3\leq r+1$. Similarly,
one treats the possibilities $\frac{r+k+1}{|u_{k}(r+1)|}=2$, and
$\frac{r+k+1}{|u_{k}(r+1)|}=3$ using Theorems 3.2 and 3.4, respectively.

Now suppose that $\frac{r+k+1}{|u_{k}(r+1)|}\geq 4$. Then by the induction,
one has $m-k\leq\frac{r+k+1}{|u_{k}(r+1)|}$, i.e., $m\leq
k+\frac{r+k+1}{|u_{k}(r+1)|}\leq\frac{r}{2}+k+1\leq\frac{r}{2}+\frac{r+1}{2}+1=r+\frac{3}{2}$.
Since $m$ is an integer, it follows that $m\leq r+1$. ∎

The next corollary in immediate from Theorem 4.1 and Fact 2.4.

######  Corollary 4.2.

If $r$ is an integer less than $-3$, and $u\in N_{r,m}$, for some $m$, then
one $m\leq|r|$.

We use similar techniques as that of Theorem 4.1 to prove our second main
result.

######  Theorem 4.3.

If $r$ is an integer greater than 3, and $u\in N_{r,r}$, then

$u(x)=(x-1)+(x-1)\cdots(x-r)p(x),$

for some non-zero $p(x)\in\mathbb{Z}[x]$.

###### Proof.

We will use induction on $r$, and use the method of proof of Theorem 4.1. The
base case follows from Theorem 3.5. Let $r$ be a positive integer greater than
or equal to 4, and that the statement is true for every integer $q$ with
$4\leq q\leq r$. Also suppose that $u\in N_{r+1,r+1}$. Let $u_{i}(r+1)$’s be
as in (1.2), and $k$ be an integer satisfying (2.3) for the given $u$ and
$r+1$. Then we claim that $k=0$. Suppose, if possible, $1\leq k\leq C_{r+1}$.
Then one can define $v$ as in the third paragraph of the proof of Theorem 4.1,
and deduce that $v\in N_{\frac{r+k+1}{|u_{k}(r+1)|},r+1}$. Then
$\frac{r+k+1}{|u_{k}(r+1)|}\leq 3$, as otherwise, one notices
$r+1\leq\frac{r+k+1}{|u_{k}(r+1)|}=\frac{r}{|u_{k}(r+1)|}+\frac{k+1}{|u_{k}(r+1)|}<r+1$,
which cannot be true. If $\frac{r+k+1}{|u_{k}(r+1)|}\in\\{1,2\\}$, then by
Corollary 4.2, one has $r+1\leq\frac{r+k+1}{|u_{k}(r+1)|}+2\leq 4$, an
impossibility as $r\geq 4$. However, if $\frac{r+k+1}{|u_{k}(r+1)|}=3$, then
by Theorem 3.3, $r+1\leq\frac{r+k+1}{|u_{k}(r+1)|}=3$, again an impossibility
as $r\geq 4$.

Thus $k=0.$ The $u_{0}(r+1)$ cannot be $1$. If $u_{0}(r+1)=-1$, then
$u(r+1)=r$, i.e., $u\in N_{r,r}$. So by the induction hypothesis,
$u(x)=(x-1)+(x-1)\cdots(x-r)p(x)$, with $p(r+1)=0$, and that means $p(x)$ has
a linear factor $x-r-1$. Now suppose $|u_{0}(r+1)|>1$. Then one defines $v$ as
in the second paragraph of the proof of Theorem 4.1, and deduce that $v\in
N_{\frac{r+1}{|u_{0}(r+1)|},r+1}$. Corollary 4.2 then implies that
$r+1\leq\frac{r+1}{|u_{0}(r+1)|}+2,$ i.e.,
$r\leq\frac{|u_{0}(r+1)|+1}{|u_{0}(r+1)|-1}\leq 3$, which is false, as $r\geq
4$. This completes the proof. ∎

From Theorem 4.3 and Fact 2.4 it follows that

######  Corollary 4.4.

If $r$ is an integer less than $-3$, and $u\in N_{r,|r|}$, then

$u(x)=(x+1)+(x+1)\cdots(x+r)p(x),$

for some non-zero $p(x)\in\mathbb{Z}[x]$.

###  4.2 Infinitely Nilpotent Polynomials over $\mathbb{Z}$

We first make the following two definitions.

######  Definition 4.5.

Let $r\in\mathbb{Z}$, and $u\in N_{r,m}$ for some $m$. If $0$ appears in
$\mathcal{O}_{u}(r)$ infinitely many times, then we say $u$ is an infinitely
nilpotent polynomial at $r$. Also, we say an integer sequence
$\\{r_{n}\\}_{n\geq 0}$ is an infinitely nilpotent sequence if $r_{n}=0$ for
infinitely many $n$’s.

######  Definition 4.6.

Let $\\{r_{n}\\}_{n\geq 0}$ be an integer sequence. We say that a polynomial
$u$ is a generating polynomial of $\\{r_{n}\\}_{n\geq 0}$, or $u$ satisfies
$\\{r_{n}\\}_{n\geq 0}$ if for each $n\in\mathbb{N}$, $u^{(n)}(r_{0})=r_{n}$.

We now state and prove the following theorem.

######  Theorem 4.7.

Let $\\{r_{n}\\}_{n\geq 0}$ be an integer sequence, and $u$ satisfies
$\\{r_{n}\\}_{n\geq 0}$. Then the following are equivalent:

  1. (a)

The sequence $\\{r_{n}\\}_{n\geq 0}$ is an infinitely nilpotent sequence.

  2. (b)

There exists a positive integer $m$ such that either $r_{m}=r_{m+1}=0$, or
$r_{m}=r_{m+2}=0$.

###### Proof.

The fact that $(b)$ implies $(a)$ is clear. Therefore we only prove that $(a)$
implies $(b)$. We pick two positive integers $m\text{ and }q$ with $m<q$, such
that $r_{m}=r_{q}=0$. That means $u$ is nilpotent at $0$. It follows from Fact
1.4 that $q\in\\{m+1,m+2\\}$. If $q=m+1$, then $\\{r_{n}\\}_{n\geq 0}$ is of
the form

$r_{0},\ldots,r_{m-1},0,0,\ldots$ (4.4)

and one has $r_{n}=u^{(n)}(r_{0})=0$ for every $n\geq m$, and if $q=m+2$, then
$\\{r_{n}\\}_{n\geq 0}$ is of the form

$r_{0},\ldots,r_{m-1},0,r_{m+1},0,\ldots$ (4.5)

and one has $r_{n}=u^{(n)}(r_{0})=0$ for every $n\in\\{m+2k~{}|~{}k\geq 0\\}$.
∎

######  Remark 4.8.

One can see that if $\\{r_{n}\\}_{n\geq 0}$ is an integer sequence satisfying
condition (b) of Theorem 4.7, then, in particular, $\\{r_{n}\\}_{n\geq 0}$ is
a bounded sequence, i.e., $m\leq r_{n}\leq M$ for every $n\geq 0$, where
$m:=\text{min}\\{r_{0},\ldots,r_{p-1},0,r_{p+1}\\}$, and
$M:=\text{max}\\{r_{0},\ldots,r_{p-1},0,r_{p+1}\\}$.

From Theorem 4.7 we know that all the infinitely nilpotent sequences must be
of one of the forms (4.4) or (4.5). We would like to classify such sequences.
The next two theorems are dedicated for that.

######  Theorem 4.9.

Let $m$ be a non-negative positive integer, and $\\{r_{n}\\}_{n\geq 0}$ be an
infinitely nilpotent sequence of the form $(4.4)$, where we assume that
$(4.4)$ is the zero sequence if $m=0$. When $m\geq 1$, we suppose that
$0\not\in\\{r_{0},\ldots,r_{m-1}\\}$. Also suppose that $u$ is a generating
polynomial of $\\{r_{n}\\}_{n\geq 0}$. Then exactly one of the following
holds:

  1. (1)

$m=1$, and then $r_{0}$ is arbitrary; and

  2. (2)

$m=2$, and then one has $r_{0}|2$, and $r_{1}=2r_{0}$.

###### Proof.

It is enough to consider the case $m\geq 1$. The given conditions on $u$, in
particular, implies that $u\in N_{0,1}$. Then by Fact 1.4, one obtains
$u(x)=xp(x)$, for some non-zero polynomial $p$, so, in particular,
$r_{0}|r_{1}|\cdots|r_{m-1}$. Define $v(x)=\frac{1}{r_{0}}u(r_{0}x)$. Then $v$
is nilpotent at $1$ of index $m$ with $v(0)=0$. From Fact 1.2 it follows that
$v$ must be of one of the following forms:

  1. (i)

$v(x)=x(x-1)Q(x)$ for some non-zero polynomial $Q$. In this case $m=1$, i.e.,
the above sequence is $r_{0},0,0,\ldots$, and $u(x)=x(x-r_{0})P(x)$, where
$P(x)=\frac{1}{r_{0}}u\left(\frac{x}{r_{0}}\right)$ .

  2. (ii)

$v(x)=-2x+4+Q(x)(x-1)(x-2)$ with $Q(0)=-2$. In this case $m=2$, i.e., the
above sequence is $r_{0},r_{1},0,0,\ldots$, and
$u(x)=-2x+4r_{0}+P(x)(x-r_{0})(x-r_{1})$, where
$P(x)=\frac{1}{r_{0}}Q\left(\frac{x}{r_{0}}\right)$ with
$P(0)=-\frac{2}{r_{0}}$, i.e., one requires $r_{0}|2$. One also has
$r_{1}=u(r_{0})=2r_{0}$.

This completes the proof. ∎

######  Theorem 4.10.

Let $\varepsilon\in\\{\pm 1\\}$, $m$ a non-negative integer,
$\\{r_{n}\\}_{n\geq 0}$ an infinitely nilpotent sequence of the form $(4.5)$,
and $u$ be a generating polynomial of $\\{r_{n}\\}_{n\geq 0}$. Then one of the
following holds:

  1. (1)

$m=0$, and then $r_{1}$ is arbitrary;

  2. (2)

$m=1$, and then either $r_{0}=r_{2}$, or, $r_{0}=\varepsilon$;

  3. (3)

$m=2$, and then either $r_{3}=r_{1}=r_{0}+\varepsilon$, or,
$r_{0}=2\varepsilon,r_{1}=\varepsilon,\text{ and }r_{3}=3\varepsilon$; and

  4. (4)

$m=3$, and then $r_{0}=\varepsilon,r_{1}=2\varepsilon,\text{ and
}r_{4}=r_{2}=3\varepsilon$.

###### Proof.

Let $v(x)=u^{(2)}(x)$. One readily notices that if $m$ is even (respectively,
$m$ is odd), the sequence of iterations of $v$ starting at $r_{0}$
(respectively, starting at $r_{1}$) will be of the form (4.4). Then by Theorem
4.7 it follows that $m$ cannot exceed 6. Therefore it is enough to look at the
following cases.

Case 1. Let $m=0$, i.e., $r_{0}=0$ and $r_{1}\neq 0$. Then $u(x)=r_{1}-x$
satisfies (4.5).

Case 2. Let $m=1$. Then the sequence looks like $r_{0},0,r_{2},0,\ldots$. From
Fact 1.4 it follows that there is a polynomial $p$ such that
$u(x)=(x-r_{2})(xp(x)-1)$. That means, in particular,
$0=(r_{0}-r_{2})(r_{0}p(r_{0})-1),$ i.e., $r_{0}=r_{2}$, or
$r_{0}=\varepsilon$.

  * •

If $r_{0}=r_{2}$, then $u(x)=r_{0}-x$ satisfies (4.5).

  * •

If $r_{0}=\varepsilon$, then $u(x)=\varepsilon(x-r_{2})(x-\varepsilon)$
satisfies (4.5).

Case 3. Let $m=2$. Then the sequence looks like
$r_{0},r_{1},0,r_{3},0,\ldots$. Then by Fact 1.3 it follows that
$u(x)=(x-r_{3})(xp(x)-1)$ for some polynomial $p$. That means, in particular,
$0=(r_{1}-r_{3})(r_{1}p(r_{1})-1)$, i.e., either $r_{1}=r_{3}$, or $r_{1}=\pm
1$. One also has $r_{1}=(r_{0}-r_{3})(r_{0}p(r_{0})-1)$.

  1. (i)

If $r_{1}=r_{3}$, then $r_{1}=(r_{0}-r_{3})(r_{0}p(r_{0})-1)$ implies, in
particular, that $r_{1}=r_{0}+\varepsilon$. It is easy to check that
$u(x)=\varepsilon(r_{1}-x)(x+\varepsilon)$ satisfies (4.5).

  2. (ii)

If $r_{1}=\varepsilon$ and $r_{1}\neq r_{3}$, then a polynomial $u$ satisfying
(4.5) must be in $N_{1,\varepsilon}$. Suppose $\varepsilon=1$. By Fact 1.1, it
follows that $u(x)=(x-1)p(x)$ for some polynomial $p$. Since $u(r_{0})=1$, one
has $r_{0}=2$ and $p(2)=1$. Also, $r_{3}\neq 1$ and $u(r_{3})=0$ implies that
$p(r_{3})=0$. Note that one also has $p(0)=-u(0)=-r_{3}$. Thus, by Fact 1.4,
$p(x)$ must be of the form $(x-r_{3})(xq(x)-1)$ for some polynomial $q$.
However, using the fact that $p(2)=1$, one immediately sees that
$1=(2-r_{3})(2q(2)-1)$, which is only possible if $r_{3}=3$. Then
$u(x)=(x-1)^{2}(3-x)$ satisfies (4.5). Similarly, when $r_{1}=-1$, one can
show that $r_{0}=-2,r_{3}=-3$, and that $u(x)=-(x+1)^{2}(x+3)$ satisfy (4.5).

Case 4. Let $m=3$. Then the sequence looks like
$r_{0},r_{1},r_{2},0,r_{4},0,\ldots.$ Then by Fact 1.4 it follows that
$u(x)=(x-r_{4})(xp(x)-1)$ for some polynomial $p$, and so
$0=u(r_{2})=(r_{2}-r_{4})(r_{2}p(r_{2})-1)$ implies, in particular, that
$r_{2}=r_{4}$ or $r_{2}=\varepsilon$. Let us consider the truncated sequence
$r_{1},r_{2},0,r_{4},0,\ldots$.

If $r_{2}=r_{4}$, then from case 3(i) it follows that
$r_{2}=r_{1}+\varepsilon$. This means (4.5) must look like
$r_{0},r_{1},r_{1}+\varepsilon,0,r_{1}+\varepsilon,0\ldots$. Suppose that
$\varepsilon=1$. One immediately sees that $r_{1}-r_{0}|u(r_{1})-u(r_{2})=1$,
i.e., $r_{0}=r_{1}\pm 1$. Since $r_{2}=r_{1}+1=(r_{0}\pm 1)+1$, and $r_{2}\neq
r_{0}$, one has $r_{1}=r_{0}+1$ and $r_{2}=r_{0}+2$. By Fact 1.4 it follows
that $u(x)=(x-r_{0}-2)Q(x)$ for some polynomial $Q$ with $Q(0)=-1$. However,
then $r_{0}+1=u(r_{0})=2-2r_{0}Q(r_{0})$, i.e., $r_{0}(1+2Q(r_{0}))=1$, i.e.,
$r_{0}=1$ (as $r_{0}=-1$ means $r_{1}=0$). One sees that
$u(x)=-x^{3}+4x^{2}-4x+3$ satisfies (4.5). Similarly, when $\varepsilon=-1$,
one can show that $r_{0}=-1,r_{1}=-2,r_{2}=-3$, and taking
$u(x)=-x^{3}-4x^{2}-4x-3$ suffices.

If $r_{2}=\varepsilon$, then one can see from case 3(ii) that
$r_{1}=2\varepsilon,r_{2}=\varepsilon,r_{4}=3\varepsilon$, and $u$ satisfying
the truncated sequence must be of the form
$(x-\varepsilon)(x-3\varepsilon)(xq(x)+\varepsilon)$ for some polynomial $q$
with the property that $q(2\varepsilon)=-1$. Now, when we go back to the
original sequence (4.5), it is clear that
$r_{0}\not\in\\{0,\varepsilon,2\varepsilon,3\varepsilon\\}$. However, then
$2\varepsilon=u(r_{0})=(r_{0}-\varepsilon)(r_{0}-3\varepsilon)(r_{0}q(r_{0})+\varepsilon)$,
which cannot happen as
$r_{0}\not\in\\{0,\varepsilon,2\varepsilon,3\varepsilon\\}$.

Case 5. Let $m=4$. Then the sequence looks like
$r_{0},r_{1},r_{2},r_{3},0,r_{5},0,\ldots$. As the sequence of iterations of
$v$ starting at $r_{0}$ is of the form (4.4), and $r_{2}\neq 0$, it follows
from Theorem 4.9 that $r_{0}|2$ and $r_{0}|2r_{2}$. If $r_{0}=\varepsilon$,
then $r_{2}=2\varepsilon$, and so it follows from either Fact 1.1 or Fact 1.2
that no $u$ can satisfy (4.5). Therefore $r_{0}=2\varepsilon$.

If $r_{0}=2$, then $r_{2}=4$ and $u\in N_{2,4}$, and so it follows from the
list in Theorem 3.2, that a polynomial $u$ satisfying (4.5) must be of the
form $(5-x)(x^{2}-4x+5)+p(x)(x-2)(x-3)(x-4)(x-5)$, for some polynomial $p$,
and also that $r_{1}=3$ and $r_{3}=5$. We claim that $r_{5}$ must be $5$. Let
$Q(x)=x^{2}-4x+5-p(x)(x-2)(x-3)(x-4)$. Then $u(x)=(5-x)Q(x)$. Suppose, if
possible, $r_{5}\neq 5$. As $0=u(r_{5})=(5-r_{5})Q(r_{5})$, one has
$Q(r_{5})=0$, i.e., $Q(x)=(x-r_{5})\tilde{Q}(x)$, for some polynomial
$\tilde{Q}$, so that $u(x)=(5-x)(x-r_{5})\tilde{Q}(x)$. However, that means
$r_{5}=u(0)=-5r_{5}\tilde{Q}(0)$, which is impossible as $r_{5}\neq 0$. Thus
$r_{5}$ must be 5. Hence, $5=u(0)=5Q(0)=5(5+24p(0))$, i.e., $1=5+24p(0)$,
i.e., $p(0)=-1/6$, which is impossible. Similarly, one can reject the
possibility that $r_{0}=-2$.

Now one readily sees that $m=5$ is not possible.∎

It should be noted that for Theorems 4.9 and 4.10, if we allow the generating
polynomial $u$ to be a polynomial over $\mathbb{Q}$, then we can always use
Lagrange’s interpolation to obtain such a polynomial no matter how large the
$m$ is, and so the restriction on $m$ that we get in the proof heavily depends
on the fact that $u\in\mathbb{Z}[x]$. Therefore this is really a question of
iterations of integer polynomials.

We end this paper by deriving an interesting result about bounded integer
sequences which is a consequence of Theorems 4.9 and 4.10.

######  Corollary 4.11.

Let $\\{r_{n}\\}_{n\geq 0}$ be a bounded sequence, and $u$ satisfies
$\\{r_{n}\\}_{n\geq 0}$. Then there is an integer $S$, and an integer $m$ with
$0\leq m\leq 3$, such that one of the following holds:

  * •

$m=0$, and either $r_{n}=S$ for every $n\geq 0$, or
$r_{2n}=S,~{}r_{2n+3}=r_{1}$ for every $n\geq 0$;

  * •

$m=1$, and either $r_{n}=S$ for every $n\geq 1$,

$\text{ or }r_{0}=s_{0}+S,~{}r_{2n-1}=S,~{}r_{2n+2}=r_{2}\text{ for every
}n\geq 1;$

  * •

$m=2$, and either $s_{0}|2,~{}r_{0}=s_{0}+S,~{}r_{1}=2s_{0}+S,~{}r_{n}=S$ for
every $n\geq 2$,

$\text{ or }r_{0}=s_{0}+S,~{}r_{2n-1}=s_{0}+S+\varepsilon,~{}r_{2n}=S\text{
for every }n\geq 1,$

$\text{ or
}r_{0}=2\varepsilon+S,~{}r_{1}=\varepsilon+S,~{}r_{2n}=S,~{}r_{2n+1}=3\varepsilon+S,\text{
for every }n\geq 1;$

  * •

$m=3$, and
$r_{0}=\varepsilon+S,~{}r_{1}=2\varepsilon+S,~{}r_{2n}=3\varepsilon+S,~{}r_{2n+1}=S$
for every $n\geq 1$;

where $s_{0}=r_{0}-S$, and $\varepsilon\in\\{\pm 1\\}$.

###### Proof.

As $\\{r_{n}\\}_{n\geq 0}$ is bounded, one obtains, in particular, that there
is an integer $S$ such that $r_{n}=S$ for infinitely many $n$’s. Define

$s_{n}:=r_{n}-S~{}(n\geq 0)\textup{, and }v(x):=u(x+S)-S.$

Then $\\{s_{n}\\}_{n\geq 0}$ is infinitely nilpotent, and $v$ satisfies
$\\{s_{n}\\}_{n\geq 0}$ as for each $n\geq 0$, one obtains, by induction, that
$v^{(n)}(x-S)=u^{(n)}(x)-S$. Thus it follows from the proof Theorem 4.7 that
$\\{s_{n}\\}_{n\geq 0}$ is must be of one of the forms (4.4) and (4.5). The
rest follows from Theorems 4.9 and 4.10. ∎

Acknowledgements. The author gratefully acknowledges his advisor, Professor
Alexander Borisov, for his invaluable suggestions and guidance on this paper,
without which this work would not have seen the light of day.

## References

  * [1] A. Borisov, Iterations of integer polynomial maps modulo primes, J. Integer Seq, Vol. 16 (2013), Article 13.8.3
  * [2] S. Sengupta, Locally nilpotent polynomials over $\mathbb{Z}$, Integers, no. 3851.