# Amalgamation of real zero polynomials

David Sawall<EMAIL_ADDRESS>and  Markus Schweighofer
<EMAIL_ADDRESS>Fachbereich Mathematik und Statistik,
Universität Konstanz, 78457 Konstanz, Germany

(Date: July 28, 2023)

###### Abstract.

With this article, we hope to launch the investigation of what we call the
_Real Zero Amalgamation Problem_. Whenever a polynomial arises from another
polynomial by substituting zero for some of its variables, we call the second
polynomial an _extension_ of the first one. The _Real Zero Amalgamation
Problem_ asks when two (multivariate real) polynomials have a common extension
(called _amalgam_) that is a real zero polynomial. We show that the obvious
necessary conditions are not sufficient. Our counterexample is derived in
several steps from a counterexample to amalgamation of matroids by Poljak and
Turzík. On the positive side, we show that even a degree-preserving
amalgamation is possible in three very special cases with three completely
different techniques. Finally, we conjecture that amalgamation is always
possible in the case of two shared variables. The analogue in matroid theory
is true by another work of Poljak and Turzík. This would imply a very weak
form of the Generalized Lax Conjecture.

##  1\. Introduction

Throughout the article, we denote by $\mathbb{N}$, $\mathbb{N}_{0}$,
$\mathbb{R}$, $\mathbb{R}_{\geq 0}$ and $\mathbb{R}_{>0}$ the set of positive
and nonnegative integers, the real, real nonnegative and real positive
numbers, respectively. We consider three tuples $x=(x_{1},\ldots,x_{\ell})$,
$y=(y_{1},\ldots,y_{m})$ and $z=(z_{1},\ldots,z_{n})$ of $\ell+m+n$ distinct
variables for some $\ell,m,n\in\mathbb{N}_{0}$. If $\ell=1$, then we sometimes
write $x$ instead of $x_{1}$, similarly for $y$ and $z$. Furthermore, we will
often consider an additional variable $s$ or $t$ when we consider univariate
polynomials or when we homogenize multivariate polynomials.

Let $p\in\mathbb{R}[x,y]$ and $q\in\mathbb{R}[x,z]$ be polynomials. We call a
polynomial $r\in\mathbb{R}[x,y,z]$ an _amalgam_ of $p$ and $q$ if $p=r(x,y,0)$
and $q=r(x,0,z)$. It is trivial that an amalgam of $p$ and $q$ exists if and
only if the compatibility condition $p(x,0)=q(x,0)$ holds. We will however ask
for amalgams having certain properties. All the properties we will consider
will be preserved by setting some of the variables to zero. Hence we will have
to require in addition that $p$ and $q$ have this property.

Our main interest lies in the property of being a _real zero polynomial_ [HV,
Vin] but on the way we will also deal with the property of being _stable_
[Pem, Wag]. A real polynomial in $n$ variables is called _real zero_ if it
does not vanish at the origin and its restriction along any line in
$\mathbb{R}^{n}$ through the origin (seen as a real univariate polynomial) is
real-rooted (i.e. has no non-real complex roots).

In Version 2 (posted on March 1, 2020) of the preprint [Sc2], the second
author showed by three completely different techniques in the following three
special cases that real zero polynomials $p\in\mathbb{R}[x,y]$ and
$q\in\mathbb{R}[x,z]$ with $p(x,0)=q(x,0)$ can be amalgamated by a real zero
polynomial $r$ with the additional property that the (total) degree of $r$
does not exceed the maximum degree of $p$ and $q$:

  1. (a)

$\ell=0$, i.e., if there are no shared variables,

  2. (b)

$\ell=m=n=1$, i.e., if each block of variables consists just of a single
variable,

  3. (c)

$p$ and $q$ are quadratic, i.e., of degree at most $2$.

We decided to move this material over to this article. For (a), we will use
the theory of stability preservers of Borcea and Brändén [BB1], for (b) the
solution to the Lax Conjecture by Helton and Vinnikov [HV] and for (c)
positive semidefinite matrix completion of Grone, Johnson, de Sá and Wolkowicz
[GJSW].

In the same preprint of the second author, it was conjectured that two
(compatible) real zero polynomials can always be amalgamated (by a real zero
polynomial). The first author recently disproved this after discussions with
the second author. This is the main result of this paper. Concretely, let
$e_{3}\in\mathbb{R}[x_{1},\ldots,x_{6},y]$ be the third elementary symmetric
polynomial in the seven variables $x_{1},\ldots,x_{6},y$ (here $\ell:=6$ and
$m:=n:=1$). Consider the polynomials

$p:=e_{3}-yx_{1}x_{4}-yx_{3}x_{6}-yx_{2}x_{5}-x_{1}x_{2}x_{3}-x_{4}x_{5}x_{6}\in\mathbb{R}[x,y]$

and

$q:=e_{3}(x,z)-zx_{1}x_{4}-zx_{2}x_{5}-x_{1}x_{2}x_{3}-x_{4}x_{5}x_{6}\in\mathbb{R}[x,z].$

We show that the polynomials $p(x+\mathbf{1},y)$ and $q(x+\mathbf{1},z)$ are
real zero and do not have a real zero amalgam although
$p(x+\mathbf{1},0)=q(x+\mathbf{1},0)$ where $\mathbf{1}$ always denotes the
all-ones vector of appropriate length.

This counterexample will rely on matroid theory and the theory of stable
polynomials. Namely, we will first consider the problem of amalgamating two
matroids [Oxl, Section 11.4]. It is well known in matroid theory that this is
not always possible. We will take a counterexample from Poljak and Turzík from
[PT2] and consider the bases generating polynomials $p$ and $q$ of the
matroids.

We will show that the considered polynomials are stable using a criterion from
Wagner and Wei [WW]. If there were a multi-affine homogeneous stable amalgam
of $p$ and $q$ then by [COSW, Theorem 7.1] its support would be an
amalgamating matroid of the matroids considered in [PT2]. This will give us
that there is no homogeneous stable amalgam of $p$ and $q$. We will then show
that the matroids Poljak and Turzík considered do not even have an amalgam as
delta-matroids in the sense of Bouchet [Bou1]. From this, we get that there is
no multi-affine stable amalgam of our bases generating polynomials because the
support of a multi-affine stable polynomial forms a delta-matroid [Brä1]. We
even get that our polynomials do not have a stable amalgam by using that the
multi-affine part of a stable polynomial is again stable. Lastly, we use the
theory of real zero polynomials and the fact that $p$ and $q$ do not have a
stable amalgam to show that $p(x+\mathbf{1},y)$ and $q(x+\mathbf{1},z)$ are
real zero and do not have a real zero amalgamating polynomial.

Knowing now that real zero amalgamation does not work under the obvious
minimal requirements (contrary to what the second author conjectured in
Version 2 of [Sc2]), the question is what could potentially be an additional
hypothesis that always allows for real zero amalgamation. Although, we are not
able to give an answer for now, we allow ourselves to speculate and search
again for inspiration in matroid theory. Poljak and Turzík introduce in their
earlier work [PT1] the notion of a _sticky_ matroid which is by definition a
matroid over which amalgamation is always possible. They showed that _modular
matroids_ [Oxl, Section 6.9] are sticky and conjectured the converse. Very
recently, Shin was able to prove this conjecture which was known under the
name of _sticky matroid conjecture_ [Shi]. This raises the question what would
be the “sticky real zero polynomials”. It is easy to check that all matroids
over a two-element ground set are modular. Hence for sure, a counterexample
which is of the same nature of the one we present here will not exist in the
case of $\ell=2$ shared variables. We will conjecture therefore that real zero
amalgamation over two shared variables is always possible. By (Version 2 of)
[Sc2] this would imply the following very weak form of the Generalized Lax
Conjecture: Given a rigidly convex set (the closure of the connected component
of the origin in the real non-vanishing set of a real zero polynomial which is
known to be always convex) and a union of finitely many planes through the
origin (a two-dimensional subspace), there is a spectrahedron containing the
rigidly convex set and agreeing with it on the finite union. One can think of
this as wrapping a rigidly convex set into a spectrahedron and “tying it with
cords”. The Generalized Lax Conjecture is much stronger and even says that
each rigidly convex set is a spectrahedron.

##  2\. Real zero and stable polynomials

Our main interest lies in real zero polynomials. They have been introduced in
[HV, Subsection 2.1] but are just a non-homogeneous version of the more
popular (homogeneous) hyperbolic polynomials going back to Gårding [Går1]
which originally arose in the study of partial differential equations and
later got popular in convex optimization [Ren]. For the proofs, we will need
in addition the more recently investigated (real) stable polynomials [BB1,
BB2, BB3, Wag] having applications in dynamical systems, probability theory
[Pem] and computer science [OSS].

######  Definition 2.1.

We call a univariate polynomial $f\in\mathbb{R}[t]$ _real-rooted_ if all its
complex roots are real, i.e., it is non-zero and splits into linear factors in
$\mathbb{R}[t]$ (in particular, the zero polynomial is not real-rooted). Now
let $p\in\mathbb{R}[x]$ be a multivariate polynomial. We call $p$

  1. (a)

_real zero_ if $p(ta)\in\mathbb{R}[t]$ is real-rooted for all
$a\in\mathbb{R}^{\ell}$,

  2. (b)

_stable_ if $p(ta+b)\in\mathbb{R}[t]$ is real-rooted for all
$a\in\mathbb{R}_{>0}^{\ell}$ and $b\in\mathbb{R}^{\ell}$

Since we speak only about _real_ stable polynomials, we chose a definition in
(b) above that avoids talking about complex numbers. This definition is
however equivalent to the one given in [BB1] (making use of the open upper
half plane in the complex numbers) by [BB1, Lemma 2.5]. By considering $a=0$
in (a), it follows easily that real zero polynomials do not vanish at the
origin. Also note that the zero polynomial is neither real zero nor stable
according to our definition (whereas the zero polynomial is declared to be
stable by some other authors [Wag]).

######  Remark 2.2.

The following are obvious:

  1. (a)

A univariate polynomial is real-rooted if and only if it is stable.

  2. (b)

Any product of real zero polynomials is again real zero.

  3. (c)

Any product of stable polynomials is again stable.

  4. (d)

If $p\in\mathbb{R}[x]$ is stable then so is $p(x+a)$ for all
$a\in\mathbb{R}^{\ell}$.

######  Example 2.3.

  1. (a)

Let $p\in\mathbb{R}[x]$ be a quadratic real zero polynomial with $p(0)=1$.
Then $p$ can be uniquely written as

$p=x^{T}Ax+b^{T}x+1$

with a symmetric matrix $A\in\mathbb{R}^{\ell\times\ell}$ and a vector
$b\in\mathbb{R}^{\ell}$. For $a\in\mathbb{R}^{\ell}$ the univariate quadratic
polynomial $p(ta)=a^{T}Aat^{2}+b^{T}at+1$ splits in $\mathbb{R}[t]$ if and
only if its discriminant $(b^{T}a)^{2}-4a^{T}Aa=a^{T}(bb^{T}-4A)a$ is is
nonnegative. Hence $p$ is a real zero polynomial if and only if the symmetric
matrix $bb^{T}-4A$ is positive semidefinite.

  2. (b)

