# On the Order of Power Series and the Sum of Square Roots Problem

Louis Gaillard École Normale Supérieure de Lyon. Email: louis.gaillard@ens-
lyon.fr Gorav Jindal Max Planck Institute for Software Systems. Email:
<EMAIL_ADDRESS>
###### Abstract

This paper focuses on the study of the order of power series that are linear
combinations of a given finite set of power series. The order of a formal
power series, known as $\operatorname{ord}(f)$, is defined as the minimum
exponent of $x$ that has a non-zero coefficient in $f(x)$. Our first result is
that the order of the Wronskian of these power series is equivalent up to a
polynomial factor, to the maximum order which occurs in the linear combination
of these power series. This implies that the Wronskian approach used in (Kayal
and Saha, TOCT’2012) to upper bound the order of sum of square roots is
optimal up to a polynomial blowup. We also demonstrate similar upper bounds,
similar to those of (Kayal and Saha, TOCT’2012), for the order of power series
in a variety of other scenarios. We also solve a special case of the
inequality testing problem outlined in (Etessami et al., TOCT’2014).

In the second part of the paper, we study the equality variant of the sum of
square roots problem, which is decidable in polynomial time due to (Blömer,
FOCS’1991). We investigate a natural generalization of this problem when the
input integers are given as straight line programs. Under the assumption of
the Generalized Riemann Hypothesis (GRH), we show that this problem can be
reduced to the so-called “one dimensional” variant. We identify the key
mathematical challenges for solving this “one dimensional” variant.

Keywords  Formal power series, Sum of square roots, Wronskian, Differential
equations, Straight line Programs.

2012 ACM Subject Classification Theory of computation $\to$ Algebraic
complexity theory, Mathematics of computing $\to$ Probabilistic algorithms.

##  1 Introduction

For numerous decision problems that require determining the sign of
expressions with real numbers, their complexity class (e.g., if they belong to
$\P$ or not) is often unknown. A notable instance is the Sum of Square Roots
problem, which can be described as:

######  Problem 1 (Sum of Square Roots ($\operatorname{SSR}$)).

Given a list $(a_{1},a_{2},\dots,a_{n})$ of positive integers and
$(\delta_{1},\delta_{2},\dots,\delta_{n})\in\\{-1,1\\}^{n}$, decide whether
$\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}>0$.

The complexity of this problem has been extensively investigated and remains
an open question according to Garey, Graham, and Johnson [GGJ76].
Additionally, it has been hypothesized that it lies in $\P$, as proposed by
Malajovich in 2001 [Mal01]. The $\operatorname{SSR}$ problem shares deep
connections with classical geometric problems such as the Euclidean Traveling
Salesman Problem (ETSP), which is not known to be in $\NP$. It is readily seen
to be in $\NP$ relative to an oracle of $\operatorname{SSR}$. An important
related problem where the task is to determine the sign of an integer (encoded
by a straight line program), is the so called $\operatorname{PosSLP}$ problem.
A sequence $P$ of integers $(b_{0},b_{1},b_{2},\dots,b_{\ell})$ is said to be
a straight line program (SLP) if $b_{0}=1$ and for all $1\leq i\leq\ell$,
$b_{i}=b_{j}\circ_{i}b_{k}$, where $\circ_{i}\in\\{+,-,*\\}$ and $j,k<i$. We
say that this SLP $P$ computes the integer $b_{\ell}$. We say that $\ell$ is
the size (or length) of this SLP $P$.

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

Given an SLP $P$, decide if the integer $n_{P}$ computed by $P$ is positive.

The approximation of $\sqrt{a_{i}}$ in Problem 1 to an appropriate precision
leads to the reduction of $\operatorname{SSR}$ to $\operatorname{PosSLP}$, as
demonstrated in [ABKPM09]. $\operatorname{PosSLP}$ was introduced in this work
to bridge the gap between classical models of computation and computation over
the reals in the Blum-Shub-Smale (BSS) model [BCSS97], which is a widely
studied model for the study of computational complexity in numerical analysis.

It was shown in [ABKPM09] that $\operatorname{PosSLP}$ captures the “Boolean
part” of languages decidable in the BSS model in polynomial time, with
polynomial time Turing reductions. Additionally, $\operatorname{PosSLP}$ was
proven to lie within the counting hierarchy $\CH$, implying that
$\operatorname{SSR}$ also falls within $\CH$. To date, this represents the
best known upper bound for the complexity of $\operatorname{SSR}$.

Our contributions can be found in Section 1.2 after having introduced some
useful previous work on Problem 1 in Section 1.1.

###  1.1 Related work

In different scenarios, there is a need to determine if the sum of square
roots is equal to zero or not, rather than determining the sign of the
expression. As a result, we encounter an intriguing problem known as
$\operatorname{SSR}_{\operatorname{eq}}$.

######  Problem 3 ($\operatorname{SSR}_{\operatorname{eq}}$).

Given a list $(a_{1},a_{2},\dots,a_{n})$ of integers and
$(\delta_{1},\delta_{2},\dots,\delta_{n})\in\\{-1,1\\}^{n}$, decide whether
$\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}=0$.

Blömer [Blö91] gave a polynomial time algorithm to compute sums of radicals
and also proved that $\operatorname{SSR}_{\operatorname{eq}}$ is in $\P$.
Thus, testing if a signed sum of square roots is zero seems to be easier than
deciding its sign. A natural idea for an algorithm for the
$\operatorname{SSR}$ problem would be to approximate the sum with a floating
point number thanks to classical numerical algorithms. However, one would need
a result on the required number of bits of precision of the approximation to
ensure that the two signs coincide. It is known ([Bre76]) that for an integer
of bit size at most $B$, its square root can be approximated up to $m$ bits of
precision in time $\mathrm{poly}(B,m)$. And this implies that a solution of
the following number theoretic problem would lead to a polynomial time
algorithm for the $\operatorname{SSR}$ problem.

######  Problem 4 (Lower-bound on a nonzero sum of square roots).

Given a sum $S=\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}$, with
$\delta_{i}\in\\{-1,1\\}$ and $1\leq a_{i}<2^{B}$, can we find a polynomial
$q(n,B)$ such that

$\displaystyle S\neq 0\implies\left|S\right|\geq\frac{1}{2^{q(n,B)}}?$

In contrast to Problem 4, one can also try to find $a_{i}$’s and corresponding
$\delta_{i}$’s such that the absolute value of
$\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}$ is _small_. In this direction, it was
shown in [QW06] that
$\left|\sum_{i=0}^{m}\binom{m}{i}(-1)^{i}\sqrt{n+i}\right|=O(n^{-m+\frac{1}{2}})$.
Kayal and Saha [KS12] chose to approach Problem 4 by formulating a related
question over polynomials. This approach proved to be simpler. They focused on
non-zero sums of square roots of polynomials, which they viewed as power
series, and demonstrated that the valuation (or order) of such a series cannot
be _too high_.

######  Theorem 1 (Bounding the order of sum of square roots of polynomials
[KS12]).

For $1\leq i\leq n$, let $c_{i}\in\mathbb{C}$ and
$f_{i},g_{i}\in\mathbb{C}[x]$ of degree at most $d$ with $f_{i}(0)\neq 0$. We
denote and fix $\sqrt{f_{i}(x)}\in\mathbb{C}[[x]]$ one of the two square roots
of $f_{i}(x)$. If the sum $S(x)=\sum_{i=1}^{n}c_{i}g_{i}(x)\sqrt{f_{i}(x)}$ is
non-zero, then $\operatorname{ord}(S)\leq dn^{2}+n$.

The main technical argument of this proof is the study of the Wronskian
determinant of the family $(g_{i}\sqrt{f_{i}})_{1\leq i\leq n}$, because by
Cramer’s rule, one can easily bound the order of $S$ with respect to the order
of this Wronskian.

Next, they apply this result to a set of integers by representing them as
polynomials and they confirm that the solution to Problem 4 is affirmative for
a significant subclass of integers known as _polynomial integers_.

######  Theorem 2 ($\operatorname{SSR}$ for _polynomial integers_ [KS12]).

