An official website of the United States government
Abstract Recently we constructed Mahler discrete residues for rational functions and showed they comprise a complete obstruction to the Mahler summability problem of deciding whether a given rational function $f(x)$ is of the form $$g(x^{p})-g(x)$$ for some rational function $g(x)$ and an integer $p> 1$. Here we develop a notion of $$\lambda $$-twisted Mahler discrete residues for $$\lambda \in \mathbb{Z}$$, and show that they similarly comprise a complete obstruction to the twisted Mahler summability problem of deciding whether a given rational function $f(x)$ is of the form $$p^{\lambda } g(x^{p})-g(x)$$ for some rational function $g(x)$ and an integer $p>1$. We provide some initial applications of twisted Mahler discrete residues to differential creative telescoping problems for Mahler functions and to the differential Galois theory of linear Mahler equations.
more »
« less
Computing discrete residues of rational functions
In 2012 Chen and Singer introduced the notion of discrete residues for rational functions as a complete obstruction to rational summability. More explicitly, for a given rational function f(x), there exists a rational function g(x) such that f(x) = g(x+1) - g(x) if and only if every discrete residue of f(x) is zero. Discrete residues have many important further applications beyond summability: to creative telescoping problems, thence to the determination of (differential-)algebraic relations among hypergeometric sequences, and subsequently to the computation of (differential) Galois groups of difference equations. However, the discrete residues of a rational function are defined in terms of its complete partial fraction decomposition, which makes their direct computation impractical due to the high complexity of completely factoring arbitrary denominator polynomials into linear factors. We develop a factorization-free algorithm to compute discrete residues of rational functions, relying only on gcd computations and linear algebra.
more »
« less
- Award ID(s):
- 1815108
- PAR ID:
- 10523740
- Publisher / Repository:
- ACM
- Date Published:
- ISBN:
- 9798400706967
- Page Range / eLocation ID:
- 65 to 73
- Subject(s) / Keyword(s):
- discrete residues creative telescoping rational summability difference Galois theory factorization-free algorithm
- Format(s):
- Medium: X
- Location:
- Raleigh NC USA
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Understanding the algorithmic behaviors that are in principle realizable in a chemical system is necessary for a rigorous understanding of the design principles of biological regulatory networks. Further, advances in synthetic biology herald the time when we will be able to rationally engineer complex chemical systems and when idealized formal models will become blueprints for engineering. Coupled chemical interactions in a well-mixed solution are commonly formalized as chemical reaction networks (CRNs). However, despite the widespread use of CRNs in the natural sciences, the range of computational behaviors exhibited by CRNs is not well understood. Here, we study the following problem: What functions f : ℝ k → ℝ can be computed by a CRN, in which the CRN eventually produces the correct amount of the “output” molecule, no matter the rate at which reactions proceed? This captures a previously unexplored but very natural class of computations: For example, the reaction X 1 + X 2 → Y can be thought to compute the function y = min ( x 1 , x 2 ). Such a CRN is robust in the sense that it is correct whether its evolution is governed by the standard model of mass-action kinetics, alternatives such as Hill-function or Michaelis-Menten kinetics, or other arbitrary models of chemistry that respect the (fundamentally digital) stoichiometric constraints (what are the reactants and products?). We develop a reachability relation based on a broad notion of “what could happen” if reaction rates can vary arbitrarily over time. Using reachability, we define stable computation analogously to probability 1 computation in distributed computing and connect it with a seemingly stronger notion of rate-independent computation based on convergence in the limit t → ∞ under a wide class of generalized rate laws. Besides the direct mapping of a concentration to a nonnegative analog value, we also consider the “dual-rail representation” that can represent negative values as the difference of two concentrations and allows the composition of CRN modules. We prove that a function is rate-independently computable if and only if it is piecewise linear (with rational coefficients) and continuous (dual-rail representation), or non-negative with discontinuities occurring only when some inputs switch from zero to positive (direct representation). The many contexts where continuous piecewise linear functions are powerful targets for implementation, combined with the systematic construction we develop for computing these functions, demonstrate the potential of rate-independent chemical computation.more » « less
-
Abstract This paper solves the rational noncommutative analogue of Hilbert’s 17th problem: if a noncommutative rational function is positive semidefinite on all tuples of Hermitian matrices in its domain, then it is a sum of Hermitian squares of noncommutative rational functions. This result is a generalisation and culmination of earlier positivity certificates for noncommutative polynomials or rational functions without Hermitian singularities. More generally, a rational Positivstellensatz for free spectrahedra is given: a noncommutative rational function is positive semidefinite or undefined at every matricial solution of a linear matrix inequality $$L\succeq 0$$ if and only if it belongs to the rational quadratic module generated by L . The essential intermediate step toward this Positivstellensatz for functions with singularities is an extension theorem for invertible evaluations of linear matrix pencils.more » « less
-
Jury and Martin establish an analogue of the classical inner-outer factorization of Hardy space functions. They show that every function in a Hilbert function space with a normalized complete Pick reproducing kernel has a factorization of the type , where is cyclic, is a contractive multiplier, and . In this paper we show that if the cyclic factor is assumed to be what we call free outer, then the factors are essentially unique, and we give a characterization of the factors that is intrinsic to the space. That lets us compute examples. We also provide several applications of this factorization.more » « less
-
Lump solutions are analytical rational function solutions localized in all directions in space. We analyze a class of lump solutions, generated from quadratic functions, to nonlinear partial differential equations. The basis of success is the Hirota bilinear formulation and the primary object is the class of positive multivariate quadratic functions. A complete determination of quadratic functions positive in space and time is given, and positive quadratic functions are characterized as sums of squares of linear functions. Necessary and sufficient conditions for positive quadratic functions to solve Hirota bilinear equations are presented, and such polynomial solutions yield lump solutions to nonlinear partial differential equations under the dependent variable logarithmic derivative transformations. Applications are made for a few generalized KP and BKP equations.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3666000.3669676
