Big O Estimates

Tie’s Extra Questions: Fall 2011, Fall 2009 (Polynomial upper bound, \(d=2\)) #complex/exercise/completed

Let \(f(z)\) be entire and assume that \(f(z) \leq M |z|^2\) outside some disk for some constant \(M\). Show that \(f(z)\) is a polynomial in \(z\) of degree \(\leq 2\).

Take a Laurent expansion at zero: \begin{align*} f(z) = \sum_{k\geq 0} c_k z^k,\qquad c_k = {1\over k!} f^{(k)}(0) = {1\over 2\pi i}\oint_{{\left\lvert {\xi} \right\rvert} = R} {f(\xi) \over \xi^{k+1}}\,d\xi .\end{align*} The usual estimate: \begin{align*} 2\pi i{\left\lvert {c_k} \right\rvert} \leq \oint_{{\left\lvert {\xi} \right\rvert} = R} R^{-(k+1)}{\left\lvert {f(\xi)} \right\rvert} \,d\xi &\leq \oint_{{\left\lvert {\xi} \right\rvert} = R}R^{-(k+1)} M R^2 \,d\xi\\ &= M R^{-(k-1)} \cdot 2\pi R \\ &= 2\pi M R^{-k+2} \\ &\overset{R\to\infty}\longrightarrow 0 ,\end{align*} provided \(-k+2<0 \iff k>2\).

Tie’s Extra Questions: Spring 2015, Fall 2016 (Polynomial upper bound, \(d\) arbitrary) #complex/exercise/completed

  • Let Let \(f:{\mathbb C}\rightarrow {\mathbb C}\) be an entire function. Assume the existence of a non-negative integer \(m\), and of positive constants \(L\) and \(R\), such that for all \(z\) with \(|z|>R\) the inequality \begin{align*}|f(z)| \leq L |z|^m\end{align*} holds. Prove that \(f\) is a polynomial of degree \(\leq m\).

  • Let \(f:{\mathbb C}\rightarrow {\mathbb C}\) be an entire function. Suppose that there exists a real number \(M\) such that for all \(z\in {\mathbb C}, \Re(f) \leq M\). Prove that \(f\) must be a constant.

\begin{align*} {\left\lvert {f^{(n)}(z)} \right\rvert} &= {\left\lvert { {1\over 2\pi i} \oint_\gamma {f(\xi) \over (\xi - z)^{n+1}} \,d\xi} \right\rvert} \\ &\leq {1\over 2\pi i} \oint_\gamma { {\left\lvert { f(\xi) } \right\rvert} \over {\left\lvert {\xi - z} \right\rvert}^{n+1}} \,d\xi\\ &\leq {1\over 2\pi i } \oint_\gamma {LR^m \over R^{n+1} } \,d\xi\\ &= {L\over 2\pi i} R^{m-(n+1)} \cdot 2\pi R \\ &= LR^{m-n} \\ &\overset{R\to\infty}\longrightarrow 0 \qquad \iff m-n<0 \iff n>m ,\end{align*} so \(f\) is a polynomial of degree at most \(m\).

Now if \(f\) is entire, \(g(z) \coloneqq e^{f(z)}\) is entire and \begin{align*} {\left\lvert {g(z)} \right\rvert} = {\left\lvert {e^{f(z)}} \right\rvert} = e^{\Re(f)} \leq e^M ,\end{align*} so \(g\) is an entire bounded function and thus constant by Liouville, making \(f\) constant. Why this is true: \begin{align*} e^{f} = C \implies e^f \cdot f' = 0 \implies f'\equiv 0 ,\end{align*} since \(e^f\) is nonvanishing, and \(f'\equiv 0\) implies \(f\) is constant.

Asymptotic to \(z^n\) #complex/exercise/work

Suppose \(f\) is entire and suppose that for some integer \(n\geq 1\), \begin{align*} \lim_{z\to \infty} {f(z) \over z^n} = 0 .\end{align*}

Prove that \(f\) is a polynomial of degree at most \(n-1\).

Choose \({\left\lvert {z} \right\rvert}\) large enough so that \({\left\lvert {f(z)} \right\rvert}/{\left\lvert {z} \right\rvert}^n < {\varepsilon}\). Then write \(f(z) = \sum_{k\geq 0} c_k z^k\) and estimate \begin{align*} 2\pi {\left\lvert {c_k} \right\rvert} &\leq \oint_{{\left\lvert {z} \right\rvert} = R} {f(\xi) \over \xi^{k+1}}\,d\xi\\ &\leq \oint_{{\left\lvert {z} \right\rvert} = R} {{\varepsilon}{\left\lvert {\xi} \right\rvert}^n \over {\left\lvert {\xi} \right\rvert}^{k+1} } \,d\xi\\ &= {\varepsilon}R^{n-(k+1)} \cdot 2\pi R \\ &= {\varepsilon}C R^{n-k} \\ &\overset{{\varepsilon}\to 0}\longrightarrow 0 \end{align*} provided \(n-k \leq 0 \iff k\geq n\), since \({\varepsilon}\to 0\) forces \(R\to \infty\).

Spring 2021.3, Tie’s Extra Questions: Spring 2014, Fall 2009 (Polynomial lower bound, \(d\) arbitrary) #complex/exercise/completed

Suppose \(f\) is entire and there exist \(A, R >0\) and natural number \(N\) such that \begin{align*} |f(z)| \geq A |z|^N\ \text{for}\ |z| \geq R .\end{align*}

Show that

  • \(f\) is a polynomial and
  • the degree of \(f\) is at least \(N\).

The easier version of this question: when \({\left\lvert {f} \right\rvert} \leq A{\left\lvert {z} \right\rvert}^N\), \(f\) is a polynomial of degree at most \(N\) by Cauchy’s integral formula: \begin{align*} {\left\lvert {f^{(n)}(z)} \right\rvert} &= {\left\lvert { {1\over 2\pi i} \oint_\gamma {f(\xi) \over (\xi - z)^{n+1}} \,d\xi} \right\rvert} \\ &\leq {1\over 2\pi i} \oint_\gamma { {\left\lvert { f(\xi) } \right\rvert} \over {\left\lvert {\xi - z} \right\rvert}^{n+1}} \,d\xi\\ &\leq {1\over 2\pi i } \oint_\gamma {AR^N \over R^{n+1} } \,d\xi\\ &= {A\over 2\pi i} R^{N-(n+1)} \cdot 2\pi R \\ &= AR^{N-n} \\ &\overset{R\to\infty}\longrightarrow 0 \qquad \iff N-n<0 \iff n>N .\end{align*}

Now rearrange the given equality \begin{align*} {\left\lvert {f(z) \over z^N} \right\rvert} \geq A \qquad {\left\lvert {z} \right\rvert} \implies {\left\lvert {z^N\over f(z)} \right\rvert} \leq A^{-1} .\end{align*} A priori, \(f\) is equal to its power series at \(z=0\), so \(f(z) = \sum_{k\geq 0} c_k z^k\). Since \({\mathbb{D}}_R\) is compact, \(f\) has finitely many zeros in this region, say \(\left\{{z_k}\right\}_{k\leq m}\). This set must be finite, since an infinite subset of a compact set has a limit point, and being zero on a set with a limit point implies being identically zero by the identity principle.

Define \begin{align*} p(z) \coloneqq\prod_{1\leq k\leq m} (z-z_k) = z^m + { \mathsf{O}}(z^{m-1}) ,\end{align*} the product of these roots. Increase \(R\) if necessary to ensure that \begin{align*} {\left\lvert {p(z)\over z^m} \right\rvert} < 1 \implies {\left\lvert {p(z)} \right\rvert} < {\left\lvert {z} \right\rvert}^m .\end{align*} Now define \begin{align*} G(z) \coloneqq{p(z) z^N \over f(z)} \implies {\left\lvert {G(z)} \right\rvert} = {\left\lvert {p(z) z^N\over f(z)} \right\rvert} = {\left\lvert {z^N\over f(z)} \right\rvert}\cdot {\left\lvert {p(z)} \right\rvert} \leq A^{-1}{\left\lvert {z} \right\rvert}^m .\end{align*}

Issue: this might not be entire? There could be poles at the zeros of \(f\) outside of \({\mathbb{D}}_R\)

By the previous result, \(G\) is a polynomial of degree at most \(m\). Now consider leading terms: on one hand, \begin{align*} f(z) G(z) = p(z) z^N \sim \qty{z^m + \cdots }\cdot z^N = z^{N+m} + \cdots .\end{align*} On the other hand, \begin{align*} f(z) G(z) &= f(z) \qty{z^m + \cdots} \\ &\sim \sum_{k\geq 0} c_k z^{k+m} + z^{m-1}f(z) + \cdots \\ &= (z^m + \cdots + c_{N}z^{N+m} + \cdots) + z^{m-1}f(z) + \cdots ,\end{align*} and by the previous expression, this must be a polynomial of degree at most \(N+m\). This forces \(c_k = 0\) for all \(k> N\), otherwise these would contribute higher order terms.

Note: maybe not quite right!

Alternatively, note that the inequality can be rewritten as \begin{align*} {\left\lvert {G(z)} \right\rvert} \leq A^{-1}{\left\lvert {z} \right\rvert}^m \implies {\left\lvert {p(z)\over f(z)} \right\rvert} \leq A^{-1}{\left\lvert {z} \right\rvert}^{m-N} .\end{align*}

  • If \(m-N = 0\), then \(p/f\) is an entire bounded function and thus constant, making \(p(z) = \lambda f(z)\) and \(f\) is a polynomial of degree exactly \(N\). -If \(m-N>0\), then \(p/f\) is a polynomial of degree at most \(m-N\) by the previous result. But \(p/f\) is a polynomial with no zeros, since \(Z_p = Z_f\), and the only nonvanishing polynomial is a constant, so again \(p = \lambda f\).
  • If \(m-N<0\), then use the inequality \begin{align*} {\left\lvert {z^{N-m}p(z) \over f(z)} \right\rvert} \leq A^{-1} ,\end{align*} so the LHS is an entire bounded function and thus constant, so \(z^{N-m}p(z) = \lambda f(z)\). But the LHS is evidently a polynomial of degree \((N-m)+m = m\).

Note that the analogue of this problem where \({\left\lvert {f(z)} \right\rvert} \leq A {\left\lvert {z} \right\rvert}^N\) implies \(f\) is a polynomial of degree at most \(N\) is easy by the Cauchy estimate: \begin{align*} {\left\lvert {f(z)} \right\rvert} ={\left\lvert {\sum_{k\geq 0} c_k z^k } \right\rvert} \implies {\left\lvert {c_n} \right\rvert} = {\left\lvert {f^{(n)}(0)} \right\rvert} &= {\left\lvert {{n!\over 2\pi i }\int_\gamma {f(\xi) \over (\xi-a)^{n+1} } \,d\xi} \right\rvert} \quad \text{ at } a=0\\ &\leq {n!\over 2\pi }\int_\gamma {{\left\lvert {f(\xi)} \right\rvert} \over {\left\lvert {\xi} \right\rvert}^{n+1} } \,d\xi\\ &\leq {n!\over 2\pi }\int_\gamma {A {{\left\lvert {\xi} \right\rvert}^N } \over {\left\lvert {\xi} \right\rvert}^{n+1} } \,d\xi\\ &= {A n!\over 2\pi }\int_\gamma {{R ^N } \over R^{n+1} } \,d\xi\\ &= {An!\over 2\pi} \cdot {2\pi R \over R^{n+1-N}} \\ &= {An! \over R^{n-N}} \\ &\overset{R\to\infty}\longrightarrow 0 \quad \iff n-N>0 \quad\iff n>N ,\end{align*} so \(f(z) = \sum_{0\leq k\leq N} c_k z^k\).

For the case at hand, a solution I liked from MSE:

  • Write \(g(z) \coloneqq f(1/z)\), so \(g\) has a singularity at \(z=0\). The claim is that this is a pole.

  • It can’t be removable: \begin{align*} {\left\lvert {g(z)} \right\rvert} \geq A {\left\lvert {1\over z} \right\rvert}^n \to\infty \quad \text{ for } {\left\lvert {1/z} \right\rvert} \geq R \,\, (\iff {\left\lvert {z} \right\rvert} < 1/R) ,\end{align*} so \(g\) is unbounded near \(z=0\).

  • It can’t be essential: if so, take the neighborhood of \(z=0\) given by \(U\coloneqq D_{1\over R}(0)\setminus\left\{{0}\right\}= \left\{{z{~\mathrel{\Big\vert}~}0< {\left\lvert {z} \right\rvert} < {1\over R} }\right\}\). Then \(g(U) \subseteq {\mathbf{C}}\) would be dense by Casorati-Weierstrass, but note that \(g(z) = w\in g(U) \implies {\left\lvert {w} \right\rvert} \coloneqq{\left\lvert {g(z)} \right\rvert} \geq A{\left\lvert {1/z} \right\rvert}^n\) since \({\left\lvert {z} \right\rvert}<1/R\), so \(g(U) \subseteq ({\mathbf{C}}\setminus D_{A\over R^n}(0))\) and in particular does not intersect the interior of \(D_{A\over R^n}(0)\).

  • Since \(z=0\) is a pole, it has some finite order \(m\), so write \begin{align*} g(z) = \qty{c_{-m}z^{-m} + \cdots + c_{-1}z^{-1}} + \qty{c_0 + c_1 z + \cdots} \coloneqq p(1/z) + h(z) ,\end{align*} where \(p\) is polynomial of degree exactly \(m\) (since \(c_{-m} \neq 0\)) and \(h\) is entire. In particular, \(z=0\) is not a singularity of \(h\).

  • Now \begin{align*} g(z) = p(1/z) + h(z) \implies f(z) = p(z) + h(1/z) .\end{align*}

  • Then \begin{align*} f(z) - p(z) = h(1/z) \overset{{\left\lvert {z} \right\rvert}\to \infty}\longrightarrow c_0 \coloneqq h(0) ,\end{align*} since holomorphic functions are continuous.

  • Then \(h\) is an entire function with a finite limit \(L\) at \(\infty\). \(h\) is bounded by \(c_0\) in a neighborhood \(U_\infty\) of \(\infty\) and takes on a maximum on \(U_\infty^c\) by compactness and the maximum modulus principle. So \(h\) is bounded on all of \({\mathbf{C}}\), and thus constant by Liouville, and thus \(h(1/z) = L\) for all \(z\).

  • So \begin{align*} f(z) &= p(z) + h(1/z) = p(z) + c_0 \\ \implies f(z) &= (c_{-1}z + \cdots + c_{-m}z^m) + c_0 ,\end{align*} which is a polynomial of degree exactly \(m\coloneqq\deg p\).

  • Why \(m \geq N\): if not, \(m<N\) so \(N-m > 0\). Then for large \(z\), \begin{align*} A \leq {\left\lvert {f(z) \over z^N} \right\rvert} &= {\left\lvert {c_0 + c_{-1}z + \cdots + c_{-m}z^m \over z^N} \right\rvert}\\ &= {\left\lvert { {c_0 \over z^N} + {c_{-1} \over z^{N-1}} + \cdots + {c_{-m} \over z^{N-m}} } \right\rvert} \\ &\overset{{\left\lvert {z} \right\rvert}\to\infty}\longrightarrow 0 ,\end{align*} since every term has a factor of \(z\) in the denominator. This contradicts \(A>0\). \(\contradiction\)


Spring 2021.4 #complex/qual/completed

Let \(f = u + iv\) be an entire function such that \(\Re(f(x+iy))\) is polynomial in \(x\) and \(y\). Show that \(f(z)\) is polynomial in \(z\).

To clear up notation: write \(f(z) = u(x, y) + iv(x, y)\), here we’re assuming that \(u\) is polynomial in \(x\) and \(y\).

If \(u\) is polynomial in \(x,y\), then so is \(v\).

This follows from the fact that \(u\) is a harmonic conjugate of \(v\), and the explicit process computing the conjugate will result in a polynomial. Gamelin describes this process in detail, see Ch.2 Section 5 on Harmonic functions where he proves the formula \begin{align*} v(x, y) = \int_{y_{0}}^{y} \frac{\partial u}{\partial x}(x, t) \,dt -\int_{x_{0}}^{x} \frac{\partial u}{\partial y}\left(s, y_{0}\right) \,ds+ C .\end{align*}

Since \(f(x, y)\) is a polynomial in \(x, y\), \(f(z)\) must be a polynomial in \(z\).

Since \(f\) is entire, it’s equal to its Laurent series everywhere, so \begin{align*} f(z) = \sum_{k\geq 0} c_k z^k, \qquad c_k = {f^{(k) }(0) \over k!} = {1\over 2\pi i} \int_{S^1} {f(\xi) \over \xi^{k+1} } \,d\xi .\end{align*} Thus \(f\) will be a polynomial if \(c_{N} = 0\) for all \(N\) large enough, which will be true if \(f^{(N)}(z) = 0\) for large enough \(N\). But we can write \begin{align*} {\frac{\partial }{\partial z}\,} f(z) = {\frac{\partial }{\partial x}\,} f(x, y) \implies 0 = \qty{{\frac{\partial ^N}{\partial x^N}\,}} f(x, y) = \qty{{\frac{\partial ^N}{\partial z^N}\,}} f(z) \coloneqq f^{(N)}(z) ,\end{align*}

Spring 2019.4 (Eventually bounded implies rational) #complex/qual/completed

Let \(f\) be a meromorphic function on the complex plane with the property that \(|f(z)| \leq\) \(M\) for all \(|z|>R\), for some constants \(M>0, R>0\).

Prove that \(f(z)\) is a rational function, i.e., there exist polynomials \(p, q\) so that \(f=\frac{p}{q}\).

Note that \(f\) must have finitely many poles – either \(z=\infty\) is a pole or a removable singularity, and since poles are isolated, there is some \(R\gg 0\) such that all other poles of \(f\) are in \({\left\lvert {z} \right\rvert} \leq R\). The set \(P_f\) of poles is a closed set and \(\overline{{\mathbb{D}}_R}\) is compact, so if \(P_f\) is infinite it has an accumulation point, contradicting that poles are isolated.

So enumerate \(P_f\) as \(\left\{{p_k}\right\}_{k\leq N}\), define \(g(z) \coloneqq\prod_{k\leq N}(z-p_k)\), and set \(F(z) \coloneqq g(z) f(z)\). Then \(F\) is an entire function, and the claim is that \(F\) is bounded and thus constant by Liouville. Proving the bound: take \({\left\lvert {z} \right\rvert} > R\), then \begin{align*} {\left\lvert {G(z)} \right\rvert} &= {\left\lvert {f(z)} \right\rvert} {\left\lvert {g(z)} \right\rvert} \\ &\leq M C {\left\lvert {z} \right\rvert}^N ,\end{align*} using that \(g\) is a polynomial of degree \(N\), so \({\left\lvert {g(z)\over z^N} \right\rvert}\to 1\) as \({\left\lvert {z} \right\rvert}\to \infty\) since \(g\) is monic. So after possibly increasing \(R\), we can choose \({\left\lvert {z} \right\rvert}\) large enough so that \({\left\lvert {g(z)\over z^N} \right\rvert} < C\) for, say, some constant \(C<2\). In any case, by a common qual question, if \({\left\lvert {G} \right\rvert} \in { \mathsf{O}}({\left\lvert {z} \right\rvert}^N)\) for \({\left\lvert {z} \right\rvert}\) large enough then \(G\) is a polynomial of degree at most \(N\). Then \(f(z) \coloneqq G(z)/g(z)\) is a rational function.

Spring 2020 HW 3.5, Tie’s Extra Questions: Fall 2015 #complex/exercise/completed

Let \(f\) be entire and suppose that \(\lim_{z \rightarrow \infty} f(z) = \infty\). Show that \(f\) is a polynomial.

Note that \(f\) has finitely many zeros: since \(f\) is unbounded, there is some \(R\) such that \(f({\mathbb{D}}_R^c) \subseteq {\mathbb{D}}^c\), so in particular \(f\) is nonvanishing on \({\mathbb{D}}_R^c\). So \(Z_f\) is a closed subset of a compact set, so is either finite or has an accumulation point. In the latter case, \(f\equiv 0\) by the identity principle, so suppose not.

Write \(Z_f = \left\{{z_k}\right\}_{k\leq n}\) for the \(n\) many zeros of \(f\), included with multiplicity, and set \begin{align*} \Phi(z) \coloneqq\prod_{k\leq n} (z-z_k), \qquad F(z) \coloneqq{\Phi(z) \over f(z) } .\end{align*} Now \(F\) is a nonvanishing entire function.

\(F\) is bounded on \({\mathbf{C}}\).

Choose \(R\gg 1\) so that all of \(z_k\) are in \({\mathbb{D}}_R\), so \({\left\lvert {\xi - z_k} \right\rvert} < R\) for all \(\xi \in {\mathbb{D}}_R\) and all \(k\). By Cauchy’s integral formula, \begin{align*} {\left\lvert {F(z)} \right\rvert} &\leq {1\over 2\pi} \oint_{{\left\lvert {\xi} \right\rvert} = R} {\left\lvert {F(\xi) \over \xi} \right\rvert} \,d\xi\\ &={1\over 2\pi} \oint_{{\left\lvert {\xi} \right\rvert} = R} {\left\lvert {\Psi(\xi) \over f(\xi) \cdot \xi} \right\rvert} \,d\xi\\ &\leq {1\over 2\pi} \oint_{{\left\lvert {\xi} \right\rvert} = R} {R^m \over {\left\lvert { f(\xi) } \right\rvert} R } \,d\xi\\ &\leq {1\over 2\pi} \oint_{{\left\lvert {\xi} \right\rvert} = R} R^{m-1} \,d\xi\\ &= R^m ,\end{align*} where \(R\) is increased if necessary to ensure \({\left\lvert {1\over f(z)} \right\rvert} < 1\), which can be done since \({\left\lvert {f(z)} \right\rvert}\to \infty\) as \(R\to \infty\). So \({\left\lvert {F(z)} \right\rvert} \leq C{\left\lvert {z} \right\rvert}^m\) in \(\overline{{\mathbb{D}}_R}^c\) for \(R\) large enough, making \(F\) a polynomial of degree at most \(m\). Since \(F\) is continuous in \(\overline{{\mathbb{D}}_R}\) which is compact, \(F\) is bounded in here as well, making \(F\) bounded on all of \({\mathbf{C}}\).

Given this, \(F\) is entire and bounded and thus constant by Liouville. So \(F(z) = c\), and as a result \(f(z) = c\Phi(z)\) which is a polynomial of degree \(n\).

Spring 2020 HW 2, SS 2.6.13 #complex/exercise/completed

Suppose \(f\) is analytic, defined on all of \({\mathbf{C}}\), and for each \(z_0 \in {\mathbf{C}}\) there is at least one coefficient in the expansion \(f(z) = \sum_{n=0}^\infty c_n(z-z_0)^n\) is zero. Prove that \(f\) is a polynomial.

Hint: use the fact that \(c_n n! = f^{(n)}(z_0)\) and use a countability argument.

Write \(Z_n \coloneqq\left\{{z\in {\mathbf{C}}{~\mathrel{\Big\vert}~}f^{(n)}(z) = 0 }\right\}\), then by hypothesis \(\bigcup_{n\geq 0} Z_n = {\mathbf{C}}\). A version of the Baire category theorem is that if \(X\) is a complete metric space and \(X\) is a countable union of closed sets, then at least one such set has a nonempty interior. Thus some \(Z_n\) has an interior point \(z_0\), and as a result there is some disc \({\mathbb{D}}_{\varepsilon}(z_0)\) on which \(f^{(n)}(z_0) \equiv 0\). This implies that \(f^{(k)}(z_0) \equiv 0\) on \({\mathbb{D}}_{\varepsilon}(z_0)\) for every \(k\geq n\), so \(f\) is a polynomial of degree at most \(n\).

#complex/exercise/completed #complex/exercise/work #complex/qual/completed