Anton Leykin

Josephine Yu

BEYOND POLYHEDRAL HOMOTOPIES

We present a new algorithmic framework which utilizes tropical geometry and homotopy continuation for solving systems of polynomial equations where some of the polynomials are generic elements in linear subspaces of the polynomial ring. This approach generalizes the polyhedral homotopies by Huber and Sturmfels.

Introduction

The polyhedral homotopy continuation method of Huber and Sturmfels [START_REF] Huber | A polyhedral method for solving sparse polynomial systems[END_REF], which is implemented in PHCpack [START_REF] Verschelde | Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation[END_REF], HOM4PS [START_REF] Lee | HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method[END_REF][START_REF] Chen | Hom4PS-3: a parallel numerical solver for systems of polynomial equations based on polyhedral homotopy continuation methods[END_REF], and PHoM [GKK + 04], is used for computing numerical approximations of all the roots of n polynomial equations in n variables, where it is assumed that each equation has generic coefficients with respect to its monomial support. We generalize this to Setting A: Instead of solving the polynomial system for all solutions in (C * ) n , we would like to find solutions lying on a variety X ⊂ C n defined by the set of polynomials G, away from the base locus, where the number of additional given polynomials (other than G) is equal to dim(X) and each of the additional polynomials is generic with respect to its monomial support. This can be further generalized to Setting B: Instead of monomial supports, we can consider arbitrary supports, i.e. we would like to find roots on X of polynomials that are generic linear combinations of arbitrary sets of polynomials.

We propose a 3-stage framework to solve this problem in the general setting.

Initialization: Reformulate the problem in Setting B into Setting A as explained in §2.

Then pick-in practice, randomly-a one-parameter system f (t) on dim(X) many polynomials with the specified monomial supports and coefficients that are generic rational powers of the parameter t multiplied by a generic complex number.

Stage 1 (mostly symbolic): Compute the tropical variety trop(X). This usually involves both polyhedral computations and Gröbner basis computations.

Stage 2 (polyhedral): Compute the (transverse) intersection of trop(X) with tropical hypersurfaces of polynomials in f (t). Stage 3 (mostly numerical): Find the initial terms-in general, distinct truncationsof Puiseux series solutions of the system G = f (t) = 0 corresponding to the tropical points found in Stage 2. Track the homotopy paths for t ∈ [0, 1], which are approximated by these truncated Puiseux series in the beginning (t close to 0) and lead to solutions of a system with generic complex coefficients at the end (t = 1). When X = C n in Setting A, the Stage 1 is not needed, and the framework specializes to the polyhedral homotopy approach. The precise statements are in the pseudocode of Algorithm 7, which is followed by remarks on currently available tools for implementation.

Date: May 31, 2018.

The problem setup

The more general setup (Setting B) is as follows.

Let X = V(G) ⊆ C n . Let L 1 , L 2 , ... , L r be vector subspaces of C[x] spanned by finite sets F 1 , F 2 , ... , F r respec- tively. Let L := L 1 × • • • × L r . Let Z L i := V(F i ) be the base locus of the linear spaces L i . Let Z L := r i=1 Z L i .
Our main goal is to compute all the points in (X \ Z L ) ∩ V(f ) for some generic element f = (f 1 , ... , f r ) ∈ L. Our enumerative goal is to compute the number d(X, L) of such points, which we assume to be finite.

A discussion of subtleties surrounding the base locus and genericity appears in the Appendix. We can deal with rational functions in F i 's by clearing the denominators and removing the zero locus of the the denominators from X\Z L .

We will now reformulate the Setting B into Setting A. Let P = {h 1 , h 2 , ... , h } be the set of non-monomials in

F 1 ∪ • • • ∪ F r . Consider (1) G = G ∪ {z i -h i (x) | 1 ≤ i ≤ }, F j = (F j with h i replaced by z i ), j = 1, ... ,
f 1 = • • • = f r = 0 on X = V(G) is equivalent to solving f 1 = • • • = f r = 0 on the variety V(G )
where f j is obtained from f j by replacing each h i with z i . The new polynomials f 1 , ... , f r are generic with respect to their monomial support. For the rest of the paper we assume Setting A, that is, F i forms a monomial basis of L i for each i = 1, ... , r. We drop the primes for simpler notation.

Example 1. Two generic circles a 1 (x 2 + y 2 ) + a 2 x + a 3 y + a 4 = 0 a 5 (x 2 + y 2 ) + a 6 x + a 7 y + a 8 = 0 intersect in two points in C 2 although the mixed volume of their Newton polytopes is 4. We rewrite the system as:

z -(x 2 + y 2 ) = 0 a 1 z + a 2 x + a 3 y + a 4 = 0 a 5 z + a 6 x + a 7 y + a 8 = 0
The original equations are transformed into polynomials that are generic with respect to their monomial supports, but we acquire a new equation whose coefficients may be special.

To achieve the main goal, we will construct a homotopy with exactly d(X, L) paths to track. The number d(X, L) is called the intersection index [L 1 , ... , L r ] and is related to the volume and mixed volume of Newton-Okounkov bodies [KK12, §4].

Algorithmic framework

Let C{{t}} be the field of Puiseux series that are convergent on a punctured neighborhood of 0 in C. (See [Ghy] for a proof of the fact that C{{t}} is an algebraically closed field and a historical excursion.) There is a valuation from C{{t}} -{0} to Q given by the leading (lowest) degree.

For an ideal I in C{{t}}[x 1 , ... , x n ] and a weight vector ω ∈ Q n , the t-initial ideal t-in ω (I) is obtained by first taking the usual initial ideal with the min-convention (leading terms are lightest), where the weight of t is 1 and the weights of x's are given by ω, and then setting t = 1. The t-initial ideal is an ideal in C[x]; it does not involve t. For example, t-in (1,2) (t + t 2 )x + 2y + 3tx 2 + (5t 2 + 7t 3 ) = x + 2y + 5 .

The tropical variety of I is defined as

trop(I) = {ω ∈ Q n : t-in ω (I) does not contain a monomial}.
We often write trop(X) to denote trop(I) when X = V(I), and we write trop(f ) to denote trop( f ). The tropical variety is a polyhedral complex, and we can define multiplicities on its maximal faces. See [MS15, Chapter 3] and [START_REF] Jensen | An algorithm for lifting points in a tropical variety[END_REF] for details.

Theorem 2 (Fundamental Theorem of Tropical Algebraic Geometry). [MS15, Theorem 3.2.3] The points in trop(I) are exactly the coordinatewise valuations of the Puiseux series points in the variety of I. The multiplicity of each tropical point ω ∈ trop(I) is equal to the number of Puiseux series point with valuation ω, counted with multiplicities.

We will now formulate the the polyhedral homotopy continuation method of Huber and Sturmfels using tropical geometry. Given

a polynomial system f = (f 1 , ... , f n ) ∈ (C[x 1 , ... , x n ]
) n with generic coefficients with respect to their monomial supports, we perturb the coefficients by throwing in extra factors of the form t α where α are arbitrary rational numbers, to obtain a family of systems f (t) = (f 1 (t), ... , f n (t)) ∈ (C{{t}}[x 1 , ... , x n ]) n . See (2) with r = n. The homotopy continuation approach looks to "connect" solutions of the original system f = f (1) to the Puiseux series solutions of f (t) convergent in some neighborhood of t = 0.

If the exponents of t's are sufficiently generic, then the intersection of tropical hypersurfaces trop(f

1 (t)) ∩ • • • ∩ trop(f n (t)
) is finite and transverse, i.e. locally at each intersection point it is a transverse intersection of affine spaces. In this case we have

trop( f 1 (t), ... , f n (t) ) = trop(f 1 (t)) ∩ • • • ∩ trop(f n (t)). The points of trop(f 1 (t)) ∩ • • • ∩ trop(f n (t)
) are most commonly computed by enumerating mixed cells of the mixed subdivision, which is the projection of lower convex hull the Newton polyhedron of the product

f 1 (t) • • • f n (t) onto the x-coordinates.
The solutions c of the binomial initial system t-in

ω f 1 (t) = • • • = t-in ω f n (t) = 0
give us the leading terms ct ω of the convergent Puiseux series with valuation ω satisfying f (t) = 0. Take cε ω as a numerical approximation of a point satisfying f (ε) = 0 for a small ε > 0. We can numerically track a segment of a real curve f (t), t ∈ [ε, 1] starting at that point and finishing with an approximation of a solution of to the original system f = f (1). This is called the polyhedral homotopy because mixed subdivisions of Newton polyhedra play a crucial role.

Getting back to our Setting A, polynomials in the set G, e.g. z -(x 2 +y 2 ) in Example 1 above, can have special coefficients, while the others have generic coefficients with respect to fixed monomial supports. As above, we wish to compute the tropical variety of the system, which should consist of finitely many points.

For each i = 1, ... , r, let f i =

x α ∈F i a i,α x α be complex polynomials with generic coefficients. Let

(2)

f i (t) = x α ∈F i a i,α t ω i,α x α
for some generic ω •,• ∈ Q. We refer to the system f (t) = (f 1 (t), ... , f r (t)) as a homotopy.

We recover the original system f ∈ L simply by specializing t = 1.

We can look at f (t) from two different angles:

(1) Consider f (t) as a family of systems in L, parameterized by t ∈ C\{0}. Given a path γ : [0, 1] → C\{0}, we get a path f • γ : [0, 1] → L. Suppose the path in L does not go through the branch locus of the projection π : I X,L → L where

I X,L = {(f 1 , ... , f r , z) | z ∈ X \ Z L and all f i vanish at z} ⊂ L × X
is the incidence variety. Then the homotopy f (t) induces smooth homotopy paths

π -1 (f (γ(τ ))), τ ∈ [0, 1]
, that give a one-to-one correspondence between starting roots π -1 (f (t 0 )) and target roots π -1 (f (t 1 )), where t 0 = γ(0) and t 1 = γ(1).

Once we find an appropriate path γ from some t 0 , where π -1 (f (t 0 )) is known, to t 1 = 1, we achieve our main goal by homotopy continuation along γ.

(2) Consider f (t) as a polynomial system over the Puiseux series C{{t}} with d(X, L) many roots over C{{t}}. The second point of view relates to the first as follows. The Puiseux series roots in (2) converge in some punctured neighborhood of t = 0 in C. Thus, if one can approximate these roots close to t = 0, one can find a starting point t 0 for (1) along with approximations of the starting roots. This requires approximating the Puiseux series roots, which is explained in Remark 6.

