Computability of finding roots in holomorphic functions. - MathOverflow

Computability of finding roots in holomorphic functions.

2012-07-31T15:54:56Z

Consider a holomorphic function $f: S \to \mathbb{C}$ where $S$ is a path connected open subset of $\mathbb{C}$ (not necessarily simply connected). Is it then possible to determine if $f$ contains a zero?.

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:

Consider all holomorphic functions $f: S \to \mathbb{C}$ where $S$ is a path connected open subset of $\mathbb{C}$ , with an associated analytic function $\tau_f: \mathbb{R} \to S$ . Then no algorithm exists that for every $f$ can determine if $f\circ \tau_f$ contains any zeroes.

EDIT: We are only considering functions that are computable at every point inside their domain.

Answer by Robert Israel for Computability of finding roots in holomorphic functions.

2012-07-31T18:34:27Z

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.

Answer by Igor Rivin for Computability of finding roots in holomorphic functions.

2012-07-31T20:13:10Z

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.