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.

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ How are you given $f$ and $S$? $\endgroup$
    – Qiaochu Yuan
    Commented Jul 31, 2012 at 16:00

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented 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$
    – Robert Israel
    Commented Jul 31, 2012 at 20:23
  • $\begingroup$ Oh, you're right. I didn't read it right the first time. Thank you. $\endgroup$
    – poizan42
    Commented 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
    Commented 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$
    – Robert Israel
    Commented 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.

Improve this answer
$\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$
    – Robert Israel
    Commented 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
    Commented 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
    Commented Jul 31, 2012 at 21:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .