# Working with scale: 2nd place solution to Product Detection in Densely
Packed Scenes

Artem Kozlov
<EMAIL_ADDRESS>

###### Abstract

This report describes a 2nd place solution of the _detection challenge_ which
is held within CVPR 2020 Retail-Vision workshop. Instead of going further
considering previous results this work mainly aims to verify previously
observed takeaways by re-experimenting. The reliability and reproducibility of
the results are reached by incorporating a popular object detection toolbox -
_MMDetection_. In this report, I firstly represent the results received for
Faster-RCNN and RetinaNet models, which were taken for comparison in the
original work. Then I describe the experiment results with more advanced
models. The final section reviews two simple tricks for Faster-RCNN model that
were used for my final submission: changing default anchor scale parameter and
train-time image tiling. The source code is available at
https://github.com/tyomj/product_detection.

##  1 Introduction

The majority of works in object detection mainly describe results on two
datasets: Pascal VOC [5] and MS-COCO [12]. While this information might be
helpful in forming the relative intuition of a model behavior for common
scenes, it is still unobvious when it comes to a dataset whose distribution of
objects deviates. Goldman et al. [7] proposed a dataset with the following key
features: 1) a high number of objects on an image, 2) objects are densely
packed.

Although in the comparison table the authors declared the dataset to have
110,712 classes, it is important to note that in this context they used the
term _class_ to describe the appearance variations among the objects. De facto
the dataset represents a single-class object detection task. Considering this
information, we might reference an example of a similar task from a different
domain [15] where both RetinaNet [11] and Faster-RCNN [14] were taking as
baseline solutions and showed good results. Hence, the first step of my plan
was to revisit some of the baseline architectures.

A rapidly growing number of papers with different new methods in object
detection makes it difficult to maintain the reliable and up-to-date
benchmarking table especially when a custom implementation of the new method
also comes with different parts of the training pipeline such as data pre-
processing or results post-processing. In order to address this issue, many
attempts have been made for the last several years to create a highly reusable
codebase that covers most of the popular models in the field. For now there
are plenty of such toolboxes based on different deep learning frameworks:
Tensorflow Object Detection API [9], Detectron [6] and Detectron2 [17],
MMDetection [4], and so on. Each of these toolboxes has reusable parts of
code, which makes it easier to compare the performance of models in vitro. For
my experiments I chose MMDetection v1.

The rest of the report is structured as follows: in Section 2 I briefly review
the parameters of the dataset and additionally highlight the features which I
found important. Section 3 contains all the experiment results where I
consequentially inspect the results starting from baseline models 3.1 then
testing a few approaches that are different from widely-used anchoring scheme
3.2. In the final subsection 3.3 I describe two simple tricks that helped to
achieve considerably good performance for Faster-RCNN, testing some commonly-
used tricks along the way.

##  2 Dataset description

The dataset for the challenge is almost the same version that was originally
described in [7] with minor differences: the train set contains 8,219 instead
of 8,233 images and the test set contains 2,936 out of 2,941. The validation
part contains exactly 588 images. During training a few more examples of
broken images were found, so those might be easily excluded.

(a) Aspect ratio

(b) Area

(c) Width

(d) Height

Figure 1: Statistics of object geometry in histograms. Outliers are clipped by
0.01 and 0.99 quantiles.

Inspecting the train set statistics the most popular image sizes were found.
It turned out that the majority of scenes were taken in portrait mode in the
following resolutions: 2448x3264 - 3463 images, 1920x2560 \- 1710 images,
2336x4160 and 2340x4160 might be combined to have 1133 samples in total. The
distribution of image sizes definitely differs from Pascal VOC and MS COCO
that is a premise to experimenting with related parameters. Secondly, object
sizes and aspect ratios were reviewed (see Fig. 1). While aspect ratio
distribution was not found interesting, object size distribution seemed a more
rewarding feature to work with. Although object sizes were distributed as
0.12%/18.53%/81.35% among "small", "medium" and "large" according to MS COCO
the object size classification, the picture is changing in the scenario of
image resizing, which is a necessary trick for training with reasonable batch
size. Decreasing the image size to 816x1088 111This size is used as a default
parameter to ”Resize” transformation for the rest of the report until
otherwise is specified. Unlike default 1333x800 the proposed size takes into
account the most popular image size within SKU110k. which is 9 times smaller,
we will see the following shift - 18.64%/80.27%/1.09%. In this scale the
number of "large" examples is substantially small. These findings drew much
attention to the ideas described in 3.3.

##  3 Experiments

###  3.1 Previously compared models

For the purpose of setting up a fair baseline two main models were chosen:
Faster-RCNN and RetinaNet. Both models are used with default configurations
utilizing ResNet-50 [8] backbone and FPN [10]. In the initial experiments
images are resized to a maximum scale of 1333x800, without changing the aspect
ratio. The training schedule is “1x”, which means 12 epochs. "RandomFlip"
image augmentation is used with probability 0.5 during training time. The
model is trained on the training set, and the test set is used for evaluation.
Evaluation is performed using official "pycocotools" package which is an
implementation of detection evaluation metrics used by COCO with "maxDets"
parameter changed to "[1 10 300]". 222The results obtained by testing with
pycocotools were slightly different from the results obtained with the
evaluation code proposed by the authors. I did not set a goal of revealing the
differences in code, so just be aware while comparing with any results taken
from other technical reports.

Given the results described in Table 1 I decided to further experiment with
stronger models.

Table 1: Revisiting default models Model | mAP |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| AR300
---|---|---|---|---
RetinaNet-r50-fpn | 0.463 | 0.751 | 0.532 | 0.512
Faster-RCNN-r50-fpn | 0.523 | 0.850 | 0.592 | 0.582

###  3.2 Different anchoring approaches

In order to test anchoring strategies different from the dense scheme used for
both previous models _Guided Anchoring_ [16] was tried in a combination with
RetinaNet on top of two different backbones. Surprisingly, GA-
RetinaNet-r50-fpn showed results comparable with Faster-RCNN model. Another
approach _RepPoints_ [18], which is an example of anchor free detectors, did
not show any significant improvement with default parameters.

Table 2: Non-dense anchoring Model | mAP |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| AR300
---|---|---|---|---
GA-RetinaNet-r50-fpn | 0.523 | 0.870 | 0.579 | 0.583
GA-RetinaNet-x101-32x4d-fpn | 0.537 | 0.882 | 0.602 | 0.598
RepPoints-moment-r50-fpn | 0.505 | 0.815 | 0.578 | 0.562

###  3.3 Scale-related tricks

####  3.3.1 Anchor scale

MMDetection Faster-RCNN default implementation uses the following anchor
settings: ‘anchor_strides‘=[4, 8, 16, 32, 64] that specifies the stride for an
anchor grid and ‘anchor_scale‘ = [8] that is used as a multiplication factor
for strides to obtain 5 anchor scales with areas [322, 642, 1282, 2562, 5122]
respectively. In Section 2 I highlighted lack of "large" objects if resizing
preprocessing is applied. Hence, in order to generate more dense proposals, it
looked like a good idea to decrease ‘anchor_scale‘ to [4] to form the
following areas [162, 322, 642, 1282, 2562]. Table 3 represent relative
importance of this parameter.

Table 3: Comparison of different anchor scales Model | Anchor scale | mAP |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| AR300
---|---|---|---|---|---
Faster-RCNN-r50-fpn | [8] | 0.522 | 0.850 | 0.591 | 0.577
Faster-RCNN-r50-fpn | [4] | 0.551 | 0.912 | 0.614 | 0.613

To pay respect to computer vision challenges widely-used tricks were tested on
top of that such as: simple TTA with ‘RandomFlip‘, additional data
augmentation using albumentations [2] config333 https://github.com/open-
mmlab/mmdetection/blob/v1.0.0/configs/albu_example/mask_rcnn_r50_fpn_1x.py,
multi-scale training. None of them gave any significant boost. See Table 4.

Table 4: Some of the common tricks Model | Lr schd | Extra augs | Train flip | Test flip | MS train | mAP |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| AR300
---|---|---|---|---|---|---|---|---|---
Faster-RCNN-r50-fpn | 1x | ✗ | ✗ | ✗ | ✓ | 0.552 | 0.912 | 0.615 | 0.616
Faster-RCNN-r50-fpn | 1x | ✓ | ✗ | ✗ | ✗ | 0.548 | 0.911 | 0.608 | 0.612
Faster-RCNN-r50-fpn | 2x | ✓ | ✓ | ✗ | ✗ | 0.540 | 0.906 | 0.596 | 0.606
Faster-RCNN-r50-fpn | 2x | ✓ | ✓ | ✓ | ✗ | 0.510 | 0.888 | 0.543 | 0.584

In order to obtain even more precise detector Cascade-RCNN [3] was also
tested. Image size was reduced for models with ResNeXt-101 in order to keep
batch size equal to 2 images. The results are available in Table 5. Soft-NMS
[1] was applied as a post-processing, which usually gives better results.

Table 5: Cascade-RCNN comparison Model | Img size | Anchor scale | Soft-NMS | mAP |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| AR300
---|---|---|---|---|---|---|---
Cascade-RCNN-r50-fpn | (816, 1088) | [8] | ✗ | 0.525 | 0.840 | 0.604 | 0.582
Cascade-RCNN-r50-fpn | (816, 1088) | [4] | ✗ | 0.553 | 0.902 | 0.626 | 0.615
Cascade-RCNN-r50-fpn | (816, 1088) | [4] | ✓ | 0.556 | 0.900 | 0.632 | 0.622
Cascade-RCNN-x101-32x4d-fpn | (768, 1024) | [4] | ✗ | 0.556 | 0.903 | 0.629 | 0.617
Cascade-RCNN-x101-32x4d-fpn | (768, 1024) | [4] | ✓ | 0.560 | 0.902 | 0.635 | 0.623

####  3.3.2 Tiling strategies

Image tiling as a trick for object detection for large images with small
objects on them was previously explored in [13]. Following the proposed method
2x2 tiling grid was chosen with 20% intersection between consecutive tiles.
Keeping in mind dense object location bounding box annotations of objects with
residual area less than 20% of the original were removed. In their work [13]
proposed to also take a full frame for merging detectors. Although it might
seem helpful for "large" objects, I’d like to emphasize that we almost never
have those, so this option seems redundant.

Hence, I decided to test the two following approaches:

  * •

Tile-combine. In this scenario each image in train and test parts of the
dataset is split into 4 tiles. Appropriate annotations are created. During
test time inference is run on each tile and the results are saved into a JSON
file. Then the results are manually merged. Duplicated objects on overlapping
areas are resolved by NMS.

  * •

Train-time tiling. Here the model on 4 tiles is trained. Test-time inference
is run using a 4 times larger resolution. The last one is possible because we
do not have to store gradients in the test time.

_Tile-combine_ seemed promising when evaluating on tiles (w/o merging), but
the metrics dramatically decreased for full frames after combining the results
(merged). I also tried to resolve multiple bounding boxes on tiles edges by
NMS providing normalized areas instead of probability scores from the
detector, which did not improve the score. Obviously when image tiling is
applied ‘anchor_scale‘ parameter becomes much less important. Finally, _train-
time tiling_ and applying detection on a full frame with 1632x2176 resize
showed the best results and I used this configuration for final training. See
Table 6.

Table 6: Tiling strategies Model | Comment | An. scale | Soft-NMS | mAP |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| AR300
---|---|---|---|---|---|---|---
Faster-RCNN-r50-fpn | w/o merging | [8] | ✗ | 0.561 | 0.912 | 0.632 | 0.628
Faster-RCNN-r50-fpn | w/o merging | [4] | ✗ | 0.566 | 0.928 | 0.636 | 0.636
Faster-RCNN-r50-fpn | merged | [4] | ✗ | 0.547 | 0.894 | 0.615 | 0.611
Faster-RCNN-r50-fpn | full frame | [4] | ✓ | 0.577 | 0.928 | 0.659 | 0.654

####  3.3.3 Final submission approach

For my final approach I used Faster-RCNN-r50-fpn with ‘anchor_scale‘ = [4]
trained on a combination of train, val and test sets tiled as described above.
During inference on a provided leaderboard-test set without annotations I used
resizing to 1632x2176 and Soft-NMS to resolve duplications. No TTA or
ensembling was used.

##  4 Conclusions

