# Time-Fuel-Optimal Navigation of a Commercial Aircraft in Cruise with Heading
and Throttle Controls using Pontryagin’s Maximum Principle

Amin Jafarimoghaddam and Manuel Soler Amin Jafarimoghaddam is with the
Department of Aerospace Engineering, Universidad Carlos III de Madrid,
Leganes, Madrid, Spain<EMAIL_ADDRESS>Soler is with the Department
of Aerospace Engineering, Universidad Carlos III de Madrid, Leganes, Madrid,
Spain<EMAIL_ADDRESS>
###### Abstract

In this research, we consider the commercial aircraft trajectory optimization
problem for a general cruise model with arbitrary spatial wind fields to be
solved using the Pontryagin’s maximum principle. The model features two
fundamental controls, namely ”throttle setting” (which appears as a singular
control) and ”heading angle” (appearing as a regular control). For a
constrained problem with minimum time-fuel objective, we show that the optimal
heading angle is fully defined through the classic Zermelo’s navigation
identity. We also show that the optimal throttle setting can be characterized
through a complete feedback function. The switching-point algorithm is
employed to solve a case study where we inspect the optimality conditions and
graph the optimal controls together with the optimal state and co-state
variables.

##  I Introduction

The agencies associated with commercial aircraft flights are inquisitively in
demand of new optimization tools to minimize the direct operating cost, i.e.,
a combination of the fuel burn and the arrival time. The optimization of
commercial aircraft trajectories has been the subject of extensive research,
with a variety of optimization techniques having been applied, however, the
Pontryagin’s maximum principle, has received comparatively little attention in
the literature [1].

Here, we rely on the Pontryagin’s maximum principle to solve minimum time-fuel
commercial aircraft trajectory optimization problem for a general cruise model
in the presence of an arbitrary spatial wind field.

Focusing only on those approaches using the Pontryagin’s maximum principle,
the commercial aircraft navigation problem in the cruise phase with various
cost functions has been solved in [2, 3, 4, 5, 6, 7, 8]. More specifically,
the range-optimal problem has been solved in [2]. The same problem was
revisited w.r.t. the compressibility effects in [3]. Also, the fuel-optimal
cruise at constant altitude with fixed arrival time has been solved in [4].
Likewise, the fuel-optimal problem in a vertical plane (including the cruise
phase) has been solved for structured flight segments in [5]. The fuel-optimal
problem in the cruise phase with a one-dimensional uniform wind field and
fixed arrival time has been solved in [6]. Approaches considering climate
impact, such as [7], also exist in the literature, in which the contrails
avoidance problem in the cruise phase was solved. Nevertheless, the study in
[7] ignores the speed dynamic and the derivative of the Hamiltonian w.r.t. the
aircraft’s mass and obtains a more general navigation formula. The direct
operating cost with multiple cruise altitudes in the presence of wind has been
addressed in [8]. It is noteworthy that the speed dynamic has been ignored in
the latter.

To summarize, the reviewed literature ([2, 3, 4, 5, 6, 7, 8]) mainly focuses
on simplified cruise models with only one active control (either ”throttle
setting”, or ”heading angle”). However, solving the optimal control problem
associated with a general cruise model using the Pontryagin’s maximum
principle is particularly challenging due to the involvement of the two
controls. In this research, we tackle this challenge and solve the problem for
the first time.

In this research, we consider a generic (realistic) cruise model, comprising
of two active controls. The controls are: 1) the heading angle (a regular
control), and, 2) the throttle setting (a singular control). The objective is
to minimize the direct operating cost. We show that the optimal heading angle
is fully characterized through the classic Zermelo’s navigation identity even
if the problem is subject to some standard state-inequality constraints (the
classic Zermelo’s navigation identity is the time-optimal, constant-speed
navigation problem between two points inside a fluid flow [9]). For the
optimal throttle setting, we employ successive derivatives of the switching
function and leverage the optimality information related to the heading angle
to characterize this singular control as a complete feedback function. In this
respect, we show (through analyzing the switching function), that the optimal
throttle setting is dependent on the optimal heading angle.

The switching-point algorithm [10] is employed to solve a case study where the
state-inequality constraints are inactive. In short, the switching-point
algorithm runs a nonlinear programming only over the switching times and
(possibly) some other scalar unknowns with a given control feedback. The
switching-point algorithm, as in [10], is for a singular control problem
without state-inequality constraints. Moreover, in [10], the decision
variables can be the switching times and values of co-states at the entry of a
singular arc. It is noteworthy that the study in [10] is an extension to the
previous works in this discipline (see e.g., [11] and [12]).

##  II Problem Statement

The point-mass dynamics are commonly used to generate aircraft trajectories
[13], [14]. For commercial aircraft flights in cruise phase, the point-mass
equations in Cartesian framework can be approximated as [15]:

$\begin{split}&\frac{dx}{dt}=v(t)\cos{(\chi(t))}+w_{x}(x(t),y(t),h)=:F_{x},\\\
&\frac{dy}{dt}=v(t)\sin{(\chi(t))}+w_{y}(x(t),y(t),h)=:F_{y},\\\
&\frac{dv}{dt}=\frac{\Pi(t)T_{max}(h)-D(m(t),v(t),h)}{m(t)}=:F_{v},\\\
&\frac{dm}{dt}=-\Pi(t)C_{s}(v(t))T_{max}(h)=:F_{m}.\\\ \end{split}$ (1)

In Eq. (1), $x$, and $y$ are geometric variables, i.e., the cruise flight
occurs in a horizontal $x-y$ plane, $v$ is the aerodynamic speed, $m$ is the
aircraft mass, and $t$ is time. In addition, $w_{x}$ and $w_{y}$ are $x$, and
$y$ components of wind respectively ($w_{x}$ and $w_{y}$ are known geometrical
functions), $h$ is a constant altitude where the cruise flight occurs,
$T_{max}$ is the maximum thrust force, $D$ is the drag force, and $C_{s}$ is
the fuel flow. The controls are the heading angle ($\chi(t)$) and the throttle
setting ($\Pi(t)$).

The objective is:

$\begin{split}\min_{\chi(t),\Pi(t),t_{f}}\mathcal{J}=\alpha
t_{f}+(\alpha-1)m(t_{f}),\quad 0\leq\alpha\leq 1.\end{split}$ (2)

Where $t_{f}$ denotes the final time.

The cruise flight envelope is defined by the dynamic constraints described in
Eq. (1) , along with the following set of standard state-inequality
constraints:

$\begin{split}&M_{min}\leq M(h,v(t))\leq M_{max},\\\ &v_{CAS,min}\leq
v_{CAS}(h,v(t))\leq v_{CAS,max},\\\ &\quad\quad\quad\quad\forall
t\in[t_{0},t_{f}].\end{split}$ (3)

and boundary conditions:

$\begin{split}&x(t_{f})=x_{f},\quad y(t_{f})=y_{f},\quad v(t_{f})=v_{f},\\\
&x(t_{0})=x_{0},\quad y(t_{0})=y_{0},\quad v(t_{0})=v_{0},\quad
m(t_{0})=m_{0}.\end{split}$ (4)

In above, $t_{0}$ is the initial time, $M$ is the $Mach$ number, and $v_{CAS}$
is the calibrated airspeed [16]. Moreover,
$x_{f},y_{f},v_{f},x_{0},y_{0},v_{0},$ and $m_{0}$ are known values assigned
for the boundary conditions.

The controls are also constrained as:

$\begin{split}&\Pi_{min}\leq\Pi(t)\leq\Pi_{max},\\\
&\chi_{min}\leq\chi(t)\leq\chi_{max},\\\ &\quad\quad\forall
t\in[t_{0},t_{f}].\end{split}$ (5)

It is noteworthy that, for the succeeding analysis, only the functionality of
$w_{x}$, $w_{y}$, $T_{max}$, $D$, $C_{s}$, $Mach$, and $V_{CAS}$ is of
relevance. Nonetheless, these terms will be elaborated in our case study (see
sec.IV).

###  II-A Compact Form Notation

The optimal control problem considered, can be written in a compact form
notation as:

$\begin{split}&\min_{U(t),t_{f}}\mathcal{J}=\Phi({X}_{f},t_{f}),\\\ &s.t.,\\\
&\frac{d{X}}{dt}=F(X(t),U(t)),\\\ &\mathcal{C}(U(t))\leq
0,\quad\mathcal{S}(X(t))\leq 0,\quad\forall t\in[t_{0},t_{f}],\\\
&\phi_{0}(X_{0})=0,\quad\phi_{f}(X_{f})=0.\\\ \end{split}$ (6)

Where $X^{T}(t)=[x(t),y(t),v(t),m(t)]$, $F^{T}=[F_{x},F_{y},F_{v},F_{m}]$,
$\phi_{0}(X_{0})=X_{0}-X(t_{0})$, $\phi_{0}\in\mathbb{R}^{4}$,
$\phi_{f}(X_{f})=X_{f}-X(t_{f})$, $\phi_{f}\in\mathbb{R}^{3}$,
$U^{T}(t)=[\chi(t),\Pi(t)]$, and $\Phi(X_{f},t_{f})=\alpha
t_{f}+(\alpha-1)m(t_{f})$. The inequality constraints are:

$\begin{split}&\mathcal{C}(U(t))=\begin{pmatrix}\chi(t)-\chi_{max}\\\
\chi_{min}-\chi(t)\\\ \Pi(t)-\Pi_{max}\\\
\Pi_{min}-\Pi(t)\end{pmatrix}\end{split}.$ (7)
$\begin{split}&\mathcal{S}(X(t))=\begin{pmatrix}M(t)-M_{max}\\\
M_{min}-M(t)\\\ v_{CAS}(t)-v_{CAS,max}\\\ v_{CAS,min}-v_{CAS}(t)\\\
\end{pmatrix}.\end{split}$ (8)

By directly adjoining the constraints, we can define an augmented cost as (see
e.g. [17]):

$\begin{split}&\bar{\mathcal{J}}:=\Phi(X_{f},t_{f})+\langle\nu_{0},\phi_{0}(X_{0})\rangle+\langle{\nu}_{f},{\phi}_{f}(X_{f})\rangle+\\\
&\int_{t_{0}}^{t_{f}}\bigg{(}\langle\lambda(t),F(X(t),U(t))-\frac{dX}{dt}\rangle+\langle\mu(t),\mathcal{C}(U(t))\rangle+\\\
&\langle\eta(t),\mathcal{S}(X(t))\rangle\bigg{)}dt.\end{split}$ (9)

In the above equation, the scalar multipliers are denoted by
$\nu_{0}\in\mathbb{R}^{4}$, and $\nu_{f}\in\mathbb{R}^{3}$, while the
inequality multipliers are represented by
$\mu^{T}(t)=[\mu^{\chi}_{u}(t),\mu^{\chi}_{l}(t),\mu^{\Pi}_{u}(t),\mu^{\Pi}_{l}(t)]$,
and $\eta(t)\in\mathbb{R}^{4}$. Additionally, the co-states are given by
$\lambda^{T}(t)=[\lambda_{x}(t),\lambda_{y}(t),\lambda_{v}(t),\lambda_{m}(t)]$.

For this optimal control problem, the Hamiltonian is defined as [17]:

$\begin{split}&\mathcal{H}(X(t),U(t),\lambda(t),\mu(t),\eta(t)):=\\\
&\langle\lambda(t),F(X(t),U(t))\rangle+\langle\mu(t),\mathcal{C}(U(t))\rangle+\\\
&\langle\eta(t),\mathcal{S}(X(t))\rangle.\end{split}$ (10)

The optimality conditions are:

$\begin{split}&\frac{\partial\mathcal{H}}{\partial U}=0,\\\
&\langle\mu(t),\mathcal{C}(U(t))\rangle=0,\quad\mu(t)\geq 0,\quad\forall
t\in[t_{0},t_{f}],\\\
&\langle\eta(t),\mathcal{S}(X(t))\rangle=0,\quad\eta(t)\geq 0,\quad\forall
t\in[t_{0},t_{f}].\\\ \end{split}$ (11)

The co-state dynamics and the transversality conditions read:

$\begin{split}&\frac{d{\lambda}^{T}}{dt}=-\frac{\partial\mathcal{H}}{\partial{X}},\\\
&{\lambda}_{0}:={\lambda}(t_{0})=-\big{[}\frac{\partial{\phi}_{0}}{\partial{X}_{0}}\big{]}^{T}{\nu}_{0},\\\
&{\lambda}_{f}:={\lambda}(t_{f})=\frac{\partial\Phi}{\partial
X_{f}}+\big{[}\frac{\partial{\phi}_{f}}{\partial{X}_{f}}\big{]}^{T}{\nu}_{f},\\\
&\mathcal{H}_{f}:=\mathcal{H}(t_{f})=-\frac{\partial\Phi}{\partial
t_{f}}-{\nu}_{f}^{T}\frac{\partial{\phi}_{f}}{\partial t_{f}}.\end{split}$
(12)

Let $\tau$ be a possible time instant within the boundary arc at which the co-
state variables are discontinuous. The jump conditions at the junction times
read [18]:

$\begin{split}&\lambda^{T}(\tau^{-})=\lambda^{T}(\tau^{+})-\nu^{T}(\tau)\frac{\partial\mathcal{S}}{\partial
X}|_{t=\tau},\\\ &\nu(\tau)\geq
0,\quad\langle\nu(\tau),\mathcal{S}(X(\tau))\rangle=0.\end{split}$ (13)

##  III Classification of the Controls

The control problem defined through Eq. (1) to Eq. (5) is regular on the
heading angle ($\chi(t)$), and singular on the throttle setting ($\Pi(t)$).

In order to classify the controls, we write:

$\begin{split}&F(X(t),\chi(t),\Pi(t))=Q(X(t),\chi(t))+\Pi(t)P(X(t)).\end{split}$
(14)

In above:

