myequation

$\BODY$

(1)

myequation2

$\BODY$

(2)

myequation3

$\BODY$

(3)

# Analyticity domains of critical points of polynomials. A proof of Sendov’s
conjecture

Petar P. Petrov Email<EMAIL_ADDRESS>
(August 27, 2024)

###### Abstract

Let $\mathscr{P}_{n}^{c}(\bar{\mu},\bar{\nu})$ be the set of all complex
polynomials $p(z)=\prod_{i=1}^{m}(z-z_{i})^{\mu_{i}}$,
$\sum_{i=1}^{m}\mu_{i}=n$, with derivatives of the form

$p^{\prime}(z)=n\prod_{i=1}^{m}(z-z_{i})^{\mu_{i}-1}\prod_{j=1}^{k}(z-\xi_{j})^{\nu_{j}},\leavevmode\nobreak\
\sum_{j=1}^{k}\nu_{j}=m-1.$

In this note we prove the following:

For a fixed ordering $\alpha=(1,2,\ldots,m)$, the distinct zeros
$\\{z_{i}\\}_{i=1}^{m}$ and the distinct critical points of the second kind
$\\{\xi_{j}\\}_{j=1}^{k}$ of polynomials from
$\mathscr{P}_{n}^{c}(\bar{\mu},\bar{\nu})$ are analytic functions
$\\{z_{i}^{\alpha\beta}\\}_{i=1}^{m}$ and
$\\{\xi_{j}^{\alpha\beta}\\}_{j=1}^{k}$, resp.,
$\beta=(i_{1},i_{2},\ldots,i_{k+1})$, of any of the variables
$(z_{i_{1}},z_{i_{2}},\ldots,z_{i_{k+1}})$ in the domain

$\\{(z_{i_{1}},z_{i_{2}},\ldots,z_{i_{k+1}})\in{\mathbb{C}}^{k+1}\leavevmode\nobreak\
|\leavevmode\nobreak\ p\in\mathscr{P}_{n}^{c}(\bar{\mu},\bar{\nu})\\},$

being also continuous on its boundary.

This statement gives an immediate proof to the well-known conjecture of Bl.
Sendov [4]:

If $n\geq 2$ and $p(z)=\prod_{i=1}^{n}(z-z_{i})$ is a polynomial of degree $n$
such that $z_{i}\in{\mathbb{C}}$, $|z_{i}|\leq 1$, $i=1,2,\ldots,n$, then for
every $i=1,2,\ldots,n$, the disk $\\{z\in{\mathbb{C}}\,|\,|z_{i}-z|\leq 1\\}$
contains at least one zero of $p^{\prime}(z)$.

Keywords: Complex polynomials $\cdot$ Analyticity of critical points $\cdot$
Sendov’s conjecture

MSC(2010): 32A10 $\cdot$ 30C10 $\cdot$ 30C15

##  1 Domains of analyticity

Let $\mathscr{P}_{n}^{c}$ be the set of complex polynomials of the form
$p(z)=\prod_{i=1}^{n}(z-z_{i})$. For given multiplicities
$\bar{\mu}:=(\mu_{1},\ldots,\mu_{m})$, $m\geq 1$, and
$\bar{\nu}:=(\nu_{1},\ldots,\nu_{k})$, $k\geq 1$, such that

$\sum_{i=1}^{m}\mu_{i}=n\quad\hbox{ and}\quad\sum_{i=1}^{k}\nu_{i}=m-1,$ (4)

let ${\mathbb{C}}^{n}(\bar{\mu},\bar{\nu})\subset{\mathbb{C}}^{n}$ be the set
consisting of all $\bar{z}=((z_{1},\mu_{1}),\ldots,(z_{m},\mu_{m}))$,
$z_{i}\neq z_{j}$, $1\leq i<j\leq m$, such that there exists a polynomial
$p\in\mathscr{P}_{n}^{c}$ satisfying

(i) $p(z)=p(\bar{z};z)=\prod_{i=1}^{m}(z-z_{i})^{\mu_{i}}$;

(ii) $p$ possesses exactly $k$ distinct critical points of the second kind
(that is, zeros of $p^{\prime}$ which are not zeros of $p$) with
multiplicities $\nu_{1},\nu_{2},\ldots,\nu_{k}$ and

$p^{\prime}(z)=n\prod_{i=1}^{m}(z-z_{i})^{\mu_{i}-1}\prod_{j=1}^{k}(z-\xi_{j})^{\nu_{j}}.$

The set of polynomials $p$ satisfying (i) and (ii) will be denoted by

$\mathscr{P}_{n}^{c}(\bar{\mu},\bar{\nu}):=\left\\{p(\bar{z};z)\in\mathscr{P}_{n}^{c}\leavevmode\nobreak\
|\leavevmode\nobreak\
\bar{z}\in{\mathbb{C}}^{n}(\bar{\mu},\bar{\nu})\right\\}.$

######  Theorem 1.

For a prescribed ordering $\alpha=(1,2,\ldots,m)$, the distinct zeros
$\\{z_{i}\\}_{i=1}^{m}$ and the distinct critical points of the second kind
$\\{\xi_{j}\\}_{j=1}^{k}$ of polynomials from
$\mathscr{P}_{n}^{c}(\bar{\mu},\bar{\nu})$ are analytic functions
$\\{z_{i}^{\alpha\beta}\\}_{i=1}^{m}$ and
$\\{\xi_{j}^{\alpha\beta}\\}_{j=1}^{k}$, respectively,
$\beta=(i_{1},i_{2},\ldots,i_{k+1})$, of any of the variables
$(z_{i_{1}},z_{i_{2}},\ldots,z_{i_{k+1}})$ in the domain

$\\{(z_{i_{1}},z_{i_{2}},\ldots,z_{i_{k+1}})\in{\mathbb{C}}^{k+1}\leavevmode\nobreak\
|\leavevmode\nobreak\ \bar{z}\in{\mathbb{C}}_{n}(\bar{\mu},\bar{\nu})\\},$

being also continuous on its boundary.

The proof of Theorem 1 is entirely based on the following lemma.

######  Lemma 2.

Let there be given multiplicities $(\bar{\mu},\bar{\nu})$ satisfying (4) with
$m>1$, and let a polynomial $p$ with zeros $\\{(z_{i},\mu_{i})\\}_{i=1}^{m}$
belong to $\mathscr{P}_{n}^{c}(\bar{\mu},\bar{\nu})$. Then, the distinct
critical points of the second kind $\\{\xi_{j}\\}_{j=1}^{k}$ and the first
$m-k-1$ zeros $z_{1},z_{2},\ldots,z_{m-k-1}$, are (locally) analytic functions
of the remaining ones $z_{m-k},z_{m-k+1},\ldots,z_{m}$.

###### Proof.

Let $p_{0}(\bar{z}^{0};z)\in\mathscr{P}_{n}^{c}(\bar{\mu},\bar{\nu})$. Set
$s:=m-1-k$. Clearly, $s\geq 0$ (with equality only when
$\nu_{j}=1,\leavevmode\nobreak\ j=1,2,\ldots,k$). Let us consider the
following system of equations

$p^{(\ell)}(\xi_{j})=0,\quad j=1,2,\ldots,k;\leavevmode\nobreak\
\ell=1,2,\ldots,\nu_{j},$ (5)

for $p=p_{0}(\bar{z}^{0};z)$. The proof of the lemma is based on the system
(5) and the Implicit Mapping Theorem (see, e.g., [2, p. 28]. We need to show
that there exist analytic functions $z_{1}=z_{1}(z_{s+1},\ldots
z_{m}),\ldots,z_{s}=z_{s}(z_{s+1},\ldots z_{m})$ and
$\xi_{1}=\xi_{1}(z_{s+1},\ldots z_{m}),\ldots,\xi_{k}=\xi_{k}(z_{s+1},\ldots
z_{m})$, satisfying (5) in an open neighbourhood of
$(z^{0}_{s+1},\ldots,z^{0}_{m})$, or in other words, that the system of $m-1$
equations (5) can be locally and analytically solved with respect to the $m-1$
functions $\\{z_{i}\\}_{i=1}^{s}$, $\\{\xi_{j}\\}_{j=1}^{k}$, or equivalently,
that the Jacobian matrix $J$ of (5) possesses the maximal rank. The Jacobian
matrix of (5) (we omit for simplicity the upper index 0) is
$J=\hbox{diag\,}\\{p^{\prime\prime}(\xi_{1}),\ldots,p^{\prime\prime}(\xi_{k})\\}$
if $s=0$, and J=[
Ω_1’(ξ_1)Ω_1’’(ξ_1)…Ω_1^(ν_1)(ξ_1)…Ω_1’(ξ_k)Ω_1’’(ξ_k)…Ω_1^(ν_k)(ξ_k)⋮⋯⋮⋮⋯⋮⋯⋮⋮Ω_s’(ξ_1)Ω_s’’(ξ_1)…Ω_s^(ν_1)(ξ_1)…Ω_s’(ξ_k)Ω_s’’(ξ_k)…Ω_s^(ν_k)(ξ_k)0…0p^(ν_1+1)(ξ_1)…0…000…00…0…00⋮⋯⋮⋮⋯⋮⋯⋮⋮0…00…0…000…00…0…0p^(ν_k+1)(ξ_k)
]^T, where $\Omega_{i}(z)=-\frac{\mu_{i}p(z)}{z-z_{i}},\leavevmode\nobreak\
i=1,2,\ldots,s$, if $s\geq 1$. We need to prove that $\hbox{rank}\,J=m-1$. If
$s=0$, this is a direct consequence of $p^{\prime\prime}(\xi_{j})\neq 0$,
$j=1,2,\ldots,k$. Let $s\geq 1$ and let us assume the contrary, that is,
$\hbox{rank}\,J<m-1$. Using that $p^{(\nu_{j}+1)}(\xi_{j})\neq 0$,
$j=1,2,\ldots,k$, our assumption implies the existence of a non-zero vector
$(\beta_{1},\beta_{2},\ldots,\beta_{s})\in{\mathbb{C}}^{s}$ such that the
polynomial $\Omega\in\mathcal{P}_{n-1}^{c}$ (the set of all complex
polynomials of degree at most $n-1$),

$\Omega(z):=-{\beta_{1}}{\mu_{1}^{-1}}\Omega_{1}(z)-{\beta_{2}}{\mu_{2}^{-1}}\Omega_{2}(z)-\cdots-{\beta_{s}}{\mu_{s}^{-1}}\Omega_{s}(z)=\left(\sum_{i=1}^{s}\frac{\beta_{i}}{z-z_{i}}\right)p(z),$

satisfies

$\Omega^{(\ell)}(\xi_{j})=\left(\sum_{i=1}^{s}\frac{\beta_{i}}{z-z_{i}}\right)_{\big{|}z=\xi_{j}}^{(\ell)}p(\xi_{j})=0,\quad
j=1,2,\ldots,k;\leavevmode\nobreak\ \ell=1,2,\ldots,\nu_{j}-1.$ (6)

Denote

$\omega(z):=\prod_{i=1}^{s}(z-z_{i}),\quad\omega_{i}(z):=\frac{\omega(z)}{z-z_{i}},\leavevmode\nobreak\
i=1,2,\ldots,s,$

and

$q(z):=\prod_{j=1}^{k}(z-\xi_{j})^{\nu_{j}-1}.$

Clearly, $q(z)\in\mathscr{P}_{s}^{c}$ since
$\sum_{j=1}^{k}(\nu_{j}-1)=m-1-k=s$. Using that $z_{i}\neq\xi_{j}$, it easily
follows from (6) that there exists a vector
$(\alpha_{1},\alpha_{2},\ldots,\alpha_{s})\in{\mathbb{C}}^{s}$ such that

$q(z)\sum_{i=1}^{s}\alpha_{i}\omega_{i}(z)+\sum_{i=1}^{s}\beta_{i}\omega_{i}^{2}(z)\equiv
0.$ (7)

If $\beta_{i}\neq 0$, $i=1,2,\ldots,\tilde{s}$, and $\beta_{i}=0$,
$i=\tilde{s}+1,\tilde{s}+2,\ldots,s$, $1\leq\tilde{s}<s$, then we rewrite (7)
in this way

$q_{1}(z)q_{2}(z)\frac{\sum_{i=1}^{s}\alpha_{i}\omega_{i}(z)}{\prod_{i=\tilde{s}+1}^{s}(z-z_{i})^{2}}+\sum_{i=1}^{\tilde{s}}\beta_{i}\tilde{\omega}_{i}^{2}(z)\equiv
0,$

where $q_{1}(z)\in\mathscr{P}_{\tilde{s}}^{c}$,
$q_{2}(z)\sum_{i=1}^{s}\alpha_{i}\omega_{i}(z)/\prod_{i=\tilde{s}+1}^{s}(z-z_{i})^{2}\in\mathcal{P}_{\tilde{s}-1}^{c}$,
$\tilde{\omega}_{i}(z)$ $:=\prod_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{\tilde{s}}(z-z_{i})$, and arrive at a similar equation with
$s$ replaced by $\tilde{s}$

$q_{1}(z)\sum_{i=1}^{\tilde{s}}\tilde{\alpha}_{i}\tilde{\omega}_{i}(z)+\sum_{i=1}^{\tilde{s}}\beta_{i}\tilde{\omega}_{i}^{2}(z)\equiv
0.$

Therefore, without loss of generality, we can and will assume that
$\beta_{i}\neq 0$, $i=1,2,\ldots,s$. Setting in (7) $z=z_{i}$,
$i=1,2,\ldots,s$, we get

$\beta_{i}=-\alpha_{i}q(z_{i})[\omega_{i}(z_{i})]^{-1},\quad i=1,2,\ldots,s,$

and

$q(z)\sum_{i=1}^{s}\alpha_{i}\omega_{i}(z)-\sum_{i=1}^{s}\alpha_{i}q(z_{i})[\omega_{i}(z_{i})]^{-1}\omega_{i}^{2}(z)\equiv
0.$ (8)

It follows from (8) that

$\sum_{i=1}^{s}\alpha_{i}=0$ (9)

and

$q(z_{i})\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{s}\alpha_{j}\omega_{j}^{\prime}(z_{i})+\alpha_{i}[q^{\prime}(z_{i})\omega_{i}(z_{i})-q(z_{i})\omega_{i}^{\prime}(z_{i})]=0,\quad
i=1,2,\ldots,s.$ (10)

According to Lagrange interpolation formula

$q(z)=\sum_{i=1}^{s}q(z_{i})\frac{\omega_{i}(z)}{\omega_{i}(z_{i})}+\omega(z),$

and in addition, by (8),

$\omega(z)\sum_{i=1}^{s}\alpha_{i}\omega_{i}(z)+\sum_{i=1}^{s}\sum_{\begin{subarray}{c}j=1\\\
j\neq
i\end{subarray}}^{s}\left[\alpha_{i}\frac{q(z_{j})}{\omega_{j}(z_{j})}+\alpha_{j}\frac{q(z_{i})}{\omega_{i}(z_{i})}\right]\omega_{i}(z)\omega_{j}(z)\equiv
0.$ (11)

Dividing (11) by $\omega(z)$ and setting $z=z_{i}$, $i=1,2,\ldots,s$, give

$\alpha_{i}\left[1+\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{s}\frac{q(z_{j})}{\omega_{j}(z_{j})(z_{i}-z_{j})}\right]+\frac{q(z_{i})}{\omega_{i}(z_{i})}\sum_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{s}\frac{\alpha_{j}}{z_{i}-z_{j}}=0,\quad
i=1,2,\ldots,s.$ (12)

The first sum in (12) will be calculated from the following equation, using
the properties of the divided difference

$\displaystyle 1$ $\displaystyle=$ $\displaystyle
q[z_{1},\ldots,z_{i-1},z_{i},z_{i},z_{i+1},\ldots,z_{s}]$ $\displaystyle=$
$\displaystyle-\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{s}\frac{q(z_{j})}{\omega_{j}(z_{j})(z_{i}-z_{j})}+\frac{q^{\prime}(z_{i})}{\omega_{i}(z_{i})}+\frac{q(z_{i})}{\omega_{i}(z_{i})}\cdot\frac{\omega_{i}^{\prime}(z_{i})}{\omega_{i}(z_{i})},$

or more precisely,

$\alpha_{i}\left[q^{\prime}(z_{i})+q(z_{i})\cdot\frac{\omega_{i}^{\prime}(z_{i})}{\omega_{i}(z_{i})}\right]+q(z_{i})\sum_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{s}\frac{\alpha_{j}}{z_{i}-z_{j}}=0,\quad
i=1,2,\ldots,s.$ (13)

Finally, we get from (10) and (13)

$2\alpha_{i}q(z_{i})\omega_{i}^{\prime}(z_{i})=\alpha_{i}q(z_{i})\omega^{\prime\prime}(z_{i})=0,\quad
i=1,2,\ldots,s.$

Since $\alpha_{i}q(z_{i})\neq 0$, $i=1,2,\ldots,s$, this means that
$\omega\in\mathscr{P}_{1}^{c}$, that is, $s=1$, and by (9),
$\alpha_{1}=\beta_{1}=0$. This is a contradiction to our assumption that
$\hbox{rank}\,J<m-1$ and hence, $\hbox{rank}\,J=m-1$. The lemma is proved. ∎

##  2 Sendov’s conjecture

Sendov’s conjecture is one of the fundamental problems in the theory of
complex polynomials. It was announced back in 1958 by Bulgarian mathematicians
Blagovest Sendov and Lyubomir Iliev (see [4] for the history of the problem
and for references before 2001). Despite the significant analytical and
computational efforts within the last more than 60 years, there has not been
yet a definitive proof of its validity. Here we show that it is an almost
direct consequence of Theorem 1.

Let $D:=\\{z\in{\mathbb{C}}\,|\,|z|\leq 1\\}$ be the closed unit disk in
${\mathbb{C}}$. Sendov’s conjecture states:

Conjecture 1. If $n\geq 2$ and $p(z)$ is a polynomial from
$\mathscr{P}_{n}^{c}$ such that $\\{z_{i}\\}_{i=1}^{n}\subset D$, then for
every $i=1,2,\ldots n$, the disk $\\{z\in{\mathbb{C}}\,|\,|z_{i}-z|\leq 1\\}$
contains at least one zero of $p^{\prime}(z)$.

Set $\bar{z}:=(z_{1},z_{2},\ldots,z_{n})$. If
$p^{\prime}(z)=n\prod_{j=1}^{n-1}(z-\zeta_{j})$, then the statement of
Conjecture 1 is equivalent to

$\max_{\bar{z}\in D^{n}}\max_{1\leq i\leq n}\min_{1\leq j\leq
n-1}|z_{i}-\zeta_{j}|=1.$

In what follows, the zeros of $p$ will also be represented in the (already
familiar) form $\\{(z_{i},\mu_{i})\\}_{i=1}^{m}$ using for simplicity the same
letters. Let

${\mathbb{C}}^{n}(m,k):=\cup\left\\{{\mathbb{C}}^{n}(\bar{\mu}^{\prime},\bar{\nu}^{\prime})\leavevmode\nobreak\
|\leavevmode\nobreak\ m^{\prime}=m,\leavevmode\nobreak\
k^{\prime}=k\right\\}.$

######  Remark 1.

Taking Theorem 1 into account, it follows that, up to the ordering
$\alpha=(1,2,\ldots,m)$ of the variables, there exist unique functions
$\\{z^{\alpha}_{i}\\}_{i=1}^{m}$ and $\\{\xi^{\alpha}_{j}\\}_{j=1}^{k}$ of
$\\{z_{i}\\}_{i=1}^{k+1}$, analytic on ${\mathbb{C}}^{n}(m,k)$, which
naturally coincide into new functions on
${\mathbb{C}}^{n}(m^{\prime},k^{\prime})$, $m^{\prime}\leq m$, $k^{\prime}<k$,
when some of the variables (zeros of $p$) and (or) some of the functions
$\\{\xi^{\alpha}_{j}\\}_{j=1}^{k}$ (critical points of the second kind of $p$)
overlap. Moreover, $\\{z^{\alpha}_{i}\\}_{i=1}^{m}$ and
$\\{\xi^{\alpha}_{j}\\}_{j=1}^{k}$ are continuous on its boundary

$\partial\,{\mathbb{C}}^{n}(m,k)={\mathbb{C}}^{n}(m-1,k-1)\cup{\mathbb{C}}^{n}(m,k-1),$

$2\leq m\leq n,\leavevmode\nobreak\ 2\leq k\leq m-1$.

Proof of Conjecture 1. Let $\bar{z}\in{\mathbb{C}}^{n}(m,k)$. Define the
functions

$S(\bar{z}):=\max_{1\leq i\leq n}\min_{1\leq j\leq n-1}|z_{i}-\zeta_{j}|$ (14)

and

$S_{\ell}:=\min_{1\leq j\leq k}|z_{\ell}-\xi_{j}|$ (15)

for all $1\leq\ell\leq m$ such that $\mu_{\ell}=1$. We will prove the
following enhancement of the conjecture under consideration:

######  Theorem 3.

If $\bar{z}\in D^{m}$ and $m\geq 2$, then we have

$\min_{1\leq j\leq k}|z_{\ell}-\xi_{j}|\leq 1,$

for any $z_{\ell}$, $\mu_{\ell}=1$, with equality if and only if $m=n$, $k=1$
and $\\{z_{i}\\}_{i=1}^{n}$ coincide with the roots of unity
$\\{e^{\frac{2(i-1)\pi\mathsf{i}}{n}}\\}_{i=1}^{n}$.

Proof. Let us show first that the proof can be reduced to the case $k=1$. Let
$k\geq 2$, $\bar{z}\in C^{n}(m,k)$ and $|z_{\ell}|<1$. Denote by
$\hbox{rad}_{c}(A)$ the radius of the circumself disk of a set of points $A$
(the smallest closed disk containing $A$). Let $\Phi$ be the map from Theorem
1 and consider all sufficiently small local paths
$\bar{z}(t),\leavevmode\nobreak\ t\in[0,t_{0})$ such that
$z_{\ell}(t)\in\hbox{int}(D),\leavevmode\nobreak\ t\in[0,t_{0})$. For each
such path we take the configuration $\Phi(\bar{z}(t))$ and consider the points
$\Phi(\bar{z}(t))/\hbox{rad}_{c}(t)\subset D^{m+k}$. All these points
constitute a set $V_{1}\times\ldots\times V_{m}\times W_{1}\times\ldots\times
W_{k}\subset D^{m+k}$ such that $V_{\ell}$ and $W_{1},\ldots,W_{k}$ are open
neighbourhoods of $z_{\ell}$ and $\\{\xi_{j}\\}_{j=1}^{k}$, respectively. This
means that we can move the points $z_{\ell},\xi_{1},\xi_{2},\ldots,\xi_{k}$ so
that to increase $S_{\ell}$ and $\bar{z}$ to remain in
${\mathbb{C}}^{n}(m,k)\cap D^{m}$. Therefore, the maximum point of $S_{\ell}$
is located on $\partial({\mathbb{C}}^{n}(m,k))\cap D^{m}$. Now, all we need to
do next is to consider the case $k=1$.

_The case $\mathbf{{k=1}}$._ Let $(\bar{\mu},\bar{\nu})$ be such that $k=1$
and $\nu_{1}=m-1$, respectively. Let $p(z)=\prod_{i=1}^{m}(z-z_{i})^{\mu_{i}}$
and $p^{\prime}(z)=n(z-\xi_{1})^{m-1}\prod_{i=1}^{m}(z-z_{i})^{\mu_{i}-1}$.
Then, we have consecutively

$\frac{p^{\prime}(z)}{p(z)}=\frac{n(z-\xi_{1})^{m-1}}{\prod_{i=1}^{m}(z-z_{i})}=\sum_{i=1}^{m}\frac{\mu_{i}}{z-z_{i}},$
$(z-\xi_{1})^{m-1}=\frac{1}{n}\sum_{i=1}^{m}\mu_{i}\omega_{i}(z),\quad\omega_{i}(z)=\prod_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{m}(z-z_{j}),$
$\xi:=\xi_{1}=\sum_{i=1}^{m}\frac{\tilde{\mu}_{i}}{n}z_{i},\quad\tilde{\mu}_{i}:=\frac{n-\mu_{i}}{m-1},\leavevmode\nobreak\
i=1,2,\ldots,m.$

We have to prove that $|z_{\ell}-\xi|\leq 1$ for all $z_{\ell}$ such that
$\mu_{\ell}=1$. Let

$|z_{i_{0}}-\xi|=\max_{\mu_{\ell}=1}|z_{\ell}-\xi|,\leavevmode\nobreak\
\hbox{for some}\leavevmode\nobreak\ z_{i_{0}},\leavevmode\nobreak\
|z_{i_{0}}|<1.$

Without loss of generality, we will assume that $\hbox{rad}_{c}(\bar{z})=1$.
Let also $m\geq 9$ (Conjecture 1 is proved for polynomials with $m\leq 8$
[1]). Denote

$\xi=:a+\mathsf{i}b,\leavevmode\nobreak\
z_{i}=:a_{i}+\mathsf{i}b_{i},\leavevmode\nobreak\ \xi-
z_{i}=:c_{i}e^{\mathsf{i}\theta_{i}},\leavevmode\nobreak\
c_{i}>0,\leavevmode\nobreak\ \theta_{i}\in[0,2\pi),$

for $i=1,2,\ldots,m$, and $c:=\prod_{i=1}^{m}c_{i}$,
$\theta:=\sum_{i=1}^{m}\theta_{i}$. By means of Kuhn-Tucker necessary
conditions, we will investigate the extremal points of the problem

$F_{0}\rightarrow\max,\quad f(z_{1},z_{2},\ldots,z_{m};z)\equiv
0,\leavevmode\nobreak\ a_{i}^{2}+b_{i}^{2}\leq 1,\leavevmode\nobreak\
i=1,2,\ldots,m,$ (16)

where

$F_{0}:=F_{0}(z_{1},z_{2},\ldots,z_{m}):=(a-a_{i_{0}})^{2}+(b-b_{i_{0}})^{2},$

and

$f:=f(z):=f(z_{1},z_{2},\ldots,z_{m};z):=(z-\xi)^{m-1}-\frac{1}{n}\sum_{i=1}^{m}\mu_{i}\omega_{i}(z).$

To this aim, set

$F:=F(z):=F_{0}(z_{1},z_{2},\ldots,z_{m})-\lambda_{1}\Re f(z)-\lambda_{2}\Im
f(z)-\sum_{i=1}^{m}\eta_{i}(a_{i}^{2}+b_{i}^{2}-1),$

where $\eta_{i}\geq 0$ and $\eta_{i}(a_{i}^{2}+b_{i}^{2}-1)=0$,
$i=1,2,\ldots,m$, at the extremal points.

The construction of the function $F$ needs some additional comments. Formally,
we should define it by using $m$ different equality constraints, corresponding
to $m$ different arbitrary points $z$ in an open neighbourhood of $\xi$.
However, our calculations below implicitly use these constraints in taking the
partial derivatives of $F$ with respect to $a,\leavevmode\nobreak\ b$ and
$\\{a_{i},b_{i}\\}_{i=1}^{m}$ and setting $z=\xi$. This is justified by the
fact that the constraint functions (and so, the extremal points) are
continuous functions of $z$. Next, we calculate the corresponding partial
derivatives at $z=\xi$. First,

$\frac{\partial f}{\partial
a_{i}}=-\frac{\tilde{\mu}_{i}}{n}(m-1)(z-\xi)^{m-2}+\frac{1}{n}\sum_{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}^{m}\mu_{j}\omega_{ij}(z),\leavevmode\nobreak\
\omega_{ij}(z)=\frac{\omega_{i}(z)}{z-z_{j}},\leavevmode\nobreak\ i\neq j.$

From here,

$(z-z_{i})\frac{\partial f}{\partial
a_{i}}=-\frac{\tilde{\mu}_{i}}{n}(m-1)(z-\xi)^{m-2}(z-z_{i})+(z-\xi)^{m-1}-\frac{\mu_{i}}{n}\omega_{i}(z)$

and

$(\xi-z_{i})\frac{\partial f}{\partial
a_{i}}(\xi)=-\frac{\mu_{i}}{n}\omega_{i}(\xi).$

Consequently,

$\displaystyle c_{i}e^{\mathsf{i}\theta_{i}}\frac{\partial f}{\partial
a_{i}}(\xi)$ $\displaystyle=$
$\displaystyle-\frac{c\mu_{i}}{nc_{i}}e^{\mathsf{i}(\theta-\theta_{i})},\qquad\frac{\partial
f}{\partial
a_{i}}(\xi)=-\frac{c\mu_{i}}{nc_{i}^{2}}e^{\mathsf{i}(\theta-2\theta_{i})},$
$\displaystyle c_{i}e^{\mathsf{i}\theta_{i}}\frac{\partial f}{\partial
b_{i}}(\xi)$ $\displaystyle=$
$\displaystyle-\frac{c\mu_{i}}{nc_{i}}\mathsf{i}e^{\mathsf{i}(\theta-\theta_{i})},\qquad\frac{\partial
f}{\partial
b_{i}}(\xi)=-\frac{c\mu_{i}}{nc_{i}^{2}}\mathsf{i}e^{\mathsf{i}(\theta-2\theta_{i})},$

and

$\displaystyle\frac{\partial\Re f}{\partial a_{i}}(\xi)$ $\displaystyle=$
$\displaystyle-\frac{c\mu_{i}}{nc_{i}^{2}}\cos(\theta-2\theta_{i}),\qquad\frac{\partial\Re
f}{\partial b_{i}}(\xi)=+\frac{c\mu_{i}}{nc_{i}^{2}}\sin(\theta-2\theta_{i})$
$\displaystyle\frac{\partial\Im f}{\partial a_{i}}(\xi)$ $\displaystyle=$
$\displaystyle-\frac{c\mu_{i}}{nc_{i}^{2}}\sin(\theta-2\theta_{i}),\qquad\frac{\partial\Im
f}{\partial b_{i}}(\xi)=-\frac{c\mu_{i}}{nc_{i}^{2}}\cos(\theta-2\theta_{i}).$

For the partial derivatives of $F_{0}$ with respect to $a_{i},b_{i}$, $i\neq
i_{0}$, we have

$\displaystyle\frac{\partial F_{0}}{\partial a_{i}}$ $\displaystyle=$
$\displaystyle\frac{2\tilde{\mu}_{i}}{n}(a-a_{i_{0}})=\frac{2\tilde{\mu}_{i}}{n}c_{i_{0}}\cos(\theta_{i_{0}}),$
$\displaystyle\frac{\partial F_{0}}{\partial b_{i}}$ $\displaystyle=$
$\displaystyle\frac{2\tilde{\mu}_{i}}{n}(b-b_{i_{0}})=\frac{2\tilde{\mu}_{i}}{n}c_{i_{0}}\sin(\theta_{i_{0}}),$

and, in addition,

$\displaystyle\frac{\partial F_{0}}{\partial a_{i_{0}}}$ $\displaystyle=$
$\displaystyle\frac{2\tilde{\mu}_{i_{0}}-2n}{n}c_{i_{0}}\cos(\theta_{i_{0}}),$
$\displaystyle\frac{\partial F_{0}}{\partial b_{i_{0}}}$ $\displaystyle=$
$\displaystyle\frac{2\tilde{\mu}_{i_{0}}-2n}{n}c_{i_{0}}\sin(\theta_{i_{0}}).$

Now, we are ready to write Kuhn-Tucker necessary conditions for a maximum of
$F_{0}$ at the points $\\{a_{i}+\mathsf{i}b_{i}\\}_{i=1}^{m}$ under the
conditions given in (16) for $z=\xi$ (for simplicity, we do not change the
notation for the points of maximum). More precisely, the following must be
fulfilled ∂F∂ai=2~μinci0cos(θi0)+cμinci2[+λ1cos(θ-2θi)+λ2sin(θ-2θi)]-2ηiai=0,
i≠i0,∂F∂bi=2~μinci0sin(θi0)+cμinci2[-λ1sin(θ-2θi)+λ2cos(θ-2θi)]-2ηibi=0,
i≠i0,∂F∂ai0=2~μi0-2nnci0cos(θi0)+cμi0nci02[+λ1cos(θ-2θi0)+λ2sin(θ-2θi0)]-2ηi0ai0=0,∂F∂bi0=2~μi0-2nnci0sin(θi0)+cμi0nci02[-λ1sin(θ-2θi0)+λ2cos(θ-2θi0)]-2ηi0bi0=0.
Using that $\lambda_{1}=\lambda\cos(\theta_{\lambda})$ and
$\lambda_{2}=\lambda\sin(\theta_{\lambda})$ for some $\lambda\geq 0$ and
$\theta_{\lambda}\in[0,2\pi)$, Equations (2) can be rewritten as follows

$\displaystyle
2\tilde{\mu}_{i}c_{i_{0}}\cos(\theta_{i_{0}})+\lambda\frac{c\mu_{i}}{c_{i}^{2}}\cos(\theta-2\theta_{i}-\theta_{\lambda})-2n\eta_{i}a_{i}=0,\quad
i\neq i_{0},$ $\displaystyle
2\tilde{\mu}_{i}c_{i_{0}}\sin(\theta_{i_{0}})-\lambda\frac{c\mu_{i}}{c_{i}^{2}}\sin(\theta-2\theta_{i}-\theta_{\lambda})-2n\eta_{i}b_{i}=0,\quad
i\neq i_{0},$
$\displaystyle(2\tilde{\mu}_{i_{0}}-2n)c_{i_{0}}\cos(\theta_{i_{0}})+\lambda\frac{c\mu_{i_{0}}}{c_{i_{0}}^{2}}\cos(\theta-2\theta_{i_{0}}-\theta_{\lambda})-2n\eta_{i_{0}}a_{i_{0}}=0,$
$\displaystyle(2\tilde{\mu}_{i_{0}}-2n)c_{i_{0}}\sin(\theta_{i_{0}})-\lambda\frac{c\mu_{i_{0}}}{c_{i_{0}}^{2}}\sin(\theta-2\theta_{i_{0}}-\theta_{\lambda})-2n\eta_{i_{0}}b_{i_{0}}=0.$

and

$\displaystyle
2\tilde{\mu}_{i}(\bar{\xi}-\bar{z}_{i_{0}})+\lambda\frac{c\mu_{i}}{c_{i}^{2}}e^{\mathsf{i}(\theta-2\theta_{i}-\theta_{\lambda})}-2n\eta_{i}\bar{z}_{i}=0,\quad
i\neq i_{0},$
$\displaystyle(2\tilde{\mu}_{i_{0}}-2n)(\bar{\xi}-\bar{z}_{i_{0}})+\lambda\frac{c\mu_{i_{0}}}{c_{i_{0}}^{2}}e^{\mathsf{i}(\theta-2\theta_{i_{0}}-\theta_{\lambda})}-2n\eta_{i_{0}}\bar{z}_{i_{0}}=0,$

from where

$\displaystyle\lambda
e^{-\mathsf{i}\theta_{\lambda}}\frac{\prod_{j=1}^{m}(\xi-z_{j})}{(\xi-
z_{i})^{2}}+\frac{2\tilde{\mu}_{i}}{\mu_{i}}(\bar{\xi}-\bar{z}_{i_{0}})-2n\frac{\eta_{i}}{\mu_{i}}\bar{z}_{i}=0,\quad
i\neq i_{0},$ (17) $\displaystyle\lambda
e^{-\mathsf{i}\theta_{\lambda}}\frac{\prod_{j=1}^{m}(\xi-z_{j})}{(\xi-
z_{i_{0}})^{2}}+\frac{2\tilde{\mu}_{i_{0}}-2n}{\mu_{i_{0}}}(\bar{\xi}-\bar{z}_{i_{0}})-2n\frac{\eta_{i_{0}}}{\mu_{i_{0}}}\bar{z}_{i_{0}}=0.$
(18)

Equations (17) and (18) yield

$\displaystyle(\xi-
z_{i})^{2}\left[\frac{\tilde{\mu}_{i}}{\mu_{i}}(\bar{\xi}-\bar{z}_{i_{0}})-n\frac{\eta_{i}}{\mu_{i}}\bar{z}_{i}\right]$
$\displaystyle=$ (19) $\displaystyle(\tilde{\mu}_{i_{0}}-n)(\xi-
z_{i_{0}})^{2}(\bar{\xi}-\bar{z}_{i_{0}})$
$\displaystyle=-\frac{\lambda}{2}e^{-\mathsf{i}\theta_{\lambda}}\prod_{j=1}^{m}(\xi-
z_{j}),\leavevmode\nobreak\ i\neq i_{0},$

since $\mu_{i_{0}}=1$ and $\eta_{i_{0}}=0$. Remind that $|z_{i_{0}}|<1$ and

$\tilde{\mu}_{i_{0}}=\frac{n-1}{m-1},\leavevmode\nobreak\ \leavevmode\nobreak\
\tilde{\mu}_{i}=\frac{n-\mu_{i}}{m-1},\leavevmode\nobreak\ i\neq i_{0},$
$\tilde{\mu}_{i_{0}}-n=\frac{n-1-(m-1)n}{(m-1)}<0,\leavevmode\nobreak\
\leavevmode\nobreak\
\frac{\tilde{\mu}_{i}}{\mu_{i}}=\frac{n-\mu_{i}}{(m-1)\mu_{i}},\leavevmode\nobreak\
i\neq i_{0}.$

Let there exist another zero $z_{i}$ with $|z_{i}|<1$ and $\eta_{i}=0$. Then,
(19) implies for $m\geq 4$

$\frac{|\xi-z_{i_{0}}|^{2}}{|\xi-
z_{i}|^{2}}=\frac{n-\mu_{i}}{\mu_{i}}\cdot\frac{1}{(m-1)n-(n-1)}<\frac{1}{2\mu_{i}}.$

If $\mu_{i}=1$, this is a contradiction to our assumption that $|\xi-
z_{i_{0}}|=\max_{\\{i\,|\,\mu_{i}=1\\}}$ $|\xi-z_{i}|$. If $\mu_{i}>1$, then

$|\xi-z_{i_{0}}|<1.$

Accordingly, it is sufficient to consider the case $|z_{i}|=1$ and
$\eta_{i}>0$, $i\neq i_{0}$. Let $z_{i}:=e^{\mathsf{i}\gamma_{i}}$,
$i=1,2,\ldots,m$, $i\neq i_{0}$. By using an appropriate rotation with center
0, we can and will suppose that $\Im(\xi-z_{i_{0}})=0$ and $\xi-z_{i_{0}}<0$.
Take an arbitrary $1\leq i\leq m$, $i\neq i_{0}$. Then, it follows from (19)
that 0 lies in the interior of the triangle with vertices 1, $\psi_{1}:=(\xi-
z_{i})^{2}=c_{i}^{2}e^{\mathsf{i}2\theta_{i}}$ and $\psi_{2}:=(\xi-
z_{i})^{2}\bar{z}_{i}=c_{i}^{2}e^{\mathsf{i}(2\theta_{i}-\gamma_{i})}$, and
thus,

$\Im\psi_{1}\Im\psi_{2}<0.$ (20)

Further, if $l\,:\,\Im z=\alpha\Re z+\beta$ is the line passing through
$\psi_{1}$ and $\psi_{2}$, and $\psi$ is the intersection point of $l$ with
the real axis, then

$\psi=-\frac{\beta}{\alpha}=\frac{\Im\psi_{2}\Re\psi_{1}-\Im\psi_{1}\Re\psi_{2}}{\Im\psi_{2}-\Im\psi_{1}}<0,$

or equivalently,

$\Re\psi_{1}<\frac{\Im\psi_{1}}{\Im\psi_{2}}\Re\psi_{2}.$ (21)

Clearly, inequalities (20) and (21) are equivalent to

$\displaystyle\sin(2\theta_{i})$
$\displaystyle\sin(2\theta_{i}-\gamma_{i})<0,$ (22)
$\displaystyle\cos(2\theta_{i})$
$\displaystyle<\frac{\sin(2\theta_{i})}{\sin(2\theta_{i}-\gamma_{i})}\cos(2\theta_{i}-\gamma_{i}).$

In view of inequalities (22), we have either $\theta_{i}\in(\pi/2,\pi)$ and
$\gamma_{i}\in(0,\pi)$ (if $\sin(2\theta_{i})<0$ and $\sin(\gamma_{i})>0$) or
$\theta_{i}\in(\pi,3\pi/2)$ and $\gamma_{i}\in(\pi,2\pi)$ (if
$\sin(2\theta_{i})>0$ and $\sin(\gamma_{i})<0$). In both cases the points
$\xi$, $z_{i}$ and $\xi-z_{i}$ lie in the same open half-plane with respect to
the real axis, for any $i=1,2,\ldots,m,\leavevmode\nobreak\ i\neq i_{0}$.
Since $|z_{i_{0}}|<1$, this implies that $\hbox{rad}_{c}(\bar{z})<1$, which is
a contradiction. Consequently, the maximum of $|z_{i_{0}}-\xi|$ is attained
when all the points $z_{i},\leavevmode\nobreak\ i=1,2,\ldots,m,$ lie on the
unit circle $\partial D$. Applying [3, Theorem 1] to $z_{i_{0}}$, it follows
that $\xi=0$ and the maximum is equal to 1. Finally, using again [3, Theorem
1], we conclude that this can happen only if $m=n$, $k=1$ and $p(z)=z^{n}-1$.
Theorem 3 is proved. $\Box$

## References

  * [1] J. E. Brown and G. Xiang, On the Sendov’s conjecture for polynomials of degree at most eight, J. Math. Anal. Appl., 252, pp. 272–292, 1999.
  * [2] L. Kaup and B. Kaup, Holomorphic functions of several variables, Walter de Gruyter, Berlin, 1983.
  * [3] Z. Rubinstein, On a problem of Ilyeff, Pacific J. Math., 26, pp. 159–161, 1968.
  * [4] Bl. Sendov, Hausdorff geometry of polynomials, East J. Approx., 7, pp. 123–178, 2001.


# Recency Ranking by Diversification of Result Set

Andrey Styskin  Fedor Romanenko  Fedor Vorobyev  Pavel Serdyukov

Search Quality Group, Yandex  119021, Leo Tolstoy 16  Moscow, Russia
{styskin, fedor, melton<EMAIL_ADDRESS>
(2011)

###### Abstract

In this paper, we propose a web search retrieval approach which automatically
detects recency sensitive queries and increases the freshness of the ordinary
document ranking by a degree proportional to the probability of the need in
recent content. We propose to solve the recency ranking problem by using
result diversification principles and deal with the query’s non-topical
ambiguity appearing when the need in recent content can be detected only with
uncertainty. Our offline and online experiments with millions of queries from
real search engine users demonstrate the significant increase in satisfaction
of users presented with a search result generated by our approach.

††conference: CIKM’11, October 24–28, 2011, Glasgow, Scotland, UK.

Categories and Subject Descriptors:
H.3 [Information Storage and Retrieval]: H.3.3 Information Search and
Retrieval.

General Terms:
Algorithms, Measurement, Performance, Experimentation.

Keywords:
Recency ranking, diversity, web search.

##  1 Introduction

Modern web search engines face the need to consider different non-topical
facets of relevance when ranking web documents in response to user queries.
While the need in a certain document feature, besides the topical relevance,
might be expressed only implicitly in the query, it is still important to
recognize its presence in order to adequately satisfy the underlying
information need. However, the quality of such recognition cannot be perfect
in all cases. Consequently, it brings a certain level of non-topical ambiguity
to the queries, which must be taken into account when generating a search
result.

One of the most popular non-topical facets of relevance is document freshness.
In this paper, we demonstrate how to deal with query ambiguity surrounding the
need for recent information. Such ambiguity typically appears during short
periods of time, when users become increasingly interested in one newsworthy
aspect, typically an event, related to a well-known entity: a person (e.g.
[Michael Jackson]) or a location (e.g. [Japan]). For example, consider the
query [michael jackson]. There has been constant and continuing interest in
the biography and discography of Michael Jackson, which can be satisfied even
by non-fresh documents, but users issuing the query [michael jackson] on (June
25, 2009) were often looking for the freshest news related to the Michael
Jackson’s death. But both intents (news and discography) continued even during
this period.

Recently, a number of techniques for search result diversification has been
proposed in order to compensate for topical ambiguity of queries and increase
the chance to satisfy the user. We propose to follow the same principles to
deal with recency sensitive queries and their non-topical ambiguity. Our
approach aims to maximize the probability that the average user finds some
useful information among the search results on recency sensitive queries by
blending necessary amount of recent results into the result set. To the best
of our knowledge, our paper describes the first attempt to tackle the problem
of non-topical query ambiguity with a result set diversification technique.

The main contributions of this paper include: 1) the approach to recency
ranking by means of search result set diversification, 2) a thorough offline
and online evaluation of the proposed approach in terms of a search result
quality metric and the overall user satisfaction.

