Simon Telen
email: simon.telen@mis.mpg.de

Polynomial Equations: Theory and Practice

Solving polynomial equations is a subtask of polynomial optimization. This article introduces systems of such equations and the main approaches for solving them. We discuss critical point equations, algebraic varieties, and solution counts. The theory is illustrated by many examples using different software packages.

Polynomial equations in optimization

. This article will be a chapter in the forthcoming book Polynomial optimisation, moments and applications presenting research acitivies conducted in the European Network POEMA. In that context, polynomial equations arise from optimization problems.

Let us consider the problem of minimizing a polynomial objective function 𝑓 (𝑥 1 , . . . , 𝑥 𝑘 ) over the set

, often written as min

(1)

Introducing new variables 𝜆 1 , . . . , 𝜆 ℓ we obtain the Lagrangian 𝐿 = 𝑓 -𝜆 1 ℎ 1 -• • • -𝜆 ℓ ℎ ℓ , whose partial derivatives give the optimality conditions

𝜕𝐿 𝜕𝑥 1 = • • • = 𝜕𝐿 𝜕𝑥 𝑘 = ℎ 1 = • • • = ℎ ℓ = 0. (2)
A solution in R 𝑘 is a candidate minimizer. Many methods for solving the equations [START_REF] Bates | Numerically solving polynomial systems with Bertini[END_REF], like those presented in Section 4, compute all complex solutions first and then select the real ones among them. The number of solutions over C is typically finite. We present two examples of [START_REF] Baldi | Computing real radicals by moment optimization[END_REF]. First, we minimize the distance to algebraic varieties.

Example: Euclidean distance degree

Given a point 𝑦 = (𝑦 1 , . . . , 𝑦 𝑘 ) ∈ R 𝑘 , we consider the squared Euclidean distance function 𝑓 (𝑥 1 , . . . , 𝑥 𝑘 ) = ∥𝑥 -

𝑦∥ 2 2 = (𝑥 1 -𝑦 1 ) 2 + • • • + (𝑥 𝑘 -𝑦 𝑘 ) 2 . As above, 𝑋 is the set {𝑥 ∈ R 𝑘 | ℎ 1 = • • • = ℎ ℓ = 0}.
The solution 𝑥 * of the optimization problem [START_REF] Baldi | Computing real radicals by moment optimization[END_REF] is

𝑥 * = arg min 𝑥 ∈𝑋 ∥𝑥 -𝑦∥ 2 2 , (3)
i.e. the point on 𝑋 that is closest to 𝑦. The algebraic complexity of this problem is studied in [START_REF] Draisma | The euclidean distance degree of an algebraic variety[END_REF]. For instance, let 𝑘 = 2, ℓ = 1 and let 𝑋 be the unit ball with respect to the 4-norm ∥•∥ 4 : ℎ = ℎ 1 = 𝑥 4 1 + 𝑥 4 2 -1. We want to find the point on 𝑋 closest to 𝑦 = (2, 1.4). In Mathematica [?], one solves (2) as follows:

f = (x1 -2)^2 + (x2 -1.4)^2; h = x1^4 + x2^4 -1; L = f -lambda*h; NSolve[{D[L, x1] == 0 && D[L, x2] == 0 && h == 0}, Reals]
This returns two critical points on 𝑋. One of them minimizes the distance to 𝑦, the other maximizes it. The minimizer is 𝑥 * = (0.904944, 0.757564). If we delete the option Reals, the program returns 16 complex solutions.

Second, we set up a polynomial optimization problem from system identification.

Example: parameter estimation for system identification

System identification is an engineering discipline that aims to construct models for dynamical systems from measured data. A model explains the relationship between input, output, and noise. It depends on a set of model parameters, which are selected to best fit the measured data. A discrete-time, single-input single-output linear timeinvariant system with input sequence 𝑢 : Z → R, output sequence 𝑦 : Z → R and white noise sequence 𝑒 : Z → R is often modeled by

𝐴(𝑞) 𝑦(𝑡) = 𝐵 1 (𝑞) 𝐵 2 (𝑞) 𝑢(𝑡) + 𝐶 1 (𝑞) 𝐶 2 (𝑞) 𝑒(𝑡). (4)
Here 𝐴, 𝐵 1 , 𝐵 2 , 𝐶 1 , 𝐶 2 ∈ C[𝑞] are unknown polynomials of a fixed degree in the backward shift operator 𝑞, acting on 𝑠 : Z → R by 𝑞𝑠(𝑡) = 𝑠(𝑡 -1). The model parameters are the coefficients of these polynomials, which are to be estimated. Clearing denominators in [START_REF] Bender | Toric eigenvalue methods for solving sparse polynomial systems[END_REF] gives 𝐴(𝑞)𝐵 2 (𝑞)𝐶 2 (𝑞)𝑦(𝑡) = 𝐵 1 (𝑞)𝐶 2 (𝑞)𝑢(𝑡) + 𝐵 2 (𝑞)𝐶 1 (𝑞)𝑒(𝑡).

(5)

Suppose we have measured 𝑢(0), . . . , 𝑢(𝑁), 𝑦(0), . . . , 𝑦(𝑁). Let 𝑑 = max(𝑑 𝐴 + 𝑑 𝐵 2 + 𝑑 𝐶 2 , 𝑑 𝐵 1 + 𝑑 𝐶 2 , 𝑑 𝐵 2 + 𝑑 𝐶 1 ), where 𝑑 𝐴 , 𝑑 𝐵 1 , 𝑑 𝐵 2 , 𝑑 𝐶 1 , 𝑑 𝐶 2 are the degrees of our polynomials. Writing [START_REF] Bender | Yet another eigenvalue algorithm for solving polynomial systems[END_REF] for 𝑡 = 𝑑, 𝑑 + 1, . . . , 𝑁, we find algebraic relations among the coefficients of 𝐴, 𝐵 1 , 𝐵 2 , 𝐶 1 , 𝐶 2 . The model parameters are estimated by solving min Θ∈R 𝑘 𝑒(0) 2 + . . . + 𝑒(𝑁) 2 subject to ( 5) is satisfied for 𝑡 = 𝑑, . . . , 𝑁

where Θ consists of 𝑒(0), . . . , 𝑒(𝑁) and the coefficients of 𝐴, 𝐵 1 , 𝐵 2 , 𝐶 1 , 𝐶 2 . We refer to [3, Section 1.1.1] for a worked-out example and more references.

More general versions of (1) add inequality constraints of the type 𝑞 1 (𝑥) ≥ 0, . . . , 𝑞 ℓ ′ (𝑥) ≥ 0, where 𝑞 1 , . . . , 𝑞 ℓ ′ are polynomials. Such problems can be handled using sums-of-squares relaxations [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF].

Our aim in this article is to introduce systems of polynomial equations in general, and methods for solving them. The reader is encouraged to try out these methods for polynomial optimization, for instance, in a Euclidean distance computation (3) or in system identification. Section 2 discusses solution sets to polynomial equations, also called algebraic varieties, and root finding over different fields. In Section 3, we present several classical upper bounds on the number of solutions. Section 4 is about normal form methods and homotopy continuation methods, which are two different important approaches to solving polynomial equations. Finally, Section 5 contains a case study in which we apply these methods to compute 27 lines on a cubic surface.

Acknowledgements. This article is based on an introductory lecture given at the workshop Solving polynomial equations and applications organized at CWI, Amsterdam in October 2022. I thank Monique Laurent for involving me in this workshop, and all other speakers and attendants for making it a success. I was supported by a Veni grant from the Netherlands Organisation for Scientific Research (NWO).

Systems of equations and algebraic varieties

Let 𝐾 be a field with algebraic closure 𝐾, e.g., 𝐾 = R and 𝐾 = C. The polynomial ring with 𝑛 variables and coefficients in 𝐾 is 𝑅 = 𝐾 [𝑥 1 , . . . , 𝑥 𝑛 ]. We abbreviate 𝑥 = (𝑥 1 , . . . , 𝑥 𝑛 ) and use variable names 𝑥, 𝑦, 𝑧 rather than 𝑥 1 , 𝑥 2 , 𝑥 3 when 𝑛 is small. Elements of 𝑅 are polynomials, which are functions 𝑓 : 𝐾 𝑛 → 𝐾 of the form

𝑓 (𝑥) = ∑ 𝛼∈N 𝑛 𝑐 ( 𝛼 1 ,..., 𝛼 𝑛 ) 𝑥 𝛼 1 1 • • • 𝑥 𝛼 𝑛 𝑛 = ∑ 𝛼∈N 𝑛 𝑐 𝛼 𝑥 𝛼 ,
with finitely many nonzero coefficients 𝑐 𝛼 ∈ 𝐾. A system of polynomial equations is

𝑓 1 (𝑥) = • • • = 𝑓 𝑠 (𝑥) = 0, (6)
where 𝑓 1 , . . . , 𝑓 𝑠 ∈ 𝑅. By a solution of (6), we mean a point 𝑥 ∈ 𝐾 𝑛 satisfying all of these 𝑠 equations. Solving usually means finding coordinates for all solutions. This makes sense only when the set of solutions is finite, which typically happens when 𝑠 ≥ 𝑛. However, systems with infinitely many solutions can be 'solved' too, in an appropriate sense [START_REF] Sommese | Numerical decomposition of the solution sets of polynomial systems into irreducible components[END_REF]. We point out that one is often mostly interested in solutions 𝑥 ∈ 𝐾 𝑛 over the ground field 𝐾. The reason for allowing solutions over the algebraic closure 𝐾 is that many solution methods, like those discussed in Section 4, intrinsically compute all such solutions. For instance, ( 2) is a polynomial system with 𝑛 = 𝑠 = 𝑘 + ℓ, and the field is 𝐾 = R. Here are some other examples.

Example: univariate polynomials (𝑛 = 1) and linear equations

When 𝑛 = 𝑠 = 1, solving the polynomial system defined by

𝑓 = 𝑎 0 +𝑎 1 𝑥+• • •+𝑎 𝑑 𝑥 𝑑 ∈ 𝐾 [𝑥],
with 𝑎 𝑑 ≠ 0, amounts to finding the roots of 𝑓 (𝑥) = 0 in 𝐾. These are the eigenvalues of the 𝑑 × 𝑑 companion matrix

𝐶 𝑓 = -𝑎 0 /𝑎 𝑑 1 -𝑎 1 /𝑎 𝑑 . . . . . . 1 -𝑎 𝑑-1 /𝑎 𝑑 (7) of 𝑓 , whose characteristic polynomial is det(𝑥 • id -𝐶 𝑓 ) = 𝑎 -1 𝑑 • 𝑓 . When 𝑓 𝑖 = 𝑛
𝑗=1 𝑎 𝑖 𝑗 𝑥 𝑗 -𝑏 𝑖 are given by affine-linear functions, ( 6) is a linear system of the form 𝐴𝑥 = 𝑏, with 𝐴 ∈ 𝐾 𝑠×𝑛 , 𝑏 ∈ 𝐾 𝑠 . This example shows that, after a trivial rewriting step, the univariate and affine-linear cases are reduced to a linear algebra problem. Here, we are mainly interested in the case where 𝑛 > 1, and some equations are of degree > 1. Such systems require tools from nonlinear algebra [START_REF] Michałek | Invitation to nonlinear algebra[END_REF]. We proceed with an example in two dimensions.

Example: intersecting two curves in the plane

Let 𝐾 = Q and 𝑛 = 𝑠 = 2. We work in the ring 𝑅 = Q[𝑥, 𝑦] and consider the system of equations 𝑓 (𝑥, 𝑦) = 𝑔(𝑥, 𝑦) = 0 where