$\begin{split}&Q(X(t),\chi(t))=\begin{pmatrix}v(t)\cos(\chi(t))+w_{x}(x(t),y(t),h)\\\
v(t)\sin(\chi(t))+w_{y}(x(t),y(t),h)\\\ -\frac{D(m(t),v(t),h)}{m(t)}\\\
0\end{pmatrix},\end{split}$ (15)

and,

$\begin{split}&P(X(t))=\begin{pmatrix}0\\\ 0\\\ \frac{T_{max}(h)}{m(t)}\\\
-C_{s}(v(t))T_{max}(h)\end{pmatrix}.\end{split}$ (16)

###  III-A The Optimal $\chi(t)$ (Heading Angle)

We initially note that the state-inequality constraints ($\mathcal{S}(X(t))$)
are functions of $v$, and $h$. Since $h$ is a constant, from Eq. (13), it is
straightforward to show that the jump condition (upon existence), applies only
to $\lambda_{v}(t)$.

The optimal $\chi(t)$, associated with the interior arc (
$\mu^{\chi}_{l}(t)=\mu^{\chi}_{u}(t)=0$), can be formulated through successive
time-derivatives of the first-order optimality condition for $\chi(t)$. To
this end, we write:

$\begin{split}&\frac{\partial\mathcal{H}}{\partial\chi}=0\rightarrow\langle\lambda(t),\frac{\partial
Q}{\partial\chi}\rangle=0\rightarrow\tan(\chi(t))=\frac{\lambda_{y}(t)}{\lambda_{x}(t)}.\\\
\end{split}$ (17)

The first time-derivative of Eq. (17) reads:

$\begin{split}&\frac{d}{dt}\tan(\chi(t))=\frac{\frac{d\lambda_{y}}{dt}\lambda_{x}(t)-\frac{d\lambda_{x}}{dt}\lambda_{y}(t)}{\lambda_{x}^{2}(t)}.\\\
\end{split}$ (18)

From Eq. (12),the co-state dynamics $\frac{d\lambda_{y}}{dt}$, and
$\frac{d\lambda_{x}}{dt}$ can be written as:

$\begin{split}&\frac{d\lambda_{x}}{dt}=-\big{(}\lambda_{x}(t)\frac{\partial
w_{x}}{\partial x}+\lambda_{y}(t)\frac{\partial w_{y}}{\partial x}\big{)},\\\
&\frac{d\lambda_{y}}{dt}=-\big{(}\lambda_{x}(t)\frac{\partial w_{x}}{\partial
y}+\lambda_{y}(t)\frac{\partial w_{y}}{\partial y}\big{)}.\end{split}$ (19)

Plugging Eq. (19) into Eq. (18), and with the help of Eq. (17), we obtain:

$\begin{split}&\frac{d\chi}{dt}\big{(}1+\tan(\chi(t))^{2}\big{)}=-\frac{\partial
w_{x}}{\partial y}+\\\ &\big{(}\frac{\partial w_{x}}{\partial
x}-\frac{\partial w_{y}}{\partial y}\big{)}\tan(\chi(t))+\big{(}\frac{\partial
w_{y}}{\partial x}\big{)}\tan(\chi(t))^{2}.\end{split}$ (20)

We observe that this equation is the Zermelo’s navigation identity [9].

Eq. (20) defines the optimal $\chi(t)$ for the interior arc even with active
state-inequality constraints. Moreover, with the assumption that $\chi(t)$ is
continuous in time, it will be straightforward to compute the boundary arc
too.

###  III-B The Optimal $\Pi(t)$ (Throttle Setting)

Let us assume that the state-inequality constraints are inactive, i.e.,
$\eta(t)=0,\forall t\in[t_{0},t_{f}]$.

The first-order optimality condition for $\Pi(t)$ reads:

$\begin{split}&\frac{\partial\mathcal{H}}{\partial\Pi}=0\rightarrow\langle\lambda(t),P(X(t))\rangle+\mu^{\Pi}_{u}(t)-\mu^{\Pi}_{l}(t)=0.\end{split}$
(21)

we define the switching function as:

$\begin{split}&S(t)=\langle\lambda(t),P(X(t))\rangle.\end{split}$ (22)

The bang-singular classification for the optimal $\Pi(t)$ is:

$\begin{split}\Pi(t)=\begin{cases}\Pi_{min}&S(t)>0,\\\ \Pi_{max}&S(t)<0,\\\
$undetermined$&S(t)=0.\end{cases}\end{split}$ (23)

The optimal $\Pi(t)$ is called bang-bang if $S(t)$ has isolated zeros on an
interval $I\subset[t_{0},t_{f}]$; whereas the optimal $\Pi(t)$ is called
singular if $S(t)=0$ holds for all $t\in I$.

For the singular $\Pi(t)$, since $S(t)=0$, we have:
$S^{(k)}(t):=\frac{d^{k}}{dt^{k}}S(t)=0,k=1,2,...$.

It can be checked that the singular $\Pi(t)$ appears in $S^{(2)}(t)$; that is
to say, order of the singular arc is one.

Since the Hamiltonian is not an explicit function of time, we have:
$\mathcal{H}(t)=constant$ ($\forall t\in[t_{0},t_{f}]$). Therefore, from Eq.
(12), we have: $\mathcal{H}(t)=-\alpha$. Moreover,
$\frac{\partial\mathcal{H}}{\partial\chi}=0$ holds at all times.

On using Eq. (14), the co-state dynamics can be written as:

$\begin{split}&\frac{d\lambda^{T}}{dt}=-\lambda^{T}(t)\big{(}\frac{\partial
Q}{\partial X}+\Pi(t)\frac{\partial P}{\partial X}\big{)}.\end{split}$ (24)

The first time-derivative of the switching function is computed as:

$\begin{split}&S^{(1)}(t)=\langle\frac{d\lambda}{dt},P(X(t))\rangle+\langle\lambda(t),\frac{dP}{dt}\rangle=0.\end{split}$
(25)

Noting that $\frac{dP}{dt}=\frac{\partial P}{\partial X}\frac{dX}{dt}$, it is
straightforward to show that $\Pi(t)$ drops from $S^{(1)}(t)$. As a result,
$S^{(1)}(t)$ can be expressed as follows:

$\begin{split}&S^{(1)}(t)=\langle\lambda(t),\mathcal{A}(X(t),\chi(t))\rangle.\end{split}$
(26)

In Eq. (26), the vector $\mathcal{A}$ is:

$\begin{split}&\mathcal{A}(X(t),\chi(t))=\frac{\partial P}{\partial
X}Q(X(t),\chi(t))-\frac{\partial Q}{\partial X}P(X(t)).\end{split}$ (27)

It should be noted that the vector $\mathcal{A}$ can also be represented using
Lie bracket notations.

We exploit the following set of algebraic equations to express the co-states
in explicit terms:

$\begin{split}&S(t)=0\rightarrow\langle\lambda(t),P(X(t))\rangle=0,\\\
&S^{(1)}(t)=0\rightarrow\langle\lambda(t),\mathcal{A}(X(t),\chi(t))\rangle=0,\\\
&\mathcal{H}(t)=-\alpha\rightarrow\langle\lambda(t),Q(X(t),\chi(t))\rangle=-\alpha,\\\
&\frac{\partial\mathcal{H}}{\partial\chi}=0\rightarrow\langle\lambda(t),\frac{\partial
Q}{\partial\chi}\rangle=0.\end{split}$ (28)

The above algebraic linear system can be simply solved by any platform
supporting symbolic computations such as MATLAB. To this end, we write the
solution to system (28) as:

$\begin{split}\det[\bar{\bar{\mathcal{M}}}]\begin{pmatrix}\lambda_{x}(t)\\\
\lambda_{y}(t)\\\ \lambda_{v}(t)\\\
\lambda_{m}(t)\end{pmatrix}=adj[\bar{\bar{\mathcal{M}}}]\mathcal{R}.\end{split}$
(29)

Where:

$\begin{split}\bar{\bar{\mathcal{M}}}=\begin{pmatrix}0&0&P_{3}&P_{4}\\\
\mathcal{A}_{1}&\mathcal{A}_{2}&\mathcal{A}_{3}&\mathcal{A}_{4}\\\
Q_{1}&Q_{2}&Q_{3}&0\\\ \tan(\chi(t))&-1&0&0\end{pmatrix},\end{split}$ (30)

and,

$\begin{split}\mathcal{R}=\begin{pmatrix}0\\\ 0\\\ -\alpha\\\
0\end{pmatrix}.\end{split}$ (31)

In Eq. (30), subscripts stand for the vector elements.

In order to obtain the optimal singular $\Pi(t)$, we write:

$\begin{split}&S^{(2)}(t)=\frac{d}{dt}S^{(1)}(t)=\frac{d}{dt}\langle\lambda(t),\mathcal{A}(X(t),\chi(t))\rangle=\\\
&\langle\frac{d\lambda}{dt},\mathcal{A}(X(t),\chi(t)\rangle+\langle\lambda(t),\frac{d\mathcal{A}}{dt}\rangle=0.\end{split}$
(32)

The time-derivative of $\mathcal{A}$ is computed as:

$\begin{split}&\frac{d\mathcal{A}}{dt}=\frac{\partial\mathcal{A}}{\partial
X}\frac{dX}{dt}+\frac{\partial\mathcal{A}}{\partial\chi}\frac{d\chi}{dt}.\end{split}$
(33)

With the help of Eq. (32), and Eq. (33), together with the co-state dynamics
(Eq. (24)), one arrives at:

$\begin{split}&S^{(2)}(t)=0\rightarrow\Pi(t)=-\frac{\langle\lambda(t),\mathcal{B}\rangle+\langle\lambda(t),\frac{\partial\mathcal{A}}{\partial\chi}\rangle\frac{d\chi}{dt}}{\langle\lambda(t),\mathcal{D}\rangle}.\end{split}$
(34)

In above, the vectors $\mathcal{B}$, and $\mathcal{D}$ are:

$\begin{split}&\mathcal{B}=\frac{\partial\mathcal{A}}{\partial
X}Q(X(t),\chi(t))-\frac{\partial Q}{\partial X}\mathcal{A}(X(t),\chi(t)),\\\
&\mathcal{D}=\frac{\partial\mathcal{A}}{\partial X}P(X(t))-\frac{\partial
P}{\partial X}\mathcal{A}(X(t),\chi(t)).\\\ \end{split}$ (35)

The generalized Legendre-Clebsch (LC) second-order necessary conditions
dictate [19]:

$\begin{split}&-\langle\lambda(t),\mathcal{D}\rangle\geq 0,\quad\forall
t\in\Omega_{s}.\end{split}$ (36)

Where $\Omega_{s}$ is an interval where the optimal $\Pi(t)$ is singular111In
the current study, all computations related to the optimal $\chi(t)$ and
singular $\Pi(t)$ were carried out symbolically in MATLAB. This involved
solving the co-state system defined by Eq. (29) and deriving symbolic formulas
for $\mathcal{A}$, $\mathcal{B}$, and $\mathcal{D}$..

####  III-B1 The Special Case $\alpha=0$

Since $\mathcal{R}=\vec{0}$ if $\alpha=0$, the solution to Eq. (29) becomes
intractable. On this occasion, from Eq. (29), we have:

$\begin{split}&\det\big{[}\bar{\bar{\mathcal{M}}}\big{]}=0\rightarrow\frac{d}{dt}\det\big{[}\bar{\bar{\mathcal{M}}}\big{]}=0.\end{split}$
(37)

Therefore, from Eq. (37), we obtain the optimal singular $\Pi(t)$ as:

$\begin{split}&\Pi(t)=-\frac{\frac{\partial}{\partial
X}\det\big{[}\bar{\bar{\mathcal{M}}}\big{]}Q(X(t),\chi(t))}{\frac{\partial}{\partial
X}\det\big{[}\bar{\bar{\mathcal{M}}}\big{]}P(X(t))}.\end{split}$ (38)

It is noteworthy that we can also handle the case $\alpha=0$ asymptotically,
i.e., to compute for $\alpha\rightarrow 0$.

##  IV Case Study

In accordance with our analysis presented in the previous sections, we
consider inequality constraints only w.r.t. the throttle setting, i.e.,
$\Pi_{min}\leq\Pi(t)\leq\Pi_{max},\forall t\in[0,t_{f}]$.

We use the BADA3 model for $T_{max}(h)$, $C_{s}(v)$, and $D(m,v,h)$ [20]. In
addition, air density is approximated by International Standard Atmospheric
(ISA) model:

$\begin{split}&T_{max}(h)=C_{T_{1}}\big{(}1-\frac{h}{C_{T_{2}}}+h^{2}C_{T_{3}}\big{)},\\\
&P(h)=P_{0}\big{(}\frac{\Theta_{0}-\beta h}{\Theta_{0}}\big{)}^{\frac{g}{\beta
R}},\quad\rho(h)=\frac{P(h)}{R(\Theta_{0}-\beta h)},\\\
&D(m,v,h)=\frac{1}{2}\rho(h)sv^{2}\big{(}C_{D_{1}}+C_{D_{2}}C_{l}^{2}\big{)},\\\
&C_{l}=\frac{2mg}{\rho sv^{2}},\quad
C_{s}(v)=C_{s_{1}}\big{(}1+\frac{v}{C_{s_{2}}}\big{)}.\end{split}$ (39)

In above, $s$ is the aerodynamic lift surface and $\rho$ is the air density.
$C_{T_{i}},i=1,2,3$, $s$, $C_{D_{i}},i=1,2$, $C_{s_{i}},i=1,2$, $R$, $\beta$,
$P_{0}$, $g$, and $\theta_{0}$ are known constants for a medium-haul aircraft
(see [16] for a quick access to their specific values and definitions).

Since $h$ is a constant (i.e., the altitude where the cruise flight occurs),
the maximum thrust force $T_{max}(h)$ will be a constant too.

The wind components are simulated by a general second-order polynomial for
each component.

Without loss of generality, we can consider $w_{x}=w_{x}(x,y)$, and
$w_{y}=w_{y}(x,y)$, and drop $h$. We also note that the vertical component of
wind is assumed to be zero [15], [13]. Therefore, for the sake of consistency
with the fluid flow behavior, the continuity equation must be satisfied, i.e.,
$\frac{\partial w_{x}}{\partial x}+\frac{\partial w_{y}}{\partial y}=0$. With
this observation, the wind components become:

$\begin{split}&w_{x}(x,y)=(a_{0}\bar{w}_{x}^{b})+(a_{1}\frac{\bar{w}_{x}^{b}}{x_{f}})x+(a_{2}\frac{\bar{w}_{x}^{b}}{x_{f}^{2}})x^{2}+\\\
&(a_{3}\frac{\bar{w}_{x}^{b}}{y_{f}})y+(a_{4}\frac{\bar{w}_{x}^{b}}{y_{f}^{2}})y^{2}+(a_{5}\frac{\bar{w}_{x}^{b}}{x_{f}y_{f}})xy,\\\
&w_{y}(x,y)=-\int\frac{\partial w_{x}}{\partial x}dy+f(x)\\\
&f(x)=\bar{w}_{y}^{b}+(b_{0}\frac{\bar{w}_{y}^{b}}{x_{f}})x+(b_{1}\frac{\bar{w}_{y}^{b}}{x_{f}^{2}})x^{2}.\end{split}$
(40)

In above, $a_{i},i=0,..,5$, and $b_{i},i=0,1$ are in general dimensionless
random values between $-1$ and $+1$. Moreover, $\bar{w}_{x}^{b}$, and
$\bar{w}_{y}^{b}$ are average dimensional wind constants.

Upon conducting an estimation of real wind data (w.r.t. various, though small,
atmospheric zones) using the aforementioned second-order model, we observed a
very good level of consistency. In particular, the total modeling error for
the wind components was found to be below 10 percent in relation to low-
resolution wind data. It is worth noting that in this study, we adopt a
generalized approach and do not fine-tune the model based on specific data
sets.

The tabulated parameters in table (I) are those we have fixed in our
simulations. Therefore, one can check that the only free parameter in our
simulations is $\alpha$.

TABLE I: boundary conditions, bounds, and the selected snapshot of the wind parameters $x_{0}$ | 0$(m)$ | $x_{f}$ | 1.5$\times 10^{6}(m)$
---|---|---|---
$y_{0}$ | 0$(m)$ | $y_{f}$ | 7$\times 10^{5}(m)$
$v_{0}$ | 200$(m/s)$ | $v_{f}$ | 200$(m/s)$
$m_{0}$ | 59000$(kg)$ | $h$ | 10000$(m)$
$\Pi_{max}$ | 1 | $\Pi_{min}$ | 0
$\bar{w}_{x}^{b}$ | 40$(m/s)$ | $\bar{w}_{y}^{b}$ | -20$(m/s)$
$a_{0}$ | 0.77406 | $a_{1}$ | -0.86240
$a_{2}$ | -0.63294 | $a_{3}$ | 0.47414
$a_{4}$ | 0.39342 | $a_{5}$ | 0.55398
$b_{0}$ | 0.00380 | $b_{1}$ | -0.14900

##  V Computational Algorithm

Preliminary analysis (using a single-shooting Euler-based direct transcription
method with high number of grids) implies that the optimal $\Pi(t)$ contains
at most one (interior) singular arc between two boundary arcs.

We have employed the switching-point algorithm, taking the switching times and
the initial heading as decision variables (see [10] for more information about
the switching-point algorithm and the associated mathematical justifications).

More specifically, we extend the state dynamics by Eq. (20), and the nonlinear
programming becomes:

$\begin{split}&\min_{\chi(0),t_{1},t_{2},t_{f}}\hat{\mathcal{J}}=\Phi(X_{f},t_{f}),\\\
&s.t.,\\\ &\frac{d{X}}{dt}=F(X(t),\chi(t),\Pi(t)),\\\
&\frac{d\chi}{dt}\big{(}1+\tan(\chi(t))^{2}\big{)}=-\frac{\partial
w_{x}}{\partial y}+\\\ &\big{(}\frac{\partial w_{x}}{\partial
x}-\frac{\partial w_{y}}{\partial y}\big{)}\tan(\chi(t))+\big{(}\frac{\partial
w_{y}}{\partial x}\big{)}\tan(\chi(t))^{2},\\\ &{\phi}_{0}(X_{0})=0,\\\
&{\phi}_{f}(X_{f})=0,\\\ &0\leq t_{1}\leq t_{2}\leq t_{f}.\end{split}$ (41)

With:

$\begin{split}\Pi(t)=\begin{cases}\Pi_{max}&t\in[0,t_{1}),\\\
Eq.(\ref{eq26})\lor Eq.(\ref{eq29})&t\in[t_{1},t_{2}],\\\
\Pi_{min}&t\in(t_{2},t_{f}].\end{cases}\end{split}$ (42)

We have adopted the interior-point/barrier algorithm of the nonlinear
programming solver $fmincon$ from MATLAB® Optimization Toolbox as the
optimization module.

We use the results due to the above nonlinear programming to compute the co-
state variables (and accordingly, the switching function) over the boundary
arcs. This is doable by backward and forward integration of the co-state
dynamics from $t_{1}$, and $t_{2}$ respectively.

###  V-A Special Case with a Constant Wind Field

Assuming a constant wind field, it is demonstrated that the optimization
problem formulated in Eq. (41) can exclude $\chi(0)$ as a decision variable.

Suppose that: $w_{x}=constant=:W_{x}$, and $w_{y}=constant=:W_{y}$.

From the system dynamics Eq. (1), we can write:

$\begin{split}&\frac{dx}{dt}=v(t)\cos(\chi(t))+W_{x},\quad\frac{dy}{dt}=v(t)\sin(\chi(t))+W_{y}.\end{split}$
(43)

Since $W_{x}$, and $W_{y}$ are constants, from Eq. (20) we have:
$\chi(t)=\chi(0)=constant$. Therefore, by integrating Eq. (43) from $0$ to
$t_{f}$, and after some elementary manipulations, we get:

$\begin{split}&\tan(\chi(0))=\frac{y_{f}-W_{y}t_{f}-y_{0}}{x_{f}-W_{x}t_{f}-x_{0}}.\end{split}$
(44)

Therefore, in case of having a constant wind field, the initial heading angle
$\chi(0)$ is a function of the constant wind components, boundary conditions,
and the final time $t_{f}$.

##  VI Numerical Results

We have obtained optimal results for various values of $\alpha$. From the
definition of the cost function, $\alpha$ determines the trade-off between
fuel-optimal and time-optimal problems. For each studied $\alpha$, we have
checked the second-order optimality condition (Eq. (36)) for the singular arc
and the first-order optimality condition for the boundary arcs. In addition,
for each stage of $\alpha$, we have compared our results with the results due
to a single-shooting Euler-based direct transcription method with high number
of grids (see Fig. 1). Upon examining this figure, we can ascertain that the
optimal costs derived from the direct method and the present indirect method
exhibit remarkable similarity. However, it is noteworthy that the estimated
singular arc generated by the direct method exhibits chattering behavior
around the singular solution by the indirect method.

Moreover, we note that the switching-point algorithm does not directly account
for $\lambda(t_{f})$. From the transversality conditions, we can check that
$\lambda_{m}(t_{f})=\alpha-1$. By computing the co-state variables over the
boundary arcs (after nonlinear programming), we have checked that
$|\lambda_{m}(t_{f})-(\alpha-1)|<10^{-4}$. This also stands as an additional
confirmation of the obtained optimal results (see Fig. 8).

The optimal controls $\Pi(t)$, $\chi(t)$, and the optimal states ($m(t)$ as a
function of $v(t)$) are shown in Fig. 2, Fig. 3, and Fig. 4 respectively.
Based on Fig. 2 and Fig. 4, it is clear that an increase in $\alpha$ leads to
a corresponding increase in the optimal speed by adjusting the throttle
setting.

From Fig. 2, it can be observed that as $\alpha$ increases, the first ”bang”
segment of the optimal throttle $\Pi(t)$ expands. This implies that there is a
specific value of $\alpha$ at which the optimal $\Pi(t)$ switches to a ”bang-
bang” control..

The optimal co-state variables in different values of $\alpha$ are graphed in
Fig. 5-Fig. 8.

As depicted in Fig. 8, $\lambda_{m}(t)$ displays only marginal changes with
respect to time. Hence, it may be reasonable to consider it as a constant for
analysis purposes, especially in engineering applications where rough
estimations of optimality are sufficient.

Fig. 9 illustrates the impact of $\alpha$ on the optimal $x-y$ trajectories.
Upon examination of the figure, it is apparent that the parameter $\alpha$
exhibits negligible influence on the evolution of the $x-y$ trajectories. More
precisely, the $x-y$ trajectories are more contingent on the wind
configuration.

Figure 1: The optimal $\Pi(t)$ (black), and $S(t)$ (red) where $\alpha=0.4$,
compared to single-shooting Euler-based direct transcription method with 400
nodes (blue dots); The optimal cost by the direct method:-30109.35, The
optimal cost by the indirect method:-30109.38 Figure 2: The optimal $\Pi(t)$
in different $\alpha$ Figure 3: The optimal $\chi(t)$ in different $\alpha$
Figure 4: The optimal $m(t)$ as a function of $v(t)$ in different $\alpha$
Figure 5: The optimal $\lambda_{x}$ in different $\alpha$ Figure 6: The
optimal $\lambda_{y}$ in different $\alpha$ Figure 7: The optimal
$\lambda_{v}$ in different $\alpha$ Figure 8: The optimal $\lambda_{m}$ in
different $\alpha$ Figure 9: The optimal $x-y$ trajectories (lateral path) in
different $\alpha$: blue and red lines show the lateral paths w.r.t.
$\alpha=0.5$, and $\alpha=0.1$ respectively.

##  VII Conclusion and Future Works

Pontryagin’s maximum principle was applied to solve a general (realistic)
version of the optimization problems related to commercial aircraft trajectory
in cruise phase. The analysis focused on the control functions, namely the
”heading angle” (regular control) and the ”throttle setting” (singular
control), from which optimality formulas were derived. To handle the singular
control, the switching-point algorithm was utilized as an alternative approach
to the conventional shooting methods. We have observed that the singular
$\Pi(t)$ vanishes in larger values of $\alpha$. Therefore, an open line of
research is to explore the condition in which the singular $\Pi(t)$
disappears. Moreover, our case study did not involve state-inequality
constraints. This can also be a subject for the future research.

## References

  * [1] Abolfazl Simorgh, Manuel Soler, Daniel González-Arribas, Sigrun Matthes, Volker Grewe, Simone Dietmüller, Sabine Baumann, Hiroshi Yamashita, Feijia Yin, Federica Castino, Florian Linke, Benjamin Lührs, and Maximilian Mendiguchia Meuser.  A comprehensive survey on climate optimal aircraft trajectory planning.  Aerospace, 9(3), 2022.
  * [2] Douglas M. Pargett and Mark D. Ardema.  Flight path optimization at constant altitude.  Journal of Guidance, Control, and Dynamics, 30(4):1197–1201, 2007\.
  * [3] Damián Rivas and Alfonso Valenzuela.  Compressibility effects on maximum range cruise at constant altitude.  Journal of Guidance, Control, and Dynamics, 32(5):1654–1658, 2009\.
  * [4] Antonio Franco, Damián Rivas, and Alfonso Valenzuela.  Minimum-fuel cruise at constant altitude with fixed arrival time.  Journal of Guidance, Control, and Dynamics, 33(1):280–285, 2010\.
  * [5] Antonio Franco and Damián Rivas.  Optimization of multiphase aircraft trajectories using hybrid optimal control.  Journal of Guidance, Control, and Dynamics, 38(3):452–467, 2015\.
  * [6] Antonio Franco and Damián Rivas.  Analysis of optimal aircraft cruise with fixed arrival time including wind effects.  Aerospace Science and Technology, 32(1):212–222, 2014.
  * [7] Banavar Sridhar, Hok K. Ng, and Neil Y. Chen.  Aircraft trajectory optimization and contrails avoidance in the presence of winds.  Journal of Guidance, Control, and Dynamics, 34(5):1577–1584, 2011\.
  * [8] Hok K. Ng, Banavar Sridhar, and Shon Grabbe.  Optimizing aircraft trajectories with multiple cruise altitudes in the presence of winds.  Journal of Aerospace Information Systems, 11(1):35–47, 2014.
  * [9] A. E. Bryson and Y. C. Ho.  Applied optimal control.  Taylor and Francis, Levittown, PA, page Chap. 2, 1975.
  * [10] Mahya Aghaee and William W. Hager.  The switch point algorithm.  SIAM Journal on Control and Optimization, 59(4):2570–2593, 2021\.
  * [11] H. Maurer, C. Büskens, J.-H. R. Kim, and C. Y. Kaya.  Optimization methods for the verification of second order sufficient conditions for bang–bang controls.  Optimal Control Applications and Methods, 26(3):129–156, 2005.
  * [12] G. Vossen.  Switching time optimization for bang-bang and singular controls.  Journal of Optimization Theory and Applications, 144:409–429, 2010\.
  * [13] Rhonda Slattery and Yiyuan Zhao.  Trajectory synthesis for air traffic automation.  Journal of Guidance, Control, and Dynamics, 20(2):232–238, 1997\.
  * [14] Michael R. Jackson, Yiyuan J. Zhao, and Rhonda A. Slattery.  Sensitivity of trajectory prediction in air traffic management.  Journal of Guidance, Control, and Dynamics, 22(2):219–228, 1999\.
  * [15] Daniel González-Arribas, Manuel Soler, and Manuel Sanjurjo-Rivo.  Robust aircraft trajectory planning under wind uncertainty using optimal control.  Journal of Guidance, Control, and Dynamics, 41(3):673–688, 2018\.
  * [16] Olivier Cots, Joseph Gergaud, and Damien Goubinat.  Direct and indirect methods in optimal control with state constraints and the climbing trajectory of an aircraft.  Optimal Control Applications and Methods, 39, 11 2017.
  * [17] D.H Jacobson, M.M Lele, and J.L Speyer.  New necessary conditions of optimality for control problems with state-variable inequality constraints.  Journal of Mathematical Analysis and Applications, 35(2):255–284, 1971.
  * [18] Richard F. Hartl, Suresh P. Sethi, and Raymond G. Vickson.  A survey of the maximum principles for optimal control problems with state constraints.  SIAM Review, 37(2):181–218, 1995.
  * [19] R. Gabasov and F. M. Kirillova.  High order necessary conditions for optimality.  SIAM Journal on Control, 10(1):127–168, 1972.
  * [20] D. Poles.  Base of aircraft data (bada) aircraft performance modelling report.  EEC Technical/Scientific Report, Eurocontrol, 2009.


hyperrefToken not allowed in a PDF string

# PosSLP and Sum of Squares

Markus Bläser Saarland University, Saarland Informatics Campus, Saarbrücken,
Germany. Email<EMAIL_ADDRESS>Julian Dörfler Saarland
University, Saarland Informatics Campus, Saarbrücken, Germany. Email:
<EMAIL_ADDRESS>Gorav Jindal Max Planck Institute for Software
Systems, Saarland Informatics Campus, Saarbrücken, Germany. Email:
<EMAIL_ADDRESS>
###### Abstract

The problem PosSLP is the problem of determining whether a given straight-line
program (SLP) computes a positive integer. PosSLP was introduced by Allender
et al. to study the complexity of numerical analysis (Allender et al., 2009).
PosSLP can also be reformulated as the problem of deciding whether the integer
computed by a given SLP can be expressed as the sum of squares of four
integers, based on the well-known result by Lagrange in 1770, which
demonstrated that every natural number can be represented as the sum of four
non-negative integer squares.

In this paper, we explore several natural extensions of this problem by
investigating whether the positive integer computed by a given SLP can be
written as the sum of squares of two or three integers. We delve into the
complexity of these variations and demonstrate relations between the
complexity of the original PosSLP problem and the complexity of these related
problems. Additionally, we introduce a new intriguing problem called Div2SLP
and illustrate how Div2SLP is connected to DegSLP and the problem of whether
an SLP computes an integer expressible as the sum of three squares.

By comprehending the connections between these problems, our results offer a
deeper understanding of decision problems associated with SLPs and open
avenues for further exciting research.

##  1 Introduction

###  1.1 Straight Line Programs and PosSLP

The problem $\operatorname{PosSLP}$ was introduced in [ABKPM09] to study the
complexity of numerical analysis and relate the computations over the reals
(in the so-called Blum-Shub-Smale model, see [BCSS97]) to classical
computational complexity. $\operatorname{PosSLP}$ asks whether a given integer
is positive or not. The problem may seem trivial at first glance but becomes
highly non-trivial when the given integer is not explicitly provided but
rather represented by an implicit expression which computes it. One way to
model the implicit computations of integers and polynomials is through the
notion of arithmetic circuits and straight line programs (SLPs).

An arithmetic circuit takes the form of a directed acyclic graph where input
nodes are designated with constants 0, 1, or variables
$x_{1},x_{2},\dots,x_{m}$. Internal nodes are labeled with mathematical
operations such as addition ($+$), subtraction ($-$), multiplication
($\times$), or division ($\div$). Such arithmetic circuits are said to be
_constant-free_. In the algebraic complexity theory literature, usually, one
studies arithmetic circuits where constants are arbitrary scalars from the
underlying field. But in this paper, we are only concerned with arithmetic
circuits that are constant-free.

On the other hand, a straight-line program is a series of instructions that
corresponds to a sequential evaluation of an arithmetic circuit. If this
program does not contain any division operations, it is referred to as
“division-free”. Unless explicitly specified otherwise, we will exclusively
consider division-free straight-line programs. Consequently, straight-line
programs can be viewed as a compact representation of polynomials or integers.
In many instances, we will be concerned with division-free straight-line
programs that do not incorporate variables, representing an integer.
Arithmetic circuits and SLPs are used interchangeably in this paper. Now we
define the central object of study in this paper.

######  Problem 1.1 ($\operatorname{PosSLP}$).

Given a straight-line program representing $N\in\mathbb{Z}$, decide whether
$N>0$.

An SLP $P$ computing an integer is a sequence
$(b_{0},b_{1},b_{2},\dots,b_{m})$ of integers such that $b_{0}=1$ and
$b_{i}=b_{j}\circ_{i}b_{k}$ for all $i>0$, where $j,k<i$ and
$\circ_{i}\in\\{+,-,\times\\}$. Given such an SLP $P$, $\operatorname{PosSLP}$
is the problem of determining the sign of the integer computed by $P$, i.e.,
the sign of $b_{m}$. Note that we cannot simply compute $b_{m}$ from a
description of $P$ because the absolute value of $b_{m}$ can be as large as
$2^{2^{m}}$. Therefore, computing $b_{m}$ exactly might require exponential
time. Hence, this brute force approach of determining the sign of $b_{m}$ is
too computationally inefficient. [ABKPM09] also show some evidence that
$\operatorname{PosSLP}$ might be a hard problem computationally. They do so by
showing the polynomial time Turing equivalence of $\operatorname{PosSLP}$ to
the Boolean part of the problems decidable in polynomial time in the Blum-
Shub-Smale (BSS) model and also to the generic task of numerical computation.
We briefly survey this relevance of $\operatorname{PosSLP}$ to emphasize its
importance in numerical analysis. For a more detailed discussion, the
interested reader is referred to [ABKPM09, Section 1].

The Blum-Shub-Smale (BSS) computational model deals with computations using
real numbers. It is a well-explored area where complexity theory and numerical
analysis meet. For a detailed understanding, see [BCSS97]. Here we only
dscribe the constant-free BSS model. BSS machines handle inputs from
$\mathbb{R}^{\infty}$, allowing polynomial-time computations over $\mathbb{R}$
to solve “decision problems” $L\subseteq\mathbb{R}^{\infty}$. The set of
problems solvable by polynomial-time BSS machines is denoted by
$\P^{0}_{\mathbb{R}}$, see e.g., [BC06]. To relate the complexity class
$\P^{0}_{\mathbb{R}}$ to classical complexity classes, one considers the
_boolean part_ of $\P^{0}_{\mathbb{R}}$, defined as:
$\operatorname{BP}(\P_{\mathbb{R}}^{0}):=\\{L\cap\\{0,1\\}^{\infty}\mid
L\in\P_{\mathbb{R}}^{0}\\}$. To highlight the importance of
$\operatorname{PosSLP}$ as a bridge between the BSS model and classical
complexity classes, [ABKPM09] proved the following Theorem 1.1.

######  Theorem 1.1 (Proposition 1.1 in [ABKPM09]).

We have $\P^{\operatorname{PosSLP}}=\operatorname{BP}(\P_{\mathbb{R}}^{0})$.

Another motivation for the complexity of $\operatorname{PosSLP}$ comes from
its connection to the task of numerical computation. Here we recall this
connection from [ABKPM09]. [ABKPM09] defined the following problem to
formalize the task of numerical computation:

######  Problem 1.2 (Generic Task of Numerical Computation
($\operatorname{GTNC}$) [ABKPM09]).