Suppose
$S=\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}$ is non-zero with
$\delta_{i}\in\\{-1,1\\}$, such that every positive integer $a_{i}$ is of the
form $a_{i}=X^{d_{i}}+b_{1,i}X^{d_{i}-1}+\dots+b_{d_{i},i}$ with $d_{i}>0$,
$X$ a positive integer and $d_{i},b_{j,i}$ are integers. Let
$B=\max\left(\left\\{\left|b_{j,i}\right|\right\\}_{j,i},1\right)$ and
$d=\max_{i}d_{i}$. There exist two fixed integer polynomials $p(n,d),q(n,d)$
in $n$ and $d$ such that if $X\geq(B+1)^{p(n,d)}$, then $S$ is lower bounded
as $\left|S\right|\geq\frac{1}{X^{q(n,d)}}$.

Based on these observations, it raises the question of whether the concept of
bounding the order of sums of power series can be generalized to other
families beyond square roots. This could potentially yield significant
insights into the complexity of determining the positivity of expressions
involving irrational real numbers.

###  1.2 Our results

From now on, $\mathbb{K}$ denotes a field of characteristic 0. All the
logarithms in this paper are natural logarithms with base $e$, unless
otherwise stated. We now define some measures to formally state our results.

######  Definition 1.

Suppose $\mathcal{F}\subseteq\mathbb{K}[[x]]$ is a finite dimensional linear
subspace of $\mathbb{K}[[x]]$, we define

$\displaystyle\mathcal{O}(\mathcal{F})\vcentcolon=\sup\\{\operatorname{ord}(f)\left|f\in\mathcal{F}\setminus\\{0\\}\right\\}\in\mathbb{N}\cup\infty.$

And for $\mathbf{f}=(f_{1},f_{2},\dots,f_{n})$ a family of linearly
independent power series, we define

$\displaystyle\mathcal{O}(f_{1},f_{2},\dots,f_{n})=\mathcal{O}(\mathbf{f})\vcentcolon=\mathcal{O}(\operatorname{span}(f_{1},f_{2},\dots,f_{n})).$

A set $\\{f_{1},f_{2},\dots,f_{n}\\}$ of $n$ functions over $\mathbb{K}$ is
said to be linearly dependent if there exist scalars
$c_{1},c_{2},\dots,c_{n}\in\mathbb{K}$ (not all zero) such that
$\sum_{i=1}^{n}c_{i}f_{i}$ is zero. To define the Wronskian of
$\\{f_{1},f_{2},\dots,f_{n}\\}$, we assume that each $f_{i}$ is $n-1$ times
differentiable. The Wronskian of $\\{f_{1},f_{2},\dots,f_{n}\\}$, denoted
$W(f_{1},f_{2},\dots,f_{n})$ is defined as the determinant of the following
matrix:

$\displaystyle
W(\mathbf{f})=W(f_{1},f_{2},\dots,f_{n})\vcentcolon=\det\begin{pmatrix}f_{1}&\dots&f_{n}\\\
f_{1}^{(1)}&\dots&f_{n}^{(1)}\\\ \vdots&\vdots&\vdots\\\
f_{1}^{(n-1)}&\dots&f_{n}^{(n-1)}\end{pmatrix}$

######  Proposition 1.

Let $\mathcal{F}\subseteq\mathbb{K}[[x]]$ be an $n$-dimensional linear
subspace. For any basis $(f_{1},f_{2},\dots,f_{n})$ of $\mathcal{F}$,
$\operatorname{ord}(W(f_{1},f_{2},\dots,f_{n}))$ does not depend on the choice
of the basis $(f_{1},f_{2},\dots,f_{n})$. We denote this quantity by
$W_{\operatorname{ord}}(\mathcal{F})$.

###### Proof.

Let $(g_{1},g_{2},\dots,g_{n})$ be another basis of $\mathcal{F}$. There
exists an invertible $n\times n$ matrix $A$ with entries in $\mathbb{K}$ such
that

$\displaystyle\begin{bmatrix}g_{1}&\dots&g_{n}\end{bmatrix}=\begin{bmatrix}f_{1}&\dots&f_{n}\end{bmatrix}\cdot
A.$

By linearity of the differentiation, we also have for all $0\leq j<n$,

$\displaystyle\begin{bmatrix}g_{1}^{(j)}&\dots&g_{n}^{(j)}\end{bmatrix}=\begin{bmatrix}f_{1}^{(j)}&\dots&f_{n}^{(j)}\end{bmatrix}\cdot
A.$

Thus we have
$W(g_{1},g_{2},\dots,g_{n})=W(f_{1},f_{2},\dots,f_{n})\cdot\det(A)$. By using
the fact that $\det(A)\in\mathbb{K}^{*}$, the result follows. ∎

The following theorem bounds $\mathcal{O}(\mathcal{F})$ in terms of
$W_{\operatorname{ord}}(\mathcal{F})$. This theorem is actually a result of
Voorhoeve and Van der Poorten [VV75]. The same idea is used by Kayal and Saha
[KS12] to establish the bound in Theorem 1.

######  Theorem 3 (Theorem 1 in [VV75]).

Let $\mathcal{F}$ be an $n$-dimensional linear subspace of $\mathbb{K}[[x]]$.
Then, $\mathcal{O}(\mathcal{F})\leq W_{\operatorname{ord}}(\mathcal{F})+n-1$.

In Section 2, we show that Theorem 3 is almost tight, in the sense that the
order of the Wronskian of a family $(h_{1},h_{2},\dots,h_{n})$ of power series
is equivalent, up to a polynomial factor, to the maximum order of a non-zero
linear combination of the $h_{i}$’s. This result is formalized in Theorem 4
below.

######  Theorem 4.

Let $\mathcal{F}$ be an $n$-dimensional linear subspace of $\mathbb{K}[[x]]$.
Then, $W_{\operatorname{ord}}(\mathcal{F})\leq
n\cdot\mathcal{O}(\mathcal{F})-\binom{n}{2}$.

For a full proof of Theorem 4, refer to Section 2. We then demonstrate that
the approach of Kayal and Saha in Theorem 1 can be extended to sums of
solutions of linear differential equations of order 1 with polynomial
coefficients, resulting in a comparable bound on the sum’s order. This result
is formally stated in Theorem 5 below.

######  Theorem 5.

Let $S(x)=\sum_{i=1}^{n}c_{i}g_{i}(x)y_{i}(x)$, with
$y_{i}^{\prime}-\frac{p_{i}}{q_{i}}y_{i}=0$, where $c_{i}\in\mathbb{K}$ and
$g_{i},p_{i},q_{i}\in\mathbb{K}[x]$ of degree at most $d$. We assume that
$q_{i}(0)\neq 0$ and that each $y_{i}\in\mathbb{K}[[x]]$. If $S\neq 0$, then

$\displaystyle\operatorname{ord}(S)\leq\sum_{i=1}^{n}\operatorname{ord}(y_{i})+n^{2}d+n-1.$

#### Proof idea for Theorem 5

The bound for $\operatorname{ord}(S)$ follows from Theorem 3, once we have
bounded the order of the Wronskian of the family $(g_{i}y_{i})_{1\leq i\leq
n}$ by $\sum_{i}\operatorname{ord}(y_{i})+n^{2}d$. To do this, we study the
entries of the Wronskian matrix and use the differential equations to replace
derivatives of the $y_{i}$’s. We show that every entry $(i,j)$ of the
Wronskian matrix can be written $y_{i}\frac{m_{i,j}}{q_{i}^{n-1}}$, where
$q_{i}$ is the denominator in the differential equation satisfied by $y_{i}$
and $m_{i,j}$ is a polynomial of degree $\leq nd$. The result directly follows
by bounding the order of the polynomials $m_{i,j}$ by their degree. For a full
proof of Theorem 5, see Section 3.

In Section 4, we investigate the following Problem 5
($\operatorname{SSR}_{\operatorname{SLP}}$) that can be regarded as a
generalization of Problem 3 ($\operatorname{SSR}_{\operatorname{eq}}$) in the
context of SLPs.

######  Problem 5 ($\operatorname{SSR}_{\operatorname{SLP}}$).

Given as input $n$ straight line programs $(P_{1},P_{2},\dots,P_{n})$ of size
$\leq s$ and $(\delta_{1},\delta_{2},\dots,\delta_{n})\in\\{-1,1\\}^{n}$, such
that $P_{i}$ computes the positive integer $a_{i}$, decide whether
$\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}=0$.

Here we show that assuming GRH, under randomized polynomial time Turing
reductions, $\operatorname{SSR}_{\operatorname{SLP}}$ can be reduced to the
following “one-dimensional” variant of
$\operatorname{SSR}_{\operatorname{SLP}}$,

