MODNET
Research Training Network in Model Theory
Publications > Preprint server > Preprint Number 1779

Preprint Number 1779

Previous Next Preprint server


1779. Wei Li, Alexey Ovchinnikov, Gleb Pogudin, and Thomas Scanlon
Algorithms yield upper bounds in differential algebra
E-mail:

Submission date: 22 April 2020

Abstract:

Consider an algorithm computing in a differential field with several commuting derivations such that the only operations it performs with the elements of the field are arithmetic operations, differentiation, and zero testing. We show that, if the algorithm is guaranteed to terminate on every input, then there is a computable upper bound for the size of the output of the algorithm in terms of the input. We also generalize this to algorithms working with models of good enough theories (including for example, difference fields).
We then apply this to differential algebraic geometry to show that there exists a computable uniform upper bound for the number of components of any variety defined by a system of polynomial PDEs. We then use this bound to show the existence of a computable uniform upper bound for the elimination problem in systems of polynomial PDEs with delays.

Mathematics Subject Classification: 12H05, 12H10, 03C10, 03C60, 03D15

Keywords and phrases:

Full text arXiv 2005.01608: pdf, ps.


Last updated: March 23 2021 10:21 Please send your corrections to: