
The concept of open weak CAD is introduced. Every open CAD is an open weak
CAD. On the contrary, an open weak CAD is not necessarily an open CAD. An
algorithm for computing projection polynomials of open weak CADs is proposed.
The key idea is to compute the intersection of projection factor sets produced
by different projection orders. The resulting open weak CAD often has smaller
number of sample points than open CADs. The algorithm can be used for computing
sample points for all open connected components of $ f\neq0$ for a given
polynomial $f$. It can also be used for many other applications, such as
testing semidefiniteness of polynomials and copositive problems. In fact, we
solved several difficult semidefiniteness problems efficiently by using the
algorithm. Furthermore, applying the algorithm to copositive problems, we find
an explicit expression of the polynomials producing open weak CADs under some
conditions, which significantly improves the efficiency of solving copositive
problems.

We present a novel algorithm for deciding whether a given planar curve is an
image of a given spatial curve, obtained by a central or a parallel projection
with unknown parameters. The motivation comes from the problem of establishing
a correspondence between an object and an image, taken by a camera with unknown
position and parameters. A straightforward approach to this problem consists of
setting up a system of conditions on the projection parameters and then
checking whether or not this system has a solution. The computational advantage
of the algorithm presented here, in comparison to algorithms based on the
straightforward approach, lies in a significant reduction of a number of real
parameters that need to be eliminated in order to establish existence or
nonexistence of a projection that maps a given spatial curve to a given planar
curve. Our algorithm is based on projection criteria that reduce the projection
problem to a certain modification of the equivalence problem of planar curves
under affine and projective transformations. To solve the latter problem we
make an algebraic adaptation of signature construction that has been used to
solve the equivalence problems for smooth curves. We introduce a notion of a
classifying set of rational differential invariants and produce explicit
formulas for such invariants for the actions of the projective and the affine
groups on the plane.

We consider systems of strict multivariate polynomial inequalities over the
reals. All polynomial coefficients are parameters ranging over the reals, where
for each coefficient we prescribe its sign. We are interested in the existence
of positive real solutions of our system for all choices of coefficients
subject to our sign conditions. We give a decision procedure for the existence
of such solutions. In the positive case our procedure yields a parametric
positive solution as a rational function in the coefficients. Our framework
allows to reformulate heuristic subtropical approaches for nonparametric
systems of polynomial inequalities that have been recently used in qualitative
biological network analysis and, independently, in satisfiability modulo theory
solving. We apply our results to characterize the incompleteness of those
methods.

Many realworld processes and phenomena are modeled using systems of ordinary
differential equations with parameters. Given such a system, we say that a
parameter is globally identifiable if it can be uniquely recovered from input
and output data. The main contribution of this paper is to provide theory, an
algorithm, and software for deciding global identifiability. First, we
rigorously derive an algebraic criterion for global identifiability (this is an
analytic property), which yields a deterministic algorithm. Second, we improve
the efficiency by randomizing the algorithm while guaranteeing probability of
correctness. With our new algorithm, we can tackle problems that could not be
tackled before.

A $\mathit{\text{moving frame}}$ at a rational curve is a basis of vectors
moving along the curve. When the rational curve is given parametrically by a
row vector $\mathbf{a}$ of univariate polynomials, a moving frame with
important algebraic properties can be defined by the columns of an invertible
polynomial matrix $P$, such that $\mathbf{a} P=[\gcd(\mathbf{a}),0\ldots,0]$. A
$\mathit{\text{degreeoptimal moving frame}}$ has columnwise minimal degree,
where the degree of a column is defined to be the maximum of the degrees of its
components. Algebraic moving frames are closely related to the univariate
versions of the celebrated QuillenSuslin problem, effective Nullstellensatz
problem, and syzygy module problem. However, this paper appears to be the first
devoted to finding an efficient algorithm for constructing a degreeoptimal
moving frame, a property desirable in various applications. We compare our
algorithm with other possible approaches, based on already available
algorithms, and show that it is more efficient. We also establish several new
theoretical results concerning the degrees of an optimal moving frame and its
components. In addition, we show that any deterministic algorithm for computing
a degreeoptimal algebraic moving frame can be augmented so that it assigns a
degreeoptimal moving frame in a $GL_n(\mathbb{K})$equivariant manner. This
crucial property of classical geometric moving frames, in combination with the
algebraic properties, can be exploited in various problems.

