In this paper we study in detail the properties of the algebraic winding number
proposed in [3] with respect to complex root counting in rectangles.
We also propose a new algebraic winding number which computes
the number of complex roots of a polynomial in a rectangle under no
assumptions, including roots on edges or vertices with appropriate counting. We extend both winding numbers to rational functions,
obtaining then an algebraic version of the argument principle for

Keywords: Root counting, Cauchy index, Winding number, Argument principle.

MSC2020: 12D10, 13J30, 14Q20.

§ INTRODUCTION

§.§ Real rational functions: Sign and Cauchy index

Let $\N = \{0, 1, 2, \dots, \}$. Let $\R$ be a real closed field and $x \in \R$. We consider the sign of $x$ as usual as

\sign(x) =
\left \{
\begin{array}{ll}
1 & \hbox{if } x > 0, \\[3mm]
0 & \hbox{if } x = 0, \\[3mm]
-1 & \hbox{if } x < 0.
\end{array} \right.

Given $P, Q \in \R[X] \setminus \{0\}$ they can be written uniquely as

P = (X - x)^{\mult_x(P)}\,{P}_x, \qquad
Q = (X - x)^{\mult_x(Q)}\,{Q}_x,

$\mult_x(P), \mult_x(Q) \in \N
$, $P_x , Q_x \in \R[X]$ and
$P_x(x) \ne 0, Q_x(x) \ne 0$.
We consider the valuation defined by $x$ on $\R(X)$ by

\val_x(P/Q) = \left \{
\begin{array}{ll}
\mult_x(P)-\mult_x(Q) & \hbox{if } P \ne 0, \\[3mm]
+\infty & \hbox{if } P = 0.
\end{array} \right.

Let $P, Q \in \R[X]$.
We define the Sign of $(P, Q)$ at $x$, which is the sign of the rational function $P/Q$
at $x$ whenever this makes sense, and $0$ otherwise. The reason why we consider pairs of polynomials instead
of rational functions is because in the following sections, the case $Q=0$ will also be of use.

For $P, Q \in \R[X]$ and $x \in \R$,

\Sign(P, Q, x) : =
\left \{
\begin{array}{ll}
\sign\left(P_x(x)Q_x(x)\right) &
\hbox{if } P \ne 0, Q\ne 0 \hbox{ and } \val_x(P/Q) = 0, \\[3mm]
0 & \hbox{otherwise.} \\[3mm]
\end{array} \right.

It can be easily checked that whenever $P(x)$ and $Q(x)$ are not simultaneously $0$,
$\Sign(P, Q, x) = \sign(P(x)Q(x))$.

We also consider the sign variation defined as follows.

For $P, Q \in \R[X]$ and $x \in \R$,

{\rm Var}_x(P,Q) := \frac12- \frac12\Sign(P,Q,x).

Also, for $a, b \in \R$,

$${\rm Var}_a^b(P, Q) :=
{\rm Var}_a(P, Q) -{\rm Var}_b(P, Q) = -\frac12 \Sign(P, Q, a) +
\frac12 \Sign(P, Q, b).

Note that ${\rm Var}_x(P,Q)$ coincides with the usual notion of sign variation whenever $P(x)$ and $Q(x)$ are not simultaneously $0$, since in this case:

{\rm Var}_x(P,Q) =
\left \{
\begin{array}{ll}
0 & \hbox{if } P(x)Q(x) > 0, \\[3mm]
\frac12& \hbox{if } P(x)Q(x) = 0, \\[3mm]
1 & \hbox{if } P(x)Q(x) < 0.
\end{array} \right.

We define the Cauchy index of $(P, Q)$ first at a point and then on an interval,
following [3].
As before, we need to consider pairs of polynomials instead of rational functions in order to not to exclude
the case $Q = 0$.

For $P, Q \in \R[X]$, $x \in \R$ and $\varepsilon \in \{+, -\}$,

{\rm Ind}_x^{\varepsilon} (P, Q ) := \left\{
\begin{array}{ll}
\frac{1}2  \sign \left(
Q_x(x) \right)  &
\hbox{if } P \ne 0, Q \ne 0, \varepsilon = + \hbox{ and } \val_x(P/Q)<0,\\[3mm]
\frac{1}2  (-1)^{\val_x(P/Q)}
\sign\left(
Q_x(x) \right)  &
\hbox{if } P \ne 0, Q \ne 0,  \varepsilon = - \hbox{ and } \val_x(P/Q)<0, \\[6mm]
0 & \hbox{otherwise;}
\end{array}
\right.

{\rm Ind}_x(P,Q) :=  {\rm Ind}_x^{+}(P, Q) - {\rm Ind}_x^{-} (P, Q).

It is easy to see that, if $\val_x(P/Q) < 0$,
${\rm Ind}_x^{+} (P, Q )$ is half the sign of $P/Q$ at a sufficiently small interval to the right of $x$ and
${\rm Ind}_x^{-} (P, Q )$ is half the sign of $P/Q$ at a sufficiently small interval to the left of $x$.
We illustrate the definition of Cauchy index at a point considering the graph of the rational function $P/Q$
around $x$ in different cases.

[-] (-6.5,0) – (-4,0);
[-] (-3,0) – (-0.5,0);
[-] (0.5,0) – (3,0);
[-] (4,0) – (6.5,0);
[-] (-5.2,-0.1) – (-5.2,0.1) node[above] $x$ ;
[-] (-1.7,-0.1) – (-1.7,0.1) node[above] $x$ ;
[-] (1.7,-0.1) – (1.7,0.1) node[above] $x$ ;
[-] (5.2,-0.1) – (5.2,0.1) node[above] $x$ ;
[line width=0.8pt, domain=-6.5:-5.3,smooth,variable=] plot (+0.05,1/(+5)+1.85);
[line width=0.8pt, domain=-5.05:-4,smooth,variable=,] plot (-0.05,-1/(+5.4)+1.35);
[line width=0.8pt, domain=-3:-1.8,smooth,variable=] plot (,1/(+1.5)+2);
[line width=0.8pt, domain=-1.5:-0.5,smooth,variable=] plot (-0.05,1/(+1.8)-2);
[line width=0.8pt, domain=0.5:1.5,smooth,variable=] plot (+0.1,-2/(-2)-2.5);
[line width=0.8pt, domain=1.65:3,smooth,variable=] plot (+0.05,-0.3/(-1.5)+0.75);
[line width=0.8pt, domain=4:5.25,smooth,variable=,] plot (-0.05,-0.2/(-5.4)+0.25);
[line width=0.8pt, domain=5.25:5.9,smooth,variable=] plot (+0.1,1/(-5)-2.4);
at (-5.2,-2.1) $\Ind_x(P,Q) = 0 $;
at (-1.7,-2.1) $\Ind_x(P,Q) = 1 $;
at (1.7,-2.1) $\Ind_x(P,Q) = -1 $;
at (5.2,-2.1) $\Ind_x(P,Q) = 0 $;

For $P, Q \in \R[X]$
and $a, b \in \R$,

{\rm Ind}_a^b(P,Q) :=
\left \{
\begin{array}{ll}
{\rm Ind}_a^+(P, Q)  +
\displaystyle{\sum_{x \in (a,b) }  {\rm Ind}_x (P, Q)}
- {\rm Ind}_b^-(P, Q) & \hbox{if }  a < b, \\[3mm]
-{\rm Ind}_b^a(P,Q) & \hbox{if } b < a , \\[3mm]
0 & \hbox{if }  a = b.
\end{array} \right.

Note that the sum is well-defined since for any $P$ and $Q$ we have
$\Ind_x(P, Q) \ne 0$ only for a finite number of $x \in \R$.

In the following picture we consider again the graph of the function
$P/Q$, this time in $[a, b]$.

[-] (-7,0) – (-1,0);
[-] (1,0) – (7,0);
[-] (-6.8,-0.1) – (-6.8,0.1) node[above] $a$;
[-] (-1.2,-0.1) – (-1.2,0.1) node[above] $b$;
[-] (1.2,-0.1) – (1.2,0.1) node[above] $a$;
[-] (6.8,-0.1) – (6.8,0.1) node[above] $b$ ;
[line width=0.8pt, domain=-7:-6.13,smooth,variable=] plot (+0.05,1/(+5.9)+3);
[line width=0.8pt, domain=-5.9:-4.1,smooth,variable=,] plot (,-1/((+6.05)*(+3.95))-1.3);
[line width=0.8pt, domain=-3.9:-2.2,smooth,variable=] plot (,(+3)/((+4.11)*(+1.9)));
[line width=0.8pt, domain=-1.9:-1,smooth,variable=] plot (-0.1,(+3)/((+4.1)*(+2.05))-1.2);
[line width=0.8pt, domain=1:2.46,smooth,variable=] plot (,-(-3)/((-4.1)*(-2.55))-1.5);
[line width=0.8pt, domain=2.5:5,smooth,variable=] plot (,-0.65*(-3.5)/((-5.2)*(-2.35))+0.3);
[line width=0.8pt, domain=5.2:6.69,smooth,variable=] plot (,-0.5*(-6)/((-5.05)*(-6.8))+0.3);
at (-4,-2.1) $\Ind_a^b(P,Q) = 1 + 0 +1 = 2 $;
at (4,-2.1) $\Ind_a^b(P,Q) = -1 -1 -\frac12 = -\frac52$;

If $P$ and $Q$ are not simultaneously $0$, then any common factor of $P$ and $Q$ can
be simplified in both $P$ and $Q$ without changing the value of $\Sign(P, Q, x)$, $\Var_a^b(P, Q)$ or
$\Ind_a^b(P, Q)$ for any $x, a, b$ in $\R$.

The algorithmic symbolic computation of the Cauchy index
defined as in Definition <ref>
can be done
using Sturm sequences as in <cit.> or subresultant
polynomials as in [4].
Classicaly, the Cauchy index is definded on intervals under the assumption that $P$ and $Q$ do not vanish at the endpoints and can be computed
by various symbolic methods (see <cit.>).

Before going on, we recall the inversion formula (see <cit.>),  which relates the Cauchy Index with the sign variation on an interval.

Let $P, Q \in \R[X]$ and $a, b \in \R$. Then

\Ind_a^b(P, Q) + \Ind_a^b(Q, P) = {\rm Var}_a^b(P, Q).

§.§ Complex rational functions: winding number on rectangles

Let $\C = \R[i]$ be the algebraic closure of $\R$.

For $F \in \C[X, Y]$, we denote
$F_{\rm re}$ and  $F_{\rm im}$ the real and imaginary parts of $F$, i.e.
the unique
polynomials in $\R[X, Y]$ such that the identity

F(X, Y) =
F_{\rm re}(X,Y)+iF_{\rm im}(X,Y)

in $\C[X, Y]$ holds.

(see <cit.>) Let $F \in \C[X, Y]$,
$x_0, x_1, y_0, y_1 \in \R$ with $x_0 < x_1$ and $y_0 < y_1$,
$\Gamma := [x_0, x_1] \times [y_0, y_1]  \subset \R^2$.
We consider the following winding number w of $F$ on $\partial \Gamma$:

\begin{array}{rcl}
\ind(F \, | \, \partial \Gamma) &:= & \frac12 \Big(
\Ind_{x_0}^{x_1}(F_{\rm re}(T, y_0),F_{\rm im}(T, y_0))
\Ind_{y_0}^{y_1}
(F_{\rm re}(x_1,T),F_{\rm im}(x_1,T))
\\[3mm]
\Ind_{x_1}^{x_0}
(F_{\rm  re}(T, y_1),F_{\rm im}(T, y_1))
\Ind_{y_1}^{y_0}
(F_{\rm re}(x_0,T),F_{\rm im}(x_0,T))
\Big). \\[0.5cm]
\end{array}

[-] (-4,0) – (4,0);
[-] (0,-2.5) – (0,2.5);
at (3,2) I;
at (-3,2) II;
at (-3,-2) III;
at (3,-2) IV;
[line width=0.8pt, domain=1:3]
plot ( 0.7*((-2)^2 + 2*(-2) - 0.75)) , 0.7*((-2)^2 - 1.5*(-2) -1));
[Triangle[scale=1.8]-, domain=-2.2:-2,smooth,variable=]         plot(  0.7*((--2)^2 + 2*(--2) - 0.75) , 0.7*((--2)^2 - 1.5*(--2) -1));
[line width=0.8pt, domain=1:3]
plot ( 0.7*( -(-2)^2 - 2.5*(-2) + 0.75) , 0.7*(-(-2)^2 + 2*(-2) + 1.5));
[Triangle[scale=1.8]-, domain=-2.6:-2.4,smooth,variable=]
plot ( 0.7*( -(--2)^2 - 2.5*(--2) + 0.75) , 0.7*(-(--2)^2 + 2*(--2) + 1.5));
[line width=0.8pt, domain=1:3]
plot ( 0.7*( (-2)^2 - 2*(-2) - 1.75) , 0.7*((-2)^2 + 2.5*(-2) - 1));
[Triangle[scale=1.8]-, domain=2:2.2,smooth,variable=]
plot ( 0.7*( (-2)^2 - 2*(-2) - 1.75) , 0.7*((-2)^2 + 2.5*(-2) - 1));
[line width=0.8pt, domain=1:3]
plot ( 0.7*( -(-2)^2 + 1.5*(-2) + 0.75) , 0.7*(-(-2)^2 -2*(-2) + 0.5));
[Triangle[scale=1.8]-, domain=1.7:2.1,smooth,variable=]
plot ( 0.7*( -(-2)^2 + 1.5*(-2) + 0.75) , 0.7*(-(-2)^2 -2*(-2) + 0.5));
(1.29, 0) circle[radius=4pt];
(0.72, 0) circle[radius=4pt];
(-1.06, 0) circle[radius=4pt];
(-1.62, 0) circle[radius=4pt];
at (0,-3.2) $\ind(F \, | \, \partial \Gamma) = 2$;

The idea behind this definition is,
if we go through the curve $F \circ \partial \Gamma$ following the counterclock sense,
to count one half of a turn each time this curve crosses the $X$-axis from quadrant IV to I or from
quadrant II to III, and minus one half of a turn each time it crosses the $X$-axis from quadrant I
to IV or from
quadrant III to II.
Since these crossings coincide with jumps of the rational function ${F_{\rm re}}/{F_{\rm im}}$ from $-\infty$ to $+\infty$
and from $+\infty$ to $-\infty$ respectively, the Cauchy index is an appropriate algebraic tool to
count the number of turns counterclockwise, which is (when  $F$ does not vanish on $\partial \Gamma$)
the classical definition of the winding number.

We consider a new variable $Z$ together with the inclusion $\C[Z] \subset
\C[X, Y]$ through the identity $Z = X + iY$.

Let $F = Z$ and $\Gamma = [0, 1] \times [0, 1]$,

\ind(F \, | \, \partial \Gamma) =  \frac12 \Big(
\Ind_{0}^{1}(T,0)
\Ind_{0}^{1}
(1,T) +
\Ind_{1}^{0}
\Ind_{1}^{0}
\Big)=\frac{1}{4}.

basic example illustrates why we consider the Cauchy index of a pair of polynomials $(P, Q)$ rather than the Cauchy index of a rational function $P/Q$:
otherwise the Cauchy index $\Ind_{0}^{1}(T,0)$ would not be well

Let $\Gamma \subset \R^2$ be a rectangle. For
any constant $\gamma \in \C$ we have $\ind(\gamma \, | \, \partial \Gamma) = 0$.
For a linear polynomial $F(Z) = Z - z_0$ with $z_0 \in \C$  we have (see <cit.>):

\ind(F \, | \, \partial \Gamma) = \left\{
\begin{array}{cl}
1 & \hbox{if } z_0 \hbox{ is in the interior of } \Gamma, \\[2mm]
\frac12 & \hbox{if } z_0 \hbox{ is in one of the edges of } \Gamma, \\[2mm]
\frac14 & \hbox{if } z_0 \hbox{ is in one of the vertices of } \Gamma, \\[2mm]
0 & \hbox{if } z_0 \hbox{ is in the exterior of } \Gamma. \\[2mm]
\end{array}
\right.

may lead to the idea that the
winding number $\ind$ could also work in general in $\C[Z] \setminus \{0\}$ for counting one quarter for roots
and poles on vertices. Indeed, this would be truth if only $\ind$ were additive with respect to multiplication in $\C[Z]\setminus \{0\}$.
Unfortunately this is not the general case as shown by the following
simple example.

Let $\Gamma = [0, 1] \times [0, 1] \subset \R^2$, $\alpha, \beta \in \R$ with
$0 < \beta < \alpha$ and $\gamma = \alpha + i \beta \in \C$. Then
$\ind(\gamma \, | \, \partial \Gamma) = 0$,
$\ind(Z \, | \, \partial \Gamma) = \frac14$ but
$\ind(\gamma Z \, | \, \partial \Gamma) = 0$ instead of $\frac14$.

[line width=0.8pt] (7, 0) – (8.96,0.4) – (8.56,2.36) – (6.6,1.96) – (7,0);
[-] (3.5, 0) – (11.8,0);
[-] (7, -1.4) – (7,3.2);
at (6.5,-0.3) $(0,0)$;
at (9.5,0.4) $(\alpha,\beta)$;
at (6,2.2) $(-\beta,\alpha)$;
at (9.5, 2.7) $(\alpha-\beta,\alpha+\beta)$;
at (11.5,2.8) I;
at (4.0,2.8) II;
at (4.0,-1) III;
at (11.5,-1) IV;
[Triangle[scale=1.8]-, domain=-0.2:1,smooth,variable=]
plot ( (1-) + 7 , (0.4/1.96)*(1-)   );
[Triangle[scale=1.8]-, domain=0.6:1,smooth,variable=]
plot ( () + 6.8 , (0.4/1.96)*() +2  );
[Triangle[scale=1.8]-, domain=0.6:1,smooth,variable=]
plot (  -(0.4/1.96)*() +6.95  ,()+0.2  );
[Triangle[scale=1.8]-, domain=0.6:1,smooth,variable=]
plot (  -(0.4/1.96)*(1-) +8.8  ,(1-)+1.1  );
(7, 0) circle[radius=2pt];
(8.96, 0.4) circle[radius=2pt];
(8.56, 2.36) circle[radius=2pt];
(6.6, 1.96) circle[radius=2pt];

Note that in the above example, even though the curve does not
cross the $X$-axis, it does cross the $Y$-axis. This motivates our definition of a new winding number $\mind$.

Let $F \in \C[X, Y]$,
$x_0, x_1, y_0, y_1 \in \R$ with $x_0 < x_1$ and $y_0 < y_1$,
$\Gamma := [x_0, x_1] \times [y_0, y_1]  \subset \R^2$.
We define the following winding number W of $F$ on $\partial \Gamma$:

\mind(F \, | \, \partial \Gamma) \ := \ \frac12 \Big(
\ind(F \, | \, \partial \Gamma) +
\ind(iF \, | \, \partial \Gamma)
\Big).$$

As will be seen later (Proposition <ref>), the new definition of $\mind$ is indeed additive with respect to multiplication in $\C[Z]\setminus \{0\}$ and  will also be good to
deal with the case where $F$ does vanish on edges or vertices of $\Gamma$
(Theorem <ref>).

For $F \in \C[X, Y]$, we denote $\overline F \in \C[X, Y]$ the conjugate polynomial

\overline F(X, Y) =
F_{\rm re}(X,Y)- iF_{\rm im}(X,Y).

Now consider $F, G \in \C[X, Y]$ with $G \ne 0$. Then $G_{\re}^2 + G_{\im}^2 \ne 0 \in \R[X, Y]$ and in $\C(X, Y)$ we have the identity

\frac{F}G \quad = \quad
\frac{F\overline G}{G\overline G} \quad = \quad
\underbrace{\frac{(F \overline G)_{\re} }{G_{\re}^2 + G_{\im}^2}}_{\in \R(X, Y)}
\ + \ i \
\underbrace{\frac{ (F\overline G)_{\im}}{G_{\re}^2 + G_{\im}^2}}_{\in \R(X, Y)},

which defines the real and imaginary part of $F/G$.
Note that the quotient in $\R(X, Y)$ between the real and imaginary parts of $F/G \in \C(X, Y)$ is the same than the quotient in $\R(X, Y)$
of the real and imaginary part of $F \overline G \in \C[X, Y]$.
This motivates the following definition.

Let $F/ G \in \C(X, Y)$,
$x_0, x_1, y_0, y_1 \in \R$ with $x_0 < x_1$ and $y_0 < y_1$,
$\Gamma := [x_0, x_1] \times [y_0, y_1]  \subset \R^2$.
We define the following winding numbers of $F/G$ on $\partial \Gamma$:

\begin{array}{rcl}
\ind(F/G \, | \, \partial \Gamma) &:= &
\ind(F \overline G \, | \, \partial \Gamma), \\[0.5cm]
\mind(F/G \, | \, \partial \Gamma) &:= &
\mind(F \overline G \, | \, \partial \Gamma).
\end{array}

Definition <ref> extends the definitions
of $\ind$ and
$\mind$ made initially for $\C[X, Y]$ to $\C(X, Y)$.
From Definitions <ref> and <ref>
we obtain

\begin{array}{rcl}
\ind(F / G \, | \, \partial \Gamma) &= & \frac12 \Big(
\Ind_{x_0}^{x_1}((F\overline G)_{\rm re}(T, y_0),(F\overline G)_{\rm im}(T, y_0))
\Ind_{y_0}^{y_1}
((F\overline G)_{\rm re}(x_1,T),(F\overline G)_{\rm im}(x_1,T))
\\[3mm]
\Ind_{x_1}^{x_0}
((F\overline G)_{\rm  re}(T, y_1),(F\overline G)_{\rm im}(T, y_1))
\Ind_{y_1}^{y_0}
((F\overline G)_{\rm re}(x_0,T),(F\overline G)_{\rm im}(x_0,T))
\Big). \\[0.5cm]
\end{array}

It can be easily checked that $\ind$ and
$\mind$ are well defined for $F/G \in \C(X, Y)$, in the sense
that they do not depend on the election of the numerator $F$ and the denominator $G$ in $\C[X, Y]$.

§.§ Goals of this paper

The classical argument principle applied to a rational function $F/G \in \C(Z)$ on a
rectangle $\Gamma$,
states that, as long as $F/G$ has no zeros or poles on $\partial \Gamma$,
the winding number of the curve $(F/G) \circ \partial \Gamma$,
defined analytically as

\frac{1}{2\pi i} \int_{\partial \Gamma} \frac{(F/G)'(z)}{(F/G)(z)}dz

counts the number of
zeros (with multiplicity) minus the number of poles (with order) of $F/G$
inside $\Gamma$ (see <cit.>).

This paper has two main goals (Theorem <ref> and Theorem <ref>) which can be considered as algebraic versions of the argument principle on rectangles, and work even if the rational function  have zeros or poles on $\partial \Gamma$.

$F/G \in \C(Z) \setminus \{0\}$  and
$\Gamma \subset \R^2$ a rectangle. Then $\mind( F/G \, | \, \partial \Gamma)$ counts the number of zeros (with multiplicity) minus
the number of poles (with order) of $F/G$ in $\Gamma$. Zeros and poles
on the edges count for one half. Zeros and poles on the vertices count for
one quarter.

Before stating the next result,
we extend the valuation
we considered before to $\C(Z)$.

Given $F, G \in \C[Z] \setminus \{0\}$ they can be written uniquely as

F = (Z - z)^{\mult_z(F)}\,{F}_z, \qquad
G = (Z - z)^{\mult_z(F)}\,{G}_z,

$\mult_z(F), \mult_z(G) \in \N
$, $F_z , G_z \in \C[Z]$ and
$F_z(z) \ne 0, G_z(z) \ne 0$.
We consider the valuation defined by $z$ on $\C(Z)$ by

\val_z(F/G) = \left \{
\begin{array}{ll}
\mult_z(F)-\mult_z(G) & \hbox{if } F \ne 0, \\[3mm]
+\infty & \hbox{if } F = 0.
\end{array} \right.

$F/G \in \C(Z) \setminus \{0\}$ and
$\Gamma \subset \R^2$ a rectangle
such that $F/G$  has
even valuation at the vertices of $\Gamma$.
Then $\ind( F/G \, | \, \partial \Gamma)$ counts the number of zeros (with multiplicity) minus
the number of poles (with order) of $F/G$ in $\Gamma$. Zeros and poles
on the edges count for one half. Zeros and poles on the vertices count for
one quarter.

As a corollary we obtain the following result.

$F/G \in \C(Z) \setminus \{0\}$ and
$\Gamma \subset \R^2$ a rectangle
such that $F/G$ does not
have zeros or poles on the vertices of $\Gamma$.
Then $\ind( F/G \, | \, \partial \Gamma)$ counts the number of zeros (with multiplicity) minus
the number of poles (with order) of $F/G$ in $\Gamma$. Zeros and poles
on the edges count for one half.

The statement  of  Theorem <ref> in the case of polynomials (instead of rational functions) comes from <cit.>.
The proof proposed by [3] had a flaw related to the fact that the  auxiliary product formula (<ref>) we discuss in Section  <ref>
(see <cit.>)
does not hold in full generality (see Example <ref> below).
For a polynomial $F$ which does not vanish on the  boundary of $\Gamma$, the proof of
Theorem <ref>
has already been fixed
(see details in <cit.>); but to our best knowledge,
Theorem <ref>
for a polynomial $F$ with roots on the edges of $\Gamma$, was not proved yet.

The rest of the paper is organized as follows. In Section <ref> we
characterize all cases where  the  auxiliary product formula (<ref>) is correct and
provide auxiliary product formulas
for the remaining cases.
In Section <ref> we
study the additivity
of the winding numbers $\ind$ and $\mind$ with respect to multipliaction in
$\C(Z) \setminus\{0\}$.
Finally, in Section <ref>,
we prove Theorem <ref>
and Theorem <ref>.

§ AUXILIARY PRODUCT FORMULA FOR UNIVARIATE POLYNOMIALS

Let $F, H \in \C[Z] \setminus \{0\}$ and let $\Gamma \subset \R^2$ be a rectangle. The strategy developed in [3]
relate $\ind(FH \, | \, \partial \Gamma)$ with
$\ind(F \, | \, \partial \Gamma) +\ind(H \, | \, \partial \Gamma)$
is to consider the polynomials $P, Q, R, S$ obtained when restricting
$F_{\re},$ $F_{\im},$ $H_{\re},$ $H_{\im}$ to each of the four sides of $\Gamma$, and then
$\Ind_a^b(PR - QS, PS + QR)$ with $\Ind_a^b(P, Q)$ $+$ $\Ind_a^b(R, S)$,
where $a < b$ are the endpoints of the interval parametrizing the side of $\Gamma$ under

For any $P, Q, R, S \in \R[X]$ and $a, b \in \R$ with $a < b$,
we consider the following
auxiliary product formula  coming from <cit.>:

\begin{equation}\label{eqn_auxiliar}
\Ind_a^b(PR - QS, PS + QR)
=  \Ind_a^b(P, Q) + \Ind_a^b(R, S)-\Var_a^b(PS + QR, QS).
\end{equation}

The auxiliary product formula (<ref>) does not hold with full generality, as can be seen in the following example appearing already in [5].

Let $a = 0$, $b = 1$, $P = 1$, $Q = X$, $R = X-1$, $S = X$. Then
$PR - QS  =  -X^2 + X - 1,$ $PS + QR =  X^2$ and

\Ind_0^1(PR - QS, PS + QR)  =   -\frac12, \quad
\Ind_0^1(P, Q)  =   \frac12, \quad
\Ind_0^1(R, S)  =   -\frac12, \quad
\Var_0^1(PS + QR, QS)  = 0,

so the auxiliary product formula (<ref>) does not hold.
Note that for $F=iZ+1$ and $H=(1+i)Z-1$,
$P,Q,R,S$ are the restrictions of
$F_{\re},$ $F_{\im},$ $H_{\re},$ $H_{\im}$ to
the bottom side of $\Gamma = [0,1] \times [0, 1]$.

We introduce the following definition.

Let $P, Q, R, S  \in \R[X]$ and
$c \in \R$. We say that $c \in \R$ is a bad number for $P, Q, R, S$,  if $Q, S \ne 0$ and
$c$ satisfies the following two

* $\val_c(P/Q) = \val_c(R/S) < 0$,

* $\val_c((PS+ QR)/QS) = 0$.

If $P, Q, R, S$ are clear from the context, we simply say that $c$ is
a bad number.

To illustrate this definition, $0$ is a bad number and 1 is not a bad number in Example <ref>.
In general, if $c$ is a bad number, then $Q, S \ne 0$
by definition but also necessarily $P, R, PS + QR \ne 0$.
Note also that since bad numbers are necessarily  roots of $Q$ and $S$,  there is at most a finite number of bad numbers in $\R$.

We now state two results.
The first one proves that the only cases where it is necessary to modify the
auxiliary product formula is at bad numbers.

Let $P, Q, R, S \in \R[X]$ with
$P$ and $Q$ not
simultaneously $0$ and
$R$ and $S$ not
simultaneously $0$, and $a, b \in \R$ with $a < b$.
If $a$ and $b$ are not bad numbers,
auxiliary product formula (<ref>)

\begin{equation*}
\Ind_a^b(PR - QS, PS + QR)
=  \Ind_a^b(P, Q) + \Ind_a^b(R, S)-\Var_a^b(PS + QR, QS)
\quad \quad \quad \quad
\end{equation*}

The second result studies the situation when $a$ or $b$ are bad numbers.

Let $P, Q, R, S \in \R[X]$ with
$P$ and $Q$ not
simultaneously $0$ and
$R$ and $S$ not
simultaneously $0$, and $a, b \in \R$ with $a < b$.

i) If $a$ is
a bad number and $b$ is not a bad number,

\begin{equation*}\label{eqn_auxiliar_2}
\Ind_a^b(PR - QS, PS + QR) \
=  \ \Ind_a^b(P, Q) + \Ind_a^b(R, S)  - \frac12 \Sign(PS + QR, QS, b).
\end{equation*}

ii) If $b$ is a bad number and $a$ is not a bad number,

\begin{equation*}\label{eqn_auxiliar_3}
\Ind_a^b(PR - QS, PS + QR) \
= \  \Ind_a^b(P, Q) + \Ind_a^b(R, S)  + \frac12 \Sign(PS + QR, QS, a).
\end{equation*}

iii)  If $a$ and $b$ are both bad numbers,

\begin{equation*}\label{eqn_auxiliar_4}
\Ind_a^b(PR - QS, PS + QR) \
=  \Ind_a^b(P, Q) + \Ind_a^b(R, S).
\end{equation*}

It can be checked that in Example <ref>, the equation  of item i)
holds instead of equation (<ref>).

The proof of Proposition <ref> uses the following two auxiliary lemmas.
The proof of these lemmas appears already in [3] as part of
the proof of <cit.> (also as part of the proof of <cit.>), but we include these proofs here for completeness.

Let $P, Q, R, S \in \R[X]$
and $a, b \in \R$ with $a < b$.
If $P = 0$ or $Q = 0$ but $P$ and $Q$ are not
simultaneously $0$,
the auxiliary product formula (<ref>) holds.
Similarly, if $R = 0$ or $S=0$ but
$R$ and $S$ are not simultaneously $0$ the auxiliary product formula (<ref>) holds.

If $P = 0$ and $Q \ne 0$, using the inversion formula (Theorem (<ref>)) with $R$ and $S$ we have

\begin{array}{ccl}
\Ind_a^b(PR - QS, PS + QR) & = & \Ind_a^b(- S,  R) \quad \\[2mm]
& = & \Ind_a^b(R,  S) - \Var_a^b(R, S) \\[2mm]
& = & \Ind_a^b(P, Q) + \Ind_a^b(R, S) -\Var_a^b(PS+QR,QS).
\end{array}

On the other hand, if $P \ne 0$ and $Q = 0$,

\Ind_a^b(PR - QS, PS + QR) = \Ind_a^b(R,  S) =
\Ind_a^b(P, Q) + \Ind_a^b(R, S)  -\Var_a^b(PS+QR,QS).

Let $P, Q, R, S \in \R[X]$
and $a, b \in \R$ with $a < b$.
If $Q, S \ne 0$ and $PS + QR = 0$, the auxiliary product formula (<ref>) holds.
Since $Q \ne 0$, $S \ne 0$ and $PS + QR = 0$, we have
$P/Q = -R/S \in \R(X)$
and then

\Ind_a^b(PR - QS, PS + QR) = 0 =
\Ind_a^b(P, Q) + \Ind_a^b(R, S)  -\Var_a^b(PS+QR,QS).

We are ready for the proof of Proposition <ref>.
Again, part of this proof appears already in the proof of <cit.> (also in the proof of <cit.>). The new part is essentially Case 3.

Proof of Proposition <ref> : If at least
one of the polynomials $P, Q, R, S$ or $PQ + RS$ is $0$,
identity (<ref>) holds
by Lemmas <ref> and <ref>.
So in the rest of the proof we assume that none of these polynomials is $0$.
We divide
$P$ and $Q$ by $\gcd(P, Q)$ and $R$ and $S$ by
$\gcd(R, S)$, so without loss of generality
we also assume that $P$ and $Q$ are coprime and $R$ and $S$ are coprime.

We divide the interval $[a, b]$ in finitely many subintervals $[a', b']$ and it is enough to prove that identity (<ref>) holds in each of these subintervals.
We consider all the roots
of $P, Q, R, S$ or $PS + QR$ in $[a, b]$ (possibly none), this includes all bad numbers in $[a, b]$ (again, possibly none).
We divide $[a, b]$ in as many subintervals as needed in such a way that each
subinterval contains at most one of these roots and additionally:

* if the root is not a bad number, then it is an endpoint of the subinterval,

* if the root is a bad number, then it is an interior point of the subinterval.

This is possible because $a$ and $b$ are not bad numbers.
We consider then several cases as follows.

Case 1: There is no root of $Q, S$ or $PS + QR$ in $[a', b']$,

\Ind_{a'}^{b'}\left(PR-QS, PS+QR\right) =
\Ind_{a'}^{b'}\left(P,Q\right) =
\Ind_{a'}^{b'}\left(R,S\right) = 0

\Sign(PS+QR, QS, a')
\Sign(PS+QR, QS, b')

so identity (<ref>) holds in $[a', b']$.

Case 2: There is one root of $Q$, $S$ or $PS + QR$ in $[a', b']$ which is not a
bad number, and therefore is an endpoint of $[a', b']$. In this case, by composing with the linear change
$X \mapsto a ' + b' - X$ (which interchanges $a'$ and $b'$) we can always suppose that the root is $a'$. We split this case in many cases:

Case 2a: If $Q(a') \ne 0, S(a') \ne 0$ and $(PS + QR)(a') = 0$, then

\Ind_{a'}^{b'}\left(P,Q\right) =
\Ind_{a'}^{b'}\left(R,S\right) =
\Sign(PS+QR, QS, a') =

On the other hand

\frac{P(a')}{Q(a')} =  - \frac{R(a')}{S(a')},

(PR - QS)(a') =
Q(a')S(a')\underbrace{\left(\frac{P(a')}{Q(a')}\frac{R(a')}{S(a')} - 1  \right)}_{<0} \ne 0.

Write $PS + QR = (X- a')^{\mu}T$ with $\mu = \mult_{a'}(PS + QR) > 0$.
Note that $\sign(T(a')) = \sign(T(b')) = \sign((PS+QR)(b'))$.

\Ind_{a'}^{b'}\left(PR-QS, PS+QR\right) = -\frac12 \sign \big(Q(a')S(a')T(a')\big) = -\frac12
\Sign(PS+QR, QS, b')

so identity (<ref>) holds in $[a', b']$.

Case 2b: If $Q(a') = 0$ and $S(a') \ne 0$, since
$P$ and $Q$ have no common roots, then $(PS + QR)(a') \ne 0$
and we have that

\Ind_{a'}^{b'}\left(PR-QS, PS+QR\right) =
\Ind_{a'}^{b'}\left(R,S\right) =
\Sign(PS+QR, QS, a')  =

Write $Q = (X- a')^{\mu}Q_{a'}$ with $\mu = \mult_{a'}(Q) >0$.
Note that $\sign(Q_{a'}(a')) = \sign(Q(b'))$.

\Ind_{a'}^{b'}\left(P,Q\right)
= \frac12 \sign\big(P(a') Q_{a'}(a')\big)
= \frac12 \sign \Big(\big((PS+QR) Q_{a'}S\big)(a')  \Big)
= \frac12 \Sign(PS+QR, QS, b')

so identity (<ref>) holds in $[a', b']$.

Case 2c: If $Q(a') \ne 0$ and $S(a') = 0$ we proceed in a similar way to the previous case.

Case 2d: If $Q(a') = 0$ and $S(a') = 0$, then $(PS + QR)(a') = 0$, and since
$P$ and $Q$ have no common roots and
$R$ and $S$ have no common roots,
$P(a') \ne 0$, $R(a') \ne 0$.

Write $PS + QR = (X- a')^{\mu_0}T$ with $\mu_0 = \mult_{a'}(PS + QR) > 0$,
$Q = (X- a')^{\mu_1}Q_{a'}$ with $\mu_1
= \mult_{a'}(Q) > 0$ and
$S = (X- a')^{\mu_2}S_{a'}$ with $\mu_2 = \mult_{a'}(S) > 0$.
Note that $\val_{a'}(P/Q) = -\mu_1$,
$\val_{a'}(R/S) = -\mu_2$ and
$\val_{a'}((PS +QR)/QS) = \mu_0 - \mu_1 - \mu_2$.
We denote

\begin{array}{rcl}
\sigma_1 & := & \sign( P(a') ) \in \{-1, 1\}, \\[2mm]
\sigma_2 & := & \sign( R(a') ) \in \{-1, 1\}, \\[2mm]
\sigma_3 & := & \sign(T(a') ) \in \{-1, 1\}, \\[2mm]
\sigma_4 & := & \sign( Q_{a'}(a') )\in \{-1, 1\}, \\[2mm]
\sigma_5 & := & \sign( S_{a'}(a') )\in \{-1, 1\}. \\[2mm]
\end{array}

Since $a'$ is not a bad number, either $\mu_1 \ne \mu_2$ or $\mu_1 = \mu_2$ but $\mu_0
\ne  \mu_1 + \mu_2$. Note that if $\mu_1 \ne \mu_2$, then again $\mu_0 = \min\{ \mu_1, \mu_2\} \ne \mu_1 + \mu_2$.
So, in any case
we have

\begin{array}{rcl}
\Sign(PS+QR, QS, a') & = & 0. \\[2mm]
\end{array}

On the other hand, we have

\begin{array}{rcl}
\Ind_{a'}^{b'}(PR - QS, PS + QR) & = & \frac12 \sigma_1\sigma_2\sigma_3,\\[2mm]
\Ind_{a'}^{b'}(P, Q) & = & \frac12 \sigma_1\sigma_4, \\[2mm]
\Ind_{a'}^{b'}(R, S) & = & \frac12 \sigma_2\sigma_5, \\[2mm]
\frac12\Sign(PS+QR, QS, b') & = & \frac12\sigma_3\sigma_4\sigma_5. \\[2mm]
\end{array}

We need to prove that

\sigma_1\sigma_2\sigma_3 = \sigma_1\sigma_4 + \sigma_2\sigma_5 - \sigma_3\sigma_4\sigma_5

or, equivalently,

\begin{equation}\label{eq:aux_prod_formula}
\big(\sigma_1\sigma_2 + \sigma_4\sigma_5\big)\sigma_3 = \sigma_1\sigma_4 + \sigma_2\sigma_5.
\end{equation}

We take into account that
$\sigma_1 = \sign(P(b'))$,
$\sigma_2 = \sign(R(b'))$,
$\sigma_3 = \sign((PS+QR)(b'))$,
$\sigma_4 = \sign(Q(b'))$ and
$\sigma_5 = \sign(S(b'))$ and one final time we split in cases as follows.

* If $\sigma_1 = \sigma_5$ and $\sigma_2 = \sigma_4$, then $\sigma_3 = 1$ and
equation (<ref>)

* If $\sigma_1 = -\sigma_5$ and $\sigma_2 = -\sigma_4$ then $\sigma_3 = -1$ and
equation (<ref>)

* In every other case, exactly three elements in the set $\{\sigma_1, \sigma_2, \sigma_4, \sigma_5\}$ are
equal and the remaining one is different. Then

\sigma_1\sigma_2 + \sigma_4\sigma_5 = \sigma_1\sigma_4 + \sigma_2\sigma_5 = 0

equation (<ref>)

So, identity (<ref>) holds in $[a', b']$.

Case 3: There is one root $c$ of $Q$, $S$ or $PS + QR$ in $[a', b']$ which is a
bad number, and therefore $c \ne a'$ and $c \ne b'$.
Since $c$ is a bad number, $c$ is indeed a root of $Q$, $S$ and $PS + QR$.
Also, since
$P$ and $Q$ have no common root and
$R$ and $S$ have no common root,
$P(c) \ne 0$, $R(c) \ne 0$.

Write $PS + QR = (X- c)^{2\mu}T$,
$Q = (X- c)^{\mu} Q_c$,
$S = (X- c)^{\mu} S_c$
with $\mu = \mult_c(Q) = \mult_c(S) = -\val_c(P/Q) = -\val_c(R/S) > 0$.
We denote

\begin{array}{rcl}
\sigma_1 & := & \sign( P(c) ) \in \{-1, 1\}, \\[2mm]
\sigma_2 & := & \sign( R(c) ) \in \{-1, 1\}, \\[2mm]
\sigma_3 & := & \sign(T(c) ) \in \{-1, 1\}, \\[2mm]
\sigma_4 & := & \sign(Q_c(c) )\in \{-1, 1\}, \\[2mm]
\sigma_5 & := & \sign(S_c(c) )\in \{-1, 1\}. \\[2mm]
\end{array}

Since $\val_c( (PR-QS)/(PS + QR) ) = -2\mu$ is even, we

\Ind_{a'}^{b'}(PR - QS, PS + QR) =  0.

On the other hand, we have

\begin{array}{rcl}
\Ind_{a'}^{b'}(P, Q) & = &  \frac12(1 - (-1)^{\mu})\sigma_1\sigma_4, \\[2mm]
\Ind_{a'}^{b'}(R, S) & = &  \frac12(1 - (-1)^{\mu})\sigma_2\sigma_5, \\[2mm]
\frac12\Sign(PS+QR, QS, a') & = & \frac12\sigma_3\sigma_4\sigma_5, \\[2mm]
\frac12\Sign(PS+QR, QS, b') & = & \frac12\sigma_3\sigma_4\sigma_5. \\[2mm]
\end{array}

We need to prove that  $\sigma_1\sigma_4 + \sigma_2\sigma_5 = 0$.
Since $\mu >0$ and

(X- c)^{2\mu}T = PS + QR = (X- c)^{\mu}(P S_c +  Q_c R),

we conclude that

P(c) S_c(c) + Q_c(c) R(c) = 0

and therefore

\sigma_1\sigma_5 =
\sign(P(c)S_c(c)) = - \sign( Q_c(c) R(c)) =
- \sigma_2\sigma_4,

but then

\sigma_1\sigma_4 = \sigma_1\sigma_5^2\sigma_4 = -\sigma_2\sigma_4^2\sigma_5 = -\sigma_2\sigma_5,

and identity (<ref>) holds in $[a', b']$.

We conclude this section with the proof of Proposition <ref>.

Proof of Proposition <ref>:
We start with item i). Since there are bad numbers, we have $P, Q, R, S, PS + QR \ne 0$. As in the proof of
we divide
$P$ and $Q$ by $\gcd(P, Q)$ and $R$ and $S$ by
$\gcd(R, S)$,
without loss of generality, we assume that $P$ and $Q$ are coprime and $R$ and $S$ are coprime.

Now, we consider $a' \in (a, b)$ such that there is no root of $P, Q, R, S$ or
$PS + QR$ in $(a, a']$. Then $a'$ is not a bad number and therefore by Lemma <ref>, identity
(<ref>) holds in $[a', b]$. It is enough then to prove that

\Ind_a^{a'}(PR - QS, PS + QR) \
=  \ \Ind_a^{a'}(P, Q) + \Ind_a^{a'}(R, S)  - \frac12 \Sign(PS + QR, QS, a').

Since $Q(a) = 0$ and $S(a) = 0$, then $(PS + QR)(a) = 0$, and since
$P$ and $Q$ have no common roots and
$R$ and $S$ have no common roots,
$P(a) \ne 0$, $R(a) \ne 0$.

Write $PS + QR = (X- a)^{2\mu}T$,
$Q = (X- a)^{\mu} Q_a$
$S = (X- a)^{\mu} S_a$
with $\mu = \mult_a(Q) = \mult_a(S) = -\val_a(P/Q) = -\val_a(R/S) > 0$.
We denote

\begin{array}{rcl}
\sigma_1 & := & \sign( P(a) ) \in \{-1, 1\}, \\[2mm]
\sigma_2 & := & \sign( R(a) ) \in \{-1, 1\}, \\[2mm]
\sigma_3 & := & \sign(T(a) ) \in \{-1, 1\}, \\[2mm]
\sigma_4 & := & \sign(  Q_a(a) )\in \{-1, 1\}, \\[2mm]
\sigma_5 & := & \sign(  S_a(a) )\in \{-1, 1\}. \\[2mm]
\end{array}

We have

\begin{array}{rcl}
\Ind_{a}^{a'}(PR - QS, PS + QR) & = & \frac12 \sigma_1\sigma_2\sigma_3,\\[2mm]
\Ind_{a}^{a'}(P, Q) & = & \frac12 \sigma_1\sigma_4, \\[2mm]
\Ind_{a}^{a'}(R, S) & = & \frac12 \sigma_2\sigma_5, \\[2mm]
\frac12\Sign(PS+QR, QS, a') & = & \frac12\sigma_3\sigma_4\sigma_5. \\[2mm]
\end{array}

So  we need to prove that

\sigma_1\sigma_2\sigma_3 = \sigma_1\sigma_4 + \sigma_2\sigma_5 - \sigma_3\sigma_4\sigma_5.

The rest of the proof is exactly as in Case 2d of the proof of Proposition <ref>.

The proof of item ii) is similar to the proof of item i). The proof of item iii) follows easily by introducing an intermediate point between $a$ and $b$ which is not a
bad number and applying items i) and ii) to the new two subintervals.

§ PRODUCT FORMULAS FOR COMPLEX RATIONAL FUNCTIONS

The strategy to study the additivity of $\ind$ and $\mind$ with
respect to product in $\C(Z) \setminus \{0\}$ is based on
the auxiliary product formula (<ref>) proved in
<ref> and following the method in

We consider $F/G, H/I\in \C(Z) \setminus \{0\}$ and a
rectangle $\Gamma = [x_0, x_1] \times [y_0, y_1]$.
Without loss of generality, througout this section we assume that $F$ and $G$
are coprime and $H$ and $I$ are coprime.

We fisrt discuss the relation between $\ind(F / G  \cdot H / I \, | \,  \partial \Gamma)$ with
$\ind(F / G \, | \,  \partial \Gamma) + \ind(H / I \, | \,  \partial \Gamma)$.

We take the parametrizations $(T, y_0)$, $(x_1, T)$, $(T, y_1)$ and $(x_0, T)$ of the lines containing the bottom, right, top and left edges of
$\Gamma$ and consider the following polynomials in $\R[T]$:

\begin{array}{cccc}
P_1(T) =  (F \overline G)_{\rm re}(T, y_0), &
Q_1(T) =  (F \overline G)_{\rm im}(T, y_0), &
R_1(T) =  (H \overline I)_{\rm re}(T, y_0), &
S_1(T) =  (H \overline I)_{\rm im}(T, y_0), \\[2mm]
P_2(T) =  (F \overline G)_{\rm re}(x_1, T), &
Q_2(T) =  (F \overline G)_{\rm im}(x_1, T), &
R_2(T) =  (H \overline I)_{\rm re}(x_1, T), &
S_2(T) =  (H \overline I)_{\rm im}(x_1, T), \\[2mm]
P_3(T) =  (F \overline G)_{\rm re}(T, y_1), &
Q_3(T) =  (F \overline G)_{\rm im}(T, y_1), &
R_3(T) =  (H \overline I)_{\rm re}(T, y_1), &
S_3(T) =  (H \overline I)_{\rm im}(T, y_1), \\[2mm]
P_4(T) =  (F \overline G)_{\rm re}(x_0, T), &
Q_4(T) =  (F \overline G)_{\rm im}(x_0, T), &
R_4(T) =  (H \overline I)_{\rm re}(x_0, T), &
S_4(T) =  (H \overline I)_{\rm im}(x_0, T).
\end{array}

Proposition <ref> (four times),
if $x_0,x_1$
are not bad numbers for $P_1, Q_1, R_1, S_1$ or $P_3, Q_3, R_3, S_3$ and
$y_0,y_1$ are not bad numbers
for $P_2, Q_2, R_2, S_2$ or $P_4, Q_4, R_4, S_4$,

\begin{array}{ccc}
& 2\, \ind(F \overline G H \overline I\, | \, \partial \Gamma) -
2\, \ind(F \overline G \, | \, \partial \Gamma) \ - \ 2\, \ind(H \overline I \, | \, \partial \Gamma) &
\\[2mm]
= &
- \  \Var_{x_0}^{x_1}(P_1S_1 + Q_1R_1, Q_1S_1)
\ - \ \Var_{y_0}^{y_1}(P_2S_2 + Q_2R_2, Q_2S_2) \\[2mm]
& - \  \Var_{x_1}^{x_0}(P_3S_3 + Q_3R_3, Q_3S_3)
\ - \ \Var_{y_1}^{y_0}(P_4S_4 + Q_4R_4, Q_4S_4).
\end{array}

$\ind( F  / G \cdot H  / I \, | \,  \partial \Gamma)$ coincides with
$\ind(F  / G  \, | \,  \partial \Gamma) + \ind(H  / I  \, | \,  \partial \Gamma)$
if and only if the four $\Var$ add up to $0$.

[-] (-2.4, 3) – (-2.4,0) – (6.4,0) – (6.4,3) – (-2.4,3) ;
at (-1.6,0.4) $(x_0, y_0)$;
at (5.6,0.4) $(x_1, y_0)$;
at (-1.6,2.55) $(x_0, y_1)$;
at (5.6,2.55) $(x_1, y_1)$;
at (2,1.6) $\Gamma$;
at (-0.8,-0.6) $+ \frac12 {\Sign}(\dots, \dots, x_0)$;
at (-0.8, 3.5) $- \frac12 {\Sign}(\dots, \dots, x_0)$;
at (4.8,-0.6) $- \frac12 {\Sign}(\dots, \dots, x_1)$;
at (4.8,3.5) $+ \frac12 {\Sign}(\dots, \dots, x_1)$;
at (-4.15 ,0.4) $- \frac12 {\Sign}(\dots, \dots, y_0)$;
at (-4.15 ,2.55) $+ \frac12 {\Sign}(\dots, \dots, y_1)$;
at (8.2 ,0.4) $+ \frac12 {\Sign}(\dots, \dots, y_0)$;
at (8.2 ,2.55) $- \frac12 {\Sign}(\dots, \dots, y_1)$;

For instance, zooming around vertex $(x_0, y_0)$ we have:

[-] (-2, 1.5) – (-2,0) – (4,0);
[dashed] (4,0) – (6,0);
[dashed] (-2,1.5) – (-2,2.2);
at (-1.2,0.4) $(x_0, y_0)$;
at (2.4,1.8) $\Gamma$;
at (0.6,-0.6) $+ \frac12 {\Sign}(P_1S_1 + Q_1R_1, Q_1S_1, x_0)$;
at (-4.9,0.4) $- \frac12 {\Sign}(P_4S_4 + Q_4R_4, Q_4S_4, y_0)$;

It would be then enough to prove that at each vertex, the
adding $\Sign$ cancels with the substracting $\Sign$.
Unfortunately, this is not the case in general, as shown by the following example.

(Continuation of Example <ref>)
Let $F = Z, G=1$, $H = \alpha +i \beta$ with $0 < \beta < \alpha$, $I=1$ and $\Gamma = [0, 1] \times [0, 1]$.

\begin{array}{llll}
P_1(T) =  T, &
Q_1(T) =  0, &
R_1(T) =  \alpha, &
S_1(T) =  \beta, \\[2mm]
P_4(T) =  0, &
Q_4(T) =  T, &
R_4(T) =  \alpha, &
S_4(T) =  \beta.
\end{array}

Notice that there are no bad numbers for
$P_1, Q_1, R_1, S_1$ or $P_4, Q_4, R_4, S_4$.
We have

{\Sign}(P_1S_1 + Q_1R_1, Q_1S_1, x_0) =
\Sign(\beta T, 0, 0) = 0

{\Sign}(P_4S_4 + Q_4R_4, Q_4S_4, y_0) =
\Sign(\alpha T, \beta T, 0) = 1.

we have already observed in Example <ref> that $\ind$ is not additive in this case.

Nevertheless, next proposition shows that $\ind$ is indeed additive with
respect to product in $\C(Z) \setminus \{0\}$ under mild hypothesis.

Let $F/G, H/I \in \C(Z) \setminus \{0\}$ and
$\Gamma \subset \R^2$ a rectangle
such that $F/G$ and $H/I$
have even valuation at the vertices of $\Gamma$.
$$\ind(F /G \cdot  H / I \, | \, \partial \Gamma) =
\ind(F / G\, | \, \partial \Gamma) +
\ind(H  /  I \, | \, \partial \Gamma).$$

Moreover, next proposition shows that  $\mind$ is
additive with
respect to product in $\C(Z)\setminus \{0\}$ with full generality.

Let $F/G, H/I \in \C(Z) \setminus \{0\}$ and
$\Gamma \subset \R^2$ a rectangle.
$$\mind( F /G \cdot  H / I \, | \, \partial \Gamma) =
\mind( F /G \, | \, \partial \Gamma)
\mind(H / I \, | \, \partial \Gamma).$$

Before the proofs of these propositions, we do some preliminary
computations and we introduce some notation will use repeteadly in the rest of the section.

We consider a new variable $\overline Z$,
together with the inclusion
$\C[Z, \overline Z] \subset \C[X, Y]$
through the identities $Z = X + iY, \overline Z = X - iY$.
For $G(Z)  =  \sum _j \gamma_j Z^j \in \C[Z]$, let
$\overline G (\overline Z) =   \sum _j \overline {\gamma_j} \overline {Z}^j \in
\C[\overline Z]$.
In this way, note that

\overline{G}(\overline Z) = \overline{G}(X, Y) \in \C[X, Y].

Let $\Gamma = [x_0, x_1] \times [y_0, y_1]$. We define $z_0 = x_0 + iy_0 \in \C$ and

\begin{array}{ll}
e=\val_{z_0}(F/G), \quad  &
p+iq= F_{z_0}(z_0) \overline {G_{z_0}(z_0)} \ne 0,  \\[2mm]
f=\val_{z_0}(H/I),  &
r+is= H_{z_0}(z_0) \overline {I_{z_0}(z_0)} \ne 0.
\end{array}

If $e \ge 0$, since $F$ and $G$ are coprime,
$F(Z)\overline G(\overline Z) = (Z-z_0)^e F_{z_0}(Z)\overline G_{z_0}(\overline Z)$

\begin{equation} \label{eq:Fz0barGz0}
F_{z_0}(Z)\overline G_{z_0}(\overline Z)
= p+iq +
(Z-z_0)A(Z, \overline Z) + (\overline Z - \overline {z_0})B(Z, \overline Z) \in \C[Z, \overline Z] \subset \C[X, Y]
\end{equation}

for some $A, B \in \C[Z, \overline Z]$.

\begin{equation}\label{eq:P1Q1epos}
\begin{array}{ccc}
P_1(T) & = & (T-x_0)^e\left(p + (T-x_0)A_1(T)\right), \\[2mm]
Q_1(T) & = & (T-x_0)^e\left(q + (T-x_0)B_1(T)\right), \\[2mm]
\end{array}
\end{equation}

for some $A_1, B_1 \in \R[T]$.
If $e$ is even,

\begin{equation} \label{eq:P4Q4eposeven}
\begin{array}{ccc}
P_4(T) & = & (-1)^{\frac{e}2}(T-y_0)^e\left(p + (T-y_0)A_{4,{\rm e}}(T)\right), \\[2mm]
Q_4(T) & = & (-1)^{\frac{e}2}(T-y_0)^e\left( q + (T-y_0)B_{4,{\rm e}}(T)\right), \\[2mm]
\end{array}
\end{equation}

for some $A_{4,{\rm e}}, B_{4,{\rm e}} \in \R[T]$.
If $e$ is odd,

\begin{equation} \label{eq:P4Q4eposodd}
\begin{array}{ccc}
P_4(T) & = & (-1)^{\frac{e-1}2}(T-y_0)^e\left(-q + (T-y_0)A_{4,{\rm o}}(T)\right), \\[2mm]
Q_4(T) & = & (-1)^{\frac{e-1}2}(T-y_0)^e\left(p + (T-y_0)B_{4,{\rm o}}(T) \right), \\[2mm]
\end{array}
\end{equation}

for some $A_{4,{\rm o}}, B_{4,{\rm o}} \in \R[T]$.

Similarly, if $e<0$, since $F$ and $G$ are coprime,
$F(Z)\overline G(\overline Z) =
(\overline Z - \overline{z_0})^{-e} F_{z_0}(Z)\overline G_{z_0}(\overline Z)$
with $F_{z_0}(Z)\overline G_{z_0}(\overline Z)$ as in (<ref>).
Therefore, we obtain formulas for $P_1, Q_1, P_4, Q_4$ as in
(<ref>), (<ref>) and (<ref>)
replacing $e$ by $-e$, and additionally multiplying $P_4$ and $Q_4$ by (-1) in
(<ref>) ($e$ odd).

If $f \ge 0$, since $H$ and $I$ are coprime,
$H(Z)\overline I(\overline Z) = (Z-z_0)^e H_{z_0}(Z)\overline I_{z_0}(\overline Z)$

\begin{equation} \label{eq:Hz0barIz0}
H_{z_0}(Z)\overline I_{z_0}(\overline Z)
= r+is +
(Z-z_0)C(Z, \overline Z) + (\overline Z - \overline {z_0})D(Z, \overline Z) \in \C[Z, \overline Z] \subset \C[X, Y]
\end{equation}

for some $C, D \in \C[Z, \overline Z]$.

\begin{equation}\label{eq:R1S1fpos}
\begin{array}{ccc}
R_1(T) & = & (T-x_0)^f\left(r + (T-x_0)C_1(T)\right), \\[2mm]
S_1(T) & = & (T-x_0)^f\left(s + (T-x_0)D_1(T)\right), \\[2mm]
\end{array}
\end{equation}

for some $C_1, D_1 \in \R[T]$.
If $f$ is even,

\begin{equation} \label{eq:R4S4fposeven}
\begin{array}{ccc}
R_4(T) & = & (-1)^{\frac{f}2}(T-y_0)^f\left(r + (T-y_0)C_{4,{\rm e}}(T)\right), \\[2mm]
S_4(T) & = & (-1)^{\frac{f}2}(T-y_0)^f\left( s + (T-y_0)D_{4,{\rm e}}(T)\right), \\[2mm]
\end{array}
\end{equation}

for some $C_{4,{\rm e}}, D_{4,{\rm e}} \in \R[T]$.
If $f$ is odd,

\begin{equation} \label{eq:R4S4fposodd}
\begin{array}{ccc}
R_4(T) & = & (-1)^{\frac{f-1}2}(T-y_0)^f\left(-s + (T-y_0)C_{4,{\rm o}}(T)\right), \\[2mm]
S_4(T) & = & (-1)^{\frac{f-1}2}(T-y_0)^f\left(r + (T-y_0)D_{4,{\rm o}}(T) \right), \\[2mm]
\end{array}
\end{equation}

for some $C_{4,{\rm o}}, D_{4,{\rm o}} \in \R[T]$.

Finally, if $f<0$, since $H$ and $I$ are coprime,
$H(Z)\overline I(\overline Z) =
(\overline Z - \overline{z_0})^{-f} H_{z_0}(Z)\overline I_{z_0}(\overline Z)$
with $H_{z_0}(Z)\overline I_{z_0}(\overline Z)$ as in (<ref>).
Therefore, we obtain formulas for $R_1, S_1, R_4, S_4$ as in
(<ref>), (<ref>) and (<ref>)
replacing the $f$ by $-f$, and additionally multiplying $R_4$ and $S_4$ by (-1) in
(<ref>) ($f$ odd).

Now, we prove an auxiliary lemma, which is a particular case of Proposition
<ref> where one of the rational functions
is a constant.

Let $F/G \in \C(Z) \setminus \{0\}$, $\gamma \in \C\setminus\{0\}$ and
$\Gamma \subset \R^2$ a rectangle
such that $F/G$
has even valuation at the vertices of $\Gamma$.

$$\ind(F / G\, | \, \partial \Gamma) =\ind(\gamma  F / G \, | \, \partial \Gamma).$$

Note that if the valuation of $F/G$ at the vertices of $\Gamma$ is even,
Lemma <ref> implies that

\mind(F /  G \, | \, \partial \Gamma) =
\ind(F / G \, | \, \partial \Gamma).

Proof of Lemma <ref>:
Let $\Gamma = [x_0, x_1] \times [y_0, y_1]$ and
$\gamma = \alpha + i \beta$.
The statement is clear if $\beta=0$, so we suppose
We take $H = \alpha + i \beta$ and $I = 1$,
and using Notation <ref>
we have

Since $S_1,S_2, S_3,S_4$ are constant, there are no bad numbers for
$P_1, Q_1, R_1, S_1;$
$P_2, Q_2, R_2, S_2;$ $P_3, Q_3, R_3, S_3$ or
$P_4, Q_4, R_4, S_4$.
Using Proposition <ref> (four times)
as explained at the beginning of the section,
and the fact that
$\ind(\alpha+i\beta\, | \, \partial \Gamma) = 0$,
we have

\begin{array}{rcl}
& 2 \, \ind((\alpha +i\beta)F \overline G \, | \, \partial \Gamma)
- 2 \, \ind(F \overline G \, | \, \partial \Gamma)
- 2 \, \ind(\alpha+i\beta\, | \, \partial \Gamma)  \\
= &
- \ \Var_{x_0}^{x_1}(\beta P_1+  \alpha Q_1, \beta Q_1)
\ - \ \Var_{y_0}^{y_1}(\beta P_2 + \alpha Q_2, \beta  Q_2)
\\[3mm]
& - \ \Var_{x_1}^{x_0}(\beta P_3 + \alpha Q_3, \beta Q_3)
\ - \  \Var_{y_1}^{y_0}(\beta P_4 + \alpha Q_4, \beta Q_4).
\end{array}

Therefore, it is enough to prove that the four $\Var$ add up to $0$.
Concentrating at vertex $(x_0, y_0)$, we
will prove that

$${\Sign}(\beta P_1 + \alpha Q_1, \beta Q_1, x_0) = {\Sign}(\beta P_4 + \alpha Q_4, \beta Q_4, y_0).

$p+iq= F_{z_0}(z_0) \overline {G_{z_0}(z_0)} \ne 0$, we have that $\beta p+ \alpha q$, $\beta q$ are not simultaneously 0.
If $e \ge 0$, using
(<ref>) and (<ref>)
we obtain

{\Sign}(\beta P_1 + \alpha Q_1, \beta Q_1, x_0)
={\sign}((\beta p + \alpha q) \beta q)
= {\Sign}(\beta P_4 + \alpha Q_4, \beta Q_4, y_0).

If $e < 0$ the same identity holds with a similar proof.

Finally, the analysis for the three remaining vertices $(x_1, y_0)$, $(x_1, y_1)$
and $(x_0, y_1)$ is identical.

Proof of Proposition <ref>:
Let $\Gamma = [x_0, x_1] \times [y_0, y_1]$ and
take $\gamma = \alpha + i \beta \in \C$. Multiplying $F / G$ by
$\gamma$ and considering for instance the parametrization of the
bottom side of $\Gamma$, we define

\begin{array}{cc}
P_{\gamma, 1}(T) =  (\gamma F \overline G)_{\rm re}(T, y_0), &
Q_{\gamma, 1}(T) =  (\gamma F \overline G)_{\rm im}(T, y_0). \\
\end{array}

Using Notation <ref> we have

\begin{array}{ccc}
P_{\gamma, 1}(T) & = & \alpha P_1(T) - \beta Q_1(T), \\[2mm]
Q_{\gamma, 1}(T) & = & \alpha Q_1(T) + \beta P_1(T).
\end{array}

Let $c \in \R$.
If $\val_c(P_1/Q_1) < 0$, then for $\beta \ne 0$ we have
$\val_c (P_{\gamma, 1}/Q_{\gamma, 1}) \ge 0$.
If $\val_c(P_1/Q_1) \ge 0$, then for generic $\alpha, \beta \in \R$ we still have
$\val_c (P_{\gamma, 1}/Q_{\gamma, 1}) \ge 0$.

This implies that, multiplying $F / G$ and $H / I$ by suitable constants if necessary, we can
assume without loss of generality that $x_0, x_1$ are not bad numbers for $P_1, Q_1, R_1, S_1$ or $P_3, Q_3, S_3, R_3$ and
$y_0, y_1$ are not bad numbers for $P_2, Q_2, R_2, S_2$  or $P_4, Q_4, S_4, R_4$.
In addition we may assume that
$F_{z}(z)\overline {G_{z}(z)}$ and
$H_{z}(z)\overline {I_{z}(z)}$
are not real for each of the four vertices $z$ of $\Gamma$.
By Lemma <ref>, this does not change $w(F / G \, | \,
\partial \Gamma)$,
$w(H / I \, | \, \partial \Gamma)$
$w(F/G \cdot H / I \, | \, \partial \Gamma)$.

Again, using Proposition <ref> (four times) we have

\begin{array}{rcl}
&2 \, \ind(F  \overline G H \overline I \, | \, \partial \Gamma)
- 2 \, \ind(F \overline G \, | \, \partial \Gamma)
- 2 \, \ind(H \overline  I  \, \partial \Gamma)
\\[3mm]
= &
- \ \Var_{x_0}^{x_1}( P_1 S_1+  Q_1 R_1, Q_1 S_1)
\ - \ \Var_{y_0}^{y_1}(P_2 S_2 + Q_2 R_2, Q_2 S_2)
\\[3mm]
& - \ \Var_{x_1}^{x_0}( P_3 S_3+  Q_3 R_3, Q_3 S_3)
\ - \  \Var_{y_1}^{y_0}(P_4 S_4+  Q_4 R_4, Q_4 S_4).
\end{array}

Therefore, it is enough to prove that the four $\Var$ add up to $0$.
Concentrating at vertex $(x_0, y_0)$,
we will prove that

{\Sign}(P_1 S_1 + Q_1 R_1, Q_1 S_1, x_0) =
{\Sign}(P_4 S_4 + Q_4 R_4,  Q_4 S_4, y_0).

Since  $p+iq=F_{z_0}(z_0)\overline {G_{z_0}(z_0)} \ne0$  and  $r+is=H_{z_0}(z_0)\overline {I_{z_0}( z_0)} \ne 0$
are such that $q \ne 0$ and $s\ne 0$, we have that $qs \ne 0$.
If $e \ge 0$ and $f\ge 0$,
using (<ref>), (<ref>), (<ref>) and
(<ref>) we obtain

$${\Sign}( P_1 S_1+ Q_1 R_1, Q_1S_1, x_0)={\sign}((p s+ q r) q  s)
= {\Sign}(P_4 S_4+ Q_4 R_4, Q_4 S_4, y_0).$$

If $e<0 $ or $f<0$  the same identity holds
with a similar proof.

Finally, the analysis for the three remaining vertices $(x_1, y_0)$, $(x_1, y_1)$
and $(x_0, y_1)$ is identical.

We focus now on Proposition
As before, we prove first an auxiliary lemma, which is a particular case of it where one of the rational functions
is a constant.

Let $F/G \in \C(Z) \setminus \{0\}$, $\gamma \in \C\setminus \{0\}$ and $\Gamma \subset \R^2$ a rectangle.

$$\mind(F / G \, | \, \partial \Gamma) =\mind( \gamma  F / G \, | \, \partial \Gamma).$$

Proof: Let $\Gamma = [x_0, x_1] \times [y_0,y_1]$ and
$\gamma = \alpha + i \beta$.
The statement is clear if $\beta=0$, so we suppose
$\beta\not=0$. We take $H = \alpha + i \beta$ and $I = 1$, and using
Notation <ref> we have

Since $S_1,S_2,S_3,S_4$ are constant, there are no bad numbers for
$P_1, Q_1, R_1, S_1; P_2, Q_2, R_2, S_2$; $P_3, Q_3, R_3, S_3$;
$P_4, Q_4, R_4, S_4$;
$-Q_1, P_1, R_1, S_1; -Q_2, P_2, R_2, S_2; -Q_3, P_3, R_3, S_3$ or
$-Q_4, P_4, R_4, S_4$.
Using Proposition <ref> (eight times)
and the fact that
$\mind(\alpha+i\beta\, | \, \partial \Gamma) =
\ind(\alpha+i\beta\, | \, \partial \Gamma) = 0$,
we have

\begin{array}{rcl}
& 4 \, \mind((\alpha +i\beta)F \overline G \, | \, \partial \Gamma)
- 4 \, \mind(F\overline G \, | \, \partial \Gamma)
- 4 \, \mind(\alpha+i\beta\, | \, \partial \Gamma)
\\[3mm]
& 2 \, \ind((\alpha +i\beta)F\overline G  \, | \, \partial \Gamma)
- 2 \, \ind(F\overline G \, | \, \partial \Gamma)
- 2 \, \ind(\alpha+i\beta\, | \, \partial \Gamma)  \\[3mm]
& + \ 2 \, \ind((\alpha +i\beta)iF\overline G  \, | \, \partial \Gamma)
- 2 \, \ind(iF\overline G \, | \, \partial \Gamma)
- 2 \, \ind(\alpha+i\beta\, | \, \partial \Gamma)  &  \\[3mm]
= &
- \ \Var_{x_0}^{x_1}(\beta P_1+  \alpha Q_1, \beta Q_1)
\ - \ \Var_{y_0}^{y_1}(\beta P_2 + \alpha Q_2, \beta Q_2)
\\[3mm]
& - \ \Var_{x_1}^{x_0}(\beta P_3 + \alpha Q_3, \beta Q_3)
\ - \  \Var_{y_1}^{y_0}(\beta P_4 + \alpha Q_4, \beta Q_4)
\\[3mm]
- \  \Var_{x_0}^{x_1}(-\beta Q_1 + \alpha P_1, \beta P_1)
\ - \ \Var_{y_0}^{y_1}(-\beta Q_2 + \alpha P_2,\beta P_2)
\\[3mm]
- \ \Var_{x_1}^{x_0}(-\beta Q_3 + \alpha P_3, \beta P_3)
\ - \  \Var_{y_1}^{y_0}(-\beta Q_4 + \alpha P_4, \beta P_4).
\end{array}

Therefore, it is enough to prove that the eight $\Var$ add up to $0$.
Zooming around vertex $(x_0, y_0)$ we have

[-] (-2, 1.5) – (-2,0) – (4,0);
[dashed] (4,0) – (6,0);
[dashed] (-2,1.5) – (-2,2.2);
at (-1.2,0.4) $(x_0, y_0)$;
at (2.4,1.8) $\Gamma$;
at (0.6,-0.6) $+ \frac12 {\Sign}(\beta P_1 + \alpha Q_1, \beta Q_1, x_0)$;
at (0.7,-1.4) $+ \frac12 {\Sign}(-\beta Q_1+ \alpha P_1, \beta P_1, x_0)$;
at (-4.9,0.4) $- \frac12{\Sign}(\beta P_4 + \alpha Q_4, \beta Q_4, y_0)$;
at (-5,1.2) $- \frac12{\Sign}(-\beta Q_4 + \alpha P_4, \beta P_4, y_0)$;

We will prove that

\begin{equation} \label{eq:four_signs_at_vertex}
\begin{array}{ccc}
& {\Sign}(\beta P_1 + \alpha Q_1, \beta Q_1, x_0) +
{\Sign}(-\beta Q_1 + \alpha P_1,  \beta P_1 , x_0) & = \\[3mm]
= &
{\Sign}(\beta P_4 + \alpha Q_4,  \beta Q_4 , y_0) +
{\Sign}(- \beta Q_4 + \alpha P_4, \beta P_4 , y_0).
\end{array}
\end{equation}

Since $p+iq = F_{z_0}(z_0)\overline {G_{z_0}(z_0)} \ne 0$ we have that
$\beta p + \alpha q$ and $\beta q$ are not simultaneously 0
and $-\beta q + \alpha p$, $\beta p$ are not simultaneously 0.
Suppose $e \ge 0$.

If $e$ is even,
using (<ref>)
and  (<ref>)
we have

$${\Sign}(\beta P_1 + \alpha Q_1, \beta Q_1, x_0)={\sign}((\beta p + \alpha q) \beta q) = {\Sign}(\beta P_4 + \alpha Q_4, \beta Q_4, y_0),$$

$${\Sign}(-\beta Q_1+ \alpha P_1, \beta P_1, x_0)={\sign}((-\beta q + \alpha p) \beta p) = {\Sign}(-\beta Q_4+ \alpha P_4, \beta P_4, y_0).$$

If $e$  is odd, using (<ref>)
and (<ref>) we have

$${\Sign}(\beta P_1 + \alpha Q_1, \beta Q_1, x_0)={\sign}((\beta p + \alpha q), \beta q) = {\Sign}(-\beta Q_4+ \alpha P_4, \beta P_4, y_0),

$${\Sign}(-\beta Q_1+ \alpha P_1, \beta P_1, x_0)={\sign}((-\beta q + \alpha p) \beta p) =
{\Sign}(\beta P_4 + \alpha Q_4, \beta Q_4, y_0).$$

Then, in both cases we have that identity (<ref>) holds.
If $e < 0$ the same identity holds with a similar proof.

Finally, the analysis for the three remaining vertices $(x_1, y_0)$, $(x_1, y_1)$
and $(x_0, y_1)$ is identical.

Proof of Proposition <ref>: Let $\Gamma = [x_0, x_1] \times
[y_0, y_1]$.
From the definition of $\ind$ and $\mind$, it follows that for any function in  $\C[X, Y]$, if we subdivide $\Gamma$ in four subrectangles $\Gamma_1, \dots, \Gamma_4$ as in the picture below, then the winding number $\ind$ or $\mind$ on $\partial \Gamma$ equals the sum of the
respective winding number on $\partial \Gamma_i$ for $1 \le i \le 4$.

[line width=0.9pt,-] (-3,-0.7) – (-3,1.8);
[line width=0.9pt,-] (-1.5,-0.7) – (-1.5,1.8);
[line width=0.9pt,-] (0.3,-0.7) – (0.3,1.8);

[<-, dashed] (-2.8,-0.4) – (-2.8,0.3);
[<-, dashed] (-2.8,0.9) – (-2.8,1.5);
[->, dashed] (-1.7,-0.4) – (-1.7,0.3);
[->, dashed] (-1.7,0.9) – (-1.7,1.5);
[<-, dashed] (-1.3,-0.4) – (-1.3,0.3);
[<-, dashed] (-1.3,0.9) – (-1.3,1.5);
[->, dashed] (0.1,-0.4) – (0.1,0.3);
[->, dashed] (0.1,0.9) – (0.1,1.5);

[line width=0.9pt,-] (-3, -0.7) – (0.3,-0.7);
[line width=0.9pt,-] (-3, 0.6) – (0.3,0.6);
[line width=0.9pt,-] (-3, 1.8) – (0.3,1.8);

[<-, dashed] (-2.7,1.6) – (-1.8,1.6);
[<-, dashed] (-1.2,1.6) – (0,1.6);
[->, dashed] (-2.7,0.8) – (-1.8,0.8);
[->, dashed] (-1.2,0.8) – (0,0.8);
[<-, dashed] (-2.7,0.4) – (-1.8,0.4);
[<-, dashed] (-1.2,0.4) – (0,0.4);
[->, dashed] (-2.7,-0.5) – (-1.8,-0.5);
[->, dashed] (-1.2,-0.5) – (0,-0.5);
at (-0.55,-0.1) $\Gamma_2$;
at (-2.15,-0.1) $\Gamma_1$;
at (-0.55,1.15) $\Gamma_3$;
at (-2.15,1.15) $\Gamma_4$;
at (1.2,0.5) $\Gamma$;

If $F, G, H$ and $I$ vanish at more than one vertex of $\Gamma$, we choose a point $z=(x,y) \in \Gamma$ such that $(x,y)$, $(x_0,y)$, $(x_1,y)$, $(x,y_0)$ and $(x,y_1)$ are not roots of any of them. Using $z$ to subdivide $\Gamma$ in four rectangles, $F,G,H$ and $I$ vanish at most at one vertex of each of these four rectangles.
So without loss of generality we replace $\Gamma$ by $\Gamma_1$ and we make the assumption that
$F,G,H$ and $I$ do not vanish at $(x_0,y_1),(x_1,y_1), (x_1,y_0)$.

As in the proof of Proposition <ref>,
multiplying $F / G$ and $H / I$ by suitable constants if necessary,
we can suppose without loss of generality that
$x_0,x_1$ and $y_0, y_1$ are not bad numbers for
all the finitely many $4$-uples of polynomials we will use along the proof.
addition we may assume that
$F_{z}(z)\overline {G_{z}(z)}$ and
$H_{z}(z)\overline {I_{z}(z)}$
are not real or purely imaginary for each of the four vertices $z$ of $\Gamma$.
By Lemma <ref>, this does not change
$\mind( F/G \, | \, \partial \Gamma)$,
$\mind( H/I \, | \, \partial \Gamma)$ or
$\mind( F/G \cdot H/I\, | \, \partial \Gamma)$.

The proof is done in several cases according to the parity of the
valuations $e$ and $f$ of $F/G$ and $H /I$ at $z_0=x_0+iy_0$.

If $e$ and $f$ are both even,  the statement follows from  Proposition <ref> since, by Remark <ref>,

\mind(F / G \, | \, \partial \Gamma) =\ind(F / G \, | \, \partial \Gamma), \
\mind(H / I \, | \, \partial \Gamma) =\ind(H / I \, | \, \partial \Gamma), \hbox{ and }
\mind(F / G \cdot H / I\, | \, \partial \Gamma) =
\ind(F / G \cdot H / I\, | \, \partial \Gamma).

If $e$ is odd and $f$ is even,
suppose first $e\ge 0$ and $f\ge 0$.
By Remark <ref>, $\mind(H \overline I\, | \, \partial \Gamma) =\ind(H \overline I\, | \, \partial \Gamma)$.
Then, using Proposition <ref> (eight times) for
$P_1, Q_1, R_1, S_1$;
$P_2, Q_2, R_2, S_2$;
$P_3, Q_3, R_3, S_3$;
$P_4, Q_4, R_4, S_4$;
$-Q_1, P_1, R_1, S_1$;
$-Q_2, P_2, R_2, S_2$;
$-Q_3, P_3, R_3, S_3$;
$-Q_4, P_4, R_4, S_4,$
we have

\begin{array}{rcl}
& 4 \, \mind(F  \overline G H \overline I \, | \, \partial \Gamma)
- 4 \, \mind(F \overline G \, | \, \partial \Gamma)
- 4 \, \mind(H \overline  I  \, \partial \Gamma)
\\[3mm]
=&2 \, \ind(F  \overline G H \overline I \, | \, \partial \Gamma)
- 2 \, \ind(F \overline G \, | \, \partial \Gamma)
- 2 \, \ind(H \overline  I  \, \partial \Gamma)
\\[3mm]
&+ \ 2 \, \ind(iF  \overline G H \overline I \, | \, \partial \Gamma)
- 2 \, \ind(iF \overline G \, | \, \partial \Gamma)
- 2 \, \ind(H \overline  I  \, \partial \Gamma)
\\[3mm]
= &
- \ \Var_{x_0}^{x_1}( P_1 S_1+  Q_1 R_1, Q_1 S_1)
\ - \ \Var_{y_0}^{y_1}(P_2 S_2 + Q_2 R_2, Q_2 S_2)
\\[3mm]
& - \ \Var_{x_1}^{x_0}( P_3 S_3+  Q_3 R_3, Q_3 S_3)
\ - \  \Var_{y_1}^{y_0}(P_4 S_4+  Q_4 R_4, Q_4 S_4)
\\[3mm]
- \  \Var_{x_0}^{x_1}(-Q_1 S_1+  P_1 R_1, P_1 S_1)
\ - \Var_{y_0}^{y_1}(- Q_2 S_2+ P_2 R_2,P_2 S_2)
\\[3mm]
- \ \Var_{x_1}^{x_0}(-Q_3 S_3+  P_3 R_3, P_3 S_3)
\ - \  \Var_{y_1}^{y_0}(-Q_4 S_4+  P_4 R_4, P_4 S_4).
\end{array}

Therefore, it is enough to prove that the eight $\Var$ add up to $0$.
Concentrating around vertex $(x_0, y_0)$
we will prove that

\begin{array}{rcl}
& {\Sign}(P_1 S_1 + Q_1 R_1, Q_1 S_1, x_0) +
{\Sign}(-Q_1 S_1+ P_1 R_1,  P_1 S_1, x_0)  & = \\[3mm]
= &
{\Sign}(P_4 S_4 + Q_4 R_4,  Q_4 S_4, y_0) +
{\Sign}(- Q_4 S_4+ P_4 R_4, P_4 S_4, y_0).
\end{array}

Since $p+iq = F_{z_0}(z_0)\overline {G_{z_0}(z_0)} \ne 0$
and $r+is = H_{z_0}(z_0)\overline {I_{z_0}(z_0)} \ne 0$
are such that $p, q, s \ne 0$, we have that $qs \ne 0$ and
$ps \ne 0$. Then,  using (<ref>), (<ref>), (<ref>)
and (<ref>)
we have

$${\Sign}( P_1 S_1+ Q_1 R_1, Q_1S_1, x_0)={\sign}((p s+ q r) q  s)
= {\Sign}(- Q_4 S_4+ P_4 R_4, P_4 S_4, y_0)$$

$${\Sign}(-Q_1 S_1+ P_1 R_1, P_1 S_1, x_0)={\sign}((-q s +  p  r) p  s)
= {\Sign}((P_4 S_4+ Q_4 R_4, Q_4 S_4,y_0).$$

If $e < 0$ or $f < 0$ the same identity holds with a similar proof.

For the remaining three vertices, since $(F\overline G)_{\re}$
$(F\overline G)_{\im}$, $(H\overline I)_{\re}$ and
$(H \overline I)_{\im}$
do not vanish at them, a simple evaluation gives

{\Sign}(P_1 S_1 + Q_1 R_1, Q_1 S_1, x_1) =
{\Sign}(P_2 S_2 + Q_2 R_2, Q_2 S_2, y_0),

{\Sign}(-Q_1 S_1+ P_1 R_1,  P_1 S_1, x_1) =
{\Sign}(-Q_2 S_2+ P_2 R_2,  P_2 S_2, x_0),

{\Sign}(P_2 S_2 + Q_2 R_2, Q_2 S_2, y_1) =
{\Sign}(P_3 S_3 + Q_3 R_3, Q_3 S_3, x_1),

{\Sign}(-Q_2 S_2+ P_2 R_2,  P_2 S_2, y_1) =
{\Sign}(-Q_3 S_3+ P_3 R_3,  P_3 S_3, x_1),

{\Sign}(P_3 S_3 + Q_3 R_3, Q_3 S_3, x_0) =
{\Sign}(P_4 S_4 + Q_4 R_4, Q_4 S_4, y_1),

{\Sign}(-Q_3 S_3+ P_3 R_3,  P_3 S_3, x_0) =
{\Sign}(-Q_4 S_4+ P_4 R_4,  P_4 S_4, y_1).

If $e$ is even and $f$ is odd we interchange $F / G$ with $H / I$ and proceed exactly as before.

If $e$ and $f$ are both odd, suppose first
$e\ge 0$ and $f\ge 0$.
By Remark <ref>, $\mind(F \overline G H \overline I\, | \, \partial \Gamma) =\ind(F \overline G H \overline I\, | \, \partial \Gamma)
= \ind(-F \overline G H \overline I\, | \, \partial \Gamma)$.
Then using Proposition <ref> (eight times) for
$P_1, Q_1, R_1, S_1$; $P_2, Q_2, R_2, S_2$;
$P_3, Q_3, R_3, S_3$;
$P_4, Q_4, R_4, S_4$;
$-Q_1, P_1, -S_1, R_1$;
$-Q_2, P_2, -S_2, R_2$;
$-Q_3, P_3, -S_3, R_3$;
$-Q_4, P_4, -S_4, R_4$,
we have

\begin{array}{rcl}
& 4 \, \mind(F  \overline G H \overline I \, | \, \partial \Gamma)
- 4 \, \mind(F \overline G \, | \, \partial \Gamma)
- 4 \, \mind(H \overline  I  \, | \,  \partial \Gamma)
\\[3mm]
=&2 \, \ind(F  \overline G H \overline I \, | \, \partial \Gamma)
- 2 \, \ind(F \overline G \, | \, \partial \Gamma)
- 2 \, \ind(H \overline  I  \, | \,  \partial \Gamma)
\\[3mm]
&+ \ 2 \, \ind(iF  \overline G i H \overline I \, | \, \partial \Gamma)
- 2 \, \ind(iF \overline G \, | \, \partial \Gamma)
- 2 \, \ind(iH \overline  I  \, | \, \partial \Gamma)
\\[3mm]
= &
- \ \Var_{x_0}^{x_1}( P_1 S_1+  Q_1 R_1, Q_1 S_1)
\ - \ \Var_{y_0}^{y_1}(P_2 S_2 + Q_2 R_2, Q_2 S_2)
\\[3mm]
& - \ \Var_{x_1}^{x_0}( P_3 S_3+  Q_3 R_3, Q_3 S_3)
\ - \  \Var_{y_1}^{y_0}(P_4 S_4+  Q_4 R_4, Q_4 S_4)
\\[3mm]
- \  \Var_{x_0}^{x_1}(-  Q_1 R_1 -P_1 S_1 , P_1 R_1)
\ - \ \Var_{y_0}^{y_1}( Q_2 R_2 -P_2 S_2-,P_2 R_2)
\\[3mm]
- \ \Var_{x_1}^{x_0}(- Q_3 R_3 -P_3 S_3 , P_3 R_3)
\ - \  \Var_{y_1}^{y_0}(-  Q_4 R_4-P_4 S_4 ,  P_4 R_4).
\end{array}

Therefore, it is enough to prove that the eight $\Var$ add up to $0$.
Concentrating around vertex $(x_0, y_0)$,
we will prove that

\begin{array}{rcl}
& {\Sign}(P_1 S_1 + Q_1 R_1, Q_1 S_1, x_0) +
{\Sign}(-Q_1 R_1 -P_1 S_1  ,  P_1 R_1, x_0) & = \\[3mm]
= &
{\Sign}(P_4 S_4 + Q_4 R_4,  Q_4 S_4, y_0)
+{\Sign}(-Q_4 R_4 -P_4 S_4  , P_4 R_4, y_0).
\end{array}

Since $p+iq = F_{z_0}(z_0)\overline {G_{z_0}(z_0)} \ne 0$
and $r+is = H_{z_0}(z_0)\overline {I_{z_0}(z_0)} \ne 0$
are such that $p, q, r, s \ne 0$, we have that $qs \ne 0$ and
$pr \ne 0$. Then, using (<ref>), (<ref>),
(<ref>) and (<ref>) we have

$${\Sign}( P_1 S_1+ Q_1 R_1, Q_1S_1, x_0)={\sign}((p s+ q r) q  s) =
{\Sign}(-Q_4 R_4 - P_4 S_4 , P_4 R_4, y_0),$$

$${\Sign}(- Q_1 R_1 - P_1 S_1, P_1 R_1, x_0)={\sign}(-(ps+qr)p r)
= {\Sign}(P_4 S_4+ Q_4 R_4, Q_4 S_4, y_0).$$

If $e < 0$ or $f < 0$ the same identity holds with a similar proof.

For the remaining three vertices, since $(F\overline G)_{\re}$
$(F\overline G)_{\im}$, $(H\overline I)_{\re}$ and
$(H \overline I)_{\im}$
do not vanish at them, a simple evaluation gives

{\Sign}(P_1 S_1 + Q_1 R_1, Q_1 S_1, x_1) =
{\Sign}(P_2 S_2 + Q_2 R_2, Q_2 S_2, y_0),

{\Sign}(- Q_1 R_1 - P_1 S_1, P_1R_1, x_1) =
{\Sign}(- Q_2 R_2 - P_2 S_2, P_2R_2, y_0),

{\Sign}(P_2 S_2 + Q_2 R_2, Q_2 S_2, y_1) =
{\Sign}(P_3 S_3 + Q_3 R_3, Q_3 S_3, x_1),

{\Sign}(- Q_2 R_2 - P_2 S_2, P_2R_2, y_1) =
{\Sign}(-Q_3 R_3 - P_3 S_3, P_3R_3, x_1),

{\Sign}(P_3 S_3 + Q_3 R_3, Q_3 S_3, x_0) =
{\Sign}(P_4 S_4 + Q_4 R_4, Q_4 S_4, y_1),

{\Sign}(-Q_3 R_3 - P_3 S_3, P_3R_3, x_0) =
{\Sign}(-Q_4 R_4 - P_4 S_4 , P_4R_4, y_1).

§ PROOFS OF THE MAIN RESULTS

Now we focus on the proof of
our main results.
First we consider the following lemma.

Let $\Gamma \subset \R^2$ be a rectangle.
For $\gamma \in \C$, $\mind(\gamma \, | \partial \Gamma) = 0$.
For  $F(Z) = Z - z_0$ with $z_0 \in \C$,

\mind(F \, | \, \partial \Gamma) =
\left\{
\begin{array}{cl}
1 & \hbox{if } z_0 \hbox{ is in the interior of } \Gamma, \\[2mm]
\frac12 & \hbox{if } z_0 \hbox{ is in one of the edges of } \Gamma, \\[2mm]
\frac14& \hbox{if } z_0 \hbox{ is in one of the vertices of } \Gamma, \\[2mm]
0 & \hbox{if } z_0 \hbox{ is in the exterior of } \Gamma. \\[2mm]
\end{array}
\right.

\mind(1/F \, | \, \partial \Gamma) =
\left\{
\begin{array}{cl}
-1 & \hbox{if } z_0 \hbox{ is in the interior of } \Gamma, \\[2mm]
-\frac12 & \hbox{if } z_0 \hbox{ is in one of the edges of } \Gamma, \\[2mm]
-\frac14& \hbox{if } z_0 \hbox{ is in one of the vertices of } \Gamma, \\[2mm]
0 & \hbox{if } z_0 \hbox{ is in the exterior of } \Gamma. \\[2mm]
\end{array}
\right.

We omit the proof of Lemma <ref> since it follows
from a straightforward computation.

Proof of Theorem <ref>:
By Lemma <ref>, $\mind$ does the right counting for non-zero constants, linear monic polynomials and their conjugates, and
by Proposition <ref>, $\mind$ is additive with respect to multiplication in $\C(Z) \setminus \{0\}$. This proves the theorem.

Proof of Theorem <ref>:
Theorem <ref> is a corollary of Theorem  <ref>,  since under the assumption that $F/G$ has even valuation at the vertices of $\Gamma$, using
Remark <ref> we have  $\mind(F / G\, | \, \partial \Gamma)=\ind(F / G\, | \, \partial \Gamma)$.

An alternative proof for Theorem <ref> follows
first proving that it
$F(Z) = (Z - z_0)^2$ with
$z_0$ a corner of $\Gamma$,
$\ind$ does the right counting for $F$ and $1/F$, and then using the additivity property for
$\ind$ proven in Proposition <ref>. This proof avoids completely
the definition of $\mind$.

[1] L.V. Ahlfors,
Complex Analysis.
An introduction to the theory of analytic functions of one complex variable. Second edition. Ed. McGraw-Hill Book Company, 1966.

[2]
S. Basu, R. Pollack, M–F. Roy, Algorithms in real algebraic geometry. Second edition. Algorithms and Computation in Mathematics, 10. Springer-Verlag, Berlin, 2006.

[3] M. Eisermann,
The fundamental theorem of algebra made effective: an elementary real-algebraic proof via Sturm chains.
Amer. Math. Monthly 119 (2012), no. 9, 715–752.

[4] D. Perrucci, M.-F. Roy,
A new general formula for the Cauchy Index on an interval with Subresultants. J. Symbolic Comput. 109 (2022), 465-481.

[5] D. Perrucci, M.-F. Roy,
Quantitative fundamental theorem of algebra. Q. J. Math.
70 (2019), no. 3, 1009–1037.


The Open University of<EMAIL_ADDRESS>https://orcid.org/0000-0002-6629-3243 The Open University of
<EMAIL_ADDRESS>Zeev Nutov and Dawod Kahba [100]Theory of computation
Design and analysis of algorithms

###### Acknowledgements.

# A 1.5-approximation algorithm for activating 2 disjoint st-paths

Zeev Nutov  Dawod Kahba

###### Abstract

In the Activation $k$ Disjoint $st$-Paths (Activation $k$-DP) problem we are
given a graph $G=(V,E)$ with activation costs $\\{c_{uv}^{u},c_{uv}^{v}\\}$
for every edge $uv\in E$, a source-sink pair $s,t\in V$, and an integer $k$.
The goal is to compute an edge set $F\subseteq E$ of $k$ internally node
disjoint $st$-paths of minimum activation cost $\displaystyle\sum_{v\in
V}\max_{uv\in E}c_{uv}^{v}$. The problem admits an easy $2$-approximation
algorithm. Alqahtani & Erlebach [1] claimed that Activation $2$-DP admits a
$1.5$-approximation algorithm. The proof of [1] has an error, and we will show
that the approximation ratio of their algorithm is at least $2$. We will then
give a different algorithm with approximation ratio $1.5$.

###### keywords:

disjoint $st$-paths, activation problem, minimum power

##  1 Introduction

In network design problems one seeks a cheap subgraph that satisfies a
prescribed property. A traditional setting is when each edge or node has a
cost, and we want to minimize the cost of the subgraph. This setting does not
capture many wireless networks scenarios, where a communication between two
nodes depends on our ”investment” in these nodes – like transmission energy
and different types of equipment, and the cost incurred is a sum of these
“investments”. This motivates the type of problems we study here.

More formally, in activation network design problems we are given an
undirected (multi-)graph $G=(V,E)$ where every edge $e=uv\in E$ has two (non-
negative) activation costs $\\{c_{e}^{u},c_{e}^{v}\\}$; here $e=uv\in E$ means
that the edge $e$ has ends $u,v$ and belongs to $E$. An edge $e=uv\in E$ is
activated by a level assignment $\\{l_{v}:v\in V\\}$ to the nodes if
$l_{u}\geq c_{e}^{u}$ and $l_{v}\geq c_{e}^{v}$. The goal is to find a level
assignment of minimum value $l(V)=\sum_{v\in V}l_{v}$, such that the activated
edge set $F=\\{e=uv\in E:c_{e}^{u}\leq l_{u},c_{e}^{v}\leq l_{v}\\}$ satisfies
a prescribed property. Equivalently, the minimum value level assignment that
activates an edge set $F\subseteq E$ is given by
$\ell_{F}(v)=\max\\{c_{e}^{v}:e\in\delta_{F}(v)\\}$; here $\delta_{F}(v)$
denotes the set of edges in $F$ incident to $v$, and a maximum taken over an
empty set is assumed to be zero. We seek an edge set $F\subseteq E$ that
satisfies the given property and minimizes $\ell_{F}(V)=\sum_{v\in
V}\ell_{F}(v)$. Note that while we use $l_{v}$ to denote a level assignment to
a node $v$, we use a slightly different notation $\ell_{F}(v)$ for the
function that evaluates the optimal assignment that activates a given edge set
$F$.

Two types of activation costs were extensively studied in the literature, see
a survey [14].

  * •

Node weights. For all $v\in V$, $c_{e}^{v}$ are identical for all edges
incident to $v$. This is equivalent to having node weights $w_{v}$ for all
$v\in V$. The goal is to find a node subset $V^{\prime}\subseteq V$ of minimum
total weight $w(V^{\prime})=\sum_{v\in V^{\prime}}w_{v}$ such that the
subgraph induced by $V^{\prime}$ satisfies the given property.

  * •

Power costs: For all $e=uv\in E$, $c_{e}^{u}=c_{e}^{v}$. This is equivalent to
having “power costs” $c_{e}=c_{e}^{u}=c_{e}^{v}$ for all $e=uv\in E$. The goal
is to find an edge subset $F\subseteq E$ of minimum total power $\sum_{v\in
V}\max\\{c_{e}:e\in\delta_{F}(v)\\}$ that satisfies the given property.

Node weighted problems include many fundamental problems such as Set Cover,
Node-Weighted Steiner Tree, and Connected Dominating Set c.f. [18, 8, 5]. Min-
power problems were studied already in the 90’s, c.f. [19, 21, 17, 7],
followed by many more. They were also widely studied in directed graphs,
usually under the assumption that to activate an edge one needs to assign
power only to its tail, while heads are assigned power zero, c.f. [7, 20, 12,
6, 14]. The undirected case has an additional requirement - we want the
network to be bidirected, to allow a bidirectional communication. The general
activation setting was first suggested by Panigrahi [16] in 2011. Here we use
a simpler but less general setting suggested in [9], which is equivalent to
that of Panigrahi [16] for problems in which inclusion minimal feasible
solutions have no parallel edges.

In the traditional edge-costs scenario, a fundamental problem in network
design is the Shortest $st$-Path problem. A natural generalization and the
simplest high connectivity network design problem is finding a set of $k$
disjoint $st$-paths of minimum edge cost. Here the paths may be edge disjoint
– the $k$ Edge Disjoint $st$-Paths problem, or internally (node) disjoint –
the $k$ Disjoint $st$-Paths problem. Both problems can be reduced to the Min-
Cost $k$-Flow problem, which has a polynomial time algorithm.

Similarly, one of the most fundamental problems in the activation setting is
the Activation $st$-Path problem. For the min-power version, a linear time
reduction to the ordinary Shortest $st$-Path problem is given by Althaus et
al. [3]. Lando and Nutov [10] suggested a more general (but less efficient)
”levels reduction” that converts several power problems into problems with
node costs; this method extends also to the activation setting, see [14]. A
fundamental generalization is activating a set of $k$ internally disjoint or
edge disjoint $st$-paths. Formally, the internally disjoint $st$-paths version
is as follows.

Activation $k$ Disjoint $st$-Paths (Activation $k$-DP)
Input: A multi-graph $G=(V,E)$ with activation costs
$\\{c_{e}^{u},c_{e}^{v}\\}$ for each $uv$-edge $e\in E$, Input:  $s,t\in V$,
and an integer $k$.
Output: An edge set $F\subseteq E$ of $k$ internally disjoint $st$-paths of
minimum activation cost.

Activation $k$-DP admits an easy approximation ratio $2$, c.f. [14, Corollary
15.4] and is polynomially solvable on bounded treewidth graphs [2]. Node-
Weighted Activation $k$-DP admits a polynomial time algorithm, by a reduction
to the ordinary Min-Cost $k$-DP. However, the complexity status of Min-Power
$k$-DP is open even for unit power costs – it is not known whether the problem
is in P or is NPC; this is so even for $k=2$.

In the augmentation version of the problem Activation $k$-DP Augmentation , we
are also given a subgraph $G_{0}=(V,E_{0})$ of $G$ of activation cost zero
that already contains $k-1$ disjoint $st$-paths, and seek an augmenting edge
set $F\subseteq E\setminus E_{0}$ such that $G_{0}\cup F$ contains $k$
disjoint $st$-paths. The following lemma was implicitly proved in [1].

######  Lemma 1.1 ([1]).

If Activation $2$-DP Augmentation admits a polynomial time algorithm then
Activation $2$-DP admits approximation ratio $1.5$.

The justification of Lemma 1.1 is as follows. We may assume that $c_{e}^{s}=0$
and $c_{e}^{t}=0$ for every edge $e$ incident to $s$ or to $t$, respectively.
For this, we “guess” the values $l_{s}=\ell_{F^{*}}(s)$ and
$l_{t}=\ell_{F^{*}}(t)$ of some optimal solution $F^{*}$ at $s$ and $t$,
respectively; there are at most $\deg_{G}(s)\cdot\deg_{G}(t)$ choices, so we
can try all choices and return the best outcome. Then for every edge $e=sv\in
E$, remove $e$ if $c_{e}^{s}>l_{s}$ and set $c^{e}_{s}=0$ otherwise, and apply
a similar operation on edges incident to $t$. One can see that the new
instance is equivalent to the original one. Since the activation cost incurred
at $s$ and $t$ is now zero, the cheaper among the two disjoint $st$ paths of
$F^{*}$ has activation cost at most half $\frac{1}{2}{\sf opt}$, where ${\sf
opt}$ is the optimal solution value (to the modified problem). Thus if we
compute an optimal $st$-path $P$ and and optimal augmenting edge set for $P$,
the overall activation cost will be $\frac{3}{2}{\sf opt}$.

When the paths are required to be only edge disjoint we get the Activation
$k$-EDP problem. This problem admits an easy ratio $2k$. Lando & Nutov [10]
improved the approximation ratio to $k$ by showing that Min-Power $k$-EDP
Augmentation (the augmentation version of Min-Power $k$-EDP) admits a
polynomial time algorithm. This algorithm extends to the activation case, see
[14]. For simple graphs, Min-Power $k$-EDP admits ratio $O(\sqrt{k})$ [15]. On
the other hand [13] shows that ratio $\rho$ for Min-Power or Node-Weighted
$k$-EDP with unit costs/weights implies ratio $1/2\rho^{2}$ for the Densest
$\ell$-Subgraph problem, that currently has best known ratio
$O(n^{-(1/4+\epsilon)})$ [4] and approximation threshold
$\Omega\left(n^{-1/poly(\log\log n)}\right)$ [11].

Based on an idea of Srinivas & Modiano [20], Alqahtani & Erlebach [1] showed
that Activation $2$-EDP is not harder to approximate than Activation $2$-DP.

######  Lemma 1.2 (Alqahtani & Erlebach [1]).

If Activation $2$-DP admits approximation $\rho$ then so is Activation
$2$-EDP.

Alqahtani & Erlebach [1] claimed that Activation $2$-DP Augmentation admits a
polynomial time algorithm, and thus (by Lemmas 1.1 and 1.2) both Activation
$2$-DP and Activation $2$-EDP admit approximation ratio $1.5$. In the next
section we will give an example that the approximation ratio of the [1]
algorithm for Activation $2$-DP Augmentation is not better than $2$. Then we
will give a different polynomial algorithm for Activation $2$-DP Augmentation
that is based on dynamic programming. Thus combining with Lemmas 1.1 and 1.2
we have the following.

######  Theorem 1.3.

Activation $2$-DP Augmentation admits a polynomial time algorithm. Thus both
Activation $2$-DP and Activation $2$-EDP admit approximation ratio $1.5$.

##  2 A bad example for the Alqahtani-Erlebach Algorithm

To illustrate the idea of the [1] algorithm, let us first describe a known
algorithm for a particular case of the Min-Cost $2$-EDP Augmentation problem,
where we seek to augment a Hamiltonian $st$-path $P$ of cost $0$ by an min-
cost edge set $F$ such that $P\cup F$ contains $2$ edge disjoint $st$-paths.
The algorithm reduces this problem to the ordinary Min-Cost $st$-Path problem
as follows, see Fig. 1(a,b).

1 Construct an edge-weighted digraph $D_{P}$ by directing $P$ “backward” from
$t$ to $s$, and directing every edge not in $P$ ”forward” – from predecessor
to successor in $P$.

2 Compute a shortest $st$-path $P^{\prime}$ in $D_{P}$.

Return the subset $F$ of $E$ that corresponds to the edges of
$P^{\prime}\setminus P$.

Algorithm 1 Hamiltonian Min-Cost $2$-EDP Augmentation$((V,E),c,P,\\{s,t\\})$

A slight modification of this algorithm works for Activation $2$-EDP
Augmentation. For $v\in V$ let $L_{v}=\\{c_{vu}^{v}:vu\in E\\}$ be the set of
possible levels at $v$. Apply the reduction in Algorithm 1, and then apply a
step which we call Levels Splitting: for every pair $(v,l)$ where $v\in V$ and
$l\in L_{v}$ we add a node $v_{l}$ of weight $l$, and put an edge from
$u_{l_{i}}$ to $v_{l_{j}}$ if there is an edge $e=uv$ in $D_{P}$ with
$c_{e}^{u}\leq l_{i}$ and $c_{e}^{v}\leq l_{j}$. The reduction here is to the
Node-Weighted $st$-Path problem. The later problem can be easily reduced to
the ordinary Min-Cost $st$-Path problem by a step which we call In-Out
Splitting: Replace each node $v\in V\setminus\\{s,t\\}$ by two nodes $v^{\sf
in},v^{\sf out}$ connected by the edge $v^{\sf in}v^{\sf out}$, and redirect
every edge that enters $v$ to enter $v^{\sf in}$ and every edge that leaves
$v$ to leave $v^{\sf out}$, where we assume that $s^{\sf in}=s^{\sf out}=s$
and $t^{\sf in}=t^{\sf out}=t$. In this reduction the cost/weight of each edge
$v^{\sf in}v^{\sf out}$ is the weight $w_{v}$ of $v$, see Fig. 1(a,b,c). This
is a particular case of the “Levels Reduction” of [10].

Figure 1: Augmenting a Hamiltonian $st$-path to two edge/internally disjoint
$st$-paths. Black edges have cost $0$, blue and red edges have cost $1$. (a)
Problem instance. (b) Reducing Min-Cost $2$-EDP Augmentation to Min-Cost
$st$-Path. (c) Levels splitting, assuming that the activation costs of the
blue edges in (a) are $1$ at $x,v,y$ and $0$ at $s,t$. (d) Reducing Min-Cost
$2$-DP Augmentation to Min-Cost $st$-Path. (e) The reduction of [1].

One can also solve the version when we have ordinary edge costs and require
that $P\cup F$ contains $2$ internally disjoint $st$-paths. For that, apply a
standard reduction that converts edge connectivity problems into node
connectivity ones, as follows

  1. (i)

After step 1 of Algorithm 1, add the In-Out Splitting step, where here the the
cost of each edge $v^{\sf in}v^{\sf out}$ is $0$.

  2. (ii)

Replace every edge $u^{\sf out}v^{\sf in}\notin P$ by the edge $u^{\sf
in}v^{\sf out}$.

See Fig. 1(d), where after applying this reduction we switched between the
names of $v^{\sf in}v^{\sf out}$, to be consistent with the [1] algorithm.

The algorithm of [1] attempts to combine the later reduction with the Levels
Reduction in a sophisticated way. In the case when $G$ has a zero cost
Hamiltonian $st$-path $P$, $st\notin E$, $L=\\{0,1\\}$, $L_{s}=L_{t}=\\{0\\}$,
and $c_{uv}^{u}=1$ for all $e=uv\in E\setminus E(P)$ and $u\in
V\setminus\\{s,t\\}$, the [1] algorithm reduces to the following, see Fig.
1(a,e).

  1. 1.

Construct an edge-weighted directed graph $D_{P}$ with nodes $s=s_{0}^{\sf
out},t=t_{0}^{\sf in}$ and $4$ nodes $\\{v_{0}^{\sf in},v_{0}^{\sf
out},v_{1}^{\sf in},v_{1}^{\sf out}\\}$ for every $v\in V\setminus\\{s,t\\}$.
The edge of $D_{P}$ and their weights are:

    1. (i)

For $v\in V\setminus\\{s,t\\}$: $w(v_{a}^{\sf out}v_{a}^{\sf in})=0$
$a\in\\{0,1\\}$.

    2. (ii)

For $uv\in P$: $w(v_{b}^{\sf in}u_{a}^{\sf out})=a$ $a,b\in\\{0,1\\}$.
For $uv\notin P$: $w(u_{a}^{\sf out}v_{b}^{\sf in})=b$ $a,b\in\\{0,1\\}$,
$u_{a}v_{b}\in E$.

  2. 2.

Compute a cheapest $st$-path $P^{\prime}$ in $D_{P}$ and return the subset of
$E$ that corresponds to $P^{\prime}$.

Figure 2:  Illustration to the [1] Algorithm. Black edges have
weight/thresholds $0$. (a) The input graph; colored edges have thresholds $0$
at $s,t$ and $1$ otherwise. (b) The edge weighted directed graph $D_{P},w$
constructed in the AE reduction and the path (shown by dashed lines) in
$D_{P}$ of weight $4$ that corresponds to the optimal solution
$\\{sx,xz,zt,uy,yq\\}$. (c) The path (shown by dashed lines) in $D_{P}$ of
weight $4$ that corresponds to the solution $\\{sv,uy,xz,yq,pt\\}$.

Here for $e=uv\in E$ we write $u_{a}v_{b}\in E$ meaning that $c_{e}^{a}\leq a$
and $c_{e}^{b}\leq b$, namely, that $uv$ can be activated by assigning $a$
units to $u$ and $b$ units to $v$. In the example in Fig. 1(d), the weight of
$P^{\prime}$ is $2$ while the optimal solution value is $3$. Still, in this
example the [1] algorithm computes an optimal solution. We give a more
complicated example, which shows that the approximation ratio of this
algorithm is no better than $2$. Consider the graph in Fig. 2(a), with the
initial $st$-path

$s-u-v-x-y-z-p-q-t\ .$

The optimal solution $\\{sx,xz,zt,,uy,yq\\}$ (the blue edges and the $uy,yq$
edges) has value $2$ (level assignment $l_{x}=l_{z}=1$ and $0$ otherwise); the
$s_{0}^{\sf out}t_{0}^{\sf in}$-path in $D_{P}$ of weight $4$ that corresponds
to this solution is (see Fig. 2(b)):

$s_{0}^{\sf out}{\color[rgb]{0,0,1}\rightarrow}\ x_{1}^{\sf in}\rightarrow
v_{0}^{\sf out}\rightarrow v_{0}^{\sf in}\rightarrow u_{0}^{\sf
out}\rightarrow y_{0}^{\sf in}{\color[rgb]{0.5,0.5,0}\rightarrow}\ x_{1}^{\sf
out}{\color[rgb]{0,0,1}\rightarrow}\ z_{1}^{\sf in}\rightarrow y_{0}^{\sf
out}\rightarrow\ q_{0}^{\sf in}\rightarrow p_{0}^{\sf out}\rightarrow
p_{0}^{\sf in}{\color[rgb]{0.5,0.5,0}\rightarrow}\ z_{1}^{\sf out}\rightarrow\
t_{0}^{\sf in}\ .$

The solution $\\{sv,uy,xz,yq,pt\\}$ (the red edges and the $uy,yq,xz$ edges)
has value $4$ (level assignment $l_{v}=l_{x}=l_{z}=l_{p}=1$ and $0$
otherwise); the $s_{0}^{\sf out}t_{0}^{\sf in}$-path in $D_{P}$ of weight $4$
that corresponds to this solution is (see Fig. 2(c)):

$s_{0}^{\sf out}{\color[rgb]{1,0,0}\rightarrow}\ v_{1}^{in}\rightarrow
u_{0}^{\sf out}\rightarrow y_{0}^{\sf in}{\color[rgb]{0.5,0.5,0}\rightarrow}\
x_{1}^{\sf out}{\color[rgb]{0,0,1}\rightarrow}\ z_{1}^{\sf in}\rightarrow
y_{0}^{\sf out}\rightarrow q_{0}^{\sf in}{\color[rgb]{0.5,0.5,0}\rightarrow}\
p_{1}^{\sf out}\rightarrow t_{0}^{\sf in}\ .$

So in $D_{P}$, both paths have the same weight $4$, but one path gives a
solution of value $2$ while the other of value $4$.

##  3 Proof of Theorem 1.3

In this section we will prove Theorem 1.3 – that Activation $2$-DP
Augmentation admits a polynomial time algorithm

Recall that for $F\subseteq E$ and $v\in V$ we denote by
$\displaystyle\ell_{F}(v)=\max_{e\in\delta_{F}(v)}c_{e}^{v}$ the activation
cost incurred by $F$ at $v$, and that for $S\subseteq V$ the activation cost
incurred by $F$ at nodes in $S$ is

$\displaystyle\ell_{F}(S)=\sum_{v\in S}\ell_{F}(v)=\sum_{v\in
S}\max_{e\in\delta_{F}(v)}c_{e}^{v}\ .$

For the proof of Theorem 1.3 it would be convenient to consider a more general
problem where each edge $e=uv\in E$ has three costs
$c_{e}^{u},c(e),c_{e}^{v}$, where $c_{e}^{u},c_{e}^{v}$ are the activation
costs of $e$ and $c(e)$ is the ordinary “middle” cost of $e$. We now describe
a method to convert an Activation $2$-DP Augmentation instance into an
equivalent instance in which $P$ is a Hamiltonian path but every edge has
three costs as above. We call this problem 3-Cost Hamiltonian Activation
$2$-DP Augmentation.

Let ${\cal I}=(G=(V,E),c,s,t,P)$ be an Activation $2$-DP Augmentation
instance. Let us say that a $uv$-path $Q$ in $G$ is an attachment path if
$u,v\in P$ but $Q$ has no internal node in $P$. Note that any inclusion
minimal edge set that contains $2$ internally disjoint $st$-paths is a cycle.
This implies that if $F$ is an inclusion minimal solution to Activation $2$-DP
Augmentation then $\deg_{F}(v)\in\\{0,2\\}$ for every node $v\in V\setminus
V(P)$, hence $F$ partitions into attachment paths. This enables us to apply a
prepossessing similar to metric completion, and to construct an equivalent
3-Cost Hamiltonian Activation $2$-DP Augmentation instance $\hat{\cal
I}=(\hat{G}=(\hat{V},\hat{E}),\hat{c},s,t,P)$. For this, for every $u,v\in P$
and $(l_{u},l_{v})\in L_{u}\times L_{v}$ do the following.

  1. 1.

Among all attachment $uv$-paths that have activation costs $l_{u}$ at $u$ and
$l_{v}$ at $v$ (if any), compute the cheapest one $Q(l_{u},l_{v})$.

  2. 2.

If $Q(l_{u},l_{v})$ exists, add a new edge $e=uv$ with activation costs
$\hat{c}_{e}^{u}=l_{u},\hat{c}_{e}^{v}=l_{v}$, and ordinary cost
$\hat{c}_{e}=\ell_{Q(l_{u},l_{v})}(V)-(l_{u}+l_{v})$ being the activation cost
of $Q(l_{u},l_{v})$ on internal nodes of $Q(l_{u},l_{v})$.

After that, remove all nodes in $V\setminus V(P)$. Now $P$ is a Hamiltonian
path, and we get a 3-Cost Hamiltonian Activation $2$-DP Augmentation instance
$\hat{\cal I}=(\hat{G},\hat{c},s,t,P)$. It is easy to see that the instance
$\hat{\cal I}$ can be constructed in polynomial time. Note that the instance
${\cal I}^{\prime}$ may have many parallel edges, but this is allowed, also in
the original instance ${\cal I}$.

Now consider some feasible solution $F$ to ${\cal I}$. Replacing every
attachment paths contained in $F$ by a single edge as in step 2 above gives a
feasible solution $\hat{F}$ to $\hat{\cal I}$ of value at most that of $F$.
Conversely, if $\hat{F}$ is a feasible $\hat{\cal I}$ solution, then replacing
every edge in $\hat{F}$ by an appropriate path gives a feasible solution $F$
to ${\cal I}$ of value at most that of $\hat{F}$. Consequently, the new
instance is equivalent to the original instance in the sense that every
feasible solution to one of the instances can be converted to a feasible
solution to the other instance of no greater value. We summarize this as
follows.

######  Corollary 3.1.

If 3-Cost Hamiltonian Activation $2$-DP Augmentation admits a polynomial time
algorithm then so is Activation $2$-DP Augmentation.

So from now and on our problem is 3-Cost Hamiltonian Activation $2$-DP
Augmentation. Let us denote by $\tau(F)$ the sum of the ordinary and the
activation cost of $F\subseteq E$, namely

$\tau(F)=\ell_{F}(V)+c(F)=\sum_{v\in
V}\max_{e\in\delta_{F}(v)}c_{e}^{v}+\sum_{e\in F}c(e)\ .$

Let ${\sf opt}$ denote an optimal solution value for an instance of this
problem. We will assume that $V=\\{0,1,\ldots,n\\}$ and that $P=0-1-\cdots-n$
is a (Hamiltonian) $(0,n)$-path, and view each edge $ij\notin P$ as a directed
edge $(i,j)$ where $i<j$. Our goal is to find and edge set $F\subset E$ such
that $P\cup F$ contains $2$ internally disjoint $(0,n)$-paths and such that
$\tau(F)$ is minimal.

######  Definition 3.2.

For $0\leq i<j<n$ let ${\cal F}_{i,j}$ denote the family of all edge sets
$F\subseteq E$ that satisfy the following two conditions.

  1. (i)

$F$ is an inclusion minimal edge set such that $P\cup F$ contains $2$
internally disjoint $(j-1,n)$-paths.

  2. (ii)

No edge in $F$ has an end strictly preceding $i$, namely, if $(x,y)\in F$ then
$x\geq i$.

We will need the following (essentially known) “recursive” property of the
sets in ${\cal F}_{i,j}$.

######  Lemma 3.3.

$F\in{\cal F}_{i,j}$ if and only if there exists $i\leq x<j$ such that exactly
one of the following holds, see Fig. 3(a).

  1. (i)

$F=\\{(x,n)\\}$.

  2. (ii)

$F=\\{(x,y)\\}\cup F^{\prime}$ for some $(x,y)\in E$ with $i\leq x<j<y<n$ and
$F^{\prime}\in{\cal F}_{j,y}$.

######  Proof 3.4.

It is easy to see that if $|F|=1$ then (i) must hold. Assume that $|F|\geq 2$.
There is $(x,y)\in F$ with $x<j<y$ as otherwise $(P\cup F)\setminus\\{j\\}$
has no $(j-1,n)$-path. Let $F^{\prime}=F\setminus\\{(x,y)\\}$. Then $P\cup
F^{\prime}$ contains $2$ internally disjoint $(y-1,n)$-paths, as otherwise
$(P\cup F)\setminus\\{y\\}$ has no $(j-1,n)$-path. Let $x^{\prime}$ be the
lowest end of an edge in $F^{\prime}$, let $(x^{\prime},y^{\prime})\in
F^{\prime}$, and let
$F^{\prime\prime}=F\setminus\\{(x^{\prime},y^{\prime})\\}$. If $x^{\prime}<j$
then $F^{\prime}\in{\cal F}_{i,j}$ (if $y^{\prime}\geq y$) or
$F^{\prime\prime}\in{\cal F}_{i,j}$ (if $y^{\prime}\leq y$), contradicting the
minimality of ${\cal F}$. If $x^{\prime}\geq y$ then $(P\cup
F)\setminus\\{y\\}$ has no $(j-1,n)$-path. This implies that
$F^{\prime}\in{\cal F}_{i,j}$, hence (ii) holds.

Figure 3: Illustration to Lemma 3.3. Three dots between nodes indicates that
these nodes are distinct, while if there are only two dotes then the nodes may
coincide.

We note that Lemma 3.3 has the following (essentially known) consequence.
Consider an inclusion minimal feasible solution $F$ to our problem. Then the
edges in $F$ have an order
$(v_{0},v_{2}),(v_{1},v_{4}),(v_{3},v_{6}),\ldots,(v_{2q-1},v_{2q+1})$ such
that (see Fig. 3(b))

$0=v_{0}<v_{1}<v_{2}\leq v_{3}<v_{4}\leq v_{5}<\cdots\leq
v_{2q-1}<v_{2q}<v_{2q+1}=n\ .$

Note that in this node sequence some nodes may be identical (e.g., we may have
$v_{2}=v_{3}$), while the others are required to be distinct (e.g.,
$v_{0}<v_{1}<v_{2}$).

For $(l_{i},l_{j})\in L_{i}\times L_{j}$ let $E(l_{i},l_{j})=\\{e\in
E:\ell_{e}(l_{i})\leq l_{i},\ell_{e}(l_{j})\leq l_{j}\\}$. Let $0\leq i<j<n$.
For $F\subseteq E$ the $(l_{i},l_{j})$-forced cost of $F$ is defined by

$\alpha_{F}(l_{i},l_{j})=\left\\{\begin{array}[]{ll}c(F)+\ell_{F}(V\setminus\\{i,j\\})+l_{i}+l_{j}&\
\mbox{if}\ \ F\subseteq E(l_{i},l_{j})\\\ \infty&\mbox{
otherwise}\end{array}\right.$

Namely, assuming $F\subseteq E(l_{i},l_{j})$ we pay $\ell_{F}(v)$ at every
node $v\in V\setminus\\{i,j\\}$, and in addition we “forcefully” pay $l_{i}$
at $i$ and $l_{j}$ at $j$. Note that

$\alpha_{F}(l_{i},l_{j})=c(F)+\ell_{F}(V\setminus\\{i,j\\})+l_{i}+l_{j}=\tau(F)+(l_{i}-\ell_{F}(i))+(l_{j}-\ell_{F}(j))\
.$

This implies the following.

######  Corollary 3.5.

$\alpha_{F}(l_{i},l_{j})\geq\tau(F)$ and an equality holds if and only if
$\ell_{F}(i)=l_{i}$ and $\ell_{F}(j)=l_{j}$.

Let $f(l_{i},l_{j})$ denote the minimal $(l_{i},l_{j})$-forced cost of an edge
set $F\in{\cal F}_{i,j}$, namely

$f(l_{i},l_{j})=\min_{F\in{\cal F}_{i,j}}\alpha_{F}(l_{i},l_{j})\ .$ (1)

The number of possible values of $f(l_{i},l_{j})$ is $O(|V|^{2}|L|^{2})$ \-
there are $O(|V|^{2})$ choices of $i,j$ and at most $|L|^{2}$ choices of
$l_{i},l_{j}$. We will show how to compute all these values in polynomial time
using dynamic programming. Specifically, we will get a recursive formula that
enables to compute each value either directly, or using previously computed
values.

The next lemma shows how the function $f(l_{i},l_{j})$ is related to our
problem.

######  Lemma 3.6.

${\sf opt}=\displaystyle{\min_{l_{0},l_{1}\in L}f(l_{0},l_{1})}$.

######  Proof 3.7.

From the definition of ${\cal F}_{i,j}$ it follows that that ${\cal F}_{0,1}$
is the set of all inclusion minimal feasible solutions. Let $F^{*}$ be an
inclusion minimal optimal solution and let $\hat{F}$ be the minimizer of (1).
Then for any $l_{0},l_{1}$ we have

$f(l_{0},l_{1})=\alpha_{\hat{F}}(l_{0},l_{1})\geq\tau(\hat{F})\geq\tau(F^{*})={\sf
opt}\ .$

Consequently, $\displaystyle{\min_{l_{0},l_{1}\in L}f(l_{0},l_{1})}\geq{\sf
opt}$. On the other hand for $l_{0}=\ell_{F^{*}}(0)$ and
$l_{1}=\ell_{F^{*}}(1)$ we have

$f(l_{0},l_{1})=\alpha_{F^{*}}(l_{0},l_{1})=\tau(F^{*})={\sf opt}\ ,$

by Corollary 3.5. This implies $\displaystyle{\min_{l_{0},l_{1}\in
L}f(l_{0},l_{1})}\leq{\sf opt}$, concluding the proof.

When $F=\\{e\\}$ is a single edge we will use the abbreviated notation
$\alpha_{e}(l_{i},l_{j})=\alpha_{\\{e\\}}(l_{i},l_{j})$. For $(l_{i},l_{y})\in
L_{i}\times L_{y}$ and an edge $e=(x,y)\in E(l_{i},l_{y})$ with $i\leq x<y$
let $\beta_{e}(l_{i},l_{y})$ be defined by

$\beta_{e}(l_{i},l_{y})=\left\\{\begin{array}[]{ll}0&\mbox{if}\ x=i\\\
\ell_{e}(x)&\mbox{if}\ x>i\end{array}\right.$

We now define two functions that reflect the two different scenarios in Lemma
3.3.

$\displaystyle g(l_{i},l_{j})$ $\displaystyle=$
$\displaystyle\min_{e}\\{\alpha_{e}(l_{i},l_{j}):e=(x,n)\in E,i\leq x<j\\}$
$\displaystyle h(l_{i},l_{j})$ $\displaystyle=$
$\displaystyle\min_{l_{y},e}\\{c(e)+l_{i}+\beta_{e}(l_{i},l_{y})+f(l_{j},l_{y}):e=(x,y)\in
E(l_{i},l_{y}),i\leq x<j<y\\}$

It is not hard to see that the function $g(l_{i},l_{j})$ is the minimal
$(l_{i},l_{j})$-forced cost of a single edge set $e=(x,n)$ such that
$\\{e\\}\in{\cal F}_{i,j}$. Thus if there exist a minimizer of (1) that is a
single edge, then $f(l_{i},l_{j})=g(l_{i},l_{j})$.

We will show that the function $h(l_{i},l_{j})$ is the minimal
$(l_{i},l_{j})$-forced cost of a non-singleton set $F\in{\cal F}_{i,j}$; note
that by lemma 3.3 any such $F$ is a union of some single edge $(x,y)\in F$
with $i\leq x<j<y<n$ and $F^{\prime}\in{\cal F}_{j,y}$. We need the following
lemma.

######  Lemma 3.8.

Let $F\in{\cal F}_{i,j}$ such that $F\subseteq E(l_{i},l_{j})$ and $|F|\geq
2$. Let $(x,y)\in F$ be the first edge of $F$ as in Lemma 3.3, let
$F^{\prime}=F\setminus\\{e\\}$, and let $l_{y}=\ell_{F}(y)$. Then

$\alpha_{F}(l_{i},l_{j})=c(e)+l_{i}+\beta_{e}(l_{i},l_{y})+\alpha_{F^{\prime}}(l_{j},l_{y})$

######  Proof 3.9.

One can verify that for $l_{y}=\ell_{F}(y)$ we have $F^{\prime}\subseteq
E(l_{j},l_{y})$ and the following holds:

$\ell_{F}(V\setminus\\{i,j\\})=\beta_{e}(l_{i},l_{y})+\ell_{F^{\prime}}(V\setminus\\{j,y\\})+l_{y}\
.$

From this and using that $c(F)=c(e)+c(F^{\prime})$ we get

$\displaystyle\alpha_{F}(l_{i},l_{j})$ $\displaystyle=$ $\displaystyle
c(F)+\ell_{F}(V\setminus\\{i,j\\})+l_{i}+l_{j}$ $\displaystyle=$
$\displaystyle
c(e)+l_{i}+\beta_{e}(l_{i},l_{y})+c(F^{\prime})+\ell_{F^{\prime}}(V\setminus\\{j,y\\})+l_{y}+l_{j}$
$\displaystyle=$ $\displaystyle
c(e)+l_{i}+\beta_{e}(l_{i},l_{y})+\alpha_{F^{\prime}}(l_{j},l_{y})\ ,$

as required.

######  Lemma 3.10.

Among all non-singleton sets in ${\cal F}_{i,j}$ let $F^{*}$ have minimal
$(l_{i},l_{j})$-forced cost. Then
$h(l_{i},l_{j})=\alpha_{F^{*}}(l_{i},l_{j})$.

######  Proof 3.11.

We show that $\alpha_{F^{*}}(l_{i},l_{j})\geq h(l_{i},l_{j})$. Let $e=(x,y)\in
F^{*}$ be the first edge of $F^{*}$ as in Lemma 3.3(ii), let
$F^{\prime}=F\setminus\\{e\\}$, and let $l_{y}=\ell_{F^{*}}(y)$. Then $e\in
E(l_{i},l_{y})$, hence by Lemma 3.8

$\alpha_{F^{*}}(l_{i},l_{j})=c(e)+l_{i}+\beta_{e}(l_{i},l_{y})+\alpha_{F^{\prime}}(l_{j},l_{y})\geq
h(l_{i},l_{j})\ .$

The inequality is since in the definition of $h(l_{i},l_{j})$ we minimize over
$e=(x,y)$ and $l_{y}$.

We show that $\alpha_{F^{*}}(l_{i},l_{j})\leq h(l_{i},l_{j})$. Let $e=(x,y)\in
E$ and $l_{y}$ be the parameters for which the minimum in the definition of
$h(l_{i},l_{j})$ is attained, and let $F^{\prime}\in{\cal F}_{j,y}$ such that
$f(l_{j},l_{y})=\alpha_{F^{\prime}}(l_{j},l_{y})$. Let
$F=F^{\prime}\cup\\{e\\}$ and note that $F\in{\cal F}_{i,j}$ (by Lemma 3.3)
and that $l_{y}=\ell_{F}(y)$ (by the definition of $h(l_{i},l_{j})$).
Consequently,

$\alpha_{F^{*}}(l_{i},l_{j})\leq\alpha_{F}(l_{i},l_{j})=c(e)+l_{i}+\beta_{e}(l_{i},l_{y})+f(l_{j},l_{y})=h(l_{i},l_{j})$

The inequality is since $F^{*}$ has minimal $(l_{i},l_{j})$-forced cost.

We showed that $\alpha_{F^{*}}(l_{i},l_{j})\geq h(l_{i},l_{j})$ and that
$\alpha_{F^{*}}(l_{i},l_{j})\leq h(l_{i},l_{j})$, hence the proof is complete.

Let $F^{*}$ be the minimizer of (1). From Lemma 3.10 we have:

  * •

If $|F^{*}|=1$ then $f(l_{i},l_{j})=g(l_{i},l_{j})$.

  * •

If $|F^{*}|\geq 2$ then $f(l_{i},l_{j})=h(l_{i},l_{j})$.

Therefore

$f(l_{i},l_{j})=\min\\{g(l_{i},l_{j}),h(l_{i},l_{j})\\}$ (2)

Note that the quantities $g(l_{i},l_{j})$ can be computed directly in
polynomial time. The recurrence in (2) enables to compute values of
$f(l_{i},l_{j})$, for all $0\leq i<j\leq n-1$ and $(l_{i},l_{j})\in
L_{i}\times L_{j}$, in polynomial time. The number of such values is
$O(n^{2}|L|^{2})$, concluding the proof of Theorem 1.3.

Let us illustrate the recursion by showing how the values of $f(l_{i},l_{j})$
are computed for $j=n-1,n-2$. Recall that the values of the function $g$ are
computed directly, without recursion and that

$h(l_{i},l_{j})=\min_{l_{y},e}\\{c(e)+l_{i}+\beta_{e}(l_{i},l_{y})+f(l_{j},l_{y}):e=(x,y)\in
E(l_{i},l_{y}),i\leq x<j<y\\}$

For $j=n-1$ we have $h(l_{i},l_{j})=\infty$, and thus:

$f(l_{i},l_{n-1})=g(l_{i},l_{n-1})$

For $j=n-2$, the only possible value of $y$ is $y=n-1$. For every $i\leq
x<y=n-1$ and $e=xy\in E$ we compute directly (without recursion) the values
$\beta_{e}(l_{i},l_{y})$. Then

$\displaystyle\displaystyle h(l_{i},l_{n-2})$ $\displaystyle=$
$\displaystyle\min_{l_{y},e}\\{c(e)+l_{i}+\beta_{e}(l_{i},l_{y})+f(l_{j},l_{y}):e=(x,y)\in
E(l_{i},l_{y}),i\leq x<j<y\\}$ $\displaystyle=$
$\displaystyle\min_{l_{n-1},e}\left\\{c(e)+l_{i}+\beta_{e}(l_{i},l_{n-1})+f(l_{n-2},l_{n-1}):\begin{array}[]{ll}e=(x,n-1)\in
E(l_{i},l_{n-1})\\\ i\leq x<j<n-1\end{array}\right\\}$

Substituting the already computed value
$f(l_{n-2},l_{n-1})=g(l_{n-2},l_{n-1})$ enables to compute the minimum of the
obtained expression, and thus also to compute $f(l_{i},l_{n}-2)$ via (2).

In a similar way we can compute $h(l_{i},l_{n-3})$, then $f(l_{i},l_{n-3})$,
and so on.

## References

  * [1] H. M. Alqahtani and T. Erlebach.  Approximation algorithms for disjoint $st$-paths with minimum activation cost.  In CIAC, pages 1–12, 2013.
  * [2] H. M. Alqahtani and T. Erlebach.  Minimum activation cost node-disjoint paths in graphs with bounded treewidth.  In SOFSEM, pages 65–76, 2014.
  * [3] E. Althaus, G. Calinescu, I. Mandoiu, S. Prasad, N. Tchervenski, and A. Zelikovsky.  Power efficient range assignment for symmetric connectivity in static ad-hoc wireless networks.  Wireless Networks, 12(3):287–299, 2006.
  * [4] A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and A. Vijayaraghavan.  Detecting high log-densities: an $O(n^{1/4})$ approximation for densest $k$-subgraph.  In STOC, pages 201–210, 2010.
  * [5] S. Guha and S. Khuller.  Approximation algorithms for connected dominating sets.  Algorithmica, 20:374–387, 1998.
  * [6] M. Hajiaghayi, G. Kortsarz, V. Mirrokni, and Z. Nutov.  Power optimization for connectivity problems.  Math. Program., 110(1):195–208, 2007.
  * [7] L. M. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc.  Power consumption in packet radio networks.  Theoretical Computer Science, 243(1-2):289–305, 2000.
  * [8] P. Klein and R. Ravi.  A nearly best-possible approximation algorithm for node-weighted Steiner trees.  J. Algorithms, 19(1):104–115, 1995.
  * [9] G. Kortsarz, Z. Nutov, and E. Shalom.  Approximating activation edge-cover and facility location problems.  Theoretical Computer Science, 930:218–228, 2022.
  * [10] Y. Lando and Z. Nutov.  On minimum power connectivity problems.  J. Discrete Algorithms, 8(2):164–173, 2010.
  * [11] P. Manurangsi.  Almost-polynomial ratio ETH-hardness of approximating densest $k$-subgraph.  In STOC, pages 954–961, 2017.
  * [12] Z. Nutov.  Approximating minimum power covers of intersecting families and directed edge-connectivity problems.  Theoretical Computer Science, 411(26-28):2502–2512, 2010.
  * [13] Z. Nutov.  Approximating steiner networks with node-weights.  SIAM J. Comput., 39(7):3001–3022, 2010.
  * [14] Z. Nutov.  Activation network design problems.  In T. F. Gonzalez, editor, Handbook on Approximation Algorithms and Metaheuristics, Second Edition, volume 2, chapter 15. Chapman & Hall/CRC, 2018.
  * [15] Z. Nutov.  An $o(\sqrt{k})$-approximation algorithm for minimum power $k$ edge disjoint $st$-paths.  CoRR, abs/2208.09373, 2022.  To appear in CIE 2023.  URL: https://doi.org/10.48550/arXiv.2208.09373.
  * [16] D. Panigrahi.  Survivable network design problems in wireless networks.  In SODA, pages 1014–1027, 2011.
  * [17] V. Rodoplu and T. H. Meng.  Minimum energy mobile wireless networks.  In IEEE International Conference on Communications (ICC), pages 1633–1639, 1998.
  * [18] A. Segev.  The node-weighted Steiner tree problem.  Networks, 17:1–17, 1987.
  * [19] S. Singh, C. S. Raghavendra, and J. Stepanek.  Power-aware broadcasting in mobile ad hoc networks.  In Proceedings of IEEE PIMRC, 1999.
  * [20] A. Srinivas and E. H. Modiano.  Finding minimum energy disjoint paths in wireless ad-hoc networks.  Wireless Networks, 11(4):401–417, 2005.
  * [21] J E. Wieselthier, G. D. Nguyen, and A. Ephremides.  On the construction of energy-efficient broadcast and multicast trees in wireless networks.  In Proc. IEEE INFOCOM, pages 585–594, 2000.