######  Problem 6 (One dimensional $\operatorname{SSR}_{\operatorname{SLP}}$).

Given $n$ straight line programs computing $n$ positive integers
$(a_{1},a_{2},\dots,a_{n})$ and
$(\delta_{1},\delta_{2},\dots,\delta_{n})\in\\{-1,1\\}^{n}$, with the promise
that $\dim(\operatorname{span}_{\mathbb{Q}}(\sqrt{a_{1}}\mathchar
44\relax\penalty 0\sqrt{a_{2}}\mathchar 44\relax\penalty 0\dots\mathchar
44\relax\penalty 0\sqrt{a_{n}}))=1$. Decide if
$\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}=0$.

#### Proof idea for reducing $\operatorname{SSR}_{\operatorname{SLP}}$ to one
dimensional $\operatorname{SSR}_{\operatorname{SLP}}$

Given an instance of Problem 5, we separate the inputs into several one-
dimensional subgroups. This is possible because we demonstrate an efficient
randomized algorithm to test the linear dependency of square roots of integers
given by SLPs, using the ideas of Kneser [Kne75] and recounted out in Blömer’s
work in [Blö91]. According to Kneser’s result [Kne75], a set of square roots
are linearly dependent over $\mathbb{Q}$ if and only if there exists a pair of
linearly dependent square roots within the set. Once the instance of Problem 5
is separated into one-dimensional subgroups, it remains only to determine if
each subsum is zero, which can be done using an oracle for Problem 6. For a
full proof, see Section 4.

In Section 5, we show a similar upper bound to that of Theorem 1, on the order
of sums of logarithms of real polynomials.

######  Proposition 2.

Let $S(x)=\sum_{i=1}^{n}c_{i}\log(f_{i}(x))\neq 0$, where
$c_{i}\in\mathbb{R}$, $f_{i}\in\mathbb{R}[x]$ of degree at most $d$ and
$f_{i}(0)>0$. Then $\operatorname{ord}(S)\leq nd$.

We also show an analogous result to Theorem 2 but for the problem of the
positivity testing of linear forms of logarithms of integers whose complexity
is connected to deep conjectures in number-theory [ESY14], such as a
refinement of the $abc$ conjecture formulated by Baker [Bak98]. This result
essentially follows from Theorem 6 below, which is our analogue of Theorem 2.
For a full proof of Theorem 6, see Section 5.

######  Theorem 6 (Sum of logarithms of _polynomial integers_).

Suppose $E=\sum_{i=1}^{n}c_{i}\log{a_{i}}$ is non-zero, where
$c_{i}\in\mathbb{Z}$, and every $a_{i}$ is a positive integer of the form
$a_{i}=X^{d_{i}}+b_{1,i}X^{d_{i}-1}+\dots+b_{d_{i},i}$, where $d_{i}>0$, $X$
is a positive integer and $d_{i},b_{j,i}$ are integers. Let
$B=\max\left(\left\\{\left|b_{j,i}\right|\right\\}_{j,i},1\right),d=\max_{i}d_{i}+1$,
and $C=\max_{i}\left|c_{i}\right|$. There exist two fixed integer polynomial
$p_{1}(n,d),p_{2}(n,d)$ in $n$ and $d$ such that if
$X>\max\left(C^{2},(B+1)^{p_{1}(n,d)}\right)$, then $E$ is lower bounded as
$\left|E\right|\geq\frac{1}{X^{p_{2}(n,d)}}$.

##  2 Order of the Wronskian determinant

In this section we show that for a family of power series, the maximal order
that can occur in a non-zero linear combination is the order of the Wronskian
determinant of the family up to a polynomial factor. Our proof of Theorem 4 is
inspired from the ideas developed in [BD10]. For $d,k\in\mathbb{N}$, we denote

$\displaystyle(d)_{k}\vcentcolon=d(d-1)\dots(d-k+1),$

with the convention $(d)_{0}=1$.

######  Definition 2 (Vandermonde determinant).

Let $(d_{1},d_{2},\dots,d_{n})\in\mathbb{K}^{n}$, we define the corresponding
Vandermonde determinant as follows:

$\displaystyle
V(d_{1},d_{2},\dots,d_{n})\vcentcolon=\det\left((d_{j}^{i-1})_{1\leq i,j\leq
n}\right)=\prod_{1\leq i<j\leq n}(d_{j}-d_{i}).$

######  Lemma 7 (Wronskian of monomials, Lemma 1 in [BD10]).

The Wronskian of the monomials $a_{1}x^{d_{1}},\dots,a_{n}x^{d_{n}}$ is

$\displaystyle
W(a_{1}x^{d_{1}},\dots,a_{n}x^{d_{n}})=V(d_{1},d_{2},\dots,d_{n})\left(\prod_{i=1}^{n}a_{i}\right)x^{d_{1}+\dots+d_{n}-\binom{n}{2}}.$

######  Lemma 8 (Lemma 2 in [BD10]).

Let $f_{1},f_{2},\dots,f_{n}$ be a family of $\mathbb{K}[[x]]$ which are
linearly independent over $\mathbb{K}$. There exists an invertible $n\times n$
matrix $A$ with entries in $\mathbb{K}$ such that the power series
$g_{1},g_{2},\dots,g_{n}$ defined by

$\displaystyle\begin{bmatrix}g_{1}&\dots&g_{n}\end{bmatrix}=\begin{bmatrix}f_{1}&\dots&f_{n}\end{bmatrix}\cdot
A$ (1)

are all non-zero and have mutually distinct orders.

######  Lemma 9 (Wronskian of distinct order power series).

If the non-zero power series $g_{1},g_{2},\dots,g_{n}\in\mathbb{K}[[x]]$ have
mutually distinct orders $d_{1},d_{2},\dots,d_{n}$, then their Wronskian
$W(g_{1},g_{2},\dots,g_{n})$ is non-zero and satisfies:

$\displaystyle\operatorname{ord}(W(g_{1},g_{2},\dots,g_{n}))=\sum_{i=1}^{n}d_{i}-\binom{n}{2}.$

###### Proof.

If the $g_{j}$’s are monomials, _i.e_. $g_{j}=a_{j}x^{d_{j}}$, the result is a
direct consequence of Lemma 7, and in this case, the $(i,j)$ entry of the
Wronskian matrix is $w_{i,j}=a_{j}(d_{j})_{i-1}x^{d_{j}-i+1}$. In the general
case, let $g_{j}=a_{j}x^{d_{j}}+u_{j}$ with $u_{j}\in\mathbb{K}[[x]]$ of order
$>d_{j}$. Then the $(i,j)$ entry of the Wronskian matrix now becomes
$w_{i,j}\times(1+xr_{i,j})$ for some $r_{i,j}\in\mathbb{K}[[x]]$.

So we have $W(g_{1},g_{2},\dots,g_{n})=a_{1}\dots
a_{n}x^{d_{1}+\dots+d_{n}-\binom{n}{2}}\det(D)$ where $D$ is the $n\times n$
matrix $D=((d_{j})_{i-1}(1+xr_{i,j}))_{1\leq i,j\leq n}$. Now we evaluate $D$
at $x=0$, and we obtain $D(0)=((d_{j})_{i-1})_{1\leq i,j\leq n}$. With
elementary row operations (which preserve the determinant), as in the proof of
Lemma 7 in [BD10], we can transform $D(0)$ into the Vandermonde matrix
associated to $d_{1},\dots,d_{n}$. So,
$\det(D(0))=V(d_{1},d_{2},\dots,d_{n})\neq 0$, because the $d_{i}$’s are
distinct. Thus $\det(D)$ is non zero modulo $x$, so $\det D$ has order zero
and the result follows. ∎

We now formulate a tight variant (Theorem 10) of Theorem 4, which immediately
implies Theorem 4. Suppose $\mathcal{F}\subseteq\mathbb{K}[[x]]$ is a finite
dimensional subspace of $\mathbb{K}[[x]]$. Lemma 8 shows that if
$\dim(\mathcal{F})=n$ then there exist $n$ power series
$g_{1},g_{2},\dots,g_{n}$ in $\mathcal{F}$ which have distinct orders
$d_{1},d_{2},\dots,d_{n}$. Moreover $g_{1},g_{2},\dots,g_{n}$ also form a
basis of $\mathcal{F}$. We now claim that these are the only possible orders
of any power series in $\mathcal{F}$. Assume $d_{1}<d_{2}<\dots<d_{n}$. If
$f=\sum_{i=1}^{n}\lambda_{i}g_{i}$ (with $\lambda_{i}\in\mathbb{K}$) is a non-
zero power series in $\mathcal{F}$, then it is clear that
$\operatorname{ord}(f)=d_{j}$ where $j$ is the minimum index such that
$\lambda_{j}\neq 0$. With this claim, we formulate the following tight variant
of Theorem 4.