Remark 3. One can show that the (really) "unlucky" vectors of coefficients a •,• in the construction of f (t) -when f (t) for some t ∈ (0, 1] intersects the ramification locus of π -is contained in a Zariski closed set of real codimension 1 in the ambient (real) coefficient space (with each a •,• ∈ C contributing two coordinates Re(a •,• ) and Im(a •,• )). This implies that with generic choices of a •,• , the real line segment path running over t ∈ [ε, 1] for a small ε > 0 is "lucky". Lemma 4. With the notation as above, if the coefficients f 1 (t), ... , f r (t) have sufficiently generic valuations, then

trop G ∪ {f 1 (t), ... , f r (t)} = trop G ∩ trop f 1 (t) ∩ • • • ∩ trop f r (t) .
The intersection on the right hand side is transverse.

Proof. The inclusion trop

G ∪{f 1 (t), ... , f r (t)} ⊆ trop G ∩ trop f 1 (t) ∩• • •∩trop f r (t)
is always true by the definition of tropical varieties, but the containment may be strict. However, when the coefficients of f 1 (t), ... , f n (t) have sufficiently generic valuations, the intersections are transverse, so the result follows from [BJS + 07, Lemma 3.2].

The multiplicities of the transverse intersection points can be computed using integer linear algebra [JY16, formula (3)]. For F i 's that are not monomial, that is, for polynomials that are generic with respect to non-monomial supports, the intersection of tropicalizations is not necessarily transverse. They become transverse to trop(G ) after the reformulation (1). See Figure 1.

The valuations of the Puiseux series roots are provided by tropical computations (see Theorem 2), while the leading coefficients at a tropical point ω ∈ trop G ∩ trop f 1 (t) ∩ • • • ∩ trop f r (t) are given by the root(s) of the t-initial ideal

J ω = t-in ω G ∪ {f 1 (t), ... , f r (t)} .
The next statement follows from [JY16, Lemma 3.1].

Lemma 5. Let J ω = t-in ω G ∪ {f 1 (t), ... , f r (t)} , then

J ω = in ω G + t-in ω f 1 (t) + • • • + t-in ω f r (t) .
The roots c ∈ V(J ω ) give us the leading coefficients of Puiseux series roots. The lemma shows that the J ω may be generated by simpler polynomials than the original polynomials in G ∪ {f 1 (t), ... , f r (t)}. In the original polyhedral homotopies the ideal J ω is binomial and all roots are regular and easy to obtain. Remark 6. In general, distinct Puiseux series roots may share the same leading terms. This happens exactly when a root c ∈ V(J ω ) is multiple.

For a multiple root c, one needs to find more terms in the truncated Puiseux series s(t) = ct ω + (higher order terms), so that these are distinct for distinct Puiseux series roots. Note that all s(t) and f i (t)'s are polynomials in C[x, t 1/N ] for some positive integer N . The most comprehensive algorithmic treatment of this is can be found in [START_REF] Jensen | An algorithm for lifting points in a tropical variety[END_REF].

Algorithm 7 (Main algorithm).

Input: G, a collection of polynomials; F i , i = 1, ... , r, sets of monomials. Output: generic f i ∈ L i = span F i for i = 1, ... , r;

approximations S to the points of V(G, f 1 , ... , f r ).

1: Compute trop(X) = trop G . 2: Construct f (t), of the form f i (t) := x α ∈F i a i,α t ω i,α x α , i = 1, ... , r. 3: Compute W = trop(X) ∩ trop f 1 (t) ∩ • • • ∩ trop f r (t) . 4: S := ∅ 5: for every point ω ∈ W do 6:
Construct truncations S ω of Puiseux series roots of G = f (t) = 0.

7:

for s(t) ∈ S ω do 8:

Pick ε = ε(ω, s(t)) > 0 close to 0, let xε = s(ε). return f i := f i (1), i = 1, ... , r, and S. 12: end for

The following points remained unsaid in the pseudocode:

• The software Gfan [Jen] can compute trop(X) in Line 1 when G has rational coefficients. • The computation of trop(X) may involve Gröbner bases, while the transverse intersection in Line 3 does not. • Jensen's tropical homotopy continuation [START_REF] Nedergaard | Tropical homotopy continuation[END_REF] may be useful for Line 3.

• Solutions to J ω = in ω G + t-in ω f 1 (t) + • • • + t-in ω f r (t)
provide the leading coefficients of S ω . They give distinct s(t) in Line 6, unless some solutions are multiple. See Remark 6. • The ideal in ω G is a byproduct of the computation of trop(X) in Line 1.

• A practical way to pin down ε = ε(ω, s(t)) in Line 8 is out of the scope of this article; we envision obtaining ε with heuristics that depend on ω and s(t). Such ε exists according to Remark 3 and the discussion preceding it. • We also purposefully omit the discussion of how one tracks a homotopy path in practice. The machinery of numerical homotopy continuation is well established with several books, e.g. [START_REF] Morgan | Solving polynomial systems using continuation for engineering and scientific problems[END_REF][START_REF] Allgower | Introduction to numerical continuation methods[END_REF], devoted to its details. Algorithm 7 achieves our main goal. The enumerative goal is achieved by executing it until Line 3 and then computing the degrees of J ω . The sum of these degrees is d(X, L).

Conclusion

In Setting B we construct an optimal homotopy, optimal in the sense that the number of homotopy paths is equal to the number of solutions generically. Our method combines symbolic, polyhedral, and numerical parts. One potential strength is that, for a concrete polynomial system, one can distribute the load between these parts to avoid bottlenecks or to decrease the generic solution count.

Indeed, polynomials in any given set of equations can be divided into two groups, G and f , fixing the variety X = V(G), on which the roots of f are sought. For each polynomial f i one can decide on which ingredients F i this polynomial is "made of". The list of ingredients may be either inherent to the given problem or be a subject of experimentation. This gives a lot of flexibility.

Appendix: Base locus

When we say a statement is true "for generic y in Y " or "for general y in Y ", we mean that it is true for all elements y in some Zariski open dense subset of Y , not to be confused with the "generic point" of a scheme. We say that a polynomial f is generic or general with respect to support s 1 , ... , s k if f = c 1 s 1 + • • • + c k s k where the coefficients (c 1 , ... , c k ) avoid a Zariski closed proper subset of C k which depends on the context. One should assume that an explicit description of this exceptional set is hard to acquire algorithmically.

In Bernstein-Khovanskii-Kushnirenko theorems and in the original polyhedral homotopies, the goal is to compute (the number of) solutions in the algebraic torus (C * ) n , of polynomials that are generic with respect to their monomial supports. In other words, we choose a monomial basis {m 1 , m 2 , ... , m k i } for each linear system L i and remove the union of their hypersurfaces from X = C n , obtaining C n \ k i j=1 V(m j ) = (C * ) n if all variables appear in the monomial basis. Here we remove the base locus instead, which is the intersection of the hypersurfaces. The following argument shows that these two settings are equivalent. For generic polynomials the solution set does not depend on the choice of set removed as long as it has smaller dimension and contains the base locus.

Proposition 8. Suppose that V(f 1 , ... , f r ) ∩ X is finite for generic (f 1 , ... , f r ) ∈ L. Let Z ⊂ X ⊂ C n be a variety that contains the base locus Z L and dim Z < dim X = r. Then

(3) V(f 1 , ... , f r ) ∩ (X \ Z L ) = V(f 1 , ... , f r ) ∩ (X \ Z) for generic (f 1 , ... , f r ) ∈ L.
Proof. The idea is that for generic choices of (f 1 , ... , f r ) ∈ L, each f i cuts down the dimension of Z \ Z L by one, and we assumed that dim Z < r, so we should have V(f 1 , ... , f r ) ∩ (Z \ Z L ) = ∅, which implies (3). We will make this precise.

If Z = Z L , then there is nothing to prove. Suppose Z Z L . Let U be a Zariski open dense subset of L such that V(f 1 , ... , f r ) ∩ X is finite for each (f 1 , ... , f r ) ∈ U . Let

W = {(f 1 , ... , f r ) ∈ U | V(f 1 , ... , f i ) ∩ (Z \ Z L ) = ∅}.
We wish to show that W contains a Zariski open dense subset of L.

Note that W is constructible, since for the incidence variety

I Z = {(f 1 , ... , f r , z) | z ∈ Z \ Z L and f 1 (z) = • • • = f r (z) = 0} ⊂ L × (Z \ Z L ),
with the projection π onto L we have W = U \ π(I Z ). For a point z ∈ Z \ Z L 1 , the set of f 1 ∈ L 1 satisfying z / ∈ V(f 1 ) is the complement of a hyperplane in L 1 . Since the degrees of the f 1 's in L 1 are bounded, the condition that V(f 1 ) does not contain any component of Z \ Z L can be translated as f 1 not vanishing on a finite set of points; hence the set of such f 1 's is a Zariski open dense subset of L 1 . By Krull's Hauptidealsatz, if V(f 1 ) does not contain any component of Z \ Z L , then V(f 1 ) ∩ (Z \ Z L ) is either empty or has dimension ≤ dim(Z) -1.

For a fixed f 1 , by a similar argument, there is a Zariski open dense subset of f 2 ∈ L 2 such that V(f 1 , f 2 ) ∩ (Z \ Z L ) has dimension ≤ dim(Z) -2, and so on. This shows that the set W is dense in L. Since it is constructible, it contains a Zariski open dense subset.

Figure 1 .

 1 Figure 1. Left: Tropicalizations of the equations for two circles in Example 1 always intersect non-transversely, even when the coefficients a 1 , ... , a 8 are generic Puiseux series. Right: The hypersurface trop(x 2 + y 2 -z) and a general tropical line, defined by two generic linear equations, intersect transversely at two points.

S

  := S ∪ {x 1 }, where x1 is the output of a homotopy continuation algorithm tracking roots of G = f (t) = 0, t ∈ [ε, 1], starting with xε .

  r, which are sets of polynomials in C[x, z] := C[x 1 , ... , x n , z 1 , ... , z ]. Solving the system

Acknowledgments

We thank Anders Jensen and Kiumars Kaveh for helpful comments. AL is supported by NSF-DMS grant #1151297, and JY is supported by NSF-DMS grant #1600569.


Thorsten J Örgens

Thorsten Theobald
email: theobald@math.uni-frankfurt.de

Timo De Wolff
email: dewolff@math.tu-berlin.de

Thorsten Jörgens
email: joergens@math.uni-frankfurt.de

IMAGINARY PROJECTIONS OF POLYNOMIALS

Keywords: Mathematics Subject Classification. 14P10, 12D10 Imaginary projection, stable polynomial, convex algebraic geometry, amoeba, component of the complement

