# Computability of finding roots in holomorphic functions.

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.

• How are you given $f$ and $S$? – Qiaochu Yuan Jul 31 '12 at 16:00

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.

• Thank you, but not really what I was looking for. The fact that some properties about non-computable functions are non-computable isn't really that interesting. – poizan42 Jul 31 '12 at 19:54
• But $f(z)$ is just as computable as $\sin(z)$ is, i.e. each coefficient of the series is computable, and you have uniform convergence on compact subsets of $S$ with provable bounds. – Robert Israel Jul 31 '12 at 20:23
• Oh, you're right. I didn't read it right the first time. Thank you. – poizan42 Jul 31 '12 at 21:26
• I am afraid this does not make much sense. With your argument, you could also claim that whether a Boolean function $f:\lbrace 0,1\rbrace\to\lbrace 0,1\rbrace$ has a $0$ is undecidable. Indeed, you could consider the function $f(z)=\bigwedge_{j\in A}z$, where $A$ is a subset of $\mathbb{N}$. Then, $f$ has a zero if and only if $A$ is non-empty. – Algernon Aug 1 '12 at 8:20
• The difference is that my $f$ is computable: for any computable $z$ in the open unit disk and $\epsilon > 0$, you can compute an approximation of $f(z)$ within accuracy $\epsilon$ by using the terms of the series up to $z^N$ where $N > \log(\epsilon(1-|z|))/\log (|z|))$ – Robert Israel Aug 1 '12 at 19:14

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.

• You can count the zeros inside a contour, but you can't rule out the existence of zeros that are outside all the contours you have tried yet. See my example on the unit disk, where if there are zeros they are very close to the unit circle. – Robert Israel Jul 31 '12 at 20:27
• @Robert well, yes and no. If there is a zero, this method will find it in finite time. If there is no zero, as you say, we may have to wait forever. Since I am not sure what the OP actually wants, I am not sure which of our answers is the one that makes him/her happier. – Igor Rivin Jul 31 '12 at 21:25
• By "Is it then possible to determine if $f$ contains a zero?." I meant if the problem is decideable. – poizan42 Jul 31 '12 at 21:37