Computability of finding roots in holomorphic functions. - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T08:13:21Z http://mathoverflow.net/feeds/question/103622 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103622/computability-of-finding-roots-in-holomorphic-functions Computability of finding roots in holomorphic functions. poizan42 2012-07-31T15:54:56Z 2012-07-31T20:13:10Z <p>Consider a holomorphic function <code>$f: S \to \mathbb{C}$</code> where $S$ is a path connected open subset of <code>$\mathbb{C}$</code> (not necessarily simply connected). Is it then possible to determine if $f$ contains a zero?.</p> <p>I would suspect that the answer is that it is not possible in general, but has this ever been proven? From Matiyasevich's theorem I have been able to prove this (weaker?) result:</p> <p>Consider all holomorphic functions <code>$f: S \to \mathbb{C}$</code> where $S$ is a path connected open subset of <code>$\mathbb{C}$</code>, with an associated analytic function <code>$\tau_f: \mathbb{R} \to S$</code>. Then no algorithm exists that for every $f$ can determine if <code>$f\circ \tau_f$</code> contains any zeroes.</p> <p>EDIT: We are only considering functions that are computable at every point inside their domain.</p> http://mathoverflow.net/questions/103622/computability-of-finding-roots-in-holomorphic-functions/103627#103627 Answer by Robert Israel for Computability of finding roots in holomorphic functions. Robert Israel 2012-07-31T18:34:27Z 2012-07-31T18:34:27Z <p>For example, let $S$ be the open unit disk and $f(z) = -1/2 + \sum_{j \in A} z^j$ where $A$ is some subset of $\mathbb N$. Then $f$ has a zero if and only if $A$ is nonempty. $A$ could be, say, the set of $n$ such that a given Turing machine with a given input halts in time $\le n$, and there is no algorithm to determine whether $A$ is nonempty. </p> http://mathoverflow.net/questions/103622/computability-of-finding-roots-in-holomorphic-functions/103631#103631 Answer by Igor Rivin for Computability of finding roots in holomorphic functions. Igor Rivin 2012-07-31T20:13:10Z 2012-07-31T20:13:10Z <p>If you can compute the function to arbitrary precision, and are given the domain in some computable way, presumably you can decompose the domain into simply connected pieces, and then note that the argument principle reduces your question to an integration problem.</p>