In this report it was empirically shown that the simple two-stage detector is
a strong baseline for the Product Detection in Densely Packed Scenes task.
Also two scale-related approaches are described which improve the detector
performance by a large margin. Hence, object scale is one of the aspects that
should be considered for further investigation and I also hope to see new
approaches being developed for the dataset taking this idea into account.

## References

  * [1] Navaneeth Bodla, Bharat Singh, Rama Chellappa, and Larry S. Davis.  Soft-nms – improving object detection with one line of code, 2017.
  * [2] Alexander Buslaev, Vladimir I. Iglovikov, Eugene Khvedchenya, Alex Parinov, Mikhail Druzhinin, and Alexandr A. Kalinin.  Albumentations: Fast and flexible image augmentations.  Information, 11(2), 2020.
  * [3] Zhaowei Cai and Nuno Vasconcelos.  Cascade r-cnn: Delving into high quality object detection, 2017.
  * [4] Kai Chen, Jiaqi Wang, Jiangmiao Pang, Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu, Jiarui Xu, Zheng Zhang, Dazhi Cheng, Chenchen Zhu, Tianheng Cheng, Qijie Zhao, Buyu Li, Xin Lu, Rui Zhu, Yue Wu, Jifeng Dai, Jingdong Wang, Jianping Shi, Wanli Ouyang, Chen Change Loy, and Dahua Lin.  Mmdetection: Open mmlab detection toolbox and benchmark, 2019.
  * [5] M Everingham, L Van Gool, CKI Williams, J Winn, and A Zisserman.  The pascal visual object classes challenge 2012 (voc2012) results (2012).  In URL http://www. pascal-network. org/challenges/VOC/voc2011/workshop/index. html, 2011.
  * [6] Ross Girshick, Ilija Radosavovic, Georgia Gkioxari, Piotr Dollár, and Kaiming He.  Detectron.  https://github.com/facebookresearch/detectron, 2018.
  * [7] Eran Goldman, Roei Herzig, Aviv Eisenschtat, Oria Ratzon, Itsik Levi, Jacob Goldberger, and Tal Hassner.  Precise detection in densely packed scenes, 2019.
  * [8] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition, 2015.
  * [9] Jonathan Huang, Vivek Rathod, Chen Sun, Menglong Zhu, Anoop Korattikara, Alireza Fathi, Ian Fischer, Zbigniew Wojna, Yang Song, Sergio Guadarrama, and Kevin Murphy.  Speed/accuracy trade-offs for modern convolutional object detectors, 2016\.
  * [10] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection, 2016.
  * [11] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection, 2017.
  * [12] Tsung-Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, and Piotr Dollár.  Microsoft coco: Common objects in context, 2014.
  * [13] F Ozge Unel, Burak O Ozkalayci, and Cevahir Cigla.  The power of tiling for small object detection.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 0–0, 2019.
  * [14] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks, 2015.
  * [15] Shuai Shao, Zijian Zhao, Boxun Li, Tete Xiao, Gang Yu, Xiangyu Zhang, and Jian Sun.  Crowdhuman: A benchmark for detecting human in a crowd, 2018.
  * [16] Jiaqi Wang, Kai Chen, Shuo Yang, Chen Change Loy, and Dahua Lin.  Region proposal by guided anchoring, 2019.
  * [17] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan-Yen Lo, and Ross Girshick.  Detectron2.  https://github.com/facebookresearch/detectron2, 2019.
  * [18] Ze Yang, Shaohui Liu, Han Hu, Liwei Wang, and Stephen Lin.  Reppoints: Point set representation for object detection, 2019.


# An analytic approach to estimating the solutions of Bézout’s polynomial
identity

Emmanuel Fricain  Laboratoire Paul Painlevé, Université de Lille, 59 655
Villeneuve d’Ascq Cédex<EMAIL_ADDRESS>,  Andreas Hartmann
Univ. Bordeaux, CNRS, Bordeaux INP, IMB, UMR 5251, F-33400, Talence, France
<EMAIL_ADDRESS>,  William T. Ross  Department of
Mathematics and Statistics, University of Richmond, Richmond, VA 23173, USA
<EMAIL_ADDRESS>and  Dan Timotin  Simion Stoilow Institute of Mathematics
of the Romanian Academy, Calea Griviţei 21, Bucharest 010702, Romania
<EMAIL_ADDRESS>
###### Abstract.

This paper contains sharp bounds on the coefficients of the polynomials $R$
and $S$ which solve the classical one variable Bézout identity $AR+BS=1$,
where $A$ and $B$ are polynomials with no common zeros. The bounds are
expressed in terms of the separation of the zeros of $A$ and $B$. Our proof
involves contour integral representations of these coefficients. We also
obtain an estimate on the norm of the inverse of the Sylvester matrix.

##  1\. Introduction

The well known Bézout polynomial identity [3] says that if $A(z)$ and $B(z)$
are complex polynomials with no common zeros, of degrees $N$ and $K$
respectively, then there are complex polynomials $R(z)$ and $S(z)$ with

(1.1) $\deg R\leqslant K-1\;\;\mbox{and}\;\;\deg S\leqslant N-1$

such that

(1.2) $A(z)R(z)+B(z)S(z)=1\;\mbox{for all $z\in\mathbb{C}$.}$

Moreover, if $A,B$ are not both constant, then $R$ and $S$ are uniquely
determined by the degree condition from (1.1) and are called the _minimal
solutions_ of (1.2). To avoid trivialities, we will assume for the rest of the
paper that both the polynomials $A$ and $B$ are not constant.

Our main result (Theorem 2.10 ) provides sharp (upper) estimates of the
coefficients of $R$ and $S$ in terms of the constant

$\delta(A,B):=\min\\{|A(z)|+|B(z)|:A(z)=0\text{ or }B(z)=0\\}.$

Namely, we prove there is a constant $C>0$, depending only on $N$ and $K$,
such that if the moduli of the coefficients of $A$ and $B$ are bounded by 1,
then the moduli of the coefficients of $R$ and $S$ are bounded by
$C\delta^{-2}$.

Computing the coefficients of $R$ and $S$ traditionally involves algebraic
methods and are not convenient for obtaining sharp estimates. Our approach
uses analytical tools based on contour integrals similar to those in [15] (see
also [14]). In Theorem 6.4 we apply our methods to obtain an upper estimate of
the norm of the inverse of the Sylvester matrix.

Quite surprisingly, we could not find any estimates of coefficients of the
minimal solutions $R$ and $S$ from (1.2) in the literature. There are
estimates of the degree and size of the solutions of the much harder analogous
problem in several variables, which is related to Hilbert’s Nullstellensatz
(see, for instance, [2] and the references therein). However, they do not
involve quantities similar to $\delta(A,B)$ and thus are not connected to
Theorem 2.10.

One can regard Bézout’s polynomial identity as an algebraic version of the
well-known corona theorem of Carleson [4]: if $\varphi,\psi\in H^{\infty}$,
the bounded analytic functions on the open unit disk $\mathbb{D}$, satisfy

(1.3) $1\geqslant|\varphi(z)|+|\psi(z)|\geqslant\delta>0\;\mbox{for all
$z\in\mathbb{D}$},$

then there are $g,h\in H^{\infty}$ such that

(1.4) $\varphi(z)g(z)+\psi(z)h(z)=1\;\mbox{for all $z\in\mathbb{D}$}.$

Moreover, results from [9, 10, 13] show there is a universal constant $C>0$
such that one can choose the $g,h\in H^{\infty}$ satisfying (1.4) so that

(1.5)
$\|g\|_{\infty},\|h\|_{\infty}\leqslant\frac{C}{\delta^{2}}\log\frac{1}{\delta},$

where $\|g\|_{\infty}:=\sup\\{|g(z)|:z\in\mathbb{D}\\}$ and $\delta$ is
defined in (1.3). A result from [11] shows that the estimate in (1.5) is
almost sharp. In the case of Bézout’s identity, it follows from our main
theorem (Theorem 2.10) that the logarithm term is not required.

A final remark: the constants $C_{1},C_{2},\dots$ that will appear in the
estimates in this paper only depend on $N=\operatorname{deg}A$ and
$K=\operatorname{deg}B$ and not on the coefficients of the polynomials $A$ and
$B$. This fact will be in force in the sequel, even if not always explicitly
stated.

##  2\. Preliminaries and the main result

Let $\mathbb{C}[z]$ denote the polynomials in the complex variable $z$ with
coefficients in $\mathbb{C}$. For $N\in\\{1,2,\ldots\\}$, let
$\mathbb{C}_{N}[z]$ denote the vector space of polynomials whose degree is at
most $N$. We need a way to measure the “size” of an $A\in\mathbb{C}[z]$. For
this we use the maximum of the moduli of the coefficients of $A$ in that if

$A(z)=a_{0}+a_{1}z+\cdots+a_{N}z^{N},$

then

$\|A\|:=\max_{0\leqslant i\leqslant N}|a_{i}|$

defines a norm on $\mathbb{C}[z]$.

In order to quantify the fact that $A\in\mathbb{C}_{N}[z]$ and
$B\in\mathbb{C}_{K}[z]$ share no common roots, we define

(2.1) $\delta(A,B):=\min\\{|A(z)|+|B(z)|:A(z)=0\text{ or }B(z)=0\\}.$

We may reformulate (2.1) by

(2.2) $\delta=\delta(A,B):=\min\\{|A(\beta_{j})|,|B(\alpha_{i})|,1\leqslant
i\leqslant N,1\leqslant j\leqslant K\\},$

where $\\{\alpha_{i}\\}_{i=1}^{N}$ are the roots of $A$ and
$\\{\beta_{j}\\}_{j=1}^{K}$ are the roots of $B$.

Another way to quantitatively express the lack of common roots for $A$ and $B$
is to consider

(2.3) $\widetilde{\delta}(A,B):=\min\\{|A(z)|+|B(z)|:z\in\mathbb{C}\\},$

which appears, for instance, in [6]. Being the infimum of a family of
continuous functions, $\widetilde{\delta}$ is upper semicontinous (but not
necessarily continuous, see Example 9.3), on the compact set

(2.4)
$\mathfrak{B}:=\\{(A,B)\in\mathbb{C}_{N}[z]\times\mathbb{C}_{K}[z]:\max\\{\|A\|,\|B\|\\}\leqslant
1\\},$

whence it is also bounded on $\mathfrak{B}$. Though $\delta(A,B)$ is used in
this paper, Corollary 3.12 shows that $\delta(A,B)$ and
$\widetilde{\delta}(A,B)$ are equivalent.

One way to obtain the unique minimal solutions $R$ and $S$ to (1.2) (see
Section 6 for the details), is to show that their coefficients are the
solutions of a linear system involving a matrix called the Sylvester matrix.
More precisely, if

$A(z)=a_{0}+a_{1}z+\cdots+a_{N}z^{N},\quad
B(z)=b_{0}+b_{1}z+\cdots+b_{K}z^{K},$

and

$R(z)=r_{0}+\dots+r_{K-1}z^{K-1},\quad S(z)=s_{0}+\dots+s_{N-1}z^{N-1},$

one can compare the coefficients of each side of (1.2), after carrying out the
algebraic manipulations, to create a linear system of equations in the
variables $\\{r_{i}\\}_{i=0}^{K-1}$ and $\\{s_{j}\\}_{j=0}^{N-1}$. Applying
Cramer’s rule to this system, one obtains that each solution $r_{i}$ and
$s_{j}$ is a quotient of two determinants of order $N+K$ whose nonzero entries
are either 1 or one of the coefficients of $A$ or $B$. Therefore,

(2.5) $r_{i}=\frac{\widetilde{r}_{i}}{\Delta(A,B)},\quad
s_{j}=\frac{\widetilde{s}_{j}}{\Delta(A,B)},$

where $\widetilde{r}_{i},\widetilde{s}_{j}$ and $\Delta(A,B)$ are fixed
polynomials, of degree $N+K$ and with at most $(N+K)!$ terms, in the
coefficients $\\{a_{j}\\}_{j=0}^{N}$ and $\\{b_{j}\\}_{j=0}^{K}$ of $A$ and
$B$ respectively. An easy consequence of these formulas is the following
lemma.

######  Lemma 2.6.

For fixed $N$ and $K$, let $\mathbb{C}_{N}^{*}[z]$ and $\mathbb{C}^{*}_{K}[z]$
denote the nonconstant polynomials in $\mathbb{C}_{N}[z]$ and
$\mathbb{C}_{K}[z]$ respectively. Define

(2.7)
$\mathcal{T}=\\{(A,B)\in\mathbb{C}_{N}^{*}[z]\times\mathbb{C}_{K}^{*}[z]:\Delta(A,B)\not=0\\}$

and let
$\varphi:\mathcal{T}\mapsto\mathbb{C}_{K-1}[z]\times\mathbb{C}_{N-1}[z]$ be
defined by $\varphi(A,B)=(R,S)$, where $R$ and $S$ are the minimal solutions
to (1.2). Then $\varphi$ is a continuous map.

The quantity $\Delta(A,B)$ in (2.5) is the determinant of the matrix of the
system and is called the Sylvester resultant. One can show (see, for instance,
[7, IV, $\S 8$]) that

$\displaystyle|\Delta(A,B)|$
$\displaystyle=\Big{|}a_{N}^{K}b_{K}^{N}\prod_{i=1}^{N}\prod_{j=1}^{K}(\alpha_{i}-\beta_{j})\Big{|}$
(2.8)
$\displaystyle=|b_{K}|^{N}\prod_{j=1}^{K}|A(\beta_{j})|=|a_{N}|^{K}\prod_{i=1}^{N}|B(\alpha_{i})|,$

whence the set $\mathcal{T}$ from (2.7) is actually the set of pairs of
nonconstant polynomials without common roots.

Since $\widetilde{r}_{i},\widetilde{s}_{j}$ are fixed polynomials of degree at
most $N+K$ in the coefficients of $A$ and $B$, the conditions
$\|A\|,\|B\|\leqslant 1$ imply that $|\widetilde{r}_{i}|$ and
$|\widetilde{s}_{j}|$ are bounded above by some positive constant depending
only on $N$ and $K$. From (2.5) and (2), there is a constant $C>0$, depending
only on $N$ and $K$, such that if $\|A\|,\|B\|\leqslant 1$ and
$|b_{K}|=|a_{N}|=1$ (i.e., $A$ and $B$ are monic polynomials), then

(2.9) $\|R\|,\|S\|\leqslant\frac{C}{\delta^{\min(N,K)}}.$

Our main result below, which will be proved in Section 8, is a significant
improvement of (2.9) in that one can replace the exponent $\min(N,K)$ by 2, as
well as ignore the assumption that $A$ and $B$ are monic polynomials.

######  Theorem 2.10.

Let $A,B\in\mathbb{C}[z]$, with $\operatorname{deg}A=N$ and
$\operatorname{deg}B=K$, satisfy $\|A\|,\|B\|\leqslant 1$. If
$\delta=\delta(A,B)>0$, then the unique minimal solutions
$R\in\mathbb{C}_{K-1}[z]$ and $S\in\mathbb{C}_{N-1}[z]$ to Bézout’s identity
(1.2) satisfy

(2.11) $\|R\|,\|S\|\leqslant\frac{C}{\delta^{2}},$

for some universal constant $C>0$ depending only on $N$ and $K$.

In Section 10 we address the issue as to what happens when we remove the
assumption that $\|A\|,\|B\|\leqslant 1$.

As noted above, we will obtain $R$ and $S$ using complex function theory. A
similar method was used to explore polynomials of several variables in
connection with Bézout identities and Hilbert’s Nullstellensatz [1].

##  3\. A separation lemma

This section contains a separation lemma that will have several interesting
consequences. Recall that

$A(z)=\sum_{k=0}^{N}a_{k}z^{k}\;\;\mbox{and}\;\;B(z)=\sum_{k=0}^{K}b_{k}z^{k}$

are two complex polynomials. If $\\{\alpha_{i}\\}_{i=1}^{N}$ are the roots of
$A$ and $\\{\beta_{j}\\}_{j=1}^{K}$ are the roots of $B$, then we can write

(3.1)
$A(z)=a_{N}\prod_{i=1}^{N}(z-\alpha_{i})\;\;\mbox{and}\;\;B(z)=b_{K}\prod_{j=1}^{K}(z-\beta_{j}).$

For $\epsilon>0$ let

(3.2) $L(A,\epsilon):=\\{z\in\mathbb{C}:|A(z)|<\epsilon\\},$

and similarly defined for $B$, denote a sub-level set for $A$ (respectively
$B$). If $A$ and $B$ share no common zeros, then certainly
$L(A,\epsilon_{A})\cap L(B,\epsilon_{B})=\varnothing$ for small enough
$\epsilon_{A},\epsilon_{B}$. The next lemma, which plays a crucial role in the
proof of our main theorem, shows that one can choose
$\epsilon_{A},\epsilon_{B}$ to only depend on $\delta$, $N$, and $K$ (and not
on the coefficients of $A$ and $B$).

######  Lemma 3.3.

If $\|A\|,\|B\|\leqslant 1$ and $\delta=\delta(A,B)>0$, then

(3.4) $L\big{(}A,\frac{\delta}{3^{N}}\big{)}\bigcap
L\big{(}B,\frac{\delta}{3^{K}}\big{)}=\varnothing.$

###### Proof.

Let us use the standard notation

$D(a,r):=\\{z\in\mathbb{C}:|z-a|<r\\},\;\;a\in\mathbb{C},r>0.$

We begin by fixing a value of $1\leqslant j\leqslant K$. If $z\in\mathbb{C}$
satisfies

$|z-\alpha_{i}|\geqslant\displaystyle\tfrac{1}{3}|\beta_{j}-\alpha_{i}|\;\;\mbox{for
all $1\leqslant i\leqslant N$},$

then (3.1) says that

$\displaystyle|A(z)|=|a_{N}|\prod_{i=1}^{N}|z-\alpha_{i}|\geqslant\frac{1}{3^{N}}|a_{N}|\prod_{i=1}^{N}|\beta_{j}-\alpha_{i}|=\frac{1}{3^{N}}|A(\beta_{j})|\geqslant\frac{\delta}{3^{N}}.$

Thus, outside the region

$\bigcup_{i=1}^{N}D(\alpha_{i},\tfrac{1}{3}|\beta_{j}-\alpha_{i}|),$

the function $|A|$ is bounded from below by $\delta/3^{N}$. This being true
for every $1\leqslant j\leqslant K$, we deduce that

(3.5)
$L\big{(}A,\frac{\delta}{3^{N}}\big{)}\subseteq\bigcap_{j=1}^{K}\bigcup_{i=1}^{N}\
D(\alpha_{i},\tfrac{1}{3}|\beta_{j}-\alpha_{i}|).$

Denote the set on the right hand side of the previous inclusion by $E_{A}$
(see Figure 1).

Figure 1. The regions $E_{B}$ (top - in one piece) and $E_{A}$ (bottom in two
pieces) together with the zeros $\\{\alpha_{i}\\}_{i=1}^{N}$ (in $E_{A}$) and
the zeros $\\{\beta_{j}\\}_{j=1}^{K}$ (in $E_{B}$). Here $A$ is the monic
polynomial whose roots are
$(\alpha_{1},\alpha_{2},\alpha_{3})=(\tfrac{1}{4}+\tfrac{i}{8},-\tfrac{1}{2},\tfrac{2}{5})$
and $B$ is the monic polynomial whose zeros are
$(\beta_{1},\beta_{2},\beta_{3},\beta_{4})=(\tfrac{1}{9}+\tfrac{5}{6}i,\tfrac{1}{8}+\tfrac{i}{2},\tfrac{i}{3},\tfrac{i}{5})$.

Then for every fixed $z\in E_{A}$, there is a function

$\sigma:\\{1,\dots,K\\}\to\\{1,\dots,N\\}$

such that for every $1\leqslant j\leqslant K$ we have

(3.6) $|z-\alpha_{\sigma(j)}|<\tfrac{1}{3}|\beta_{j}-\alpha_{\sigma(j)}|.$

Similarly, if

$E_{B}:=\bigcap_{i=1}^{N}\bigcup_{j=1}^{K}\
D(\beta_{j},\tfrac{1}{3}|\alpha_{i}-\beta_{j}|),$

(see Figure 1) then $L(B,\delta/3^{K})\subseteq E_{B}$, and for every fixed
$z\in E_{B}$ there is a function

$\tau:\\{1,\dots,N\\}\to\\{1,\dots,K\\}$

such that for every $1\leqslant i\leqslant N$ we have

(3.7) $|z-\beta_{\tau(i)}|<\tfrac{1}{3}|\alpha_{i}-\beta_{\tau(i)}|.$

Towards a contradiction, suppose that

$L\big{(}A,\frac{\delta}{3^{N}}\big{)}\bigcap
L\big{(}B,\frac{\delta}{3^{K}}\big{)}\not=\varnothing.$

Then, using the facts that

$L\big{(}A,\frac{\delta}{3^{N}}\big{)}\subseteq
E_{A}\;\;\mbox{and}\;\;L\big{(}B,\frac{\delta}{3^{K}}\big{)}\subseteq E_{B},$

it must be the case that $E_{A}\cap E_{B}\not=\varnothing$, and so there
exists a $w\in E_{A}\cap E_{B}$. Let $\sigma,\tau$ denote the functions from
(3.6) and (3.7) corresponding to this $w$.

Start with a $k\in\\{1,\dots,K\\}$ and alternately apply the functions
$\sigma$ and $\tau$ to $k$, i.e.,

$\sigma(k),\;\tau(\sigma(k)),\;\sigma(\tau(\sigma(k))),\;\dots.$

At some point the elements of the above sequence must repeat. We will consider
a minimal cycle in the sense that there are no repetitions. In other words,
there is an integer $p$, distinct elements
$j_{1},\dots,j_{p}\in\\{1,\dots,K\\}$, and distinct elements
$i_{1},\dots,i_{p}\in\\{1,\dots,N\\}$, such that $\sigma(j_{s})=i_{s}$ for
$1\leqslant s\leqslant p$, while $\tau(i_{s})=j_{s+1}$ for $1\leqslant
s\leqslant p-1$, and $\tau(i_{p})=j_{1}$ (see Figure 2).

For the rest of the argument, we will only use $\alpha_{\sigma(j)}$ and
$\beta_{\tau(i)}$ for the selected $i$ and $j$. Therefore, to simplify things,
we renumber (corresponding to a change of notation of the indices of $\alpha$
and $\beta$) and assume that $i_{s}=j_{s}=s$ for $1\leqslant s\leqslant p$.
With this renumbering, the function $\sigma$ restricted to the relevant set
$\\{1,\dots,p\\}$ becomes the identity, while $\tau(s)=s+1$ for $1\leqslant
s\leqslant p-1$ and $\tau(p)=1$.

${1}$${2}$${3}$${4}$${5}$${1}$${2}$${3}$${4}$${5}$ Figure 2. An example with
$N=K=5$. Solid lines represent $\sigma$ while dashed lines represent $\tau$.
Starting with 3 on the top row, we obtain
$4=\sigma(3),1=\tau(4),2=\sigma(1),4=\tau(2),4=\sigma(4)$. The associated
minimal cycle that starts with 1 on the top row, is
$\\{1,2=\sigma(1),4=\tau(2),4=\sigma(4)\\}$. So $p=2$ and
$j_{1}=1,j_{2}=4,i_{1}=2,i_{2}=4$.

We may also rewrite the inequalities (3.6) and (3.7) for $z=w$ as follows,
where the inequalities from (3.6) appear in the left column, while those from
(3.7) appear in the right column:

(3.8)
$\begin{split}|w-\alpha_{1}|<\tfrac{1}{3}|\alpha_{1}-\beta_{1}|&\qquad|w-\beta_{2}|<\tfrac{1}{3}|\beta_{2}-\alpha_{1}|\\\
|w-\alpha_{2}|<\tfrac{1}{3}|\alpha_{2}-\beta_{2}|&\qquad|w-\beta_{3}|<\tfrac{1}{3}|\beta_{3}-\alpha_{2}|\\\
\vdots\\\
|w-\alpha_{p}|<\tfrac{1}{3}|\alpha_{p}-\beta_{p}|&\qquad|w-\beta_{1}|<\tfrac{1}{3}|\beta_{1}-\alpha_{p}|.\end{split}$

Adding the two inequalities in each line and using the triangle inequality, we
obtain a series of inequalities that do not contain the term $w$:

$\begin{split}|\beta_{2}-\alpha_{1}|&<\tfrac{1}{3}|\alpha_{1}-\beta_{1}|+\tfrac{1}{3}|\beta_{2}-\alpha_{1}|\\\
|\beta_{3}-\alpha_{2}|&<\tfrac{1}{3}|\alpha_{2}-\beta_{2}|+\tfrac{1}{3}|\beta_{3}-\alpha_{2}|\\\
\vdots\\\
|\beta_{1}-\alpha_{p}|&<\tfrac{1}{3}|\alpha_{p}-\beta_{p}|+\tfrac{1}{3}|\beta_{1}-\alpha_{p}|\end{split}$

or, equivalently,

(3.9)
$\begin{split}|\beta_{2}-\alpha_{1}|&<\tfrac{1}{2}|\alpha_{1}-\beta_{1}|\\\
|\beta_{3}-\alpha_{2}|&<\tfrac{1}{2}|\alpha_{2}-\beta_{2}|\\\ \vdots\\\
|\beta_{1}-\alpha_{p}|&<\tfrac{1}{2}|\alpha_{p}-\beta_{p}|.\end{split}$

Returning to (3.8), we now add each inequality in the right column with the
one in the next row of the left column (with the obvious change in the last
row). Applying the triangle inequality and reducing the similar terms, we
obtain

(3.10)
$\begin{split}|\beta_{2}-\alpha_{2}|&<\tfrac{1}{2}|\beta_{2}-\alpha_{1}|\\\
|\beta_{3}-\alpha_{3}|&<\tfrac{1}{2}|\beta_{3}-\alpha_{2}|\\\ \vdots\\\
|\beta_{1}-\alpha_{1}|&<\tfrac{1}{2}|\beta_{1}-\alpha_{p}|.\end{split}$

Now add all the inequalities from (3.9) and (3.10) to obtain

$\begin{split}&\sum_{i=2}^{p}|\beta_{i}-\alpha_{i-1}|+|\beta_{1}-\alpha_{p}|+\sum_{i=1}^{p}|\beta_{i}-\alpha_{i}|\\\
&\qquad\qquad<\tfrac{1}{2}\left(\sum_{i=1}^{p}|\alpha_{i}-\beta_{i}|+\sum_{i=2}^{p}|\beta_{i}-\alpha_{i-1}|+|\beta_{1}-\alpha_{p}|\right),\end{split}$

which is an obvious contradiction. This shows that $E_{A}\cap
E_{B}=\varnothing$ which, as argued earlier, proves (3.3). ∎

######  Remark 3.11.

Observe that $\\{\alpha_{i}\\}_{i=1}^{N}$ (the zeros of $A$) belong to the
regions

$\bigcup_{i=1}^{N}D(\alpha_{i},\tfrac{1}{3}|\beta_{j}-\alpha_{i}|)\;\;\mbox{
for all $1\leqslant j\leqslant K$},$

and thus belong to $E_{A}$. On the other hand, for a fixed $j$, the point
$\beta_{j}$ (a zero of $B$) is at a positive distance from the region

$\bigcup_{i=1}^{N}D(\alpha_{i},\tfrac{1}{3}|\beta_{j}-\alpha_{i}|),$

and therefore at a positive distance from $E_{A}$. Furthermore, any
$z\in\partial E_{A}$ must satisfy $|A(z)|\geqslant\delta/3^{N}$ (since $z$ is
in the closure of the complement of $L(A,\delta/3^{N})$) as well as
$|B(z)|\geqslant\delta/3^{K}$ (by (3.4)). Similar considerations apply to
$E_{B}$.

An immediate consequence of Lemma 3.3 is the equivalence of the quantities
$\delta(A,B)$ and $\widetilde{\delta}(A,B)$.

######  Corollary 3.12.

If $\widetilde{\delta}(A,B)$ is defined by (2.3), then

(3.13)
$\frac{1}{3^{\max(N,K)}}\delta(A,B)\leqslant\widetilde{\delta}(A,B)\leqslant\delta(A,B).$

###### Proof.

The inequality on the right hand side of (3.13) is immediate. For the left
hand side, note that (3.4) is equivalent to

$\Big{\\{}z\in\mathbb{C}:|A(z)|\geqslant\frac{\delta}{3^{N}}\Big{\\}}\bigcup\Big{\\{}z\in\mathbb{C}:|B(z)|\geqslant\frac{\delta}{3^{K}}\Big{\\}}=\mathbb{C}.$

This implies that any $z\in\mathbb{C}$ must satisfy either
$|A(z)|\geqslant\delta/3^{N}$ or $|B(z)|\geqslant\delta/3^{K}$. Therefore,

$\widetilde{\delta}(A,B)\geqslant\frac{\delta(A,B)}{3^{\max(N,K)}},$

which is precisely the left hand side of (3.13). ∎

We have noted in Section 2 that $\widetilde{\delta}$ is bounded on
$\mathfrak{B}$ defined by (2.4). From Corollary 3.11 it follows that the same
is true for $\delta$, and so there exists a $T>0$, depending only on $N$ and
$K$, such that

(3.14) $\delta(A,B)\leqslant T$

for all $A\in\mathbb{C}_{N}[z]$, $B\in\mathbb{C}_{K}[z]$ with $\|A\|\leqslant
1$, $\|B\|\leqslant 1$.

Lemma 3.3 will be used in the sequel to construct the systems of contours that
appear in a Cauchy integral method to compute the coefficients of the
polynomials $R$ and $S$.

##  4\. The Cauchy integral method

The following lemma is implicit in [15, Section 1.3], but we include a direct
proof in order to make our paper self-contained.

######  Lemma 4.1.

Suppose $\Omega\subseteq\mathbb{C}$ is an open set, $F,G$ are two analytic
functions defined on $\Omega$, $\alpha\in\Omega$ is a zero of $G$, and
$\Gamma$ is a positively oriented system of closed rectifiable contours in
$\Omega\setminus\\{\alpha\\}$ whose index with respect to $\alpha$ is 1, and
such that $G(\zeta)\not=0$ for any $\zeta\in\Gamma$. Define

$g(\zeta,z)=\frac{G(\zeta)-G(z)}{\zeta-z}\quad\mbox{and}\quad\varphi(z)=\frac{1}{2\pi
i}\int_{\Gamma}\frac{g(\zeta,z)F(\zeta)}{G(\zeta)}\,d\zeta.$

Then:

  1. (i)

$\varphi$ is analytic on $\Omega\setminus\Gamma$ and
$\varphi(\alpha)=F(\alpha)$.

  2. (ii)

If $G\in\mathbb{C}_{N}[z]$, then $\varphi\in\mathbb{C}_{N-1}[z]$.

###### Proof.

(i): For $\zeta\in\Gamma$, the function $z\mapsto g(\zeta,z)$ is analytic on
$\Omega\setminus\Gamma$. This implies that $\varphi$ is also analytic on
$\Omega\setminus\Gamma$. Since $G(\alpha)=0$, we see from Cauchy’s formula
that

$\varphi(\alpha)=\frac{1}{2\pi
i}\int_{\Gamma}\frac{G(\zeta)F(\zeta)}{G(\zeta)(\zeta-\alpha)}\,d\zeta=\frac{1}{2\pi
i}\int_{\Gamma}\frac{F(\zeta)}{\zeta-\alpha}\,d\zeta=F(\alpha).$

(ii): If $G\in\mathbb{C}_{N}[z]$, then for every fixed $\zeta\in\Gamma$,
$g(\zeta,\cdot)\in\mathbb{C}_{N-1}[z]$, which implies that
$\varphi\in\mathbb{C}_{N-1}[z]$. ∎

######  Remark 4.2.

So that we can use them later, we now compute the coefficients of
$\varphi\in\mathbb{C}_{N-1}[z]$ when $G(z)=g_{0}+g_{1}z+\dots+g_{N}z^{N}$.
Observe that

$\displaystyle G(\zeta)-G(z)$
$\displaystyle=\sum_{k=1}^{N}g_{k}(\zeta^{k}-z^{k})$
$\displaystyle=(\zeta-z)\sum_{k=1}^{N}g_{k}\frac{\zeta^{k}-z^{k}}{\zeta-z}$
$\displaystyle=(\zeta-z)\sum_{k=1}^{N}g_{k}\sum_{j=0}^{k-1}z^{j}\zeta^{k-1-j}$
$\displaystyle=(\zeta-z)\sum_{j=0}^{N-1}z^{j}\sum_{k=j+1}^{N}g_{k}\zeta^{k-(j+1)},$

and hence

$g(\zeta,z)=\sum_{j=0}^{N-1}z^{j}\sum_{k=j+1}^{N}g_{k}\zeta^{k-(j+1)}.$

Thus,

(4.3) $\varphi(z)=\sum_{j=0}^{N-1}z^{j}\sum_{k=j+1}^{N}g_{k}\frac{1}{2\pi
i}\int_{\Gamma}\frac{F(\zeta)\zeta^{k-(j+1)}}{G(\zeta)}d\zeta,$

where $\Gamma$ is a system of contours as in Lemma 4.1.

Next we obtain the solution to a Bézout-type equation when the zeros of $A$
and $B$ are simple. For $\zeta,z\in\mathbb{C}$, define

$a(\zeta,z)=\frac{A(\zeta)-A(z)}{\zeta-z}\;\;\mbox{and}\;\;b(\zeta,z)=\frac{B(\zeta)-B(z)}{\zeta-z},\;\;\zeta\not=z,$

and of course, $a(\zeta,\zeta)=A^{\prime}(\zeta)$,
$b(\zeta,\zeta)=B^{\prime}(\zeta)$.

######  Corollary 4.4.

Let $A,B,P$ be polynomials with $\deg A=N$, $\deg B=K$, and $\deg P\leqslant
N+K-1$. Suppose the roots $\\{\alpha_{i}\\}_{i=1}^{N}$ of $A$ and the roots
$\\{\beta_{j}\\}_{j=1}^{K}$ of $B$ are all simple and
$\\{\alpha_{i}\\}_{i=1}^{N}\cap\\{\beta_{j}\\}_{j=1}^{K}=\varnothing$.
Consider the equation

(4.5) $A(z)\widehat{R}(z)+B(z)\widehat{S}(z)=P(z).$

Suppose that $\Gamma_{1},\Gamma_{2}$ are positively oriented systems of closed
rectifiable contours in $\mathbb{C}$ such that $\Gamma_{1}$ surrounds the
roots of $A$ (with index $1$) and not those of $B$, while the opposite is true
for $\Gamma_{2}$. Then the unique solutions $\widehat{R},\widehat{S}$ of (4.5)
with the property that $\deg\widehat{R}\leqslant K-1$ and
$\deg\widehat{S}\leqslant N-1$ are given by the formulas

(4.6) $\widehat{S}(z):=\frac{1}{2\pi
i}\int_{\Gamma_{1}}\frac{a(\zeta,z)P(\zeta)}{A(\zeta)B(\zeta)}\,d\zeta,\quad\widehat{R}(z):=\frac{1}{2\pi
i}\int_{\Gamma_{2}}\frac{b(\zeta,z)P(\zeta)}{A(\zeta)B(\zeta)}\,d\zeta.$

###### Proof.

Apply Lemma 4.1 to the functions $G(z)=A(z)$ and $F(z)=P(z)/B(z)$, the region
$\Omega=\mathbb{C}\setminus\\{\beta_{1},\dots,\beta_{K}\\}$, and the contour
$\Gamma_{1}$. The first formula in (4.6) yields a polynomial
$\widehat{S}(z)\in\mathbb{C}_{N-1}[z]$ such that

(4.7) $\widehat{S}(\alpha_{i})=\frac{P(\alpha_{i})}{B(\alpha_{i})}\;\mbox{ for
all $1\leqslant i\leqslant N$.}$

Similarly, by the second formula in (4.6), one obtains
$\widehat{R}(z)\in\mathbb{C}_{K-1}[z]$ such that

(4.8) $\widehat{R}(\beta_{j})=\frac{P(\beta_{j})}{A(\beta_{j})}\;\mbox{ for
all $1\leqslant j\leqslant K$.}$

One can check that $\widehat{R}A+\widehat{S}B\in\mathbb{C}_{N+K-1}[z]$ which
takes the values $P(\alpha_{i})$ at the roots of $A$ and $P(\beta_{j})$ at the
roots of $B$. The assumption of simplicity of the roots of $A$ and $B$ implies
that the total number of roots of $A$ and $B$ is precisely $N+K$. Therefore
$\widehat{R}A+\widehat{S}B$ takes the same values as $P$ at $N+K$ distinct
points. Since $\widehat{R}A+\widehat{S}B$ and $P$ are both polynomials of
degree at most $N+K-1$, they must coincide everywhere. This proves the
existence of $\widehat{R}$ and $\widehat{S}$.

