Lipschitz Continuity of Bounded Rational Functions

This text is fully human written and the result of my weekend's thought process about a totally different problem. Neither should it contain anything super surprising for any heartfelt mathematician. I still found the result surprising, since it illustrates a huge difference in the expressiveness of uni- and multivariate polynomials.

Preliminaries

Definition 1. A function \(f\colon D \to \mathbb{R}\) is bounded if there exists a bound \(b \in \mathbb{R}\) such that \(|f(x)| \leq b\) for all \(x \in D\).

Definition 2. A function \(f\colon D \to \mathbb{R}\) is Lipschitz continuous if there exists a \(L \in \mathbb{R}\) such that \(|f(x) - f(y)| \leq L \, \lVert x - y \rVert\) holds for all \(x, y \in D\). The smallest \(L\) that satisfies this condition is called the Lipschitz modulus of \(f\).

Proposition 1. A differentiable function is Lipschitz continuous if and only if its first derivative is bounded.

Since continuous functions are bounded on a compact domain, we also have:

Proposition 2. A continuously differentiable function is Lipschitz continuous if the domain is compact.

The Univariate Case

Definition 3. A rational function is a function \(f\colon D \to \mathbb{R}\) with domain \(D \subseteq \mathbb{R}\) such that there exist polynomials \(p, q \in \mathbb{R}[X]\) with \(f(x) = \frac{p(x)}{q(x)}\) for all \(x \in D\).

For a normal form, it can be assumed that the polynomials \(p, q\) are co-prime, that is, \(\gcd(p,q) = 1\). In particular, \(Q\) cannot have a root on \(D\): suppose \(q(x) = 0\) for some \(x \in D\), then \(p(x) \neq 0\). The function \(f\) would diverge at this point. Thus, it can even be assumed that \(q(x) > 0\) for all \(x \in D\).

Note that a rational functions \(f = \frac{p(x)}{q(x)}\) always is differentiable; its derivative \(f'\) simply is given by the well-known quotient rule, $$ f'(x) ~=~ \frac{p'(x) q(x) - p(x) q'(x)}{q(x)^2} $$ for all \(x \in D\). This again is a rational function as \(p', q'\) are polynomials and \(q(x)^2 = q^2(x)\).

Proposition 3. A rational function \(f = \frac{p(x)}{q(x)}\) is bounded if and only if \(\deg p \leq \deg q\).

It's a simple consequence that if \(f\) is bounded, then so must be \(f'\): The denominator \(q(x)^2\) has the same roots as \(q(x)\), and \(\deg p' q - p q' = \max \, \{ \deg p' q, \deg p q' \} \leq \deg p q \leq \deg q^2\) as differentiating decrements the degree by one. From Proposition 1 we thus obtain:

Proposition 4. A bounded rational function is Lipschitz continuous.

While this to me was rather intuitive, it should rather be surprising as the next section will show. The converse statement (Lipschitz implies bounded) obviously is false, as can already be seen from \(f(x) = x\).

The Multivariate Case

Definition 4. A multivariate rational function is a function \(f\colon D \to \mathbb{R}\) with domain \(D \subseteq \mathbb{R}^d\) such that there exist multivariate polynomials \(p, q \in \mathbb{R}[X_1, \ldots, X_d]\) with \(f(x) = \frac{p(x)}{q(x)}\) for all \(x \in D\). Again, it can be assumed that \(p\) and \(q\) are co-prime and \(q(x) > 0\) for all \(x \in D\).

In contrast to the nice result from Proposition 4, the multivariate case is much wilder.

Example 1. Consider $$ f(x,y) = \frac{xy}{x^2 y^2 + 1} ~. $$ The function is multivariate rational. Its also bounded, as by the arithmetic-geometric mean inequality we have $$ x^2 y^2 + 1 \geq 2 \sqrt{x^2 y^2 \cdot 1} = 2 |xy| ~. $$ However, looking at its partial derivative $$ f_y(x,y) = \frac{x \, (x^2 y^2 + 1) - xy \, (2 x^2 y)}{(x^2 y^2 + 1)^2} = \frac{x - x^3 y^2}{x^4 y^4 + 2 x^2 y^2 + 1} $$ and projecting onto the subvariety \(y=0\) (this means we are just looking at \(f\) on the \(x\)-axis), we have \(f_y(x, 0) = x\) which diverges as \(x \to \pm\infty\). Analogous to Proposition 1, this means that \(f\) is not Lipschitz continuous.

What happened here? Introducing the fresh variable \(z = xy\) and letting $$ F(z) = \frac{z}{z^2 + 1} ~, $$ we have that \(F(xy) = f(x,y)\) for all \(x, y \in \mathbb{R}\). In this light, we can view \(f\) as squeezing the function \(F\) along the \(y\)-axis, causing an arbitrarily steep wall. Just look at \(F(x), F(2x), F(3x), \ldots\) The \(y\)-component of the function \(f\) compressed its \(x\)-component and vice versa; the compression actually happens in all directions. In certain directions, the denominator does not grow fast enough to swallow the numerator. This observation motivates the next definition.

Definition 5. A multivariate rational function \(f\colon D \to \mathbb{R}, z \mapsto \frac{p(z)}{q(z)}\) is radially bounded if there exists a \(c > 0\) such that \(q(z) \geq c \, \lVert z \rVert^{\deg P}\) for all \(z \in D\).