We introduce the imaginary projection of a multivariate polynomial f ∈ C[z] as the projection of the variety of f onto its imaginary part,

the notion offers a novel geometric view underlying stability questions of polynomials.

We show that the connected components of the closure of the complement of the imaginary projections are convex, thus opening a central connection to the theory of amoebas and coamoebas. Building upon this, the paper establishes structural properties of the components of the complement, such as lower bounds on their maximal number, proves a complete classification of the imaginary projections of quadratic polynomials and characterizes the limit directions for polynomials of arbitrary degree.

Introduction

Recent years have seen a lot of interest in stable polynomials, see, e.g., [START_REF] Borcea | Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products[END_REF][START_REF] Borcea | The Lee-Yang and Pólya-Schur programs. II. Theory of stable polynomials and applications[END_REF][START_REF] Marcus | Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem[END_REF][START_REF] Wagner | Multivariate stable polynomials: theory and applications[END_REF] and the references therein. A polynomial f = f (z) = f (z 1 , . . . , z n ) ∈ C[z] = C[z 1 , . . . , z n ] is called stable if every root z satisfies Im(z j ) ≤ 0 for some j. We call f real stable if f has real coefficients and is stable.

As recent prominent applications, Marcus, Spielman, and Srivastava employed stable polynomials in the proof of the Kadison-Singer Conjecture [START_REF] Marcus | Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem[END_REF] and in the existence proof of families of bipartite Ramanujan graphs of every degree larger than two [START_REF] Marcus | Interlacing families I: Bipartite Ramanujan graphs of all degrees[END_REF]. Stable polynomials have also been used by Borcea and Brändén to prove Johnson's Conjecture [START_REF] Borcea | Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products[END_REF] and in Gurvits' simple proof of a generalization of van der Waerden's Conjecture for permanents [START_REF] Gurvits | Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all[END_REF]. Moreover, there are strong connections to hyperbolic polynomials and their hyperbolicity cones, see Section 2.1.

In this paper, we initiate to study the underlying projections on the imaginary parts from a geometric point of view. Given a polynomial f ∈ C[z], introduce the imaginary projection of f as

I(f ) = {Im(z) : z ∈ V(f )} ⊆ R n ,
where V(f ) denotes the variety of f and Im(z) = (Im(z 1 ), . . . , Im(z n )). So, in particular, f is stable if and only if

I(f ) ∩ R n >0 = ∅ .
Our work is motivated by the theory of amoebas as well as by the general goal to reveal and understand convexity phenomena in algebraic geometry, see [START_REF] Blekherman | Semidefinite Optimization and Convex Algebraic Geometry[END_REF]. Amoebas are the images of algebraic varieties in the algebraic torus (C * ) n under the log-absolute map:

A(f ) = {(log |z 1 |, . . . , log |z n |) : z ∈ V(f ) ∩ (C * ) n } ⊆ R n ,
see [START_REF] Gelfand | Discriminants, Resultants and Multidimensional Determinants[END_REF]. Coamoebas employ the arg-map rather than the log-absolute map; see, e.g., [START_REF] Forsgård | Tropical Aspects of Real Polynomials and Hypergeometric Functions[END_REF].

For amoebas, important structural results as well as their occurrences in a broad spectrum of mathematical disciplines have been intensively studied, see [START_REF] Mikhalkin | Amoebas of algebraic varieties and tropical geometry[END_REF][START_REF] Passare | Amoebas, Monge-Ampére measures and triangulations of the Newton polytope[END_REF][START_REF] Passare | Amoebas: their spines and their contours[END_REF] as well as the recent survey [START_REF] Wolff | Amoebas and their tropicalizations -a survey[END_REF]. For coamoebas, investigations are much more recent [START_REF] Forsgård | Tropical Aspects of Real Polynomials and Hypergeometric Functions[END_REF][START_REF] Forsgård | On the order map for hypersurface coamoebas[END_REF][START_REF] Nisse | The phase limit set of a variety[END_REF]. A prominent result states that the complement of an amoeba as well as the complement of the closure of a coamoeba consists of finitely many convex components, see [START_REF] Forsgård | On the order map for hypersurface coamoebas[END_REF][START_REF] Gelfand | Discriminants, Resultants and Multidimensional Determinants[END_REF]. As a key result, which also motivates our study, we show that the closure of the complement of the imaginary projection of a polynomial consists of finitely many convex components as well, see Theorem 4.1.

While there are important analogies among amoebas, coamoebas, and imaginary projections, there are also fundamental differences between these structures. The fibers of the log-absolute maps underlying amoebas are compact, whereas for imaginary projections they are not compact. Furthermore, the limit directions of amoebas, also known as tentacles, are characterized by the logarithmic limit sets and thus carry a polyhedral structure; see [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]Theorem 1.4.2]. In contrast, the limit directions of the imaginary projections are not polyhedral in general, see Section 6. For coamoebas, which are defined on a torus, Nisse and Sottile have introduced a variant of the logarithmic limit sets, by considering accumulation points of arguments of sequences with unbounded logarithm [START_REF] Nisse | The phase limit set of a variety[END_REF].

Building upon the fundamental convexity result, we study structural properties of imaginary projections. We also give lower bounds on the maximal number of components of the complement, see Corollary 4.5.

We investigate important subclasses, such as quadratic and multilinear polynomials. For the class of real quadratic polynomials, we can provide a complete classification of the imaginary projections, see Theorem 5.4. Indeed, this classification result in Theorem 5.4 is somewhat unexpected, since it involves various qualitatively different cases.

Starting from the well-known results on tentacles of amoebas, we characterize the limit points of the imaginary projections. Contrary to the case of the amoeba of a non-zero polynomial f , it is possible that every point on the sphere S n-1 is a limit direction of the imaginary projection of f . For f ∈ C[z], we provide a criterion for one-dimensional families of limit directions at infinity. In the case n = 2 this also characterizes the situations that all points are limit points. See Theorem 6.5 and Corollary 6.7 for further details.

It is easy to see that real projections of complex polynomials should behave in the same way as imaginary projections, since one projection is easily seen to be an instance of the other by replacing the polynomial f (x) with f ( √ -1x). However, we focus on imaginary projections since the latter projections are more naturally connected to stability and hyperbolicity in the setting of real polynomials.

Our paper is structured as follows. Section 2 collects existing facts on stable polynomials as well as on amoebas and coamoebas. In Section 3, we study the structure of imaginary projections. Section 4 considers the components of the complement. In Section 5, we discuss quadratic and multilinear (in the sense of multi-affine-linear) polynomials, and Section 6 is concerned with the situation at infinity. In Section 7 we close with some open questions.

Preliminaries

We collect basic notions on stable polynomials as well as on amoebas and coamoebas. Let R ≥0 and R >0 denote the set of non-negative and the set of strictly positive real numbers.

Throughout the paper, we use bold letters for vectors, e.g., z = (z 1 , . . . , z n ) ∈ C n . Unless stated otherwise, the dimension of these vectors is n. Denote by V(f ) the complex variety of a polynomial f ∈ C[z] and by V R (f ) the real variety of f . We denote by Re(z) and Im(z) the real and the imaginary part of a point z ∈ C, i.e., z = Re(z) + i Im(z), and component-wise for points z ∈ C n . For an arbitrary set M ⊆ C n we understand Re(M ) and Im(M ) as the real parts and the imaginary parts of all elements in M . Moreover, for a polynomial f ∈ C[z] we denote by Re(f ) and Im(f ) the real part and the imaginary part of f after the realification z

= x + iy ∈ C n → (x, y) ∈ R 2n , i.e., f (x, y) = Re f (x, y) + i Im f (x, y). Note that Re(f ) and Im(f ) are real polynomials in R[x, y].
Furthermore, we use the notations

H n C for the set {z ∈ C n : Im(z j ) > 0, 1 ≤ j ≤ n} and H n R = Im H n C
, which is the positive orthant. 2.1. Stable polynomials. Based on the notions of stability and real stability defined in the introduction, we collect the following statements and properties. As a general source on stability of polynomials, we refer to [START_REF] Wagner | Multivariate stable polynomials: theory and applications[END_REF] and the references therein.

Definition 2.1. A polynomial f ∈ C[z] is called stable if it has no root z in H n C . Example 2.2.
f (z) = det(z 1 A 1 + • • • + z n A n + B)
is real stable or identically zero.

There is a close connection between stable, homogeneous polynomials and hyperbolic polynomials. A homogeneous polynomial f ∈ R[z] is called hyperbolic in direction e ∈ R n , if f (e) = 0 and for every x ∈ R n the real function t → f (x + te) has only real roots. It is known that a homogeneous polynomial f ∈ R[z] is real stable if and only if f is hyperbolic with respect to every point in the positive orthant, see [START_REF] Gårding | An inequality for hyperbolic polynomials[END_REF][START_REF] Wagner | Multivariate stable polynomials: theory and applications[END_REF].

Stability of univariate polynomials can be tested as follows. Here, we call two univariate polynomials f, g ∈ R[z] in proper position, f g, if the zeros of f and g interlace (i.e., alternate, see [START_REF] Brändén | Polynomials with the half-plane property and matroid theory[END_REF][START_REF] Marcus | Interlacing families I: Bipartite Ramanujan graphs of all degrees[END_REF]), and if their Wronskian W [f, g] := f g -f g is non-negative on R. Note that if the roots of two polynomials f and g interlace, then W [f, g] is non-negative or non-positive.

Theorem 2.3. (Hermite-Biehler, see [START_REF] Rahman | Analytic Theory of Polynomials[END_REF]Thm. 6.3.4] or [START_REF] Wagner | Multivariate stable polynomials: theory and applications[END_REF]

∆ jk (f ) = ∂f ∂z j ∂f ∂z k - ∂ 2 f ∂z j ∂z k • f is non-negative on R n .
Hence, a non-zero bivariate polynomial f (z 1 , z 2 ) = αz 1 z 2 +βz 1 +γz 2 +δ with α, β, γ, δ ∈ R is real stable if and only if βγ -αδ ≥ 0.