The remainder of the paper is organized as follows. We first review the
related work in Section 2. Section 3 describes our machine learning based
approach to obtaining a smooth probability of the need in recent content for a
query. Section 4 explains how we utilize that probability to diversify
ordinary document rankings with fresh documents. Section 5 presents the
results of evaluation and Section 6 concludes the paper and outlines the
research questions left for future work.

##  2 RELATED WORK

There are only a few papers focused exclusively on recency ranking. The
pioneering work in this area proposed to learn a ranking function which is
trained using a subset of features that help to infer the recency of page
content [3]. The follow-up work extended that subset to include features
extracted from the micro-blogging data stream [4]. Our approach differs in a
number of aspects. For one, we try to deal with temporal ambiguity of queries
and balance the number of fresh and ordinary relevant documents in the result
set, based on the smooth probability of the need in recent content. As a
result, while the aforementioned works focus entirely on improving the ranking
for one specific case (breaking news queries, 1-2% of search engine’s
traffic), we aim to affect the ordinary ranking by explicitly increasing its
freshness for any query with non-zero probability of the need in recent
content. The inference of query’s recency sensitivity plays an important role
in recency ranking. The aforementioned works detected only highly recency
sensitive queries using a linear combination of a few features. In a similar
way, Arguello et. al. [5] used a number of features to find verticals relevant
for a query, including the News vertical. While those methods focused on
binary classification of a query, our work is rather based on regression to
obtain and utilize the precise estimate of the probability of the need in
recent content.