𝑓 = -7𝑥 -9𝑦 -10𝑥 2 + 17𝑥𝑦 + 10𝑦 2 + 16𝑥 2 𝑦 -17𝑥𝑦 2 , 𝑔 = 2𝑥 -5𝑦 + 5𝑥 2 + 5𝑥𝑦 + 5𝑦 2 -6𝑥 2 𝑦 -6𝑥𝑦 2 . (8)
Geometrically, we can think of 𝑓 (𝑥, 𝑦) = 0 as defining a curve in the plane. This is the orange curve shown in Fig. 1a. The curve defined by 𝑔(𝑥, 𝑦) = 0 is shown in blue. The set of solutions of 𝑓 = 𝑔 = 0 consists of points (𝑥, 𝑦) ∈ Q 2 satisfying 𝑓 (𝑥, 𝑦) = 𝑔(𝑥, 𝑦) = 0. These are the intersection points of the two curves. There are seven such points in Q 2 , of which two lie in Q 2 . These are the points (0, 0) and [START_REF] Baldi | Computing real radicals by moment optimization[END_REF][START_REF] Baldi | Computing real radicals by moment optimization[END_REF]. Note that all seven solutions are real: replacing Q by 𝐾 = R, we count as many solutions over 𝐾 as over 𝐾 = C. The set of solutions of the polynomial system ( 6) is called an affine variety. We denote this by 𝑉 Example: surfaces in R 3

𝐾 ( 𝑓 1 , . . . , 𝑓 𝑠 ) = {𝑥 ∈ 𝐾 𝑛 | 𝑓 1 (𝑥) = • • • = 𝑓 𝑠 (𝑥) = 0},
Let 𝐾 = R and consider the affine variety 𝑉 = 𝑉 C ( 𝑓 ) where

𝑓 = 81(𝑥 3 + 𝑦 3 + 𝑧 3 ) -189(𝑥 2 𝑦 + 𝑥 2 𝑧 + 𝑦 2 𝑥 + 𝑦 2 𝑧 + 𝑥𝑧 2 + 𝑦𝑧 2 ) + 54𝑥𝑦𝑧 + 126(𝑥𝑦 + 𝑥𝑧 + 𝑦𝑧) -9(𝑥 2 + 𝑦 2 + 𝑧 2 ) -9(𝑥 + 𝑦 + 𝑧) + 1. (9)
Its real part 𝑉 R ( 𝑓 ) is the surface shown in Fig. 1b. The variety 𝑉 is called the Clebsch surface. It is a cubic surface because it is defined by an equation of degree three. We will revisit this surface in Section 5. Note that 𝑓 is invariant under permutations of the variables, i.e., 𝑓 (𝑥, 𝑦, 𝑧) = 𝑓 (𝑦, 𝑥, 𝑧) = 𝑓 (𝑧, 𝑦, 𝑥) = 𝑓 (𝑥, 𝑧, 𝑦) = 𝑓 (𝑧, 𝑥, 𝑦) = 𝑓 (𝑦, 𝑧, 𝑥). This reflects in the symmetries of the surface 𝑉 R ( 𝑓 ). Many polynomials from applications have similar symmetry properties. Exploiting this in computations is an active area of research, see for instance [START_REF] Hubert | Algorithms for fundamental invariants and equivariants[END_REF].

More pictures of real affine varieties can be found, for instance, in [16, Chapter 1, §2], or in the algebraic surfaces gallery hosted at https://homepage.univie.ac.at/herwig.hauser/bildergalerie/gallery.html. We now briefly discuss commonly used fields 𝐾. In many engineering applications, the coefficients of 𝑓 1 , . . . , 𝑓 𝑠 lie in R or C. Computations in such fields use floating point arithmetic, yielding approximate results. The required quality of the approximation depends on the application. Other fields also show up: polynomial systems in cryptography often use 𝐾 = F 𝑞 , see for instance [START_REF] Sala | Gröbner bases, coding, and cryptography: a guide to the state-of-art[END_REF]. Equations of many prominent algebraic varieties have integer coefficients, i.e., 𝐾 = Q. Examples are determinantal varieties (e.g., the variety of all 𝑚 × 𝑛 matrices of rank < min(𝑚, 𝑛)), Grassmannians in their Plücker embedding [START_REF] Michałek | Invitation to nonlinear algebra[END_REF]Chapter 5], discriminants and resultants [49, Sections 3.4, 5.2] and toric varieties obtained from monomial maps [START_REF] Telen | Introduction to toric geometry[END_REF]Section 2.3]. In number theory, one is interested in studying rational points 𝑉 Q ( 𝑓 1 , . . . , 𝑓 𝑠 ) ⊂ 𝑉 Q ( 𝑓 1 , . . . , 𝑓 𝑠 ) on varieties defined over Q. Recent work in this direction for del Pezzo surfaces can be found in [START_REF] Mitankin | Rational points on del Pezzo surfaces of degree four[END_REF][START_REF] Desjardins | Density of rational points on a family of del Pezzo surfaces of degree one[END_REF]. Finally, in tropical geometry, coefficients come from valued fields such as the 𝑝-adic numbers Q 𝑝 or the Puiseux series C{{𝑡}} [START_REF] Maclagan | Introduction to tropical geometry[END_REF]. Solving over the field of Puiseux series is also relevant for homotopy continuation methods, see Section 4.2. We end the section with two examples highlighting the difference between 𝑉 𝐾 ( 𝑓 1 , . . . , 𝑓 𝑠 ) and 𝑉 𝐾 ( 𝑓 1 , . . . , 𝑓 𝑠 ).

Example: Fermat's last theorem

Let 𝑘 ∈ N \ {0} be a positive integer and consider the equation 𝑓 = 𝑥 𝑘 + 𝑦 𝑘 -1 = 0. For any 𝑘, the variety 𝑉 Q ( 𝑓 ) has infinitely many solutions in Q

2

. For 𝑘 = 1, 2, there are infinitely many rational solutions, i.e. solutions in Q 2 . For 𝑘 ≥ 3, the only solutions in Q 2 are (1, 0), (0, 1) and, when 𝑘 is even, (-1, 0), (0, -1) [START_REF] Darmon | Fermat's last theorem[END_REF].

Example: computing real solutions

The variety 𝑉 C (𝑥 2 + 𝑦 2 ) consists of the two lines 𝑥 + √ -1 • 𝑦 = 0 and 𝑥 -√ -1 • 𝑦 = 0 in C 2 . However, the real part 𝑉 R (𝑥 2 + 𝑦 2 ) = {(0, 0)} has only one point. If we are interested only in this real solution, we may replace 𝑥 2 + 𝑦 2 with the two polynomials 𝑥, 𝑦, which have the property that 𝑉 R (𝑥 2 + 𝑦 2 ) = 𝑉 R (𝑥, 𝑦) = 𝑉 C (𝑥, 𝑦). After this replacing step, an algorithm that computes all complex solutions will still recover only the interesting solutions. It turns out that such a 'better' set of equations can always be computed. The new polynomials generate the real radical ideal associated to the original equations [START_REF] Michałek | Invitation to nonlinear algebra[END_REF]Sec. 6.3]. For recent computational progress, see [START_REF] Baldi | Computing real radicals by moment optimization[END_REF]. A different approach for real root finding in bounded domains is subdivision, see [START_REF] Mourrain | Subdivision methods for solving polynomial equations[END_REF].

Number of solutions

A univariate polynomial 𝑓 ∈ C[𝑥] of degree 𝑑 has at most 𝑑 roots in C. Moreover, 𝑑 is the expected number of roots. We now formalize this. Consider the family

F (𝑑) = {𝑎 0 + 𝑎 1 𝑥 + • • • + 𝑎 𝑑 𝑥 𝑑 | (𝑎 0 , . . . , 𝑎 𝑑 ) ∈ C 𝑑+1 } ≃ C 𝑑+1 (10)
of polynomials of degree at most 𝑑. There is an affine variety ∇ 𝑑 ⊂ C 𝑑+1 , such that all 𝑓 ∈ F (𝑑) \ ∇ 𝑑 have precisely 𝑑 roots in C. Here ∇ 𝑑 = 𝑉 C (Δ 𝑑 ), where Δ 𝑑 is a polynomial in the coefficients 𝑎 𝑖 of 𝑓 ∈ F (𝑑). Equations for small 𝑑 are

Δ 1 = 𝑎 1 , Δ 2 = 𝑎 2 • (𝑎 2 1 -4 𝑎 0 𝑎 2 ), Δ 3 = 𝑎 3 • (𝑎 2 1 𝑎 2 2 -4 𝑎 0 𝑎 3 2 -4 𝑎 3 1 𝑎 3 + 18 𝑎 0 𝑎 1 𝑎 2 𝑎 3 -27 𝑎 2 0 𝑎 2 3 ), Δ 4 = 𝑎 4 • (𝑎 2 1 𝑎 2 2 𝑎 2 3 -4 𝑎 0 𝑎 3 2 𝑎 2 3 -4 𝑎 3 1 𝑎 3 3 + 18 𝑎 0 𝑎 1 𝑎 2 𝑎 3 3 + • • • + 256 𝑎 3 0 𝑎 3 4 ).
Notice that Δ 𝑑 = 𝑎 𝑑 • Δ 𝑑 , where Δ 𝑑 is the discriminant for degree 𝑑 polynomials. Similar results exist for families of polynomial systems with 𝑛 > 1, which bound the number of isolated solutions from above by the expected number. This section states some of these results. It assumes that 𝐾 = 𝐾 is algebraically closed.

Bézout's theorem

Let 𝑅 = 𝐾 [𝑥] = 𝐾 [𝑥 1 , . . . , 𝑥 𝑛 ].
A monomial in 𝑅 is a finite product of variables:

𝑥 𝛼 = 𝑥 𝛼 1 • • • 𝑥 𝛼 𝑛 , 𝛼 ∈ N 𝑛 .
The degree of the monomial 𝑥 𝛼 is deg(𝑥 𝛼 ) = 𝑛 𝑖=1 𝛼 𝑖 , and the degree of a polynomial 𝑓 = 𝛼 𝑐 𝛼 𝑥 𝛼 is deg( 𝑓 ) = max { 𝛼 : 𝑐 𝛼 ≠0} deg(𝑥 𝛼 ). We define the vector subspaces

𝑅 𝑑 = { 𝑓 ∈ 𝑅 : deg( 𝑓 ) ≤ 𝑑}, 𝑑 ∈ N.
For an 𝑛-tuple of degrees (𝑑 1 , . . . , 𝑑 𝑛 ), we define the family of polynomial systems

F (𝑑 1 , . . . , 𝑑 𝑛 ) = 𝑅 𝑑 1 × • • • × 𝑅 𝑑 𝑛 . That is, 𝐹 = ( 𝑓 1 , . . . , 𝑓 𝑛 ) ∈ F (𝑑 1 , . . . , 𝑑 𝑛 ) satisfies deg( 𝑓 𝑖 ) ≤ 𝑑 𝑖 , 𝑖 = 1, . . . , 𝑛,
and represents the polynomial system 𝐹 = 0 with 𝑠 = 𝑛. We leave the fact that F (𝑑 1 , . . . , 𝑑 𝑛 ) ≃ 𝐾 𝐷 , with 𝐷 = 𝑛 𝑖=1 𝑛+𝑑 𝑖 𝑛 , as an exercise to the reader. Note that this is a natural generalization of [START_REF] Breiding | Nonlinear algebra and applications[END_REF]. The set of solutions of 𝐹 = 0 is denoted by 𝑉 𝐾 (𝐹) = 𝑉 𝐾 ( 𝑓 1 , . . . , 𝑓 𝑛 ), and a point in 𝑉 𝐾 (𝐹) is isolated if it does not lie on a component of 𝑉 𝐾 (𝐹) with dimension ≥ 1.

Theorem 1 (Bézout)

For any 𝐹 = ( 𝑓 1 , . . . , 𝑓 𝑛 ) ∈ F (𝑑 1 , . . . , 𝑑 𝑛 ), the number of isolated solutions of 𝑓 1 = • • • = 𝑓 𝑛 = 0, i.e., the number of isolated points in 𝑉 𝐾 (𝐹), is at most

