Multiplicative and additive functions

2022-11-16  ·  # math

Introduction

Multiplicative structure often shows up in number theory when one considers common arithmetic functions (functions whose domain are the integers).

In addition, we say that $f$ is completely multiplicative if it satisfies (1) for all integers $x, y$, not just those which are relatively prime. From now on we will use the term "multiplicative" to refer to completely multiplicative functions and take our domain to be the reals.

In contrast, some functions have additive structure. For example, for any real $x, y$, the line $f(x) = k x$ for some fixed constant $k$ satisfies

$$\begin{aligned} f(x + y) = f(x) + f(y) \end{aligned}$$

since $f(x + y) = k(x + y) = k x + k y = f(x) + f(y)$.

Examples

Some functions turn multiplicative structure into additive structure; for example, for any real $x, y > 0$, the logarithm function (base irrelevant) satisfies

$$\begin{aligned} \log(xy) = \log(x) + \log(y) \end{aligned}$$

which is an interesting and often quite useful property turning multiplications into additions. However, there is no easy formula (that I know of) for $\log(x + y)$, which is quite unfortunate.

Every symmetric positive-definite (s.p.d.) matrix $\Theta$ has a lower triangular Cholesky factor $L$ satisfying $\Theta = L L^{\top}$. In some sense all matrix factorizations are product structures since they write a complicated matrix as the product of matrices that are hopefully esimpler or easier to work with. Expanding $L L^{\top}$ reveals the hidden additive structure of the Cholesky factorization, owing to the fact that the lower triangularity of $L$ implies a sort of decreasing or nested structure. Indeed, we can write $\Theta$ as the contributions of rank-one matrices given by the outer product of the columns of $L$ (4) (which is generally true for any matrix product) where each outer product affects smaller and smaller submatrices of $\Theta$ (from the triangularity of $L$).

$$\begin{aligned} \Theta = L L^{\top} = L_{:, 1} L_{:, 1}^{\top} + \dotsb + L_{:, n} L_{:, n}^{\top} \end{aligned}$$

Although the Cholesky factor is both an additive and multiplicative factorization, the $\operatorname{chol}(\cdot)$ operator itself does not play well with addition or multiplication. For multiplication the product of two s.p.d. matrices is not even necessarily s.p.d. and for addition even adding a multiple of the identity, that is, trying to factor $\Theta + \sigma^2 \text{Id}$ requires somewhat sophisticated tricks [3], even if one is able to factor $\Theta$ efficiently.

Finally, the $\operatorname{trace}(\cdot)$ and $\det(\cdot)$ operators have additive and multiplicative structure, respectively. That is, for all square matrices $A, B$ of the same size,

$$\begin{aligned} \operatorname{trace}(A + B) &= \operatorname{trace}(A) + \operatorname{trace}(B) \\ \det(AB) &= \det(A) \det(B) \end{aligned}$$

However, there are not as nice decompositions for $\operatorname{trace}(AB)$ or $\det(A + B)$. Although it is possible to turn $\operatorname{trace}(AB)$ into additive structure by expanding the matrix-matrix product and to turn $\det(A + B)$ into multiplicative structure by the Sherman–Morrison–Woodbury identity, this is more of a conversion and a bit less natural than applying (5) directly.

Problem statement

Throughout these examples it seems although multiplicative and additive structure can be converted between, they are hard to mix in some sense. In order to make this notion precise,

Solution

Our strategy will to identify a few specific observations and then work our way up to the naturals $\mathbb{N}$, the integers $\Z$, the rationals $\mathbb{Q}$, and then finally, the reals $\R$. Extension to the complex numbers $\mathbb{C}$ is left as an exercise for the reader.

Naturals

First, we observe that if we fix $y = 1$, then the multiplicative condition (6) implies $\forall x \in \R$

Moving $T(x)$ to the left side and factoring, we have

implying either $T(1) = 1$ or $T(x) = 0$ for all $x$. So immediately the constant function $T(x) = 0$ is a candidate solution and indeed, it also satisfies the additive condition (7) trivially. For the more interesting situation where $T(1) = 1$, now using the additive condition (7), we have

Therefore $T(2) = T(1) + 1 = 2$, $T(3) = T(2) + 1 = 3$, and so on. By induction $T(x) = x$ for all natural numbers $x$ (where we exclude 0 as a natural number for now).

Integers

To extend this result to the integers, first we fill in the hole at 0 by making use of (7),

Then we observe for a natural number $x$ and a negative number $y = -x$, using (7),

where we use that $T(x) = x$ for natural $x$, concluding that $T(x) = x$ for integer $x$.

Rationals

To extend this result to the rationals: let $x = p/q$ for integers $p, q$ and let $y = q$. From (6),

where we use $T(p) = p$ and $T(q) = q$ for integers $p, q$, concluding that $T(x) = x$ for rational $x$.

Reals

Throughout all these examples it seems that $T(x) = x$, but it is hard to extend to the reals without additional structure; we've sort of hit the limit on what our assumptions tell us. We would like our function to commute with limits, that is, we would like for any sequence $(x_n)$,

This is precisely condition (iii) of Theorem 4.3.2. of [1] defining the continuity of a function:

Theorem 4.3.2 (Characterizations of Continuity). Let $f: A \to \bm{R}$, and let

$c \in A$. The function $f$ is continuous at $c$ if and only if any one of the following

three conditions is met:

...

(iii) For all $(x_n) \to c$ (with $x_n \in A$), it follows that $f(x_n) \to f(c)$.

If we enforce that $T(x)$ must be continuous, then every real number $x$ is a Cauchy sequence of rational numbers, so assume $(x_n) \to x$ for rational $x_n$ and observe that

where we use that $T(x_n) = x_n$ from the fact that $T$ is identity on the rationals so we can conclude $T(x) = x$ for all real $x$. In summary, we have the following theorem:

Conclusion

This is just one of many reasons why the identity operator is perhaps the easiest possible operator to work with and analyze; for more details, see our soon-to-be released GitHub repository brownie-in-motion/identity which is joint work with Daniel Lu (brownie-in-motion) and Eshan Ramesh (eshrh).

It's well known [2] that Gilbert Strang's favorite matrix is the following -1, 2, -1 tridiagonal matrix (8) which forms a second-order finite difference approximation for the derivative.

$$\begin{aligned} \operatorname{strang}(n) &= \begin{pmatrix} 2 & -1 & & & & \\ -1 & 2 & -1 & & & \\ & -1 & \ddots & \ddots & & \\ & & \ddots & \ddots & -1 & \\ & & & -1 & 2 & -1 \\ & & & & -1 & 2 \\ \end{pmatrix} \end{aligned}$$

If I was asked upfront I'm not sure what my favorite linear operator would be, but the identity function/matrix/operator is definitely pretty high on the list after this discussion.

Lastly, this article is similar to Exercise 4.3.13 of [1] but I only discovered the connection after I already had the idea. A similar line of reasoning holds for the textbook exercise.