Note that the equivalence of norms on finite dimensional real vector spaces allows for an arbitrary choice in this definition. We immediately see that this is equivalent to boundedness in the univariate case, as was illustrated in Proposition 3. However, this new condition is stronger in the multivariate case:

Proposition 6. A radially bounded (multivariate) rational function is Lipschitz continuous.

In the univariate case there simply wasn't enough space for both properties to differ. Revisiting the function from Example 1, we have the norm \(\lVert z \rVert = \sqrt{x^2 + y^2}\) which simply evaluates to \(|x|\) on the subvariety \(y = 0\). Since \(q(x,0) = 1 < c \, x^2\) for any \(c\), the function there indeed is not radially bounded.

Example 2. The function $$ g(x,y) = \frac{xy}{x^2 + y^2 + 1} $$is radially bounded.

From Algebraic to Tropical Geometry

After all this, I am somewhat astonished that a function can stay bounded without being radially bounded. Let us try to find a more satisfactory explanation. Indeed, the asymptotic behavior of multivariate polynomials can be determined by its Newton polytope.

Definition. Let \(p = \sum_{\alpha \in \mathbb{Z}_{\geq 0}^d} c_{\alpha} \, X^{\alpha}\) be a multivariate polynomial in \(X = (X_1, \ldots, X_d)\). Its Newton polytope \(N(p)\) is the convex hull of vectors \(\alpha\) such that \(c_{\alpha} \neq 0\).

Obviously, the Newton polytope indeed is a polytope, that is, a bounded polyhedron. The Minkowski sum \(A + B\) of two sets \(A, B \subseteq \mathbb{R}^d\) is defined as the set \(\{ a + b : a \in A, b \in B \}\). This operation is associative and commutative. The Newton polytope has the nice property that \(N(pq) = N(p) + N(q)\). This can be easily seen by looking at the generators of the polytopes.

Given \(r \in \mathbb{R}\), we also write \(r A\) for the set \(\{ r a : a \in A \}\). For convex \(A\) and \(k \in \mathbb{Z}_{\geq 0}\), we even have $$ \underbrace{A + \ldots + A}_{k~\text{times}} = k A ~. $$ It follows \(N(p^k) = k \, N(p)\) by induction.

The Newton polytope captures the asymptotic behavior of the polynomial:

Proposition 7. A rational function \(f(x) = \frac{p(x)}{q(x)}\) is bounded if and only if \(N(p) \subseteq N(q)\).

Of course it suffices to check if the vertices for \(N(p)\) are included in \(N(q)\) already.

The Geometry of Differentiation

So why does boundedness not suffice in the multivariate case? The answer lies in the quotient rule of differentiation, as it somewhat mixes up the possible monomials. Hence, let us study in more detail how differentiation affects the Newton polytope.

To this end, let \(p \in \mathbb{R}[X_1, \ldots, X_d]\) be a multivariate polynomial. The partial derivative \(p_i\) of \(p\) with respect to \(X_i\) has Newton polytope \(N(p_i) = \{ a \ominus e_i : a \in N(p) \}\), where monus \(a \ominus b = \max\{0, a - b\}\) operates pointwise on the tuple and \(e_i\) is the standard basis vector that is \(1\) at position \(i\) and \(0\) elsewhere. Now, consider a multivariate rational function \(f(x) = \frac{p(x)}{q(x)}\) and its partial derivative \(f_i\) with respect to the coordinate \(X_i\). By the quotient rule, this is determined as $$ f_i(x) ~=~ \frac{p_i(x) q(x) - p(x) q_i(x)}{q(x)^2} ~, $$ where \(p_i\) and \(q_i\) are the partial derivatives of \(p\) and \(q\) with respect to \(X_i\). The differentiation thus can affect the shape of the numerators polytope, while the denominator only is scaled.

Example 3. Recall $$ f(x,y) = \frac{xy}{x^2 y^2 + 1} $$ from Example 1. The single point \((1,1)\) corresponding to its numerator lies within the line segment \(\operatorname{conv}\,\{ (2,2), (0,0) \}\) that is the Newton polytope of its denominator. As we already saw, the function is bounded. Now the partial derivative \(f_y\) has \((1,0)\) and \((3,2)\) as generators for the Newton polytope of its numerator. Regarding its denominator, we obtain the line segment \(\operatorname{conv}\,\{ (4,4), (0,0) \}\), which excludes both \((1,0)\) and \((3,2)\). Indeed, \(f_y\) is unbounded and thus \(f\) not Lipschitz.

A multivariate rational function can be bounded as one line segment can include another. After differentiation, however, the Newton polytope of the numerator is not just a line segment anymore and thus unboundedness occurs. This simply cannot happen in the univariate case, as the polytopes always are line segments. Furthermore, it captures how radially bounded rational functions are Lipschitz: The Newton polytope of the denominator cannot simply be a line segment but must expand in every dimension. For this reason, the numerator of any partial derivative cannot suddenly escape it, in contrast to what happened in the previous example. As the gradient is determined by the partial derivatives, and in turn determines any directional derivatives via the inner product, this already suffices for Lipschitz continuity.