An arithmetic function is a real or complex-valued functions defined on the set of positive integers. Often, arithmetic functions reflect arithmetical information concerning integers and are intensively studied in number theory.
Defintion. An arithmetic function $f$ is said to be multiplicative if $f(1) = 1$ and $f(mn) = f(m)f(n)$ whenever $m$ and $n$ are relatively prime.
By unique factorization of integers, a multiplicative arithmetic function is determined completely by its values on all of the prime powers.
Examples. (i) Identity function $id$: $id(n) = n$.
(ii) Delta function $\delta$: $\delta(1) = 1, \delta(n) = 0$ for $n > 1$.
(iii) Constant one function $\mathbf{1}$: $\mathbf{1}(n) = 1$.
(iv) Moebius function $\mu$: $\mu(1) = 1$ and if $n$ is the product of $m$ distinct primes, then $\mu(n) = (-1)^m$, otherwise $\mu(n) = 0$.
The set of all multiplicative functions can be made into a commutative ring with identity with pointwise addition and the Dirichlet convolution defined below as multiplication.
Definition. Let $f$ and $g$ be multiplicative functions. The Dirichlet convolution of $f$ and $g$ is the arithmetic function $f * g$ defined by $$f * g(n) = \sum_{d \mid n} f(d)g(\frac{n}{d}).$$
Proposition. Let $f, g, h$ be multiplicative functions.
(i) $f * g$ is multiplicative.
(ii) $(f * g) * h = f * (g * h)$.
(iii) $f * g = g * f$.
(iv) $f * \delta = f$.
Hence the multiplicative identity for Dirichlet convolution is the delta function. Below we see that the multiplicative inverse of constant one function is Moebius function.
Proposition. $\mu * \mathbf{1} = \delta$.
Proof: Firstly, $\mu * \mathbf{1}(1) = \sum_{d \mid 1} \mu(d) = \mu(1) = 1 = \delta(1)$. Now let $n > 1$ with prime factorization $n = p_1^{k_1} \cdots p_m^{k_m}$. Then $$\begin{align*}
\mu * \mathbf{1}(n) &= \sum_{d \mid n} \mu(d) \\
&= \mu(1) + \mu(p_1) + \cdots + \mu(p_m) + \mu(p_1 p_2) + \cdots + \mu(p_{m - 1} p_m) + \cdots + \mu(p_1 \cdots p_m) \\
&= 1 + \binom{m}{1} (-1) + \binom{m}{2} (-1)^2 + \cdots + \binom{m}{m} (-1)^m \\
&= (1 - 1)^m = 0 = \delta(n).
\end{align*}$$ Q. E. D.
We now introduce an important arithmetic function in number theory, Euler's totient function $\phi$. For a positive integer $n$, $\phi(n)$ is the number of integers from 1 to $n$ which are relative prime to $n$.
Theorem. $\phi = \mu * id$.
Proof: $$\begin{align*}
\phi(n) &= \sum_{1 \leq k \leq n, (k, n) = 1} 1 = \sum_{k = 1}^n \delta((k, n)) \\
&= \sum_{k = 1}^n \mu * \mathbf{1}((k, n)) \\
&= \sum_{k = 1}^n \sum_{d \mid (k, n)} \mu(d) \\
&= \sum_{k = 1}^n \sum_{d \mid k, d \mid n} \mu(d) \\
&= \sum_{d \mid n} \sum_{1 \leq k \leq n, d \mid k} \mu(d) \\
&= \sum_{d \mid n} \sum_{1 \leq k \leq n, k = dm} \mu(d) \\
&= \sum_{d \mid n} \sum_{1 \leq m \leq n/d} \mu(d) \\
&= \sum_{d \mid n} \mu(d) \frac{n}{d} \\
&= \mu * id(n).
\end{align*}$$ Q. E. D.
Corollary. $\phi$ is multiplicative.
Another corollary is the classical formula by Euler.
Corollary. $\sum_{d \mid n} \phi(d) = n$, i.e, $\phi * \mathbf{1} = id$.
Proof: $\phi * \mathbf{1} = (\mu * id) * \mathbf{1} = (\mu * \mathbf{1}) * id = \delta * id = id$. Q. E. D.
Now we derive a formula for Euler's totient function in terms of prime factorizations.
Lemma. For a prime $p$ and positive integer $k$, $\phi(p^k) = p^k - p^{k - 1}$.
Proof: It suffices to note that the numbers between 1 and $p^k$ not relative prime to $p^k$ are $p, 2p, 3p, \ldots, p^{k - 1} \cdot p$. Q. E. D.
Theorem. Let $n > 1$ with prime factorization $n = p_1^{k_1} \cdots p_m^{k_m}$. Then $$\phi(n) = n(1 - \frac{1}{p_1}) \cdots (1 - \frac{1}{p_m}).$$
Proof: $\phi(n) = \prod_{j = 1}^m (p_j^{k_j} - p_j^{k_j - 1}) = \prod_{j = 1}^m p_j^{k_j} (1 - \frac{1}{p_j}) = n \prod_{j = 1}^m (1 - \frac{1}{p_j})$. Q. E. D.
Reference:
Apostol - Introduction to Analytic Number Theory
Tuesday, August 14, 2012
Friday, May 4, 2012
Additive subgroups of the reals and irrational rotation
We present a useful characterization of the additive subgroups of $\mathbb{R}$.
Theorem. Let $G$ be a subgroup of $(\mathbb{R}, +)$. Then precisely one of the following holds:
(i) $G = d\mathbb{Z}$ for some $d \in \mathbb{R}$;
(ii) $G$ is dense in $\mathbb{R}$.
Proof: If $G = \{0\}$, then $G = 0\mathbb{Z}$. Assume $G$ is nontrivial. Let \[ d = \inf\{g: 0 < g \in G\}.\] Note that $d \geq 0$ since for every nonzero $y \in G$, $ky \in G$ and $ky > 0$ for some $k \in \mathbb{Z}$.
Case 1: $d > 0$. We claim that $d \in G$. If not, then for every $\epsilon > 0$ there exists $g \in G$ with $g \in (d, d + \epsilon)$. It follows that for every $\epsilon > 0$ there are $g, h \in G$ such that $0 < g - h < \epsilon$, thus there exists $x \in G$ with $0 < x < \epsilon$ (let $x = g - h$). This contradicts to $d > 0$. We also have $d = \min\{|g|: 0 \neq g \in G\}$. Now fix any $0< g \in G$ and consider $S = \{g - nd: n = 0, 1, 2, \ldots\}$. The set $S$ is discrete, we can find $n \geq 0$ such that $g - nd \geq 0$ and $g - (n + 1)d < 0$. Since $g - nd, g - (n +1)d \in G$, $g - (n + 1)d \leq -d$, so $g - nd \leq 0$ and $g = nd$. Therefore $G = d\mathbb{Z}$.
Case 2: $d = 0$. Arguing as in the beginning of case 1, we find that 0 is a cluster point of $G \cap \mathbb{R}_+$. Let $(a, b)$ be any nonempty bounded open interval of $\mathbb{R}$. Take $\epsilon = b - a$ and pick some $g \in G \cap (0, \epsilon)$. For sufficiently large $n$, $ng \geq a$, and we take the smallest such $n$. Then $ng - g < a$, i.e. $ng \in (a - g, a]$, thus $ng + g \in (a, a + g] \subseteq (a, b)$. Therefore $G \cap (a, b) \neq \emptyset$. It follows that $G$ is dense in $\mathbb{R}$.
The above result can be used to prove the density of the orbit of an irrational rotation in the unit circle.
Corollary. (i) For an irrational $t$, $\mathbb{Z} + t\mathbb{Z}$ is dense in $\mathbb{R}$.
(ii) For an irrational $t$, $\{e^{2\pi int}: n \in \mathbb{Z}\}$ is dense in the unit circle.
Proof: (i) Note that $\mathbb{Z} + t\mathbb{Z}$ is a subgroup of $(\mathbb{R}, +)$. If $\mathbb{Z} + t\mathbb{Z} = a\mathbb{Z}$ for some $a \in \mathbb{R}$, then $1 = an$ for some $n \in \mathbb{Z}$, so $a \in \mathbb{Q}$. But $t = am$ for some $m \in \mathbb{Z}$, so $t \in \mathbb{Q}$, contradiction. By Theorem, $\mathbb{Z} + t\mathbb{Z}$ must be dense in $\mathbb{R}$.
(ii) Let $e^{2\pi i x}$ be a point on the unit circle. By (i), there exist sequences $m_k, n_k$ of integers such that $|m_k + n_k t - x| \rightarrow 0$. Then $|e^{2 \pi i n_k t} - e^{2 \pi i x}| = |e^{2\pi i x}||e^{2 \pi i (n_k t - x)} - 1| = |e^{2\pi i (m_k + n_k t - x)} - 1| = O(|m_k + n_k t - x|) \rightarrow 0$. Hence $\{e^{2\pi int}\}_{n \in \mathbb{Z}}$ is dense in the unit circle.
Proof: If $G = \{0\}$, then $G = 0\mathbb{Z}$. Assume $G$ is nontrivial. Let \[ d = \inf\{g: 0 < g \in G\}.\] Note that $d \geq 0$ since for every nonzero $y \in G$, $ky \in G$ and $ky > 0$ for some $k \in \mathbb{Z}$.
Case 1: $d > 0$. We claim that $d \in G$. If not, then for every $\epsilon > 0$ there exists $g \in G$ with $g \in (d, d + \epsilon)$. It follows that for every $\epsilon > 0$ there are $g, h \in G$ such that $0 < g - h < \epsilon$, thus there exists $x \in G$ with $0 < x < \epsilon$ (let $x = g - h$). This contradicts to $d > 0$. We also have $d = \min\{|g|: 0 \neq g \in G\}$. Now fix any $0< g \in G$ and consider $S = \{g - nd: n = 0, 1, 2, \ldots\}$. The set $S$ is discrete, we can find $n \geq 0$ such that $g - nd \geq 0$ and $g - (n + 1)d < 0$. Since $g - nd, g - (n +1)d \in G$, $g - (n + 1)d \leq -d$, so $g - nd \leq 0$ and $g = nd$. Therefore $G = d\mathbb{Z}$.
Case 2: $d = 0$. Arguing as in the beginning of case 1, we find that 0 is a cluster point of $G \cap \mathbb{R}_+$. Let $(a, b)$ be any nonempty bounded open interval of $\mathbb{R}$. Take $\epsilon = b - a$ and pick some $g \in G \cap (0, \epsilon)$. For sufficiently large $n$, $ng \geq a$, and we take the smallest such $n$. Then $ng - g < a$, i.e. $ng \in (a - g, a]$, thus $ng + g \in (a, a + g] \subseteq (a, b)$. Therefore $G \cap (a, b) \neq \emptyset$. It follows that $G$ is dense in $\mathbb{R}$.
The above result can be used to prove the density of the orbit of an irrational rotation in the unit circle.
Corollary. (i) For an irrational $t$, $\mathbb{Z} + t\mathbb{Z}$ is dense in $\mathbb{R}$.
(ii) For an irrational $t$, $\{e^{2\pi int}: n \in \mathbb{Z}\}$ is dense in the unit circle.
Proof: (i) Note that $\mathbb{Z} + t\mathbb{Z}$ is a subgroup of $(\mathbb{R}, +)$. If $\mathbb{Z} + t\mathbb{Z} = a\mathbb{Z}$ for some $a \in \mathbb{R}$, then $1 = an$ for some $n \in \mathbb{Z}$, so $a \in \mathbb{Q}$. But $t = am$ for some $m \in \mathbb{Z}$, so $t \in \mathbb{Q}$, contradiction. By Theorem, $\mathbb{Z} + t\mathbb{Z}$ must be dense in $\mathbb{R}$.
(ii) Let $e^{2\pi i x}$ be a point on the unit circle. By (i), there exist sequences $m_k, n_k$ of integers such that $|m_k + n_k t - x| \rightarrow 0$. Then $|e^{2 \pi i n_k t} - e^{2 \pi i x}| = |e^{2\pi i x}||e^{2 \pi i (n_k t - x)} - 1| = |e^{2\pi i (m_k + n_k t - x)} - 1| = O(|m_k + n_k t - x|) \rightarrow 0$. Hence $\{e^{2\pi int}\}_{n \in \mathbb{Z}}$ is dense in the unit circle.
Wednesday, May 2, 2012
Hadamard gap theorem
Definition. A sequence $\{n_k\}$ of nonnegative integers is said to be lacunary if there is some $\delta > 0$ such that $n_{k + 1}/n_k \geq 1 + \delta$ for all $k \geq 1$.
A typical example of a lacunary sequence is $n_k = 2^k$.
A typical example of a lacunary sequence is $n_k = 2^k$.
Theorem (Hadamard Gap Theorem). Suppose $\{n_k\}$ is a lacunary sequence and the power series $f(z) = \sum_{n = 0}^\infty a_n z^n$ with $a_n$ nonzero precisely when $n = n_k$ for some $k$ and has radius of convergence 1. Then $f(z)$ cannot be analytically extended to any larger region containing a point on the unit circle.
Proof: Suppose $f(z)$ extends to an analytic function on a region containing the open unit disk $B$ and a point $w_0$ on the unit circle. WLOG, we may assume $w_0 = 1$. Then $f(z)$ is analytic on a region $\Omega$ containing $B \cup \{1\}$. Define $g(w) = f(w^m(1 + w)/2)$ where $m$ is a positive integer. Since $1^m(1 + 1)/2 = 1$ and $|w^m(1+w)/2| = |w|^m|1+w|/2 < |w|^m \leq 1$ when $|w| \leq 1$ and $w \neq 1$ because $|1 + w| < 2$, so $g(w)$ is well-defined when $|w| \leq 1$, hence when $|w| < 1 + \epsilon$ for some $\epsilon > 0$. Write $g(w) = \sum_{m = 0}^\infty b_m w^m$ for $|w| < 1 + \epsilon$. Note that the powers of $w$ in the terms of $[w^m(1 + w)/2]^{n_k}$ range from $n_k m$ to $n_k (m + 1)$. Since $\{n_k\}$ is lacunary, we can choose $m$ to be so large that $n_{k + 1} m > n_k (m + 1)$ for all $k$, then the powers of $w$ in all of $[w^m(1 + w)/2]^{n_k}$ are distinct. Now
\[ \sum_{n = 0}^{n_k} a_n z^n = \sum_{m = 0}^{n_k (m + 1)} b_m w^m. \]
When $|w| < 1 + \epsilon$, RHS converges as $k \rightarrow \infty$. But LHS is the partial sums of $\sum_{k = 1}^\infty a_{n_k} z^{n_k}$ as $k$ varies, so the power series converges for all $z = w^m(1 + w)/2$ where $|w| < 1 + \epsilon$, which includes the case $z = 1$. The image of $B(0, 1 + \epsilon)$ under the map $w^m(1 + w)/2$ is an region $W$ containing 1, so the power series of $f(z)$ at 0 converges on $W$, contradicting its radius of convergence being 1. QED.
Reference:
Gamelin - Complex Analysis
Rudin - Real and Complex Analysis (3rd Ed.)
\[ \sum_{n = 0}^{n_k} a_n z^n = \sum_{m = 0}^{n_k (m + 1)} b_m w^m. \]
When $|w| < 1 + \epsilon$, RHS converges as $k \rightarrow \infty$. But LHS is the partial sums of $\sum_{k = 1}^\infty a_{n_k} z^{n_k}$ as $k$ varies, so the power series converges for all $z = w^m(1 + w)/2$ where $|w| < 1 + \epsilon$, which includes the case $z = 1$. The image of $B(0, 1 + \epsilon)$ under the map $w^m(1 + w)/2$ is an region $W$ containing 1, so the power series of $f(z)$ at 0 converges on $W$, contradicting its radius of convergence being 1. QED.
Reference:
Gamelin - Complex Analysis
Rudin - Real and Complex Analysis (3rd Ed.)
Subscribe to:
Posts (Atom)