Elimination of unknowns for systems of algebraic differential-difference equations

Li Wei; Ovchinnikov Alexey; Pogudin Gleb; Scanlon Thomas

Working paper

Elimination of unknowns for systems of algebraic differential-difference equations

Working papers by Cornell University. Cornell University, 2018

Li W., Ovchinnikov A., Pogudin G., Scanlon T.

We establish effective elimination theorems for differential-difference equations. Specifically, we find a computable function B(r,s) of the natural number parameters r and s so that for any system of algebraic differential-difference equations in the variables x=x1,…,xq and y=y1,…,yr each of which has order and degree in y bounded by s over a differential-difference field, there is a non-trivial consequence of this system involving just the x variables if and only if such a consequence may be constructed algebraically by applying no more than B(r,s) iterations of the basic difference and derivation operators to the equations in the system. We relate this finiteness theorem to the problem of finding solutions to such systems of differential-difference equations in rings of functions showing that a system of differential-difference equations over C is algebraically consistent if and only if it has solutions in a certain ring of germs of meromorphic functions.

Research target: Computer Science Mathematics

Priority areas: IT and mathematics

Language: English

Text on another site

Keywords: elimination theory delayed equation

Effective difference elimination and Nullstellensatz

Ovchinnikov A., Pogudin G., Scanlon T. Journal of the European Mathematical Society. 2019.

We prove effective Nullstellensatz and elimination theorems for difference equations in sequence rings. More precisely, we compute an explicit function of geometric quantities associated to a system of difference equations (and these geometric quantities may themselves be bounded by a function of the number of variables, the order of the equations, and the degrees of the equations) so that for any system of difference equations in variables x=(x_1,…,x_m) and u=(u_1,…,u_r), if these equations have any nontrivial consequences in the x variables, then such a consequence may be seen algebraically considering transforms up to the order of our bound. Specializing to the case of m=0, we obtain an effective method to test whether a given system of difference equations is consistent.

Added: Nov 1, 2019

A resultant system as the set of coefficients of a single resultant

Abramov Y. V. Functional Analysis and Its Applications. 2013. Vol. 47. No. 3. P. 82-87.

Explicit expressions for polynomials forming a homogeneous resultant system of a set of m+1 homogeneous polynomial equations in n+1

Added: Nov 20, 2012

Bounds for elimination of unknowns in systems of differential-algebraic equations

Ovchinnikov A., Pogudin G., Vo T. Working papers by Cornell University. Cornell University, 2018

Elimination of unknowns in systems of equations, starting with Gaussian elimination, is a problem of general interest. The problem of finding an a priori upper bound for the number of differentiations in elimination of unknowns in a system of differential-algebraic equations (DAEs) is an important challenge, going back to Ritt (1932). The first characterization of this via an asymptotic analysis is due to Grigoriev's result (1989) on quantifier elimination in differential fields, but the challenge still remained. In this paper, we present a new bound, which is a major improvement over the previously known results. We also present a new lower bound, which shows asymptotic tightness of our upper bound in low dimensions, which are frequently occurring in applications. Finally, we discuss applications of our results to designing new algorithms for elimination of unknowns in systems of DAEs.

Added: Nov 1, 2019

Труды ХХ Международного совещания «Радиационная физика твердого тела» (Севастополь, 5 июля - 10 июля 2010 г.)

Edited by: Г. Г. Бондаренко Т. 1-2. М.: ФГБНУ "НИИ ПМТ", 2010.

Added: Apr 12, 2012

System of Resultants as a collection of coefficients of a unique Resultant

Abramov Y. V. arxiv.org. math. Cornell University, 2011. No. arXiv:1111.4974v1.

I give the explicit formula for the (set-theoretical) system of Resultants of m+1 homogeneous polynomials in n+1 variables

Added: Jun 28, 2012

Имплементация элементов с лапласовскими передаточными функциями в программу схемотехнического моделирования

Ulyanov S., Gourary M. M., Rusakov S. G. et al. Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2017. No. 1. P. 39-45.

The paper presents an approach to the implementation of multiport linear dynamical blocks in a circuit simulator. Block characteristics are supposed to be presented in the form of rational transfer functions. The approach is based on the state space method, which allows avoiding problems of numerical convolution. The extension of the approach to the case of the exponential-rational form of transfer function is taken into account. The MNA formulation of Laplace element model is presented. The methodology providing construction of arbitrary multi-port Laplace elements on the base of developed set of simple Laplace elements is proposed. The approach was implemented in SPICE3 circuit simulator. Examples are given in the paper.

Added: Feb 19, 2018

Труды ХХI Международного совещания «Радиационная физика твердого тела» (Севастополь, 22-27 августа 2011 г.)

Бондаренко Г. Г. Т. 1-2. М.: ФГБНУ "НИИ ПМТ", 2011.