Our work is also largely based on the principles of search result
diversification. In [2], a framework for evaluation that systematically
rewards diversity was proposed. In [1], a systematic approach to diversifying
results that aims to minimize the risk of dissatisfaction of the average user
was presented. A number of follow-up papers were published recently which we
do not cover here due to space constraints. Our work complements the research
in this area by demonstrating that diversification principles and algorithms
are also helpful to increase the chance to satisfy the user in the presence of
non-topical query ambiguity.

##  3 RECENCY SENSITIVE QUERY
CLASSIFICATION

In order to quantify the ambiguity of a recency sensitive query, we learned a
regression model which predicted the level of interest in recent documents for
a particular query and a particular time slot. We used around 30 different
features (including their minor modifications) previously described in the
papers dealing with similar problems (see Section 2). We do not provide a
thorough analysis of feature importance due to space constraints. The most
valuable features were the probabilities of queries to be generated by
language models of recent content from different sources, including the query,
social and news data streams, as well as the probability of a click on a news
item.

To train the regression model we asked annotators to provide labels of recency
sensitivity for a set of queries. In order to preselect a list of candidate
queries for assessment, we defined a small threshold on each feature used to
learn our regression function and filtered out all queries that did not have
at least one feature value exceeding the corresponding threshold. As a result,
we collected judgments for a set of 4000 unique queries issued to Yandex
(www.yandex.ru) web search engine (the major russian search engine) over the
period of three weeks. On each day during this period, judges were presented
with the queries submitted by search engine users on that particular day and
were asked to determine whether these queries express an interest in upcoming
or ongoing events for which web search users would prefer recent content.
Labeling queries basically represented the manual assignment of the
probabilities that a particular query is recency sensitive. So, if a query was
strictly about a recent event it received the probability of 0.95 (e.g. [flood
in thailand] on the day of the event). If a query’s primary interest was
related to a recent event, but many users would also like to see just
topically relevant results, it was labeled with 0.75 (e.g. the query [oscar]
on the day of the ceremony). If the query’s primary interest was not likely to
be focused on a particular event, but there was some chance that users issuing
such a query would look for some fresh content, assessors assigned the
probability of 0.25 (e.g. it always makes sense to present users with some
recent content in response to the query [britney spears]). Otherwise, a query
was assigned zero probability to be recency sensitive. Each query was labeled
by 3 assessors. Average Cohen’s kappa coefficient between all pairs of
assessors was 0.76, which is considered a substantial agreement.

We learned the regression model to assign smooth probability of the need in
fresh content to any query using Gradient Boosted Regression Trees (GDBT) [8].
Recency sensitive queries traffic coverage by these types based on 4000 human
made judgments is illustrated on Figure 1.

$0.25$$0.75$$0.95$$2$$4$$4.9$$1.11$$0.73$Probability of recency sensitivity%
search traffic Figure 1:  Recency sensitive queries traffic coverage

##  4 Diversification of the search
result with fresh documents

###  4.1 Diversification method

To produce a search result for recency sensitive queries we follow the search
result set diversification principles. Namely, we aim to maximize the utility
of the diversified search result expressed in terms of the Expected Reciprocal
Rank measure, which we extended to include an abandonment probability and to
handle multiple query intents. Both extensions are proposed by Chapelle et.
al. [9] and we combine both of them in this work. We call this metric Intent
Aware Expected Reciprocal Rank with Abandonment (ERR-IAA) and regard as the
objective we aim to maximize:

$\text{ERR-
IAA}=\sum^{r}_{i=1}{pBreak^{r}*\sum_{t}{P(t|q)*\prod^{r-1}_{i=1}{(1-R^{t}_{i})}*R^{t}_{r}}},$
(1)

where $P(t|q)$ is taken from the distribution over two classes of information
needs $t$ (the need in fresh topically relevant documents and the need in any
topically relevant documents) for the given query $q$. Each document is
assigned the probability $R^{t}_{r}$ to satisfy the information need of type
$t$ at position $r$. We take into account the probability that the documents
at the previous $r-1$ positions have not satisfied that need. We also assume
that any user always may stop (abandon the search result) at rank $r$ with the
abandonment probability $pBreak^{r}$ due to accumulated frustration ($pBreak$
is empirically set to 0.85 in our experiments).