𝑑 1 • • • 𝑑 𝑛 . Moreover, there exists a proper subvariety ∇ 𝑑 1 ,...,𝑑 𝑛 ⊊ 𝐾 𝐷 such that, when 𝐹 ∈ F (𝑑 1 , . . . , 𝑑 𝑛 ) \ ∇ 𝑑 1 ,...,𝑑 𝑛 , 𝑉 𝐾 (𝐹) consists of exactly 𝑑 1 • • • 𝑑 𝑛 isolated points.
The proof of this theorem can be found in [START_REF] Eisenbud | The geometry of schemes[END_REF]. As in our univariate example, the variety ∇ 𝑑 1 ,...,𝑑 𝑛 can be described using discriminants and resultants. See, for instance, the discussion at the end of [START_REF] Telen | Solving Systems of Polynomial Equations[END_REF]Section 3.4.1]. Theorem 1 is an important result and gives an easy way to bound the number of isolated solutions of a system of 𝑛 equations in 𝑛 variables. The bound is almost always tight, in the sense that the only systems with fewer solutions lie in ∇ 𝑑 1 ,...,𝑑 𝑛 . Unfortunately, many systems coming from applications lie inside ∇ 𝑑 1 ,...,𝑑 𝑛 . Here is an example.

Example: a planar robot arm

This example comes from robotics. Consider a planar robot arm whose shoulder is fixed at the origin (0, 0) in the plane, and whose two arm segments have fixed lengths 𝐿 1 and 𝐿 2 . We determine the possible positions of the elbow (𝑥, 𝑦), given that the hand of the robot touches a given point (𝑎, 𝑏). The situation is illustrated in Fig. 2. The Pythagorean theorem gives the identities

𝑥 2 + 𝑦 2 -𝐿 2 1 = (𝑎 -𝑥) 2 + (𝑏 -𝑦) 2 -𝐿 2 2 = 0, (11)
which is a system of 𝑠 = 2 equations in 𝑛 = 2 variables 𝑥, 𝑦. The plane curves corresponding to these equations are shown in Fig. 2. Their intersection points are the possible configurations. Naturally, more complicated robots lead to more involved equations, see [START_REF] Wampler | Numerical algebraic geometry and algebraic kinematics[END_REF]. The system [START_REF] Breiding | Certifying zeros of polynomial systems using interval arithmetic[END_REF] with 𝐾 = C lies in ∇ 2,2 : the two real solutions seen in Fig. 2 are the only solutions over C, and 2 < 𝑑 1 • 𝑑 2 = 4. However, the slightest perturbation of the equations introduces two extra solutions. For instance, replace the first equation with 𝑥 2 + 𝜖 • 𝑥𝑦 + 𝑦 2 -𝐿 2 1 = 0, for small 𝜖. The resulting system lies in F (2, 2) \ ∇ 2,2 . It has four complex solutions, two of which lie close to the intersection points in Figure 2. The other two are large, see Remark 1.

Remark 1 Bézout's theorem more naturally counts solutions in projective space P 𝑛 𝐾 , and it accounts for solutions with multiplicity > 1. More precisely, if 𝑓 𝑖 is a homogeneous polynomial in 𝑛 + 1 variables of degree 𝑑 𝑖 , and 𝑓 1 = • • • = 𝑓 𝑛 = 0 has finitely many solutions in P 𝑛 𝐾 , the number of solutions (counted with multiplicity) is always 𝑑 1 • • • 𝑑 𝑛 . We encourage the reader who is familiar with projective geometry to check that [START_REF] Breiding | Certifying zeros of polynomial systems using interval arithmetic[END_REF] defines two solutions at infinity, when each of the equations is viewed as an equation on P 2 C by homogenizing. Introducing 𝜖 brings these solutions back into C 2 . Since they come from infinity, they have large coordinates.

Kushnirenko's theorem

An intuitive consequence of Theorem 1 is that random polynomial systems given by polynomials of fixed degree always have the same number of solutions. Looking at 𝑓 and 𝑔 from ( 8), we see that they do not look so random, in the sense that some monomials of degree ≤ 3 are missing. For instance, 𝑥 3 and 𝑦 3 do not appear. Having zero coefficients standing with some monomials in F (𝑑 1 , . . . , 𝑑 𝑛 ) is sometimes enough to conclude that the system lies in ∇ 𝑑 1 ,...,𝑑 𝑛 . That is, the system is not random in the sense of Bézout's theorem. The (monomial

) support of 𝑓 = 𝛼 𝑐 𝛼 𝑥 𝛼 is supp ∑ 𝛼 𝑐 𝛼 𝑥 𝛼 = {𝛼 : 𝑐 𝛼 ≠ 0} ⊂ N 𝑛 .
This subsection considers families of polynomial systems with fixed support. Let A ⊂ N 𝑛 be a finite subset of exponents of cardinality |A|. We define

F (A) = { ( 𝑓 1 , . . . , 𝑓 𝑛 ) ∈ 𝑅 𝑛 : supp( 𝑓 𝑖 ) ⊂ A, 𝑖 = 1, . . . , 𝑛 } ≃ 𝐾 𝑛• | A | .
The next theorem expresses the number of solutions for systems in this family in terms of the volume Vol

(A) = ∫ Conv( A) d𝛼 1 • • • d𝛼 𝑛 of the convex polytope Conv(A) = ∑ 𝛼∈A 𝜆 𝛼 • 𝛼 : 𝜆 𝛼 ≥ 0, ∑ 𝛼∈A 𝜆 𝛼 = 1 ⊂ R 𝑛 . ( 12
)
The normalized volume vol(A) is defined as 𝑛! • Vol(A).

Theorem 2 (Kushnirenko)

For any 𝐹 = ( 𝑓 1 , . . . , 𝑓 𝑛 ) ∈ F (A), the number of isolated solutions of

𝑓 1 = • • • = 𝑓 𝑛 = 0 in (𝐾 \ {0}) 𝑛 , i.e.
, the number of isolated points in 𝑉 𝐾 (𝐹) ∩ (𝐾 \ {0}) 𝑛 , is at most vol(A). Moreover, there exists a proper subvariety

∇ A ⊊ 𝐾 𝑛• | A | such that, when 𝐹 ∈ F (A) \ ∇ A , 𝑉 𝐾 (𝐹) ∩ (𝐾 \ {0}) 𝑛 consists of vol(A) isolated points.
For a proof, see [START_REF] Kushnirenko | Newton polytopes and the Bézout theorem[END_REF]. The theorem necessarily counts solutions in (𝐾 \{0}) 𝑛 ⊂ 𝐾 𝑛 , as multiplying all equations with a monomial 𝑥 𝛼 may change the number of solutions in the coordinate hyperplanes (i.e., there may be new solutions with zero-coordinates). However, it does not change the normalized volume vol(A). The statement can be adapted to count solutions in 𝐾 𝑛 , but becomes more involved [START_REF] Huber | Bernstein's theorem in affine space[END_REF]. We point out that, with the extra assumption that 0 ∈ A, one may replace (𝐾 \ {0}) 𝑛 by 𝐾 𝑛 in Theorem 2. To compare Kushnirenko's theorem with Bézout, note that F (A) for

A = {𝛼 ∈ N 𝑛 : deg(𝑥 𝛼 ) ≤ 𝑑} (13)
is F (𝑑, . . . , 𝑑), and 𝑑 𝑛 = vol(A). Theorem 2 recovers Theorem 1 for

𝑑 1 = • • • = 𝑑 𝑛 .

Example: back to plane curves

The polynomial system 𝑓 = 𝑔 = 0 from (8) belongs to the family F (A) with

A = {(1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2)}. The convex hull Conv(A) is a hexagon in R 2 , see Fig. 3. Its normalized volume is vol(A) = 𝑛!•Vol(A) = 2!•3 = 6.
Theorem 2 predicts six solutions in (Q \ {0}) 2 . These are six of the seven black dots seen in the left part of Fig. 1a: the solution (0, 0) is not counted. We have a chain of inclusions

∇ A ⊂ F (A) ⊂ ∇ 3,3 ⊂ F (3, 3) and ( 𝑓 , 𝑔) ∈ F (A) \ ∇ A . 𝑥 𝑥 𝑦 𝑥 𝑦 2 𝑦 𝑦 2 𝑥 2 𝑥 2 𝑦

Bernstein's theorem

There is a generalization of Kushnirenko's theorem which allows different supports for the polynomials 𝑓 1 , . . . , 𝑓 𝑛 . We fix 𝑛 finite subsets of exponents A 1 , . . . , A 𝑛 ⊂ N 𝑛 with respective cardinalities |A 𝑖 |. These define the family of polynomial systems

F (A 1 , . . . , A 𝑛 ) = { ( 𝑓 1 , . . . , 𝑓 𝑛 ) ∈ 𝑅 𝑛 : supp( 𝑓 𝑖 ) ⊂ A 𝑖 , 𝑖 = 1, . . . , 𝑛 } ≃ 𝐾 𝐷 , where 𝐷 = |A 1 | + • • • + |A 𝑛 |.
The number of solutions is characterized by the mixed volume of A 1 , . . . , A 𝑛 , which we now define. The Minkowski sum 𝑆 + 𝑇 of two sets 𝑆, 𝑇 ⊂ R 𝑛 is {𝑠 + 𝑡 : 𝑠 ∈ 𝑆, 𝑡 ∈ 𝑇 }, where 𝑠 + 𝑡 is the usual addition of vectors in R 𝑛 . For a nonnegative real number 𝜆, the 𝜆-

dilation of 𝑆 ⊂ R 𝑛 is 𝜆 • 𝑆 = {𝜆 • 𝑠 : 𝑠 ∈ 𝑆},
where 𝜆 • 𝑠 is the usual scalar multiplication in R 𝑛 . Each of the supports A 𝑖 gives a convex polytope Conv(A 𝑖 ) as in [START_REF] Breiding | HomotopyContinuation.jl: A package for homotopy continuation in Julia[END_REF]. The function R 𝑛 ≥0 → R ≥0 given by

(𝜆 1 , . . . , 𝜆 𝑛 ) ↦ -→ Vol( 𝜆 1 • Conv(A 1 ) + • • • + 𝜆 𝑛 • Conv(A 𝑛 ) ) (14)
is a homogeneous polynomial of degree 𝑛, meaning that all its monomials have degree 𝑛 [15, Chapter 7, §4, Proposition 4.9]. The mixed volume MV(A 1 , . . . , A 𝑛 ) is the coefficient of the polynomial ( 14) standing with the monomial 𝜆 1 • • • 𝜆 𝑛 .

Theorem 3 (Bernstein-Kushnirenko)

For any 𝐹 = ( 𝑓 1 , . . . , 𝑓 𝑛 ) ∈ F (A 1 , . . . , A 𝑛 ), the number of isolated solutions of

𝑓 1 = • • • = 𝑓 𝑛 = 0 in (𝐾 \ {0}) 𝑛 , i.e.
, the number of isolated points in 𝑉 𝐾 (𝐹) ∩ (𝐾 \ {0}) 𝑛 , is at most MV(A 1 , . . . , A 𝑛 ). Moreover, there exists a proper subvariety ∇ A 1 ,..., A 𝑛 ⊂ 𝐾 𝐷 such that, when 𝐹 ∈ F (A 1 , . . . , A 𝑛 ) \ ∇ A 1 ,..., A 𝑛 , 𝑉 𝐾 (𝐹) ∩ (𝐾 \ {0}) 𝑛 consists of precisely MV(A 1 , . . . , A 𝑛 ) isolated points.

This theorem was originally proved by Bernstein for 𝐾 = C in [START_REF] Bernstein | The number of roots of a system of equations[END_REF]. The proof by Kushnirenko in [START_REF] Kushnirenko | Newton polytopes and the Bézout theorem[END_REF] works for algebraically closed fields. Several alternative proofs were found by Khovanskii [START_REF] Khovanskii | Newton polyhedra and the genus of complete intersections[END_REF]. Theorem 3 is sometimes called the BKK theorem, after the aforementioned mathematicians. Like Kushnirenko's theorem, Theorem 3 can be adapted to count roots in 𝐾 𝑛 rather than (𝐾 \ {0}) 𝑛 [START_REF] Huber | Bernstein's theorem in affine space[END_REF], and if 0 ∈ A 𝑖 for all 𝑖, one may replace (𝐾 \ {0}) 𝑛 by 𝐾 𝑛 .

When

A 1 = • • • = A 𝑛 = A, we have F (A 1 , . . . , A 𝑛 ) = F (A)
, and when A 𝑖 = {𝛼 ∈ N 𝑛 : deg(𝑥 𝛼 ) ≤ 𝑑 𝑖 }, we have F (A 1 , . . . , A 𝑛 ) = F (𝑑 1 , . . . , 𝑑 𝑛 ). Hence, all families of polynomials we have seen before are of this form, and Theorem 3 generalizes Theorems 1 and 2. Note that, in particular, we have MV(A, . . . , A) = vol(A).