The quadratic polynomial $1-x_{1}^{2}-x_{2}^{2}$ is real zero but not stable.

  3. (c)

The quadratic polynomial $x_{1}x_{2}-1$ is stable but not real zero.

The following is folklore and easy to prove but we record it here because of
its importance:

######  Proposition 2.4.

Let $A_{1},\ldots,A_{\ell}\in\mathbb{R}^{d\times d}$ be symmetric matrices.
Then the polynomial

$\det(I_{d}+x_{1}A_{1}+\ldots+x_{\ell}A_{\ell})$

is real zero.

###### Proof.

This follows easily from the fact that all complex eigenvalues of real
symmetric matrices are real and that a univariate polynomial is real-rooted if
and only if its reciprocal is real-rooted. ∎

Helton and Vinnikov proved by deep methods that surprisingly for $\ell=2$
variables the following converse to Proposition 2.4 holds [HV] (see also [Han,
Subsection 5] for a more algebraic but yet difficult proof). For $\ell=1$, the
corresponding statement is trivial and $A_{1}$ can even be chosen diagonal.
For $\ell>2$, the converse of Proposition 2.4 in this sense is in general very
far from being true [Brä2].

######  Theorem 2.5 (Helton and Vinnikov).

If $p\in\mathbb{R}[x_{1},x_{2}]$ is a real zero polynomial of degree $d$ with
$p(0)=1$, then there exist symmetric $A_{1},A_{2}\in\mathbb{R}^{d\times d}$
such that

$p=\det(I_{d}+x_{1}A_{1}+x_{2}A_{2}).$

A weaker version of this theorem where real symmetric matrices are replaced by
(complex) hermitian matrices would be enough for our purposes. This weaker
version seems to be considerably easier to prove (see mainly [GKVW], also [PV]
and [Han, Section 7]). Proposition 2.4 obviously also continues to hold for
hermitian matrices instead of real symmetric ones. In general, we could work
throughout the article with hermitian matrices if we replaced certain
integrals over the orthogonal group with the corresponding integral over the
unitary group. For ease of notation, we restrict our exposition to the real
case.

For our counterexamples in Sections 5 and 6 to stable and real zero
amalgamation, we will need to consider multi-affine parts of stable
polynomials in the following sense:

######  Definition 2.6.

For $\alpha\in\mathbb{N}_{0}^{\ell}$, we denote

$x^{\alpha}:=x_{1}^{\alpha_{1}}\dotsm x_{\ell}^{\alpha_{\ell}}.$

For any polynomial

$p=\sum_{\alpha\in\mathbb{N}_{0}^{\ell}}a_{\alpha}x^{\alpha}$

where all but finitely many of the $a_{\alpha}\in\mathbb{R}$ are zero, we
define its _multi-affine part_

$\operatorname{MAP}(p):=\sum_{\alpha\in\\{0,1\\}^{\ell}}a_{\alpha}x^{\alpha}.$

We call $p\in\mathbb{R}[x]$ _multi-affine_ if $p=\operatorname{MAP}(p)$. For a
multi-affine $p\in\mathbb{R}[x]$, it will be convenient for us to define its
_support_ in a slightly unusual way as

$\operatorname{supp}(p):=\\{\\{x_{i}\mid\alpha_{i}=1\\}\mid\alpha\in\\{0,1\\}^{\ell},a_{\alpha}\neq
0\\}$

The following theorem has first been observed by Choe, Oxley, Sokal and Wagner
[COSW, Proposition 4.17] (where the setup is slightly different but can easily
be adapted). Alternatively, it follows easily from the theory of linear
stability preservers [BB1, Page 542] due to Borcea and Brändén [BB1, Theorem
2.1] (see also [Wag, Theorem 5.2] and [Lea, Theorem 1.1]).

######  Theorem 2.7 (Choe, Oxley, Sokal and Wagner).

The multi-affine part of a stable polynomial is again stable unless it is the
zero polynomial.

The following example shows that the multi-affine part of a real zero
polynomial is in general not real zero.

######  Example 2.8.

The polynomial $p:=(1+x_{1}+x_{2})(1-x_{1}+2x_{2})$ is a real zero polynomial
but its multi-affine part $\operatorname{MAP}(p)=1+3x_{2}+x_{1}x_{2}$ is not
real zero since the quadratic univariate polynomial
$p(3t,t)=1+3t+3t^{2}\in\mathbb{R}[t]$ has negative discriminant $3^{2}-4\cdot
3\cdot 1$.

The following definition stems from [HV] but it is just a non-homogeneous
version of the well-known notion of a hyperbolicity cone [Går1, Går2, Ren].

######  Definition 2.9.

Let $p\in\mathbb{R}[x]$ be a real zero polynomial. The set

$C(p):=\\{a\in\mathbb{R}^{\ell}\mid p(ta)\neq 0\text{ for all }t\in(0,1)\\}$

is called the _rigidly convex_ set of $p$.

It is well-known although not obvious that $C(p)$ is indeed convex [HV,
Subsection 5.3] (a fact that we will crucially use in our counterexample 6.1
to real zero amalgamation) and is the closure of the connected component at
the origin of the complement of the real zero set of $p$ [HV, Subsection 2.2].
Moreover, even the following is true and essentially already due to Gårding
[Går2].

######  Proposition 2.10 (Gårding).

Let $p\in\mathbb{R}[x]$ be a real zero polynomial. Then $C(p)$ is convex and
for each $a$ in the interior of $C(p)$, the shifted polynomial $p(x+a)$ is
again a real zero polynomial with $C(p)=\\{a+b\mid b\in C(p(x+a))\\}$.

There are many connections and similarities between stable and real zero
polynomials. As an example, we give those two that we will need. These
following two propositions can certainly be found elsewhere in disguised form
or can be deduced easily from the literature. For convenience of the reader,
we state them in the form we need and give a proof.

######  Proposition 2.11.

Let $p\in\mathbb{R}[x]$ be homogeneous and stable and suppose
$a\in\mathbb{R}_{\geq 0}^{\ell}$ with $p(a)\neq 0$. Then $p(a+x)$ is a real
zero polynomial.

###### Proof.

Let $b\in\mathbb{R}^{\ell}$. We have to show that the univariate polynomial
$f:=p(a+tb)$ is real-rooted. Setting $d:=\deg p\in\mathbb{N}_{0}$, $f$ is
real-rooted if and only if

$g:=t^{d}f\left(\frac{1}{t}\right)=t^{d}p\left(a+\frac{b}{t}\right)=p(ta+b)$

is real-rooted (if $p(b)\neq 0$, this is the reciprocal polynomial of $f$,
otherwise it is the reciprocal polynomial times a power of $t$). It is easy to
see that there is a sequence $(a_{n})_{n\in\mathbb{N}}$ in
$\mathbb{R}_{>0}^{\ell}$ such that $\lim_{n\to\infty}a_{n}=a$ and
$p(a_{n})\neq 0$ for all $n\in\mathbb{N}$. By the stability of $p$, we have
that $g_{n}:=p(ta_{n}+b)$ is then for each $n\in\mathbb{N}$ a real-rooted
polynomial of degree $d$. By the continuity of roots [RS, Theorem 1.3.1] it
follows that $g=\lim_{n\to\infty}g_{n}$ is also a real-rooted polynomial. ∎

######  Proposition 2.12.

Let $p\in\mathbb{R}[x]$ be a real zero polynomial with $\mathbb{R}_{\geq
0}^{\ell}\subseteq C(p)$. Then $p$ is stable.

###### Proof.

Let $a\in\mathbb{R}_{>0}^{n}$ and $b\in\mathbb{R}^{n}$. We claim that
$p(ta+b)\in\mathbb{R}[t]$ is real-rooted. WLOG, we can suppose that
$b\in\mathbb{R}_{>0}^{\ell}$ for otherwise we replace $b$ by $b+\lambda a$ for
large enough $\lambda\in\mathbb{R}$. In particular, $b$ lies in the interior
of $C(p)$. But then $p(x+b)$ is a real zero polynomial by Proposition 2.10 and
the claim follows. ∎

The aim of this article is to advertise the following problem and to give
first positive and negative results on it:

######  Problem 2.13 (Real Zero Amalgamation Problem).

Suppose that $p\in\mathbb{R}[x,y]$ and $q\in\mathbb{R}[x,z]$ are real zero
polynomials with

$p(x,0)=q(x,0).$

When does there exist a real zero polynomial $r\in\mathbb{R}[x,y,z]$ such that

$r(x,y,0)=p\qquad\text{and}\qquad r(x,0,z)=q\qquad?$

When $r$ as in Problem 2.13 exists, we call it an _amalgam_ of the real zero
polynomials $p$ and $q$. Without the conditions that $p$ and $q$ are real zero
or without the _compatibility condition_ $p(x,0)=q(x,0)$ such an amalgam could
obviously not exist. In March 2020, the second author released a preprint (the
second version of [Sc2]) where he conjectured that no other condition is
needed. In Section 6 we will disprove this. In Section 7, we will motivate why
it could possibly still be true for the case of $\ell=2$ shared variables
$x_{1}$ and $x_{2}$. By [Sc2], this would still imply a very weak form of the
long-standing Generalized Lax Conjecture [HV, Subsection 6.1] saying that each
rigidly convex set is a spectrahedron, i.e., the solution set of a linear
matrix inequality. This weak form says the following: Given a rigidly convex
set and finitely many planes through the origin (i.e., two-dimensional
subspaces), one can find a spectrahedron containing the rigidly convex set
that agrees with the rigidly convex set on the union of these planes.

##  3\. Some sufficient conditions for real zero amalgamation

In this section, we prove some positive results concerning the Real Zero
Amalgamation Problem 2.13. We start with some very special situations where
amalgamation is obviously possible.

######  Remark 3.1.

The Real Zero Amalgamation Problem 2.13 is of course solvable in the case
where $p$ and $q$ have simultaneous determinantal representations

$\displaystyle p$
$\displaystyle=\det(I_{d}+x_{1}A_{1}+\ldots+x_{\ell}A_{\ell}+y_{1}B_{1}+\ldots+y_{m}B_{m})\qquad\text{and}$
$\displaystyle q$
$\displaystyle=\det(I_{d}+x_{1}A_{1}+\ldots+x_{\ell}A_{\ell}+z_{1}C_{1}+\ldots+z_{n}C_{n})$

with symmetric matrices $A_{i},B_{j},C_{k}\in\mathbb{C}^{d\times d}$
(“simultaneous” refers here to having the same $A_{i}$ for both $p$ and $q$)
since then

$r:=\det(I_{d}+x_{1}A_{1}+\ldots+x_{\ell}A_{\ell}+y_{1}B_{1}+\ldots+y_{m}B_{m}+z_{1}C_{1}+\ldots+z_{n}C_{n})$

is a real zero polynomial (in fact, even of degree at most $d$) by Proposition
2.4.

The next observation is that the case $\ell=0$ is trivial.

