Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn algorithm to determine regular singular Mahler systems
86
0
0.0
(
0
)
Added by
Marina Poulet
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Colin Faverjon
Ask ChatGPT about the research
No Arabic abstract
This paper is devoted to the study of the analytic properties of Mahler systems at 0. We give an effective characterisation of Mahler systems that are regular singular at 0, that is, systems which are equivalent to constant ones. Similar characterisations already exist for differential and (q-)difference systems but they do not apply in the Mahler case. This work fill in the gap by giving an algorithm which decides whether or not a Mahler system is regular singular at 0.
rate research
Read More
This paper is concerned with certifying that a given point is near an exact root of an overdetermined or singular polynomial system with rational coefficients. The difficulty lies in the fact that consistency of overdetermined systems is not a continuous property. Our certification is based on hybrid symbolic-numeric methods to compute the exact rational univariate representation (RUR) of a component of the input system from approximate roots. For overdetermined polynomial systems with simple roots, we compute an initial RUR from approximate roots. The accuracy of the RUR is increased via Newton iterations until the exact RUR is found, which we certify using exact arithmetic. Since the RUR is well-constrained, we can use it to certify the given approximate roots using alpha-theory. To certify isolated singular roots, we use a determinantal form of the isosingular deflation, which adds new polynomials to the original system without introducing new variables. The resulting polynomial system is overdetermined, but the roots are now simple, thereby reducing the problem to the overdetermined case. We prove that our algorithms have complexity that are polynomial in the input plus the output size upon successful convergence, and we use worst case upper bounds for termination when our iteration does not converge to an exact RUR. Examples are included to demonstrate the approach.
Mahler equations relate evaluations of the same function $f$ at iterated $b$th powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. In this work, we present algorithms for solving linear Mahler equations for series, polynomials, and rational functions, and get polynomial-time complexity under a mild assumption. Incidentally, we develop an algorithm for computing the gcrd of a family of linear Mahler operators.
The difference Galois theory of Mahler equations is an active research area. The present paper aims at developing the analytic aspects of this theory. We first attach a pair of connection matrices to any regular singular Mahler equation. We then show that these connection matrices can be used to produce a Zariski-dense subgroup of the difference Galois group of any regular singular Mahler equation.
Quantifier elimination over the reals is a central problem in computational real algebraic geometry, polynomial system solving and symbolic computation. Given a semi-algebraic formula (whose atoms are polynomial constraints) with quantifiers on some variables, it consists in computing a logically equivalent formula involving only unquantified variables. When there is no alternation of quantifiers, one has a one block quantifier elimination problem. This paper studies a variant of the one block quantifier elimination in which we compute an almost equivalent formula of the input. We design a new probabilistic efficient algorithm for solving this variant when the input is a system of polynomial equations satisfying some regularity assumptions. When the input is generic, involves $s$ polynomials of degree bounded by $D$ with $n$ quantified variables and $t$ unquantified ones, we prove that this algorithm outputs semi-algebraic formulas of degree bounded by $mathcal{D}$ using $O {widetilde{~}}left ((n-s+1) 8^{t} mathcal{D}^{3t+2} binom{t+mathcal{D}}{t} right )$ arithmetic operations in the ground field where $mathcal{D} = 2(n+s) D^s(D-1)^{n-s+1} binom{n}{s}$. In practice, it allows us to solve quantifier elimination problems which are out of reach of the state-of-the-art (up to $8$ variables).
We show that the Mahler measure of every Borwein polynomial -- a polynomial with coefficients in $ {-1,0,1 }$ having non-zero constant term -- can be expressed as a maximal Lyapunov exponent of a matrix cocycle that arises in the spectral theory of binary constant-length substitutions. In this way, Lehmers problem for height-one polynomials having minimal Mahler measure becomes equivalent to a natural question from the spectral theory of binary constant-length substitutions. This supports another connection between Mahler measures and dynamics, beyond the well-known appearance of Mahler measures as entropies in algebraic dynamics.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