We assume that the optimal search result page is the one which maximizes the
ERR-IAA measure. In order to maximize it, we follow the greedy approach
described by Agrawal et. al. [1] and select the document, whose selection
leads to the maximum increase of the objective at each step of the selection
process.

###  4.2 Aggregation of ordinary and fresh results

We also assume that any web document is fresh only for 3 days since the time
of its creation or the last update. We use a proprietary algorithm to extract
the correct and the most relevant timestamp from document content. Our choice
of the number of days is motivated by the following observations. First,
according to the studies by Dong et. al. [3], assessors, who judged the
freshness of a set of documents, found out that the 1–4 days old documents are
the ones most likely containing fresh content. Second, the peak of interest in
new events lasts for three days in average according to our analysis of
100,000 spiky and long-tail (so, previously unseen) queries submitted by users
of Yandex search engine in January, 2011. Figure 2 shows average share of
total query volume for each such a query per for each day since the 1st day
they become first known to the search engine until the 3rd day when their
popularity falls off almost completely.

$1$$2$$3$$0$$50$$100$73%20%4%Days% times Figure 2:  Cumulative share of query
instances submitted since the day of the first query

Guided by our definition of a fresh document, we produce the ranking of fresh
topically relevant documents by simply removing the outdated documents from
the initial ranking. As a result, we have two document rankings which we use
to maximize the ERR-IAA measure, described by Equation 1: the one containing
any topically relevant documents and the one containing only fresh topically
relevant documents.