Added: Apr 12, 2012

О топологической устойчивости непрерывных функций в некоторых пространствах, связанных с рядами Фурье

В. В. Лебедев Известия РАН. Серия математическая. 2010. Т. 74. № 2. С. 131-164.

We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.

Added: Apr 12, 2012

Оценки в теоремах типа теоремы Берлинга-Хелсона. Многомерный случай

В. В. Лебедев Математические заметки. 2011. Т. 90. № 3. С. 394-407.

We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.

Added: Apr 12, 2012

Short lists with short programs in short time

Bauwens B., Makhlin A., Vereshchagin N. et al. Electronic Colloquium on Computational Complexity. Technical report. Hasso-Plattner-Institut, 2013. No. TR13-007.

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on input $x$ a list of polynomial size guaranteed to contain a $O(\log |x|)$-short program for $x$. We also show that there exist computable functions that map every $x$ to a list of size $O(|x|^2)$ containing a $O(1)$-short program for $x$ and this is essentially optimal because we prove that such a list must have size $\Omega(|x|^2)$. Finally we show that for some machines, computable lists containing a shortest program must have length $\Omega(2^{|x|})$.

Added: Dec 14, 2013

Laminations from the Main Cubioid

Timorin V., Blokh A., Oversteegen L. et al. arxiv.org. math. Cornell University, 2013. No. 1305.5788.

According to a recent paper \cite{bopt13}, polynomials from the closure $\ol{\phd}_3$ of the {\em Principal Hyperbolic Domain} ${\rm PHD}_3$ of the cubic connectedness locus have a few specific properties. The family $\cu$ of all polynomials with these properties is called the \emph{Main Cubioid}. In this paper we describe the set $\cu^c$ of laminations which can be associated to polynomials from $\cu$.

Added: Oct 6, 2013

Количественные оценки в теоремах типа теоремы Берлинга-Хелсона

В. В. Лебедев Математический сборник. 2010. Т. 201. № 12. С. 103-130.

We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.

Added: Apr 12, 2012

Введение в математическую статистику

Ивченко Г. И., Медведев Ю. И. М.: ЛКИ, 2010.

Added: Apr 12, 2012

Bounded limit cycles of polynomial foliations of ℂP²

Goncharuk N. B., Kudryashov Y. arxiv.org. math. Cornell University, 2015. No. 1504.03313.

In this article we prove in a new way that a generic polynomial vector field in ℂ² possesses countably many homologically independent limit cycles. The new proof needs no estimates on integrals, provides thinner exceptional set for quadratic vector fields, and provides limit cycles that stay in a bounded domain.

Added: Apr 15, 2015

Разложения решений пятого уравнения Пенлеве вблизи его неособой точки

Брюно А. Д., Парусникова А. В. Институт прикладной математики им. М.В. Келдыша Российской академии наук, 2011. № 18.

Added: Apr 18, 2012

Многовариантный анализ процессов прокатки на базе компьютерного моделирования

Аксенов С. А., Чумаченко Е. Н., Сырчина О. О. Вестник Воронежского государственного технического университета. 2011. Т. 7. № 11.2. С. 62-64.

Added: Apr 12, 2012

Автоматическая обработка текстов на естественном языке и компьютерная лингвистика

Большакова Е. И., Клышинский Э. С., Ландэ Д. В. и др. М.: Московский государственный институт электроники и математики, 2011.

Added: Apr 12, 2012

Асимптотические разложения решений пятого уравнения Пенлеве

Парусникова А. В., Брюно А. Д. Институт прикладной математики им. М.В. Келдыша Российской академии наук, 2010. № 39.

Added: Apr 18, 2012

Локальные разложения решений пятого уравнения Пенлеве

Брюно А. Д., Парусникова А. В. Институт прикладной математики им. М.В. Келдыша Российской академии наук, 2010. № 72.

Added: Apr 18, 2012

Применение информационных и космических технологий в задачах о движении небесных объектов

Чумаченко Е. Н., Кулагин В. П., Назиров Р. Р. и др. Информатизация образования и науки. 2011. № 3 (11). С. 178-187.

One of directions of activity of the scientifically-educational centre "SPACE" created by the Moscow state institute of electronics and mathematics (technical university) and Space research institute of the Russian Academy of Sciences is discussed. The general statements of problems connected with working out of models of movement of asteroids and comets taking into account not gravitational indignations and construction of models for measurement of trajectories are considered. On a space vehicle orbit in a vicinity of libration’s points the traffic control model is discussed with application of a solar sail with operated reflective characteristics.

Added: Apr 12, 2012

Анализ методов компьютерного моделирования механических испытаний

Чумаченко Е. Н., Аксенов С. А., Борхсениус С. С. Вестник Воронежского государственного технического университета. 2011. Т. 7. № 11.2. С. 9-11.

Added: Apr 12, 2012