In this paper, we give an explicit expression for a certain family of ternary
cyclotomic polynomials: specifically $\Phi_{p_{1}p_{2}p_{3}}$, where
$p_{1}<p_{2}<p_{3}$ are odd primes such that $p_{2} \equiv1 \mod p_{1}$ and
$p_{3} \equiv1 \mod {p_{1}p_{2}}$. As an application of the explicit
expressions, we give an exact formula for the number of nonzero terms in the
polynomials in the family, which in turn immediately shows that the density
(number of nonzeros terms / degree) is roughly inversely proportional to
$p_{2}$, when $p_{1}$ is sufficiently large.

It is well known that for two univariate polynomials over complex number
field the number of their common roots is equal to the order of their
resultant. In this paper, we show that this fundamental relationship still
holds for the tropical polynomials under suitable adaptation of the notion of
order, if the roots are simple and nonzero.

The Kuramoto model describes synchronization behavior among coupled
oscillators and enjoys successful application in a wide variety of fields. Many
of these applications seek phasecoherent solutions, i.e., equilibria of the
model. Historically, research has focused on situations where the number of
oscillators, n, is extremely large and can be treated as being infinite. More
recently, however, applications have arisen in areas such as electrical
engineering with more modest values of n. For these, the equilibria can be
located by solving a system of polynomial equations utilizing techniques from
algebraic geometry. Typical methods for solving such systems locate all complex
solutions even though only the real solutions, corresponding to equilibria of
the model, are of physical interest. In this paper, we develop an algorithm to
locate only all equilibria of the model, thereby shortening computation time by
several orders of magnitude in certain situations. This is accomplished by
choosing specific equilibria representatives and the consequent algebraic
decoupling of the system. We compare this solving approach to other
computational algebraic geometric methods. Furthermore, analyzing this approach
allows us to prove, asymptotically, that the maximum number of equilibria grows
at the same rate as the number of complex solutions of a corresponding
polynomial system. Finally, we conjecture an upper bound on the maximum number
of equilibria for any number of oscillators which generalizes the known cases
and is obtained on a range of explicitly provided natural frequencies.

In this paper, we list several interesting structures of cyclotomic
polynomials: specifically relations among blocks obtained by suitable partition
of cyclotomic polynomials.
We present explicit and selfcontained proof for all of them, using a uniform
terminology and technique.

We present a new algorithm for computing a $\mu$basis of the syzygy module
of $n$ polynomials in one variable over an arbitrary field $\mathbb{K}$. The
algorithm is conceptually different from the previouslydeveloped algorithms by
Cox, Sederberg, Chen, Zheng, and Wang for $n=3$, and by Song and Goldman for an
arbitrary $n$. It involves computing a "partial" reduced rowechelon form of a
$ (2d+1)\times n(d+1)$ matrix over $\mathbb{K}$, where $d$ is the maximum
degree of the input polynomials. The proof of the algorithm is based on
standard linear algebra and is completely selfcontained. It includes a proof
of the existence of the $\mu$basis and as a consequence provides an
alternative proof of the freeness of the syzygy module. The theoretical (worst
case asymptotic) computational complexity of the algorithm is
$O(d^2n+d^3+n^2)$. We have implemented this algorithm (HHK) and the one
developed by Song and Goldman (SG). Experiments on random inputs indicate that
SG gets faster than HHK when $d$ gets sufficiently large for a fixed $n$, and
that HHK gets faster than SG when $n$ gets sufficiently large for a fixed $d$.

The maximum gap $g(f)$ of a polynomial $f$ is the maximum of the differences
(gaps) between two consecutive exponents that appear in $f$. Let $\Phi_{n}$ and
$\Psi_{n}$ denote the $n$th cyclotomic and $n$th inverse cyclotomic
polynomial, respectively. In this paper, we give several lower bounds for
$g(\Phi_{n})$ and $g(\Psi_{n})$, where $n$ is the product of odd primes. We
observe that they are very often exact. We also give an exact expression for
$g(\Psi_{n})$ under a certain condition. Finally we conjecture an exact
expression for $g(\Phi_{n})$ under a certain condition.

We provide an algorithm for computing semiFourier sequences for expressions
constructed from arithmetic operations, exponentiations and integrations. The
semiFourier sequence is a relaxed version of Fourier sequence for polynomials
(expressions made of additions and multiplications).

The resultant plays a crucial role in (computational) algebra and algebraic
geometry. One of the most important and well known properties of the resultant
is that it is equal to the determinant of the Sylvester matrix. In 2008,
Odagiri proved that a similar property holds over the tropical semiring if one
replaces subtraction with addition. The tropical semiring belongs to a large
family of algebraic structures called commutative idempotent semiring. In this
paper, we prove that the same property (with subtraction replaced with
addition) holds over an \emph{arbitrary\/} commutative idempotent semiring.