######  Theorem 10.

Let $\mathcal{F}$ be an $n$-dimensional linear subspace of $\mathbb{K}[[x]]$.
Suppose $d_{1},d_{2},\dots,d_{n}$ are the distinct orders of power series
which occur in $\mathcal{F}$. Then,
$W_{\operatorname{ord}}(\mathcal{F})=\sum_{i=1}^{n}d_{i}-\binom{n}{2}$.

###### Proof.

By Lemma 8, there exists a basis $(g_{1},g_{2},\dots,g_{n})$ of $\mathcal{F}$
with distinct order $d_{1},d_{2},\dots,d_{n}$. By using Lemma 9,
$W_{\operatorname{ord}}(\mathcal{F})=\sum_{i=1}^{n}d_{i}-\binom{n}{2}$.∎

See 4

###### Proof.

The claim immediately follows from Theorem 10. ∎

This completes the proof of Theorem 4. By combining Theorem 4 and Theorem 3,
we conclude that the order of the Wronskian determines the maximum order of
linear combinations of power series, up to a polynomial factor in $n$.

Now we show an example where the bound claimed in Theorem 3 is tight. Suppose
$\mathcal{G}$ is the linear subspace of $\mathbb{K}[[x]]$ generated by the
monomials $1,x,x^{2},\dots,x^{n-1}$. It is easy to see that Wronskian of
$1,x,x^{2},\dots,x^{n-1}$ is $\prod_{i=1}^{n-1}i!$. Hence
$W_{\operatorname{ord}}(\mathcal{G})=0$. We also have that
$\mathcal{O}(\mathcal{G})=n-1$.

##  3 Sums of solutions of linear differential equations

As a generalization of Theorem 1 and as an application of Theorem 3, we now
prove a polynomial bound on the order of a sum of power series that are
solutions of linear differential equations of order 1 with polynomial
coefficients.

See 5

###### Proof.

Let $h_{i}=g_{i}y_{i}$. Without loss of generality, we can assume that
$\mathbf{h}=(h_{1},h_{2},\dots,h_{n})$ are linearly independent. If they are
not, we can rewrite $S$ as a linear combination of a subfamily of the
$h_{i}$’s that are linearly independent.

We shall bound the order of the Wronskian $W(h_{1},h_{2},\dots,h_{n})$ and
apply Theorem 3. We have:

$\displaystyle y_{i}^{\prime}$ $\displaystyle=\frac{p_{i}}{q_{i}}y_{i},$
$\displaystyle y_{i}^{\prime\prime}$
$\displaystyle=\frac{p_{i}^{\prime}q_{i}-p_{i}q_{i}^{\prime}}{q_{i}^{2}}y_{i}+\frac{p_{i}}{q_{i}}y_{i}^{\prime}=\frac{p_{i}^{\prime}q_{i}-p_{i}q_{i}^{\prime}+p_{i}q_{i}}{q_{i}^{2}}y_{i}.$

So by induction, we deduce that for $0\leq j<n$,

$\displaystyle
y_{i}^{(j)}=\frac{P_{i,j}}{q_{i}^{j}}y_{i}=\frac{q_{i}^{n-1-j}P_{i,j}}{q_{i}^{n-1}}y_{i},$

where $q_{i}^{n-1-j}P_{i,j}$ is a polynomial of degree at most $(n-1)d$. Then,
by the Leibniz’s formula,
$h_{i}^{(j)}=\sum_{k=0}^{j}\binom{j}{k}g_{i}^{(j-k)}y_{i}^{(j)}$, and the
Wronskian has the form

$\displaystyle
W(h_{1},h_{2},\dots,h_{n})=\prod_{i=1}^{n}\frac{y_{i}}{q_{i}^{n-1}}\det M,$

with $M$ being a matrix whose entries are polynomials of degree at most $nd$.
In particular, $\operatorname{ord}(\det M)\leq\deg(\det M)\leq n^{2}d$. As
$q_{i}(0)\neq 0$ for all $i$, we have:

$\operatorname{ord}(W(\mathbf{h}))=\sum_{i=1}^{n}\operatorname{ord}(y_{i})+\operatorname{ord}(\det
M)\leq\sum_{i=1}^{n}\operatorname{ord}(y_{i})+n^{2}d.$

Finally, Theorem 3 implies the claimed bound. ∎

As a direct corollary of Theorem 5, we obtain upper bounds for the order of a
sum of power series in $\mathbb{C}[[x]]$ in several different contexts.

######  Corollary 1.

Let $S(x)=\sum_{i=1}^{n}c_{i}g_{i}(x)y_{i}(x)$ be a non-zero sum, where
$c_{i}\in\mathbb{C}$, and $g_{i}\in\mathbb{C}[x]$ are of degree at most $d$.
Let $f_{i}\in\mathbb{C}[x]$ of degree at most $d$.

  1. (i)

If $y_{i}=\exp(f_{i})$, then $\operatorname{ord}S\leq n^{2}(d-1)+n-1$.

  2. (ii)

If $y_{i}=\varphi(f_{i})$ with $\varphi\in\\{\cosh,\sinh,\cos,\sin\\}$, then
$\operatorname{ord}S\leq 4n^{2}(d-1)+2n-1$.

  3. (iii)

If $y_{i}=\left(\frac{p_{i}}{q_{i}}\right)^{\alpha_{i}}$, with
$p_{i},q_{i}\in\mathbb{C}[x]$ of degree at most $d$, $\alpha_{i}\in\mathbb{R}$
and $p_{i}(0),q_{i}(0)\neq 0$, then $\operatorname{ord}S\leq 2n^{2}d+n-1$.

###### Proof.

For item i, $y_{i}=\exp(f_{i})$, $y_{i}$ admits a power series expansion and
$\operatorname{ord}y_{i}=0$ because $y_{i}(0)=\exp f_{i}(0)\neq 0$. Moreover,
$y_{i}^{\prime}-f_{i}^{\prime}y_{i}=0$, with $\deg f_{i}^{\prime}\leq d-1$. By
Theorem 5, $\operatorname{ord}S\leq n^{2}(d-1)+n-1$.

For item ii, one can write $\cosh f=\frac{e^{f}+e^{-f}}{2},\sinh
f=\frac{e^{f}-e^{-f}}{2}$, $\cos f=\frac{e^{{i\mkern 1.0mu}f}+e^{-{i\mkern
1.0mu}f}}{2},\sin f=\frac{e^{{i\mkern 1.0mu}f}-e^{-{i\mkern
1.0mu}f}}{2{i\mkern 1.0mu}}$. We can then apply item i with $2n$ terms in the
sum and obtain the claimed bound.

For item iii, because both $p_{i}(0)$ and $q_{i}(0)$ are non-zero for all $i$,
$y_{i}$ admits a power series expansion in $0$ and
$\operatorname{ord}y_{i}=0$. Moreover, it satisfies
$y_{i}^{\prime}-\alpha_{i}\frac{p_{i}^{\prime}q_{i}-p_{i}q_{i}^{\prime}}{p_{i}q_{i}}y_{i}=0$.
Again, the bound is obtained by using Theorem 5. ∎

A similar bound for $y_{i}=\exp f_{i}$ was already established in [VV75] (see
Example 1). The proof also relies on Wronskians.

##  4  Sum of square roots of integers given by straight-line programs

As we mentioned in introduction, testing if an expression involving square
roots is zero is an interesting problem and Blömer [Blö91] developed a
polynomial time algorithm solving $\operatorname{SSR}_{\operatorname{eq}}$. In
$\operatorname{SSR}_{\operatorname{eq}}$, the integers in input are given in
binary and in this case, the problem is _easy_. It is a natural extension of
$\operatorname{SSR}_{\operatorname{eq}}$ to ask what happens for the
complexity of this problem in an algebraic model of computation, that is if
the integers in input are given by straight line programs. More precisely, we
want to study Problem 5.