######  Remark 3.2.

For $\ell=0$, i.e., in the absence of shared variables, the Real Zero
Amalgamation Problem 2.13 becomes trivial. This is because essentially the
product works, more exactly

$r:=\frac{pq}{p(0)}=\frac{pq}{q(0)}$

is a real zero amalgam by Remark 2.2(b). Of course, the degree of the amalgam
$r$ will here in general exceed the degrees of $p$ and $q$.

While we have absolutely no idea of how to generalize the trivial idea in
Remark 3.2 to the case $\ell>0$, we have a certain hope that the idea of the
degree preserving amalgamation of simultaneous determinantal representations
from Remark 3.1 could be adapted to a more general case, say where
$p(x,0)=q(x,0)$ has a determinantal representation

$p(x,0)=q(x,0)=\det(I_{d}+x_{1}A_{1}+\ldots+x_{\ell}A_{\ell})$

with real symmetric $A_{i}\in\mathbb{R}^{d\times d}$ which is always the case
for $\ell=2$ by the Helton-Vinnikov theorem 2.5 after assuming WLOG
$p(0)=q(0)=1$.

We know however only how to carry out this degree-preserving adaption in the
case $\ell=0$ which is already covered by the non-degree-preserving
amalgamation in Remark 3.2. The starting point is Remark 3.4 below. It is a
variant of Remark 3.1 which we do not know how to generalize to the case
$\ell>0$. Before we state it, we introduce some notation.

######  Notation 3.3.

For any polynomial $p\in\mathbb{R}[x]$ and $i\in\\{1,\ldots,\ell\\}$, we
denote by $\partial_{x_{i}}$ the linear operator on $\mathbb{R}[x]$ that maps
a polynomial to its partial derivative with respect to $x_{i}$. For
$k\in\mathbb{N}_{0}$ and $i\in\\{1,\ldots,\ell\\}$, $\partial_{x_{i}}^{k}$ is
the $k$-fold application of this differential operator.

Unfortunately, we do not know how to generalize the approach of Remark 3.4 to
$\ell>0$, i.e., to the case with shared variables.

######  Remark 3.4.

If $\ell=0$ and $p$ and $q$ have determinantal representations

$\displaystyle p$
$\displaystyle=\det(I_{d}+y_{1}B_{1}+\ldots+y_{m}B_{m})\qquad\text{and}$
$\displaystyle q$ $\displaystyle=\det(I_{d}+z_{1}C_{1}+\ldots+z_{n}C_{n})$

with symmetric matrices $B_{j},C_{k}\in\mathbb{C}^{d\times d}$ then it will
turn out that the polynomial

$\displaystyle r:=$
$\displaystyle\int_{O_{d}}\det(I_{d}+y_{1}B_{1}+\ldots+y_{m}B_{m}+U^{T}(z_{1}C_{1}+\ldots+z_{n}C_{n})U)\;dU$
$\displaystyle=$
$\displaystyle\int_{O_{d}}\det(I_{d}+U^{T}(y_{1}B_{1}+\ldots+y_{m}B_{m})U+z_{1}C_{1}+\ldots+z_{n}C_{n})\;dU$
$\displaystyle=$
$\displaystyle\int_{O_{d}}\int_{O_{d}}\det(I_{d}+U^{T}(y_{1}B_{1}+\ldots+y_{m}B_{m})U+V^{T}(z_{1}C_{1}+\ldots+z_{n}C_{n})V)\;dU\;dV$

(of degree at most $d$) is a real zero polynomial. See Corollary 3.11 below.
The integrals here are all taken with respect to the Haar (probability)
measure on the orthogonal group $O_{d}$. These are integrals of vector-valued
functions with values in a finite-dimensional subspace of the vector space of
polynomials. Equivalently, you could say that the integral has to be
understood coefficient-wise. It is obvious that $r(y,0)=p$ and $r(0,z)=q$.

An obvious advantage of $r$ over the amalgamating polynomial

$\det(I_{d}+y_{1}B_{1}+\ldots+y_{m}B_{m}+z_{1}C_{1}+\ldots+z_{n}C_{n})$

from Remark 3.1 is that it depends less on the concrete determinantal
representations of $p$ and $q$. Namely, $r$ will not change if one exchanges
simultaneously all $B_{i}$ by $U^{T}B_{i}U$ and all $C_{j}$ by $V^{T}C_{j}V$
for some $U,V\in O_{d}$ (i.e., one takes conjugate determinantal
representations of $p$ and $q$).

In fact, a closer look shows that $r$ depends really only on $d$ and the
polynomials $p$ and $q$ rather than on their given determinantal
representations. Moreover, this is even true line by line. To see this, we fix
a direction $(b,c)\in\mathbb{R}^{m}\times\mathbb{R}^{n}$ and show that the
univariate polynomial $r(tb,tc)$ depends only on $d$ and the univariate
polynomials $p(tb)$ and $q(tc)$. Indeed $r(tb,tc)$ depends obviously only on
the (real) eigenvalues of the real symmetric matrices
$b_{1}B_{1}+\ldots+b_{m}B_{m}$ and $c_{1}C_{1}+\ldots+c_{n}C_{n}$ and their
multiplicities. But these eigenvalues and their multiplicities correspond to
the roots of the univariate polynomials $t^{d}p(-t^{-1}a)$ and
$t^{d}q(-t^{-1}b)$ and their multiplicities.

Since $r$ depends now only on $d$, $p$ and $q$, the strategy will now be to
make this dependance explicit and hope that it gives an idea of how to define
$r$ in case that $p$ or $q$ does not have a determinantal representation as
above. It will indeed turn out (see Theorem 3.8 below) that $r$ as above
arises as follows: Let $\tilde{p}:=s^{d}p(s^{-1}y)\in\mathbb{R}[s,y]$ and
$\tilde{q}:=t^{d}p(t^{-1}z)\in\mathbb{R}[t,z]$ denote the degree $d$
homogenizations of $p$ and $q$ with respect to new variables $s$ and $t$,
respectively. Then it will turn out that

$\tilde{r}:=\frac{1}{d!}\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}\tilde{p}\tilde{q}\in\mathbb{R}[s,t,y,z]$

lies in $\mathbb{R}[s+t,y,z]$ and that $r$ arises from $\tilde{r}$ by setting
“the variable” $s+t$ to $1$ (e.g., by substituting $1$ for one of $s$ and $t$
and $0$ for the other variable, or by substituting $\frac{1}{2}$ for each of
$s$ and $t$). This way of getting $r$ from $d$, $p$ and $q$ will serve as our
definition of the degree-preserving amalgamation in the general case $\ell=0$
even if $p$ and $q$ are real zero polynomials that do not have determinantal
representations as above. See the proof of Theorem 3.12(a) below.

The following lemma of Marcus, Spielman and Srivastava will be an important
ingredient for the proof of Theorem 3.8 below. The original proof [MSS2,
Theorem 2.11] is quite lengthy. We gave a different and more direct proof in
the first draft of this article. We are very grateful to the anonymous referee
who revealed that the statement simply follows immediately from polarization.

######  Lemma 3.5 (Marcus, Spielman and Srivastava).

Consider the polynomial ring $\mathbb{R}[s,t]$ in two single variables $s$ and
$t$. For all $d\in\mathbb{N}_{0}$ and
$a_{1},\ldots,a_{d},b_{1},\ldots,b_{d}\in\mathbb{C}$, we have

$\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}\prod_{\alpha=1}^{d}(s+a_{\alpha})\prod_{\beta=1}^{d}(t+b_{\beta})=\sum_{\sigma\in
S_{d}}\prod_{i=1}^{d}(s+t+a_{i}+b_{\sigma(i)}).$

###### Proof.

Both sides of the claimed identity are obviously multi-affine and symmetric in
the $a_{i}$ and also in the $b_{j}$. By polarization (see for example [Pem,
Subsection 5.3] or [Wag, Section 4]), one can therefore suppose that all of
the $a_{i}$ are the same and all of the $b_{j}$ are the same. But then an easy
calculation shows that the left hand side is just a binomial expansion of the
right hand side. ∎

A variant of the next lemma has been proven by Marcus, Spielman and Srivastava
[MSS1, Theorem 4.8]. Whereas we sum over the subgroup $S_{d}$ of $O_{d}$
consisting of the permutation matrices, they sum over a certain different
finite subgroup of $O_{d}$ and they assume $A$ and $D$ symmetric (although
they forgot to state this) instead of $A$ arbitrary and $D$ diagonal. They
need several pages to prove their result whereas we can provide a short proof
for ours.

######  Lemma 3.6.

Let $A,D,U\in\mathbb{R}^{d\times d}$ where $D$ is diagonal and $U$ is
orthogonal. Then

$\sum_{P\in S_{d}}\det(A+P^{T}DP)=\sum_{P\in S_{d}}\det(A+U^{T}P^{T}DPU).$

###### Proof.

Let $\lambda_{1},\ldots,\lambda_{d}\in\mathbb{R}$ be the consecutive diagonal
entries of $D$. For all $I\subseteq\\{1,\ldots,d\\}$ we write
$\lambda^{I}:=\prod_{i\in I}\lambda_{i}$ and $B_{I}$ for the matrix arising
from a square matrix $B$ of size $d$ by deleting all rows and columns indexed
by an element of $I$. An easy calculation shows that the left hand side of our
claimed equation equals