To prove uniqueness, suppose that $\widehat{R}_{1},\widehat{S}_{1}$ were
another pair of polynomials satisfying the same conditions. Then

$A(z)(\widehat{R}(z)-\widehat{R}_{1}(z))+B(z)(\widehat{S}(z)-\widehat{S}_{1}(z))=0\;\mbox{for
all $z\in\mathbb{C}$.}$

For any $1\leqslant i\leqslant N$, observe that $A(\alpha_{i})=0$ while
$B(\alpha_{i})\not=0$. Therefore,
$\widehat{S}(\alpha_{i})=\widehat{S}_{1}(\alpha_{i})$. Since
$\widehat{S},\widehat{S}_{1}\in\mathbb{C}_{N-1}[z]$, they must coincide
everywhere. A similar argument shows that $\widehat{R}=\widehat{R}_{1}$, which
completes the proof. ∎

In particular, when $P(z)=z^{t}$ for some integer $0\leqslant t\leqslant
N+K-1$, we see, using (4.6) as well as formula (4.3), that the (unique)
solutions $\widehat{S}$ and $\widehat{R}$ (of appropriate degree) of the
Bézout type identity

(4.9) $A(z)\widehat{R}(z)+B(z)\widehat{S}(z)=z^{t}$

are given by

(4.10)
$\begin{split}\widehat{S}(z)&=\sum_{j=0}^{N-1}z^{j}\sum_{k=j+1}^{N}a_{k}\frac{1}{2\pi
i}\int_{{\Gamma}_{1}}\frac{\zeta^{t+k-j-1}}{{A}(\zeta){B}(\zeta)}\,d\zeta,\\\
\widehat{R}(z)&=\sum_{j=0}^{K-1}z^{j}\sum_{k=j+1}^{K}{b}_{k}\frac{1}{2\pi
i}\int_{{\Gamma}_{2}}\frac{\zeta^{t+k-j-1}}{{A}(\zeta){B}(\zeta)}\,d\zeta.\end{split}$

##  5\. A weak form of the main result

In this section we show how the description of the solutions of (4.9), given
by (4.10), may be used to obtain estimates for the coefficients of the
polynomials $R$ and $S$ in (1.2). Although these estimates are not sufficient
to yield Theorem 2.10, since they depend on the size of the roots of $A$ and
$B$, the proof is much simpler. This weaker version gives a feeling of the
general case and is enough to give the bounds on the norm of the inverse of
the Sylvester matrix (see Theorem 6.4 below).

Recall that we consider two polynomials $A$ and $B$ of respective degrees $N$
and $K$, that is, $A(z)=\sum_{k=0}^{N}a_{k}z^{k}$,
$B(z)=\sum_{k=0}^{K}b_{k}z^{k}$. We also assume $\|A\|,\|B\|\leqslant 1$. The
roots of $A$ are denoted by $\\{\alpha_{i}\\}_{i=1}^{N}$ and the roots of $B$
by $\\{\beta_{j}\\}_{j=1}^{K}$. We start with a lemma which will allow us to
reduce to the case when both $A$ and $B$ have simple roots.

######  Lemma 5.1.

Let $A\in\mathbb{C}_{N}[z]$, $B\in\mathbb{C}_{K}[z]$ satisfy
$\|A\|,\|B\|\leqslant 1$. Then there exist
$A_{n}\in\mathbb{C}_{N}[z],B_{n}\in\mathbb{C}_{K}[z]$, all with distinct
roots, such that

  1. (i)

$\|A_{n}\|\leqslant 1$ and $\|B_{n}\|\leqslant 1$ for all $n$;

  2. (ii)

$A_{n}\to A$, $B_{n}\to B$, and

  3. (iii)

$\delta(A_{n},B_{n})\to\delta(A,B)$.

###### Proof.

Write

$A(z)=a_{N}(z-\alpha_{1})\dots(z-\alpha_{N})\;\;\mbox{and}\;\;B(z)=b_{K}(z-\beta_{1})\dots(z-\beta_{K}),$

where we do not assume that the roots $\alpha_{1},\alpha_{2},\dots,\alpha_{N}$
are different and similarly for $\beta_{1},\beta_{2},\dots\beta_{K}$. Take
sequences $\alpha_{1}^{(n)},\alpha_{2}^{(n)},\dots,\alpha_{N}^{(n)}$ such that
for all $1\leqslant i\leqslant N$, $\alpha_{i}^{(n)}\to\alpha_{i}$ when
$n\to\infty$ and for all $1\leqslant i,s\leqslant N$, $i\neq s$, and
$n\geqslant 1$, $\alpha_{i}^{(n)}\neq\alpha_{s}^{(n)}$. Similarly, take
sequences $\beta_{1}^{(n)},\beta_{2}^{(n)},\dots,\beta_{N}^{(n)}$ such that
for all $1\leqslant j\leqslant K$, $\beta_{j}^{(n)}\to\beta_{j}$ when
$n\to\infty$ and for all $1\leqslant j,\ell\leqslant K$, $j\neq\ell$, and
$n\geqslant 1$, $\beta_{j}^{(n)}\neq\beta_{\ell}^{(n)}$. If

$A_{n}^{\sharp}(z):=a_{N}(z-\alpha_{1}^{(n)})\dots(z-\alpha_{N}^{(n)})\;\;\mbox{and}\;\;B_{n}^{\sharp}(z):=b_{K}(z-\beta^{(n)}_{1})\dots(z-\beta^{(n)}_{K}),$

define

$A_{n}=\frac{\|A\|}{\|A_{n}^{\sharp}\|}A_{n}^{\sharp}\quad\mbox{and}\quad
B_{n}=\frac{\|B\|}{\|B_{n}^{\sharp}\|}|B_{n}^{\sharp}.$

By construction, $A_{n}$ and $B_{n}$ have both simple roots and satisfy
$\|A_{n}\|\leqslant 1$ and $\|B_{n}\|\leqslant 1$. Moreover, by Viete’s
formula, $\|A_{n}-A\|\to 0$ and $\|B_{n}-B\|\to 0$ as $n\to\infty$. Finally,
from $\alpha_{i}^{(n)}\to\alpha_{i}$ and $\beta_{j}^{(n)}\to\beta_{j}$ it
follows that $\delta(A_{n},B_{n})\to\delta(A,B)$. ∎

We now need to find appropriate contours $\Gamma_{1},\Gamma_{2}$ to apply to
Corollary 4.4. Returning to the notation in Lemma 3.3, we have

(5.2) $L(A,\frac{\delta}{3^{N}})\subseteq
E_{A}\;\;\mbox{and}\;\;L(B,\frac{\delta}{3^{K}})\cap E_{A}=\varnothing.$

In particular, $\alpha_{i}\in E_{A}$ for all $1\leqslant i\leqslant N$.

In the definition of $E_{A}$, we may apply the distributivity of the (outer)
intersection with respect to the (inner) union to obtain

(5.3) $E_{A}=\bigcup_{1\leqslant i_{1},\dots,i_{K}\leqslant
N}\Omega_{i_{1}i_{2}\dots i_{K}},$

where

(5.4) $\Omega_{i_{1}i_{2}\dots
i_{K}}:=\bigcap_{j=1}^{K}D(\alpha_{i_{j}},\tfrac{1}{3}|\alpha_{i_{j}}-\beta_{j}|).$

As the $N^{K}$ sets $\Omega_{i_{1}i_{2}\dots i_{K}}$ are intersections of
disks, the boundary of $E_{A}$ is formed by a finite number of circular arcs
and is therefore a rectifiable system of closed contours. Let
$\operatorname{len}$ denote the length of such a curve. Since

$\partial
E_{A}\subseteq\bigcup_{i_{1},\dots,i_{K}}\partial\Omega_{i_{1}i_{2}\dots
i_{K}},$

we have

(5.5) $\operatorname{len}(\partial
E_{A})\leqslant\sum_{i_{1},\dots,i_{K}}\operatorname{len}(\partial\Omega_{i_{1}i_{2}\dots
i_{K}}).$

Define $\Gamma_{1}$ to be $\partial E_{A}$ oriented such that its index with
respect to points in $E_{A}$ is 1, while it is 0 with respect to points
outside $\overline{E_{A}}$ (see Figure 3). In particular, this applies to the
points $\alpha_{i}\in E_{A}$ and $\beta_{j}\notin\overline{E_{A}}$ (recall
Remark 3.11).

In a similar way, $\Gamma_{2}$ will be the boundary of $E_{B}$, appropriately
oriented (see Figure 3). Using Remark 3.11 again, it follows that if
$\zeta\in\Gamma_{1}\cup\Gamma_{2}$, then $|A(\zeta)|\geqslant\delta/3^{N}$ and
$|B(\zeta)|\geqslant\delta/3^{K}$.

In order to estimate the length of the contours discussed above, we will need
the following folklore result (see [5, Ch. 1] for a precise reference).

######  Lemma 5.6.

If $G_{1}$ and $G_{2}$ are open convex sets with $G_{1}\subseteq G_{2}$, then
$\operatorname{len}(\partial G_{1})\leqslant\operatorname{len}(\partial
G_{2})$.

Figure 3. The sets $E_{A}$ and $E_{B}$ from Figure 1 with boundaries oriented.
The contour $\Gamma_{1}=\partial E_{A}$ (bottom – in two pieces) surrounds the
zeros of $A$, while $\Gamma_{2}=\partial E_{B}$ (top - in one piece) surrounds
the zeros of $B$. Recall that $A$ is the monic polynomial whose roots are
$(\alpha_{1},\alpha_{2},\alpha_{3})=(\tfrac{1}{4}+\tfrac{i}{8},-\tfrac{1}{2},\tfrac{2}{5})$
and $B$ is the monic polynomial whose zeros are
$(\beta_{1},\beta_{2},\beta_{3},\beta_{4})=(\tfrac{1}{9}+\tfrac{5}{6}i,\tfrac{1}{8}+\tfrac{i}{2},\tfrac{i}{3},\tfrac{i}{5})$.

######  Lemma 5.7.

For all $1\leqslant i\leqslant N$ and $1\leqslant j\leqslant K$, suppose that
$|\alpha_{i}|,|\beta_{j}|\leqslant M$ for some $M>0$. Fix $\ell\in\mathbb{N}$.
With the notation above, there is a constant $C_{1}>0$, depending only on $N$
and $K$, such that

(5.8)
$\left|\int_{\Gamma_{s}}\frac{\zeta^{\ell}}{A(\zeta)B(\zeta)}d\zeta\right|\leqslant\frac{C_{1}M^{\ell+1}}{\delta^{2}},\quad
s=1,2.$

###### Proof.

The hypothesis says that $|\alpha_{i}-\beta_{j}|\leqslant 2M$ for all $i$ and
$j$, and so $E_{A}\subseteq D(0,5M/3)$. By Lemma 5.6, we have

$\operatorname{len}(\partial\Omega_{i_{1}i_{2}\dots i_{K}})\leqslant
2\pi\frac{5M}{3}\;\;\mbox{for every $i_{1},\dots,i_{K}$.}$

Then (5.5) yields

$\operatorname{len}(\Gamma_{1})\leqslant\frac{10\pi MN^{K}}{3},$

and therefore,

$\left|\int_{\Gamma_{1}}\frac{\zeta^{\ell}}{A(\zeta)B(\zeta)}d\zeta\right|\leqslant\frac{10\pi
MN^{K}}{3}\left(\frac{5M}{3}\right)^{\ell}\frac{3^{N+K}}{\delta^{2}}.$

This proves (5.8) for $\Gamma_{1}$. A similar argument is used for
$\Gamma_{2}$. ∎

As a consequence, one obtains a weaker form of Theorem 2.10, where the bounds
on the coefficients of $R$ and $S$ depend on the size of the zeros of $A,B$.

######  Theorem 5.9.

Let $A$ and $B$ be two polynomials of respective degrees $N$ and $K$. Suppose
that $\|A\|,\|B\|\leqslant 1$ and their roots are bounded in modulus by $M>0$.
If $\delta(A,B)>0$, then there is $C(N,M,K)>0$ such that the unique minimal
polynomials $R\in\mathbb{C}_{K-1}[z]$ and $S\in\mathbb{C}_{N-1}[z]$ from (1.2)
satisfy