Example: mixed areas

A useful formula for 𝑛 = 2 is MV(A 1 , A 2 ) = Vol(A 1 + A 2 ) -Vol(A 1 ) -Vol(A 2 ).
For instance, the following two polynomials appear in [49, Example 5.3.1]:

𝑓 = 𝑎 0 + 𝑎 1 𝑥 3 𝑦 + 𝑎 2 𝑥𝑦 3 , 𝑔 = 𝑏 0 + 𝑏 1 𝑥 2 + 𝑏 2 𝑦 2 + 𝑏 3 𝑥 2 𝑦 2 .
The system 𝑓 = 𝑔 = 0 is a general member of the family F (A 1 , A 2 ) ≃ 𝐾 7 , where A 1 = {(0, 0), (3, 1), (1, 3)} and A 2 = {(0, 0), (2, 0), (0, 2), (2, 2)}. The Newton polygons, together with their Minkowski sum, are shown in Fig. 4. By applying the Fig. 4: The green area counts the solutions to equations with support in 𝑃 1 , 𝑃 2 . formula for MV(A 1 , A 2 ) seen above, we find that the mixed volume for the system 𝑓 = 𝑔 = 0 is the green area in the right part of Fig. 4, which is 12. Note that the Bézout bound (Theorem 1) is 16. and Theorem 2 also predicts 12 solutions, with

A = A 1 ∪ A 2 . Hence F (A 1 , A 2 ) ⊂ F (A) ⊂ ∇ 4,4 ⊂ F (4, 4) and F (A 1 , A 2 ) ⊄ ∇ A .
Theorem 3 provides an upper bound on the number of isolated solutions to any system of polynomial equations with 𝑛 = 𝑠. Although it improves significantly on Bézout's bound for many systems, it still often happens that the bound is not tight for systems in applications. That is, one often encounters systems 𝐹 ∈ ∇ A 1 ,..., A 𝑛 . Even more refined root counts exist, such as those based on Newton-Okounkov bodies [START_REF] Kaveh | Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory[END_REF]. In practice, with today's computational methods (see Section 4), we often count solutions reliably by simply solving the system. Certification methods provide a proof for a lower bound on the number of solutions [START_REF] Breiding | Certifying zeros of polynomial systems using interval arithmetic[END_REF]. The actual number of solutions is implied if one can match this with a theoretical upper bound.

Computational methods

We give a brief introduction to two of the most important computational methods for solving polynomial equations. The first method uses normal forms, the second is based on homotopy continuation. We keep writing 𝐹 = ( 𝑓 1 , . . . , 𝑓 𝑠 ) = 0 for the system we want to solve. We require 𝑠 ≥ 𝑛, and assume finitely many solutions over 𝐾. All methods discussed here compute all solutions over 𝐾, so we keep assuming that 𝐾 = 𝐾 is algebraically closed. An important distinction between normal forms and homotopy continuation is that the former works over any field 𝐾, while the latter needs 𝐾 = C. If the coefficients are contained in a subfield (e.g. R ⊂ C), a significant part of the computation in normal form algorithms can be done over this subfield. Also, homotopy continuation is most natural when 𝑛 = 𝑠, whereas 𝑠 > 𝑛 is not so much a problem for normal forms. However, if 𝐾 = C and 𝑛 = 𝑠, continuation methods are extremely efficient and can compute millions of solutions.

Normal form methods

Let 𝐼 = ⟨ 𝑓 1 , . . . , 𝑓 𝑠 ⟩ ⊂ 𝑅 = 𝐾 [𝑥 1 , . . . , 𝑥 𝑛 ] be the ideal generated by our polynomials. For ease of exposition, we assume that 𝐼 is radical, which is equivalent to all points in 𝑉 𝐾 (𝐼) = 𝑉 𝐾 ( 𝑓 1 , . . . , 𝑓 𝑠 ) having multiplicity one. In other words, the Jacobian matrix (𝜕 𝑓 𝑖 /𝜕𝑥 𝑗 ), evaluated at any of the points in 𝑉 𝐾 (𝐼), has rank 𝑛. Let us write 𝑉 𝐾 (𝐼) = {𝑧 1 , . . . , 𝑧 𝛿 } ⊂ 𝐾 𝑛 for the set of solutions, and 𝑅/𝐼 for the quotient ring obtained from 𝑅 by the equivalence relation 𝑓 ∼ 𝑔 ⇔ 𝑓 -𝑔 ∈ 𝐼. The main observation behind normal form methods is that the coordinates of 𝑧 𝑖 are encoded in the eigenstructure of the 𝐾-linear endomorphisms 𝑀 𝑔 : 𝑅/𝐼 → 𝑅/𝐼 given by

[ 𝑓 ] ↦ → [𝑔 • 𝑓 ],
where [ 𝑓 ] is the residue class of 𝑓 in 𝑅/𝐼.

We will now make this precise. First, we show that dim 𝐾 𝑅/𝐼 = 𝛿. We define ev 𝑖 : 𝑅/𝐼 → 𝐾 as ev 𝑖 ( [ 𝑓 ]) = 𝑓 (𝑧 𝑖 ), and combine these to get ev = ( ev 1 , . . . , ev 𝛿 ) : 𝑅/𝐼 -→ 𝐾 𝛿 , given by ev( [ 𝑓 ]) = ( 𝑓 (𝑧 1 ), . . . , 𝑓 (𝑧 𝛿 ) ).

By Hilbert's Nullstellensatz

Theorem 4

The left eigenvectors of the 𝐾-linear map 𝑀 𝑔 are the evaluation functionals ev 𝑖 , 𝑖 = 1, . . . , 𝛿. The eigenvalue corresponding to ev 𝑖 is 𝑔(𝑧 𝑖 ).

Proof We have (ev

𝑖 •𝑀 𝑔 ) ( [ 𝑓 ]) = ev 𝑖 ( [𝑔• 𝑓 ]) = 𝑔(𝑧 𝑖 ) 𝑓 (𝑧 𝑖 ) = 𝑔(𝑧 𝑖 )•ev 𝑖 ( [ 𝑓 ]), which
shows that ev 𝑖 is a left eigenvector with eigenvalue 𝑔(𝑧 𝑖 ). Moreover, the ev 𝑖 form a complete set of eigenvectors, since ev : 𝑅/𝐼 → 𝐾 𝛿 is a 𝐾-linear isomorphism. □ We encourage the reader to check that the residue classes of the Lagrange polynomials [ℓ 𝑖 ] ∈ 𝑅/𝐼 form a complete set of right eigenvectors. We point out that, after choosing a basis of 𝑅/𝐼, the functional ev 𝑖 is represented by a row vector 𝑤 ⊤ 𝑖 of length 𝛿, and 𝑀 𝑔 is a multiplication matrix of size 𝛿 × 𝛿. The eigenvalue relation in the proof of Theorem 4 reads more familiarly as 𝑤 ⊤ 𝑖 𝑀 𝑔 = 𝑔(𝑧 𝑖 ) • 𝑤 ⊤ 𝑖 . Theorem 4 suggests breaking up the task of computing 𝑉 𝐾 (𝐼) = {𝑧 𝑖 } 𝛿 𝑖=1 into two parts: (A) Compute multiplication matrices 𝑀 𝑔 and (B) extract the coordinates of 𝑧 𝑖 from their eigenvectors or eigenvalues.

For step (B), let {[𝑏 1 ], . . . , [𝑏 𝛿 ]} be a 𝐾-basis for 𝑅/𝐼, with 𝑏 𝑗 ∈ 𝑅. The vector 𝑤 𝑖 is explicitly given by 𝑤 𝑖 = (𝑏 1 (𝑧 𝑖 ), . . . , 𝑏 𝛿 (𝑧 𝑖 )). If the coordinate functions 𝑥 1 , . . . , 𝑥 𝑛 are among the 𝑏 𝑗 , one reads the coordinates of 𝑧 𝑖 directly from the entries of 𝑤 𝑖 . If not, some more processing might be needed. Alternatively, one can choose 𝑔 = 𝑥 𝑗 and read the 𝑗-th coordinates of the 𝑧 𝑖 from the eigenvalues of 𝑀 𝑥 𝑗 . There are many things to say about these procedures, in particular about their efficiency and numerical stability. We refer the reader to [START_REF] Telen | Solving Systems of Polynomial Equations[END_REF]Remark 4.3.4] for references and more details, and do not elaborate on this here.

We turn to step (A), which is where normal forms come into play. Suppose a basis {[𝑏 1 ], . . . , [𝑏 𝛿 ]} of 𝑅/𝐼 is fixed. We identify 𝑅/𝐼 with 𝐵 = span 𝐾 (𝑏 1 , . . . , 𝑏 𝛿 ) ⊂ 𝑅. For any 𝑓 ∈ 𝑅, there are unique constants 𝑐 𝑗 ( 𝑓 ) ∈ 𝐾 such that

𝑓 - 𝛿 ∑ 𝑗=1 𝑐 𝑗 ( 𝑓 ) • 𝑏 𝑗 ∈ 𝐼. ( 15
)
These are the coefficients in the unique expansion of

[ 𝑓 ] = 𝛿 𝑗=1 𝑐 𝑗 ( 𝑓 ) • [𝑏 𝑗 ] in our basis. The 𝐾-linear map N : 𝑅 → 𝐵 which sends 𝑓 to 𝛿 𝑗=1 𝑐 𝑗 ( 𝑓 ) • 𝑏 𝑗 is called a normal form.
Its key property is that N projects 𝑅 onto 𝐵 along 𝐼, meaning that N •N = N (N |𝐵 is the identity), and ker N = 𝐼. The multiplication map 𝑀 𝑔 : 𝐵 → 𝐵 is simply given by 𝑀 𝑔 (𝑏) = N (𝑔 • 𝑏). More concretely, the 𝑖-th column of the matrix representation of 𝑀 𝑔 contains the coefficients 𝑐 𝑗 (𝑔 • 𝑏 𝑖 ), 𝑗 = 1, . . . , 𝛿 of N (𝑔 • 𝑏 𝑖 ). Here is a familiar example. One checks this by verifying that 𝑥 𝑖 -N (𝑥 𝑖 ) ∈ ⟨ 𝑓 ⟩. The coefficients 𝑐 𝑗 (𝑥 𝑖 ), 𝑗 = 1, . . . , 𝑑 of N (𝑥 𝑖 ) form the 𝑖-th column of the companion matrix 𝐶 𝑓 in [START_REF] Berthomieu | msolve: A library for solving polynomial systems[END_REF]. Hence 𝑀 𝑥 = 𝐶 𝑓 , and Theorem 4 confirms that the eigenvalues of 𝐶 𝑓 are the roots of 𝑓 .

Example: normal forms for

𝑛 = 1 Let 𝐼 = ⟨ 𝑓 ⟩ = ⟨𝑎 0 + 𝑎 1 𝑥 + • • • + 𝑎 𝑑 𝑥 𝑑 ⟩
Computing normal forms can be done using linear algebra on certain structured matrices, called Macaulay matrices. We illustrate this with an example from [START_REF] Telen | A stabilized normal form algorithm for generic systems of polynomial equations[END_REF].

Example: Macaulay matrices

Consider the ideal 𝐼 = ⟨ 𝑓 , 𝑔⟩ ⊂ Q[𝑥, 𝑦] given by 𝑓 = 𝑥 2 + 𝑦 2 -2, 𝑔 = 3𝑥 2 -𝑦 2 -2. The variety 𝑉 Q (𝐼) = 𝑉 Q (𝐼) consists of 4 points {(-1, - 1
), (-1, 1), (1, -1), (1, 1)}, as predicted by Theorem 1. We construct a Macaulay matrix whose rows are indexed by 𝑓 , 𝑥 𝑓 , 𝑦 𝑓 , 𝑔, 𝑥𝑔, 𝑦𝑔, and whose columns are indexed by all monomials of degree ≤ 3:

M =             𝑥 3 𝑥 2 𝑦 𝑥 𝑦 2 𝑦 3 𝑥 2 𝑦 2 1 𝑥 𝑦 𝑥 𝑦 𝑓 1 1 -2 𝑥 𝑓 1 1 -2 𝑦 𝑓 1 1 -2 𝑔 3 -1 -2 𝑥𝑔 3 -1 -2 𝑦𝑔 3 -1 -2             . The first row reads 𝑓 = 1•𝑥 2 +1•𝑦 2 -2•1. A basis for Q[𝑥, 𝑦]/𝐼 is {[1], [𝑥], [𝑦], [𝑥𝑦]}.
These monomials index the last four columns. We now invert the leftmost 6 × 6 block and apply this inverse from the left to M:

M =             𝑥 3 𝑥 2 𝑦 𝑥 𝑦 2 𝑦 3 𝑥 2 𝑦 2 1 𝑥 𝑦 𝑥 𝑦 𝑥 3 -𝑥 1 -1 𝑥 2 𝑦-𝑦 1 -1 𝑥 𝑦 2 -𝑥 1 -1 𝑦 3 -𝑦 1 -1 𝑥 2 -1 1 -1 𝑦 2 -1 1 -1             .
The rows of M are linear combinations of the rows of M, representing polynomials in 𝐼. The first row reads 𝑥 3 -1 • 𝑥 ∈ 𝐼. Comparing this with [START_REF] Cox | Using algebraic geometry[END_REF], we see that we have found that N (𝑥 3 ) = 𝑥. Using M we can construct 𝑀 𝑥 and 𝑀 𝑦 :

𝑀 𝑥 =         [𝑥 ] [𝑥 2 ] [𝑥 𝑦 ] [𝑥 2 𝑦 ] [1] 0 1 0 0 [𝑥 ]
1 0 0 0

[𝑦 ] 0 0 0 1

[𝑥 𝑦 ] 0 0 1 0         , 𝑀 𝑦 =         [𝑦 ] [𝑥 𝑦 ] [𝑦 2 ] [𝑥 𝑦 2 ] [1]
0 0 1 0

[𝑥 ] 0 0 0 1 [𝑦 ]
1 0 0 0

[𝑥 𝑦 ] 0 1 0 0         .
The reader is encouraged to verify Theorem 4 for these matrices.

Remark 4

The entries of a Macaulay matrix M are the coefficients of the polynomials 𝑓 1 , . . . , 𝑓 𝑠 . An immediate consequence of the fact that normal forms are computed using linear algebra on Macaulay matrices is that when the coefficients of 𝑓 𝑖 are contained in a subfield K ⊂ 𝐾, all computations in step ( 𝐴) can be done over K. This assumes the polynomials 𝑔 for which we want to compute 𝑀 𝑔 have coefficients in K.

As illustrated in the example above, to compute the matrices 𝑀 𝑔 it is sufficient to determine the restriction of the normal form N : 𝑅 → 𝐵 to a finite-dimensional 𝐾-vector space 𝑉 ⊂ 𝑅, containing 𝑔 • 𝐵. The restriction N |𝑉 : 𝑉 → 𝐵 is called a truncated normal form, see [START_REF] Telen | Solving polynomial systems via truncated normal forms[END_REF] and [START_REF] Telen | Solving Systems of Polynomial Equations[END_REF]Chapter 4]. The dimension of the space 𝑉 counts the number of columns of the Macaulay matrix.

Usually, one chooses the basis elements 𝑏 𝑗 of 𝐵 to be monomials, and 𝑔 to be a coordinate function 𝑥 𝑖 . The basis elements may arise as standard monomials from a Gröbner basis computation. We briefly discuss this important concept.

• > Gröbner bases

Gröbner bases are powerful tools for symbolic computation in algebraic geometry. A nice way to motivate their definition is by considering Euclidean division as a candidate for a normal form map. In the case 𝑛 = 1, this rewrites 𝑔 ∈ 𝐾 [𝑥] as

𝑔 = 𝑞 • 𝑓 + 𝑟, where deg(𝑟) < 𝑑. (16)
Clearly

[𝑔] = [𝑟] in 𝐾 [𝑥]/⟨ 𝑓 ⟩, and N (𝑔) = 𝑟 since 𝑟 ∈ 𝐵 = span 𝐾 (1, 𝑥, . . . , 𝑥 𝑑-1
).

To generalize this to 𝑛 > 1 variables, we fix a monomial order ⪯ on 𝑅 = 𝐾 [𝑥 1 , . . . , 𝑥 𝑛 ] and write LT( 𝑓 ) for the leading term of 𝑓 with respect to ⪯. The reader who is unfamiliar with monomial orders can consult [16, Chapter 2, §2]. As above, let 𝐼 = ⟨ 𝑓 1 , . . . , 𝑓 𝑠 ⟩ ⊂ 𝑅 be a radical ideal such that |𝑉 𝐾 (𝐼)| = 𝛿 < ∞. As basis elements 𝑏 1 , . . . , 𝑏 𝛿 of 𝐵 ≃ 𝑅/𝐼, we use the 𝛿 ⪯-smallest monomials which are linearly independent modulo our ideal 𝐼. They are also called standard monomials. By [16, Chapter 9, §3, Theorem 3], there exists an algorithm which, for any input 𝑔 ∈ 𝑅, computes 𝑞 1 , . . . , 𝑞 𝑠 , 𝑟 ∈ 𝑅 such that

𝑔 = 𝑞 1 • 𝑓 1 + • • • + 𝑞 𝑠 • 𝑓 𝑠 +𝑟,
where LT( 𝑓 𝑖 ) does not divide any term of 𝑟, ∀𝑖. [START_REF] Darmon | Fermat's last theorem[END_REF] This algorithm is called multivariate Euclidean division. Note how the condition "LT( 𝑓 𝑖 ) does not divide any term of 𝑟, for all 𝑖" generalizes deg(𝑟) < 𝑑 in [START_REF] Cox | Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra[END_REF]. From [START_REF] Darmon | Fermat's last theorem[END_REF], it is clear that [𝑔] = [𝑟]. However, we do not have 𝑟 ∈ 𝐵 in general. Hence, unfortunately, sending 𝑔 to its remainder 𝑟 is usually not a normal form. . . but it is when 𝑓 1 , . . . , 𝑓 𝑠 is a Gröbner basis! A set of polynomials 𝑔 1 , . . . , 𝑔 𝑘 ∈ 𝐼 forms a Gröbner basis of the ideal 𝐼 if the leading terms LT(𝑔 1 ), . . . , LT(𝑔 𝑘 ) generate the leading term ideal ⟨LT(𝑔) : 𝑔 ∈ 𝐼⟩. We point out that no finiteness of 𝑉 𝐾 (𝐼) or radicality of 𝐼 is required for this definition. The remainder 𝑟 in 𝑔 = 𝑞 1 • 𝑔 1 +• • •+ 𝑞 𝑘 • 𝑔 𝑘 +𝑟 where LT( 𝑓 𝑖 ) does not divide any term of 𝑟, for all 𝑖, now satisfies [𝑔] = [𝑟] and 𝑟 ∈ 𝐵. This justifies the following claim:

Taking remainder upon Euclidean division by a Gröbner basis is a normal form.

Computing a Gröbner basis 𝑔 1 , . . . , 𝑔 𝑘 from a set of input polynomials 𝑓 1 , . . . , 𝑓 𝑠 can be interpreted as Gaussian elimination on a Macaulay matrix [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF]. Once this has been done, multiplication matrices are computed via taking remainder upon Euclidean division by {𝑔 1 , . . . , 𝑔 𝑘 }.

On a sidenote, we point out that Gröbner bases are often used for the elimination of variables. For instance, if 𝑔 1 , . . . , 𝑔 𝑘 form a Gröbner basis of an ideal 𝐼 with respect to a lex monomial order for which 𝑥 1 ≺ 𝑥 2 ≺ • • • ≺ 𝑥 𝑛 , we have for 𝑗 = 1, . . . 𝑛 that the 𝑗-th elimination ideal

𝐼 𝑗 = 𝐼 ∩ 𝐾 [𝑥 1 , . . . , 𝑥 𝑗 ] = ⟨𝑔 𝑖 : 𝑔 𝑖 ∈ 𝐾 [𝑥 1 , . . . , 𝑥 𝑗 ]⟩

Example: smooth del Pezzo surfaces

In [START_REF] Mitankin | Rational points on del Pezzo surfaces of degree four[END_REF], the authors study del Pezzo surfaces of degree 4 in P 4 with defining equations The work behind the final command is a Gröbner basis computation.

𝑥 0 𝑥 1 -𝑥 2 𝑥 3 = 𝑎 0 𝑥 2 0 + 𝑎 1 𝑥 2 1 + 𝑎 2 𝑥 2 2 + 𝑎 3 𝑥 2 3 + 𝑎 4 𝑥 2 4 = 0. We will substitute 𝑥 4 = 1 -𝑥 0 -𝑥 1 -𝑥 2 -

Remark 5

In a numerical setting, it is better to use border bases or more general bases to avoid amplifying rounding errors. Border bases use basis elements 𝑏 𝑖 for 𝐵 whose elements satisfy a connectedness property. See, for instance, [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF] for details. They do not depend on a monomial order. For a summary and comparison between Gröbner bases and border bases, see [START_REF] Telen | Solving Systems of Polynomial Equations[END_REF]Sections 3.3.1,3.3.2]. Nowadays, bases are selected adaptively by numerical linear algebra routines, such as QR decomposition with optimal column pivoting or singular value decomposition. This often yields a significant improvement in terms of accuracy. See, for instance, Section 7.2 in [START_REF] Telen | A stabilized normal form algorithm for generic systems of polynomial equations[END_REF].

Homotopy Continuation

The goal of this subsection is to briefly introduce the method of homotopy continuation for solving polynomial systems. For more details, we refer to the textbook [START_REF] Sommese | The Numerical solution of systems of polynomials arising in engineering and science[END_REF]. We set 𝐾 = C and 𝑛 = 𝑠. We think of 𝐹 = ( 𝑓 1 , . . . , 𝑓 𝑛 ) ∈ 𝑅 as an element of a family F of polynomial systems. The reader can replace F with any of the families seen in Section 3. A homotopy in F with target system 𝐹 ∈ F and start system 𝐺 ∈ F is a continuous deformation of the map 𝐺 = (𝑔 1 , . . . , 𝑔 𝑛 ) : C 𝑛 → C 𝑛 into 𝐹, in such a way that all systems obtained throughout the deformation are contained in F . For instance, When 𝐹 ∈ F (𝑑 1 , . . . , 𝑑 𝑛 ) as in Section 3.1 and 𝐺 is any other system in F (𝑑 1 , . . . , 𝑑 𝑛 ), a homotopy is 𝐻 (𝑥; 𝑡) = 𝑡 • 𝐹 (𝑥) + (1 -𝑡) • 𝐺 (𝑥), where 𝑡 runs from 0 to 1. Indeed, for any fixed 𝑡 * ∈ [0, 1], the degrees of the equations remain bounded by (𝑑 1 , . . . , 𝑑 𝑛 ), hence 𝐻 (𝑥; 𝑡 * ) ∈ F (𝑑 1 , . . . , 𝑑 𝑛 ).

The method of homotopy continuation for solving the target system 𝑓 1 = • • • = 𝑓 𝑛 = 0 assumes that a start system 𝑔 1 = • • • = 𝑔 𝑛 = 0 can easily be solved. The idea is that transforming 𝐺 continuously into 𝐹 via a homotopy 𝐻 (𝑥; 𝑡) in F transforms the solutions of 𝐺 continuously into those of 𝐹. Here is an example with 𝑛 = 1.

Example: 𝑛

= 𝑠 = 1, F = F (3)
Let 𝑓 = -6 + 11𝑥 -6𝑥 2 + 𝑥 3 = (𝑥 -1) (𝑥 -2) (𝑥 -3) be the Wilkinson polynomial of degree 3. We view 𝑓 = 0 as a member of F (3) and choose the start system 𝑔 = 𝑥 3 -1 = 0. The solutions of 𝑔 = 0, are the third roots of unity. The solutions of 𝐻 (𝑥; 𝑡) = 𝛾 • 𝑡 • 𝑓 (𝑥) + (1 -𝑡) • 𝑔(𝑥) travel from these roots to the integers 1, 2, 3 as 𝑡 moves from 0 to 1. This is illustrated in Fig. 5. The random complex constant 𝛾 is needed to avoid the discriminant, see below. This is known as the gamma trick.