The non-multilinear case can be reduced to the multilinear case via the polarization P(f ) of a multivariate polynomial f , see [START_REF] Brändén | Polynomials with the half-plane property and matroid theory[END_REF]. Denoting by d j the degree of f in the variable z j , P(f ) is the unique polynomial in the variables z jk , 1 ≤ j ≤ n, 1 ≤ k ≤ d j with the properties (1) P(f ) is multilinear, (2) P(f ) is symmetric in the variables z j1 , . . . , z jd j , 1 ≤ j ≤ n, (3) if we apply the substitutions z jk = z j for all j, k, then P(f ) coincides with f . By the Grace-Walsh-Szegö Theorem, P(f ) is stable if and only if f is stable; see, e.g., [START_REF] Brändén | Polynomials with the half-plane property and matroid theory[END_REF]Cor. 5.9]. By Theorem 2.5, deciding whether a multilinear polynomial f is stable is equivalent to deciding whether ∆ jk (f ) ≥ 0 on R n for all j, k. In [START_REF] Kummer | Hyperbolic polynomials, interlacers, and sums of squares[END_REF], sum of squares-relaxations are considered to decide this question.

Amoebas and coamoebas. The theory of amoebas builds upon algebraic varieties in the complex torus (C

* ) n = (C \ {0}) n . For a Laurent polynomial f ∈ C[z ±1 1 , . . . , z ±1 n ], define the semialgebraic amoeba S(f ) (also known as unlog amoeba) by (2.1) S(f ) = {|z| = (|z 1 |, . . . , |z n |) ∈ R n : z ∈ V(f ) ∩ (C * ) n },
and the amoeba A(f ) by

(2.2) A(f ) = {log |z| = (log |z 1 |, . . . , log |z n |) ∈ R n : z ∈ V(f ) ∩ (C * ) n } .
Amoebas were first introduced and studied by Gelfand, Kapranov and Zelevinsky in [START_REF] Gelfand | Discriminants, Resultants and Multidimensional Determinants[END_REF]. Similarly, the coamoeba of f is defined as

(2.3) coA(f ) = {arg(z) = (arg(z 1 ), . . . , arg(z n )) : z ∈ V(f ) ∩ (C * ) n } ⊆ T n ,
where arg denotes the argument of a complex number and

T n = (R/2πZ) n .
If log C is the complex logarithm, then we have the relations

A(f ) = Re • log C V(f ) and coA(f ) = Im • log C V(f ) ,
where all maps are understood component-wise. See Figure 1 for an example of an amoeba and a coamoeba. We recall some basic statements about amoebas, see [START_REF] Forsberg | Laurent determinants and arrangements of hyperplane amoebas[END_REF][START_REF] Gelfand | Discriminants, Resultants and Multidimensional Determinants[END_REF][START_REF] Theobald | Amoebas of genus at most one[END_REF]. For a Laurent polynomial f ∈ C[z], the amoeba A(f ) is a closed set. The complement of A(f ) consists of finitely many convex regions, and these regions are in bijective correspondence with the different Laurent series expansions of the rational function 1/f . The number of components in the complement of an amoeba is bounded from above by the number of lattice points in the Newton polytope of f and bounded from below by the number of vertices of the Newton polytope of f . For coamoebas, it has been conjectured that the complement of the closure of coA(f ) contains at most n! vol New(f ) connected components, where vol denotes the volume, see [START_REF] Forsgård | Tropical Aspects of Real Polynomials and Hypergeometric Functions[END_REF] for more background as well as a proof for the special case n = 2. One can also consider amoebas and coamoebas of arbitrary varieties rather than of hypersurfaces alone, see, e.g., [START_REF] Theobald | Approximating amoebas and coamoebas by sums of squares[END_REF].

The structure of the imaginary projection of polynomials

We investigate the structure of the imaginary projection of multivariate polynomials. Writing z j = x j + iy j with real variables x j , y j , we see that I(f ) is the projection

(3.1) R 2n → R n , (x 1 , y 1 , . . . , x n , y n ) → (y 1 , .
. . , y n ) of a real algebraic variety, and thus I(f ) is a semialgebraic set. Since the map (3.1) is continuous, the imaginary projection of an irreducible polynomial f is connected. See Figure 2 for an example.

The following fact allows to reduce the case of reducible polynomials to the case of irreducible polynomials.

Lemma 3.1. For f 1 , f 2 ∈ C[z], we have I(f 1 • f 2 ) = I(f 1 ) ∪ I(f 2 ). Figure 2. The imaginary projection of f (z 1 , z 2 ) = z 2 1 +z 2 2 +z 1 z 2 +z 1 +z 2 +1, intersected with [-2, 2] 2 .
Proof. By definition of the imaginary projection we have

I(f 1 • f 2 ) = Im V(f 1 • f 2 ) = Im(V(f 1 ) ∪ V(f 2 )) = Im V(f 1 ) ∪ Im V(f 2 ) = I(f 1 ) ∪ I(f 2 ).
The imaginary projections of affine hyperplanes can be characterized as follows.

Theorem 3.2. For every affine-linear polynomial f = a 0 + n j=1 a j z j ∈ C[z] with (a 1 , . . . , a n ) = 0 the following statements hold.

(1)

I(f ) =            V R (Im(a 0 e -iϕ ) + n j=1 a j e -iϕ y j ) , if a 0 ∈ C and (a 1 , . . . , a n ) = b • e iϕ with some b ∈ R n and ϕ ∈ [0, 2π) . R n ,
otherwise.

(2) If all coefficients of f are real, then f is stable if and only if a 1 , . . . , a n ≥ 0 or a 1 , . . . , a n ≤ 0.

Note that by statement (1), an affine-linear polynomial f cannot be stable if (a 1 , . . . , a n ) ∈ e iϕ • R n , and thus statement (2) provides a complete classification for the stability of an affine-linear polynomial.

Proof. If all coefficients a 1 , . . . , a n are real, then

I(f ) = y ∈ R n : ∃x ∈ R n Re(a 0 ) + n j=1 a j x j = 0 and Im(a 0 ) + n j=1 a j y j = 0 = y ∈ R n : Im(a 0 ) + n j=1
a j y j = 0 , and in the situation (a 1 , . . . , a n ) ∈ e iϕ • R n , apply the real case to e -iϕ f . Now assume that (a 1 , . . . , a n ) is not a complex multiple of a real vector. That is, the

real matrix Re(a 1 ) • • • Re(a n ) Im(a 1 ) • • • Im(a n ) has rank 2.
By possibly changing the order of the coefficients a j , we can assume that the matrix A = Re(a 1 ) Re(a 2 ) Im(a 1 ) Im(a 2 ) is invertible. In order to show I(f ) = R n , consider a fixed y ∈ R n and choose arbitrary x 3 , . . . , x n ∈ R.

Then the conditions Re f (x + iy) = 0 and Im f (x + iy) = 0 yield a system of two real linear equations in x 1 , x 2 with coefficient matrix A,

0 = Re f (x + iy) = Re a 0 + n j=1 Re(a j )x j - n j=1
Im(a j )y j ,

0 = Im f (x + iy) = Im a 0 + n j=1 Im(a j )x j + n j=1
Re(a j )y j .

Since A is invertible and x 3 , . . . , x n are fixed, there exists a solution x 1 , x 2 ∈ R, and thus y ∈ I(f ). This completes the proof of (1). Now let all coefficients of f be real. By part (1), f has a zero with Im(z j ) > 0 for all j if and only if there exists at least one positive coefficient and one negative coefficient.

Corollary 3.3. Let n ≥ 2 and f = a 0 + n j=1 a j z j be a stable affine-linear polynomial. Then there exists a (complex) ε-perturbation of the coefficients such that the resulting polynomial is not stable. If all coefficients a 0 , . . . , a n are real and non-zero then for any real infinitesimal perturbations the stability of f is preserved.

Figure 3. The imaginary projections of f (z 1 , z 2 ) = z 2 1 + z 2 2 + 1 and f (z 1 , z 2 ) = z 1 z 2 + z 1 + z 2 -1.
The set I(f ) is not always a closed set. Indeed, already in the quadratic setting all the following cases can occur.

(1)

I(f ) is open for f (z 1 , z 2 ) = z 2 1 + z 2 2 -1. In fact, I(f ) = R n . (2) I(f ) is closed for f (z 1 , z 2 ) = z 2 1 + z 2 2 + 1. (3) I(f ) is neither open nor closed for f (z 1 , z 2 ) = z 1 z 2 + z 1 + z 2 -1.
I(f ) = R n ?
Clearly, the if-direction is obvious. Remark 3.5. If f has real coefficients, then the zeros of f come in conjugated pairs. Therefore, I(f ) is symmetric with respect to the origin.

Components of the complement

Similar to amoebas and coamoebas, the complement of an imaginary projection can have several connected components. In contrast to amoebas, already quadratic polynomials can lead to bounded components in the complement. Indeed, the complement of the imaginary projection of f (z 1 , z 2 ) = z 2 1 +z 2 2 +1 has a bounded component, see Figure 3. The existence of this bounded component of the complement is a consequence of Re(f (x

1 +iy 1 , x 2 +iy 2 )) = x 2 1 -y 2 1 + x 2 2 -y 2 2 + 1. If y 2 1 + y 2 2 < 1
, then there cannot be any x 1 , x 2 ∈ R with Re(f ) = 0. Also note that the origin is contained in the complement of an imaginary projection I(f ) whenever f has a real solution.

Set A c = R n \ A for the complement of a set A ⊂ R n , and write A for the closure of A. As pointed out in Section 2.2, it is an important property of amoebas and coamoebas that the components of A(f ) and of coA(f ) are convex. As a key property of imaginary projections, we show that the closure their complement consists of convex components as well.

ψ : C n → C n , z → z • e -i π 2 ,
which is equivalent to x + iy → y -ix. Furthermore, let

C ψ = ψ(R n + iC) = C -iR n = C + iR n .
We observe that C ψ is a tubular region, that is, for any y ∈ C ψ ∩R n we have y+ix ∈ C ψ for all x ∈ R n . Moreover, the function

g : C ψ → C, w → 1 f (ψ(w))
is holomorphic on C ψ , and C ψ is the maximal tube with this property. By Bochner's Tube Theorem [START_REF] Bochner | A theorem on analytic continuation of functions in several variables[END_REF], g is holomorphic on the convex hull of C ψ (considered as set in R 2n ∼ = C n ). Due to the maximality of C ψ , this implies the convexity of The left picture in Figure 4 shows the imaginary projection of the polynomial f (z 1 , z 2 ) = z 2 1 + z 2 1 z 2 + 2z 1 + z 2 + 1 with its 6 convex components of the complement. The imaginary projection of a non-constant polynomial is always unbounded, see Section 6. As the two right pictures in Figure 4 show, it is possible that an imaginary projection contains both bounded and unbounded components in the complement. The proof of Corollary 4.3 constructed f as a product of linear polynomials. In the following, we investigate the imaginary projection of products of linear polynomials in more detail. Proof. By Theorem 3.2, the imaginary projection of an affine-linear polynomial is either a hyperplane or the whole space R n . We can assume here that the first case holds for every affine-linear polynomial. Then the imaginary projection of the product defines a hyperplane arrangement in R n . If the hyperplanes are in general position, then they decompose the ambient space into exactly n k=0 m k many regions, see [START_REF] Stanley | An introduction to hyperplane arrangements[END_REF]Proposition 2.4]. Theorem 4.4 implies the following lower bound for the maximal number of components of the complement of I(f ) for polynomials f of total degree d in n variables. For homogeneous polynomials, the components of the complement are always unbounded since the imaginary projection is a cone. Furthermore, we have the following relation to hyperbolic polynomials. Theorem 4.6. Let f ∈ R[z] be homogeneous. Then I(f ) = R n if and only if f is hyperbolic (with respect to some vector e ∈ R n ).

C ψ . Since C ψ = ψ(R n + iC) = C + iR n ,
(z 1 , z 2 ) = z 2 1 + z 2 1 z 2 + 2z 1 + z 2 + 1, f (z 1 , z 2 ) = z 4 1 + iz 3 1 -z 2 1 z 2 2 + 3z 2 1 -2iz 1 z 2 2 + (4 -2i)z 1 + 0.5z 2 2 + 1.5 and of f (z 1 , z 2 ) = z 3 1 z 2 2 -iz 3 1 z 2 + 2z 3 1 -1.8z 2 1 z 2 -1.8iz
Proof. Let f be hyperbolic with respect to e ∈ R n . Assuming e ∈ I(f ) then implies that for some x ∈ R n , the imaginary unit i is a root of the real function t → f (x + te). This is a contradiction to the hyperbolicity of f .

Conversely, let e ∈ I(f ). Then we have f (x+ie) = 0 for all x ∈ R n , so that in particular

f (e) = (1 + i) -deg f f ((1 + i)e) = (1 + i) -deg f f (e + ie) = 0 .
Furthermore, if there exists an x ∈ R n such that t → f (x + te) has a complex solution a + ib with b = 0, then the homogeneous function f would satisfy f (x + ae + ibe) = 0 in contradiction to e ∈ I(f ). Hence, f is hyperbolic with respect to e.

Similar to Theorem 4.6, for the case of homogeneous polynomials f ∈ R[z], the components of the complement of I(f ) actually coincide with the hyperbolicity cones of f (as defined, e.g., in [START_REF] Gårding | An inequality for hyperbolic polynomials[END_REF]). The connection between hyperbolicity cones of homogeneous polynomials and imaginary connections are explored further in a follow-up article by the first and the second author [START_REF] Jörgens | Hyperbolicity cones and imaginary projections[END_REF].

Quadratic and multilinear polynomials

In this section, we deal with quadratic and multilinear polynomials. First, we characterize the imaginary projections of quadratic polynomials with real coefficients. The initial two lemmas reduce the problem to the imaginary projections of quadratic polynomials in a normal form. Proof. Writing z = x + iy, the matrix A operates separately on x and y. Hence,

I(f (Az)) = {y : ∃x ∈ R n f (A(x + iy)) = 0} = {A -1 y : ∃x ∈ R n f (x + iy ) = 0} = A -1 I(f (z)).
Lemma 5.2. A real translation z → z + a, a ∈ R n , does not change the imaginary projection of a polynomial. An imaginary translation z → z + ia, a ∈ R n , shifts an imaginary projection in direction -a.

Proof. The statement holds, since the first kind of transformation just translates the real part of the variables and the second one shifts the imaginary parts of the solutions of f (z) = 0 in direction -a.

By the Lemmas 5.1 and 5.2, it suffices to study the imaginary projections of polynomials in a normal form in order to understand the imaginary projections of general quadratic polynomials with real coefficients. Every real bivariate quadric is affinely equivalent to a quadric given by one of the following polynomials, where the names come from the conic sections arising from considering these polynomials as real polynomials.

(i)

z 2 1 + z 2 2 -1 (ellipse), (ii) z 2 1 -z 2 2 -1 (hyperbola), (iii) z 2 1 + z 2 (parabola), (iv) z 2 1 + z 2 2 + 1 (empty set), or one of the special cases (v) z 2 1 -z 2 2
(pair of crossing lines), (vi) z 2 1 -1 (parallel lines, or a single line z 2 1 ), (vii) z 2 1 + z 2 2 (isolated point), (viii) z 2 1 + 1 (empty set). In the following theorem, we characterize the imaginary projections of these quadratic polynomials.

Theorem 5.3. For a quadratic polynomial f ∈ R[z 1 , z 2 ], we have

I(f ) =          R 2 if f is of type (i), {-1 ≤ y 2 1 -y 2 2 < 0} ∪ {0} if f is of type (ii), R 2 \ {(0, y 2 ) : y 2 = 0} if f is of type (iii), {y 2 1 + y 2 2 -1 ≥ 0} if f is of type (iv).
In the cases (v) -(viii), we respectively have

I(f ) = {y ∈ R 2 : y 2 1 -y 2 2 = 0}, I(f ) = {y ∈ R 2 : y 1 = 0}, I(f ) = R 2 , and I(f ) = {y ∈ R 2 : y 1 = ±1}. Figure 5. The imaginary projections of f (z 1 , z 2 ) = -z 2 1 +z 2 2 -1, f (z 1 , z 2 ) = z 2 1 -z 2 2 -1, and f (z 1 , z 2 ) = 2z 2 1 + z 2 2 + 1.
The imaginary projections of some quadratic polynomials are shown in Figure 5, in particular, the middle figure depicts case (ii) from Theorem 5.3.

Proof.

For cases (i)-(ii) and (iv)-(viii), we consider a polynomial f = αz 2 1 + βz 2 2 + γ with α, β, γ ∈ R. Decomposing f (z) = 0 into the real and imaginary parts gives αx 2 1 -αy 2 1 + βx 2 2 -βy 2 2 + γ = 0 and αx 1 y 1 + βx 2 y 2 = 0. For y 1 = 0, eliminating x 1 shows that (5.1)

I(f ) = {y ∈ R n : x 2 2 αβy 2 1 + β 2 y 2 2 = αy 2 1 (αy 2 1 +βy 2 2 -γ) has a real solution x 2 } . In case (i), we have α = β = 1, γ = -1, which altogether gives I(f ) = R 2 . In case (ii), we have α = 1, β = γ = -1.
For y 1 = 0, real solutions for x 2 in (5.1) exist for 0 < y 2 2 -y 2 1 < 1 as well as in the special case y 2 1 -y 2 2 + 1 = 0. And for y 1 = 0, we obtain y ∈ I(f ) if and only if y 2 2 ≤ 1. Cases (iv)-(viii) can be treated similarly. Finally, case (iii) is linear in z 2 , so that the equations for the real and imaginary part can be solved directly for x 2 and y 2 . Now we deal with quadrics in n-dimensional space. Since every quadric in R n is affinely equivalent to a quadric given by one of the following polynomials, (I)

p j=1 z 2 j -r j=p+1 z 2 j (1 ≤ p ≤ r, r ≥ 1, p ≥ r 2 ) , (II) p j=1 z 2 j -r j=p+1 z 2 j + 1 (0 ≤ p ≤ r, r ≥ 1) , (III) p j=1 z 2 j -r j=p+1 z 2 j + z r+1 (1 ≤ p ≤ r, r ≥ 1, p ≥ r 2 )
, it suffices to discuss these cases. (See, e.g., [START_REF] Berger | Geometry. I + II. Universitext[END_REF] as a general background reference for real quadrics.) Theorem 5.4. Let n ≥ r ≥ 3 and f ∈ R[z] be a quadratic polynomial.

(1) If f is of type (I), then (5.2)

I(f ) = R n if r 2 ≤ p < r -1 or p = r , {y ∈ R n : y 2 r ≤ r-1 j=1 y 2 j } if p = r -1 . (2) If f is of type (II), then (5.3) I(f ) =          R n if p = 0 or 1 < p < r -1 , {y ∈ R n : y 2 1 -r j=2 y 2 j ≤ 1} if p = 1 , {y ∈ R n : r-1 j=1 y 2 j > y 2 r } ∪ {0} if p = r -1 , {y ∈ R n : r j=1 y 2 j ≥ 1} if p = r .
(3) If n > r and f is of type (III), then I(f ) = R n \ {(0, . . . , 0, y r+1 , y r+2 , . . . , y n ) : y r+1 = 0, y r+2 , . . . , y n ∈ R}.

Note that the case n ≥ 3 differs significantly from n = 2. The proof of Theorem 5.4 is given in the Lemmas 5.5-5.7.

Lemma 5.5. Let n ≥ r ≥ 3. If f (z) = p j=1 z 2 j -r j=p+1 z 2 j with r 2 < p ≤ r, then I(f ) is given by (5.2).
Proof. Without loss of generality we can assume r = n. Splitting the problem into the real and imaginary part yields

p j=1 x 2 j - n j=p+1 x 2 j - p j=1 y 2 j + n j=p+1 y 2 j = 0 , (5.4) p j=1 x j y j - n j=p+1 x j y j = 0 . (5.5) Consider a fixed y ∈ R n . If -p j=1 y 2 j + n j=p+1 y 2 j = 0, then x 1 = • • • = x n = 0
gives a solution to (5.4) and (5.5). Therefore, we can assume -p j=1 y 2 j + n j=p+1 y 2 j = 0. In the case p = n, by reordering the indices, we can assume that y 2 1 + y 2 2 = 0, and choose x =

y 2 (y 2 1 +y 2
2 ) 1/2 (-y 2 , y 1 , 0, . . . , 0) to obtain a solution for (5.4) and (5.5). In the case p = n -1, the n-dimensional hyperboloid (5.4) in the x-variables is onesheeted for -n-1 j=1 y 2 j + y 2 n < 0 and two-sheeted for -n-1 j=1 y 2 j + y 2 n > 0. In case of a onesheeted hyperboloid, its intersection with the hyperplane (5.5) is never empty. Namely, choosing

x 3 = • • • = x n-1 = 0, gives the hyperboloid x 2 1 + x 2 2 -x 2 n = n-1 j=1 y 2 j -y n in x 1 , x 2 ,
x n , that contains the origin in the inner component of its complement. Now consider the case where the hyperboloid consists of two sheets. For any α > 0, the sets {y ∈ R n : -n-1 j=1 y 2 j + y 2 n = α > 0} and {x ∈ R n :

n-1 j=1 x 2 j -x 2 n = -α} coincide. Furthermore, after a coordinate transformation we can assume α = 1 and set H = {x ∈ R n : -n-1 j=1 x 2 j + x 2 n = 1}. We claim that the intersection of H with the hyperplane (5.5) is always empty. Due to the symmetry of H with respect to all the coordinate hyperplanes x k = 0 for 1 ≤ k ≤ n-1, it suffices by (5.5) to show that the hyperboloid H does not contain two distinct points, whose position vectors are orthogonal to each other with respect to the Euclidean scalar product. Because of the rotational symmetry of H with regard to the x n -axis and the invariance of scalar products under orthogonal transformations, by applying an orthogonal transformation it suffices to consider the situation x 2 = • • • = x n-1 = 0. The resulting hyperbola -x 2 1 + x 2 n = 1 in the x 1 -x n -plane has no two orthogonal position vectors. Namely, the asymptotes x 1 = ±x n divide the plane into four quarters, and the hyperbola is contained in the strict interiors of two opposite quarters. Now consider the case n 2 < p < n -1. By our initial considerations in the proof, we have already covered the case y = 0. In the case y = 0, by changing the coordinates we can assume that (y 1 , y 2 , y p+1 ) is not the zero vector. Choose (x p+2 , . . . , x n ) ∈ R n-p-1 such that -n j=p+2 x 2 j -p j=1 y 2 j + n j=p+1 y 2 j =: α < 0. Then, since y is fixed, (5.4) becomes a hyperboloid of one sheet and (5.5) becomes an affine hyperplane. The intersection of these two hypersurfaces is non-empty. Namely, choosing x 3 = • • • = x p = 0, gives the onesheeted hyperboloid {(x 1 , x 2 , x p+1 ) ∈ R 3 : x 2 1 + x 2 2 -x 2 p+1 = -α > 0}, which intersects the affine hyperplane with normal vector (y 1 , y 2 , -y p+1 ) and constant term -n j=p+2 x j y j . Hence, there exists an x ∈ R n satisfying (5.4) and (5.5).

Lemma 5.6. Let n ≥ r ≥ 3 and f (z) = p j=1 z 2 j -r j=p+1 z 2 j + 1 with 0 ≤ p ≤ r.

( In the case p = 0, we obtain the two equations n j=1 x 2 j = n j=1 y 2 j + 1 and n j=1 x j y j = 0. Setting x =

) If p = 0 then I(f ) = R n . ( 1
) If p = 1 then I(f ) = {y ∈ R n : y 2 1 -r j=2 y 2 j ≤ 1}. (3) If 1 < p < r -1 then I(f ) = R n . (4) If p = r -1 then I(f ) = {y ∈ R n : r-1 j=1 y 2 j > y 2 r } ∪ {0}. ( 2
y 2 2 +1 y 2 1 +y 2 2
1/2 (-y 2 , y 1 , 0, . . . , 0) gives a solution.

In the case p = 1, set α = -y 2 1 + n j=2 y 2 j + 1. Then the statement follows identically as in Lemma 5.5 in the cases α = 0, α < 0 and α > 0. For α = 0, the point x = 0 is a solution for f (z) = f (x + iy) = 0. For α > 0, (5.6) is a one-sheeted hyperboloid and (5.7) is a hyperplane. Their intersection is non-empty. For α < 0, the formula for α and (5.6) both define two-sheeted hyperboloids. We consider the hyperboloids H 1 := {y ∈ R n : y 2 1 -n j=2 y 2 j = 1 -α} and H 2 := {x ∈ R n : x 2 1 -n j=2 x 2 j = -α}. Via the transformations y → y/ √ 1 -α and x → x/ √ -α these sets are transformed into the same set C = {x ∈ R n : x 2 1 -n j=2 x 2 j = 1}. We know by the proof of Lemma 5.5 that there is no pair of orthogonal position vectors on C. Therefore, there are no orthogonal position vectors in H 1 and H 2 . Hence, for α < 0 the equation f (z) = 0 has no solution in x. The case p = r -1 is similar.

In the case 1 < p < r -1, the statement follows as in Lemma 5.5.

In the case p = n, there exists an x satisfying (5.6) and (5.7) if and only if n j=1 y

2 j -1 ≥ 0. Lemma 5.7. Let n > r ≥ 2. If f (z) = p j=1 z 2 j -r j=p+1 z 2 j + z r+1 with 1 ≤ p ≤ r, then I(f ) = R n \
{(0, . . . , 0, y r+1 , y r+2 , . . . , y n ) : y r+1 = 0, y r+2 , . . . , y n ∈ R}.

Proof. We can assume n = r + 1. In the system for the real and the imaginary parts x j y j + y n = 0 , (5.9) consider a fixed (y 1 , . . . , y n ) ∈ R n . If (y 1 , . . . , y n-1 ) = 0, then we can choose (x 1 , . . . , x n-1 ) ∈ R n such that (5.9) is satisfied. Since (5.8) is linear in x n , it has a real solution for x n . In the special case (y 1 , . . . , y n-1 ) = 0, we see that y = (y 1 , . . . , y n ) ∈ I(f ) if and only if y n = 0. Lemmas 5.1 and 5.2 also provide a statement about the existence of unbounded components in the complement. (1) The complement of I(f ) contains the non-negative y 1 -axis R ≥0 × {0} n-1 if and only if the polynomial f (z 1 + ir, z 2 , . . . , z n ) has no real solution in z for any r ≥ 0. (2) I(f ) has an unbounded component in the complement if and only if there is an affine transformation z → Az + ib with a real matrix A and a real vector b such that condition (1) is satisfied.

Proof. The first statement immediately follows from the definition of I(f ). For the second statement, Corollary 4.2 implies that the existence of an unbounded component in the complement is equivalent to the existence of a ray in the complement. By the Lemmas 5.1 and 5.2, the affine transformation reduces the situation to (1).

Multilinear polynomials. We study the imaginary projection of multilinear polynomials (in the sense of multi-affine-linear). Brändén's stability result for this class was given in Theorem 2.5. The next statement describes the imaginary projection of bivariate multilinear polynomials; see the right picture in Figure 3 for an example.

Theorem 5.9. Let f (z 1 , z 2 ) = z 1 z 2 + βz 1 + γz 2 + δ be a multilinear polynomial with β, γ, δ ∈ R. Then

I(f ) = y ∈ R 2 : 0 < y 1 y 2 δ -βγ ≤ 1 ∪ {0} for δ -βγ = 0 .
In the special case δ = βγ, the multilinear polynomial is reducible and thus I(f

) = I(z 1 + γ) ∪ I(z 2 + β) = I(z 1 ) ∪ I(z 2 ) = (R × {0}) ∪ ({0} × R).
As a consequence, we rediscover that the multilinear polynomial f is stable if and only if βγ -δ ≥ 0, see Theorem 2.5.

Proof. Since f can be written as f (z 1 , z 2 ) = (z 1 + γ)(z 2 + β) + δ -βγ, Lemma 5.2 implies that I(f ) = I(g) where g(z 1 , z 2 ) = z 1 z 2 + δ -βγ. Substituting z 1 = z 1 + z 2 and z 2 = (βγ -δ)(z 1 -z 2 ), we can express g as g(z 1 , z 2 ) = (βγ -δ)(z 2 1 -z 2 2 -1), and by Theorem 5.3, the imaginary projection of g with respect to the z -variables is {y ∈ R 2 : -1 ≤ (y 1 ) 2 -(y 2 ) 2 < 0} ∪ {0} . For the case of n-dimensional multilinear polynomials, we provide the subsequent, less explicit, characterization of the imaginary projection, and more generally, of polynomials of the form f = g + z n+1 h ∈ C[z, z n+1 ] with g, h ∈ C[z].

the case of four real roots corresponds to H ≤ 0 and H 2 -16a 2 4 I ≥ 0, while the case of four complex roots corresponds to H > 0 or H 2 -16a 2 4 I < 0, see, e.g., [START_REF] Cremona | Reduction of binary cubic and quartic forms[END_REF]Proposition 7]. In our situation, p = p(x 1 ) is the polynomial in (5.12), Disc(p) = 16(64y 4 1 y 2 2 -27)y 4 1 y 2 2 , H = 16y 2 1 y 2 2 and H 2 -16a 2 4 I = 0. The set of points y ∈ R 2 , where (5.12) has at least two real solutions in x 1 , is given by 64y 4 1 y 2 2 ≤ 27. Taking into account the exceptional set E = {0} × R gives I(f ) = {y ∈ R 2 : 0 < 64y 4 1 y 2 2 ≤ 27} ∪ (R × {0}) .

We will return to multilinear polynomials when studying their asymptotic geometry in Theorem 6.3.

The limit set of imaginary projections

For the amoeba A(f ) of a polynomial f it is well-known that the set of limit points of points in 1 r A(f ) ∩ S n-1 , where r > 0 tends to infinity, is a spherical polyhedral complex. It is called the logarithmic limit set

A ∞ (f ) = lim r→∞ 1 r A(f ) ∩ S n-1
and provides one way of defining a tropical hypersurface; see, e.g., [START_REF] Maclagan | Introduction to Tropical Geometry[END_REF]Section 1.4].

For imaginary projections, the situation is different from amoebas, as shown by the following counterexample: For f ∈ C[z],

I ∞ (f ) = lim r→∞ 1 r I(f ) ∩ S n-1
is not a spherical polyhedral complex in general.

Example 6.1. Let f (z) = z 2 1 -n j=2 z 2 j + 1 with n ≥ 3. Then, by Theorem 5.4,

I(f ) = {y ∈ R n : y 2 1 - n j=2 y 2 j ≤ 1} .
Therefore, I ∞ (f ) = lim r→∞ y ∈ S n-1 : (ry 1 ) 2 -n j=2 (ry j ) 2 ≤ 1 can be written as

I ∞ (f ) = y ∈ S n-1 : y 2 1 ≤ n j=2 y 2 j = y ∈ S n-1 : y 2 1 ≤ 1 2 .
Since n ≥ 3, this cannot be written as the intersection of S n-1 with a polyhedral fan. Hence, I ∞ (f ) is not a spherical polyhedral complex, and since I ∞ (f ) is already closed, this persists under taking the closure. Definition 6.2. Let f ∈ C[z]. We call a point p ∈ R n a limit direction of the imaginary projection of f if p ∈ I ∞ (f ).

exists an order map which distinguishes the different components of the complement, as in the case of amoebas. For coamoebas such an order map is known only in special cases so far (see [START_REF] Forsgård | On the order map for hypersurface coamoebas[END_REF]). Moreover, no sharp upper bound (as a function of the underlying Newton polytope) is known for the number of components of the complement of an imaginary projection.