$\|R\|,\|S\|\leqslant\frac{C(N,K,M)}{\delta^{2}}.$

###### Proof.

By Lemma 2.6 and Lemma 5.1 we can assume that the roots of $A$ and $B$ are
simple. From (4.10) (when $t=0$), it follows that
$S(z)=\sum_{j=0}^{N-1}s_{j}z^{j},$ with

$s_{j}=\sum_{k=j+1}^{N}a_{k}\frac{1}{2\pi
i}\int_{\Gamma_{1}}\frac{\zeta^{k-j-1}}{A(\zeta)B(\zeta)}d\zeta.$

Since $|a_{k}|\leqslant 1$, Lemma 5.7 yields the desired estimate for $\|S\|$.
A similar argument estimates $\|R\|$. ∎

It is worth pointing out that simple examples show that even though $\|A\|$
and $\|B\|$ are bounded by $1$, their roots can be arbitrarily large.

Before proceeding with the next two sections, it is worth reminding the reader
of our standing assumption that the constants $C_{1},C_{2},\dots$ that will
appear in the estimates below always depend only on $N$ and $K$ and not on the
coefficients of $A\in\mathbb{C}_{N}[z]$ and $B\in\mathbb{C}_{K}[z]$.

##  6\. Intermezzo—the Sylvester matrix

In this section, we show how Lemma 5.7 can be used to obtain an estimate of
the norm of the inverse of the Sylvester matrix. To see this, consider a
general polynomial

$P(z)=p_{0}+p_{1}z+\dots+p_{N+K-1}z^{N+K-1}$

and the Bézout type equation

(6.1) $A(z)R(z)+B(z)S(z)=P(z).$

Suppose that, as above, $A$ and $B$ have no common roots. Using the notation
in Section 2, the identity in (6.1) translates into the system of $N+K$
equations

(6.2) $\mathfrak{S}(A,B)\bf x=\bf p,$

where $\mathfrak{S}(A,B)$ is the $(N+K)\times(N+K)$ Sylvester matrix

(6.3) $\mathfrak{S}(A,B)=\left[\begin{array}[]{rrrrrrrr}a_{0}&&&&b_{0}&&&\\\
a_{1}&a_{0}&&&b_{1}&b_{0}&&\\\ a_{2}&a_{1}&\ddots&&b_{2}&b_{1}&\ddots&\\\
\vdots&&\ddots&a_{0}&\vdots&&\ddots&b_{0}\\\ &\vdots&&a_{1}&&\vdots&&b_{1}\\\
a_{N}&&&&b_{K}&&&\\\ &a_{N}&&\vdots&&b_{K}&&\vdots\\\ &&\ddots&&&&\ddots&\\\
\makebox[0.0pt][l]{$\smash{\underbrace{\phantom{\begin{matrix}&&&a_{N}\end{matrix}}}_{\text{$K\text{
columns}$}}}$}&&&a_{N}&\makebox[0.0pt][l]{$\smash{\underbrace{\phantom{\begin{matrix}&&&b_{K}\end{matrix}}}_{\text{$N\text{
columns}$}}}$}&&&b_{K}\end{array}\right],$

$\mathbf{x}=[r_{0},r_{1},\cdots,r_{K-1},s_{0},s_{1},\cdots,s_{N-1}]^{T},$

and

$\mathbf{p}=[p_{0},p_{1},\ldots,p_{N+K-1}]^{T}.$

######  Theorem 6.4.

Let $A$ and $B$ are two polynomials of respective degree $N$ and $K$, with
$\|A\|,\|B\|\leqslant 1$, $\delta=\delta(A,B)$ is given by (2.2), and let

$M=\max(\|A\|/|a_{N}|,\|B\|/|b_{K}|).$

There is a constant $C_{3}>0$ (depending only on $N$ and $K$) such that if
$\mathfrak{S}=\mathfrak{S}(A,B)$ denotes the Sylvester matrix of $A$ and $B$,
then

(6.5)
$\|\mathfrak{S}^{-1}\|\leqslant\frac{C_{3}M^{N+K+\max(N,K)-1}}{\delta^{2}}.$

###### Proof.

By Lemma 2.6 and Lemma 5.1 we can assume that the roots of $A$ and $B$ are
simple.

From a classical result of Cauchy (for instance, see [8, p. 167]) it follows
that the roots of $A$ (denoted by $\\{\alpha_{i}\\}_{i=1}^{N}$) and $B$
(denoted by $\\{\beta_{j}\\}_{j=1}^{K}$) satisfy the inequality

(6.6) $|\alpha_{i}|,|\beta_{j}|\leqslant 1+M\leqslant 2M.$

For each $0\leqslant\ell\leqslant N+K-1$, let $R^{(\ell)},S^{(\ell)}$ denote
the solution of (6.2) corresponding to $P(z)=z^{\ell}$. If $\mathfrak{R}$
denotes the $(N+K)\times(N+K)$ matrix with columns

$[r^{(\ell)}_{0},\dots,r^{(\ell)}_{K-1},s^{(\ell)}_{0},\dots,s^{(\ell)}_{N-1}]^{T},\quad
0\leqslant\ell\leqslant N+K-1,$

it follows from (6.2) that $\mathfrak{S}\mathfrak{R}=I_{N+K}$, and therefore
$\mathfrak{R}=\mathfrak{S}^{-1}$.

To prove the theorem, we need to estimate the coefficients $r^{(\ell)}_{i}$
and $s^{(\ell)}_{j}$, for $0\leqslant\ell\leqslant N+K-1$, $0\leqslant
i\leqslant N-1$ and $0\leqslant j\leqslant K-1$. If we fix
$0\leqslant\ell\leqslant N+K-1$, applying the formulas from (4.10), we have

$s^{(\ell)}_{j}=\sum_{k=j+1}^{N}a_{k}\frac{1}{2i\pi}\int_{\Gamma_{1}}\frac{\zeta^{\ell+k-j-1}}{A(\zeta)B(\zeta)}\,d\zeta.$

It follows from Lemma 5.7 that

$|s^{(\ell)}_{j}|\leqslant\sum_{k=j+1}^{N}|a_{k}|\frac{C_{1}}{\delta^{2}}(2M)^{\ell+k-j}\leqslant\frac{C_{1}}{\delta^{2}}\sum_{k=j+1}^{N}(2M)^{\ell+k-j}\leqslant\frac{NC_{1}}{\delta^{2}}(2M)^{\ell+N-j}.$

Now use the fact that $\ell+N-j\leqslant N+K+\max(N,K)-1$ and $M\geqslant 1$,
which gives that

$|s^{(\ell)}_{j}|\leqslant\frac{C_{3}M^{N+K+\max(N+K)-1}}{\delta^{2}}.$

Similar estimates hold for $|r^{(\ell)}_{i}|$, and we thus get (6.5). Notice
the use of the fact that $\|\mathfrak{S}^{-1}\|$ is equivalent to the maximum
of its entries $|r_{i}^{(\ell)}|$ and $|s_{j}^{(\ell)}|$ since all norms on a
finite dimensional Banach space are equivalent. ∎

######  Remark 6.7.

If one removes the hypothesis of $\|A\|,\|B\|\leqslant 1$, one can make small
adjustments to the proof of Theorem 6.4 to obtain the estimate

$\|\mathfrak{S}^{-1}\|\leqslant\frac{C_{3}M^{N+K+\max(N,K)-1}\max(\|A\|,\|B\|)}{\delta^{2}}.$

######  Remark 6.8.

It is natural for the estimate of $\|\mathfrak{S}^{-1}\|$ to depend on the
leading coefficients $|a_{N}|$ and $|b_{K}|$. To see this, take
$A(z)=az,B(z)=az+1$. Then $\delta=1$, and

$\mathfrak{S}=\begin{bmatrix}0&1\\\
a&a\end{bmatrix},\quad\mathfrak{S}^{-1}=\begin{bmatrix}-1&a^{-1}\\\
\phantom{-}1&0\end{bmatrix}.$

Thus, $\big{\|}\mathfrak{S}^{-1}\big{\|}$ becomes unbounded as $a\to 0$. Note
that this example also shows that for $t>0$ one cannot expect bounds for
$\widehat{R}$ and $\widehat{S}$ from (4.9) in terms only of $\delta$.

##  7\. Finding convenient contours

We return now to our main purpose, that of proving Theorem 2.10. To obtain
better estimates than those given in Section 5, we need to use Corollary 4.4
more delicately. The most important step is an appropriate choice of the
contours $\Gamma_{1}$ and $\Gamma_{2}$. This is the goal of this section. We
will only discuss the construction for $\Gamma_{1}$ since the construction of
$\Gamma_{2}$ is analogous.

For sufficiently small $\varepsilon$, depending on $N$ and $K$, there are
$N+K+1$ disjoint closed disks of radius $2\varepsilon$ inside $\mathbb{D}$. It
follows that at least one of these disks does not contain any of the roots of
$A$ or $B$. Indeed, suppose it is $\overline{D(z_{0},2\varepsilon)}$ for a
suitable $z_{0}\in\mathbb{D}$.

Now replace $A(z)$ and $B(z)$ by $A(z+z_{0})$ and $B(z+z_{0})$ and notice that

$\delta(A,B)=\delta(A(\cdot+z_{0}),B(\cdot+z_{0})),$

while

(7.1) $\|A(\cdot+z_{0})\|,\|B(\cdot+z_{0})\|\leqslant C_{4},$

where $C_{4}$ depends only on $N,K$. From now on, we will assume that
$\overline{D(0,2\varepsilon)}$ does not contain any of the zeros of $A$ or
$B$.

Also observe that the equivalence of norms on finite dimensional Banach spaces
(with constants depending only on the dimension), applied to
$\mathbb{C}_{N}[z]$, yields

$\|A\|_{\varepsilon}:=\sup_{|z|\leqslant\varepsilon}|A(z)|\geqslant
C_{5}\|A\|$

for some $C_{5}>0$. By the maximum principle, one can choose a
$z_{1}\in\partial D(0,\varepsilon)$ such that

$|A(z_{1})|=\sup_{|z|\leqslant\epsilon}|A(z)|.$

If $z\in\mathbb{C}$ satisfies
$|z-\alpha_{i}|\geqslant\tfrac{1}{2}|\alpha_{i}-z_{1}|$ for every $1\leqslant
i\leqslant N$, then the previous inequality shows that

(7.2)
$|A(z)|=\Big{|}a_{N}\prod_{i=1}^{N}(z-\alpha_{i})\Big{|}\geqslant\Big{|}a_{N}\prod_{i=1}^{N}\tfrac{1}{2}(z_{1}-\alpha_{i})\Big{|}=|A(z_{1})|2^{-N}\geqslant
C_{5}\|A\|2^{-N}.$

Since $|z_{1}|=\varepsilon\leqslant\tfrac{1}{2}|\alpha_{i}|$, we have
$\tfrac{1}{2}|\alpha_{i}-z_{1}|\leqslant\tfrac{1}{2}(|\alpha_{i}|+\varepsilon)\leqslant\frac{3}{4}|\alpha_{i}|$.

Let

$D_{i}:=D\big{(}\alpha_{i},\tfrac{3}{4}|\alpha_{i}|\big{)}\;\;\mbox{and}\;\;D_{A}:=\bigcup_{i=1}^{N}D_{i}.$

Each $z\not\in D_{A}$ satisfies

$|z-\alpha_{i}|\geqslant\tfrac{1}{2}|\alpha_{i}-z_{1}|\;\mbox{for every
$1\leqslant i\leqslant N$}.$

From (7.2) it follows that $L(A,C_{5}\|A\|2^{-N})\subseteq D_{A}$ (Recall the
definition of the sub-level set $L(A,\cdot)$ from (3.2)).

Since $|\alpha_{i}|>2\varepsilon$ for all $1\leqslant i\leqslant N$, the
triangle inequality says that if $z\in D_{i}$, then
$|z|\geqslant\tfrac{1}{4}|\alpha_{i}|\geqslant\tfrac{1}{2}\varepsilon$. Thus

(7.3) $|z|\geqslant\frac{\varepsilon}{2}\text{ for all }z\in\overline{D_{A}}.$

Now define the sets

$F_{A}^{(i)}:=E_{A}\cap D_{i}\quad\mbox{and}\quad F_{A}:=E_{A}\cap
D_{A}=\bigcup_{i=1}^{N}F_{A}^{(i)}.$