Given a straight-line program $P$ with $n$ variables, and given inputs
$a_{1},a_{2},\dots,a_{n}$ for $P$ (as floating-point numbers) and an integer
$k$ in unary, compute a floating-point approximation of
$P(a_{1},a_{2},\dots,a_{n})$ with $k$ significant bits.

The following result was also demonstrated in [ABKPM09].

######  Theorem 1.2 (Proposition 1.2 in [ABKPM09]).

$\operatorname{GTNC}$ is polynomial-time Turing equivalent to
$\operatorname{PosSLP}$.

###  1.2 How Hard is $\operatorname{PosSLP}$?

$\operatorname{GTNC}$ can be viewed as the task that formalizes what is
computationally efficient when we are allowed to compute with arbitrary
precision arithmetic. Conversely, the BSS model can be viewed as formalizing
computational efficiency where we have infinite precision arithmetic at no
cost. Theorem 1.1 and Theorem 1.2 show that both these models are equivalent
to $\operatorname{PosSLP}$ under polynomial-time Turing reductions. One can
also view these results as an indication that $\operatorname{PosSLP}$ is
computationally intractable. Despite this, no unconditional non-trivial
hardness results are known for $\operatorname{PosSLP}$. Still, a lot of
important computational problems reduce to $\operatorname{PosSLP}$. We briefly
survey some of these problems now. By the $n$-bit binary representation of an
integer $N$ with the condition $\lvert N\rvert<2^{n}$, we mean a binary string
with a length of $n+1$. This string consists of a sign bit followed by $n$
bits encoding the absolute value of $N$, with leading zeros added if
necessary. A very important problem in complexity theory is the
$\operatorname{EquSLP}$ problem defined as:

######  Problem 1.3 ($\operatorname{EquSLP}$, [ABKPM09]).

Given a straight-line program representing an integer $N$, decide whether
$N=0$.

$\operatorname{EquSLP}$ is also known to be equivalent to arithmetic circuit
identity testing ($\operatorname{ACIT}$) or polynomial identity testing
[ABKPM09]. It is easy to see that $\operatorname{EquSLP}$ reduces to
$\operatorname{PosSLP}$: $N\in\mathbb{Z}$ is zero if and only if $1-N^{2}>0$.
Recently, a conditional hardness result was proved for $\operatorname{PosSLP}$
in [BJ23], formalized below.

######  Theorem 1.3 (Theorem 1.2 in [BJ23]).

If a constructive variant of the radical conjecture of [DSS18] is true and
$\operatorname{PosSLP}\in\BPP$ then $\NP\subseteq\BPP$.

As for upper bounds on $\operatorname{PosSLP}$, $\operatorname{PosSLP}$ was
shown to be in the counting hierarchy $\CH$ in [ABKPM09]. This is still the
best-known upper bound on the complexity of $\operatorname{PosSLP}$. Another
important problem is the sum of square roots, defined as follows:

######  Problem 1.4 (Sum of Square Roots ($\operatorname{SoSRoot}$)).

Given a list $(a_{1},a_{2},\dots,a_{n})$ of positive integers and a list
$(\delta_{1},\delta_{2},\dots,\delta_{n})\in\\{\pm 1\\}^{n}$ of signs, decide
if $\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}$ is positive.

$\operatorname{SoSRoot}$ is widely recognized and finds applications in
computational geometry and various other domains. The Euclidean traveling
salesman problem, whose inclusion in $\NP$ is not known, is easily seen to be
in $\NP$ relative to $\operatorname{SoSRoot}$. $\operatorname{SoSRoot}$ is
conjectured to be in $\P$ in [Mal96] but this is far from clear. Still, one
can show that $\operatorname{SoSRoot}$ reduces to $\operatorname{PosSLP}$
[Tiw92, ABKPM09]. There are several other problems related to straight line
program which are intimately related to $\operatorname{PosSLP}$. For instance,
the following problems were also introduced in [ABKPM09]. These problems would
be useful in our discussion later.

######  Problem 1.5 ($\operatorname{BitSLP}$).

Given a straight-line program representing $N$, and given $n,i\in\mathbb{N}$
in binary, decide whether the $i^{\textrm{th}}$ bit of the $n$-bit binary
representation of $N$ is 1.

It was also shown in [ABKPM09] that $\operatorname{PosSLP}$ reduces to
$\operatorname{BitSLP}$. Although we do not know any unconditional hardness
results for $\operatorname{PosSLP}$, $\operatorname{BitSLP}$ was shown to be
$\\#\P$-hard in [ABKPM09]. Another important problem related to
$\operatorname{PosSLP}$ is the following $\operatorname{DegSLP}$ problem,
which was shown to be reducible to $\operatorname{PosSLP}$ in [ABKPM09].

######  Problem 1.6 ($\operatorname{DegSLP}$).

Given a straight-line program representing a polynomial $f\in\mathbb{Z}[x]$
and a natural number $d$ in binary, decide whether $\deg(f)\leq d$.

The problem $\operatorname{DegSLP}$ was posed in [ABKPM09] for multivariate
polynomials, here we have considered its univariate version. But these are
seen to be equivalent under polynomial time many one reductions [ABKPM09,
Proof of Proposition 2.3], we recall this reduction in Appendix C. We also
recall the following new problem from [DJPS21] related to straight line
programs, which is important to results in this paper.

######  Problem 1.7 ($\operatorname{OrdSLP}$).

Given a straight-line program representing a polynomial $f\in\mathbb{Z}[x]$
and a natural number $\ell$ in binary, decide whether
$\operatorname{ord}\left(f\right)\geq\ell$. Here, the order of $f$, denoted as
$\operatorname{ord}\left(f\right)$, is defined to be the largest $k$ such that
$x^{k}\mid f$.

###  1.3 Our Results

Lagrange proved in 1770 that every natural number can be represented as a sum
of four non-negative integer squares [NZM91, Theorem 6.26]. Therefore,
$\operatorname{PosSLP}$ can be reformulated as: Given a straight-line program
representing $N\in\mathbb{Z}$, decide if there exist $a,b,c,d\in\mathbb{N}$
such that $N=a^{2}+b^{2}+c^{2}+d^{2}$. In light of this rephrasing of
$\operatorname{PosSLP}$, we study the various sum of squares variants of
$\operatorname{PosSLP}$ in Section 2 and Section 3. To formally state our
results, we define these problems now. For convenience, we say that
$n\in\mathbb{N}$ is $\operatorname{3SoS}$ if it can be expressed as the sum of
three squares (of integers). We study the following problem.

######  Problem 1.8 ($\operatorname{3SoSSLP}$).

Given a straight-line program representing $N\in\mathbb{Z}$, decide whether
$N$ is a $\operatorname{3SoS}$.