We would like to know if zero testing for this class of expressions is as easy
as testing zero for straight line programs computing integers, namely
$\operatorname{EquSLP}$ defined in [ABKPM09]. In the problem
$\operatorname{EquSLP}$, given an input SLP $P$, we want to test if the
integer $n_{P}$ computed by $P$ is zero. In [ABKPM09], it is proven that
$\operatorname{EquSLP}$ reduces to Polynomial Identity Testing
($\operatorname{PIT}$), so it admits a randomized polynomial time algorithm.
In the hope of designing a randomized polynomial time algorithm for
$\operatorname{SSR}_{\operatorname{SLP}}$, we present in this section how one
can reuse some of the ideas of Blömer for
$\operatorname{SSR}_{\operatorname{eq}}$ in the context of Problem 5. We show
that the problem $\operatorname{SSR}_{\operatorname{SLP}}$ can be _reduced_
under the General Riemann Hypothesis (GRH) to a one dimensional case where all
the square roots involved are on the same line over $\mathbb{Q}$. Actually,
this special one dimensional case captures all the hardness of the whole
problem. One can also find related results in [Blö98, BNSW22]. They give
randomized algorithms to decide if expressions involving radicals of depth 1
is equal to 0. In [BNSW22], some algorithms are also valid under GRH and use
comparable arguments about density of certain prime numbers that we also
develop in this section. However, the expressions involved in these results
are different; the expressions are not only sums of square roots but general
arithmetic circuits involving square-roots of integers given in binary.

###  4.1 Reduction to the one-dimensional case

We now explain formally why it is enough to focus on the _one dimensional_
(Problem 6) version of Problem 5 in order to design an efficient algorithm for
$\operatorname{SSR}_{\operatorname{SLP}}$. We actually prove Theorem 11.

######  Theorem 11.

Under GRH, there exists a randomized polynomial time Turing reduction from
Problem 5 to Problem 6.

The starting point is the following result due to Kneser [Kne75] recalled by
Blömer ([Blö91], corollary 2.6).

######  Lemma 12.

Let $a_{1},a_{2},\dots,a_{n}$ be $n$ positive integers. Reals
$\sqrt{a_{1}}\mathchar 44\relax\penalty 0\sqrt{a_{2}}\mathchar
44\relax\penalty 0\dots\mathchar 44\relax\penalty 0\sqrt{a_{n}}$ are linearly
dependent over $\mathbb{Q}$ if and only if there exist $1\leq i<j\leq n$ such
that $(\sqrt{a_{i}},\sqrt{a_{j}})$ are linearly dependent over $\mathbb{Q}$ or
equivalently

$\displaystyle\frac{\sqrt{a_{i}}}{\sqrt{a_{j}}}\in\mathbb{Q}.$ (2)

######  Corollary 2.

Let $a_{1},\dots,a_{n}$ be positive integers and
$(\delta_{1},\dots,\delta_{n})\in\\{-1,1\\}^{n}$. Let
$(\sqrt{a_{i_{1}}},\dots,\sqrt{a_{i_{\ell}}})$ be a basis of
$\operatorname{span}_{\mathbb{Q}}(\sqrt{a_{1}},\dots,\sqrt{a_{i}})$. Then for
all $1\leq i\leq n$, there exists a unique $1\leq j\leq\ell$ such that
$\sqrt{a_{i}}\in\mathbb{Q}\cdot\sqrt{a_{i_{j}}}$. And

$\displaystyle\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}=0\iff\forall 1\leq
j\leq\ell,\sum_{i:~{}\sqrt{a_{i}}\in\mathbb{Q}\sqrt{a_{i_{j}}}}\delta_{i}\sqrt{a_{i}}=0.$
(3)

###### Proof.

Without loss of generality, we can assume $i_{j}=j$. Assuming existence,
uniqueness is clear because if $\sqrt{a_{i}}\in\mathbb{Q}\cdot\sqrt{a_{j}}$
and $\sqrt{a_{i}}\in\mathbb{Q}\cdot\sqrt{a_{j^{\prime}}}$, then $\sqrt{a_{j}}$
and $\sqrt{a_{j^{\prime}}}$ are not linearly independent. Now, for an element
of the basis existence is clear and for $\sqrt{a_{i}}$ not in the basis,
$(\sqrt{a_{1}},\dots,\sqrt{a_{\ell}},\sqrt{a_{i}})$ is linearly dependent. By
Lemma 12, two elements are linearly dependent, and it can not be between to
elements of the basis. So $\sqrt{a_{i}}$ is involved in this pair.

We partition $\\{1,\dots,n\\}=I_{1}\cup\dots\cup I_{\ell}$, with
$I_{j}=\\{i|~{}\sqrt{a_{i}}=q_{i,j}\sqrt{a_{j}},q_{i,j}\in\mathbb{Q}\\}$. Now,
$\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}=\sum_{j=1}^{\ell}\left(\sum_{i\in
I_{j}}\delta_{i}q_{i,j}\right)\sqrt{a_{j}}$. As $(\sqrt{a_{j}})_{1\leq
j\leq\ell}$ form a basis, the previous sum is zero if and only if for all
$1\leq j\leq\ell,\sum_{i\in I_{j}}\delta_{i}q_{i,j}=0$. By multiplying by
$\sqrt{a_{j}}$, we obtain

$\displaystyle\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}=0\iff\forall 1\leq
j\leq\ell,\sum_{i\in I_{j}}\delta_{i}\sqrt{a_{i}}=0.$

∎

The reduction for Theorem 11 then works in two steps and can be found in
Algorithm 1. Given an instance of Problem 5, we first build the partition of
the set of square roots in $\ell$ one-dimensional subsets, and then use the
oracle for Problem 6 to test if each associated subsum is zero. To build the
partition, Algorithm 1 works as follows: for each integer $a_{i}$, either we
have already seen an integer $a_{j}$ before such that
$\sqrt{a_{i}}/\sqrt{a_{j}}\in\mathbb{Q}$ and we add $a_{i}$ to the same one
dimensional sum as $a_{j}$ or we construct a new one for $a_{i}$. To complete
the proof of Theorem 11, it only remains to show that one can perform the test
of Equation 2 efficiently under GRH.

Input : $a_{1},a_{2},\dots,a_{n}$ integers given by SLPs, signs
$\delta_{1},\delta_{2},\dots,\delta_{n}\in\\{-1,1\\}$.

Output : Decide if $S=\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}=0$.

SubSums $\leftarrow[~{}]$ ;

for  _$1\leq i\leq n$_ do

$k\leftarrow 0~{};~{}\mathrm{FoundSubSum}\leftarrow\mathrm{false}$ ;

while  _$k <\left|\mathrm{SubSums}\right|$ and not $\mathrm{FoundSubSum}$_ do

Pick an element $b$ in $\mathrm{SubSums}[k]$ ;

if  _$\sqrt{a_{i}}/\sqrt{b}\in\mathbb{Q}$_ then

Add $a_{i}$ to $\mathrm{SubSums}[k]$ ;
$\mathrm{FoundSubSum}\leftarrow\mathrm{true}$ ;

else

$k$++;

end if

end while

if not $\mathrm{FoundSubSum}$ then Add $\\{a_{i}\\}$ to SubSums ;

end for

For each element of SubSums, test if the corresponding one dimensional sum is
zero using oracle for Problem 6;

Algorithm 1 Algorithm for Problem 5

######  Lemma 13.

Let $a,b$ be two positive integers. $\frac{\sqrt{a}}{\sqrt{b}}\in\mathbb{Q}$
iff $\sqrt{ab}\in\mathbb{N}$.

###### Proof.

$\sqrt{a}/\sqrt{b}\in\mathbb{Q}$ is equivalent to the statement that for any
prime $p$, the $p$-adic valuation $v_{p}(a/b)$ of $a/b$ is even,
$v_{p}(a/b)=v_{p}(a)-v_{p}(b)$, or equivalently $v_{p}(a)+v_{p}(b)=v_{p}(ab)$
is even, _i.e_. $\sqrt{ab}\in\mathbb{N}$ . ∎

Lemma 13 suggests that for testing Equation 2, we just have to check if
$a_{i}a_{j}$ is a perfect square. Note that if both $a_{i}$ and $a_{j}$ can be
computed by SLPs of size $s$, then $a_{i}a_{j}$ admits an SLP of size $2s+1$.
In the next section we design a randomized polynomial time algorithm to
perform this task under GRH.

###  4.2 Testing if an SLP computes a perfect square

We now demonstrate an algorithm for the following Problem 7.