$\displaystyle\sum_{P\in S_{d}}\det(PAP^{T}+D)$ $\displaystyle=\sum_{P\in
S_{d}}\sum_{I\subseteq\\{1,\ldots,d\\}}(\det((PAP^{T})_{I}))\lambda^{I}$
$\displaystyle=\sum_{k=0}^{d}\sum_{\begin{subarray}{c}I\subseteq\\{1,\ldots,d\\}\\\
\\#I=k\end{subarray}}\sum_{P\in
S_{d}}(\det((PAP^{T})_{\\{1,\ldots,k\\}}))\lambda^{I}$
$\displaystyle=\sum_{k=0}^{d}\left(\sum_{P\in
S_{d}}\det((PAP^{T})_{\\{1,\ldots,k\\}})\right)\sum_{\begin{subarray}{c}I\subseteq\\{1,\ldots,d\\}\\\
\\#I=k\end{subarray}}\lambda^{I}$
$\displaystyle=\sum_{k=0}^{d}c_{k}\underbrace{\left(\sum_{\begin{subarray}{c}I\subseteq\\{1,\ldots,d\\}\\\
\\#I=k\end{subarray}}\det(A_{I})\right)}_{=:a_{k}}\sum_{\begin{subarray}{c}I\subseteq\\{1,\ldots,d\\}\\\
\\#I=k\end{subarray}}\lambda^{I}.$

where $c_{k}$ is the number of permutations on $d$ objects that maps the first
$k$ of these objects to $k$ prescribed other objects, i.e., $c_{k}:=k!(d-k)!$.
Now $a_{k}$ is the coefficient of $t^{k}$ in $\det(A+tI_{d})$ (up to sign it
is therefore the $k$-th coefficient of the characteristic polynomial of $A$).
If we exchange in this calculation $A$ by $UAU^{T}$, then $a_{k}$ will become
the coefficient of $t^{k}$ in $\det(UAU^{T}+tI_{d})=\det(A+tI_{d})$ and will
therefore not change. ∎

All we will need from the last lemma is the following immediate consequence.
Just like the last lemma, this corollary has a certain analogue in the work of
Marcus, Spielman and Srivastava [MSS1, Theorem 4.2]. The same authors give a
much more general variant in their later work [MSS2] where they prove for
example that $A$ can be allowed to be arbitrary instead of diagonal if one
averages on the left hand side over all _signed_ permutation matrices (in
[MSS2] see Theorem 2.10 in connection with Lemma 2.6 and Corollary 2.7,
compare also the proof of their Theorem 2.11, note also that the unitary group
$U_{d}$ can easily be replaced by the orthogonal group $O_{d}$). The latter
result implies obviously ours so that we attribute the result to them. Note
however again that our derivation of the special case we need has really been
much shorter.

######  Corollary 3.7 (Marcus, Spielman and Srivastava).

For all $A,D\in\mathbb{R}^{d\times d}$ with $D$ diagonal,

$\frac{1}{d!}\sum_{P\in S_{d}}\det(A+P^{T}DP)=\int_{O_{d}}\det(A+U^{T}DU)dU.$

Now we can reprove a slight variation of [MSS2, Theorem 1.2]. Our proof will
use directly Corollary 3.7 and Lemma 3.5 and therefore indirectly Lemma 3.6.
All this was just to explain that we are implementing the ideas of Remark 3.4.
This idea was to mimic the glueing of determinantal representations as in
Remark 3.1 also in some cases where these determinantal representations do not
exist by introducing the twist that consists in conjugating with an orthogonal
matrix. As explained before Remark 3.4, we do not know how to handle this in
the case $\ell>0$ where $p$ and $q$ have shared variables. If we could find a
variant of the following theorem for $\ell>0$, we suspect that it would lead
to other cases where real zero amalgamation is possible.

######  Theorem 3.8 (Marcus, Spielman and Srivastava).

Let $B_{1},\ldots,B_{m},C_{1},\ldots,C_{n}\in\mathbb{R}^{d\times d}$ be
symmetric matrices. Set

$\displaystyle p$
$\displaystyle:=\det(sI_{d}+y_{1}B_{1}+\ldots+y_{m}B_{m})\in\mathbb{R}[s,y]\qquad\text{and}$
$\displaystyle q$
$\displaystyle:=\det(tI_{d}+z_{1}C_{1}+\ldots+z_{n}C_{n})\in\mathbb{R}[t,z].$

Then

$\int_{O_{d}}\det((s+t)I_{d}+y_{1}B_{1}+\ldots+y_{m}B_{m}+U^{T}(z_{1}C_{1}+\ldots+z_{n}C_{n})U)\;dU\\\
=\frac{1}{d!}\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}pq\in\mathbb{R}[s,t,y,z].$

###### Proof.

By arguing pointwise, one easily reduces to the following variant of our
claim: Let $B,C\in\mathbb{R}^{d\times d}$ be symmetric. Set

$p:=\det(sI_{d}+B)\in\mathbb{R}[s]\qquad\text{and}\qquad
q:=\det(tI_{d}+C)\in\mathbb{R}[t].$

Then we claim that

$\int_{O_{d}}\det((s+t)I_{d}+B+U^{T}CU)\;dU\\\
=\frac{1}{d!}\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}pq\in\mathbb{R}[s,t].$

Here we can suppose WLOG $B$ and $C$ to be diagonal. Using Corollary 3.7, we
can rewrite the left hand side of our claim which then gets

$\sum_{P\in
S_{d}}\det((s+t)I_{d}+B+P^{T}CP)=\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}pq.$

But this holds due to Lemma 3.5 since $B$ and $C$ are both diagonal. ∎

This following lemma follows (just as Theorem 2.7 above) again easily from the
theory of linear stability preservers [BB1, Page 542] due to Borcea and
Brändén [BB1, Theorem 2.1] (see also [Wag, Theorem 5.2] and [Lea, Theorem
1.1]).

######  Lemma 3.9 (Borcea and Brändén).

If $p\in\mathbb{R}[s,t]$ is stable, then

$\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}p$

is again stable.

###### Proof.

See [BB2, Theorem 3.4] or [BB2, Lemma 6.1]. ∎

All what we will need from the last lemma is the following fact that was
already known (in a disguised form) to Walsh more than a hundred years ago
(see the last footnote in [Wal], see also [RS, Section 5.3]).

######  Corollary 3.10 (Walsh).

If $p,q\in\mathbb{R}[s]$ are real-rooted, then

$\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}p(s)q(t)\in\mathbb{R}[s+t]$

is again real-rooted when viewed as a univariate polynomial in $s+t$.

The form in which we will need this for Part (a) of Theorem 3.12 below is as
follows:

######  Corollary 3.11.

Let $d\in\mathbb{N}_{0}$ and let $p\in\mathbb{R}[y]$ and $q\in\mathbb{R}[z]$
be real zero polynomials of degree at most $d$. Denote by
$\tilde{p}:=s^{d}p(s^{-1}y)\in\mathbb{R}[s,y]$ and
$\tilde{q}:=t^{d}q(t^{-1}z)\in\mathbb{R}[t,z]$ their degree $d$
homogenizations. Then

$\tilde{r}:=\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}\tilde{p}\tilde{q}\in\mathbb{R}[s,t,y,z]$

lies in $\mathbb{R}[s+t,y,z]$ and becomes a real zero polynomial $r$ in
$\mathbb{R}[y,z]$ after substituting $s+t$ by $1$.

###### Proof.

From Lemma 3.5 it follows that $\tilde{r}\in\mathbb{R}[s+t,y,z]$. To prove
that $r$ is a real zero polynomial, we fix $b\in\mathbb{R}^{m}$ and
$c\in\mathbb{R}^{n}$ and show that the univariate polynomial
$r(tb,tc)\in\mathbb{R}[t]$ which is of degree at most $d$ is real-rooted. But
this is equivalent to $t^{d}r(t^{-1}b,t^{-1}c)\in\mathbb{R}[t]$ being real-
rooted. But this latter polynomial equals

$t^{d}\tilde{r}(1,0,t^{-1}b,t^{-1}c)=t^{d}\tilde{r}(0,1,t^{-1}b,t^{-1}c).$

Now observe that $\tilde{r}$ is homogeneous of degree $d$ since
$\tilde{p}\tilde{q}$ is homogeneous of degree $2d$. We therefore have

$t^{d}\tilde{r}(0,1,t^{-1}b,t^{-1}c)=\tilde{r}(0,t,b,c)$

and this polynomial is real-rooted as desired by Corollary 3.10 applied to
$\tilde{p}(s,b)$ and $\tilde{q}(t,c)$. ∎

We are now able to prove our three positive results on real zero amalgamation
where we use for each case another non-trivial ingredient, namely the theory
of stability preservers, the Helton-Vinnikov theorem and positive semidefinite
matrix completion.

######  Theorem 3.12.

The Real Zero Amalgamation Problem 2.13 is solvable, even in such a way that
the degree of the amalgam $r$ does not exceed the maximum of the degrees of
$p$ and $q$, in each of the following cases:

  1. (a)

$\ell=0$, i.e., if there are no shared variables,

  2. (b)

$\ell=m=n=1$, i.e., if each block of variables consists just of a single
variable,

  3. (c)

for quadratic polynomials, i.e., if the degrees of $p$ and $q$ are at most
$2$.

###### Proof.

Let $d\in\mathbb{N}_{0}$ and let $p\in\mathbb{R}[x,y]$ and
$q\in\mathbb{R}[x,z]$ be real zero polynomials of degree at most $d$ such that
$p(x,0)=q(x,0)$. WLOG, we suppose that $p(0,0)=q(0,0)=1$. In each of the cases
(a), (b) and (c) we have to show that there exists $r\in\mathbb{R}[x,y,z]$ of
degree at most $d$ such that $r(x,y,0)=p$ and $r(x,0,z)=q$. We proceed very
differently in each of the cases.

(a) Here we suppose that $\ell=0$, i.e., $p\in\mathbb{R}[y]$ and
$q\in\mathbb{R}[z]$. We claim that $\frac{1}{d!}r$ where $r$ is defined
exactly as in Theorem 3.11 does the job. First note that it is of degree at
most $d$. Finally, $r(y,0)=\tilde{r}(1,0,y,0)$ arises from

$\sum_{\begin{subarray}{c}i,j\in\mathbb{N}_{0}\\\
i+j=d\end{subarray}}\partial_{s}^{i}\partial_{t}^{j}\tilde{p}(s,y)\tilde{q}(t,0)\in\mathbb{R}[s,t,y]$

by setting $s$ to $1$ and $t$ to $0$. Since
$\tilde{q}(t,0)=t^{d}\tilde{q}(1,0)=t^{d}q(0)=t^{d}$, only one of the terms in
this sum survives when $t$ is set to $0$, namely $\partial_{t}^{d}t^{d}=d!$.
Hence $\frac{1}{d!}r(y,0)=p$. Analogously, one proves that
$r(0,z)=\tilde{r}(0,1,0,z)=d!q$ and hence $\frac{1}{d!}r(0,z)=q$.

(b) Here we suppose that $\ell=m=n=1$, i.e., $x$, $y$ and $z$ are single
variables. By the Helton-Vinnikov theorem 2.5, we can choose hermitian
matrices $A,A^{\prime},B,C\in\mathbb{C}^{d\times d}$ such that

$p=\det(I_{d}+xA+yB)\qquad\text{and}\qquad q=\det(I_{d}+xA^{\prime}+zC).$

By conjugating each of $A$ and $B$ with a suitable unitary matrix, we can WLOG
assume that $A$ is diagonal. Conjugating it once more with a suitable
permutation matrix, we can moreover suppose that the (real) diagonal entries
of $A$ are weakly increasing. In the same way, we may assume that also
$A^{\prime}$ is a diagonal matrix with weakly increasing diagonal. The
diagonal entries of $A$ can now be reconstructed from the polynomial
$\det(I_{d}+xA)$ by looking at its degree, its roots and the multiplicities of
its roots. We proceed in completely the same manner with $A^{\prime}$. Because
of the polynomial identity
$\det(I_{d}+xA)=p(x,0)=q(x,0)=\det(I_{d}+xA^{\prime})$, we thus get
$A=A^{\prime}$. Now $r:=\det(I_{d}+xA+yB+zC)$ is an amalgamation polynomial
just like in Remark 3.1.

(c) The cases $d\in\\{0,1\\}$ are easy. Hence we suppose here that $d=2$. We
will use the theory of positive semidefinite matrix completion from [GJSW]. By
Example 2.3(a), there are

  * •

symmetric matrices $A\in\mathbb{R}^{\ell\times\ell}$, $B\in\mathbb{R}^{m\times
m}$ and $C\in\mathbb{R}^{n\times n}$,

  * •