In light of (5.4), $F_{A}^{(i)}$ is a union of at most $N^{K}$ intersections
of disks. Each of these intersections is contained in $D_{i}$ and thus Lemma
5.6 says that the length of its boundary is bounded above by
$\operatorname{len}(\partial D_{i})=2\pi\frac{3}{4}|\alpha_{i}|$. Therefore,

(7.4) $\operatorname{len}(\partial F_{A}^{(i)})\leqslant\frac{3\pi
N^{K}}{2}|\alpha_{i}|\;\;\mbox{for all $1\leqslant i\leqslant N$}.$

We define the new system of contours $\Gamma_{1}$ by

$\Gamma_{1}:=\partial(D_{A}\cap E_{A}).$

Since $\alpha_{i}\in D_{i}$, and we already know that $\alpha_{i}\in E_{A}$
(see Remark 3.11), it follows that $\alpha_{i}\in D_{A}\cap E_{A}$ for all
$i$. On the other hand, $\beta_{j}\notin\overline{E_{A}}$ (also by Remark
3.11) and so $\beta_{j}\notin\overline{D_{A}\cap E_{A}}$ for all $j$.
Therefore, we may orient $\Gamma_{1}$ such that its index is $1$ for any
$\alpha_{i}$ and $0$ for any $\beta_{j}$ (An example appears in Figures 4 and
5).

Figure 4. The regions $E_{A}$ (black) and $D_{A}$ (gray) with the zeros
$\\{\alpha_{i}\\}_{i=1}^{3}$ of $A$ and the zeros $\\{\beta_{j}\\}_{j=1}^{4}$
of $B$. Here
$(\alpha_{1},\alpha_{2},\alpha_{3})=(\tfrac{1}{3},-0.2+0.34641i,-0.2-0.34641i)$
and $(\beta_{1},\beta_{2},\beta_{3},\beta_{4})=(1,i,-1,-i)$. Figure 5. The
system of curves $\Gamma_{1}=\partial(E_{A}\cap D_{A})$ for the example in
Figure 4, with the zeros $\\{\alpha_{i}\\}_{i=1}^{3}$ of $A$ inside
$\Gamma_{1}$ and the zeros $\\{\beta_{j}\\}_{j=1}^{4}$ of $B$ outside
$\Gamma_{1}$. Recall that
$(\alpha_{1},\alpha_{2},\alpha_{3})=(\tfrac{1}{3},-0.2+0.34641i,-0.2-0.34641i)$
and $(\beta_{1},\beta_{2},\beta_{3},\beta_{4})=(1,i,-1,-i)$.

Recalling the proof of Theorem 5.9, it would be natural to estimate the length
of $\Gamma_{1}$ as well as the values of $A$ and $B$ on $\Gamma_{1}$. However,
one can see that the length of $\Gamma_{1}$ depends on the absolute values of
the roots $\alpha_{i}$ and $\beta_{j}$ (which can be very large). The method
we will use in Section 8 circumvents this problem by using another system of
contours $\widetilde{\Gamma}_{1}$ defined by

$\widetilde{\Gamma}_{1}:=\Big{\\{}\frac{1}{z}:z\in\Gamma_{1}\Big{\\}}.$

This is well defined, since $0\notin\Gamma_{1}$. As inversion is a
homeomorphism, $\widetilde{\Gamma}_{1}$ is the boundary of

$\Big{\\{}\frac{1}{z}:z\in D_{A}\cap E_{A}\Big{\\}},$

which is also a finite union of circular arcs. Moreover, as we will use this
in Section 8, we may orient $\widetilde{\Gamma}_{1}$ such that its index with
respect to $1/\alpha_{i}$ is 1 for all $1\leqslant i\leqslant N$, while the
index with respect to $1/\beta_{j}$ is 0 for all $1\leqslant j\leqslant K$.

This next result contains the basic estimates that will be used in the proof
of Theorem 2.10.

######  Lemma 7.5.

With the notation above, the following hold:

  * (i)

There is a constant $C_{6}>0$, depending only on $N$ and $K$, such that

${\displaystyle\int_{\Gamma_{1}}\frac{|du|}{|u|}\leqslant C_{6}}.$

  * (ii)

For all $z\in\Gamma_{1}$, we have that

$|B(z)|\geqslant\delta/3^{K}\;\;\mbox{and}\;\;|A(z)|\geqslant
m:=\min\\{C_{5}\|A\|/2^{N},\delta/3^{N}\\}.$

###### Proof.

(i): For each $1\leqslant i\leqslant N$ let

$\Gamma_{1,i}=\partial F_{A}^{(i)}.$

Clearly we have $\Gamma_{1}\subseteq\bigcup_{i=1}^{N}\Gamma_{1,i}$. If
$u\in\Gamma_{1,i}$, then $|u-\alpha_{i}|\leqslant\tfrac{3}{4}|\alpha_{i}|$ and
therefore,

(7.6)
$|u|\geqslant|\alpha_{i}|-|u-\alpha_{i}|\geqslant\tfrac{1}{4}|\alpha_{i}|.$

Hence, by (7.4), we have

$\int_{\Gamma_{1,i}}\frac{|du|}{|u|}\leqslant\frac{\frac{3\pi
N^{K}}{2}|\alpha_{i}|}{\tfrac{1}{4}|\alpha_{i}|}=6\pi N^{K}$

and thus,

(7.7)
$\int_{\Gamma_{1}}\frac{|du|}{|u|}\leqslant\sum_{i=1}^{N}\int_{\Gamma_{1,i}}\frac{|du|}{|u|}\leqslant
6\pi N^{K+1}=:C_{6}.$

(ii): If $z\in\Gamma_{1}$, then either $z\in\partial D_{A}$, in which case
(7.2) yields $|A(z)|\geqslant C_{5}\|A\|/2^{N}$, or $z\in\partial E_{A}$, in
which case $|A(z)|\geqslant\delta/3^{N}$. Since
$\Gamma_{1}\subseteq\overline{E_{A}}$, and $E_{A}$ is disjoint from $E_{B}$,
we see that $|B|\geqslant\delta/3^{K}$ on $\Gamma_{1}$. ∎

Note that the constant $m$, defined in (ii), is not a constant depending only
on $N$ and $K$, since it also depends on $\|A\|$.

##  8\. Proof of the main result

As noted above, we have no control of the size of the zeros of $A$ and $B$.
However, the assumptions made in Section 7 imply that their inverses are
bounded: $|\alpha_{i}|,|\beta_{j}|\geqslant 2\varepsilon$ implies that

$\frac{1}{|\alpha_{i}|},\frac{1}{|\beta_{j}|}\leqslant\frac{1}{2\varepsilon}.$

This is the basis of the proof that follows.

###### Proof of Theorem 2.10.

Once again, by Lemma 2.6 and Lemma 5.1 we can assume that the roots of $A$ and
$B$ are simple. Define

$\widetilde{A}(z)=z^{N}A(1/z)\;\;\mbox{and}\;\;\widetilde{B}(z)=z^{K}B(1/z).$

Notice that $\|\widetilde{A}\|=\|A\|$ and $\|\widetilde{B}\|=\|B\|$ since the
coefficients of $\widetilde{A}$ are the reverse of those of $A$ (and similarly
for $\widetilde{B}$). Moreover, the roots of $\widetilde{A}$ are
$\widetilde{\alpha}_{i}:=1/\alpha_{i}$ while the roots of $\widetilde{B}$ are
$\widetilde{\beta}_{j}:=1/\beta_{j}$.

Applying Corollary 4.4 when $P(z)=z^{N+K-1}$, one produces polynomials
$\widetilde{R}\in\mathbb{C}_{K-1}[z]$ and
$\widetilde{S}\in\mathbb{C}_{N-1}[z]$ which satisfy the modified Bézout
equation

(8.1)
$\widetilde{A}(z)\widetilde{R}(z)+\widetilde{B}(z)\widetilde{S}(z)=z^{N+K-1},$

and, according to to (4.10), applied to the case $t=N+K-1$, they are given by
the formulas

(8.2)
$\begin{split}\widetilde{S}(z)&=\sum_{j=0}^{N-1}z^{j}\sum_{k=j+1}^{N}\widetilde{a}_{k}\frac{1}{2\pi
i}\int_{\widetilde{\Gamma}_{1}}\frac{\zeta^{N+K+k-j-2}}{\widetilde{A}(\zeta)\widetilde{B}(\zeta)}\,d\zeta,\\\
\widetilde{R}(z)&=\sum_{j=0}^{K-1}z^{j}\sum_{k=j+1}^{K}\widetilde{b}_{k}\frac{1}{2\pi
i}\int_{\widetilde{\Gamma}_{2}}\frac{\zeta^{N+K+k-j-2}}{\widetilde{A}(\zeta)\widetilde{B}(\zeta)}\,d\zeta.\end{split}$

Let us estimate the integrals above. We have

$\int_{\widetilde{\Gamma}_{1}}\frac{\zeta^{N+K+k-j-2}}{\widetilde{A}(\zeta)\widetilde{B}(\zeta)}\,d\zeta=\int_{\widetilde{\Gamma}_{1}}\frac{\zeta^{k-j-2}}{{A}(1/\zeta){B}(1/\zeta)}\,d\zeta=\int_{\Gamma_{1}}\frac{1}{u^{k-j}A(u)B(u)}\,du,$

where for the last equality we have made the change of variable $u=1/\zeta$.

Applying Lemma 7.5 (ii), it follows that

$\Big{|}\widetilde{a}_{k}\int_{\widetilde{\Gamma}_{1}}\frac{\zeta^{N+K+k-j-2}}{\widetilde{A}(\zeta)\widetilde{B}(\zeta)}\,d\zeta\Big{|}\leqslant\frac{|\widetilde{a}_{k}|}{m\delta/3^{K}}\int_{\Gamma_{1}}\frac{|du|}{|u|^{k-j}}\leqslant\frac{3^{K}\|A\|}{m\delta}\int_{\Gamma_{1}}\frac{|du|}{|u|^{k-j}}.$

Since $\Gamma_{1}\subseteq\overline{D_{A}}$, (7.3) implies that
$|u|\geqslant\varepsilon/2$ for all $u\in\Gamma_{1}$. Therefore applying Lemma
7.5 and noting that $k-j-1\geqslant 0$, yields

$\displaystyle\int_{\Gamma_{1}}\frac{|du|}{|u|^{k-j}}$
$\displaystyle=\int_{\Gamma_{1}}\frac{|du|}{|u||u|^{k-j-1}}\leqslant\left(\frac{2}{\varepsilon}\right)^{k-j-1}\int_{\Gamma_{1}}\frac{|du|}{|u|}$
$\displaystyle\leqslant
C_{6}\left(\frac{2}{\varepsilon}\right)^{\max(N,K)-1}=:C_{7}.$

Thus,

$\Big{|}\widetilde{a}_{k}\int_{\widetilde{\Gamma}_{1}}\frac{\zeta^{N+K+k-j-2}}{\widetilde{A}(\zeta)\widetilde{B}(\zeta)}\,d\zeta\Big{|}\leqslant
C_{7}\frac{3^{K}\|A\|}{m\delta}$

and so

$|s_{j}|\leqslant\frac{NC_{7}3^{K}\|A\|}{m\delta}\;\;\mbox{for all $0\leqslant
j\leqslant K-1$.}$

Recall that

$m=\min\\{C_{5}\|A\|/2^{N},\delta/3^{N}\\}.$

When $m=C_{5}\|A\|/2^{N}$, it follows using (3.14) that

$|s_{j}|\leqslant\frac{NC_{7}3^{K}2^{N}}{C_{5}\delta}\leqslant\frac{NC_{7}3^{K}2^{N}T}{C_{5}\delta^{2}}.$

When $m=\delta/3^{N}$, taking into account that, by (7.1), $\|A\|\leqslant
C_{4}$ , we obtain

$|s_{j}|\leqslant\frac{NC_{7}C_{4}3^{N+K}}{\delta^{2}}.$

Thus, in all cases

(8.3) $|s_{j}|\leqslant\frac{C_{8}}{\delta^{2}}\;\;\mbox{for all $1\leqslant
j\leqslant N-1$}$

for some constant $C_{8}>0$.