More formally, if 𝐻 (𝑥; 𝑡) = (ℎ 1 (𝑥; 𝑡), . . . , ℎ 𝑛 (𝑥; 𝑡)) is a homotopy with 𝑡 ∈ [0, 1], the solutions describe continuous paths 𝑥(𝑡) satisfying 𝐻 (𝑥(𝑡); 𝑡) = 0. Taking the derivative with respect to 𝑡 gives the Davidenko differential equation

• > Predict and correct

Naively applying ODE methods for solving the Davidenko equation ( 18) is not the best we can do. Indeed, we have the extra information that the solution paths 𝑥(𝑡) satisfy the implicit equation 𝐻 (𝑥(𝑡), 𝑡) = 0. This is used to improve the accuracy of the ODE solver in each step. Given an approximation of 𝑥(𝑡 * ) at any fixed 𝑡 * ∈ [0, 1) and a step size 0 < Δ𝑡 ≪ 1, one approximates 𝑥(𝑡 * + Δ𝑡) by x using, for instance, Euler's method. This is called the predictor step. Then, one refines x to a satisfactory approximation of 𝑥(𝑡 * + Δ𝑡) by using x as a starting point for Newton iteration on 𝐻 (𝑥, 𝑡 * + Δ𝑡) = 0. This is the corrector step. The two-step process is illustrated in Fig. 5 (predict in orange, correct in green, solution paths 𝑥(𝑡) in blue). In the right part of the figure, the predict-correct procedure fails: because of a too-large step size Δ𝑡 in the predictor step, the Newton correction converges to a different path. This phenomenon is called path jumping, and to avoid it one must choose the stepsize Δ𝑡 adaptively. Recent work in this direction uses Padé approximants, see [START_REF] Telen | A robust numerical path tracking algorithm for polynomial homotopy continuation[END_REF][START_REF] Timme | Mixed precision path tracking for polynomial homotopy continuation[END_REF].

• > Avoid the discriminant Each of the families seen in Section 3 has a subvariety ∇ F ⊂ F consisting of systems with non-generic behavior in terms of their number of solutions. This subvariety is sometimes referred to as the discriminant of F , for reasons alluded to at the beginning of Section 3. When the homotopy 𝐻 (𝑥; 𝑡) crosses ∇ F , i.e. 𝐻 (𝑥; 𝑡 * ) ∈ ∇ F for some 𝑡 * ∈ [0, 1), two or more solution paths collide at 𝑡 * , or some solution paths diverge. This is not allowed for the numerical solution of [START_REF] Desjardins | Density of rational points on a family of del Pezzo surfaces of degree one[END_REF]. Fortunately, crossing ∇ F can be avoided. The discriminant ∇ F has complex codimension at least one, hence real codimension at least two. Since the homotopy 𝑡 ↦ → 𝐻 (𝑥; 𝑡) describes a one-realdimensional path in F , it is always possible to go around the discriminant. See for instance [START_REF] Sommese | The Numerical solution of systems of polynomials arising in engineering and science[END_REF]Section 7]. When the target system 𝐹 belongs to the discriminant, end games are used to deal with colliding/diverging paths at 𝑡 = 1 [START_REF] Sommese | The Numerical solution of systems of polynomials arising in engineering and science[END_REF]Section 10]. This story implies that the number of paths tracked in a homotopy algorithm is the generic number of solutions of the family F . In that sense, results like Theorems 1, 2 and 3 characterize the complexity of homotopy continuation in the respective families.

• > Start systems in practice

There are recipes for start systems in the families F from Section 3. For instance, we use 𝐺 = (𝑥 𝑑 1 1 -1, . . . , 𝑥 𝑑 𝑛 𝑛 -1) for F (𝑑 1 , . . . , 𝑑 𝑛 ). The 𝑑 1 • • • 𝑑 𝑛 solutions can easily be written down. Note that 𝐺 ∉ ∇ 𝑑 1 ,...,𝑑 𝑛 . For the families F (A) and F (A 1 , . . . , A 𝑛 ), an algorithm to solve start systems was developed in [START_REF] Huber | A polyhedral method for solving sparse polynomial systems[END_REF]. For solving start systems of other families, one may use monodromy loops [START_REF] Duff | Solving polynomial systems via homotopy continuation and monodromy[END_REF].

Case study: 27 lines on the Clebsch surface

A classical result from intersection theory states that every smooth cubic surface in complex three-space contains exactly 27 lines. In this final section, we use Gröbner bases and homotopy continuation to compute lines on the Clebsch surface defined by [START_REF] Breiding | An algebraic geometry perspective on topological data analysis[END_REF]. This particular surface is famous for the fact that all its 27 lines are real. Let 𝑓 (𝑥, 𝑦, 𝑧) be as in [START_REF] Breiding | An algebraic geometry perspective on topological data analysis[END_REF]. A line in R 3 parameterized by (𝑎

1 +𝑡 • 𝑏 1 , 𝑎 2 +𝑡 • 𝑏 2 , 𝑎 3 +𝑡 • 𝑏 3 ) is contained in our Clebsch surface if and only if 𝑓 (𝑎 1 + 𝑡 • 𝑏 1 , 𝑎 2 + 𝑡 • 𝑏 2 , 𝑎 3 + 𝑡 • 𝑏 3 ) ≡ 0.
) 19
We further reduce this to a system of 𝑠 = 4 equations in 𝑛 = 4 unknowns by removing the redundancy in our parameterization of the line: the space of lines in three-space (i.e. the Grassmannian G(1, 3)) has dimension four, not six. We may impose a random affine-linear relation among the 𝑎 𝑖 and 𝑏 𝑖 . We choose to substitute Implementations of Gröbner bases are available, for instance, in Maple [START_REF] Maplesoft | [END_REF] and in msolve [START_REF] Berthomieu | msolve: A library for solving polynomial systems[END_REF], which can be used in julia via the package msolve.jl. This is also available in the package Oscar.jl [START_REF]Oscar -open source computer algebra research system[END_REF]. The following snippet of Maple code constructs our system [START_REF] Dickenstein | Biochemical reaction networks: An invitation for algebraic geometers[END_REF] and computes a Gröbner basis with respect to the graded lexicographic monomial ordering with 𝑎 1 ≻ 𝑎 2 ≻ 𝑏 1 ≻ 𝑏 2 . This basis consists of 23 polynomials 𝑔 1 , . . . , 𝑔 23 . The set of standard monomials is the first output of the command NormalSet. It consists of 27 elements, and the multiplication matrix with respect to 𝑎 1 in this basis is constructed using MultiplicationMatrix:

> ns, rv := NormalSet(GB, grlex(a [START_REF] Baldi | Computing real radicals by moment optimization[END_REF], a [START_REF] Bates | Numerically solving polynomial systems with Bertini[END_REF], b [START_REF] Baldi | Computing real radicals by moment optimization[END_REF], b [START_REF] Bates | Numerically solving polynomial systems with Bertini[END_REF])): > nops(ns); ----> output: 27 > Ma1 := MultiplicationMatrix(a [START_REF] Baldi | Computing real radicals by moment optimization[END_REF], ns, rv, GB, grlex(a [START_REF] Baldi | Computing real radicals by moment optimization[END_REF], a [START_REF] Bates | Numerically solving polynomial systems with Bertini[END_REF], b [START_REF] Baldi | Computing real radicals by moment optimization[END_REF], b [START_REF] Bates | Numerically solving polynomial systems with Bertini[END_REF])):

This is a matrix of size 27 × 27 whose eigenvectors reveal the solutions (Theorem 4). We now turn to julia and use msolve to compute the 27 lines on { 𝑓 = 0} as follows: We have drawn three of these lines on the Clebsch surface in Fig. 6 as an illustration. Other software systems supporting Gröbner bases are Macaulay2 [START_REF] Grayson | Macaulay2, a software system for research in algebraic geometry[END_REF], Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF], Mathematica [?] and Singular [START_REF] Greuel | Singular-a computer algebra system for polynomial computations[END_REF].

Homotopy continuation methods provide an alternative way to compute our 27 lines. Here we use the julia package HomotopyContinuation.jl [START_REF] Breiding | HomotopyContinuation.jl: A package for homotopy continuation in Julia[END_REF]. The output is shown in Fig. 7. There are 27 solutions, as expected. The last line indicates that a :polyhedral start system was used. In our terminology, this means that the system was solved using a homotopy in the family F (A 1 , . . . , A 4 ) from Section 3.3. The number of tracked paths is 45, which is the mixed volume MV(A 1 , . . . , A 4 ) of this family. The discrepancy 27 < 45 means that our system 𝐹 lies in the discriminant ∇ A 1 ,..., A 4 . The 18 'missing' solutions are explained in [START_REF] Bender | Toric eigenvalue methods for solving sparse polynomial systems[END_REF]Section 3.3]. The output also tells us that all solutions have multiplicity one (this is the meaning of non-singular) and all of them are real. Other software implementing homotopy continuation are Bertini [START_REF] Bates | Numerically solving polynomial systems with Bertini[END_REF] and PHCpack [START_REF] Verschelde | Algorithm 795: Phcpack: A general-purpose solver for polynomial systems by homotopy continuation[END_REF]. Numerical normal form methods are used in EigenvalueSolver.jl [START_REF] Bender | Yet another eigenvalue algorithm for solving polynomial systems[END_REF].

  (a) Curves defined by 𝑓 , 𝑔 from (8).(b) The Clebsch surface.

Fig. 1 :

 1 Fig. 1: Algebraic curves in the plane (𝑛 = 2) and an algebraic surface (𝑛 = 3).

  and replace 𝐾 by 𝐾 in this notation to mean only the solutions over the ground field. Examples of affine varieties are the red curve 𝑉 𝐾 ( 𝑓 ) and the set of black dots 𝑉 𝐾 ( 𝑓 , 𝑔) in Fig. 1a. In the case of 𝑉 𝐾 ( 𝑓 ), Fig. 1a only shows the real part 𝑉 𝐾 ( 𝑓 ) ∩ R 2 .

Fig. 2 :

 2 Fig. 2: The two configurations of a robot arm are the intersection points of two circles.

Fig. 3 :Remark 2

 32 Fig.3: The polytope Conv(A) in this example is a hexagon.

[ 16 ,

 16 Chapter 4], a polynomial 𝑓 ∈ 𝑅 belongs to 𝐼 if and only if 𝑓 (𝑧 𝑖 ) = 0, 𝑖 = 1, . . . , 𝛿. In other words, the map ev is injective. It is also surjective: there exist Lagrange polynomialsℓ 𝑖 ∈ 𝑅 satisfying ℓ 𝑖 (𝑧 𝑗 ) = 1 if 𝑖 = 𝑗 and ℓ 𝑖 (𝑧 𝑗 ) = 0 for 𝑖 ≠ 𝑗 [49, Lemma 3.1.2]. We conclude that 𝑅/𝐼 ev ≃ 𝐾 𝛿 .The following statement makes our claim that the zeros 𝑧 1 , . . . , 𝑧 𝛿 are encoded in the eigenstructure of 𝑀 𝑔 concrete.

  be the ideal generated by the univariate polynomial 𝑓 ∈ 𝐾 [𝑥]. For general 𝑎 𝑖 , there are 𝛿 = 𝑑 roots with multiplicity one, hence 𝐼 is radical. The dimension dim 𝐾 𝐾 [𝑥]/𝐼 equals 𝑑, and a canonical choice of basis is {[1], [𝑥], . . . , [𝑥 𝑑-1 ]}. Let us construct the matrix 𝑀 𝑥 in this basis. That is, we set 𝑔 = 𝑥. We compute the normal forms N (𝑥 • 𝑥 𝑖-1 ): N (𝑥 𝑖 ) = 𝑥 𝑖 , 𝑖 = 1, . . . , 𝑑 -1 and N (𝑥 𝑑 ) = -𝑎 -1 𝑑 (𝑎 0 + 𝑎 1 𝑥 + • • • + 𝑎 𝑑-1 𝑥 𝑑-1 ).

  is generated by those elements of our Gröbner basis which involve only the first 𝑗 variables, see [16, Chapter 3, §1, Theorem 2]. In our case, a consequence is that one of the 𝑔 𝑖 is univariate in 𝑥 1 , and its roots are the 𝑥 1 -coordinates of 𝑧 1 , . . . , 𝑧 𝛿 . The geometric counterpart of computing the 𝑗-th elimination ideal is projection onto a 𝑗-dimensional coordinate space: the variety 𝑉 𝐾 (𝐼 𝑗 ) ⊂ 𝐾 𝑗 is obtained from 𝑉 𝐾 (𝐼) ⊂ 𝐾 𝑛 by forgetting the final 𝑛 -𝑗 coordinates (𝑥 1 , . . . , 𝑥 𝑛 ) ↦ → (𝑥 1 , . . . , 𝑥 𝑗 ) and taking the closure of the image. Here are two examples. Example: the projection of a space curve To the right we show a blue curve in R 3 defined by an ideal 𝐼 ⊂ R[𝑥, 𝑦, 𝑧]. Its Gröbner basis with respect to the lex ordering 𝑥 ≺ 𝑦 ≺ 𝑧 contains 𝑔 1 ∈ R[𝑥, 𝑦], which generates 𝐼 2 . The variety 𝑉 R (𝐼 2 ) = 𝑉 R (𝑔 1 ) ⊂ R 2 is the orange curve in the picture.