matrices $E\in\mathbb{R}^{\ell\times m}$ and $F\in\mathbb{R}^{\ell\times n}$
and

  * •

vectors $a\in\mathbb{R}^{\ell}$, $b\in\mathbb{R}^{m}$ and $c\in\mathbb{R}^{n}$

such that

$\displaystyle p$
$\displaystyle=\begin{pmatrix}x^{T}&y^{T}\end{pmatrix}\begin{pmatrix}A&E\\\
E^{T}&B\end{pmatrix}\begin{pmatrix}x\\\
y\end{pmatrix}+\begin{pmatrix}a^{T}&b^{T}\end{pmatrix}\begin{pmatrix}x\\\
y\end{pmatrix}+1\qquad\text{and}$ $\displaystyle q$
$\displaystyle=\begin{pmatrix}x^{T}&z^{T}\end{pmatrix}\begin{pmatrix}A&F\\\
F^{T}&C\end{pmatrix}\begin{pmatrix}x\\\
z\end{pmatrix}+\begin{pmatrix}a^{T}&c^{T}\end{pmatrix}\begin{pmatrix}x\\\
z\end{pmatrix}+1$

where both “discriminants”

$\displaystyle P$ $\displaystyle:=\begin{pmatrix}aa^{T}-4A&ab^{T}-4E\\\
ba^{T}-4E^{T}&bb^{T}-4B\end{pmatrix}=\begin{pmatrix}a\\\
b\end{pmatrix}\begin{pmatrix}a^{T}&b^{T}\end{pmatrix}-4\begin{pmatrix}A&E\\\
E^{T}&B\end{pmatrix}\in\mathbb{R}^{(\ell+m)\times(\ell+m)}$ and $\displaystyle
Q$ $\displaystyle:=\begin{pmatrix}aa^{T}-4A&ac^{T}-4F\\\
ca^{T}-4F^{T}&cc^{T}-4C\end{pmatrix}=\begin{pmatrix}a\\\
c\end{pmatrix}\begin{pmatrix}a^{T}&c^{T}\end{pmatrix}-4\begin{pmatrix}A&F\\\
F^{T}&C\end{pmatrix}\in\mathbb{R}^{(\ell+n)\times(\ell+n)}$

are positive semidefinite. The task is to find a matrix
$G\in\mathbb{R}^{m\times n}$ such that the quadratic polynomial

$r:=\begin{pmatrix}x^{T}&y^{T}&z^{T}\end{pmatrix}\begin{pmatrix}A&E&F\\\
E^{T}&B&G\\\ F^{T}&G^{T}&C\end{pmatrix}\begin{pmatrix}x\\\ y\\\
z\end{pmatrix}+\begin{pmatrix}a^{T}&b^{T}&c^{T}\end{pmatrix}\begin{pmatrix}x\\\
y\\\ z\end{pmatrix}+1$

is a real zero polynomial, i.e., the “discriminant” of $r$

$\begin{pmatrix}aa^{T}-4A&ab^{T}-4E&ac^{T}-4F\\\
ba^{T}-4E^{T}&bb^{T}-4B&bc^{T}-4G\\\
ca^{T}-4F^{T}&cb^{T}-4G^{T}&cc^{T}-4C\end{pmatrix}=\begin{pmatrix}a\\\ b\\\
c\end{pmatrix}\begin{pmatrix}a^{T}&b^{T}&c^{T}\end{pmatrix}-4\begin{pmatrix}A&E&F\\\
E^{T}&B&G\\\ F^{T}&G^{T}&C\end{pmatrix}$

is positive semidefinite. Since $a$ and $c$ are now fixed vectors, this
amounts to filling the blocks marked by a question mark in the “partial
matrix”

$\begin{pmatrix}aa^{T}-4A&ab^{T}-4E&ac^{T}-4F\\\
ba^{T}-4E^{T}&bb^{T}-4B&\text{?}\\\
ca^{T}-4F^{T}&\text{?}&cc^{T}-4C\end{pmatrix}$

by real numbers so that one obtains a positive semidefinite matrix of size
$\ell+m+n$. This is a positive semidefinite matrix completion problem. The
undirected graph $G$ with loops whose edges correspond to the known entries is

$G=\\{1,\ldots,\ell+m\\}^{2}\cup(\\{1,\ldots,\ell\\}\cup\\{\ell+m+1,\ldots,\ell+m+n\\})^{2}$

and is obtained by glueing together a complete graph on $\ell+m$ vertices with
a complete graph on $\ell+n$ vertices along a complete graph on $\ell$
vertices. It is an easy exercise to show that this graph is _chordal_ in the
sense of [GJSW], i.e., each cycle consisting of at least four pairwise
distinct nodes in this graph has a chord. By [GJSW, Theorem 7] it follows that
our matrix completion problem can be solved since the principal submatrices
corresponding to cliques of the graph in the partial matrix are all positive
semidefinite. Indeed, each such submatrix is a principal submatrix of the
discriminants $P$ and $Q$ of $p$ and $q$ which are both positive semidefinite.
∎

##  4\. Amalgamation of Matroids

Matroids generalize the concept of linear independence. It turns out there is
a notion of amalgamation of matroids that has been studied since the 1980s
[Oxl, Subsection 11.4] and that will turn out to be related to our notion of
amalgamation of real zero polynomials. We will need only the very basics of
matroid theory [Oxl, Sections 1.1–1.4]. We do not assume the reader to be
familiar with it and instead will recall everything we need together with the
corresponding references in Oxley’s standard textbook [Oxl]. There are many
equivalent ways of defining matroids. We follow here [Oxl, Page 7]:

######  Definition 4.1.

Let $S$ be a finite set and $\mathcal{I}$ be set of subsets of $S$. The tuple
$M=(S,\mathcal{I})$ is called a _matroid_ on $S$ if

  1. (a)

$\emptyset\in\mathcal{I}$,

  2. (b)

if $I\in\mathcal{I}$ and $J\subseteq I$, then $J\in\mathcal{I}$ and

  3. (c)

if $I,J\in\mathcal{I}$ such that $\\#I<\\#J$, then there is $x\in J\setminus
I$ such that $I\cup\\{x\\}\in\mathcal{I}$.

The set $S$ is called the _ground set_ of $M$ and the elements of
$\mathcal{I}$ are called the _independent sets_ of $M$. The maximal (with
respect to inclusion) elements of $\mathcal{I}$ are called the _bases_ of $M$.

From (c) one sees immediately that all bases of a matroid have the same number
of elements [Oxl, Lemma 1.2.1]. The independent sets of a matroid are of
course exactly the subsets of its bases. Now we define the notion of
amalgamation of matroids which will be crucial for us [Oxl, Pages 20, 100, 101
and 436].

######  Definition 4.2.

Let $M$ be a matroid on $S$.

  1. (a)

For a subset $A\subseteq S$, we denote by $M|A$ the matroid on $A$ whose
independent sets are exactly the sets $I\subseteq A$ which are independent
sets of $M$. We call $M|A$ the _restriction_ of $M$ to $A$.

  2. (b)

For a subset $A\subseteq S$, we denote by $M/A$ the matroid on $S\setminus A$
whose independent sets are exactly the sets $I\subseteq S\setminus A$ for
which there exists a basis $B$ of $M|A$ such that $I\cup B$ is an independent
set of $M$. We call $M/A$ the _contraction_ of $A$ from $M$.

  3. (c)

Let $M_{1}$ and $M_{2}$ be matroids on $S_{1}$ and $S_{2}$, respectively. If
there is a matroid $M$ on some set containing $S_{1}\cup S_{2}$ such that
$M|S_{1}=M_{1}$ and $M|S_{2}=M_{2}$ then $M$ is called an _amalgam_ of $M_{1}$
and $M_{2}$. Clearly, if there exists an amalgam then $M_{1}|(S_{1}\cap
S_{2})=M_{2}|(S_{1}\cap S_{2})$ (see [Oxl, Page 436]).

Amalgamation of matroids is known to be not always possible. See Example 4.6
below. To understand this, we will need more notions: One can define a matroid
by specifying the set of bases instead of the set of independent sets [Oxl,
Corollary 1.2.5]:

######  Proposition 4.3.

A set $\mathcal{B}$ of subsets of $S$ is a basis of a matroid on $S$ if and
only if

  1. (a)

$\mathcal{B}\neq\emptyset$ and

  2. (b)

if $B,C\in\mathcal{B}$ and $x\in B\setminus C$, there is $y\in C\setminus B$
such that $(B\setminus\\{x\\})\cup\\{y\\}\in\mathcal{B}$.

We will need the notions of rank and closure [Oxl, Pages 21 and 25]:

######  Definition 4.4.

Let $M$ be a matroid on $S$. The size of the bases of $M$ is called _rank_ of
$M$ and denoted by $r(M)$. More generally, the rank of a subset $A$ of $S$ is
$r(M|A)$ and will be denoted by $r(A)$. For a subset $A$ of $S$,

$\operatorname{cl}(A):=\\{x\in S\mid r(A\cup\\{x\\})=r(A)\\}$

is called the _closure_ or _span_ of $A$.

Finally, we record the following properties of the rank function [Oxl, Lemmata
1.3.1, 1.4.2 and 1.4.3].

######  Proposition 4.5.

For any matroid $M$ on $S$. the following properties hold:

  1. (a)

$r(A)\leq\\#A$ for all $A\subseteq S$,

  2. (b)

$r(A)\leq r(B)$ for all $A\subseteq B\subseteq S$,

  3. (c)

$r(A\cap B)+r(A\cup B)\leq r(A)+r(B)$ for all $A,B\subseteq S$,

  4. (d)

$r(\operatorname{cl}(A))=r(A)$ for all $A\subseteq S$,

  5. (e)

$\operatorname{cl}(A)\subseteq\operatorname{cl}(B)$ for all $A\subseteq
B\subseteq S$.

Condition (c) is referred to as _submodularity_ of the rank function.

In 1982, Poljak and Turzík gave a counterexample [PT2, Example 1] for matroid
amalgamation that will ultimately lead to our counterexamples to amalgamation
of stable and real zero polynomials in Sections 5 and 6. For convenience of
the reader, we include it here.

######  Example 4.6.

Consider the matroids $M_{1}$ on $\\{x_{1},\ldots,x_{6},y\\}$ and $M_{2}$ on
$\\{x_{1},\ldots,x_{6},z\\}$ given by the following drawing in the sense that
all three element subsets should be bases except those for which the three
elements lie on one of the drawn lines.

Figure 1. The matroids $M_{1}$ and $M_{2}$

$y$$x_{1}$$x_{3}$$x_{2}$$x_{4}$$x_{6}$$x_{5}$

$z$$x_{1}$$x_{3}$$x_{2}$$x_{4}$$x_{6}$$x_{5}$

Specifying matroids by such pictures is very common but one usually has to
check the matroid axioms [Oxl, Section 1.5]. This is here easy (in fact these
are even affine matroids [Oxl, Page 32] which can be seen by a slight
horizontal shift of $x_{3}$ in the picture on the right hand side). The
restrictions of $M_{1}$ and $M_{2}$ to the set $\\{x_{1},\ldots,x_{6}\\}$
agree. We reproduce Poljak and Turzík’s proof that there is no amalgam $M$ of
$M_{1}$ and $M_{2}$.

