11
$\begingroup$

We assume we are given an entire function $f: \mathbb C \to \mathbb C$ with $f(0)=1$ and $f'(0)=0$ and $f$ is real on the real axis.

We assume (as a fact about $f$, that we want to demonstrate computationally using other facts about $f$) that $f$ has a zero of order $2$ at some real $z_0 \in \mathbb R$ and that there is no other zero of $f$ inside the disc of radius $2\vert z_0 \vert$ apart from this one.

We assume we have access to the Taylor expansion of $f$ and any of its derivatives, i.e. we have access to coefficients $a_k(n)$

$$f^{(n)}(z) = \sum_{k=0}^N a_k(n) z^k + R_{N,n}(z),$$ where we also have a bound on $\lvert R_{N,n}(z)\rvert$ for any $z,N,n.$

The task is now: Given $\varepsilon>0$, is it possible to show with the help of a computer that there exists $z_0^* \in \mathbb R$ with $\lvert z_0^*-z_0 \rvert \le \varepsilon$ such that $f$ has a zero of order $2$ at $z_0^*$? Does there exist an algorithmic way for a computer to show this?

To see why the order $2$ is subtle here. If one wanted to show the existence of a zero of order $1$ instead, this would be trivial as it would suffice to show that $f$ changes sign and $f'$ is non-zero in a neighbourhood of where the sign change happens.

$\endgroup$
13
  • $\begingroup$ What does "changes sign" mean of a complex-valued function? Real or complex part, I guess? $\endgroup$
    – LSpice
    Aug 19 at 23:42
  • 3
    $\begingroup$ @LSpice The OP specifies that $f$ is real on the real axis. $\endgroup$ Aug 19 at 23:50
  • 3
    $\begingroup$ The argument principle may be useful here since $f$ has no poles, though I don't know if there's a way to distinguish between two very close simple zeroes and a single isolated double zero. $\endgroup$
    – doobdood
    Aug 20 at 0:14
  • 3
    $\begingroup$ @doobdood In a similar direction I thought about studying $f/f'.$ This function has only a zero of order 1 in a vicinity of our point of interest. By studying $f''$ we know the root cannot be of order higher than $2$. Hence, the question is only whether $f$ has a simple zero at this point or a zero of order $2$. If it was a simple zero, this would imply that $f$ takes negative values, on the real line, after passing through the zero which one can rule out by the Taylor series of $f$. The problem with this is $f/f'$ is not a nice function (it has a pole at 0) so I don't know how to bound it. $\endgroup$ Aug 20 at 0:34
  • 1
    $\begingroup$ If the pole of $f/f'$ at zero is your only problem, use $xf/f'$. $\endgroup$ Aug 20 at 5:16

3 Answers 3

11
$\begingroup$

I'm not sure I understand exactly how the Taylor expansion of $f(z)$ is "given," but suppose it is "given" only in the sense that for any specified $n$, I can consult an oracle that will tell me the coefficient of $z^n$. Then there is no way I can rule out the possibility that the "given" function is actually $g(z) := f(z) + \delta z^{2N}$ for unknown large $N$ and unknown small $\delta$ (if $f$ is positive in the vicinity of $z_0$ then take $\delta>0$; if it is negative then take $\delta<0$). Without knowing $N$ and $\delta$, we do not know how far out to search the coefficients or how good our bounds need to be. Since $f$ has a zero of order 2 at $z_0$ but $g$ does not, we cannot tell whether the given function has a zero of order 2.

$\endgroup$
6
  • 2
    $\begingroup$ To extend on this: In any standard model of computation you can only ever know finitely many Taylor coefficients up to finite precision. This only allows you to characterize your function up to small perturbations. So the only thing you can ever deduce on your function are properties stable under small perturbations. Single real zeros are stable, double real zeros aren't: If you perturb your function, they can either turn into two real zeros arbitrarily close to each other, or two complex zeros arbitrarily close to each other (and no real ones). $\endgroup$ Aug 20 at 6:54
  • 5
    $\begingroup$ Nicely explained. This issue comes up in connection with the question of determining whether a numerically computed zero of the Riemann zeta function is a double zero or two distinct zeros that are very close to each other. As far as I understand there is no known algorithm that’s guaranteed to certify a double zero in finite time. See this discussion that touches briefly on this point. $\endgroup$
    – Dan Romik
    Aug 20 at 7:52
  • $\begingroup$ The OP says you get estimated on the remainders of the Taylor series, and that matters. $\endgroup$ Aug 20 at 10:29
  • $\begingroup$ @AndrejBauer It seems to me that Timothy Chow's answer shows that estimates on the remainder also cannot solve this problem; by taking $\delta$ as small as we want, we can make the remainder as small as we want. $\endgroup$ Aug 20 at 11:22
  • $\begingroup$ @AndrejBauer In fact, at one point, I deleted my answer because I thought that the remainder estimate might save us, but as David Speyer says, if we don't know how small $\delta$ is then we don't know how good an estimate we need to terminate. $\endgroup$ Aug 20 at 12:41
1
$\begingroup$

Just as an incidental remark, but perhaps with interesting substance: if we run a numerical Newton-Raphson process to approximate an alleged double $0$, at some point it will behave very badly, [EDIT: if there is no actual zero...] throwing the "next approximation" far away. I've never thought about quantifying this...

$\endgroup$
1
  • $\begingroup$ Good point. It doesn't solve the problem under discussion, though, because you can't rule out the possibility that the bad behavior was just about to start, except that you prematurely decided to halt your computation. $\endgroup$ Aug 20 at 13:01
1
$\begingroup$

I find the question written in a confusing way, so I am not sure I understood it correctly, but perhaps the following observation can help.

In order to pose the question correctly, we need to work in a setup that endows mathematical structures with computability, of which there are several. I am going to work with computability over (Type 1) Turing machines, in which every structure is endowed with a Gödel coding that provides a notion of computability.

Throughout all entities are therefore going to be computable. I am not going to keep writing that. Nontheless, when we write down a function, we must argue that it is computable.

Let $$ S = \{ f : \mathbb{C} \to \mathbb{C} \mid \text{$f$ entire, $f(0) = 1$, $f'(0) = 0$, $f(\mathbb{R}) \subseteq \mathbb{R}$} \}. $$ (Note that according to the above statement, $S$ contains only computable maps. Moreover, the elements of $f$ are computably entire, which implies that all their higher derivatives are also computable.)

The map $u : [0,1] \times S \times S \to S$, defined by $$ u(f, g, t) = (z \mapsto t \cdot g(z) + (1 - t) \cdot h(z)) $$ is computable. That is, $S$ is a computable convex space, computably so. (One last time, let me note that the elements of $[0,1]$ are the computable reals between $0$ and $1$.)

We claim that every computable predicate $P : S \to \{0, 1\}$ is constant, thereby answering the original question negatively. Indeed, the question was whether a predicate of the form $$f \mapsto \begin{cases} 1 & \text{if $f$ has a certain kind of zero}\\ 0 & \text{otherwise} \end{cases} $$ is computable.

Suppose first that $P$ is non-constant, i.e., there are (computable) $g, h \in S$ such that $P(g) = 1$ and $P(h) = 0$. Then the map $[0,1] \to \{0, 1\}$, defined by $$ t \mapsto P(u(g, h, t)) $$ is computable, hence continuous (this is a fundamental theorem in computable analysis) and therefore constant (this holds even when we work just with computable reals). But this cannot be because $P(u(g, h, 0)) = P(h) = 0$ and $P(u(g, h, 1)) = P(h) = 1$.

$\endgroup$
9
  • $\begingroup$ @AndrejBauer Does your answer address the question? Let $S$ be as in your post. If $f\in S$ happens to have a simple zero, then there is a computational procedure that will eventually verify this fact (using approximations for $f$ and $f'$ near such a zero). Thus, the class of such functions is semidecidable. Your argument shows that this class is not decidable. Similarly, I think the OP was asking whether or not the class of functions with double zeros is semidecidable (rather than decidable). $\endgroup$ Aug 20 at 15:36
  • $\begingroup$ @SamHopkins: fixed, thanks. $\endgroup$ Aug 20 at 16:48
  • $\begingroup$ @PaceNielsen: the OP does not seem to know the standard terminology, so we have some guessing to do. It sounded to me like they were asking for a decision procedure that can decide whether a certain predicate (has such-and-such double zero) holds. My answer, if correct, shows that no predicate whatsoever can be computable, unless it's trivial. $\endgroup$ Aug 20 at 16:51
  • $\begingroup$ How do you verify that $f$ has zero at $x$? That's not a semidecidable predicate, it's co-semidecidable. $\endgroup$ Aug 20 at 16:52
  • 2
    $\begingroup$ Andrej, I agree the OP didn't use standard terminology, but I personally thought the OP made it clear what they were asking for, by giving the case of order 1 zeros. And note, the question isn't asking for us to computationally verify where the zeros are located. It is asking us to merely verify their order. The order, for order 1 zeros, is computationally semidecidable. Their position is co-semidecidable as you say. $\endgroup$ Aug 20 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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