######  Problem 7.

Given an SLP of size $t$ computing a positive integer $a$, decide if $a$ is a
perfect square.

Let $a$ be a positive integer computed by an SLP of size $t$. By induction on
$t\geq 0$, we have the bound $a\leq 2^{2^{t}}$.

Our algorithm is the following: sample at random a prime $p\leq 2^{q(t)}$,
with $q$ a polynomial to be determined later, compute $a\bmod p$ and test if
$a\bmod p$ is a square in $\mathbb{F}_{p}$. All these computations can be done
in polynomial time in $t$ [BS96]. If $a$ is actually a perfect square, then
for all such primes $p$, $a\bmod p$ is a square in $\mathbb{F}_{p}$ and the
answer of the algorithm is correct. Whereas if $a$ is not a perfect square,
Chebotarev’s density theorem guarantees that the set of primes $p$ for which
the polynomial $X^{2}-a$ splits in $\mathbb{F}_{p}$, _i.e_., the set of primes
$p$ where $a$ is a square in $\mathbb{F}_{p}$ has density $\frac{1}{2}$
[SL96]. To ensure that we can use small primes and keep a non negligible
probability to have a correct answer, we need an effective version. This
effective version of Chebotarev’s density theorem requires GRH and can be
found in [Ser81] (Theorem 4).

Our application of the effective Chebotarev’s density theorem leads us to the
following key lemma. The statement directly follows from [Ser81] (Theorem 4)
for the splitting field of $X^{2}-a$. This only makes sense when
$\mathrm{disc}(X^{2}-a)=4a$ does not vanish in $\mathbb{F}_{p}$. This is the
reason why we only consider primes $p$ that do not divide $4a$.

######  Lemma 14.

Let $a$ be a positive integer that is not a square. For $x\geq 2$, we define:

$\displaystyle d_{a}(x)\vcentcolon=\frac{\left|\\{p\text{ prime }\leq
x,a\text{ is not a square mod $p$ and }p\nmid 4a\\}\right|}{\left|\\{p\text{
prime }\leq x\\}\right|}.$

There exists a constant $C$ such that, under GRH, for all $x\geq 2$,

$\displaystyle\left|d_{a}(x)-\frac{1}{2}\right|\leq
C\frac{\log_{2}x}{\sqrt{x}}\left(\log_{2}(4a)+2\log_{2}x\right).$

Now we can state the main lemma.

######  Lemma 15.

Let $a\leq 2^{2^{t}}$ be a positive integer that is not a perfect square. Then
there exists an integer polynomial $q$ such that for $x=2^{q(t)}$, we have
$d_{a}(x)\geq\frac{1}{4}$.

###### Proof.

From Lemma 14, the following inequality holds:

$\displaystyle
d_{a}(x)\geq\frac{1}{2}-C\frac{\log_{2}x}{\sqrt{x}}(\log_{2}(4a)+2\log_{2}x).$

To conclude, we need to ensure that

$\displaystyle
C\frac{\log_{2}x}{\sqrt{x}}(\log_{2}(4a)+2\log_{2}x)\leq\frac{1}{4},\text{\emph{i.e}.\hbox{},}$
$\displaystyle\log_{2}(4a)\leq\frac{1}{4}\frac{\sqrt{x}}{C\log_{2}x}-2\log_{2}x.$

With $a\leq 2^{2^{t}}$, and $x=2^{q(t)}$, it is sufficient to have

$\displaystyle 2^{t}+2\leq\frac{1}{4}\frac{2^{\frac{q(t)}{2}}}{Cq(t)}-2q(t).$
(4)

and one can see that $q(t)=O(t^{2})$ satisfies Equation 4. ∎

If one chooses $q(t)$ as in Lemma 15, our randomized algorithm runs in
polynomial time and has a one sided error for solving Problem 7. This
completes the proof of Theorem 11.

###  4.3 About the One Dimensional Variant

In the previous section, we showed that it is enough to focus on Problem 6.
Suppose $\operatorname{span}_{\mathbb{Q}}(\sqrt{a_{1}}\mathchar
44\relax\penalty 0\sqrt{a_{2}}\mathchar 44\relax\penalty 0\dots\mathchar
44\relax\penalty 0\sqrt{a_{n}})=\mathbb{Q}\cdot\sqrt{a_{1}}$. Then, for all
$i$, $\sqrt{a_{i}a_{1}}\in\mathbb{N}$. And
$S=\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}}=0\iff
S\sqrt{a_{1}}=\sum_{i=1}^{n}\delta_{i}\sqrt{a_{i}a_{1}}=0$, with
$S\sqrt{a_{1}}\in\mathbb{N}$. One approach to design an algorithm to test
$S\sqrt{a_{1}}=0$, is reducing it modulo a randomly selected prime number $p$.
The problem with this approach, is that once we have reduced $a_{i}a_{1}$
modulo $p$, one can compute its two square roots in $\mathbb{F}_{p}$ but there
is no way to decide which one of the two is the correct representation of
$\sqrt{a_{1}a_{i}}$ in $\mathbb{F}_{p}$. Determining the correct reduction of
$S\sqrt{a_{1}}$ modulo $p$ seems like a non trivial task. And we most likely
need a different approach in order to tackle Problem 6.

##  5 An application to sums of logarithms

In order to motivate the interest of proving bounds for the order of sums of
certain power series, we show that the approach of Kayal and Saha [KS12] that
led to a non trivial statement for the Sum of Square Roots problem can also be
used to establish non-trivial statements for other fundamental number
theoretic problems. In particular in this section, we focus on the sums of
logarithms that is a well-studied problem [Bak98, ESY14] and is related to
deep number theory conjectures.

######  Problem 8.

Given two lists $(a_{1},a_{2},\dots,a_{n})$, $(c_{1},c_{2},\dots,c_{n})$ of
integers with $a_{i}>0$, decide if

$\displaystyle\sum_{i=1}^{n}c_{i}\log{a_{i}}>0.$

Similarly as for the Sum of Square roots problem (Problem 1), the complexity
in the bit-model of Problem 8 is an open question. A refinement of the
$abc$-conjecture formulated by Baker [BW93] would imply Problem 8 to be in
$\P$. Interesting details about the link between the complexity of Problem 8
and open questions in number-theory can be found in [ESY14]. All these
conjectures essentially state the existence of a _gap_ , namely that a non-
zero sum of logarithms can not be _too close to zero_. These _gaps_ or lower
bounds are very similar to Problem 4 but in the case of logarithms. Our goal
is to reuse the analogy between polynomials and integers in order to deduce a
lower bound for a non trivial class of instances of Problem 8 via a lower
bound on the order of a non-zero sum of logarithms of real polynomials.

See 2

###### Proof.

First, if $f_{i}(0)>0$, the power series $\log f_{i}(x)$ is well defined in a
neighborhood of 0. So, $S$ admits a valid power series expansion. Now, we have

$\displaystyle
S^{\prime}(x)=\sum_{i=1}^{n}c_{i}\frac{f_{i}^{\prime}(x)}{f_{i}(x)}=\frac{\sum_{i=1}^{n}c_{i}F_{i}(x)}{\prod_{i=1}^{n}f_{i}(x)},$

with $F_{i}(x)=f_{i}^{\prime}(x)\prod_{j\neq i}f_{j}(x)$, is a polynomial of
degree $\leq(n-1)d+d-1=nd-1$. As $f_{i}(0)\neq 0$, we have:

$\displaystyle\operatorname{ord}(S^{\prime})=\operatorname{ord}\left(\sum_{i=1}^{n}c_{i}F_{i}(x)\right)\leq\deg\left(\sum_{i=1}^{n}c_{i}F_{i}(x)\right)\leq
nd-1.$

Finally,

$\displaystyle\operatorname{ord}(S)\leq\operatorname{ord}(S^{\prime})+1\leq
nd.$

∎

And now, we can instantiate Proposition 2 over integers and obtain the
following gap theorem for a restricted but non trivial class of the instances
of Problem 8.

See 6

###### Proof.

We choose any integer polynomials $p_{1},p_{2}$ satisfying the following
conditions and show that they satisfy the claimed bounds:

$\displaystyle p_{1}(n,d)$ $\displaystyle\geq 20dn\log(dn),$ (5)
$\displaystyle p_{2}(n,d)$ $\displaystyle\geq 1+dn(\log(dn)+1).$ (6)

One can write $E$ as follows:

$\displaystyle E$ $\displaystyle=\underbrace{\sum_{i=1}^{n}c_{i}d_{i}\log
X}_{=A}+\underbrace{\sum_{i=1}^{n}c_{i}\log\left(1+\frac{b_{1,i}}{X}+\dots+\frac{b_{d_{i},i}}{X^{d_{i}}}\right)}_{=S}.$

If $\mathbf{A\neq 0}$, as $\sum_{i=1}^{n}c_{i}d_{i}$ is a non-zero integer, we
have

$\displaystyle\left|A\right|\geq\log X.$

So an upper bound for $S$ of the form $\left|S\right|\leq\frac{1}{2}\log X$ is
enough to prove that $\left|E\right|\geq\frac{1}{2}\log X$. And we have the
bound

$\displaystyle\left|S\right|$ $\displaystyle\leq nC\max_{1\leq i\leq
n}\log\left(1+\frac{b_{1,i}}{X}+\dots+\frac{b_{d_{i},i}}{X^{d_{i}}}\right).$

Now, as $\forall x\geq 0,\log(1+x)\leq x$, and
$\frac{b_{1,i}}{X}+\dots+\frac{b_{d_{i},i}}{X^{d_{i}}}\leq\frac{B}{X-1}$, we
have

$\displaystyle\left|S\right|$ $\displaystyle\leq nC\frac{B}{X-1}.$

But, as $C\leq X^{\frac{1}{2}}$

$\displaystyle\left|S\right|\leq nC\frac{B}{X-1}$
$\displaystyle\leq\frac{nBX^{\frac{1}{2}}}{X-1}\leq\frac{2nB}{X^{\frac{1}{2}}}\leq\frac{2nB}{(B+1)^{\frac{1}{2}p_{1}(n,d)}},$

because $X-1\geq\frac{X}{2}$ since $X\geq 2$. Then, to have
$\left|S\right|\leq\frac{1}{2}\log X$, it is sufficient that:

$\displaystyle p_{1}(n,d)\log(B+1)(B+1)^{\frac{1}{2}p_{1}(n,d)}-4nB\geq 0.$
(7)

One can easily check that Equation 7 holds using Equation 5 and thus,
$\left|E\right|\geq\frac{1}{2}\log X\geq\frac{1}{X^{p_{2}(n,d)}}$.

If $\mathbf{A=0}$, we show that
$\left|E\right|=\left|S\right|\geq\frac{1}{X^{p_{2}(n,d)}}$. Let
$y=\frac{1}{X}$, we have

$S=\sum_{i=1}^{n}c_{i}\underbrace{\log\left(1+b_{1,i}y+\dots+b_{d_{i},i}y^{d_{i}}\right)}_{=h_{i}(y)}=\sum_{j\geq
1}\underbrace{y^{j}\sum_{i=1}^{n}c_{i}h_{i,j}}_{S_{j}}$ $\text{with
}h_{i}(y)=\sum_{j=1}^{\infty}h_{i,j}y^{j}=\sum_{k=1}^{\infty}\frac{(-1)^{k+1}}{k}\left(b_{1,i}y+\dots+b_{d_{i},i}y^{d_{i}}\right)^{k}.$

By applying Proposition 2, the minimum exponent $\ell$ such that $S_{\ell}\neq
0$ is such that $\ell\leq dn$. The idea of the proof is to show that for every
$t\geq 1$,

$\displaystyle\frac{\left|S_{\ell+t}\right|}{\left|S_{\ell}\right|}\leq\frac{1}{2^{t+1}},$
(8)

because in this case, we would have

$\displaystyle\left|S\right|\geq\left|\left|S_{\ell}\right|-\left|S_{\ell+1}\right|-\dots\right|\geq\left|\left|S_{\ell}\right|-\frac{1}{2}\left|S_{\ell}\right|\right|=\frac{1}{2}\left|S_{\ell}\right|,$
(9)

and one can obtain a lower bound for $\left|S\right|$ via a lower bound for
$\left|S_{\ell}\right|$. But to satisfy Equation 8, one also needs an upper
bound on $S_{\ell+t}$, for every $t$.

These two lower and upper bounds are both obtained as in the proof of Theorem
2 in [KS12]. The technical details can be found in Section 5.1. In the end, we
show that conditions on $p_{1}$ and $p_{2}$ (Equations 5 and 6) are sufficient
in order to satisfy Equations 8 and 9 and then deduce that
$\left|E\right|=\left|S\right|\geq\frac{1}{X^{p_{2}(n,d)}}$.

∎

###  5.1 Bounds for the Proof of Theorem 6

We recall that we have

$S=\sum_{i=1}^{n}c_{i}\underbrace{\log\left(1+b_{1,i}y+\dots+b_{d_{i},i}y^{d_{i}}\right)}_{=h_{i}(y)}=\sum_{j\geq
1}\underbrace{y^{j}\sum_{i=1}^{n}c_{i}h_{i,j}}_{S_{j}}$ $\text{with
}h_{i}(y)=\sum_{j=1}^{\infty}h_{i,j}y^{j}=\sum_{k=1}^{\infty}\frac{(-1)^{k+1}}{k}\left(b_{1,i}y+\dots+b_{d_{i},i}y^{d_{i}}\right)^{k}.$

The goal is to show that $p_{1}(n,d)$ and $p_{2}(n,d)$ satisfying Equations 5
and 6 give both an upper bound and a lower bound on $S_{j}$ that allows us to
satisfy Equation 8.
An upper bound on $S_{j}$:
For any $j$, $h_{i,j}$ is contributed by the term of order $j$ in the sum
$\sum\frac{(-1)^{k+1}}{k}\left(b_{1,i}y+\dots+b_{d_{i},i}y^{d_{i}}\right)^{k}$
for $k$ in range $\left[1,j\right]$. Then

$\displaystyle h_{i,j}$
$\displaystyle=\sum_{k=1}^{j}\frac{(-1)^{k+1}}{k}v_{k,i,j},\text{ with }$
$\displaystyle v_{k,i,j}$
$\displaystyle=\sum_{\begin{subarray}{c}k_{1}+2k_{2}+\dots+d_{i}k_{d_{i}}=j\\\
k_{1}+k_{2}+\dots+k_{d_{i}}=k\end{subarray}}\binom{k}{k_{1},k_{2},\dots,k_{d_{i}}}b_{1,i}^{k_{1}}\dots
b_{d_{i},i}^{k_{d_{i}}}.$

where $k_{1},k_{2},\dots,k_{d_{i}}$ are non-negative integers. Notice that for
$k<\frac{j}{d_{i}},v_{k,i,j}=0$ as the sum is empty. Then

$\displaystyle\left|v_{k,i,j}\right|$
$\displaystyle\leq\sum_{k_{1}+k_{2}+\dots+k_{d_{i}}=k}\binom{k}{k_{1},k_{2},\dots,k_{d_{i}}}\left|b_{1,i}\right|^{k_{1}}\dots\left|b_{d_{i},i}\right|^{k_{d_{i}}}$
$\displaystyle\leq(Bd_{i})^{k}\leq(Bd)^{k}.$ (Multinomial theorem)

Since $\left|\frac{(-1)^{k+1}}{k}\right|\leq 1$,

$\displaystyle\left|h_{i,j}\right|\leq\sum_{k=0}^{j}(Bd)^{k}\leq(Bd)^{j+1}.$

Hence, let $S=\sum_{j\geq 1}S_{j}$, with
$S_{j}=y^{j}\sum_{i=1}^{n}c_{i}h_{i,j}$ satisfies for all $j\geq 1$

$\displaystyle\left|S_{j}\right|\leq y^{j}nC(Bd)^{j+1}.$

A lower bound on $S_{\ell}$:
Now we prove a lower bound for
$\left|S_{\ell}\right|=y^{\ell}\left|\sum_{i=1}^{n}c_{i}h_{i,\ell}\right|\neq
0$. We have

$\displaystyle\sum_{i=1}^{n}c_{i}h_{i,\ell}$
$\displaystyle=\sum_{i=1}^{n}c_{i}\sum_{k=1}^{\ell}\frac{(-1)^{k+1}}{k}v_{k,i,\ell}=\sum_{k=1}^{\ell}\frac{(-1)^{k+1}}{k}\underbrace{\left(\sum_{i=1}^{n}c_{i}v_{k,i,\ell}\right)}_{\in\mathbb{Z}}.$