Assume for a contradiction that there is an amalgam. Then denote by $r$ its
rank function. We consider the sets $A:=\\{x_{1},x_{4}\\}$ and
$B:=\\{x_{2},x_{5}\\}$. We have
$y,z\in\operatorname{cl}(A)\cap\operatorname{cl}(B)$. Thus, by Proposition
4.5, we get

$\displaystyle r(\\{y,z\\})+r(\operatorname{cl}(A)\cup\operatorname{cl}(B))$
$\displaystyle\leq
r(\operatorname{cl}(A)\cap\operatorname{cl}(B))+r(\operatorname{cl}(A)\cup\operatorname{cl}(B))$
$\displaystyle\leq
r(\operatorname{cl}(A))+r(\operatorname{cl}(B))=r(A)+r(B)=4.$

Since $r(\operatorname{cl}(A)\cup\operatorname{cl}(B))\geq 3$, we get
$r(\\{y,z\\})=1=r(\\{y\\})=r(\\{z\\})$. Thus

$2=r(\\{y,x_{3},x_{6}\\})=r(\\{y,z,x_{3},x_{6}\\})=r(\\{z,x_{3},x_{6}\\})=3$

again by Proposition 4.5, which is impossible.

##  5\. Counterexample for stable polynomials

In this section, we show that the bases generating polynomials of the two
matroids from Example 4.6 are stable polynomials and that there is no stable
amalgam of these polynomials. We will use a criterion developed by Wagner and
Wei in [WW] to show that both bases generating polynomials are stable. Since
the support of a homogeneous multi-affine stable polynomial corresponds to the
set of bases of a matroid (see Theorem 5.6 below), this will easily imply that
there is no _homogeneous_ stable amalgam. To show however that there is no
_non-homogeneous_ stable amalgam we will have to employ the theory of delta-
matroids emanating from the work of Bouchet [Bou1].

######  Definition 5.1.

Let $M$ be a matroid on $\\{x_{1},\ldots,x_{\ell}\\}$ where
$x_{1},\ldots,x_{\ell}$ are distinct variables. Let $\mathcal{B}$ be the set
of bases of $M$. We call the multi-affine homogeneous polynomial

$p_{M}:=\sum_{B\in\mathcal{B}}\prod_{v\in B}v$

the _bases generating polynomial_ of $M$.

Note that, in the situation of the above definition, the support of $p_{M}$ in
the sense of Definition 2.6 is $\mathcal{B}$. We will now investigate how to
get from such a bases generating polynomial the bases generating polynomial of
certain restrictions and contractions in the sense Definition 4.2 above. There
is a pitfall here that is related to loops and coloops which we will now
define.

######  Definition 5.2.

Let $M$ be a matroid on $S$ and $x\in S$. Then $x$ is called a

  1. (a)

_loop_ if it is contained in no basis of $M$ [Oxl, Page 12, Exercise 2 of
Section 1.2] and

  2. (b)

_coloop_ if it is contained in all bases of $M$ [Oxl, Page 67].

The following is obvious and well-known [COSW, Proposition 4.1]. We will need
only (a) and (b) but for completeness we also formulate (c) and (d). We write
$p|_{x_{i}=a}$ for the polynomial arising from $p\in\mathbb{R}[x]$ by
substituting $a\in\mathbb{R}$ for $x_{i}$. Recall also our Notation 3.3 for
partial derivatives.

######  Remark 5.3.

Let $M$ be a matroid on $S:=\\{x_{1},\ldots,x_{\ell}\\}$ where
$x_{1},\ldots,x_{\ell}$ are distinct variables. Let $p:=p_{M}$ be its bases
generating polynomial.

  1. (a)

If $v$ is not a coloop of $M$ then $p|_{v=0}$ is the bases generating
polynomial of the restriction of $M$ to $S\setminus\\{v\\}$.

  2. (b)

If $v$ is not a loop of $M$ then $\partial_{v}p$ is the bases generating
polynomial of the contraction of $\\{v\\}$ from $M$.

  3. (c)

If $v$ is a coloop of $M$ then $p|_{v=1}$ is the bases generating polynomial
of the restriction of $M$ to $S\setminus\\{v\\}$.

  4. (d)

If $v$ is a loop of $M$ then $p$ is the bases generating polynomial of the
contraction of $\\{v\\}$ from $M$.

The following criterion from [WW, Theorem 3] will be very convenient for us.

######  Theorem 5.4 (Wagner and Wei).

Let $p\in\mathbb{R}[x]$ be a multi-affine polynomial with only nonnegative
coefficients. Then the following are equivalent:

  1. (a)

$p$ is stable,

  2. (b)

$\partial_{x_{i}}p$ and $p|_{x_{i}=0}$ are stable for all
$i\in\\{1,\ldots,\ell\\}$ and there are $i,j\in\\{1,\ldots,\ell\\}$ with
$i\neq j$ such that the (so-called Rayleigh) polynomial

$(\partial_{x_{i}}p)(\partial_{x_{j}}p)-p\partial_{x_{i}}\partial_{x_{j}}p$

is nonnegative in the whole of $\mathbb{R}^{\ell-2}$.

Note that
$(\partial_{x_{i}}p)(\partial_{x_{j}}p)-p\partial_{x_{i}}\partial_{x_{j}}p$ is
actually a polynomial in $\ell-2$ variables.

For the following theorem see [COSW, Proposition 10.4] or [Oxl, Page 602].

######  Theorem 5.5 (Choe, Oxley, Sokal and Wagner).

Let $M$ be a matroid on a set with at most $6$ elements. Then $p_{M}$ is
stable.

As a last preparation before we continue to study the implications of Example
4.6 for stable polynomials, we state the following fundamental theorem [COSW,
Theorem 7.1].

######  Theorem 5.6 (Choe, Oxley, Sokal and Wagner).

The support of a multi-affine homogeneous stable polynomial
$p\in\mathbb{R}[x]$ is the set of bases of a matroid on
$\\{x_{1},\ldots,x_{\ell}\\}$.

Now, we are ready to prove that the bases generating polynomials of $M_{1}$
and $M_{2}$ of Example 4.6 are stable and that they do not admit a
_homogeneous_ stable amalgam.

######  Example 5.7.

We consider the polynomials $p:=p_{M_{1}}$ and $q:=p_{M_{2}}$, where $M_{1}$
and $M_{2}$ are the matroids from Example 4.6. In [COSW, Corollary 8.2(b)] it
was shown that the matroid $M_{1}$ (denoted by $P_{7}$ in [COSW, Appendix
A.2.3]) satisfies the so-called half-plane property, which is known to be
equivalent to the stability of the bases generating polynomial of $M_{1}$ (see
[Brä1, Corollary 5.14] for the equivalence). In [WW, Page 1389] it was shown
that the matroid $M_{2}$ (denoted by $\mathcal{P}_{7}^{\prime}$ in [WW] and by
$P_{7}^{\prime}$ in [COSW]) has the half-plane property, i.e., $q$ is stable.
For convenience of the reader, we present a slight variation of the argument
of [WW] for $M_{2}$ and use the same method for $M_{1}$ (which is completely
different from the reasoning in [COSW] for $M_{1}$). In both cases, we use
crucially Theorems 5.4 and 5.5. Since neither $M_{1}$ nor $M_{2}$ contains
loops or coloops, we have that $p$ and $q$ are stable after setting one of
their variables to $0$ or after taking a partial derivative with respect to
one of their variables by Remark 5.3(a),(b) and Theorem 5.5. By Theorem 5.4 it
suffices thus to check that the two Rayleigh polynomials
$(\partial_{x_{1}}p)(\partial_{x_{2}}p)-p\partial_{x_{1}}\partial_{x_{2}}p$
and
$(\partial_{x_{1}}q)(\partial_{x_{2}}q)-q\partial_{x_{1}}\partial_{x_{2}}q$
are nonnegative on the whole of $\mathbb{R}^{5}$. In fact, it happily turns
out that they are even sums of squares of polynomials. Namely using
semidefinite programming and the Gram matrix method (see for example [Lau] or
[Sc1, Section 2.6]), we obtain

$(\partial_{x_{1}}p)(\partial_{x_{2}}p)-p\partial_{x_{1}}\partial_{x_{2}}p=\\\
\left(yx_{3}+yx_{6}+x_{3}x_{4}+x_{3}x_{5}+x_{3}x_{6}+\frac{1}{2}x_{4}x_{5}+\frac{1}{2}x_{4}x_{6}+\frac{1}{2}x_{5}x_{6}\right)^{2}\\\
+\frac{3}{4}(x_{4}x_{5}+x_{4}x_{6}+x_{5}x_{6})^{2}$

and

$(\partial_{x_{1}}q)(\partial_{x_{2}}q)-q\partial_{x_{1}}\partial_{x_{2}}q=\\\
\left(zx_{3}+\frac{1}{2}zx_{6}+x_{3}x_{4}+x_{3}x_{5}+x_{3}x_{6}+\frac{1}{2}x_{4}x_{5}+\frac{1}{2}x_{4}x_{6}+\frac{1}{2}x_{5}x_{6}\right)^{2}\\\
+\frac{1}{12}(3zx_{6}+x_{4}x_{5}+x_{4}x_{6}+x_{5}x_{6})^{2}\\\
+\frac{2}{3}(x_{4}x_{5}+x_{4}x_{6}+x_{5}x_{6})^{2}.$

This shows that $p$ and $q$ are indeed stable.

Now, we show that $p$ and $q$ do not have a homogeneous stable amalgam. Assume
for a contradiction that there is a homogeneous stable amalgam
$r\in\mathbb{R}[x,y,z]$ of $p$ and $q$. Using Theorem 2.7, its multi-affine
part $\operatorname{MAP}(r)$ is a stable, homogeneous and multi-affine amalgam
of $p$ and $q$. Indeed,

$(\operatorname{MAP}(r))(x,y,0)=\operatorname{MAP}(r(x,y,0))=\operatorname{MAP}(p)=p$

since $p$ is multi-affine and evaluating at 0 and applying
$\operatorname{MAP}$ commutes (both are just deletion of certain monomials)
and similarly $(\operatorname{MAP}(r))(x,0,z)=q$. Thus, we can assume WLOG
that $r$ is multi-affine. By Theorem 5.6, the support of $r$ is now the set of
bases of a matroid $N$ on the set $\\{x_{1},\ldots,x_{6},y,z\\}$. Since the
monomials of $p$ and $q$ appear in $r$, every basis of $M_{1}$ and $M_{2}$ has
to be a basis of $N$. Since $M_{1}$ and $M_{2}$ have no coloops, $N$ has thus
also no coloops. By Remark 5.3(a), $N$ restricted to
$\\{x_{1},\ldots,x_{6},y\\}$ is $M_{1}$ and $N$ restricted to
$\\{x_{1},\ldots,x_{6},z\\}$ is $M_{2}$. By Example 4.6 this is impossible.
Hence, there is no homogeneous stable amalgam of $p$ and $q$.

