# On the Number of Real Types of Univariate Polynomials

Nicolas Faroß, Thomas Sturm

► To cite this version:

Nicolas Faroß, Thomas Sturm. On the Number of Real Types of Univariate Polynomials. ISSAC 2025 - 50th International Symposium on Symbolic and Algebraic Computation, ACM, Jul 2025, Guanajuato, Mexico. pp.62-69, 10.1145/3747199.3747547. hal-05406461

HAL Id: hal-05406461

https://hal.science/hal-05406461v1

Submitted on 13 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# On the Number of Real Types of Univariate Polynomials

Nicolas Faroß

Saarland University
Saarbrücken, Germany
faross@math.uni-sb.de

## Abstract

The real type of a finite family of univariate polynomials characterizes the combined sign behavior of the polynomials over the real line. We derive explicit formulas for numbers of real types subject to various degree bounds. For the special case of a single polynomial we present a closed-form expression involving Fibonacci numbers. This allows us to precisely describe the asymptotic growth of the number of real types as the degree increases, in terms of the golden ratio.

## Keywords

polynomial roots, real algebra, real type

## ACM Reference Format:

Nicolas Faroß and Thomas Sturm. 2025. On the Number of Real Types of Univariate Polynomials. In *International Symposium on Symbolic and Algebraic Computation (ISSAC '25), July 28–August 01, 2025, Guanajuato, Mexico*. ACM, New York, NY, USA, 8 pages. https://doi.org/10.1145/3747199.3747547

## 1 Introduction

We consider univariate polynomials with real coefficients. The real type of such a polynomial is the finite sequence of its signs listed from $-\infty$ to $\infty$. For instance, the polynomial $f = x^4 - 4x^2$ plotted in Figure 1 has real roots at $-2, 0, 2$. Evaluation of the signs of $f$ at and between those real roots yields its real type

$$ [1, 0, -1, 0, -1, 0, 1]. \qquad (1) $$

The notion of a real type generalizes to finite families $f_1, \dots, f_n$ of polynomials by considering their combined signs as column vectors of length $n$. For instance, all real roots of the polynomials of the family $f_1 = x + 1, f_2 = 2x + 1, f_3 = x^2 - 1$ plotted in Figure 1 are located at $-1, -\frac{1}{2}, 1$. Evaluation of the signs of $[f_1, f_2, f_3]^T$ at and between those points yields the real type

$$ \begin{bmatrix} -1 & 0 & 1 & 1 & 1 & 1 & 1 \\ -1 & -1 & -1 & 0 & 1 & 1 & 1 \\ 1 & 0 & -1 & -1 & -1 & 0 & 1 \end{bmatrix}. \qquad (2) $$

In this paper, we are interested in the number of possible real types of families of $n$ polynomials subject to a degree bound $d$. Note that Eq. (1) is not a possible real type of a polynomial of degree 3, although it contains only three zeros. Košta [8, pp.11–13] has

<figure><img src="image_2.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License. *ISSAC '25, Guanajuato, Mexico*

© 2025 Copyright held by the owner/authors(s).

ACM ISBN 979-8-4007-2075-8/25/07

https://doi.org/10.1145/3747199.3747547

Thomas Sturm*

CNRS, Inria, and the University of Lorraine
Nancy, France
thomas.sturm@cnrs.fr

<figure><img src="image_3.png" /><figcaption>**Figure 1:** The polynomial $f = x^4 - 4x^2$ and the family $f_1 = x + 1, f_2 = 2x + 1, f_3 = x^2 - 1$ of polynomials discussed in the Introduction</figcaption></figure>

shown that the number of possible real types of a single polynomial of degree $d$ is exactly

$$ R_d = \sum_{m=0}^{d} R_d^{(m)} \quad \text{with} \quad R_d^{(m)} = 2 \cdot \sum_{j \ge 0} \binom{m}{2m-j+2} \qquad (3) $$

and considered it unlikely that Eq. (3) could be expressed in a closed form, pointing at an existing result by Petkovšek et al. [12] that a sum of the form $\sum_{j \ge l} \binom{m}{j}$ cannot be expressed in closed form as a function of $m$ and $l$, unless one resorts to hypergeometric functions. We are not aware of any results on the number of possible real types of families $f_1, \dots, f_n$ of polynomials for $n > 1$.

Let us make precise the notion of a closed form for our purposes here. A *closed form* represents a function using a term in arithmetic symbols and elementary functions. Let $F_n$ denote the $n$-th Fibonacci number. Then we allow ourselves to say that $2F_n - 1$ is in closed form, because there exists a closed form for $F_n$ via Binet's formula. An *explicit form* additionally admits finite sums and products with parametric upper bounds, but not recursion.

Real types play a key role in a number of decision and quantifier elimination procedures for real closed fields. Quantifier elimination methods based on virtual substitution beyond degree 2 of the quantified variables systematically enumerate all possible real types of certain parametric polynomials occurring in the input formula [16, 21]. Modern implementations of this approach by Košta in

<footnote>*Also with MPI Informatics and Saarland University, Saarland Informatics Campus, Saarbrücken, Germany.</footnote>
Redlog [1, 8] and by Tonks in Maple [17, 18] have evolved from a seminal article by Weispfenning [20]. Virtual substitution methods are well known for numerous applications in the sciences [2, 15]. Recent application areas include chemical reaction network theory in the sense of Feinberg [3] in Redlog [4, 13] and economics in Maple [11].

Another group of quantifier elimination procedures employs disjunctive normal form computations and systematic case distinctions on parameters to arrive at systems of univariate constraints such as $f_1 > 0, f_2 = 0, f_3 \le 0$ with $f_i$ as above. The existence of a solution of the system is equivalent to the occurrence of one of the columns $[1, 0, 0]^T$ or $[1, 0, -1]^T$ in the real type Eq. (2). This approach has been described by Hörmander [6], based on an unpublished manuscript by Paul Cohen. An algorithm by Muchnik [10, 14] is closely related. In spite of its comparatively high asymptotic complexity, the approach has received quite some attention for its simplicity. For instance, it was used as a basis for a fully proof-producing quantifier elimination procedure by McLaughlin and Harrison [9].

We found that there exists surprisingly little foundational work on real types. Specifically, natural combinatorial questions related to their number are not answered in the literature. Our foundational work here aims at contributing to closing this gap. It is our hope that our work will be helpful for algorithm design and complexity considerations in the field.

We consider finite families $f_1, \dots, f_n$ of polynomials, and we denote by $d_1, \dots, d_n$ their degrees and by $m$ the finite cardinality of the union of their real roots. In terms of these notions we are going to derive here the following results:

(1) In the special case $n = 1$, we simplify Košta's result Eq. (3) to a simple case distinction

$$R_d = \begin{cases} 2F_{d+2} & \text{if } d \text{ is even,} \\ 2F_{d+2} - 2 & \text{if } d \text{ is odd,} \end{cases}$$

based on Fibonacci numbers, which can be expressed in closed form, in contrast to sums of binomial coefficients; see Theorem 10.

(2) On these grounds, we derive another closed form for the number of all real types realized by a single polynomial up to degree $d$; see Theorem 13:

$$\hat{R}_d = 2 \cdot F_{d+3} - 2.$$

It follows that $R_d, \hat{R}_d \in \Theta(\varphi^d)$, where $\varphi$ is the golden ratio, and $\Theta$ is the Bachmann–Landau symbol for asymptotic growth of the same order following Knuth's definition [7]; see Corollary 15.

(3) For the general case $n \ge 1$, we derive a formula for the number of all real types realized by polynomials with degrees $d_i$ and $m$ distinct real roots:

$$R_{d_1, \dots, d_n}^{(m)} = \sum_{i=0}^{m} (-1)^i \binom{m}{i} \prod_{j=1}^{n} \sum_{k=0}^{m-i} \binom{m-i}{k} R_{d_j}^{(k)} \quad (4)$$

with $R_{d_j}^{(k)}$ defined as in Eq. (3). Summation over $m$ yields an explicit form for the number $R_{d_1, \dots, d_n}$ of all real types realized by polynomials with degrees $d_i$ and any number of roots, in analogy to Eq. (3). However, compared to the

<table><caption>**Table 1: List of symbols**</caption><tr><td>$R_d^{(m)}$</td><td>The number of real types realized by ...</td></tr><tr><td>$R_d$</td><td>one polynomial of degree $d$ with $m$ distinct real roots</td></tr><tr><td>$\hat{R}_d$</td><td>one polynomial of degree $d$</td></tr><tr><td>$R_{d_1, \dots, d_n}^{(m)}$</td><td>one polynomial up to degree $d$</td></tr><tr><td>$R_{d_1, \dots, d_n}$</td><td>$n$ polynomials of degrees $d_i$ with $m$ distinct real roots</td></tr><tr><td>$\hat{R}_{d_1, \dots, d_n}$</td><td>$n$ polynomials of degrees $d_i$</td></tr><tr><td>$S_n^{(m)}$</td><td>$n$ polynomials up to degrees $d_i$</td></tr><tr><td>$S_n^{(m)}$</td><td>$n$ polynomials of any degree with $m$ distinct real roots</td></tr></table>

special case $n = 1$ above, we do not obtain a closed form; see Theorem 20.

(4) For the number of all real types realized by polynomials with any choice of $d_1, \dots, d_n$ and $m$ distinct real roots, we can reduce Eq. (4) to the closed form

$$S_n^{(m)} = 2^n \cdot (3^n - 1)^m,$$

which generalizes $S_1^{(m)} = 2^{m+1}$. In particular, this imposes an upper bound on Eq. (4); see Proposition 26.

Table 1 provides a summary of the symbols introduced throughout this article. Section 2 presents relevant definitions and basic results used throughout the article. Section 3 discusses the special case of a single polynomial, and Section 4 subsequently generalizes to families of polynomials. In a final Section 5 we finally summarize and evaluate our results.

## 2 Preliminaries

In the following, we denote with $\Sigma = \{-1, 0, 1\}$ the set of all possible signs.

### 2.1 Real types of single polynomials

Consider a non-zero univariate polynomial $f \in \mathbb{R}[x]$ of degree $d$ and assume $f$ has exactly $m$ real zeros $x_1 < \dots < x_m$. Then the real line can be partitioned into $2m + 1$ subsets

$$\mathbb{R} = (-\infty, x_1) \cup \{x_1\} \cup (x_1, x_2) \cup \{x_2\} \cup \dots \cup \{x_m\} \cup (x_m, \infty)$$

where the sign of $f$ is constant on each subset. The real type of $f$ is the sign sequence $s \in \Sigma^{2m+1}$ where $s_i \in \Sigma$ is the sign of $f$ on the $i$-th subset.

**Example 1.** The linear polynomials $2x + 1$ and $-x + 3$ have real types $[-1, 0, 1]$ and $[1, 0, -1]$, respectively. The quadratic polynomial $x^2 + 2x - 3$ has real type $[1, 0, -1, 0, 1]$, and the cubic polynomial $x^3$ has again real type $[-1, 0, 1]$.

Let $s \in \Sigma^{2m+1}$. Then we say $s$ is a real $d$-type if it can be realized by a polynomial of degree $d$, i.e. there exists a non-zero polynomial $f \in \mathbb{R}[x]$ of degree $d$ with real type $s$. For example

**Example 2.** On the one hand, $[-1, 0, 1]$ is both a real 1-type and a real 3-type, since it can be realized by $2x + 1$ and $x^3$, respectively. On the other hand, $[1, 0, 1]$ is a real 2-type, since it can be realized by $x^2$, but it is not a real 1-type.
<table><caption>**Table 2:** Exact numbers of real *d*-types for *d* = 0, ..., 10</caption><thead><tr><th>d</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th></tr></thead><tbody><tr><th>R<sub>d</sub></th><td>2</td><td>2</td><td>6</td><td>8</td><td>16</td><td>24</td><td>42</td><td>66</td><td>110</td><td>176</td><td>288</td></tr></tbody></table>

Košta [8, Section 2.1] derived a formula for the number of real *d*-types. The main step was to prove the following proposition, which gives a formula for the number $R_d^{(m)}$ of real *d*-types which are realized by polynomials with exactly *m* distinct real roots.

**PROPOSITION 3 (KOŠTA, 2016).** The number $R_d^{(m)}$ of real *d*-types realized by polynomials with exactly *m* distinct real roots is given by

$$R_d^{(m)} = 2 \sum_{j \ge 0} \binom{m}{2m-d+2j} \quad \square$$

Note that the sum in the proposition is finite, since the binomial coefficients vanish for $2m - d + 2j > m$.

Since a polynomial of degree *d* has at most *d* distinct real roots, it follows directly that the number $R_d$ of all real *d*-types is given by the following equation [8, Equation 2.3]:

$$R_d = \sum_{m=0}^{d} R_d^{(m)} = 2 \cdot \sum_{m=0}^{d} \sum_{j \ge 0} \binom{m}{2m-d+2j} \quad (5)$$

Table 2 shows the numbers of real *d*-types up to *d* = 10 [8, Table 2.1]. All values in the table are even, because $f \mapsto -f$ induces a bijection between real *d*-types realized by polynomials with a positive and with a negative leading coefficient. Note that we do not count the zero polynomial. It is possible to define the real type of $0 \in \mathbb{R}[x]$ as [0], which is not realized by any non-zero polynomial. This would increase all relevant bounds in the table by 1.

## 2.2 The structure of real types

We present some facts about the structure of real types of single polynomials that will be used throughout the paper. We begin with a key lemma by Košta that gives constraints on the entries of a real type depending on the multiplicities of the real roots of a polynomial.

**Lemma 4 (Košta, 2016; Lemma 4).** Let $[s_1, \dots, s_{2m+1}]$ be a real type of a positive-degree polynomial $f \in \mathbb{R}[x]$ with $m$ distinct real roots $\beta_1 < \dots < \beta_m$ with multiplicities $k_1, \dots, k_m$, respectively. Then for each $j \in \{1, \dots, m\}$, we have

$$s_{2j+1} = (-1)^{k_j} \cdot s_{2j-1}. \quad \square$$

As a consequence, the real type of a polynomial depends only on the sign of its leading coefficient and the parity of the multiplicities of its real roots.

**Lemma 5.** Let $f \in \mathbb{R}[x]$ be a non-zero polynomial with leading coefficient $\alpha$ and $m$ real roots $\beta_1 < \dots < \beta_m$ with multiplicities $k_1, \dots, k_m$, respectively. Then the real type of $f$ depends only on sign($\alpha$) and $k_i \mod 2$ for $1 \le i \le m$.

**PROOF.** Denote with $s = (s_1, \dots, s_{2m+1}) \in \Sigma^{2m+1}$ the real type of $f$. By assumption, we can factor $f$ as

$$f(x) = (x - \beta_1)^{k_1} \cdots (x - \beta_m)^{k_m} \cdot g(x)$$

for a polynomial $g \in \mathbb{R}[x]$ with $g(x) \neq 0$ for all $x \in \mathbb{R}$. Then

$$\begin{aligned} s_1 &= \lim_{x \to -\infty} \operatorname{sign} f(x) = \operatorname{sign}(\alpha) \cdot (-1)^{\deg f} \\ &= \operatorname{sign}(\alpha) \cdot (-1)^{\deg f \mod 2} \end{aligned}$$

where $\deg f = \sum_{i=1}^{m} k_i + \deg g$. Since $g$ has no real roots, the intermediate value theorem implies that $\deg g$ is even. Hence,

$$s_1 = \operatorname{sign}(\alpha) \cdot (-1)^{\sum_{i=1}^{m} k_i \mod 2}$$

which depends only on $\operatorname{sign}(\alpha)$ and $k_i \mod 2$. Lemma 4 then implies that

$$s_{2j+1} = \operatorname{sign}(\alpha) \cdot (-1)^{\sum_{i=j+1}^{m} k_i \mod 2}$$

for all $1 \le j \le m$. Additionally, we always have $s_{2j} = 0$ for all $1 \le j \le m$. Thus, the real type $s$ depends only on $\operatorname{sign}(\alpha)$ and $k_i \mod 2$. $\square$

Using this lemma, Košta arrives at Proposition 3 by counting all possible parities of multiplicities for a given degree *d* and a given number of real roots *m*. Moreover, it follows that a sign sequence is a real type if and only if it is a real type of a polynomial with integer coefficients. This is important for algorithmic purposes, where input over a finite alphabet is required.

**PROPOSITION 6.** A sign sequence in $\Sigma^{2m+1}$ is the real type of a polynomial in $\mathbb{R}[x]$ if and only if it is the real type of a polynomial in $\mathbb{Z}[x]$.

**PROOF.** Let $s \in \Sigma^{2m+1}$ be the real type of a polynomial $f \in \mathbb{R}[x]$. Assume that $f$ has leading coefficient $\alpha$ and $m$ real roots $\beta_1 < \dots < \beta_m$ with multiplicities $k_1, \dots, k_m$, respectively. Define the polynomial

$$g(x) = \operatorname{sign}(\alpha) \cdot (x-1)^{k_1} \cdots (x-m)^{k_m} \in \mathbb{Z}[x].$$

Then Lemma 5 implies that $g$ has also real type $s$, since the leading coefficients of $f$ and $g$ have the same sign and the multiplicities of both polynomials agree. The converse follows from $\mathbb{Z}[x] \subseteq \mathbb{R}[x]$. $\square$

## 2.3 Real types of families of polynomials

We generalize our notion of real types to families of polynomials. Let $f_1, \dots, f_n \in \mathbb{R}[x]$ be non-zero polynomials and consider their combined roots

$$V = \{x \in \mathbb{R} \mid f_i(x) = 0 \text{ for some } 1 \le i \le n\}.$$

Since each polynomial has a finite number of roots, $V$ is again finite and consists of $m$ points $x_1 < \dots < x_m$. As in the case of a single polynomial, these points partition the real line into $2m + 1$ subsets

$$\mathbb{R} = (-\infty, x_1) \cup \{x_1\} \cup (x_1, x_2) \cup \{x_2\} \cup \dots \cup \{x_m\} \cup (x_m, \infty),$$

where the sign of each polynomial $f_i$ is constant on each subset. Denote with $\sigma_{i,j} \in \Sigma$ the sign of $f_i$ on the $j$-th subset. Then the real type of $f_1, \dots, f_n$ is given by the sign matrix

$$\begin{bmatrix} \sigma_{1,1} & \dots & \sigma_{1,2m+1} \\ \vdots & \ddots & \vdots \\ \sigma_{n,1} & \dots & \sigma_{n,2m+1} \end{bmatrix} \in \Sigma^{n \times (2m+1)}.$$

It follows that every odd column of a real type contains exclusively -1 or 1, and every even column contains at least one zero.
Furthermore, the i-th row is given by the real type of $f_i$, possibly with some entries repeated.

It is not hard to see that Proposition 6 generalizes to families of polynomials and sign matrices.

### 3 Counting real types of single polynomials

We want to improve the explicit form given in Eq. (5) to a closed form, which will be based on Fibonacci numbers $F_n$. The Fibonacci sequence is recursively defined as $F_1 = 1$, $F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \ge 3$. It starts with

$$1, 1, 2, 3, 5, 8, 13, 21, \dots \qquad (6)$$

Before we can prove our first theorem, we first need the following two lemmas, which establish a recursive relation and base cases for the number $R_d^{(m)}$ of real $d$-types realized by polynomials with exactly $m$ distinct real roots.

**Lemma 7.** Let $d \ge 0$. Then

$$R_d^{(0)} = \begin{cases} 2 & \text{if } d \text{ is even,} \\ 0 & \text{if } d \text{ is odd.} \end{cases}$$

**PROOF.** First, assume that the degree $d$ is even. Then, the intermediate value theorem implies that any real $d$-type without zeros is of the form $(1, \dots, 1)$ or $(-1, \dots, -1)$. Both real types can for example be realized by $x^d + 1$ and $-x^d - 1$, respectively, which shows $R_d^{(0)} = 2$. Next, assume that $d$ is odd. By the intermediate value theorem, every polynomial of odd degree has at least one real zero. Thus, $R_d^{(0)} = 0$ in this case. $\square$

**Lemma 8.** Let $d \ge 2$ and $m \ge 1$. Then

$$R_d^{(m)} = R_{d-2}^{(m-1)} + R_{d-1}^{(m-1)}.$$

**PROOF.** Consider the set $T_d^{(m)} = \{s \in \Sigma^{2m+1} | s \text{ is a real } d\text{-type}\}$, which can be partitioned depending on whether $s_{2m+1} = s_{2m-1}$ or $s_{2m+1} = -s_{2m-1}$. We show that there is a bijection between the first part and $T_{d-2}^{(m-1)}$, on the one hand, and between the second part and $T_{d-1}^{(m-1)}$, on the other hand.

For the first part, consider a polynomial $f$ of degree $d-2$ that realizes a real type $s \in T_{d-1}^{(m-1)}$. Let $p \in \mathbb{R}$ be larger than all roots of $f$. Then $f \cdot (x-p)^2$ realizes the type $[s_1, \dots, s_{2m-1}, 0, s_{2m-1}]$. Conversely, assume that a polynomial $f$ of degree $d$ realizes a real type $s \in T_d^{(m)}$ such that $s_{2m+1} = s_{2m-1}$. Let $p \in \mathbb{R}$ be the largest root of $f$ and denote by $k \in \mathbb{N}$ its multiplicity. Then $k$ is even, and therefore $(x^{k-2} + 1) \cdot f/(x-p)^k$ is of degree $d-2$ and realizes the real type $[s_1, \dots, s_{2m-1}]$.

We use the same argument for the second part. Consider a polynomial $f$ of degree $d-1$ that realizes a real type $s \in T_{d-1}^{(m-1)}$. Let $p \in \mathbb{R}$ be larger than all roots of $f$. Then $f \cdot (x-p)$ realizes the type $[s_1, \dots, s_{2m-1}, 0, -s_{2m-1}]$. Conversely, assume that a polynomial $f$ of degree $d$ realizes a real type $s \in T_d^{(m)}$ such that $s_{2m+1} = -s_{2m-1}$. Let $p \in \mathbb{R}$ be the largest root of $f$ and denote by $k \in \mathbb{N}$ its multiplicity. Then $k$ is odd, and therefore $(x^{k-1} + 1) \cdot f/(x-p)^k$ is of degree $d-1$ and realizes the real type $[s_1, \dots, s_{2m-1}]$. $\square$

**Remark 9.** Shorter, though less insightful, the lemma can be proved via a simple transformation on binomial coefficients. Let $j \ge 0$. Then the relation $(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n-1 \\ k \end{matrix}) + (\begin{matrix} n-1 \\ k-1 \end{matrix})$ for all $n \ge 1$ and $k \in \mathbb{Z}$ yields

$$\begin{pmatrix} n \\ 2n - d + 2j \end{pmatrix} = \begin{pmatrix} n-1 \\ 2n - d + 2j \end{pmatrix} + \begin{pmatrix} n-1 \\ 2n - d + 2j - 1 \end{pmatrix} \\ = \begin{pmatrix} n-1 \\ 2(n-1) - (d-2) + 2j \end{pmatrix} + \begin{pmatrix} n-1 \\ 2(n-1) - (d-1) + 2j \end{pmatrix}.$$

Hence, by summing over all $j \ge 0$ on both sides and using Proposition 3, we obtain $R_d^{(m)} = R_{d-2}^{(m-1)} + R_{d-1}^{(m-1)}$.

Using the previous two lemmas, we can show by induction that the number of real $d$-types is given by a case distinction of closed forms involving Fibonacci numbers.

**THEOREM 10.** The number $R_d$ of real $d$-types is

$$R_d = \begin{cases} 2F_{d+2} & \text{if } d \text{ is even,} \\ 2F_{d+2} - 2 & \text{if } d \text{ is odd.} \end{cases}$$

**PROOF.** We prove the statement by induction on $d$. The cases $d=0$ and $d=1$ can directly be checked using Table 2 and Eq. (6). Now, let $d \ge 2$ and assume the statement holds for $d-1$ and $d-2$. Then Lemma 8 yields

$$R_d = \sum_{m=0}^{d} R_d^{(m)} = R_d^{(0)} + \sum_{m=1}^{d} (R_{d-1}^{(m-1)} + R_{d-2}^{(m-1)}).$$

By splitting up the sum and performing an index shift, we obtain

$$R_d = R_d^{(0)} + \sum_{m=0}^{d-1} R_{d-1}^{(m)} + \sum_{m=0}^{d-2} R_{d-2}^{(m)} + R_{d-2}^{(d-1)}.$$

Furthermore, a polynomial of degree $d-2$ has at most $d-2$ distinct real roots, which implies $R_{d-2}^{(d-1)} = 0$. Thus,

$$R_d = R_d^{(0)} + R_{d-1} + R_{d-2}.$$

If $d$ is even, Lemma 7 and the induction hypothesis yield

$$R_d = 2 + (2F_{d+1} - 2) + 2F_d = 2F_{d+2}.$$

Otherwise, $d$ is odd and

$$R_d = 2F_{d+1} + (2F_d - 2) = 2F_{d+2} - 2. \quad \square$$

Next, we extend the previous theorem to counting the number of real types for polynomials up to degree $d$ instead of exactly degree $d$. The following two lemmas show that this number is given by $R_d + R_{d-1}$. Note that we do not sum over all smaller degrees.

**Lemma 11.** If $s$ is a real $d$-type, then $s$ is also a real $(d+2)$-type.

**PROOF.** Let $s$ be a real $d$-type. Then $s$ is realized by a polynomial $f \in \mathbb{R}[x]$ of degree $d$. Define the polynomial $g = f \cdot (x^2 + 1)$. For all $x \in \mathbb{R}$, we have $x^2 + 1 > 0$, and thus

$$\operatorname{sign} g(x) = \operatorname{sign} f(x).$$

Thus $s$ is also realized by the polynomial $g$, which has degree $d+2$. $\square$

**Lemma 12.** The sets of real types realized by polynomials with an even degree and with an odd degree are disjoint.
PROOF. Let $s \in \Sigma^n$ be a sign sequence which is realized by a polynomial $f \in \mathbb{R}[x]$ of degree $d$. Assume $d$ is even. Then

$$ \lim_{x \to -\infty} \operatorname{sign} f(x) = \lim_{x \to \infty} \operatorname{sign} f(x), $$

which implies $s_1 = s_n$. On the other hand, if $d$ is odd, then

$$ \lim_{x \to -\infty} \operatorname{sign} f(x) = - \lim_{x \to \infty} \operatorname{sign} f(x), $$

which implies $s_1 = -s_n$. Thus, a sign sequence $s$ can not be realized by a polynomial of even degree and by a polynomial of odd degree at the same time. $\square$

After these preparations, we can state our theorem.

THEOREM 13. Then the number $\hat{R}_d$ of real types realized by polynomials up to degree $d$ is $\hat{R}_d = 2F_{d+3} - 2$.

PROOF. In the case $d = 0$, Table 2 and Eq. (6) yield $\hat{R}_0 = 2 = 2F_3 - 2$. Now assume $d \ge 1$. According to Lemma 11 and Lemma 12, any real type which can be realized by a polynomial up to degree $d$ can either be realized by a polynomial of degree $d$ or by a polynomial of degree $d-1$. Thus, $\hat{R}_d = R_d + R_{d-1}$. Applying Theorem 10 yields that this number is given by

$$ \hat{R}_d = R_d + R_{d-1} = 2 \cdot F_{d+2} + 2 \cdot F_{d+1} - 2 = 2 \cdot F_{d+3} - 2. \quad \square $$

Given Theorem 10 and Theorem 13, Binet's formula can be used to obtain a closed formula for the numbers $R_d$ and $\hat{R}_d$. This additionally allows us to determine their precise asymptotic growth.

PROPOSITION 14 (BINET'S FORMULA). The Fibonacci numbers can be expressed in closed form as

$$ F_n = \frac{1}{\sqrt{5}} (\varphi^n - (-\varphi)^{-n}), $$

where $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$ is the golden ratio. $\square$

COROLLARY 15. Let $R_d$ be the number of real types realized by polynomials of exactly degree $d$, let $\hat{R}_d$ be the number of real types realized by polynomials up to degree $d$, and let $\varphi$ denote the golden ratio. Then the following holds:

$$ R_d = \Theta(\varphi^d), \quad \hat{R}_d = \Theta(\varphi^d). $$

PROOF. This follows immediately from Theorem 10, Theorem 13 and Proposition 14 since $|\varphi^{-1}| < 1$, which implies $\varphi^{-n} \to 0$ as $n \to \infty$. $\square$

# 4 Counting real types of families of polynomials

We are interested in two possible questions regarding sign matrices of families of real polynomials, where (a) is a generalization of Košta's result from Proposition 3 for a single polynomial:

(a) the number of sign matrices as a function of matrix dimensions and polynomial degrees;

(b) the number of sign matrices as a function of matrix dimensions, for arbitrary polynomial degrees.

## 4.1 Sign matrices depending on degrees

Consider $n, m \in \mathbb{N}$ and degrees $d_1, \dots, d_n \ge 1$. We want to count the number $R_{d_1, \dots, d_n}^{(m)}$ of matrices in $\Sigma^{n \times (2m+1)}$ that establish a real $(d_1, \dots, d_n)$-type for a family of $n$ polynomials.

As a first step, we characterize these matrices as follows.

PROPOSITION 16. A matrix in $\Sigma^{n \times (2m+1)}$ is a real $(d_1, \dots, d_n)$-type if and only if the following hold:

(1) Every even column contains at least one zero.

(2) Every odd column does not contain any zero.

(3) Row $i$ is a real $d_i$-type up to repeated entries.

PROOF. Let $A \in \Sigma^{n \times (2m+1)}$ be a real $(d_1, \dots, d_n)$-type. Then all three properties follow directly from the definition of real $(d_1, \dots, d_n)$-types in Section 2.3. Conversely, consider $A \in \Sigma^{n \times (2m+1)}$ that satisfies the three properties. According to property (3), each row $i$ of $A$ is the real type of a polynomial $f_i$ up to repeated entries. Using the construction in the proof of Proposition 6, we may assume without loss of generality that $f_i$ has its real roots at the points $j \in \{1, \dots, 2m+1\}$ with $A_{i,j} = 0$. It is not hard to see that the real type of the polynomials $f_1, \dots, f_n$ thus obtained is our matrix $A$. Hence, $A$ is a real $(d_1, \dots, d_n)$-type. $\square$

It is noteworthy that $R_{d_1, \dots, d_n}^{(m)}$ satisfies a recurrence relation similar to Lemma 8:

PROPOSITION 17. Let $d_1, \dots, d_n \ge 2$ and $m \ge 1$. Then

$$ R_{d_1, \dots, d_n}^{(m)} = \sum_{\substack{e \in \{0,1,2\}^n \\ e \neq (0, \dots, 0)}} R_{d_1-e_1, \dots, d_n-e_n}^{(m-1)} $$

PROOF. Partition the set

$$ T_{d_1, \dots, d_n}^{(m)} = \{A \in \Sigma^{n \times (2m+1)} \mid A \text{ is a real } (d_1, \dots, d_n)\text{-type}\} $$

into $\{P_e \mid e \in \{0, 1, 2\}^n, e \ne (0, \dots, 0)\}$, where $P_e$ is the set of all $A$ such that for all $i \in \{1, \dots, n\}$ the following holds:

(a) if $e_i = 0$, then $A_{i,2m} = A_{i,2m+1}$;

(b) if $e_i = 1$, then $A_{i,2m-1} = -A_{i,2m+1}$;

(c) if $e_i = 2$, then $A_{i,2m-1} = A_{i,2m+1}$.

This case distinction is disjoint and complete by Proposition 16. Let $e \in \{0, 1, 2\}^n$ with $e \ne (0, \dots, 0)$, and denote $d - e = (d_1 - e_1, \dots, d_n - e_n)$. We show that there is a bijection between $T_{d-e}^{(m)}$ and $P_e$ using essentially the arguments of the proof of Lemma 8.

Let $f_1, \dots, f_n$ be polynomials of degrees $d_1 - e_1, \dots, d_n - e_n$, respectively, that realize a real type $A \in T_{d-e}^{(m)}$. Let $p \in \mathbb{R}$ be larger than all real roots of all $f_i$. Then the polynomials $f_i \cdot (x-p)^{e_i}$ realize the corresponding real $(d_1, \dots, d_n)$-type in $P_e$.

Conversely, let $f_1$, dots, $f_n$ be polynomials with degrees $d_1, \dots, d_n$, respectively, that realize a real type in $P_e$. Let $p \in \mathbb{R}$ be the maximum of all roots of the $f_i$. Let $k_i$ be the multiplicity of $f_i$ at $p$, where the multiplicity is 0 if $p$ is not a root. Then the polynomials $(x^{k_i-e_i} + 1) \cdot f_i/(x-p)^{k_i}$ realize the corresponding real type in $T_{d-e}^{(m)}$. $\square$

Our next goal is to find a closed formula for $R_{d_1, \dots, d_n}^{(m)}$. Since we know how to compute the number of real $d_i$-types, we can focus on the distribution of zeros in sign matrices. To handle the condition that every even column contains at least one zero, we
use an inclusion-exclusion argument in the sense of van Lint and Wilson [19, Theorem 10.1]:

**PROPOSITION 18 (VAN LINT AND WILSON, 1992).** Let $S$ be a set of size $N$ and $E_1, \dots, E_r$ not necessarily distinct subsets of $S$. For any subset $M$ of $\{1, \dots, r\}$, we define $N(M)$ to be the number of elements of $S$ in $\bigcap_{i \in M} E_i$ and for $0 \le j \le r$, we define $N_j = \sum_{|M|=j} N(M)$. Then the number of elements of $S$ not in any of the subsets $E_i$, $1 \le i \le r$, is

$$N - N_1 + N_2 - N_3 + \dots + (-1)^r N_r. \quad \square$$

In order to apply this proposition to real types, we define the set $S$ to be the set of all matrices in $\Sigma^{n \times (2m+1)}$ such that

(1) every odd column does not contain any zero;

(2) row $i$ is a real $d_i$-type up to repeated entries.

Furthermore, we define the subsets $E_i$ for $1 \le i \le m$ as the sets of all elements in $S$ that satisfy the additional constraint

(3) column $2i$ does not contain a zero.

On these grounds, Proposition 16 yields that the number $R_{d_1, \dots, d_n}^{(m)}$ of real $(d_1, \dots, d_n)$-types with $m$ distinct real roots is given by

$$R_{d_1, \dots, d_n}^{(m)} = |S \setminus (E_1 \cup \dots \cup E_m)|,$$

which can, in turn, be computed using the inclusion-exclusion formula from Proposition 18. However, before we can apply the formula, we first have to determine the numbers $N(M)$ of elements in the intersections $\bigcap_{i \in M} E_i$ for subsets $M \subseteq \{1, \dots, m\}$.

**Lemma 19.** Let $M \subseteq \{1, \dots, m\}$ be a possibly empty subset. Then the number $N(M)$ of matrices in $S$ that contain no zero in column $2j$ for all $j \in M$ is given by

$$N(M) = \prod_{i=1}^{n} \sum_{k=0}^{m-|M|} \binom{m-|M|}{k} R_{d_i}^{(k)}.$$

**PROOF.** Consider the row $i$ of a matrix in $S$ and assume it contains exactly $k$ zeros in the columns $\{2, 4, \dots, 2m\} \setminus 2M$. Then there are $\binom{m-|M|}{k}$ possibilities for choosing these zeros, and for each selection of zeros there are $R_{d_i}^{(k)}$ possibilities to choose the remaining entries from $\{-1, 1\}$. Thus, by summing over all possible values of $k$, we obtain

$$\sum_{k=0}^{m-|M|} \binom{m-|M|}{k} R_{d_i}^{(k)}$$

possibilities for row $i$. Since the entries in each of the $n$ rows do not depend on the entries of other rows, the total number of matrices is given by

$$N(M) = \prod_{i=1}^{n} \sum_{k=0}^{m-|M|} \binom{m-|M|}{k} R_{d_i}^{(k)} \quad \square$$

Using this lemma, we can apply the inclusion-exclusion formula to obtain a formula for the number of real types of families of polynomials.

**THEOREM 20.** The number $R_{d_1, \dots, d_n}^{(m)}$ of matrices in $\Sigma^{n \times (2m+1)}$ that are real $(d_1, \dots, d_n)$-types is given by

$$R_{d_1, \dots, d_n}^{(m)} = \sum_{i=0}^{m} (-1)^i \binom{m}{i} \prod_{j=1}^{n} \sum_{k=0}^{m-i} \binom{m-i}{k} R_{d_j}^{(k)}. \quad (7)$$

**PROOF.** Using the previous notation, Proposition 16 and Proposition 18 imply that the number of real types is given by

$$R_{d_1, \dots, d_n}^{(m)} = |S \setminus (E_1 \cup \dots \cup E_m)| = \sum_{i=0}^{m} (-1)^i N_i, \quad (8)$$

where $N_i = \sum_{|M|=i} N(M)$ and $N(M)$ is the number of matrices in $S$ that for all $j \in M$ there occurs no zero in column $2j$. By Lemma 19, $N(M)$ depends only on $|M|$ and is given by

$$N(M) = \prod_{j=1}^{n} \sum_{k=0}^{m-|M|} \binom{m-|M|}{k} R_{d_j}^{(k)}.$$

Furthermore, there are $\binom{m}{i}$ possibilities of choosing $M \subseteq \{1, \dots, m\}$ with $|M| = i$, which yields

$$N_i = \binom{m}{i} \prod_{j=1}^{n} \sum_{k=0}^{m-i} \binom{m-i}{k} R_{d_j}^{(k)}.$$

Substituting $N_i$ back into Eq. (8) shows that the number of real types is given by

$$R_{d_1, \dots, d_n}^{(m)} = \sum_{i=0}^{m} (-1)^i \binom{m}{i} \prod_{j=1}^{n} \sum_{k=0}^{m-i} \binom{m-i}{k} R_{d_j}^{(k)} \quad \square$$

As with a single polynomial, we can eliminate the dependence on $m$ and count sign matrices with an arbitrary number of columns by summing over all possible numbers of roots.

**COROLLARY 21.** The number $R_{d_1, \dots, d_n}$ of sign matrices that are real $(d_1, \dots, d_n)$-types is given by

$$R_{d_1, \dots, d_n} = \sum_{m=0}^{d_1 + \dots + d_n} R_{d_1, \dots, d_n}^{(m)} \quad (9)$$

**PROOF.** The statement follows directly from Theorem 20 since sets of sign matrices of different dimensions are disjoint, and $n$ non-zero polynomials of degrees $d_1, \dots, d_n$ have at most $d_1 + \dots + d_n$ many roots. $\square$

Additionally, we can regard the degrees $d_1, \dots, d_n$ as only upper bounds and obtain a generalization of Theorem 13 for families of polynomials.

**COROLLARY 22.** The number $\tilde{R}_{d_1, \dots, d_n}$ of sign matrices realized by $n$ non-zero polynomials up to degrees $d_1, \dots, d_n$ is given by

$$\tilde{R}_{d_1, \dots, d_n} = \sum_{\delta \in \{0, 1\}^n} R_{d_1 - \delta_1, \dots, d_n - \delta_n}.$$

**PROOF.** As in the proof of Theorem 20, we have $\tilde{R}_d = R_d + R_{d-1}$ for a single polynomial. Since the rows of a sign matrices are given by $n$ independent real types of single polynomials, the statement follows. $\square$

Note that the formulas for $R_{d_1, \dots, d_n}$ and $\tilde{R}_{d_1, \dots, d_n}$ in the previous two corollaries exclude the zero polynomial. It is possible to adjust the formulas to cover the zero polynomial via summation over all sublists of $(d_1, \dots, d_n)$.
**Example 23.** Hong discussed the following example as an application of his method of slope resultants [5, Section 5]:

$$ \exists x(f_1 = 0 \land f_2 = 0 \land f_3 \le 0), $$

where $f_1 = ux^2 + vx + 1$, $f_2 = vx^3 + wx + u$, and $f_3 = wx^2 + vx + u$. This asks for a Boolean combination of polynomial constraints in the parameters $u, v, w$ for the system $f_1 = 0, f_2 = 0, f_3 \le 0$ to have a real solution. Given a choice of parameters, the answer is positive if and only if the corresponding sign matrix of the family $f_1, f_2, f_3$ with degrees 2, 3, 2, respectively, contains a column $[0, 0, 0]^T$ or a column $[0, 0, -1]^T$. It follows from Lemma 5 that only finitely many sign matrices need be considered. Those sign matrices are enumerated in the course of constructing a full case distinction on the combined vanishing of sequences of leading terms with parametric coefficients. Since all cases are treated independently, identical sign matrices get enumerated multiple times [6, 14]. We are interested in an upper bound on the number of sign matrices thus enumerated.

The number of $R_{2,3,2}$ of real (2, 3, 2)-types can be computed via Eq. (9) in Corollary 21. Assuming for simplicity that all coefficients are parametric and algebraically independent, the following summation takes into consideration all cases of vanishing leading terms as described above, except for border cases where one of the polynomials $f_1, f_2, f_3$ vanishes altogether. This exception is owed to the general exclusion of zero polynomials throughout our work here:

$$ \bar{R}_{d_1, d_2, d_3} = \sum_{e_1=0}^{d_1} \sum_{e_2=0}^{d_2} \sum_{e_3=0}^{d_3} R_{e_1, e_2, e_3}. \quad (10) $$

The possible complete vanishing of one or several of the $f_1, f_2, f_3$ is finally modeled by considering all sublists of $(d_1, d_2, d_3)$:

$$ \bar{\bar{R}}_{d_1, d_2, d_3} = \sum_{e \subseteq (d_1, d_2, d_3)} \bar{R}_e. \quad (11) $$

Note that the summations in Eq. (10) and Eq. (11) reflect the application of our results to an exponential number of subproblems, all of which are independent from the perspective of our framework here. This genuinely distinguishes these summations from, e.g., the summation in Corollary 22.

Using the Python code in Figure 2, we quickly compute $R_{2,3,2} = 26624$, $\bar{R}_{2,3,2} = 53736$, and our main result

$$ \bar{\bar{R}}_{2,3,2} = 55339 \approx 5 \cdot 10^4. \quad (12) $$

**Example 24.** Similarly to Example 23, Weispfenning introduced the following first-order formula as a benchmark for real quantifier elimination [21, Section 5.5]:

$$ \exists x \left( \bigwedge_{i=1}^{2} f_i = 0 \land \bigwedge_{i=3}^{5} f_i < 0 \right), \quad f_i = a_i x^2 + b_i x + c_i. $$

Here, the answer is positive for choices of parameters $a_1, \dots, c_5$ for which the sign matrix of the family $f_1, \dots, f_5$ contains a column $[0, 0, -1, -1, -1]^T$. Using our Python code in Figure 2 once again, we obtain:

$$ \bar{\bar{R}}_{2,2,2,2,2} = 311476091 \approx 3 \cdot 10^8. \quad (13) $$

The large factor between the upper bounds on the numbers of relevant sign matrices in Eq. (13) vs. Eq. (12) supports the intuition that Weispfenning's quantifier elimination example is harder than Hong's.

```python
from itertools import chain, combinations, product as cart produ
from math import comb, prod
from typing import Iterator
```

```python
def binomial(n: int, k: int) -> int:
    # Binomial coefficients with possibly negative arguments
    return comb(n, k) if k >= 0 else 0
```

```python
def all_sublists(L: list[int]) -> Iterator(list[int]):
   itr = chain( combinations(L, i) for i in range(len(L) + 1))
    for tup in itr:
        yield list(tup)
```

```python
def R_m(d: list[int], m: int) -> int:
    # Implements Eq. (7) in Theorem 20
    n = len(d)
    s = sum((-1)**i * binomial(m, i)
            * prod(sum(binomial(m - i, k))
                    for k in range(m - i + 1))
            for j in range(n))
            for i in range(m + 1))
    return 2 ** n * s
```

```python
def R(d: list[int]) -> int:
    # Implements Eq. (9) in Corollary 21
    return sum(R_m(d, m) for m in range(sum(d) + 1))
```

```python
def R_bar(d: list[int]) -> int:
    # Implements Eq. (10) in Example 23
    ranges = [range(d_i + 1) for d_i in d]
    return sum(R(list(e)) for e in cart produ(*ranges))
```

```python
def R_doublebar(d: list[int]) -> int:
    # Implements Eq. (11) in Example 23
    return sum(R_bar(dd) for dd in all_sublists(d))
```

<caption>Figure 2: Python code for the computations in Ex. 23 and 24</caption>

## 4.2 Sign matrices independent of degrees

Recall that $n$ is the number of polynomials considered and $m$ is the number of their distinct real roots. We are now interested in the number $S_n^{(m)}$ of sign matrices in $\Sigma^{n \times (2m+1)}$ that are real types of $n$ polynomials with arbitrary degrees, which eliminates the parameters $d$ and $d_1, \dots, d_n$. The following result considers the case of a single polynomial.

**PROPOSITION 25.** There are $2^{m+1}$ real types realized by single polynomials with exactly $m$ distinct real roots and arbitrary degree.

**PROOF.** Let $s$ be a real type of a polynomial with $m$ distinct real roots. Then $s \in \Sigma^{2m+1}$ and $s_{2i} = 0$ for $1 \le i \le m$. Thus there are at most $2^{m+1}$ possibilities for choosing $s_{2i+1} \in \{-1, 1\}$ for $0 \le i \le m$. Conversely, the number of real types with $m$ roots is bounded from below by $R_{2m+1}^{(m)} + R_{2m}^{(m)}$ since real types with even and odd degree are disjoint by Lemma 12. Proposition 3 then implies

$$ R_{2m+1}^{(m)} + R_{2m}^{(m)} = 2 \sum_{j \ge 0} \binom{m}{2j} + 2 \sum_{j \ge 0} \binom{m}{2j+1} = 2 \sum_{k \ge 0} \binom{m}{k} = 2 \cdot 2^m. $$

This agrees with the above upper bound such that the number of real types is exactly $2^{m+1}$. $\square$

Using Proposition 25, we can simplify the right hand side of Eq. (7) in Theorem 20. We arrive at the following result in closed form, which generalizes that proposition to families of polynomials.

**PROPOSITION 26.** The number $S_n^{(m)}$ of sign matrices in $\Sigma^{n \times (2m+1)}$ which are real types of $n$ polynomials of arbitrary degree is given by

$$ S_n^{(m)} = 2^n \cdot (3^n - 1)^m. \quad (14) $$
PROOF. Proposition 25 and the proof of Lemma 19 and Theorem 20 show that the number of real types realized by polynomials with an arbitrary degree can be obtained by replacing the terms $R_{d_j}^{(k)}$ in

$$ \sum_{i=0}^{m} (-1)^i \binom{m}{i} \prod_{j=1}^{n} \sum_{k=0}^{m-i} \binom{m-i}{k} R_{d_j}^{(k)} $$

with the terms $2^{k+1}$. By the binomial theorem, we have

$$ \sum_{k=0}^{m-i} \binom{m-i}{k} 2^{k+1} = 2 \sum_{k=0}^{m-i} \binom{m-i}{k} 2^k (1)^{(m-i)-k} = 2 \cdot (2+1)^{m-i}, $$

which yields

$$ \prod_{j=1}^{n} 2 \cdot (2+1)^{m-i} = 2^n \cdot 3^{(m-i) \cdot n}. $$

Applying the binomial theorem once again shows that the number $S_n^{(m)}$ is given by

$$ \begin{aligned} S_n^{(m)} &= \sum_{i=0}^{m} (-1)^i \binom{m}{i} 2^n \cdot 3^{(m-i) \cdot n} \\ &= 2^n \sum_{i=0}^{m} \binom{m}{i} (-1)^i (3^n)^{m-i} \\ &= 2^n \cdot (3^n - 1)^m. \end{aligned} \quad \square $$

Note that Eq. (14) imposes an upper bound on $R_{d_1, \dots, d_n}^{(m)}$ in Eq. (7) of Theorem 20.

Remark 27. Alternatively, Proposition 26 can be proved purely combinatorically. From Proposition 16, it follows that we have to count the number of matrices satisfying the properties (1) and (2) in Proposition 25. Consider a matrix of a real type with $2m+1$ columns. There are $2^n$ choices for its first column. Then each row $[s_1, \dots, s_{2m+1}]$ can be extended in three different ways:

(a) $[s_1, \dots, s_{2m+1}, s_{2m+1}, s_{2m+1}]$,

(b) $[s_1, \dots, s_{2m+1}, 0, s_{2m+1}]$,

(c) $[s_1, \dots, s_{2m+1}, 0, -s_{2m+1}]$.

It is easy to see that not all rows can be simultaneously extended via (a). Therefore the matrix can be extended in $3^n - 1$ different ways, which yields the result $2^n \cdot (3^n - 1)^m$.

## 5 Concluding remarks

We have derived explicit or even closed formulas for numbers of real types of single polynomials as well as finite families of polynomials, subject to various parameterizations. In particular, we have provided an explicit formula for the number of real types of families of $n$ polynomials with degrees $d_1, \dots, d_n$ and exactly $m$ distinct real roots. For the special case $n = 1$ we obtain even closed forms, in terms of the golden ratio, with a case distinction depending on the parity of the degree. This refutes a conjecture in the literature.

It remains a challenging open question whether or not closed forms exist in the general case.

## Acknowledgments

The authors gratefully acknowledge the constructive comments of several anonymous reviewers, which significantly improved the article. In particular, one reviewer suggested the proof of Theorem 8 as an alternative to that in Remark 9, encouraged the addition and proof of Proposition 17, and contributed Remark 27.

## References

[1] Andreas Dolzmann and Thomas Sturm. 1997. Redlog: Computer Algebra Meets Computer Logic. ACM SIGSAM Bulletin 31, 2 (June 1997), 2–9. doi:10.1145/261320. 261324

[2] Andreas Dolzmann, Thomas Sturm, and Volker Weispfenning. 1998. Real Quantifier Elimination in Practice. In Algorithmic Algebra and Number Theory, B. H. Matzat, G.-M. Greuel, and G. Hiss (Eds.). Springer, Berlin, 221–247. doi:10.1007/978-3-642-59932-3_11

[3] Martin Feinberg. 2019. Foundations of Chemical Reaction Network Theory. Applied Mathematical Sciences, Vol. 202. Springer. doi:10.1007/978-3-030-03858-8

[4] Dima Grigoriev, Alexandru Iosif, Hamid Rahkooy, Thomas Sturm, and Andreas Weber. 2020. Efficiently and Effectively Recognizing Toricity of Steady State Varieties. Math. Comput. Sci. 15, 2 (2020), 199–232. doi:10.1007/s11786-020-00479-9

[5] Hoon Hong. 1993. Quantifier Elimination for Formulas Constrained by Quadratic Equations via Slope Resultants. THE Computer Journal 36, 5 (1993), 440–449. doi:10.1093/comjnl/36.5.439

[6] Lars Hörmander. 2005. The Analysis of Linear Partial Differential Operators II: Differential Operators with Constant Coefficients. Springer. doi:10.1007/b138375

[7] Donald E. Knuth. 1976. Big Omicron and Big Omega and Big Theta. SIGACT News 8, 2 (April 1976), 18–24. doi:10.1145/1008328.1008329

[8] Marek Kośta. 2016. New Concepts for Real Quantifier Elimination by Virtual Substitution. Doctoral Dissertation. Saarland University, Germany. doi:10.22028/D291-26679

[9] Sean McLaughlin and John Harrison. 2005. A Proof-Producing Decision Procedure for Real Arithmetic. In Proc. CADE-20, Robert Nieuwenhuis (Ed.). LNCS, Vol. 3632. Springer, 295–314. doi:10.1007/11532231_22

[10] Christian Michaux and Adem Ozturk. 2002. Quantifier Elimination following Muchnik. Preprint 10. Université de Mons-Hainaut. Institut de Mathématique, Mons, Belgium.

[11] Casey B. Mulligan, Russell J. Bradford, James H. Davenport, Matthew England, and Zak Tonks. 2018. Non-linear Real Arithmetic Benchmarks derived from Automated Reasoning in Economics. In Proc. SC-Square 2018 (CEUR Workshop Proceedings, Vol. 2189), Anna Maria Bigatti and Martin Brain (Eds.). CEUR-WS.org, 48–60. http://ceur-ws.org/Vol-2189/paper2.pdf

[12] Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger. 1996. A = B. CRC Press. doi:10.1201/9781439864500

[13] Hamid Rahkooy and Thomas Sturm. 2021. Parametric Toricity of Steady State Varieties of Reaction Networks. In Proc. CASC 2021, François Boulier, Matthew England, Timur M. Sadykov, and Evgenii V. Vorozhtsov (Eds.). LNCS, Vol. 12865. Springer, 314–333. doi:10.1007/978-3-030-85165-1_18

[14] Hans Schoutens. 2001. Muchnik's Proof of Tarski–Seidenberg. Online on ResearchGate. https://www.researchgate.net/publication/265186731_MUCHNIK_S_PROOF_OF_TARSKI-SEIDENBERG

[15] Thomas Sturm. 2017. A Survey of Some Methods for Real Quantifier Elimination, Decision, and Satisfiability and Their Applications. Math. Comput. Sci. 11, 3–4 (December 2017), 483–502. doi:10.1007/s11786-017-0319-2

[16] Thomas Sturm. 2018. Thirty Years of Virtual Substitution. In Proc. ISSAC 2018. ACM, 11–16. doi:10.13140/RG.2.2.32377.16485/1

[17] Zak Tonks. 2020. A Poly-algorithmic Quantifier Elimination Package in Maple. In Proc. MC 2019, Jürgen Gerhard and Ilias Kotsireas (Eds.). Springer, 171–186. doi:10.1007/978-3-030-41258-6_13

[18] Zak Tonks. 2021. Poly-algorithmic Techniques in Real Quantifier Elimination. Doctoral Thesis. University of Bath, UK. https://researchportal.bath.ac.uk/en/studentThesis/poly-algorithmic-techniques-in-real-quantifier-elimination

[19] J.H. van Lint and R.M. Wilson. 2012. A Course in Combinatorics (2nd ed.). Cambridge University Press. doi:10.1017/CBO9780511987045

[20] Volker Weispfenning. 1994. Quantifier Elimination for Real Algebra—the Cubic Case. In Proc. ISSAC 94. ACM Press, New York, 258–263. doi:10.1145/190347. 190425

[21] Volker Weispfenning. 1997. Quantifier Elimination for Real Algebra—the Quadratic Case and Beyond. Appl. Algebr. Eng. Comm. 8, 2 (Feb. 1997), 85–101. doi:10.1007/s002000050055