Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDesingularization Explains Order-Degree Curves for Ore Operators
393
0
0.0
(
0
)
Added by
Manuel Kauers
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Desingularization is the problem of finding a left multiple of a given Ore operator in which some factor of the leading coefficient of the original operator is removed. An order-degree curve for a given Ore operator is a curve in the $(r,d)$-plane such that for all points $(r,d)$ above this curve, there exists a left multiple of order $r$ and degree $d$ of the given operator. We give a new proof of a desingularization result by Abramov and van Hoeij for the shift case, and show how desingularization implies order-degree curves which are extremely accurate in examples.
rate research
Read More
It is well known that for a first order system of linear difference equations with rational function coefficients, a solution that is holomorphic in some left half plane can be analytically continued to a meromorphic solution in the whole complex plane. The poles stem from the singularities of the rational function coefficients of the system. Just as for differential equations, not all of these singularities necessarily lead to poles in solutions, as they might be what is called removable. In our work, we show how to detect and remove these singularities and further study the connection between poles of solutions and removable singularities. We describe two algorithms to (partially) desingularize a given difference system and present a characterization of removable singularities in terms of shifts of the original system.
Polynomial remainder sequences contain the intermediate results of the Euclidean algorithm when applied to (non-)commutative polynomials. The running time of the algorithm is dependent on the size of the coefficients of the remainders. Different ways have been studied to make these as small as possible. The subresultant sequence of two polynomials is a polynomial remainder sequence in which the size of the coefficients is optimal in the generic case, but when taking the input from applications, the coefficients are often larger than necessary. We generalize two improvements of the subresultant sequence to Ore polynomials and derive a new bound for the minimal coefficient size. Our approach also yields a new proof for the results in the commutative case, providing a new point of view on the origin of the extraneous factors of the coefficients.
We present a Sage implementation of Ore algebras. The main features for the most common instances include basic arithmetic and actions; gcrd and lclm; D-finite closure properties; natural transformations between related algebras; guessing; desingularization; solvers for polynomials, rational functions and (generalized) power series. This paper is a tutorial on how to use the package.
Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~$G$ begin in one of two states, dormant or active. Given a fixed integer $r$, a dormant vertex becomes active if at any stage it has at least $r$ active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices $A$, we say that $G$ $r$-percolates (from $A$) if every vertex in $G$ becomes active after some number of steps. Let $m(G,r)$ denote the minimum size of a set $A$ such that $G$ $r$-percolates from $A$. Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure $m(G,2)=2$. In particular, we give an Ore-type degree sum result that states that if a graph $G$ satisfies $sigma_2(G)ge n-2$, then either $m(G,2)=2$ or $G$ is in one of a small number of classes of exceptional graphs. We also give a Chv{a}tal-type degree condition: If $G$ is a graph with degree sequence $d_1le d_2ledotsle d_n$ such that $d_i geq i+1$ or $d_{n-i} geq n-i-1$ for all $1 leq i < frac{n}{2}$, then $m(G,2)=2$ or $G$ falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. Combin.]
In this paper, we present a new method for computing bounded-degree factors of lacunary multivariate polynomials. In particular for polynomials over number fields, we give a new algorithm that takes as input a multivariate polynomial f in lacunary representation and a degree bound d and computes the irreducible factors of degree at most d of f in time polynomial in the lacunary size of f and in d. Our algorithm, which is valid for any field of zero characteristic, is based on a new gap theorem that enables reducing the problem to several instances of (a) the univariate case and (b) low-degree multivariate factorization. The reduction algorithms we propose are elementary in that they only manipulate the exponent vectors of the input polynomial. The proof of correctness and the complexity bounds rely on the Newton polytope of the polynomial, where the underlying valued field consists of Puiseux series in a single variable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