For later use, we record the following.

######  Remark 5.8.

In the situation of Example 5.7, we have even shown that $p$ and $q$ have no
(homogenous) multi-affine (not necessarily stable) amalgam
$r\in\mathbb{R}[x,y,z]$ with the property that its support is the set of bases
of a matroid on $\\{x_{1},\ldots,x_{6},y,z\\}$.

For non-homogeneous stable polynomials, we need some of the theory of delta-
matroids. Bouchet [Bou1, Page 156] introduced delta-matroids to study greedy
algorithms. For any two sets $A$ and $B$, we denote by

$A\mathbin{\Delta}B:=(A\setminus B)\cup(B\setminus A)$

its _symmetric difference_.

######  Definition 5.9.

Let $S$ be a finite set and $\mathcal{F}$ be a non-empty set of subsets of
$S$. Then $M=(S,\mathcal{F})$ is called a _delta-matroid_ on $S$ if for all
$A,B\in\mathcal{F}$ and all $x\in A\mathbin{\Delta}B$ there is some $y\in
A\mathbin{\Delta}B$ such that $A\mathbin{\Delta}\\{x,y\\}\in\mathcal{F}$.

We call this condition the _symmetric exchange property_. Note that it
perfectly allows for $y=x$ in which case
$A\mathbin{\Delta}\\{x,y\\}=A\mathbin{\Delta}\\{x\\}$. Using Proposition 4.3,
the reader shows easily the following with an almost identical argument [Bou2,
Page 64]:

######  Proposition 5.10 (Bouchet).

Let $M=(S,\mathcal{F})$ be a delta-matroid.

  1. (a)

The minimal elements of $\mathcal{F}$ form a set of bases of a matroid that we
call the _lower matroid_ of $M$.

  2. (b)

The maximal elements of $\mathcal{F}$ form a set of bases of a matroid that we
call the _upper matroid_ of $M$.

Whereas Part (a) of the last proposition will be crucially used in Example
5.13 below, we will need Part (b) only in the following proposition which we
only include as an additional motivation of the notion of delta-matroid. The
result is from Bouchet [Bou1, Corollaries 7.3 and 7.4] but we give a short
self-contained proof.

######  Proposition 5.11 (Bouchet).

Let $S$ be a set and $\mathcal{F}$ be a set of subsets of $S$.

  1. (a)

$\mathcal{F}$ is the set of bases of a matroid if and only if
$(S,\mathcal{F})$ is a delta-matroid and all elements of $\mathcal{F}$ have
the same cardinality.

  2. (b)

$\mathcal{F}$ is the set of independent sets of a matroid if and only if
$(S,\mathcal{F})$ is a delta-matroid and $\mathcal{F}$ is closed under taking
subsets.

###### Proof.

The “if” part of (a) follows from either part of Proposition 5.10 and the
“only if” part from Proposition 4.3. The “if” part of (b) follows from
Proposition 5.10(b). For the remaining part of (b) it suffices to show that
every matroid in the sense of Definition 4.1 is a delta-matroid. Hence let
$M=(S,\mathcal{I})$ be a matroid. Let $I,J\in\mathcal{I}$. We have to show
that for each $x\in I\mathbin{\Delta}J$ there is some $y\in
I\mathbin{\Delta}J$ such that $I\mathbin{\Delta}\\{x,y\\}\in\mathcal{I}$. To
this end, fix $x\in I\mathbin{\Delta}J$. By passing over from $M$ to its
restriction $M|(I\cup\\{x\\})$ defined in Definition 4.2(a) (and exchanging
$J$ by its intersection with $I\cup\\{x\\}$), we can suppose WLOG that
$I\cup\\{x\\}=S$. WLOG suppose $S\notin\mathcal{I}$. Then $I$ is a basis of
$M$. Moreover the case where $x\in I\setminus J$ is trivial since it suffices
then to take $y:=x$. We finally treat the case where $x\in J\setminus I$. In
this case we promise to find $y\in I\setminus J$ such that
$I\mathbin{\Delta}\\{x,y\\}\in\mathcal{I}$. But then we can exchange $J$ by a
basis of $M$ in which it is contained. Hence not only $I$ but also $J$ is WLOG
a basis of $M$. But by the already proven Part (a) the set of bases of $M$
forms a delta-matroid on $S$. So we know that there is $y\in
I\mathbin{\Delta}J$ such that $I\mathbin{\Delta}\\{x,y\\}$ is a basis of $M$.
It remains to show $y\in I\setminus J$. But if we had $y\in J\setminus I$,
then the basis $I\cup\\{x,y\\}=I\mathbin{\Delta}\\{x,y\\}$ of $M$ would
strictly contain the basis $I$ of $M$ which is impossible. ∎

Finally, we formulate the following result of Brändén which will be crucial to
us [Brä1, Corollary 3.3].

######  Theorem 5.12 (Brändén).

The support of a multi-affine stable polynomial is a delta-matroid.

Finally, we continue our Examples 4.6 and 5.7 and show that the stable
analogue of Problem 2.13 is in general not solvable.

######  Example 5.13.

Let again $M_{1}$ and $M_{2}$ be the matroids from Example 4.6. We show that
there is no stable amalgam of $p:=p_{M_{1}}$ and $q:=p_{M_{2}}$.

Assume to the contrary that $r$ is such an amalgam. We seek for a
contradiction. Exactly as in Example 5.7, we can suppose WLOG that $r$ is
multi-affine and therefore is of the form

$r=p+z\partial_{z}q+yzf=q+y\partial_{y}p+yzf$

for some multi-affine $f\in\mathbb{R}[x]$. Thus, all monomials we add to the
supports of $p$ and $q$ in order to amalgamate are multiples of $yz$ and thus
of degree at least $3$ except for possibly the monomial $yz$. By Theorem 5.12,
$\operatorname{supp}(r)$ is a delta-matroid on
$S:=\\{x_{1},\ldots,x_{6},y,z\\}$. Now we distinguish two cases and show that
none of them can occur.

Case 1: $yz$ is a monomial of $r$.

Consider the monomial $x_{1}x_{4}x_{5}$, which appears in $p$ and thus in $r$.
The monomials $x_{1}x_{4}x_{5}$ and $yz$ violate the symmetric exchange
property. Indeed, after deleting $x_{5}$ from $\\{x_{1},x_{4},x_{5}\\}$, we
can only remove $x_{1}$ or $x_{4}$ or add $y$ or $z$ or do nothing. But the
monomials $x_{4},\,x_{1},\,yx_{1}x_{4},\,zx_{1}x_{4}$ and $x_{1}x_{4}$ do not
appear in $p$ or $q$ and thus do not appear in $r$. Hence, $yz$ cannot be a
monomial of a stable multi-affine amalgam $r$.

Case 2: $yz$ is no monomial of $r$.

Then one deduces easily from Proposition 5.10(a) that the elements of the
delta-matroid $\operatorname{supp}(r)$ of cardinality $3$ form the set of
bases of a matroid $N$ on $S$. Since $r$ is an amalgam of the cubic
homogeneous polynomials $p$ and $q$, so is its cubic homogeneous part $r_{3}$.
Now $\operatorname{supp}(r_{3})$ is the set of bases of $N$. By Remark 5.8
this is impossible.

In both cases, we attained the desired contradiction. Hence $p$ and $q$ have
no stable amalgam.

######  Remark 5.14.

The lowest homogeneous part of a nonzero stable polynomial $p\in\mathbb{R}[x]$
is again stable (see [RVY, Proposition 4.1] and [KS, Proposition 2.6], the
analogous fact for the highest homogeneous part was discovered already in
[COSW, Proposition 2.2]). This can be seen by using Hurwitz’s Theorem [RS,
Theorem 1.3.8] and the fact that the lowest homogeneous part of $p$ is equal
to

$\lim_{\varepsilon\to 0}\varepsilon^{-d}p(\varepsilon x_{1},\ldots,\varepsilon
x_{\ell})$

where $d$ is its degree. For this reason, the polynomial $r_{3}$ in Case 2 of
Example 5.13 is actually stable. Instead of appealing to Remark 5.8, one could
thus reduce in Case 2 directly to Example 4.6. We preferred our argument via
Remark 5.8 to keep the proof more self-contained and because we do not see how
to avoid the use of delta-matroids in Case 1.

Indeed, for stable polynomials with nonnegative coefficients all of its
homogeneous components are again stable [BBL, Lemma 4.16]. But this fails in
general, e.g., the polynomial $(x-1)(y+1)$ is stable but its degree 1
component $x-y$ is not stable. Thus we cannot circumvent Case 1 by just taking
the homogeneous component of degree 3 and neglecting the monomial $yz$.

##  6\. Counterexample for real zero polynomials

In the second version of the preprint [Sc1] released in March 2020, the second
author conjectured that the Real Zero Amalgamation Problem 2.13 would always
admit a solution. Using Example 5.13 and the theory of stable and real zero
polynomials from Section 2, we are now ready to give the first counterexample.
For linear polynomials, it is trivially solvable. For quadratic polynomials we
have shown in Theorem 3.12(c) that it is still possible. Hence the smallest
degree where it can fail is $3$. Indeed, we will provide cubic real zero
polynomials that cannot be amalgamated by an (arbitrary degree) real zero
polynomial. By Remark 3.2, they will of course need to have $\ell\geq 1$
shared variables (for $\ell=0$ there would be even a degree-preserving real
zero amalgam by Theorem 3.12(a)). In order to minimize the degrees of freedom
for the amalgam, it is perhaps not astonishing that the two blocks of non-
shared variables will consist of just $m=n=1$ variable each. If we make this
choice then we know by Theorem 3.12(b) that we need to choose $\ell$ to be at
least $2$. In Section 7 below, we will however argue that our particular
technique based on matroids will not work for $\ell=2$. Our example will have
$\ell=6$ shared variables. We would suspect that counterexamples to real
amalgamation with smaller $\ell$ can be found.

######  Example 6.1.

We consider the two cubic homogeneous polynomials $p:=p_{M_{1}}$ and
$q:=p_{M_{2}}$ from the previous examples. In Example 5.7, we recorded that
$p$ and $q$ are stable. Set
$a:=(\mathbf{1},0)=(1,1,1,1,1,1,0)\in\mathbb{R}_{\geq 0}^{7}$. Due to
$p(a)=q(a)=18\neq 0$, Proposition 2.11 yields that $p(x+\mathbf{1},y)$ and
$q(x+\mathbf{1},z)$ are real zero polynomials. Of course, we have
$p(x+\mathbf{1},0)=q(x+\mathbf{1},0)$ since $p(x,0)=q(x,0)$.

Now suppose that there is a real zero polynomial $r\in\mathbb{R}[x,y,z]$ such
that $p(x+\mathbf{1},y)=r(x,y,0)$ and $q(x+\mathbf{1},z)=r(x,0,z)$. Since the
coefficients of $p(x+\mathbf{1},y)$ and $q(x+\mathbf{1},z)$ are nonnegative,
we get that