3 ∑𝑖=0𝑎 𝑖 𝑥 2 𝑖 + 𝑎 4 1 - 3 ∑ 𝑖=0 𝑥 𝑖 2 =

 3232 𝑥 3 to reduce to the affine case. It is claimed that the smooth del Pezzo surfaces of this form are those for which the parameters 𝑎 0 , . . . , 𝑎 4 lie outside the hypersurface 𝐻 = {𝑎 0 𝑎 1 𝑎 2 𝑎 3 𝑎 4 (𝑎 0 𝑎 1 -𝑎 2 𝑎 3 ) = 0}. This hypersurface is the projection of the variety(𝑎, 𝑥) ∈ Q 5 × Q 4 : 𝑥 0 𝑥 1 -𝑥 2 𝑥 3 = 0 and rank(𝐽) < 2 onto Q 5 .Here 𝐽 is the 2 × 4 Jacobian matrix of our two equations with respect to the four variables 𝑥 0 , 𝑥 1 , 𝑥 2 , 𝑥 3 . The defining equation of 𝐻 is computed in Macaulay2 [25] as follows: R = QQ[x_0..x_3,a_0..a_4] x_4 = 1-x_0-x_1-x_2-x_3 I = ideal( x_0*x_1-x_2*x_3 , a_0*x_0^2 + a_1*x_1^2 + ... + a_4*x_4^2 ) M = submatrix( transpose jacobian I , 0..3 ) radical eliminate( I+minors(2,M) , {x_0,x_1,x_2,x_3} )

Fig. 5 :

 5 Fig. 5: The third roots of unity travel to 1, 2, 3 along continuous paths.

  The left-hand side evaluates to a cubic polynomial in 𝑡 with coefficients in the ringZ[𝑎 1 , 𝑎 2 , 𝑎 3 , 𝑏 1 , 𝑏 2 , 𝑏 3 ] = Z[𝑎, 𝑏]: 𝑓 ( 𝑎 1 +𝑡 • 𝑏 1 , 𝑎 2 +𝑡 • 𝑏 2 , 𝑎 3 +𝑡 • 𝑏 3 ) = 𝑓 1 (𝑎, 𝑏) •𝑡 3 + 𝑓 2 (𝑎, 𝑏) •𝑡 2 + 𝑓 3 (𝑎, 𝑏) •𝑡 + 𝑓 4 (𝑎, 𝑏).The lines contained in the Clebsch surface satisfy 𝑓 1 (𝑎, 𝑏) = 𝑓 2 (𝑎, 𝑏) = 𝑓 3 (𝑎, 𝑏) = 𝑓 4 (𝑎, 𝑏) = 0.(

𝑎 3 =

 3 -(7 + 𝑎 1 + 3𝑎 2 )/5, 𝑏 3 = -(11 + 3𝑏 1 + 5𝑏 2 )/7.

  > f := 81*(x^3 + y^3 + z^3) -189*(x^2*y + x^2*z + x*y^2 + x*z^2 + y^2*z + y*z^2) + 54*x*y*z + 126*(x*y + x*z + y*z) -9*(x^2 + y^2 + z^2) -9*(x + y + z) + 1: > f := expand(subs({x = t*b[1] + a[1], y = t*b[2] + a[2], z = t*b[3] + a[3]}, f)): > f := subs({a[3] = -(7 + a[1] + 3*a[2])/5, b[3] = -(11 + 3*b[1] + 5*b[2])/7}, f): > ff := coeffs(f, t): > with(Groebner): > GB := Basis({ff}, grlex(a[1], a[2], b[1], b[2])); > nops(GB); ----> output: 23

  a1,a2,b1,b2) = PolynomialRing(QQ,["a1","a2","b1","b2"]) I = ideal(R, [-189*b2*b1^2 -189*b2^2*b1 + 27*(11 + 3*b1 + 5*b2)*b1^2 + ... A, B = msolve(I) The output B contains 4 rational coordinates (𝑎 1 , 𝑎 2 , 𝑏 1 , 𝑏 2 ) of 27 lines which approximate the solutions. To see them in floating point format, use for instance [convert.(Float64,convert.(Rational{BigInt},b)) for b in B]

Fig. 6 :

 6 Fig. 6: Two views on the Clebsch surface with three of its 27 lines.

Fig. 7 :

 7 Fig. 7: The julia output when computing 27 lines on the Clebsch surface.


Positioning of Imbalu Circumcision Ritual Dances among the Bagisu ethnic tribe

Keywords: Imbalu circumcision, ritual dances, ritual process

Circumcision as a cultural practice is a rite of passage with a nuanced symbolic and associated public status. An event, lasting days, weeks or even months, the performative elements involved are a reflection of political, cultural and social positions among the Bagisu ethnic tribe of eastern Uganda. The entire event is divided into three sections, each with a special dance; 1, Isonja, 2, Mwaga/Kadodi and, 3 Inemba dances.

In this article, however, the focus is on Isonja and Inemba dances in a ritual setting and their relation to a broader community context. The article further sheds light on the notions of dance, music, and dancemusicking elements rooted in the ritual while theorizing the Imbalu circumcision process according to Arnold Van Gennep and Victor Turner's triple concepts of separation, transition, and incorporation.

I define the notion of ritual, as understood by Emile [START_REF] Durkheim | The elementary forms of the religious life[END_REF], as a social process that binds the individual to society through symbolic acts [of the candidates in relation to their culture]. The community in question is that of the Bagisu or Bamasaba, who are a Bantu people living on the slopes of Mount Elgon in Eastern Uganda. They speak Lugisu, also known as Lumasaba, a language among the Bantu family languages.

Ethnically, among the Bagisu, circumcision is an initiation ritual and is considered the only way to turn a boy into a man. It is a communal ritual of a rite of passage for manhood that occurs only in the even years of the calendar. Circumcision is intended for every young man over the age of sixteen in an elaborate ritual known as Imbalu. Makwa expounds on the involvement of other performative arts when he asserts that, this ritual denotes 'not only the cutting of the foreskin of the penis but also other rituals involving music and dance' (2010:2). The discussions and arguments contained herein, are drawn in part from 1) my two decades of practical experience as a Ugandan folk dancer, teacher, and choreographer in and outside of Uganda and 2), from literary sources of mainly Ugandan scholars who have conducted extensive ethnographic research on Imbalu circumcision rituals focusing on issues such as gender, identity, dancing and dance-musicking among the Bagisu, see [START_REF] Makwa | Role of Music and Dance Among the Bagisu of Eastern Uganda[END_REF][START_REF]Musicking and Dancing Imbalu Circumcision Rituals (Khushina Imbalu): Performing Gender Among the Bagisu of Eastern Uganda[END_REF], 2016[START_REF] Khamalwa Wotsuna | The Power of Culture and Identity: Imbalu Initiation Ritual Among the Bamasaaba of Uganda[END_REF][START_REF] Durkheim | The elementary forms of the religious life[END_REF][START_REF] Kitaka | Secularisation of Mwaga/Kadodi; 'A Circumcision Dance and Music of the Bagisu of eastern Uganda: A Comparison of the Performance Within and outside the Ritual Context[END_REF][START_REF] Khanakwa | Reinventing Imbalu and Forcible Circumcision: Gisu Political Identity and The Fight for Mbale in Late Colonial Uganda[END_REF].

To contextualize the dance and music of Imbalu circumcision rituals, one must examine the phenomena within the rituals combined with music and dance, as observed by Royce in Nahachewsky's claim that one of the strategies that facilitate better, cross-cultural discussions about dance is 'contemplation to open beyond the movement patterns themselves and to include the entire dance event ' (2012:11). This notion is further developed by John Kaemmer when he explicitly posits that 'music [dance] and ritual are so closely intertwined that, it is difficult to determine with certainty which influences the other ' (1993:69). Therefore, 'due to the integrative nature of music and dance and other cultural elements in Imbalu, the Bagisu refer to the entire Imbalu event as dancing circumcision, locally translated as Khushina Imbalu' (Makwa 2009:33). The music and dances performed in each phase of the Imbalu convey the broad and subtle meanings behind the performance of these rituals, aimed at creating a society of brave men. One of the aspects that highlight the composition of the Bagisu ancestors is the structure of the Imbalu circumcision rituals. The entire season is divided into three consecutive sections marked by different performative specificity. These include 'preparing and examining the candidate', 'performing the Imbalu circumcision', and 'welcome the men'. The first stage of preparation in the ritual cycle begins in January and lasts until July of an even year, the year of the Imbalu circumcision. The rituals, music, and dances performed in this phase are intended to let the prospective Imbalu candidates, their parents and relatives know that the year of Imbalu rituals has begun. The dance performed at this stage is called Isonja. The second and third sections run from August to December and the dances and music performed are Mwaga and Inemba respectively [START_REF] Kitaka | Secularisation of Mwaga/Kadodi; 'A Circumcision Dance and Music of the Bagisu of eastern Uganda: A Comparison of the Performance Within and outside the Ritual Context[END_REF]. For this paper, I will focus my discussion on the first section containing the Isonja dance and give an in-depth description and analysis of the last section involving the Inemba dance.

Phase one, Isonja Dance: Preparing and testing the candidate

This is one of the introductory dances performed during the process of Imbalu circumcision rituals. All ritual candidates of the community usually gather in one place, an open area, and normally begin the practices each evening under the direction of special Isonja teachers, traditionally known as Banamyenya. The candidates are introduced to singing and dancing skills as 'a candidate needs to sing and dance during the Imbalu circumcision ritual' (Makwa 2008:85), to demonstrate courage and determination to be circumcised. However, while learning and performing the Isonja dance, the role of leading songs rests with the leaders or coaches, traditionally known as Namyenya singular or Banamyenya plural, while the candidates are only expected to respond to the songs for motivation while dancing. Furthermore, during the training, candidates are introduced to ethnogenetic information about their culture, including the ancestral history, norms and customs of Bagisu ideologies, to embolden the 'real men' within them, first through words and later through deeds. Makwa adds that 'the trainers (Banamyenya) keep reminding the candidates that their mission is to initiate them into men, emphasizing the fact that a real Mugisu man should be energetic and aggressive enough to defend himself, his family and the kingdom against any outside attacks' (2008:87). The songs that accompany the Isonja dance convey powerful messages to test the candidates' resolve and determination to prove if they are ready to be accepted and welcomed back into the community as real men. In addition, the dance aims to test the candidates' maturity and masculinity for them to qualify for that year's Imbalu circumcision rituals. Depending on their dancing ability, the young and weak may be disqualified, as suggested by watching community members or advised by clan members to wait for the next season when they mature and get stronger (Makwa 2008:90). The candidates adorn the Imbalu paraphernalia, which consists of props such as ankle, leg, and thigh bells, headgear made from colobus monkey skin, and cowrie shells. Meanwhile, the dancers also carry tree branches, sticks and clubs to demonstrate their fearlessness and give a strong impression to the terrified onlookers.

