2
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ How are you given $f$ and $S$? $\endgroup$ Jul 31, 2012 at 16:00

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – poizan42
    Jul 31, 2012 at 19:54
  • 4
    $\begingroup$ 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. $\endgroup$ Jul 31, 2012 at 20:23
  • $\begingroup$ Oh, you're right. I didn't read it right the first time. Thank you. $\endgroup$
    – poizan42
    Jul 31, 2012 at 21:26
  • $\begingroup$ 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. $\endgroup$
    – Algernon
    Aug 1, 2012 at 8:20
  • 1
    $\begingroup$ 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|))$ $\endgroup$ Aug 1, 2012 at 19:14
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jul 31, 2012 at 20:27
  • $\begingroup$ @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. $\endgroup$
    – Igor Rivin
    Jul 31, 2012 at 21:25
  • $\begingroup$ By "Is it then possible to determine if $f$ contains a zero?." I meant if the problem is decideable. $\endgroup$
    – poizan42
    Jul 31, 2012 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.