However, in order to proceed with maximization of our objective, we still
needed to determine the probabilities of relevance $R^{t}_{i}$. In order to be
independent of specific retrieval scores, which may significantly vary over
queries and bear a relative, rather than absolute meaning, we turn document
ranks into their probabilities of relevance using the internal search engine’s
statistics about the probability to encounter a relevant document at the
specific position. So, since we fixed the probabilities of document relevance
for each of two aggregated rankings, the final ordering of documents depended
only on the probabilistic output of our classifier of query’s recency
sensitivity.

##  5 Experiments

###  5.1 Offline results

The research questions we aim to answer in this subsection are how our search
quality objective (ERR-IAA) changes while we aggregate two result sets:
ordinary and fresh, and how the quality of our classifier of query’s recency
sensitivity affects the quality of such aggregation.

Figure 3 demonstrates how ERR-IAA changes as the estimation of the probability
of the need in recent documents deviates from its true value for the three
different true values assigned by our assessors: 0.25, 0.75 and 0.95. As we
see, while minor errors in the probability estimation do not significantly
affect the quality of the aggregated ranking, it is evidently important to
keep the errors low as the ranking quality drops quite rapidly with their
increase.

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$Recent documents need
approximationERR-IAAERR-IAA for 0.25ERR-IAA for 0.75ERR-IAA for 0.95 Figure 3:
ERR-IAA for queries with different “true" probabilities of need in fresh
content