Phase Three, Inemba Dance: Welcome the men

Inemba is both a ritual and a dance performed to mark the culmination of the Imbalu circumcision ritual. The newly circumcised boys (initiates) of kindred lines gather to be commissioned as men in this dance. They make their way from their houses to gathering spots, where they collectively rush to the community performance venue. Here, they sing songs depicting themselves as triumphant men in the community, which songs are responded to by people accompanying them. They dance from eastern to western villages as they approach the performance venue from a mountaintop. Since it also a celebration, the Inemba dance is done in an open arena large enough for initiates from different lineages to dance together. Additionally, the dance is performed during the dry season when people have not been growing their crops to minimise the destruction that might occur when the ritual commences. In some districts and counties in Eastern Uganda, when the dry spell begins in February, Inemba is performed for three days to provide initiates adequate time to interact with their peers and share their Imbalu circumcision rite experiences. According to Khamalwa, newly initiated person should participate in the [Inemba] dance at least once. If someone cannot attend in person [,] a proxy is paid to attend on their behalf ' (2004:103). It is therefore obligatory for all initiates and their family members to attend and participate in Inemba rituals.

Preparations for Inemba dance performances begin at noon. The relatives of the initiate gather at his father's house to drink local beer which has been prepared to welcome the initiate back to the community. Makwa elucidates that, 'at around 4:00 O'clock in the evening, the initiate performs the ritual of being clothed into the new robe ' (2010:138). He further adds that 'an elder who is kind, affluent, and has produced male children, is chosen to put the animal skin (isumbati) on the initiate. The elder re-echoes the admonitions that the circumciser issued during purification as he hands the initiate the skin,' (Makwa 2010:139). Then he drapes a long garland of (libombwe), a fast-growing creeper thought to bring good luck, around the initiate's neck as he is given more gift by other elders to welcome him back into society. Meanwhile, others of the community are forming a ring around the initiates to follow suit and deliver their presents. Anyone with a gift places libombwe around the initiate's neck and hands him the gift. In fact, the more creepers (kamabombwe-plural) he wears around his neck while performing Inemba dance, the more gifts the initiate is said to have received from relatives and friends.

When the reminding drum sounds in the evening, the initiates rush to the gathering sites to meet their peers from other clans and move together to the Inemba performance venue. However, a few meters before reaching this venue, initiates perform the ritual of 'tightening their skins' khubwaa tsingubo-tsisumbati (Khamalwa 2004).

Elders from several clans gather their initiates and instruct them to kneel in two parallel lines, facing one another.

Each initiate unties his skin, folds it, and tosses it to the person kneeling across him. In the process of exchanging these skins, the elders enlighten the initiates on the importance of unity for men in society.The tightening of the initiates' skins takes place at around 4:30 in the evening and afterwards, initiates run to the Inemba performance venue reaching there from the eastern direction. 'It is believed that the Bagisu normal life moves in a clockwise direction just as the sun rises from the east and sets in the west' (Makwa, 2010). In his ethnographic article Identity, Power and Culture, Khamalwa revealed, 'that moving in an anti-clockwise direction is associated with bad luck, therefore, the Bagisu avert bad luck when they are out for a journey by spitting to the right to evoke ancestors for their protection ' (2004:91).

Inemba Dance Description

Inemba, like the Isonja dance, is celebrated in an open community area. The drums are hoisted up on two poles to allow the sound to travel further, and the dancers, who make up most of the congregation, move around the drums. The main motif of the Inemba dance is in a demi-plie position, demonstrated by putting the feet apart and somehow bending backwards. After that, the performer swings his body from right to left while moving his hands in the same direction. The performers then bend and pass the skins between their legs, providing another dance pattern. The skin is lifted to the left, then to the right shoulder and thrown between the legs. The female performers, who come mainly to accompany the initiates, dance while raising their legs. In addition, when the females spread their arms, they bend slightly to the left, and then to the right. Usually, their torsos are lifted forward when they show their breasts. All the Inemba dance motifs discussed above relate to the theme of sexuality as it underpins society's inclusivity in both ritual and dance. In addition, initiates raise their legs to indicate to the girls that they are healed and can therefore engage in sexual activities with them. While dancing Isonja, when initiates see less attractive girls, they push their skins to the left and right of their bodies to symbolize that they are not interested in such ladies. On the contrary, the female dancers indicate to the initiates by raising their legs that they are ready to be married as wives. Unlike Isonja, the Inemba dance is a stage to affirm masculinity before the community which is exhibited through leading songs while dancing. Now that they are men, society views the initiates as strong and tough individuals capable of sharing men's space. The initiates sing triumphant songs as they dance, mocking their colleagues who feared, cried, and fell during circumcision. They sing and dance for joy to demonstrate to the community that they are victorious men ready to fulfil men's obligations. Women exclusively respond to the initiates' songs and often dance to show the initiates that they are ready to be married. Inemba dance forms a path by which young girls and initiates can attract future spouses.

Inemba dance video at Mutoto grounds in Mbale district

Recorded by Dennis Machio

Theorising Imbalu Circumcision Ritual Process I contextualize the process of Imbalu rituals to the threefold classification of separation, transition and incorporation of rituals by Arnold [START_REF] Van Gennep | The Rites of Passage[END_REF][START_REF] Turner | The Ritual Process: Structure and Anti-Structure[END_REF], while highlighting the nature of dancing in Imbalu rituals. Makwa discusses how dancing transforms a 'boy right from the time he separates himself as a candidate, through the time of circumcision and healing the penis wound until he is re-integrated into the community ' (2010:131). When the confirmed candidates have been selected by their families or clans, they undergo rigorous training to become fully equipped and prepared for the tough circumcision ceremony ahead. There are high expectations from their families and clan members to fully get equipped with the knowledge and determination required of 'real men' hence the need to be isolated from all external influences that may affect their behaviour in the proper conduct during these preparatory stages. Victor Turner classified rituals such as circumcision as 'life-crisis rituals whose aim is to elevate the status of the involved individuals, families and communities' (1969:169); thereby cementing and solidifying their social and political status within peers and the entire community. Nevertheless, consolidating such a status takes a long process and requires a prepared mind. The separation from the community and the family only happens when candidates meet the trainers locally known as Banamyenya to embark on a completely new, unfamiliar and stressful journey.

Moreover, the different stages the ritual 'undergoes can fit into Van Gennep's scheme of separation, transition/seclusion, and social re-integration that he uses to describe the process through which rites of passage undergo' [START_REF] Van Gennep | The Rites of Passage[END_REF].

While discussing the stages through which ritual subjects undergo, Van Gennep argues that one is first separated by and from the community before being initiated, secluded, and finally re-integrated into society. [START_REF] Turner | The Ritual Process: Structure and Anti-Structure[END_REF] builds on Van Gennep's notion and provides details about the liminal stage of rites of passage. Like Van Gennep, Turner posits that people intending to engage in rites of passage are first separated from the wider community before being initiated. After that, they are sequestered and subjected to a transformation process through seclusion rituals. Rites like Imbalu bring multiple initiates together under one roof to undergo healing, and this creates a bond that Turner refers to as communitas. Once the process of separation is complete, initiates are reintegrated into society to take on new roles expected of them as men.

According to Van Gennep, the first phase is separation, characterized by purification rites, innuendo, loss of old identity, bathing, shaving, changing clothes and markings and removal from the main social group (1960:72).

Before the Imbalu candidate joins the others in Isonja ritual, he is smeared with white corn flour or yeast. On the second day, the candidate undertakes the khubeka litsune ceremony, which entails shaving off all his hair. This rite is carried out by a paternal aunt who has been chosen for her good behaviour, kindness, and ability to produce offspring, particularly boys. The aunt invokes ancestral spirits to appear and bless the candidate while shaving his hair. According to Makwa, the Bagisu believe that the paternal aunt is more or less the father in Bugisu (2010:112). As such, the paternal aunt is given the title of female-father (papa mukhasi) and freely calls the mother of her nephews or nieces 'my wife'. After all, the cows she brought home as a bride price are the ones her brother used for his wife's bride price. Additionally, the candidates are taken away from their immediate family members and put in a place where they do not see friends; they usually socialize and meet entirely new faces. They are taught how to behave and act after circumcision and are expected to abandon their old ways and lose their old identity to embrace a whole new identity and role.

During the second phase, the transition, or the 'liminal period, the characteristics of the ritual subject are ambiguous; they traverse a cultural domain that has few or no attributes of the past or future state' (Turner 1969:94). Although a well-known phenomenon, the operation (circumcision) itself is a new experience for the candidate, proceeded by other rituals such as khucheenda tsinzila (walking the paths) and mukombe (seclusion). This eventually adds up to what Victor Turner calls the 'liminal stage-simplification and elimination of a social structure [ imbalu ritual]' (1969:167). Walking the paths takes place three days after the circumcision and is a ceremony where an elder shows the initiates around the village to re-orient them into daily life. Khamalwa posits 'that at this stage the initiate is shown the paths that he should use as well as those he must avoid whenever he is able to leave the solitude room ' (2018:23). During these excursions, Makwa adds that 'initiates sing songs depicting them as brave men who faced the knife' (Makwa 2021). Through such songs, they also make fun of those who either were not circumcised or cried during the operation. After this ritual, the boys are returned to their seclusion rooms (some may remain there as individuals while others live as a group) to continue the healing process. Seclusion puts boys in an indeterminate state where they reflect on how far they have come to project their post circumcision lives; this usually happens during the healing process of the penis. [START_REF] Van Gennep | The Rites of Passage[END_REF] concept sheds light on transition as another phase marked by the suspension from normal routines and conventions. For this phase, I will associate it with the circumcision process, in which the candidates are limboed in a 'betwixt and between the positions assigned and arrayed by the customs and the ceremony' (Turner 1969:95), which I have characterised as a 'moment of no return'. At this stage, there are strict rules that must be followed.

When candidates for training are separated from their families, they are expected to abide by the rules of a new environment, such as meeting at a specific time and place. This aims to cleanse and purify them from their old ways and embrace new ones as instructed by Banamyenya. First, the Imbalu candidates undergo a 'metaphorical death' during which they are separated from a previous state of being and, break with previous practices and routines. They then find themselves between two different planes of existence, in which their own identity is partially dissolved and the assumption of a new one is imminent. Here candidates spend time with the initiator and learn new things repeatedly for three consecutive days until it becomes a routine and a permanent way of doing things.

The final phase of incorporation can be inferred to be the operational rite among Australians as Van Gennep argues, in which 'an individual is welcomed back into society, but now with a new status and identity ' (1960:39).

According to Imbalu, the post-circumcision celebration begins with a celebratory dance -Inemba, which is also known as the welcome dance for families, clan members and the wider community. The freshmen are dressed in new skins and wear garlands of creepers around their necks. At the opening of the Inemba ceremony, the newly circumcised are inaugurated for the last and most important time, but related clans almost follow the original traditional paths trodden on the day of the circumcision. Shouting, cheering and beer blowing are performed as before. Inemba dancers (initiates) hold specially prepared long branches and dance around the drum area. At the end of each rhythm, dancers point in Mutoto 1 direction in salutation.

Summary

In the article, I discussed dance in a ritual context and demonstrated how circumcision rituals among the Bagisu people of eastern Uganda are a community event whose values transcend dancing to emboldening social aesthetics and cultural knowledge. It is a significant rite of passage of turning boys into men with maximum respect to their tribal leaders. The elders' cultural positions and roles in identifying the embedded knowledge and responsibilities in the activities of the Imbalu rituals are critical to the preservation of their traditions. Furthermore, theorising the circumcision ritual process in light of Van Gennep and Victor Turner's ritual concepts in retrospect elucidates the interconnectedness of ritual, performance and community among the Bagisu. It is therefore worth noting that the circumcision rituals for the Gisu, although spread over a longer period (months), are viewed as an event involving various activities, including dancing and musicking, among others, and aimed at the social well-being of a community.

1 Mutoto is a place where Imbalu circumcision is believed to have started.