Can computers find zeros of order $2$?

Question

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.

Answer 1

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.

Answer 2

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...

Answer 3

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$.