It is also an open problem to provide effective criteria for general n to decide whether all points on the sphere are limit directions of the imaginary projection of an n-variate polynomial.

[ 5 ,

 5 Proposition 2.4] For positive semidefinite d × d-matrices A 1 , . . . , A n and a Hermitian d × d-matrix B, the polynomial

Figure 1 .

 1 Figure 1. An approximation of the amoeba and the coamoeba of the Laurent polynomial f (z 1 , z 2 ) = 2z 3 1 z 2 +z 1 z 2 2 -4z 1 z 2 -2.5•e 0.7•π•i z 2 1 z 2 +1 together with its corresponding Newton polytope.

  The hyperbolic curve belongs to I(f ), but, except the origin, the axes do not belong to I(f ). See Figure3, and for further details on the specific examples we refer to the discussion of quadratic polynomials in Section 5. Open problem 3.4. Let f ∈ C[z] be a polynomial. Is I(f ) open if and only if

Theorem 4 . 1 .

 41 For every polynomial f ∈ C[z], all components of I(f ) c are convex. The number of these convex components is finite. Proof. Let C be a component of the complement of I(f ). Define the holomorphic map

  we obtain the convexity of C. As I(f ) is a semialgebraic set, the complement of I(f ) is semialgebraic as well. Then finiteness of the number of convex components follows from the classical bounds of Oleinik-Petrovski or Milnor-Thom, see, e.g., [1, Chapter 7]. Theorem 4.1 implies the following statement on the unbounded components of the complement. Corollary 4.2. Every unbounded component of the complement of the closure of an imaginary projection contains a ray. Proof. Let C be an unbounded component of the complement of I(f ). Then the convex set C is at least one-dimensional. By well-known results in convex analysis (see [26, Cor. II.8.3.1, Thm. II.8.4]), the relative interior of C has a recession cone which coincides with the recession cone of the closure of C, and that recession cone contains a non-zero vector. Hence, C contains a ray.

Figure 4 .

 4 Figure 4. The imaginary projection of f(z 1 , z 2 ) = z 2 1 + z 2 1 z 2 + 2z 1 + z 2 + 1, f (z 1 , z 2 ) = z 4 1 + iz 3 1 -z 2 1 z 2 2 + 3z 2 1 -2iz 1 z 2 2 + (4 -2i)z 1 + 0.5z 2 2 + 1.5 and of f (z 1 , z 2 ) = z 3 1 z 2 2 -iz 3 1 z 2 + 2z 3 1 -1.8z 2 1 z 2 -1.8iz2 1 + 2.1z 1 z 2 2 + 2.1iz 1 z 2 + 4.2z 1 -0.2iz 2 2 + 0.4z 2 + 1.6i

Theorem 4 . 4 .

 44 Let f ∈ C[z] be a product of m affine-linear polynomials in n variables. Then the complement of I(f ) consists of at most n k=0 m k components, and this bound is tight.

Corollary 4 . 5 .

 45 There exists a polynomial f of total degree d in n variables such that the complement of I(f ) consists of exactly n k=0 d k components.

Lemma 5 . 1 .

 51 Let f ∈ C[z] and A ∈ R n×n be an invertible matrix. Then, I(f (Az)) = A -1 I(f (z)).

)x

  If p = r then I(f ) = {y ∈ R n : r j=1 y 2 j ≥ 1}. Note that for r = 3 the case (3) cannot occur. Proof. Similar to the proof of Lemma 5.5, we can assume r = n and split the problem into the real and imaginary part, n y n = 0 . (5.7) Consider a fixed y ∈ R n .

Theorem 5 . 8 .

 58 Let f ∈ C[z].

Using 1 1 1 = 1 21 1 /

 1111 βγ -δ -(βγ -δ) -(βγ -δ) 1 -1/(βγ -δ), transforming back to the z-variables with Lemma 5.1 yields the claim.

  ) A non-constant univariate polynomial f ∈ C[z] is stable if and only if Im f Re f . Let f ∈ R[z]be non-constant and multilinear. Then f is stable if and only if for all 1 ≤ j, k ≤ n the function

	Borcea and Brändén gave the following multivariate generalization of the Hermite-
	Biehler Theorem. Here, two multivariate polynomials f, g ∈ R[z] are called in proper
	position, written f	g, if the univariate polynomials f (x + te), g(x + te) are in proper
	position for all x ∈ R n , e ∈ R n ≥0 \ {0}.
	Theorem 2.4. ([7, Cor. 2.4], see also [8, Thm. 5.3]) A non-constant polynomial f ∈ C[z]
	is stable if and only if Im f	Re f .
	We call a polynomial f ∈ C[z] multilinear if it has degree at most 1 with respect to each
	variable. Brändén characterized stability of multilinear polynomials with real coefficients.
	Theorem 2.5. [8, Theorem 5.6]

  We choose an arrangement H of d hyperplanes H 1 , . . . , H d ⊆ R n such that H has t bounded components of the complement. Using Theorem 3.2, each of the hyperplanes is the imaginary projection of an affine-linear polynomial f 1 , . . . , f d ∈ C[z]. By Lemma 3.1, the imaginary projection of the product of these polynomials gives exactly the hyperplane arrangement.

2 1 + 2.1z 1 z 2 2 + 2.1iz 1 z 2 + 4.2z 1 -0.2iz 2 2 + 0.4z 2 + 1.6i

Corollary 4.3. For any integers n > 0 and t > 0, there exists a polynomial f ∈ C[z] = C[z 1 , . . . , z n ] such that the complement of I(f ) has exactly t bounded components.

Proof.

Acknowledgment. We would like to thank the referees for helpful comments.

Proof. Writing z n+1 = u + iv, the conditions Re f = 0 and Im f = 0 give Re g Im g

Considering this equation as a linear equation in u shows that there exists a solution if and only if the coefficient vector and the constant vector are linearly dependent, that is, if and only the determinant (5.10) vanishes.

We obtain the following corollary.

Corollary 5.11.

Then, writing z = x + iy, the sets I(g + z n+1 h) and

coincide outside of the exceptional set E = {Im((z, z n+1 )) : h(z) = 0 and g(z) = 0}.

We observe that the determinantal condition in (5.10) and (5.11) gives a linear condition in v. For a multilinear polynomial of the form f = g + z n+1 h ∈ R[z, z n+1 ] with g and h multilinear, the condition is quadratic in any of the variables x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ).

Example 5.12. We revisit the multilinear polynomial f (z 1 , z 2 ) = z 1 z 2 + δ, δ ∈ R \ {0} to illustrate Corollary 5.11; see Theorem 5.9. Setting g = δ and h = z 1 , the determinantal condition (5.10) gives (where we write y 2 instead of v) δy 1 -y 2 1 y 2 -x 2 1 y 2 = 0 . For y 2 = 0, there exists a real solution for x 1 if and only if y 1 y 2 (δ -y 1 y 2 ) ≥ 0. Taking into account the exceptional set E = {0}×R, we obtain I(f ) = {y ∈ R 2 : 0 < y 1 y 2 δ ≤ 1}∪{0}, in accordance with Theorem 5.9.

Example 5.13. We consider the non-multilinear polynomial f (z 1 , z 2 ) = 1+z 2 z 2 1 , which is of the form f = g + z 2 h with g = 1 and h = z 2 1 . Corollary 5.11 gives the quartic condition in the variable x 1 (5.12) -y 2 x 4 1 -2y 2 1 y 2 x 2 1 + 2y 1 x 1 -y 2 y 4 1 = 0 . Recall that the discriminant of a general polynomial p(z) = n j=0 a j z j is given by Disc(p) = (-1)

an Res(p, p ), where Res denotes the resultant. For a quartic, a positive discriminant corresponds to zero or four real roots, while a negative discriminant corresponds to two real roots. Moreover, with the notation