One might expect that $\operatorname{3SoSSLP}$ is easier than
$\operatorname{PosSLP}$, but we show that $\operatorname{PosSLP}$ reduces to
$\operatorname{3SoSSLP}$ under polynomial-time Turing reductions. More
precisely, we prove the following Theorem 1.4 in Section 2.

######  Theorem 1.4.

$\operatorname{PosSLP}\in\P^{\operatorname{3SoSSLP}}$.

Similarly, we say that $n\in\mathbb{N}$ is $\operatorname{2SoS}$ if it can be
expressed as the sum of two squares (of integers). We also study the following
problem.

######  Problem 1.9 ($\operatorname{2SoSSLP}$).

Given a straight-line program representing $N\in\mathbb{Z}$, decide whether
$N$ is a $\operatorname{2SoS}$.

These problems $\operatorname{3SoSSLP}$ and $\operatorname{2SoSSLP}$ can also
be seen as special cases of the renowned Waring problem. The Waring problem
has an intriguing history in number theory. It asks whether for each
$k\in\mathbb{N}$ there exists a positive integer $g(k)$ such that any natural
number can be written as the sum of at most $g(k)$ many $k^{\textrm{th}}$
powers of natural numbers. Lagrange’s four-square theorem can be seen as the
equality $g(2)=4$. Later, Hilbert settled the Waring problem for integers by
proving that $g(k)$ is finite for every $k$ [Hil09]. Therefore problems
$\operatorname{2SoSSLP}$ and $\operatorname{3SoSSLP}$ can be seen as
computational variants of the Waring problem. These computational variants of
the Waring problems are extensively studied in computer algebra and algebraic
complexity theory and Shitov actually proved that computing the Waring rank of
multivariate polynomials is $\exists\mathbb{R}$-hard [Shi16]. For
$\operatorname{2SoSSLP}$, we prove the following conditional hardness result
in Section 3.

######  Theorem 1.5.

If the generalized Cramér conjecture A (Conjecture 3.1) is true, then
$\operatorname{PosSLP}\in\NP^{\operatorname{2SoSSLP}}$.

We also study whether $\operatorname{3SoSSLP}$ can be reduced to
$\operatorname{PosSLP}$. Unfortunately, we cannot show this reduction
unconditionally. Hence we study and rely on the following problem
$\operatorname{Div2SLP}$, which might be of independent interest. One can view
$\operatorname{Div2SLP}$ as the variant of $\operatorname{OrdSLP}$ for numbers
in binary.

######  Problem 1.10 ($\operatorname{Div2SLP}$).

Given a straight-line program representing $N\in\mathbb{Z}$, and a natural
number $\ell$ in binary, decide if $2^{\ell}$ divides $\left|N\right|$ , i.e.,
if the $\ell$ least significant bits of $\left|N\right|$ are zero.

We show that if we are allowed oracle access to both $\operatorname{PosSLP}$
and $\operatorname{Div2SLP}$ oracles then $\operatorname{3SoSSLP}$ can be
decided in polynomial time, formalized below in Theorem 1.6. A proof can be
found in Section 2.

######  Theorem 1.6.

$\operatorname{3SoSSLP}\in\P^{\\{\operatorname{Div2SLP},\operatorname{PosSLP}\\}}$.

We also study how $\operatorname{Div2SLP}$ is related to other problems
related to straight line programs. To this end, we prove the following Theorem
1.7 in Section 2.

######  Theorem 1.7.

$\operatorname{OrdSLP}\equiv_{\P}\operatorname{DegSLP}\leq_{\P}\operatorname{Div2SLP}$.

As for the hardness results for $\operatorname{3SoSSLP}$ and
$\operatorname{2SoSSLP}$, we also show that similar to
$\operatorname{PosSLP}$, $\operatorname{EquSLP}$ reduces to both
$\operatorname{3SoSSLP}$ and $\operatorname{2SoSSLP}$. Analogous to integers,
we also study the complexity of deciding the positivity of univariate
polynomials computed by a given SLP. In this context, we study the following
problem.

######  Problem 1.11 ($\operatorname{PosPolySLP}$).

Given a straight-line program representing a univariate polynomial
$f\in\mathbb{Z}[x]$, decide if $f$ is positive, i.e., $f(x)\geq 0$ for all
$x\in\mathbb{R}$.

We prove that in contrast to $\operatorname{PosSLP}$, hardness of
$\operatorname{PosPolySLP}$ can be proved unconditionally, formalized below in
Theorem 1.8.

######  Theorem 1.8.

$\operatorname{PosPolySLP}$ is $\coNP$-hard under polynomial-time many-one
reductions.

In constrast to numbers, every positive polynomial can be written as the sum
of two squares (but only over the reals, see Section Section 4 for a detailed
discussion). So $\operatorname{PosPolySLP}$ is equivalent to the question
whether $f$ is the sum of two squares. To conclude, we motivate and study the
following problem (see Section 4 for more details).

######  Problem 1.12 ($\operatorname{SqPolySLP}$).

Given a straight-line program representing a univariate polynomial
$f\in\mathbb{Z}[x]$, decide if $\exists g\in\mathbb{Z}[x]$ such that
$f=g^{2}$.

We show in Section 4 that $\operatorname{SqPolySLP}$ is in $\coRP$.

##  2 SLPs as Sums of Three Squares

This section is concerned with studying the complexity of
$\operatorname{3SoSSLP}$ and related problems.

###  2.1 Lower Bound for $\operatorname{3SoSSLP}$

In this section, we prove Theorem 1.4. We use the following characterization
of integers which can be expressed as the sum of three squares.

######  Theorem 2.1 ([Leg97, Gau01, Ank57, Mor58]).

An integer $n$ is $\operatorname{3SoS}$ if and only if it is not of the form
$4^{a}(8k+7)$, with $a,k\in\mathbb{N}.$

Theorem 2.1 informally implies that $\operatorname{3SoS}$ integers are “dense”
in $\mathbb{N}$ and hence occur very frequently. A useful application of this
intuitive high density of $\operatorname{3SoS}$ integers is demonstrated below
in Lemma 2.1. More formally, Landau showed that the asymptotic density of
$\operatorname{3SoS}$ integers in $\mathbb{N}$ is 5/6 [Lan09]. To reduce
$\operatorname{PosSLP}$ to $\operatorname{3SoSSLP}$, we shift the given
integer (represented by a given SLP) by a positive number to convert into
$\operatorname{3SoS}$. To this end we prove the following Lemma 2.1.

######  Lemma 2.1.

For every $n\in\mathbb{N}$, at least one element in the set $\\{n,n+2\\}$ is
$\operatorname{3SoS}$.

###### Proof.

If $n$ is $\operatorname{3SoS}$ then we are done. Suppose $n$ is not
$\operatorname{3SoS}$, by using Theorem 2.1 we know that $n=4^{a}(8k+7)$ for
some $a,k\in\mathbb{N}.$ If $a=0$ then $n=8k+7$ and hence $n+2=8k+9$ is
clearly not of the form $4^{b}(8c+7)$ for any $b,c\in\mathbb{N}$. If $a>0$
then $n+2=4^{a}(8k+7)+2$ is not divisible by $4$. Hence for $n+2$ of the form
$4^{b}(8c+7)$, we have to have $4^{a}(8k+7)+2=8c+7$. This is clearly
impossible because the LHS is even whereas RHS is odd. ∎

######  Lemma 2.2.

If $M\in\mathbb{Z}_{+}$ then $7M^{4}$ not a $\operatorname{3SoS}$.

###### Proof.

Suppose $M=4^{a}(4b+c)$ where $a$ is the largest power of $4$ dividing $M,$
$c=\frac{M}{4^{a}}\pmod{4}$ and $b=\lfloor\frac{M}{4^{a+1}}\rfloor$. We prove
the claim by analyzing the following cases.

If

$c=0$ then $M=4^{a}b$ for some $a,b\in\mathbb{N}$ and 4 does not divide $b$.
Note that here $a>0$, otherwise $c$ cannot be zero by its definition.
Therefore $7M^{4}=4^{4a}\cdot 7b^{4}$. Now we can apply this Lemma recursively
on $b$ (which is smaller than $M$) to infer that $7b^{4}$ is of the form
$4^{\alpha}(8\beta+7)$ for some $\alpha,\beta\in\mathbb{N}$. Hence $7M^{4}$ is
also of this form and thus not a $\operatorname{3SoS}$ by using Theorem 2.1.

If

$c=1$ then $7M^{4}=4^{4a}\cdot
7\cdot(256b^{4}+256b^{3}+96b^{2}+16b+1)=4^{\alpha}(8\beta+7)$ for some
$\alpha,\beta\in\mathbb{N}$, hence $7M^{4}$ is not a $\operatorname{3SoS}$ by
using Theorem 2.1.

If

$c=2$ then $7M^{4}=4^{4a+2}\cdot
7\cdot(16b^{4}+32b^{3}+24b^{2}+8b+1)=4^{\alpha}(8\beta+7)$ for some
$\alpha,\beta\in\mathbb{N}$, hence $7M^{4}$ is not a $\operatorname{3SoS}$ by
using Theorem 2.1.

If

$c=3$ then $7M^{4}=4^{4a}\cdot
7\cdot(256b^{4}+768b^{3}+964b^{2}+12496b+81)=4^{\alpha}(8\beta+7)$ for some
$\alpha,\beta\in\mathbb{N}$, hence $7M^{4}$ is not a $\operatorname{3SoS}$ by
using Theorem 2.1.

∎

Lemma 2.2 implies the following $\operatorname{EquSLP}$ hardness of
$\operatorname{3SoSSLP}$.

######  Lemma 2.3.

$\operatorname{EquSLP}\leq_{\P}\operatorname{3SoSSLP}$.

###### Proof.

Given a straight-line program representing an integer $N$, we want to decide
whether $N=0$. Suppose $M=N^{2}$. We have $M\geq 0$ and $M=0$ iff $N=0$. By
using Lemma 2.2, we know that $7M^{4}$ is a $\operatorname{3SoS}$ iff $M=0$. ∎

######  Remark 2.1.

Lemma 2.3 illustrates that $\operatorname{3SoSSLP}$ is at least as hard as
$\operatorname{EquSLP}$ under deterministic polynomial time Turing reductions.
This may not appear as a very strong result since $\operatorname{EquSLP}$ can
be decided in randomized polynomial time anyway. However, unconditionally,
even $\operatorname{PosSLP}$ is known to be only $\operatorname{EquSLP}$-hard.
Moreover, we rely on Lemma 2.3 in the proof of Theorem 1.4 below.

###### Proof of Theorem 1.4.

Given a straight-line program representing an integer $N$, we want to decide
whether $N>0$. Using an $\operatorname{EquSLP}$ oracle, we first check if
$N\in\\{0,-1,-2\\}$. By using Lemma 2.3, these oracle calls to
$\operatorname{EquSLP}$ can also be simulated by oracle calls to the
$\operatorname{3SoSSLP}$ oracle. Hence this task belongs to
$\P^{\operatorname{3SoSSLP}}$. If $N\in\\{0,-1,-2\\}$, then clearly $N>0$ is
false and we answer “No”. Otherwise we check if $N$ is a
$\operatorname{3SoS}$, if it is then clearly $N>0$ and we answer “Yes”. If it
is not a $\operatorname{3SoS}$ then we check if $N+2$ is a
$\operatorname{3SoS}$. If $N+2$ is a $\operatorname{3SoS}$ then clearly $N>0$
because $N\not\in\\{0,-1,-2\\}$. If $N+2$ is not a $\operatorname{3SoS}$, then
by Lemma 2.1 we can conclude that $N<-2$ and hence we answer “No”. ∎

###  2.2 Upper Bound for $\operatorname{3SoSSLP}$

Now we prove the upper bound for $\operatorname{3SoSSLP}$, claimed in Theorem
1.6.

###### Proof of Theorem 1.6.

Given an $N\in\mathbb{Z}$ represented by a given SLP, we want to decide if $N$
is a $\operatorname{3SoS}$. By using the $\operatorname{PosSLP}$ oracle, we
first check if $N\geq 0$. If $N<0$ then we answer “No”. Hence we can now
assume that $N>0$. By using Theorem 2.1, it is easy to see that $N$ is not a
$\operatorname{3SoS}$ iff the binary representation
$\operatorname{Bin}\left(N\right)$ of $N$ looks like below:

$N\text{ is not a
}\operatorname{3SoS}\iff\operatorname{Bin}\left(N\right)=S1110^{t}\text{ where
}t\text{ is even and }S\in\\{0,1\\}^{*}.$

By using the $\operatorname{Div2SLP}$ oracle, we compute the number of
trailing zeroes (call it again $t$) in the binary representation of $N$. This
can be achieved by doing a binary search and repeatedly using the
$\operatorname{Div2SLP}$ oracle. If $t$ is not even then $N$ is a
$\operatorname{3SoS}$. Next we construct an SLP which computes $2^{t}$, i.e.,
the number $10^{t}$ in the binary representation. Such an SLP can be
constructed in time $\poly(\log t)$ and is of size $O(\log^{2}t)$. This can be
seen by looking at the binary representation of $t$ and then using repeated
squaring. We have:

$\operatorname{Bin}\left(N+2^{t}\right)=S^{\prime}0^{t+3}\iff\operatorname{Bin}\left(N\right)=S1110^{t}\text{
for some }S,S^{\prime}\in\\{0,1\\}^{*}.$

Hence $N$ is not a $\operatorname{3SoS}$ iff $N+2^{t}$ has $t+3$ trailing
zeroes, which again can be decided using the $\operatorname{Div2SLP}$ oracle.
∎

###  2.3 Complexity of $\operatorname{Div2SLP}$

In this section, we show a $\operatorname{DegSLP}$ lower bound for
$\operatorname{Div2SLP}$. To this end, we first prove the following
equivalence of $\operatorname{DegSLP}$ and $\operatorname{OrdSLP}$.

######  Lemma 2.4.