In 1990 Lazard proposed an improved projection operation for cylindrical
algebraic decomposition (CAD). For the proof he introduced a certain notion of
valuation of a multivariate Puiseux series at a point. However a gap in one of
the key supporting results for the improved projection was subsequently
noticed. In this report we study a more limited but rigorous concept of
Lazard's valuation: namely, we study Lazard's valuation of a multivariate
polynomial at a point. We prove some basic properties of the limited Lazard
valuation and identify some relationships between valuationinvariance and
orderinvariance.

In this paper, we introduce an algebraic method to construct stable and
consistent univariate autoregressive (AR) models of low order for filtering and
predicting nonlinear turbulent signals with memory depth. By stable, we refer
to the classical stability condition for the AR model. By consistent, we refer
to the classical consistency constraints of AdamsBashforth methods of
ordertwo. One attractive feature of this algebraic method is that the model
parameters can be obtained without directly knowing any training data set as
opposed to many standard, regressionbased parameterization methods. It takes
only longtime average statistics as inputs. The proposed method provides a
discretization time step interval which guarantees the existence of stable and
consistent AR model and simultaneously produces the parameters for the AR
models. In our numerical examples with two chaotic time series with different
characteristics of decaying time scales, we find that the proposed AR models
produce significantly more accurate shortterm predictive skill and comparable
filtering skill relative to the linear regressionbased AR models. These
encouraging results are robust across wide ranges of discretization times,
observation times, and observation noise variances. Finally, we also find that
the proposed model produces an improved shorttime prediction relative to the
linear regressionbased ARmodels in forecasting a data set that characterizes
the variability of the MaddenJulian Oscillation, a dominant tropical
atmospheric wave pattern.

Consider the problem: given a real number $x$ and an error bound $\epsilon$,
find an interval such that it contains the $\sqrt[n]{x}$ and its width is less
than $\epsilon$. One way to solve the problem is to start with an initial
interval and to repeatedly update it by applying an interval refinement map on
it until it becomes narrow enough. In this paper, we prove that the well known
SecantNewton map is optimal among a certain family of natural generalizations.

We consider the problem of counting (stable) equilibriums of an important
family of algebraic differential equations modeling multistable biological
regulatory systems. The problem can be solved, in principle, using real
quantifier elimination algorithms, in particular real root classification
algorithms. However, it is well known that they can handle only very small
cases due to the enormous computing time requirements. In this paper, we
present a special algorithm which is much more efficient than the general
methods. Its efficiency comes from the exploitation of certain interesting
structures of the family of differential equations.

Let $g(f)$ denote the maximum of the differences (gaps) between two
consecutive exponents occurring in a polynomial $f$. Let $\Phi_n$ denote the
$n$th cyclotomic polynomial and let $\Psi_n$ denote the $n$th inverse
cyclotomic polynomial. In this note, we study $g(\Phi_n)$ and $g(\Psi_n)$ where
$n$ is a product of odd primes, say $p_1 < p_2 < p_3$, etc. It is trivial to
determine $g(\Phi_{p_1})$, $g(\Psi_{p_1})$ and $g(\Psi_{p_1p_2})$. Hence the
simplest nontrivial cases are $g(\Phi_{p_1p_2})$ and $g(\Psi_{p_1p_2p_3})$. We
provide an exact expression for $g(\Phi_{p_1p_2}).$ We also provide an exact
expression for
$g(\Psi_{p_1p_2p_3})$ under a mild condition. The condition is almost always
satisfied (only finite exceptions for each $p_1$). We also provide a lower
bound and an upper bound for $g(\Psi_{p_1p_2p_3})$.

In 1853 Sylvester introduced a family of double sum expressions for two
finite sets of indeterminates and showed that some members of the family are
essentially the polynomial subresultants of the monic polynomials associated
with these sets. A question naturally arises: What are the other members of the
family? This paper provides a complete answer to this question. The technique
that we developed to answer the question turns out to be general enough to
charactise all members of the family, providing a uniform method.

In 1853 Sylvester stated and proved an elegant formula that expresses the
polynomial subresultants in terms of the roots of the input polynomials.
Sylvester's formula was also recently proved by Lascoux and Pragacz by using
multiSchur functions and divided differences. In this paper, we provide an
elementary proof that uses only basic properties of matrix multiplication and
Vandermonde determinants.