The estimates are similar for the integral on $\Gamma_{2}$, and so all
coefficients of $\widetilde{R}$ and $\widetilde{S}$ are bounded by
$C_{9}\delta^{-2}$, where $C_{9}$ depends only on $N$ and $K$.

Now observe that (8.1) can be written as

$z^{N}A(1/z)\widetilde{R}(z)+z^{K}B(1/z)\widetilde{S}(z)=z^{N+K-1}.$

Dividing by $z^{N+K-1}$ we obtain

$A(1/z)\widetilde{R}(z)/z^{K-1}+B(1/z)\widetilde{S}(z)/z^{N-1}=1.$

Replacing $z$ with $1/z$ yields

$A(z)z^{K-1}\widetilde{R}(1/z)+B(z)z^{N-1}\widetilde{S}(1/z)=1.$

Setting $R(z)=z^{K-1}\widetilde{R}(1/z)$ and $S(z)=z^{N-1}\widetilde{S}(1/z)$
gives us

$A(z)R(z)+B(z)S(z)=1.$

Thus $R$ and $S$ are the solutions of the desired Bézout equation. Since the
coefficients of $R$ and $S$ are those of $\widetilde{R}$ and $\widetilde{S}$
in reverse order, it follows that $\|R\|,\|S\|\leqslant C_{9}\delta^{-2}$. The
proof of the theorem, at least when the roots of $A$ and $B$ are simple, is
now finished by setting $C=C_{9}$.

As observed earlier, the assumption that $A$ and $B$ have simple roots can be
removed by Lemma 2.6. This completes the proof of Theorem 2.10. ∎

##  9\. Examples

In this section, we give three examples. The first one shows the optimality of
our estimates. The second one discusses the necessity of the assumption that
$\|A\|,\|B\|\leqslant 1$ in Theorem 2.10. The last one shows that the
functions $\delta$ and $\widetilde{\delta}$ (from (2.1) and (2.3)) are not
continuous.

######  Example 9.1.

For $N\in\mathbb{N}$ let $w=e^{2\pi i/(2N-1)}$ and $0<a<1$. A calculation
shows that

$z^{2N-1}-a^{2N-1}=\prod_{j=1}^{2N-1}(z-aw^{j}),$

from which one derives the Bézout identity $AR+BS=1$ with

$A(z)=z^{N},\quad R(z)=\frac{1}{a^{2N-1}}z^{N-1},$
$B(z)=\prod_{j=1}^{N}(z-aw^{j}),\quad\mbox{and}\quad
S(z)=-\frac{1}{a^{2N-1}}\prod_{j=N+1}^{2N-1}(z-aw^{j}).$

Here $\delta=a^{N}$ and the unique nonzero coefficient of $R$ has modulus
$\delta^{-2+1/N}$. This shows that the exponent of $\delta$ in an estimate for
$\|R\|$ and $\|S\|$ must be at least $\delta^{-2+1/N}$.

### Open problem

Is

$C\delta^{-2+\frac{1}{\max(N,K)}}$

the best possible estimate for $\|R\|$ and $\|S\|$?

######  Example 9.2.

With $A$ and $B$ as in the previous example, define

$A_{1}=a^{-2}A\quad\mbox{and}\quad B_{1}=a^{-2}B.$

Observe that $\|A_{1}\|,\|B_{1}\|\to\infty$ when $a\to 0$. Then
$R_{1}=a^{2}R$, $S_{1}=a^{2}S$ (the solutions to Bézout’s identity for $A_{1}$
and $B_{1}$), and

$\delta(A_{1},B_{1})=a^{-2}\delta(A,B)=a^{N-2}.$

The unique nonzero coefficient of $R_{1}$ is

$r^{(1)}_{N-1}=a^{2}a^{1-2N}=a^{-2N+3}.$

Furthermore, since $0<a<1$, we have $\delta(A_{1},B_{1})<1$. Then

$r^{(1)}_{N-1}\delta(A_{1},B_{1})^{2}=a^{-2N+3}a^{2N-4}=a^{-1}.$

The last quantity is not bounded independently of $a$. This shows that in
Theorem 2.10, without the condition that $\|A\|,\|B\|\leqslant 1$, there is no
constant $C>0$ such that

$\|R\|\leqslant C\delta^{-2}.$

######  Example 9.3.

Let $A(z)=z$, $B(z)=1-z$. Then $\delta(A,B)=1$ and
$\widetilde{\delta}(A,B)=\tfrac{1}{2}$. Let

$A_{n}=z+\frac{1}{n}z^{2}\quad\mbox{and}\quad
B_{n}(z)=1-z-\left(\frac{1}{n}+\frac{1}{n^{2}}\right)z^{2}.$

Observe that $\|A_{n}-A\|=\frac{1}{n}\to 0$ and
$\|B_{n}-B\|=\frac{1}{n}+\frac{1}{n^{2}}\to 0$ as $n\to\infty$. Clearly the
zeros of $A_{n}$ are $0$ (which is the zero of $A$) and $-n$ (which goes to
infinity). Then

$0\leqslant\widetilde{\delta}(A_{n},B_{n})\leqslant\delta(A_{n},B_{n})\leqslant|B_{n}(-n)|=0,$

which implies that $\delta(A_{n},B_{n})=\widetilde{\delta}(A_{n},B_{n})=0$.
This shows that both $\delta$ and $\widetilde{\delta}$ are not continuous at
$(A,B)$.

##  10\. Final remarks

###  10.1. An extension

In our main theorem, one can relax the assumption that $\|A\|,\|B\|\leqslant
1$ and prove a similar type of result but with bounds depending on the norm of
$A$ and $B$. To see this, take arbitrary polynomials $A$ and $B$ and set
$M=\max(\|A\|,\|B\|)$. Now apply Theorem 2.10 to the polynomials $A_{1}=A/M$
and $B_{1}=B/M$ to obtain

$\delta(A_{1},B_{1})=\frac{\delta(A,B)}{M},\quad R_{1}=MR,\quad\mbox{and}\quad
S_{1}=MS.$

Therefore,

$\|R\|\leqslant\frac{C\max(\|A\|,\|B\|)}{\delta(A,B)^{2}}\;\;\mbox{and}\;\;\|S\|\leqslant\frac{C\max(\|A\|,\|B\|)}{\delta(A,B)^{2}}.$

###  10.2. A related problem

The paper [12] considers the related problem of estimating the solutions of
the corona problem in $H^{\infty}$ when the initial data are polynomials.
However, our results are not directly comparable to those in [12]. First, the
starting problem is not the same since the initial lower bound therein is
equivalent to

$\delta^{\prime}(A,B)=\inf_{z\in\mathbb{D}}\\{|A(z)|+|B(z)|\\}.$

Clearly $\widetilde{\delta}(A,B)\leqslant\delta^{\prime}(A,B)$. However, the
example on [12, p. 422] shows that these quantities are not equivalent.
Secondly, the resulting solutions $R,S$ to (1.2) obtained in [12] are rational
functions (not necessarily polynomials) and moreover, the estimates for
$\|R\|$ and $\|S\|$ are of order

$\left(\frac{1}{\delta^{\prime}(A,B)}\log\frac{1}{\delta^{\prime}(A,B)}\right)^{2}.$

This is known to be a good, though not necessarily the best, estimate for the
solutions of the corona problem in $H^{\infty}$.

###  10.3. Varying the degrees of $A,B$

As stated from the beginning, the various constants that appear in our results
depend only on $N=\operatorname{deg}A$ and $K=\operatorname{deg}B$ (and not
the coefficients of $A$ and $B$). If we let $N$ and $K$ increase, one can see
that our methods produce constants that increase quite rapidly in $N$ and $K$
(see (7.7) for example). For possible numerical applications, it would be
interesting to explore the optimal estimates of these constants as functions
of $N$ and $K$.

###  10.4. Generalizing to more than two polynomials

Bézout’s polynomial identity from (1.2) generalizes to more than two
polynomials in that if $A_{1},\dots,A_{q}\in\mathbb{C}[z]$ have no common
zeros, then there exist $R_{1},\dots,R_{q}\in\mathbb{C}[z]$ with $\deg
R_{i}\leqslant\max\\{\deg A_{j}\\}-1$ such that
$A_{1}R_{1}+\dots+A_{q}R_{q}=1$ (see, for instance, [15, Section 1.3]).
However, our methods do not extend to provide estimates of $\|R_{i}\|$ when
$q\geqslant 3$. Note that when $q\geqslant 3$, the solutions $R_{i}$ are no
longer unique, even if we put restrictions on their degree.

### Open problem

Suppose that $A_{1},\dots,A_{q}\in\mathbb{C}[z]$ have no common zeros, and
define

$\delta=\min\Big{\\{}\sum_{i=1}^{q}|A_{i}(z)|:z\in\mathbb{C},\prod_{i=1}^{q}A_{i}(z)=0\Big{\\}}.$

Prove there exists a constant $C>0$, depending only on $\max\\{\deg A_{i}\\}$,
such that one can find $R_{1},\dots,R_{q}\in\mathbb{C}[z]$ with
$A_{1}R_{1}+\dots+A_{q}R_{q}=1$ and

$\max_{0\leqslant i\leqslant q}\|R_{i}\|\leqslant\frac{C}{\delta^{2}}.$

## Acknowledgements

We are indebted to Laurent Baratchart for pointing out the problem of
estimating the norm of the inverse of the Sylvester matrix.

Emmanuel Fricain was supported the Labex CEMPI (ANR-11-LABX -0007-01). Andreas
Hartmann was supported by the Project REPKA (ANR-18-CE40-0035). Dan Timotin
was partially supported by a grant of the Ministry of Research, Innovation and
Digitization, CNCS/CCCDI – UEFISCDI, Project Number PN-III-P4-ID-
PCE-2020-0458, within PNCDI III.

## References

  * [1] Carlos A. Berenstein, Roger Gay, Alekos Vidras, and Alain Yger.  Residue currents and Bezout identities, volume 114 of Progress in Mathematics.  Birkhäuser Verlag, Basel, 1993.
  * [2] Carlos A. Berenstein and Alain Yger.  Effective Bezout identities in ${\bf Q}[z_{1},\cdots,z_{n}]$.  Acta Math., 166(1-2):69–120, 1991.
  * [3] Étienne Bézout.  Théorie générale des équations algébrique.  Paris, France, 1779.
  * [4] Lennart Carleson.  Interpolations by bounded analytic functions and the corona problem.  Ann. of Math. (2), 76:547–559, 1962.
  * [5] Isaak M. Jaglom and Vladimir G. Boltjanskiĭ.  Convex figures.  Holt, Rinehart and Winston, New York, 1960.  Translated by Paul J. Kelly and Lewis F. Walton.
  * [6] Hyun-Kyoung Kwon, Anupan Netyanun, and Tavan T. Trent.  An estimate for the degree bound of a matrix of polynomials.  Complex Anal. Oper. Theory, 12(1):101–109, 2018.
  * [7] Serge Lang.  Algebra, volume 211 of Graduate Texts in Mathematics.  Springer-Verlag, New York, third edition, 2002.
  * [8] Themistocles M. Rassias, editor.  Survey on classical inequalities, volume 517 of Mathematics and its Applications.  Kluwer Academic Publishers, Dordrecht, 2000.
  * [9] Marvin Rosenblum.  A corona theorem for countably many functions.  Integral Equations Operator Theory, 3(1):125–137, 1980.
  * [10] Vadim A. Tolokonnikov.  Estimates in the Carleson corona theorem, ideals of the algebra $H^{\infty}$, a problem of Sz.-Nagy.  Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 113:178–198, 267, 1981.  Investigations on linear operators and the theory of functions, XI.
  * [11] Sergei Treil.  Estimates in the corona theorem and ideals of ${H^{\infty}}$: a problem of T. Wolff.  J. Anal. Math., 87:481–495, 2002.
  * [12] Tavan T. Trent.  An algorithm for corona solutions on ${H}^{\infty}(\mathbb{D})$.  Integral Equations Operator Theory, 59:421–435, 2007.
  * [13] Akihito Uchiyama.  Corona theorems for countably many functions and estimates for their solutions,.  preprint, UCLA, 1980.
  * [14] Alekos Vidras and Alain Yger.  Multidimensional Residue Theory and Applications, volume 275 of Mathematical Surveys and Monographs.  American Mathematical Society, 2023.
  * [15] Alain Yger.  Trace, residue currents and multidimensional residues, duality and division.  https://cel.archives-ouvertes.fr/cel-00281761, 2008.