So $\ell!\left(\sum_{i=1}^{n}c_{i}h_{i,\ell}\right)$ is an integer. Then, if
$\sum_{i=1}^{n}c_{i}h_{i,\ell}\neq 0$,

$\displaystyle\ell!\left|\sum_{i=1}^{n}c_{i}h_{i,\ell}\right|\geq 1.$

And finally, we obtain

$\displaystyle\left|S_{\ell}\right|\geq\frac{y^{\ell}}{\ell!}.$

With the obtained upper and lower bound, we can now deduce a requirement that
ensures Equation 8 to be satisfied. Actually, it is sufficient that for every
$t\geq 1$,

$\displaystyle
ny^{t}C(Bd)^{\ell+t+1}\ell!\leq\frac{1}{2^{t+1}},\emph{i.e}.\hbox{}$ (10)
$\displaystyle X^{t}\geq 2^{t+1}nC(Bd)^{\ell+t+1}\ell!.$ (11)

Recall that $C\leq X^{1/2}$ and $\ell\leq dn$, so it suffices that

$\displaystyle X^{t-\frac{1}{2}}\geq 2^{t+1}n(Bd)^{nd+t+1}(nd)!.$

By applying $\log$, it is sufficient that for all $t\geq 1$,

$\displaystyle(t-\frac{1}{2})p_{1}(n,d)\log(B+1)\geq$
$\displaystyle(t+1)\log(2)+\log(n)$
$\displaystyle+(nd+t+1)\log(Bd)+nd\log(nd).$

Therefore, one can show that $p_{1}(n,d)\geq 20dn\log(dn)$ is sufficient (this
bound is not optimized at all). And in this case, by Equation 9, we have

$\displaystyle\left|S\right|\geq\frac{1}{2}\left|S_{\ell}\right|\geq\frac{1}{2\ell!X^{\ell}}\geq\frac{1}{2^{\ell\log\ell+1}X^{\ell}}\geq\frac{1}{X^{p_{2}(n,d)}},$

with $p_{2}(n,d)\geq dn(\log(dn)+1)+1$.

##  6 Conclusion and Open Questions

In Theorem 5, we greatly generalized the ideas developed in [KS12]. This leads
to the fact that the results in [KS12] can be generalized to various other
families of power series, as evident in Corollary 1. The Wronskian approach of
[KS12] was also proven to be tight, up to a polynomial blowup. Our work also
made significant progress in the straight line variant of the classical SSR
equality problem. We also extended the results of [KS12] for sign testing of
the sum of square roots of polynomial integers to a linear combination of
logarithms of polynomial integers, solving a special case of Problem 2
proposed in [ESY14]. There are several directions for future research:

  1. 1.

item ii in Corollary 1 applies to some special cases of solutions of 2nd order
differential equations, like $\cos f$ where $f$ is a polynomial. It would be
intriguing to see if this applies to generic solutions of higher order
equations.

  2. 2.

Can we generalize Theorem 1 by bounding the order of sums of arbitrary
algebraic power series? Square roots of polynomials are examples of algebraic
functions. However, finding a satisfying way to bound the order of the
Wronskian determinant of a family of algebraic power series is challenging.
The best upper bound we could find is about $r^{\mathrm{poly}(n)}d$ where
$(r,d)$ is a bound on the bi-degree of the polynomial equations satisfied by
the algebraic power series.

  3. 3.

We saw that both the sign testing of the sum of square roots and logarithms
are specific examples of $\operatorname{PosSLP}$. In order to advance in
understanding the complexity of $\operatorname{PosSLP}$, it is important to
consider other special cases. For instance, the following are additional
special cases of $\operatorname{PosSLP}$ that are worth exploring.

    1. (a)

Given positive integers $a,b,c,n$ in binary, determine the sign of
$a^{n}+b^{n}-c^{n}$. To our knowledge, even this very special case of
$\operatorname{PosSLP}$ remains open.

    2. (b)

Given an integer trinomial
$f(x)\vcentcolon=c_{1}+c_{2}x^{a}_{2}+c_{3}x^{a_{3}}\in\mathbb{Z}[x]$ and a
rational $\frac{p}{q}$, determine the sign of $f\left(\frac{p}{q}\right)$.
This problem was posed in [Koi19]. Significant progress was made on it in
[BDR22] but the general form of the problem remains open.

##  7 Acknowledgements

Louis Gaillard expresses gratitude to Peter Bürgisser for hosting him during
an internship at TU Berlin in the summer of 2022, where this research work was
conducted. Gorav Jindal was a member of Graduiertenkolleg ”Facets of
Complexity/Facetten der Komplexität” (GRK 2434) and Institut für Mathematik,
Technische Universität Berlin, where most of the work was completed.

## References

  * [ABKPM09] Eric Allender, Peter Buergisser, Johan Kjeldgaard-Pedersen, and Peter Bro Miltersen.  On the complexity of numerical analysis.  SIAM Journal on Computing, 38(5):1987–2006, 2009.
  * [Bak98] A. Baker.  Logarithmic forms and the abc- conjecture, pages 37–44.  De Gruyter, Berlin, New York, 1998.
  * [BCSS97] Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale.  Complexity and Real Computation.  Springer-Verlag, Berlin, Heidelberg, 1997.
  * [BD10] Alin Bostan and Philippe Dumas.  Wronskians and linear independence.  The American Mathematical Monthly, 117(8):722–727, 2010.
  * [BDR22] Eric Boniface, Wei Deng, and J. Maurice Rojas.  Trinomials and deterministic complexity limits for real solving, 2022\.
  * [Blö91] Johannes Blömer.  Computing sums of radicals in polynomial time.  In 32nd Annual Symposium on Foundations of Computer Science, 1-4 October 1991, pages 670–677, San Juan, Puerto Rico, 1991. IEEE Computer Society.
  * [Blö98] Johannes Blömer.  A probabilistic zero-test for expressions involving roots of rational numbers.  In Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, and Geppino Pucci, editors, Algorithms — ESA’ 98, pages 151–162, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.
  * [BNSW22] Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi, and James Worrell.  Identity testing for radical expressions.  In Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’22, New York, NY, USA, 2022. Association for Computing Machinery.
  * [Bre76] Richard P Brent.  Fast multiple-precision evaluation of elementary functions.  Journal of the ACM (JACM), 23(2):242–251, 1976.
  * [BS96] Eric Bach and Jeffrey Shallit.  Algorithmic Number Theory.  MIT Press, Cambridge, MA, USA, 1996.
  * [BW93] A. Baker and G. Wüstholz.  Logarithmic forms and group varieties.  Journal für die reine und angewandte Mathematik, 442:19–62, 1993\.
  * [ESY14] Kousha Etessami, Alistair Stewart, and Mihalis Yannakakis.  A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing.  ACM Trans. Comput. Theory, 6(2):9:1–9:23, 2014.
  * [GGJ76] M. R. Garey, R. L. Graham, and D. S. Johnson.  Some np-complete geometric problems.  In Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, STOC ’76, page 10–22, New York, NY, USA, 1976. Association for Computing Machinery.
  * [Kne75] Martin Kneser.  Lineare abhängigkeit von wurzeln.  Acta Arithmetica, 26(3):307–308, 1975.
  * [Koi19] Pascal Koiran.  Root separation for trinomials.  Journal of Symbolic Computation, 95:151–161, 2019.
  * [KS12] Neeraj Kayal and Chandan Saha.  On the sum of square roots of polynomials and related problems.  ACM Trans. Comput. Theory, 4(4), nov 2012.
  * [Mal01] Gregorio Malajovich.  An eective version of kronecker’s theorem on simultaneous diophantine approximation.  Technical report, Technical report, City University of Hong Kong, 2001\.
  * [QW06] Jianbo Qian and Cao An Wang.  How much precision is needed to compare two sums of square roots of integers?  Information Processing Letters, 100(5):194–198, 2006.
  * [Ser81] Jean-Pierre Serre.  Quelques applications du théoreme de densité de chebotarev.  Publications Mathématiques de l’IHÉS, 54:123–201, 1981\.
  * [SL96] Peter Stevenhagen and Hendrik Willem Lenstra.  Chebotarëv and his density theorem.  The Mathematical Intelligencer, 18(2):26–37, 1996.
  * [VV75] M Voorhoeve and A.J Van Der Poorten.  Wronskian determinants and the zeros of certain functions.  Indagationes Mathematicae (Proceedings), 78(5):417–424, 1975.