Given a straight-line program $P$ of length $s$ computing a polynomial
$f\in\mathbb{Z}[x]$ , we can compute in $\poly(s)$ time:

  1. 1.

A number $m\in\mathbb{N}$ such that $\deg(f)\leq m\leq 2^{s}$.

  2. 2.

A straight line program $Q$ of length $O(s)$ such that Q computes the
polynomial $x^{m}f\left(\frac{1}{x}\right)$.

###### Proof.

We generate the desired straight line program $Q$ in an inductive manner.
Namely, if a gate $g$ in $P$ computes a polynomial $R_{g}$ then the
corresponding gate in $Q$ computes a number $m_{g}\geq\deg(R_{g})$ (the gate
itself does not compute a number, to be precise, but our reduction algorithm
does) and the polynomial
$x^{m_{g}}R_{g}\left(\frac{1}{x}\right)\in\mathbb{Z}[x]$. It is clear how to
do it for leaf nodes. Suppose $g=g_{1}+g_{2}$ is a $+$ gate in $P$. So we have
already computed integers $m_{g_{1}},m_{g_{2}}$ and polynomials
$x^{m_{g_{1}}}R_{g_{1}}\left(\frac{1}{x}\right),x^{m_{g_{2}}}R_{g_{2}}\left(\frac{1}{x}\right).$
We consider $m_{g}:=m_{g_{1}}+m_{g_{2}}$. We then have:

$x^{m_{g}}R_{g}\left(\frac{1}{x}\right)=x^{m_{g_{2}}}x^{m_{g_{1}}}R_{g_{1}}\left(\frac{1}{x}\right)+x^{m_{g_{1}}}x^{m_{g_{2}}}R_{g_{2}}\left(\frac{1}{x}\right).$

We also construct a straight-line program of length $O(s)$ that simultaneously
computes $x^{m_{h}}$ for all gates $h$ in $P$. With this, we can compute
$x^{m_{g}}R_{g}\left(\frac{1}{x}\right)$ using 3 additional gates. This
implies the straight-line program for $Q$ can be implemented using only $O(s)$
gates. Similarly for a $\times$ gate $g=g_{1}\times g_{2}$, we can simply use
$x^{m_{g}}R_{g}\left(\frac{1}{x}\right)=x^{m_{g_{1}}+m_{g_{2}}}R_{g_{1}}\left(\frac{1}{x}\right)R_{g_{2}}\left(\frac{1}{x}\right)$
with $m_{g}=m_{g_{1}}+m_{g_{2}}$. By induction it is also clear that at the
top gate $g$, we have $m_{g}\leq 2^{s}$. It remains to describe a straight-
line program of length $O(s)$ which computes $x^{m_{h}}$ for all gates $h$ in
$P$. Consider the straight-line program $P^{\prime}$ obtained from $P$ by
changing every addition gate into a multiplication gate. If $g^{\prime}$ is a
gate in $P^{\prime}$ corresponding to the gate $g$ in $P$, then one can show
via induction that $R_{g^{\prime}}\left(x\right)$ = $x^{m_{g}}$. This gives
the desired straight-line program. ∎

######  Lemma 2.5.

$\operatorname{DegSLP}\leq_{\P}\operatorname{OrdSLP}$.

###### Proof.

Suppose we are given a straight line program $P$ of length $s$ computing a
polynomial $f\in\mathbb{Z}[x]$. By using Lemma 2.4, we compute:

  1. 1.

A number $m\in\mathbb{N}$ such that $\deg(f)\leq m\leq 2^{s}$.

  2. 2.

A straight line program $Q$ of length $O(s^{2})$ such that $Q$ computes the
polynomial $x^{m}f\left(\frac{1}{x}\right)\in\mathbb{Z}[x]$.

Now it clear that:

$\deg(f)\leq
d\Longleftrightarrow\operatorname{ord}\left(x^{m}f\left(\frac{1}{x}\right)\right)\geq(m-d).$

Hence the claim follows. ∎

Proof of the following Lemma 2.6 is almost same to that of Lemma 2.5, hence we
omit it.

######  Lemma 2.6.

$\operatorname{OrdSLP}\leq_{\P}\operatorname{DegSLP}$.

######  Theorem 2.2.

$\operatorname{OrdSLP}\equiv_{\P}\operatorname{DegSLP}$.

###### Proof.

Follows immediately from Lemma 2.5 and Lemma 2.6. ∎

######  Theorem 2.3.

$\operatorname{OrdSLP}\equiv_{\P}\operatorname{DegSLP}\leq_{\P}\operatorname{Div2SLP}$.

###### Proof.

We only need to show that
$\operatorname{OrdSLP}\leq_{\P}\operatorname{Div2SLP}$. Suppose we are given a
straight line program $P$ of length $s$ computing a polynomial
$f\in\mathbb{Z}[x]$ and $\ell\in\mathbb{N}$ in binary, we want to decide if
$\operatorname{ord}\left(f\right)\geq\ell$. We know that $\lVert
f\lVert_{\infty}\leq 2^{2^{s}}$, where $\lVert f\lVert_{\infty}$ is the
maximum absolute value of coefficients of $f(x)$. We now construct an SLP
which computes $f(B)$ where $B$ is a suitably chosen large integer which we
will specify in a moment. If $\operatorname{ord}\left(f\right)\geq\ell$ then
clearly $B^{\ell}$ divides $f(B)$. Now consider the case when
$\operatorname{ord}\left(f\right)<\ell$ . So we have $f=x^{m}(f_{0}+xg)$ for
some $f_{0}\in\mathbb{Z},g\in\mathbb{Z}[x]$ and $m<\ell$. In this case we
have:

$f(B)=B^{m}(f_{0}+Bg(B)).$

If $B$ is chosen large enough then $B$ does not divide $f_{0}+Bg(B)$ and hence
$B^{\ell}$ does not divide $f(B)$. It can be verified that choosing
$B=2^{2^{3s}}$ suffices for this argument. It is also not hard to see that an
SLP for $f(B)$ can be constructed in polynomial time. Hence we conclude:

$\operatorname{ord}\left(f\right)\geq\ell\iff 2^{\ell 2^{3s}}\text{ divides
}f(2^{2^{3s}}).$

This completes the reduction. ∎

######  Problem 2.1.

What is the exact complexity of $\operatorname{Div2SLP}$?

Now we show that $\operatorname{Div2SLP}$ is in $\CH$, this claim follows by
employing ideas from [ABKPM09].

######  Lemma 2.7.

$\operatorname{Div2SLP}$ is in $\CH$.

###### Proof.

Given a straight-line program representing $N\in\mathbb{Z}$, and a natural
number $\ell$ in binary, we want to decide if $2^{\ell}$ divides
$\left|N\right|$, i.e., if the $\ell$ least significant bits of
$\left|N\right|$ are zero. We show that this can be done in
$\coNP^{\operatorname{BitSLP}}$. The condition $2^{\ell}\nmid\left|N\right|$
is equivalent to the statement that at least one bit in $\ell$ least
significant bits of $\left|N\right|$ is one. Hence there is a witness of this
statement, i.e., the index $i\leq\ell$ such that $i^{\textrm{th}}$ bit of
$\left|N\right|$ is one. By using the $\operatorname{BitSLP}$ oracle, we can
verify the existence of such a witness in polynomial time. Therefore
$\operatorname{Div2SLP}\in\coNP^{\operatorname{BitSLP}}$. By using [ABKPM09,
Theorem 4.1], we get that $\operatorname{Div2SLP}\in\coNP^{\CH}\subseteq\CH$.
∎

In Appendix B, we give a more general proof that shows that “SLP versions” of
problems in dlogtime uniform $\TC_{0}$ are in $\CH$.

##  3 SLPs as Sum of Two and Fewer Squares

This section is primarily concerned with studying the complexity of
$\operatorname{2SoSSLP}$. To this end, we first recall the following renowned
Theorem 3.1 which characterizes when a natural number is a sum of two squares.

######  Theorem 3.1 ([Dud12, Section 18]).

An integer $n>1$ is not $\operatorname{2SoS}$ if and only if the prime-power
decomposition of $n$ contains a prime of the form $4k+3$ with an odd power.

When the input integer $n$ is given explicitly as a bit string, Theorem 3.1
illustrates that a factorization oracle suffices to determine whether $n$ is a
$\operatorname{2SoS}$. In fact, we are not aware of any algorithm that
bypasses the need for factorization. For $x\in\mathbb{Z}_{+}$, let $B(x)$
denote the number of $\operatorname{2SoS}$ integers in $[x]$. Landau’s Theorem
[Lan08] gives the following asymptotic formula for $B(x)$.

######  Theorem 3.2 ([Lan08]).

$B(x)=K\frac{x}{\sqrt{\ln x}}+O\left(\frac{x}{\ln^{3/2}x}\right)$ as
$x\to\infty$, where $K$ is the Landau-Ramanujan constant with $K\approx
0.764$.

Ideally, we want to use the above Theorem 3.2 on the density of
$\operatorname{2SoS}$ to show that $\operatorname{PosSLP}$ reduces to
$\operatorname{2SoSSLP}$, as we did for $\operatorname{3SoSSLP}$. There are
two issues with this approach:

  1. 1.

The density of $\operatorname{2SoS}$ integers is not as high as
$\operatorname{3SoS}$ integers, hence to find the next $\operatorname{2SoS}$
integer after a given $N\in\mathbb{N}$ might require a larger shift (as
compared to the shift of 2 for $\operatorname{3SoS}$). This issue is overcome
below by using $\NP$ oracle reductions instead of $\P$ reductions.

  2. 2.

A more serious issue is that Theorem 3.2 says something about the density of
$\operatorname{2SoS}$ integers only asymptotically, as $x\to\infty$. But for
this idea of finding the next $\operatorname{2SoS}$ integer after a given
integer only works if this density bound is true for all intervals of
naturals. This issue is side stepped by relying on the Conjecture 3.1 below.

Let $q$ and $r$ be positive integers such that $1\leq r<q$ and $\gcd(q,r)=1$.
We use $G_{q,r}(x)$ to denote maximum gap between primes in the arithmetic
progression $\\{qn+r\mid n\in\mathbb{N},qn+r\leq x\\}$. We use $\varphi(n)$ to
denote the Euler’s totient function, i.e., the number of positive $m\leq n$
with $\gcd(m,n)=1$.

######  Conjecture 3.1 (Generalized Cramér conjecture A, [Kou18]).

For any $q>r\geq 1$ with $\gcd(q,r)=1$, we have

$G_{q,r}(p)=O(\varphi(q)\log^{2}p).$

###  3.1 Lower Bounds for $\operatorname{2SoSSLP}$

######  Lemma 3.1.

$\operatorname{EquSLP}\leq_{\P}\operatorname{2SoSSLP}$.

###### Proof.

Given a straight-line program representing an integer $N$, we want to decide
whether $N=0$. Suppose $M=N^{2}$. We have $M\geq 0$ and $M=0$ iff $N=0$. If
$M\neq 0$ then by employing Theorem 3.1, $3M^{2}$ cannot be a
$\operatorname{2SoS}$. Hence $3M^{2}$ is a $\operatorname{2SoS}$ iff $M=0$.

∎

###### Proof of Theorem 1.5.

Given a straight-line program of size $s$ representing an integer $N$, we want
to decide whether $N>0$. Choose $M=2^{3s}$. We compute the value of $N\bmod
T$, where $T:=2M+1$. This can be done in $\poly(s)$ time by simulating the
computation of the given SLP (which computes $N$) modulo $T$. If
$\left|N\right|\leq M$, then we can even recover the exact value of $N$ by
knowing $N\bmod T$. So by assuming $\left|N\right|\leq M$, we guess the exact
value of $N$. Let us call this guessed value (computed by knowing $N\bmod T$)
to be $N^{\prime}$. Then by using $\operatorname{EquSLP}$ oracle (which can be
simulated by $\operatorname{2SoSSLP}$ oracle using Lemma 3.1), we check if the
equality $N=N^{\prime}$ is actually true. If $N=N^{\prime}$ then we can easily
determine the sign of $N$. Otherwise our assumption $\left|N\right|\leq M$ is
false and hence we can assume that $\left|N\right|>M$.

Suppose $p\geq\left|N\right|$ is the smallest prime of the form $4k+1$. By
using the results in [Bre32], we know that $p\leq 2\left|N\right|$ for
$\left|N\right|\geq 7$. By using Conjecture 3.1 with $q=4,r=1$, we get that
$p\leq\left|N\right|+O(\varphi(4)\log^{2}p)\leq\left|N\right|+c\log^{2}\left|N\right|$
for some absolute constant $c$. For large enough $\left|N\right|$, it implies
that $p\leq\left|N\right|+\log^{3}\left|N\right|\leq\left|N\right|+2^{3s}$.
Therefore $p-\left|N\right|\leq M$. By using Theorem 3.1, we know that $p$ is
a $\operatorname{2SoS}$. Now we guess the witness $S:=p-\left|N\right|$,
clearly this has a binary description of size at most $O(s)$. Now we use
$\operatorname{2SoSSLP}$ oracle to check if $N+S$ is a $\operatorname{2SoS}$.
If $N>0$ then clearly such a witness exists. On the other hand if $N<0$ then
we know that $N<-M$ and $N+S$ cannot be a $\operatorname{2SoS}$. Therefore if
Conjecture 3.1is true then
$\operatorname{PosSLP}\in\NP^{\operatorname{2SoSSLP}}$. ∎

Similarly to $\operatorname{2SoSSLP}$ and $\operatorname{3SoSSLP}$, one can
also study the complexity of the following problem $\operatorname{SquSLP}$.

######  Problem 3.1 ($\operatorname{SquSLP}$, Problem 7 in [JG23]).

Given a straight-line program representing $N\in\mathbb{Z}$, decide whether
$N=a^{2}$ for some $a\in\mathbb{Z}$.