Unless f is univariate or constant, f has at least one limit direction. Namely, for any integer N > 0 and (z 1 , . . . , z n-1 ) ∈ C n-1 such that (Im(z 1 ), . . . ,

The resulting sequence of points z N induces a sequence of points Im(z N )/ Im(z N ) on the unit sphere S n-1 . By compactness, there exists a convergent subsequence. If f has real coefficients, then, by Remark 3.5, the limit directions are symmetric with respect to the origin.

In Theorem 6.3 and Corollary 6.4, we deal with the limit directions of multilinear polynomials. Then, in Theorem 6.5 and Corollary 6.7, we provide criteria for one-dimensional families of limit directions, which means in the case n = 2 that every point on S 1 is a limit direction of the imaginary projection. Theorem 6.3. Let f ∈ C[z] be a multilinear polynomial, and assume that the monomial z 1 • • • z n appears in f , i.e., deg(f ) = n. Then the limit directions of I(f ) are given by S n-1 ∩ H, where H is the union of the n coordinate hyperplanes {y ∈ R n :

Proof. Homogenizing f to f h (z 0 , z 1 , . . . , z n ), the homogeneous polynomial f h has a zero at infinity, i.e., (0,

The imaginary projections of the n hyperplanes {z ∈ C n : z j = 0} then imply the claim. Theorem 6.3 allows one to characterize the number of unbounded components in the complement of the imaginary projection of multilinear polynomials. We remark that this number coincides with the number stated in Theorem 4.4 when choosing m = n.

Proof. By Theorem 6.3, the complement of I ∞ (f ) consists of 2 n components. Therefore, the complement of I(f ) has exactly 2 n unbounded components.

C , then every point in the intersection S n-1 ∩ H is a limit direction, where H = {λ Re(p) + µ Im(p) : λ, µ ∈ R} and p = (p 1 , . . . , p n ).

Proof. Let p h = (0 : p 1 : • • • : p n ) be a zero at infinity of f h . Since ip h is also a point at infinity for f h , we can assume that n j=1 Im(p j ) 2 = 0. Since f is non-constant, there exists a sequence (p (k) ) = (p

is a limit direction. Multiplying p h with a complex number µ + iλ, λ, µ ∈ R keeps p h invariant, and under the imaginary projection it leads to a projected point Im((µ+iλ)•p) = µ Im(p) + λ Re(p). Considering all complex numbers µ + iλ ∈ C, these points form the subspace H.

Example 6.6. We revisit the polynomial f (z 1 , z 2 ) = z 2 1 -z 2 2 -1; see Figure 5 for its imaginary projection. Its homogenization is

3 whose zeros at infinity are given by the equation

For the points p h = (0 : 1 : ±1), Theorem 6.5 provides the two one-dimensional lines H 1,2 = {λ(1, ±1) : λ ∈ R}. We obtain the intersection

2 )}. Theorem 6.5 implies the following statement about bivariate polynomials of arbitrary degree: Corollary 6.7. Let f ∈ C[z 1 , z 2 ] be of total degree d and assume its homogenization f h has the zeros at infinity (0 : 1 : a j ), j = 1, . . . , d. Then,

Note that by changing coordinates, zeros of the form (0 : 0 : b j ) with b j = 0 are covered by the statement as well.

Proof. Assume first that there is an a j with Im(a j ) = 0, say a 1 . Then, by Theorem 6.5, the subspace H = {λ(1, Re(a 1 )) + µ(0, Im(a 1 )) : λ, µ ∈ R} is two-dimensional and thus the set of limit directions is H ∩ S 1 = S 1 .

If all a j are real, then all the subspaces H j corresponding to the points (0 : 1 : a j ) are one-dimensional. The intersection H j ∩ S 1 contains the points ± 1 √ 1+a 2 j (1, a j ).

In order to show that there are no further limit directions, let (p (n) ) n∈N be a sequence of points in V(f ) with Im(p (n) ) 2 → ∞. Since the curve V(f ) has only a finite number of points in the plane at infinity, namely d, the sequence (p (n) ) n∈N can be decomposed into d disjoint subsequences (q (n) 1 ), . . . , (q (n) l ) (some of them possibly contain only finitely many elements) such that any infinite sequence (q (n) j ) converges to the projective point (0 : 1 : a j ). Example 6.8. Let f (z 1 , z 2 ) = z 2 1 + z 2 2 + 1. Then the zeros of f h at infinity are determined by the equation z 2 1 + z 2 2 = 0, giving the two zeros (0 : 1 : ±i). Since the third coordinate is purely imaginary, any point on S 1 is a limit direction, as already visualized in the left picture of Figure 3.

Open questions

In this paper, we have introduced and developed the foundations of the imaginary projection of complex polynomial zero sets. A central open question is whether there


How to install modules in Julia ?

Installing is easy ! julia> Pkd.

Overview of famous Julia modules

Plotting:

Winston.jl for easy plotting like MATLAB PyPlot.jl interface to Matplotlib (Python) The JuliaDiffEq collection for differential equations The JuliaOpt collection for optimization The JuliaStats collection for statistics And many more! Find more specific packages on GitHub.com/svaksha/Julia.jl

L Norm norm(v) norm(v) Inverse inv(a) inv(a)
Solve syst.

function Ei(x, minfloat=1e-3, maxfloat=100) f = t -> exp(-t) / t # inline function if x > 0 return quadgk(f, -x, -minfloat)[1] + quadgk(f, minfloat, maxfloat)[1] else return quadgk(f, -x, maxfloat)[1] end end X = linspace(-1, 1, 1000) # 1000 points Y = [ Ei(x) for x in X ] # Python-like syntax! « Julia,
θ (t) + b θ (t) + c sin(θ(t)) = 0 For b = 1/4, c = 5, θ(0) = π -0.1, θ (0) = 0, t ∈ [0, 10]
How to?

Use packages! Example of a computation that cannot be vectorized Smoothing of a signal {u } :

y = ay + (1 -a)u , k ∈N
Parameter a tunes the smoothing (none: a = 0, strong a → 1 ). Iteration ( for loop) cannot be avoided. min j, such that ∥r∥ ≤ j @variable(m, j) @constraint(m, norm(res) <= j) @objective(m, Min, j)

(SOCP problem ⟹ ECOS solver) i ∑ i 2 2 « Julia,

«

  Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 14 Many packages, and a quickly growing community Julia is still in development, in version v0.6 but version 1.0 is planned soon! « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 15

  fft(a) , ifft(a) fft(a) , ifft(a) Very close to MATLAB for linear algebra! 2 « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 20 3. Scientific problems solved with Julia Just to give examples of syntax and modules 1. 1D numerical integration and plot 2. Solving a 2 order Ordinary Differential Equation nd « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 21 3.1. 1D numerical integration and plot Exercise: evaluate and plot this function on [-1, 1] : my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 22 using QuadGK

  DifferentialEquations.jl function for ODE integrationWinston.jl for 2D plotting nd ′′ ′ ′ « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 25 using DifferentialEquations b, c = 0.25, 5.0 y0 = [pi -0.1, 0] # macro magic! pend2 = @ode_def Pendulum begin dθ = ω # yes, this is UTF8, θ and ω in text dω = (-b * ω) -(c * sin(θ)) end prob = ODEProblem(pend, y0, (0.0, 10.0)) sol = solve(prob) # solve on interval [0,10] t, y = sol.t, hcat(sol.u...)' « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 26 « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 27 Examples 1. Iterative computation: signal filtering 2. Optimization: robust regression on RADAR data « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 28 Ex. 1: Iterative computation Objective: show the efficiency of Julia's Just-in-Time (JIT) compilation but also its fragility... Note: you can find companion notebooks on GitHub « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 29 Iterative computation: signal filtering The classical saying: « Vectorized code often runs much faster than the corresponding code containing loops. » (cf. MATLAB doc) does not hold for Julia, because of its Just-in-Time compiler.

  my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 30 Signal filtering in Julia function smooth(u, a) y = zeros(u) y[1] = (1-a)*u[1] for k=2:length(u) # this loop is NOT slow! y[k] = a*y[k-1] + (1-a)*u[k] end return y end « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. numba.jit 50 ms since 2012 *on a VM which adds an overhead of 20% to 40%, (so that 70 ms → 100 ms) (Matlab and Python implementations) function y = smooth(u, a) y = zeros(length(u),1); y(1) = (1-a)*u(1); for k=2:length(u) y(k) = a*y(k-1) + (1-a)*u(k); end end Python (optionally with Numba's jit decorator) @numba.jit # <-factor ×100 speed-up! def smooth_jit(u, a): y = np.zeros_like(u) y[0] = (1-a)*u[0] for k in range(1, len(u)): y[k] = a*y[k-1] + (1-a)*u[k] return y « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 33 Conclusion on the performance For this simple iterative computation: Julia performs very well, much better than native Python but it's possible to get the same with fresh Python tools (Numba) more realistic examples are needed « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 34 Regression choice: least squares regression min r Reformulated as a Second-Order Cone Program (SOCP):

  Datatype Array of any type multi-dim doubles array Array

	2. Main differences in MATLAB File ext. Comment # blabla... % blabla... [1 2; 3 4] [1 2; 3 4] Size size(a) Nb Dim ndims(a) Last a[end] ones(2, 3, 5) ones(2, 3, 5) Ones a(end) zeros(2, 3, 5) zeros(2, 3, 5) Zeros ndims(a) a .^ 3 Element-wise ^a ^ 3 size(a) Element-wise x a .* b a .* b a ./ b a ./ b Element-wise / syntax between Julia and 2. Main differences in syntax between Julia Julia MATLAB Help ?func help func Julia MATLAB Tranpose a.' a.' Julia MATLAB Maximum max(a) max(max(a)) ? and MATLAB Ref: CheatSheets.QuanteCon.org Julia MATLAB And a & b a && b Or a | b a * b a * b Matrix x a || b Conj. transpose a' a' Random matrix rand(3, 4) rand(3, 4)
	Identity	eye(10)	eye(10)
	Range	range(0, 100, 2) or 1:2:100	1:2:100
	« Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 19

Ref: CheatSheets.QuanteCon.org « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 16 Indexing a[1] to a[end] a(1) to a(end) Slicing a[1:100] (view) a(1:100) ( copy) Operations Linear algebra by default Linear algebra by default Block Use end to close all blocks Use endif endfor etc « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 17 « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 18

  Your mission, if you accept it... 1. Padawan level: Train yourself a little bit on Julia ↪ JuliaBox.com ? Or install it on your laptop! And read introduction in the Julia manual! 2. Jedi level: Try to solve a numerical system, from your research or teaching, in Julia instead of MATLAB 3. Master level: From now on, try to use open-source & free tools for your research (Julia, Python and others)…

	Regression choice: least absolute deviation Solve! JuMP: summary Conclusion (1/2) Conclusion (2/2)
	min Reformulated as a Linear Program (LP) |r | min t , such that -t ≤ r ≤ t @variable(m, t[1:n]) @constraint(m, res .<= t) @constraint(m, res .>= -t) @objective(m, Min, sum(t)) i ∑ i i ∑ i i i i julia> solve(m) [solver blabla... ⏳ ] :Optimal # hopefully julia> getvalue(a), getvalue(b) (-1.094, 127.52) # for least squares Observations: least abs. val., Huber least squares A modeling language for optimization, within Julia: Thanks for joining ! Sum-up gives access to all classical optimization solvers I hope you got a good introduction to Julia very fast (claim) It's not hard to migrate from MATLAB to Julia gives freedom to explore many variations of an optimization Good start: problem (fast prototyping) docs.JuliaLang.org/en/stable/manual/getting-started More on optimization with Julia: Julia is fast! JuliaOpt: host organization of JuMP Free and open source! Optim.jl: implementation of classics in Julia (e.g., Nelder-Mead) Can be very efficient for some applications! JuliaDiff: Automatic Differentiation to compute gradients, thanks to Julia's strong capability for code introspection Thank you ! !

my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 46 « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 47 « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 48 « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 49 « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 50 « Julia, my new computing friend? » | 14 June 2018, IETR@Vannes | By: L. Besson & P. Haessig 51

.jl.m

Fragility of Julia's JIT Compilation

The efficiency of the compiled code relies on type inference. An order of magnitude difference vs julia> @time smooth1(u, 0.9); 0.212018 seconds (30.00 M allocations: 457.764 MiB ...)

julia> @time smooth2(u, 0.9); 0.024883 seconds (5 allocations: 176 bytes)

Fortunately, Julia gives a good diagnosis tool julia> @code_warntype smooth1(u, 0.9); ... # ↓ we spot a detail y::Union{Float64, Int64} ...

Regression as an optimization problem

The parameters for the trend (a, b) should minimize a criterion J which penalizes the residuals r = y -= ya.x + b:

where ϕ is the penaly function, to be chosen: How to solve the regression problem?

Option 1: a big bag of tools A specific package for each type of regression:

« least square toolbox » (→ MultivariateStats.jl) « least absolute value toolbox » (→ quantile regression) « Huber toolbox » (i.e., robust regression → ??) ... res (« residuals ») is an Array of 300 elements of type JuMP.GenericAffExpr{Float64,JuMP.Variable} , i.e., a semi-symbolic affine expression. Now, we need to specify the penalty on those residuals.