$\mathbb{R}_{\geq 0}^{7}\subseteq
C(p(x+\mathbf{1},y))\qquad\text{and}\qquad\mathbb{R}_{\geq 0}^{7}\subseteq
C(q(x+\mathbf{1},z)).$

Thus, by the convexity of the rigidly convex set $C(r)$ and the fact that $r$
is an amalgam of $p$ and $q$, we get that the convex hull of
$(\mathbb{R}_{\geq 0}^{7}\times\\{0\\})\cup(\mathbb{R}_{\geq
0}^{6}\times\\{0\\}\times\mathbb{R}_{\geq 0})$ is contained in $C(r)$. But
this convex hull is the orthant $\mathbb{R}_{\geq 0}^{8}$ Thus, by Proposition
2.12 $r$ is stable. But now $r(x-\mathbf{1},y,z)$ is a stable amalgam of $p$
and $q$ by Remark 2.2(d). This is a contradiction to Example 5.13.

##  7\. Real zero amalgamation conjectures

Poljak and Turzík [PT1] introduced the following notion for matroids.

######  Definition 7.1.

A matroid $M$ is called _sticky_ if whenever it is the common restriction of
two matroids $M_{1}$ and $M_{2}$, then $M_{1}$ and $M_{2}$ can be amalgamated.

Inspired by this, we make the following definition.

######  Definition 7.2.

We call a real zero polynomial $f\in\mathbb{R}[x]$ _sticky_ if the Real Zero
Amalgamation Problem 2.13 admits a solution whenever $p(x,0)=q(x,0)=f$.

In this section, we will report what is known about sticky matroids and we
will speculate about which real zero polynomials might be sticky. We need some
further standard notions for matroids first which are based on Definition 4.4
above [Oxl, Pages 28 and 228].

######  Definition 7.3.

Let $M=(S,\mathcal{I})$ be a matroid.

  1. (a)

A set $F\subseteq S$ is called a _flat_ (or _closed_) if
$\operatorname{cl}(F)=F$.

  2. (b)

$M$ is called _modular_ if $r(F\cap G)+r(F\cup G)=r(F)+r(G)$ for all flats
$F,G\subseteq S$

Note that the condition in (b) says that the submodularity inequality from
Proposition 4.5(c) becomes sharp on flats. Poljak and Turzík showed already
that every modular matroid is sticky, that every sticky matroid of rank at
most $3$ is modular and conjectured that in fact every sticky matroid is
modular [PT1]. This became known as the _sticky matroid conjecture_ and was
open almost for 40 years until it got recently solved by Shin [Shi].

######  Theorem 7.4 (Shin).

The sticky matroids are exactly the modular ones.

The proof of Poljak and Turzík that every modular matroid is sticky is not
very hard and it is a very easy exercise for the reader that matroids on two-
element sets are modular. So we record the following corollary.

######  Corollary 7.5 (Poljak and Turzík).

Matroids with a two-element ground set are sticky.

A matroid-based example of the kind we have constructed in Section 6 above
does therefore not exist for $\ell=2$ shared variables. In addition, real zero
polynomials in two variables are very special since they enjoy for example
having the determinantal representation guaranteed by the Helton-Vinnikov
theorem 2.5. This gives hope that real zero polynomials in two variables could
be sticky. Since this would have positive consequences for the famous
Generalized Lax Conjecture [HV, Subsection 6.1] mentioned at the end of
Section 2 [Sc2], we think that the following conjecture is well-motivated.

######  Conjecture 7.6 (Weak real zero amalgamation conjecture).

Real zero polynomials in two variables are sticky.

A stronger form of this conjecture motivated by our degree preserving
approaches to real amalgamation in Theorem 3.12 above is the following.

######  Conjecture 7.7 (Strong real zero amalgamation conjecture).

Let $\ell=2$, i.e., $x=(x_{1},x_{2})$, and $d\in\mathbb{N}_{0}$. Suppose
$p\in\mathbb{R}[x,y]$ and $q\in\mathbb{R}[x,z]$ are real zero polynomials of
degree at most $d$ such that $p(x,0)=q(x,0)$. Then there exists a real zero
polynomial $r\in\mathbb{R}[x,y,z]$ of degree at most $d$ such that

$p=r(x,y,0)\qquad\text{and}\qquad q=r(x,0,z).$

## Acknowledgements

We thank Mario Bauer and Cynthia Vinzant for useful discussions at the
Oberwolfach workshop _Real Algebraic Geometry with a View toward Koopman
Operator Methods_ in March 2023. We are very grateful to both anonymous
referees for their help in improving the paper. In particular, we owe the now
really simple proof of Lemma 3.5 to one of these referees.

## References

  * [BB1] J. Borcea, P. Brändén: The Lee-Yang and Pólya-Schur programs. I. Linear operators preserving stability, Invent. Math. 177 (2009), no. 3, 541–569
  * [BB2] J. Borcea, P. Brändén: The Lee-Yang and Pólya-Schur programs. II. Theory of stable polynomials and applications, Comm. Pure Appl. Math. 62 (2009), no. 12, 1595–1631
  * [BB3] J. Borcea, P. Brändén,: Multivariate Pólya-Schur classification problems in the Weyl algebra, Proc. Lond. Math. Soc. (3) 101 (2010), no. 1, 73–104
  * [BBL] J. Borcea, P. Brändén, T.M. Liggett: Negative dependence and the geometry of polynomials, J. Amer. Math. Soc. 22 (2009), no. 2, 521–567
  * [Bou1] A. Bouchet: Greedy algorithm and symmetric matroids, Math. Programming 38 (1987), no. 2, 147–159
  * [Bou2] A. Bouchet: Maps and $\Delta$-matroids, Discrete Math. 78 (1989), no. 1–2, 59–71
  * [Brä1] P. Brändén: Polynomials with the half-plane property and matroid theory, Adv. Math. 216 (2007), no. 1, 302–320
  * [Brä2] P. Brändén: Obstructions to determinantal representability, Adv. Math. 226 (2011), no. 2, 1202–1212
  * [COSW] Y.-B. Choe, J.G. Oxley, A.D. Sokal, D.G. Wagner: Homogeneous multivariate polynomials with the half-plane property, Special issue on the Tutte polynomial. Adv. in Appl. Math. 32 (2004), no. 1–2, 88–187
  * [Går1] L. Gårding: Linear hyperbolic partial differential equations with constant coefficients, Acta Math. 85 (1951), 1–62
  * [Går2] L. Gårding: An inequality for hyperbolic polynomials. J. Math. Mech. 8, 1959, 957–965
  * [GJSW] R. Grone, C.R. Johnson, E.M. de Sá, H. Wolkowicz: Positive definite completions of partial Hermitian matrices, Linear Algebra Appl. 58 (1984), 109–124
  * [GKVW] A. Grinshpan, D. Kaliuzhnyi-Verbovetskyi, V. Vinnikov, H. Woerdeman: Stable and real-zero polynomials in two variables, Multidimens. Syst. Signal Process. 27 (2016), no. 1, 1–26
  * [Han] C. Hanselka: Characteristic polynomials of symmetric matrices over the univariate polynomial ring, J. Algebra 487 (2017), 340–356
  * [HV] J.W. Helton, V. Vinnikov: Linear matrix inequality representation of sets, Comm. Pure Appl. Math. 60 (2007), no. 5, 654–674
  * [KS] M. Kummer, B. Sert: Matroids on eight elements with the half-plane property and related concepts, preprint [https://arxiv.org/abs/2111.09610]
  * [Lau] M. Laurent: Optimization over polynomials: selected topics, Proceedings of the International Congress of Mathematicians, Seoul 2014. Vol. IV, 843–869, Kyung Moon Sa, Seoul, 2014
  * [Lea] J. Leake: A representation theoretic explanation of the Borcea-Brändén characterization, Math. Z. 300 (2022), no. 2, 1359–1400
  * [MSS1] A.W. Marcus, D. Spielman, N. Srivastava: Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. SIAM J. Comput. 47, No. 6, 2488-2509 (2018).
  * [MSS2] A.W. Marcus, D. Spielman, N. Srivastava: Finite free convolutions of polynomials, Probab. Theory Related Fields 182 (2022), no. 3–4, 807–848
  * [OSS] S. Oveis Gharan, A. Saberi, M. Singh: A randomized rounding approach to the traveling salesman problem, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, 550–559, IEEE Computer Soc., Los Alamitos, CA, 2011
  * [Oxl] J. Oxley: Matroid theory, Second edition, Oxford Graduate Texts in Mathematics 21, Oxford University Press, Oxford, 2011
  * [Pem] R. Pemantle: Hyperbolicity and stable polynomials in combinatorics and probability, Current developments in mathematics, 2011, 57–123, Int. Press, Somerville, MA, 2012
  * [PT1] S. Poljak, D. Turzík: A note on sticky matroids, Discrete Math. 42 (1982), no. 1, 119–123
  * [PT2] S. Poljak, D. Turzík: Amalgamation over uniform matroids, Czechoslovak Math. J. 34(109) (1984), no. 2, 239–246
  * [PV] D. Plaumann, C. Vinzant: Determinantal representations of hyperbolic plane curves: an elementary approach, J. Symbolic Comput. 57 (2013), 48–60
  * [Ren] J. Renegar: Hyperbolic programs, and their derivative relaxations, Found. Comput. Math. 6 (2006), no. 1, 59–79
  * [RS] Q. I. Rahman, G. Schmeisser: Analytic theory of polynomials, London Mathematical Society Monographs, New Series, 26, The Clarendon Press, Oxford University Press, Oxford, 2002
  * [RVY] F. Rincón, C. Vinzant, J. Yu: Positively hyperbolic varieties, tropicalization, and positroids, Adv. Math. 383 (2021), Paper No. 107677, 35 pp.
  * [Sc1] M. Schweighofer: Real Algebraic Geometry, Positivity and Convexity, preprint [https://arxiv.org/abs/2205.04211]
  * [Sc2] M. Schweighofer: Spectrahedral relaxations of hyperbolicity cones, preprint [https://arxiv.org/abs/1907.13611]
  * [Shi] J. Shin: The sticky matroid conjecture, preprint [https://arxiv.org/abs/2108.04757]
  * [Vin] V. Vinnikov: LMI representations of convex semialgebraic sets and determinantal representations of algebraic hypersurfaces: past, present, and future, Mathematical methods in systems, optimization, and control, 325–349, Oper. Theory Adv. Appl., 222, Birkhäuser/Springer Basel AG, Basel, 2012
  * [Wag] D.G. Wagner: Multivariate stable polynomials: theory and applications, Bull. Amer. Math. Soc. (N.S.) 48 (2011), no. 1, 53–84
  * [Wal] J. L. Walsh: On the location of the roots of certain types of polynomials, Trans. Amer. Math. Soc. 24 (1922), no. 3, 163–180
  * [WW] D.G. Wagner, Y. Wei: A criterion for the half-plane property, Discrete Math. 309 (2009), no. 6, 1385–1390 [note the corrigendum in Discrete Math. 313 (2013), no. 6, 830]