$\operatorname{SquSLP}$ was shown to be decidable in randomized polynomial
time in [JG23, Sec 4.2], assuming GRH. The complexity of
$\operatorname{2SoSSLP}$ remains an intriguing open problem. If
$\operatorname{2SoSSLP}$ were to be in $\P$ then this would disprove
Conjecture 3.1 or prove that $\operatorname{PosSLP}\in\NP$, neither of which
is currently known.

##  4 Polynomials as Sum of Squares

###  4.1 Positivity of Polynomials

Analogous to $\operatorname{PosSLP}$, we also study the positivity problem for
polynomials represented by straight line programs. In particular, we study the
following problem, called $\operatorname{PosPolySLP}$.

######  Problem 4.1 ($\operatorname{PosPolySLP}$).

Given a straight-line program representing a univariate polynomial
$f\in\mathbb{Z}[x]$, decide if $f$ is positive, i.e., $f(x)\geq 0$ for all
$x\in\R$.

It is known that every positive univariate polynomial $f$ can be written as
sum of two squares. The formal statement (Lemma A.1) and its folklore proof
can be found in the appendix.

Now we look at the rational variant of the Lemma A.1. Suppose
$f\in\mathbb{Z}[x]\subset\mathbb{Q}[x]$ is a positive polynomial. We know that
it can be written as sum of squares of two real polynomials. Can it also be
written as sum of squares of rational polynomials? In this direction, Landau
proved that each positive polynomial in $\mathbb{Q}[x]$ can be expressed as a
sum of at most eight polynomial squares in $\mathbb{Q}[x]$ [Edm06]. Pourchet
improved this result and proved that only five or fewer squares are needed
[Y.71].

We now show that $\operatorname{PosPolySLP}$ is $\coNP$-hard, this result
follows from an application of results proved in [PS07]. Suppose $W$ is a
3-SAT formula on $n$ literals $x_{1},x_{2},\dots,x_{n}$ with $W=C_{1}\land
C_{2}\land\dots\land C_{\ell}$, here $C_{i}$ is a clause composed of 3
literals. We choose any $n$ distinct odd primes $p_{1}<p_{2}<\dots<p_{n}$. So
$x_{i}$ is associated with the prime $p_{i}$. Thereafter, we define
$M:=\prod_{i\in[n]}p_{i}$. The following Theorem 4.1 was proved in [PS07].

######  Theorem 4.1 ([PS07]).

One can construct a SLP $C$ of size $\poly(p_{n},\ell)$ which computes a
polynomial $P_{M}(W)$ of the form:

$P_{M}(W):=\sum_{i\in[\ell]}(F_{M}(C_{i}))^{2}$

such that $P_{M}(W)$ has a real root iff $W$ is satisfiable. Here,
$F_{M}(C_{i})$ is a univariate polynomial that depends on $C_{i}$ (see [PS07]
for more details).

######  Theorem 4.2 (Theorem 1.2 in [BLR09]).

Let $f\in\mathbb{Z}[x]$ be a univariate polynomial of degree $d$ taking only
positive values on the interval $[0,1]$. Let $\tau$ be an upper bound on the
bit size of the coefficients of $f$. Let $m$ denote the minimum of $f$ over
$[0,1]$. Then

$m>\frac{3^{d/2}}{2^{(2d-1)\tau}(d+1)^{2d-1/2}}.$

The theorem above proves the lower bound for the interval $[0,1]$. Next, we
extend it to the whole real line.

######  Lemma 4.1.

Let $f\in\mathbb{Z}[x]$ be a positive univariate polynomial of degree $d$. Let
$\tau$ be an upper bound on the bit size of the coefficients of $f$. Let $m$
denote the minimum of $f$ over $\mathbb{R}$. If $m\neq 0$ then

$m>\frac{3^{d/2}}{2^{(2d-1)\tau}(d+1)^{2d-1/2}}.$

###### Proof.

We assume $m\neq 0$. Consider the reverse polynomial
$f_{\operatorname{rev}}:=x^{d}f\left(\frac{1}{x}\right)$. It is is clear that
$f_{\operatorname{rev}}$ is positive on $[0,\infty)$. Moreover,
$f_{\operatorname{rev}}$ has degree $d$ and $\tau$ is an upper bound on the
bit size of its coefficients. By employing Theorem 4.2 on
$f_{\operatorname{rev}}$, we infer that

$\min_{a\in[0,1]}f_{\operatorname{rev}}(a)>\frac{3^{d/2}}{2^{(2d-1)\tau}(d+1)^{2d-1/2}}.$

Theorem 4.2 implies that:

$\min_{a\in[0,1]}f(a)>\frac{3^{d/2}}{2^{(2d-1)\tau}(d+1)^{2d-1/2}}.$ (1)

Now consider a $\lambda\in[0,1]$, we have:

$f\left(\frac{1}{\lambda}\right)=\frac{f_{\operatorname{rev}}(\lambda)}{\lambda^{d}}\geq
f_{\operatorname{rev}}(\lambda)>\frac{3^{d/2}}{2^{(2d-1)\tau}(d+1)^{2d-1/2}}.$
(2)

By combining Equation 1 and Equation 2, we obtain that:

$\min_{a\in[0,\infty)}f(a)>\frac{3^{d/2}}{2^{(2d-1)\tau}(d+1)^{2d-1/2}}.$

By repeating the above argument on $f(-x)$ instead of $f(x)$, we obtain:

$m=\min_{a\in(-\infty,\infty)}f(a)>\frac{3^{d/2}}{2^{(2d-1)\tau}(d+1)^{2d-1/2}}.$

∎

###### Proof of Theorem 1.8.

Suppose $W$ is 3-SAT formula on $n$ literals $x_{1},x_{2},\dots,x_{n}$ with
$W=C_{1}\land C_{2}\land\dots\land C_{\ell}$, here $C_{i}$ is a clause
composed of 3 literals. By using Theorem 4.1, we can construct a SLP of size
$\poly(p_{n},\ell)$ which computes a polynomial $P(W)\in\mathbb{Z}[x]$ such
that $P(W)$ has a real root iff $W$ is satisfiable. (Recall that
$p_{1}<\dots<p_{n}$ was a sequence of odd primes.) Since $P(W)$ is a sum of
squares, $P(W)$ is positive. Suppose $m$ is the minimum value of $P(W)$ over
$\mathbb{R}$. We know that $m\geq 0$.

By the prime number theorem we can assume $p_{n}=O(n\log n)$. Moreover, it is
easy to see that $\ell\leq 8n^{3}$. Hence the constructed SLP is of size
$s=\poly(n)$. Suppose $\tau$ is an upper bound on the bit size of the
coefficients of $P(W)$. It is easy to see that $\deg(P(W))\leq 2^{s}$ and
$\tau\leq 2^{s}$. If $W$ is not satisfiable then we know that $m\neq 0$ and
therefore Lemma 4.1 implies that

$\log(m)>2^{s-1}\log 3-(2^{s+1}-1)2^{s}-(2^{s+1}-1/2)\log(2^{s}+1)>-2^{2s+2}.$

Hence

$m>\frac{1}{2^{2^{2s+2}}}.$

Suppose $B=2^{2^{2s+2}}$. Then $B\cdot P(W)-1$ is positive iff $m>0.$ Hence we
have:

$B\cdot P(W)-1\text{\text{ is positive} iff }W\text{ is unsatisfiable}.$

Moreover $B\cdot P(W)-1$ has a SLP of size $O(s)=\poly(n)$ and this SLP can be
constructed in time $\poly(n)$. Since determining the unsatisfiability of $W$
is $\coNP$-complete, it follows that $\operatorname{PosPolySLP}$ is
$\coNP$-hard. ∎

###  4.2 Checking if a Polynomial is a Square

In light of [Y.71]’s result and Theorem 1.8, we also study the following
related problem $\operatorname{SqPolySLP}$. Another motivation to study this
problem also comes from the quest for studying the complexity of factors of
polynomials. In this context, one wants to prove that if a polynomial can be
computed a small arithmetic circuit then so can be its factors. In this
direction, Kaltofen showed that if a polynomial $f=g^{e}h$ can be computed an
arithmetic circuit of size $s$ and $g,h$ are coprime, then $g$ can also be
computed by a circuit of size $\poly(e,\deg(g),s)$ [Kal87]. When $f=g^{e}$ ,
Kaltofen also showed that $g$ can be computed an arithmetic circuit of size
$\poly(\deg(g),s)$ [Kal87]. This question for finite fields is asked as an
open question in [KSS14]. What if we do not want to find a small circuit for
polynomial $g$ in case $f=g^{e}$ but only want to determine if $f$ is
$e^{\textrm{th}}$ power of some polynomial. And in this decision problem, we
want to avoid the dependency on $\deg(g)$ in running time, which can be
exponential in $s$. We study this problem for $e=2$ in
$\operatorname{SqPolySLP}$, but our results work for any arbitrary constant
$e$.

######  Problem 4.2 ($\operatorname{SqPolySLP}$).

Given a straight-line program representing a univariate polynomial
$f\in\mathbb{Z}[x]$, decide if $\exists g\in\mathbb{Z}[x]$ such that
$f=g^{2}$.

One can also study the complexity of determining if the given univariate
polynomial can be written as a sum of two, three or four squares but in this
section, we only focus on the problem $\operatorname{SqPolySLP}$. The
following Theorem 4.3 hints to an approach that $\operatorname{SqPolySLP}$ can
be reduced to $\operatorname{SquSLP}$.

######  Theorem 4.3 (Theorem 4 in [Mur08]).

For $f\in\mathbb{Z}[x]$, $\exists g\in\mathbb{Z}[x]$ with $f=g^{2}$ iff
$\forall t\in\mathbb{Z}$, $f(t)$ is a perfect square.

We shall use an effective variant of Theorem 4.3 which follows the following
effective variant of the Hilbert’s irreducibility theorem. For an integer
polynomial $f$, $H(f)$ is the height of $f$, i.e., the maximum of the absolute
values of the coefficients of $f$.

######  Theorem 4.4 ([Wal05, DW08]).

Suppose $P(T,Y)$ is an irreducible polynomial in $\mathbb{Q}[T,Y]$ with
$\deg_{Y}(P)\geq 2$ and with coefficients in $\mathbb{Z}$ assumed to be
relatively prime. Suppose $B$ is a positive integer such that $B\geq 2$. We
define:

$\displaystyle m$ $\displaystyle:=\deg_{T}(P)$ $\displaystyle n$
$\displaystyle:=\deg_{Y}(P)$ $\displaystyle H$
$\displaystyle:=\max(H(P),e^{e})$ $\displaystyle S(P,B)$
$\displaystyle:=\left|\\{1\leq t\leq B\mid P(t,Y)\text{ is reducible in
}\mathbb{Q}[Y]\\}\right|$

Then we have:

$S(P,B)\leq 2^{165}m^{64}2^{296n}\log^{19}(H)B^{\frac{1}{2}}\log^{5}(B).$

######  Corollary 4.1.

Suppose $f(x)\in\mathbb{Z}[x]$ is an integer polynomial computed by a SLP of
size $s$. Define $S(f):=\left|\\{1\leq t\leq 2^{200s}\mid f(t)\text{ is a
square }\\}\right|$. If $f$ is not a square then we have:

$S(f)<2^{800}s^{5}2^{183s}.$

###### Proof.

Consider the polynomial $P(T,Y):=Y^{2}-f(T)$. Since $f(x)$ is not a square, we
infer that $P(T,Y)$ is an irreducible polynomial in $\mathbb{Q}[T,Y]$. Now we
employ Theorem 4.4 on $P(T,Y)$ with $B=2^{200s}$, we have $m\leq 2^{s},n=2$
and $H\leq 2^{2^{s}}.$ In this case, we have $S(P,B)=S(f)$. By using Theorem
4.4 , we have:

$S(f)\leq
2^{165}2^{64s}2^{592}2^{19s}2^{100s}(200s)^{5}<2^{800}s^{5}2^{183s}.$

∎

Corollary 4.1 implies a randomized polynomial time algorithm for
$\operatorname{SqPolySLP}$, as demonstrated below in Theorem 4.5.

######  Theorem 4.5.

$\operatorname{SqPolySLP}$ is in $\coRP$.

###### Proof.

Given an integer polynomial $f(x)$ computed by a SLP of size $s$, we want to
decide if $f=g^{2}$ for some $g\in\mathbb{Z}[x]$. We sample a positive integer
uniformly at random from the set $\\{1\leq t\leq 2^{200s}\mid
t\in\mathbb{N}\\}$. Using the algorithm in [JG23, Sec 4.2], we test if $f(t)$
is a square. We output “Yes” if $f(t)$ is a square. If $f=g^{2}$ for some
$g\in\mathbb{Z}[x]$, then we always output “Yes”. Suppose $f\neq g^{2}$ for
any $g\in\mathbb{Z}[x]$. By using Corollary 4.1, we obtain that:

$\Pr[f(t)\text{ is a
square}]<\frac{2^{800}s^{5}2^{183s}}{2^{200s}}<\frac{1}{100}\text{ for
}s>100.$

Hence with probability at least $0.99$ we sample a $t$ such that $f(t)$ is not
a square. The algorithm for $\operatorname{SquSLP}$ verifies that $f(t)$ is
not a square with probability at least $\frac{1}{3}$ [JG23, Sec 4.2]. Hence we
output “No” with probability at least $0.33$. This implies
$\operatorname{SqPolySLP}\in\coRP$. ∎

##  5 Conclusion and Open Problems