Further, we analyze the quality of the aggregation for the recency sensitivity
classifier that we use in this work (Figure 4). We split our queries judged by
their recency sensitivity (see Section 3) into two parts (training and test,
2000 queries each) and conduct the evaluation via two-fold cross-validation.
We train our classifier on the training set of queries and evaluate how its
accuracy affects the quality of the aggregation on the test set. Note, that in
a real setting that we simulate in this experiment, the initial ranking
naturally contains some number of fresh documents. As a result, ERR-IAA
measured on the ordinary ranking starts to grow as the recency need
probability approaches 1.0, since the queries with such high probability of
the need in recent content are typically the queries that are unambiguous:
highly descriptive and possessing enough discriminating power to retrieve very
relevant content. For example, for the query [europe alert icelandic ash
cloud], both the ordinary result set and the fresh result set are quite
similar on the day of the infamous volcano eruption. The major gain from
applying the diversification comes for the queries with probabilities of the
need in recent content from 0.3 to 0.8. This is to be expected, as our
approach to recency ranking focuses on the cases of temporal query ambiguity,
in contrast to the previous approaches, which aim to maximize the quality of
ranking for the queries with no temporal ambiguity (see [3, 4] for more
details).

$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$0$$0.2$$0.4$$0.6$$0.8$Recent
documents needERR-IAADiversify with ideal classifierDiversify with our
classifierInitial rankingRecent documents ranking Figure 4:  ERR-IAA for
queries with different level of ambiguity, diversified and non-diversified
rankings

###  5.2 Online results

In order to test our approach in terms of web search engine metrics measuring
user satisfaction, we conducted an A/B test [7]. Some users of Yandex search
engine were always presented with ordinary search results (control bucket),
which were never diversified with fresh documents, and some users were
presented with diversified search results (treatment bucket). We ran the
experiment for 13 days in March 2011 and that involved about 10 million
queries in each bucket (issued by real users as we filtered out bots and
spammers). We measured user satisfaction using metrics suggested by Radlinski
et. al. [10], as they are known to correlate with search result quality. Final
results for the control and the treatment are listed in Table 1.

Table 1:  User behavior metrics for the control and the treatment buckets Metric |  Meaning |  Contr |  Treat
---|---|---|---
Abandonment Rate |  % of queries with no results clicked |  33.65 |  32.77
Time to first click |  Time to first click on any result (in sec) |  10.95 |  10.76
1st Position CTR |  % of queries with 1st position clicked |  44.22 |  45.31
2nd Position CTR |  % of queries with 2nd position clicked |  14.88 |  14.92
First Click Position |  Position of first click |  1.91 |  1.87

All metrics in the treatment are significantly different from metrics in the
control (Mann-Whitney U test, $\alpha=0.01$) and all these differences
indicate the increase of search result quality after diversification. In other
words, the decrease of abandonment rate means less cases when users could not
find any relevant result, the decrease of the mean first click position
indicates that top results became more relevant, the decrease of the mean time
to first click also indicates that relevant results received higher ranks and
hence could be spotted faster, and the increase of CTRs of the URLs at the
first two positions also indicates their increased relevance.

##  6 Conclusions and Future Work

In this paper, we present an approach to improve recency ranking, while
preserving the overall relevance of the ordinary search result. We developed a
multi-grade recency sensitive queries classifier that predicts the degree of
the need in recent documents. We further demonstrated how to diversify the
ordinary search result with fresh documents by maximizing the search quality
measure which takes the query’s temporal ambiguity into account. We
demonstrated the behavior of our diversification model in different cases
using a set of judged queries. We finally confirmed the intuitions behind our
approaches by a large-scale online experiment involving millions of queries
from real users.

While we consider a fixed time window to determine if documents are fresh, it
definitely makes more sense to determine time window which takes the essence
of the information need expressed in the query into account. We also need to
more systematically handle the challenge of score normalization to obtain the
probabilities of document relevance generated according to each possible
definition of relevance. In this regard, we look forward to exploit the
techniques of results merging developed in the area of Distributed Information
Retrieval [6].

The diversification based approach to recency ranking can be also useful to
aggregate documents from a set of relevant verticals (videos, images or
shopping items). However, the danger of over-diversification is not well
studied yet. It is not clear if users would prefer too many results of
different kinds blended into one search result page. Our long term goal is to
develop a unified approach to deal with several kinds of query ambiguities:
topical and non-topical.

## References

  * [1] Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, Samuel Ieong.  Diversifying Search Results.  In WSDM’09
  * [2] Charles L. A. Clarke, Maheedhar Kolla, Gordon V. Cormack, Olga Vechtomova, Azin Ashkan, Stefan Buttcher, Ian MacKinnon.  Novelty and Diversity in Information Retrieval Evaluation  In SIGIR’09, 2009.
  * [3] Anlei Dong, Yi Chang, Zhaohui Zheng, Gilad Mishne, Jing Bai, Ruiqiang Zhang, Karolina Buchner, Ciya Liao, Fernando Diaz.  Towards Recency Ranking in Web Search  In WSDM’10, 2010.
  * [4] Anlei Dong, Ruiqiang Zhang, Pranam Kolari, Jing Bai, Fernando Diaz, Yi Chang, Zhaohui Zheng.  Time is of the Essence: Improving Recency Ranking Using Twitter Data  In WWW’10, 2010.
  * [5] Jaime Arguello, Fernando Diaz, Jamie Callan, Jean-Francois Crespo.  Sources of Evidence for Vertical Selection.  In SIGIR’09, 2009.
  * [6] J. Callan.  Distributed information retrieval. In W. B. Croft, editor, Advances in Information Retrieval.
  * [7] Ron Kohavi, Randy Henne, and Dan Sommerfield  Practical Guide to Controlled Experiments on the Web: Listen to Your Customers not to the HiPPO.  In KDD ’07, pages 959–967, 2007.
  * [8] Jerome H. Friedman.  Greedy function approximation: A gradient boosting machine  In Annals of Statistics, 29, pages 1189–1232, 2001.
  * [9] O. Chapelle, D. Metlzer, Y. Zhang, and P. Grinspan.  Expected reciprocal rank for graded relevance.  In Proceedings of the 18th ACM conference on Information and knowledge management, pages 621–630, 2009.
  * [10] Filip Radlinski, Madhu Kurup, Thorsten Joachims  How Does Clickthrough Data Reflect Retrieval Quality?  In CIKM’08, pages 26–30, 2008.