We studied the connection between $\operatorname{PosSLP}$ and problems related
to the representation of integers as sums of squares, drawing on Lagrange’s
four-square theorem from 1770. We investigated variants of the problem,
considering whether the positive integer computed by a given SLP can be
represented as the sum of squares of two or three integers. We analyzed the
complexity of these variations and established relationships between them and
the original $\operatorname{PosSLP}$ problem. Additionally, we introduced the
$\operatorname{Div2SLP}$ problem, which involves determining if a given SLP
computes an integer divisible by a given power of 2. We showed that
$\operatorname{Div2SLP}$ is at least as hard as $\operatorname{DegSLP}$. We
also showed the relevance of $\operatorname{Div2SLP}$ in connecting the
$\operatorname{3SoSSLP}$ to $\operatorname{PosSLP}$. In contrast to
$\operatorname{PosSLP}$, we also showed that the polynomial variant of the
$\operatorname{PosSLP}$ problem is unconditionally $\coNP$-hard. Overall, this
paper contributes to a deeper understanding of decision problems associated
with SLPs and provides insights into the computational complexity of problems
related to the representation of integers as sums of squares. A visual
representation illustrating the problems discussed in this paper and their
interrelations is available in Figure 1. Our results open avenues for further
research in this area; in particular, we highlight the following research
avenues:

  1. 1.

What is the complexity of $\operatorname{Div2SLP}$? We showed it is
$\operatorname{DegSLP}$ hard. Is it $\NP$-hard too? How does it relate to
$\operatorname{PosSLP}$?

  2. 2.

Can we prove Theorem 1.5 without relying on Conjecture 3.1?

  3. 3.

One can also study the problems of deciding whether a given SLP computes an
integer univariate polynomial, which can be written as the sum of two, three,
or four squares. We studied these questions for integers in this paper. But it
makes for an interesting research to study these questions for polynomials.

  4. 4.

And finally, can we prove unconditional hardness results for
$\operatorname{PosSLP}$?

#### Acknowledgments:

We would like to thank Robert Andrews for providing a simpler proof of Lemma
2.4. We had a proof of it that was a bit longer. Robert Andrews simplified the
proof after reviewing our proof in a personal communication.

$\operatorname{Div2SLP}$$\operatorname{OrdSLP}$$\operatorname{DegSLP}$$\operatorname{PosSLP}$$\operatorname{EquSLP}$$\operatorname{3SoSSLP}$$\operatorname{2SoSSLP}$$\operatorname{Div2SLP}\cup\operatorname{PosSLP}$$\equiv$$\NP$,
cond. Figure 1: A visualization of the relations between the problems studied
in this work. An arrow means that there is a Turing reduction. A thicker arrow
indicates a polynomial time many one reduction. The reduction from
$\operatorname{PosSLP}$ to $\operatorname{2SoSSLP}$ is nondeterministic and
depends on Conjecture 3.1.

## References

  * [ABKPM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen.  On the complexity of numerical analysis.  SIAM Journal on Computing, 38(5):1987–2006, 2009.
  * [AKR+01] Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, and V. Vinay.  Time-space tradeoffs in the counting hierarchy.  In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pages 295–302. IEEE Computer Society, 2001.
  * [Ank57] N. C. Ankeny.  Sums of three squares.  Proceedings of the American Mathematical Society, 8(2):316–319, 1957.
  * [BC06] Peter Bürgisser and Felipe Cucker.  Counting complexity classes for numeric computations ii: Algebraic and semialgebraic sets.  Journal of Complexity, 22(2):147–191, 2006.
  * [BCSS97] Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale.  Complexity and Real Computation.  Springer-Verlag, Berlin, Heidelberg, 1997.
  * [BJ23] Peter Bürgisser and Gorav Jindal.  On the hardness of posslp, 2023.
  * [BLR09] Saugata Basu, Richard Leroy, and Marie-Francoise Roy.  A bound on the minimum of a real positive polynomial over the standard simplex, 2009.
  * [Bre32] R. Breusch.  Zur verallgemeinerung des bertrandschen postulates, dass zwischen x und 2x stets primzahlen liegen.  Mathematische Zeitschrift, 34:505–526, 1932.
  * [DJPS21] Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu.  Arithmetic Circuit Complexity of Division and Truncation.  In Valentine Kabanets, editor, 36th Computational Complexity Conference (CCC 2021), volume 200 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:36, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [DSS18] Pranjal Dutta, Nitin Saxena, and Amit Sinhababu.  Discovering the roots: Uniform closure results for algebraic classes under factoring.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 1152–1165, New York, NY, USA, 2018. Association for Computing Machinery.
  * [Dud12] U. Dudley.  Elementary Number Theory: Second Edition.  Dover Books on Mathematics. Dover Publications, 2012.
  * [DW08] Pierre Debes and Yann Walkowiak.  Bounds for hilbert’s irreducibility theorem.  Pure and Applied Mathematics Quarterly, 4(4):1059–1083, 2008.
  * [Edm06] Landau Edmund.  Über die darstellung definiter funktionen durch quadrate.  Mathematische Annalen, 62:272–285, 1906.
  * [Gau01] C.F. Gauss.  Disquisitiones arithmeticae.  Apud G. Fleischer, 1801.
  * [Hil09] David R. Hilbert.  Beweis für die darstellbarkeit der ganzen zahlen durch eine feste anzahlnter potenzen (waringsches problem).  Mathematische Annalen, 67:281–300, 1909.
  * [JG23] Gorav Jindal and Louis Gaillard.  On the order of power series and the sum of square roots problem.  In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, ISSAC ’23, page 354–362, New York, NY, USA, 2023\. Association for Computing Machinery.
  * [Kal87] E. Kaltofen.  Single-factor hensel lifting and its application to the straight-line complexity of certain polynomials.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, page 443–452, New York, NY, USA, 1987. Association for Computing Machinery.
  * [Kou18] Alexei Kourbatov.  On the distribution of maximal gaps between primes in residue classes, 2018.
  * [KSS14] Swastik Kopparty, Shubhangi Saraf, and Amir Shpilka.  Equivalence of polynomial identity testing and deterministic multivariate polynomial factorization.  In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 169–180. IEEE, 2014.
  * [Lan08] Edmund Landau.  Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindestzahl der zu ihrer additiven Zusammensetzung erforderliche Quadrate.  [s.n.] [S.l.], [S.l.], 1908.
  * [Lan09] E. Landau.  Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindestzahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate.  1909\.
  * [Leg97] Adrien Marie Legendre.  Essai Sur La Théorie Des Nombres.  Duprat, 1797.
  * [Mal96] Gregorio Malajovich.  An effective version of kronecker’s theorem on simultaneous diophantine approximation.  Technical report, Citeseer, 1996.
  * [Mor58] LJ Mordell.  On the representation of a number as a sum of three squares.  Rev. Math. Pures Appl, 3:25–27, 1958.
  * [Mur08] M Ram Murty.  Polynomials assuming square values.  Number theory and discrete geometry, pages 155–163, 2008.
  * [NZM91] Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery.  An Introduction to the Theory of Numbers.  Wiley, hardcover edition, 1 1991.
  * [PS07] Daniel Perrucci and Juan Sabia.  Real roots of univariate polynomials and straight line programs.  Journal of Discrete Algorithms, 5(3):471–478, 2007.  Selected papers from Ad Hoc Now 2005.
  * [Ruz81] Walter L. Ruzzo.  On uniform circuit complexity.  J. Comput. Syst. Sci., 22(3):365–383, 1981.
  * [Shi16] Yaroslav Shitov.  How hard is the tensor rank?, 2016.
  * [Tiw92] Prasoon Tiwari.  A problem that is easier to solve on the unit-cost algebraic ram.  Journal of Complexity, 8(4):393–397, 1992.
  * [Wal05] Yann Walkowiak.  Théorème d’irréductibilité de hilbert effectif.  Acta Arithmetica, 116(4):343–362, 2005.
  * [Y.71] Pourchet Y.  Sur la représentation en somme de carrés des polynômes à une indéterminée sur un corps de nombres algébriques.  Acta Arithmetica, 19(1):89–104, 1971.

##  Appendix A Missing Proofs

######  Lemma A.1.

For every positive polynomial $f\in\mathbb{R}[x]$, there exist
$g,h\in\mathbb{R}[x]$ such that $f=g^{2}+h^{2}$

###### Proof.

If $f(x)\geq 0$ for $x\in\R$ and $\alpha$ is a real root of $f$, then it must
have even multiplicity. We have $(x-\alpha)^{2}=(x-\alpha)^{2}+0^{2}$. We use
$\mathbb{\imath}$ to denote $\sqrt{-1}.$ If $\beta=s+\mathbb{\imath}t$ and
$\overline{\beta}=s-\mathbb{\imath}t$ are a complex-conjugate pair of roots of
$f$ then,
$(x-\beta)(x-\overline{\beta})=(x-s-\mathbb{\imath}t)(x-s+\mathbb{\imath}t)=(x-s)^{2}+t^{2}$
is a sum of two squares. Now the claim follows by using the identity
$(a^{2}+b^{2})(c^{2}+d^{2})=(ac-bd)^{2}+(ad+bc)^{2}$. ∎

##  Appendix B Alternative Proof of Lemma 2.7

We prove a general theorem on how to show that problems involving SLPs are in
$\CH$. It is similar to the proof of [AKR+01, Lem 5]. Let $C$ be a Boolean
circuit in $\TC_{0}$. $C$ consists of unbounded AND, unbounded OR, and
unbounded majority gates (MAJ). According to [Ruz81], when a family $(C_{n})$
is in dlogtime-uniform $\TC_{0}$, this means that there is a deterministic
Turing machine (DTM) that decides in time $O(\log n)$ whether given $(n,f,g)$
the gate $f$ is connected to the gate $g$ and whether given $(n,f,t)$ the gate
$f$ has type $t$. All numbers are given in binary. For a language
$B\subseteq\\{0,1\\}^{*}$, let $\operatorname{SLP}(B)$ be the language:

$\operatorname{SLP}(B):=\\{P\mid\text{$P$ is an SLP computing a number $N$
such that $\operatorname{Bin}\left(N\right)\in B$ (as a binary string)}\\}$

This can be viewed as the “SLP-version” of $B$.

######  Lemma B.1.

Let $B$ be in dlogtime-uniform $\TC_{0}$. Then $\operatorname{SLP}(B)\in\CH$.

###### Proof.

The proof is by induction on the depth. We prove the more general statement:
Let $M$ be a DTM from the definition of dlogtime and $(C_{n})$ be the sequence
of circuits for $B$. Let $P$ be the given SLP encoding a number $N$. Given
$(P,g,b)$ we can decide in $\CH_{t+c}$ whether the value of the gate $g$ on
input $N$ given by $P$ is $b$. $t$ is the depth of $g$. If $t=0$, then $g$ is
an input gate. Thus this problem is $\operatorname{BitSLP}$ which is in
$\CH_{c}$ for some $c$. If $t>0$, then we have to decide whether the majority
of the gates that are children of $g$ are $1$. This can be done using a
$\PP$-machine with oracle to $\CH_{c+t-1}$. We guess a gate $f$ and check
using the DTM $M$ whether $f$ is a predecessor of $g$. If not we add an
accepting and rejecting path. If yes, we use the oracle to check whether $f$
has value $1$. If yes we accept and otherwise, we reject. ∎

It is easy to see that checking whether the $\ell$ least significant bits of a
number given in binary are $0$ can be done in dlogtime-uniform $\TC_{0}$. Thus
$\operatorname{Div2SLP}$ is in $\CH$ by the lemma above.

##  Appendix C Reduction from multivariate $\operatorname{DegSLP}$ to
univariate $\operatorname{DegSLP}$

We use $\operatorname{mDegSLP}$ to denote the multivariate variant of the
$\operatorname{DegSLP}$ problem, which we define formally below.

######  Problem C.1 ($\operatorname{mDegSLP}$).

Given a straight line program representing a polynomial
$f\in\mathbb{Z}[x_{1},x_{2},\dots,x_{n}]$, and given a natural number $d$ in
binary, decide whether $\deg(f)\leq d$.

$\operatorname{mDegSLP}$ was simply called $\operatorname{DegSLP}$ in
[ABKPM09]. Now we recall the proof in [ABKPM09], to show that to study the
hardness of $\operatorname{mDegSLP}$, it is enough to focus on its univariate
variant $\operatorname{DegSLP}$. To this end, we note the following
Observation C.1.

######  Observation C.1 ([ABKPM09]).

$\operatorname{mDegSLP}$ is equivalent to $\operatorname{DegSLP}$ under
deterministic polynomial time many one reductions.

###### Proof.

We only need to show that $\operatorname{mDegSLP}$ reduces o
$\operatorname{DegSLP}$ under deterministic polynomial time many one
reductions, other direction is trivial. Suppose we are given an SLP of size
$s$ which computes $f\in\mathbb{Z}[x_{1},x_{2},\dots,x_{n}]$, and we want to
decide whether $\deg(f)\leq d$ for a given $d\in\mathbb{N}$. Suppose
$D=\deg(f)$. For all $i\in\\{0,1,\dots,D\\}$, we use $f_{i}$ to denote the
homogeneous degree $i$ part of $f$. Now notice that for any
$\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2},\dots,\alpha_{n})\in\mathbb{Z}^{d}$,
we have:

$f(y\boldsymbol{\alpha})=f(y\alpha_{1},y\alpha_{2},\dots,y\alpha_{n})=\sum_{i=0}^{D}y^{i}f_{i}(\boldsymbol{\alpha}),$

where $y$ is a fresh variable. So if $\boldsymbol{\alpha}$ is chosen such that
$f_{D}(\boldsymbol{\alpha})$ is non-zero then
$\deg(f(y\boldsymbol{\alpha}))=\deg(f)=D$. If we choose
$\alpha_{i}=2^{2^{is^{2}}}$ then it can seen that $f_{D}(\boldsymbol{\alpha})$
is non-zero, see e.g. [ABKPM09, Proof of Proposition 2.2]. SLPs computing
$\alpha_{i}$ can be constructed using iterated squaring in polynomial time.
Hence we can construct an SLP for $f(y\boldsymbol{\alpha})$ in polynomial
time. By this argument, we know that $\deg(f(y\boldsymbol{\alpha}))\leq d$ if
and only if $\deg(f)\leq d$ . Therefore $\operatorname{mDegSLP}$ reduces to
$\operatorname{DegSLP}$ under polynomial time many one reductions. ∎