Group Theory 7: Congruence Modulo $n$

 In this note, we study the congruence modulo $n$, $\equiv\mod n$ on $\mathbb{Z}$ more in depth. As seen here, $\equiv\mod n$ is an equivalence relation on $\mathbb{Z}$. It turns out that $\equiv\mod n$ is more than just an equivalence relation. $\equiv\mod n$ also preserves operations $+$ and $\cdot$ on $\mathbb{Z}$. (See #1 of Problem Set 5 here) Because of this, we can define an operation $+$ on the quotient set $\mathbb{Z}/\equiv\mod n$ so that it becomes a quotient group. In general, if an equivalence relation on an algebra preserves operations, it is called a congruence relation and a congruence relation allows us to define a quotient algebra, for example, a quotient group. Let $G$ be a group and $H\leq G$. We studied the equivalence relation $\sim$ on $G$: $\forall a,b\in G$,
$$a\sim b \Longleftrightarrow ab^{-1}\in H.$$ The equivalence relation $\sim$ is a congruence relation i.e. it preserves the group operation $\cdot$ if $H$ is a normal subgroup of $G$.

Let us recall that on $\mathbb{Z}$, $a\equiv b\mod n$, we say $a$ is congruent to $b$ modulo $n$, if $n|a-b$. The equivalence class of $a$
$$[a]=\{a+nk: k\in\mathbb{Z}\}$$ is called the congruence class of $a$. By Euclid's algorithm, $\forall b\in\mathbb{Z}$, $b=qn+r$ where $0\leq r<n$. This implies that $b\equiv r\mod n$ and so $[b]=[r]$. Hence, there are exactly $n$ distinct congruence classes $[0],[1],\cdots,[n-1]$. Let
$$\mathbb{Z}_n=\{[0],[1],\cdots,[n-1]\}.$$ That is, $\mathbb{Z}_n$ is the quotient set modulo the equivalence relation $\equiv\mod n$, $\mathbb{Z}/\equiv\mod n$. Define $+$ on $\mathbb{Z}_n$: $\forall [a],[b]\in\mathbb{Z}_n$,
$$[a]+[b]:=[a+b].$$ Then $+$ is well-defined on $\mathbb{Z}_n$. What this means is that $+$ is well-defined as a function $+:\mathbb{Z}_n\times\mathbb{Z}_n\longrightarrow\mathbb{Z}_n$. In other words, if $[a]=[a']$ and $[b]=[b']$ then $[a+b]=[a'+b']$. This can be shown straightforwardly and is left for the readers as an exercise. One can readily see that $(\mathbb{Z}_n,+)$ is an abelian group. Define $\cdot $ on $\mathbb{Z}_n$: $\forall [a],[b]\in\mathbb{Z}_n$,
$$[a]\cdot[b]:=[ab].$$ Then $\cdot$ is also well-defined on $\mathbb{Z}_n$. However, $(\mathbb{Z}_n,\cdot)$ is not a group. $\forall [a]\in\mathbb{Z}_n$, $[0][a]=[0]$ and $[1]$ is the identity for the multiplication, so $[0]$ does not have a multiplicative inverse. Would the nonzero elements of $\mathbb{Z}_n$ form a group then? The answer is no. For instance, in $\mathbb{Z}_6$, $[2],[3]\ne [0]$ but $[2][3]=[6]=[0]$. Such elements like $[2]$ and $[3]$ in $\mathbb{Z}_6$ are called zero divisors. So, is there a subset of $\mathbb{Z}_n$ that forms a group under $\cdot$? The answer is affirmative. Let $\mathbb{Z}_n^\ast=\{[a]\in\mathbb{Z}_n: (a,n)=1\}$. First, note that for $[a]=[b]$, $(a,n)=1$ if and only if $(b,n)=1$. This can be proved by contrapositive. Suppose that $[a]=[b]$. Then $a\equiv b\mod n\Rightarrow a-b=nk$ for some $k\in\mathbb{Z}$. If $(b,n)=d>1$ then since $d|b$ and $ d|n$, $d|a=b+nk\Rightarrow (a,n)\ne 1$. In the same manner, it can be also shown that if $(a,n)\ne 1$ then $(b,n)\ne 1$. Recall the property that if $(a,n)=1$ and $(b,n)=1$, then $(ab,n)=1$. (# 4 of Problem Set 1 here.) This implies that $[a][b]=[ab]\in\mathbb{Z}_n^\ast$. Now suppose that $[a][b]=[a][c]$. Then
\begin{align*}
[ab]=[ac]&\Longrightarrow n|a(b-c)\\
&\Longrightarrow n|b-c\ (\mbox{since}\ (a,n)=1)\\
&\Longrightarrow [b]=[c].
\end{align*}
That is, $\mathbb{Z}_n^\ast$ has the cancellation property, so $(\mathbb{Z}_n^\ast,\cdot)$ is a group. (See # 2 of Problem Set 5 here.) In some textbooks, $\mathbb{Z}_n^\ast$ is also denoted by $U_n$. The order of $\mathbb{Z}_n^\ast$ is the number of integers $1\leq m<n$ such that $(m,n)=1$.

Definition. The Euler $\varphi$-function, $\varphi(n)$, is defined by $\varphi(1)=1$ and for $n>1$, $\varphi(n)=$ the number of positive integers $m$ with $1\leq m<n$ such that $(m,n)=1$. Hence, $|\mathbb{Z}_n^\ast|=\varphi(n)$. If $n=p$, a prime, then $\varphi(p)=p-1$.

Note that the Euler $\varphi$-function is multiplicative, namely if $(m,n)=1$, then $\varphi(mn)=\varphi(m)\varphi(n)$.

Example. $\varphi(8)=4$, $\varphi(15)=8$.

Example.
\begin{align*}
\mathbb{Z}_8^\ast&=\{[1],[3],[5],[7]\},\\
\mathbb{Z}_{15}^\ast&=\{[1],[2],[4],[7],[8],[11],[13],[14]\}.
\end{align*}

Example. $\mathbb{Z}_9^\ast=\{[1],[2],[4],[5],[7],[8]\}$.
\begin{align*}
[2]^1&=[2],\ [2]^2=[4],\ [2]^3=[8],\ [2]^4=[16]=[7],\\
[2]^5&=[32]=[5],\ [2]^6=[2][2]^5=[2][5]=[10]=[1].
\end{align*}
Hence, $\mathbb{Z}_9^\ast$ is a cyclic group $\mathbb{Z}_9^\ast=\langle[2]\rangle$.

As a summary,

Theorem. $\mathbb{Z}_n^\ast$ forms an abelian group under the product $[a][b]=[ab]$, of order $\varphi(n)$, where $\varphi(n)$ is the Euler $\varphi$-function.

Theorem. [Euler]
If $(a,n)=1$ then $a^{\varphi(n)}\equiv 1\mod n$.

Proof. Since $\mathbb{Z}_n^\ast$ is a group of order $\varphi(n)$, $[a]^{\varphi(n)}=[1]$, $\forall [a]\in\mathbb{Z}_n^\ast$. So,
$$[a^{\varphi(n)}]=[a]^{\varphi(n)}=[1]\Longrightarrow a^{\varphi(n)}\equiv 1\mod n.$$

Corollary. [Fermat]

If $p$ is a prime and $p\not | a$, then
$$a^{p-1}\equiv 1\mod p.$$
For any integer $b$, $b^p\equiv b\mod p$. This corollary is usually called Fermat's Little Theorem.

Proof. If $p$ is a prime and $p\not |a$, then $(a,p)=1$, so by the preceding theorem,
$$a^{\varphi(p)}=a^{p-1}\equiv 1\mod p$$
For any integer $b$, if $p\not b$ then
$$b^{p-1}\equiv 1\mod p\Rightarrow b^p=b^{p-1}b\equiv b\mod p,$$
since $\equiv\mod p$ preserves multiplication. One can also show that using only the definition of $\equiv\mod p$:
\begin{align*}
b^{p-1}\equiv 1\mod p &\Longrightarrow b^{p-1}-1=pk\ \mbox{for some integer}\ k\\
&\Longrightarrow b^p-b=p(bk)\\
&\Longrightarrow b^p\equiv b\mod p.
\end{align*}
If $p|b$, then $b\equiv 0\mod p\Longrightarrow b^p\equiv 0\mod p$. Hence, for any $b\in\mathbb{Z}$, $b^p\equiv b\mod p$.

Example. Compute the remainder of $8^{103}$ when it is divided by 13.

Solution. Since 13 is a prime and $13\not|8$, by Fermat's Little Theorem we have
$$8^{13-1}=8^{12}\equiv 1\mod 13.$$ Dividing 103 by 13, we obtain $103=12\cdot 8+7$. So,
\begin{align*}
8^{103}&= (8^{12})^88^7\\
&\equiv 8^7\mod 13\\
&\equiv (-5)^7\mod 13\ (8\equiv -5\mod 13)\\
&\equiv (25)^3(-5)\mod 13\\
&\equiv (-1)^3(-5)\equiv 5\mod 13\ (25\equiv -1\mod 13).
\end{align*}

Example. Show that $2^{11,213}-1$ is not divisible by 11.

Solution. Since $11$ is a prime and $11\not| 2$, by Fermat's Little Theorem we have $$2^{11-1}=2^{10}\equiv 1\mod 11.$$
$11,213=10\cdot 1,121+3$, so
\begin{align*}
2^{11,213}-1&= (2^{10})^{1,121}\cdot 2^3-1\\
&\equiv 2^3-1\mod 11\\
&\equiv 7\mod 11.
\end{align*}
Hence, when $2^{11,213}-1$ is divided by 11, the remainder is 7.

The number $11,213$ is a prime and $2^{11,213}-1$ is also a prime. In number theory, primes of the form $2^p-1$ where $p$ is a prime are called Mersenne primes.

NT: Linear Combinations

 Theorem 1. Given integers $a$, $b$, and $c$ with $a$ and $b$ not both $0$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=c$ if and only if $(a,b)|c$.

Proof. Left as an exercise. See Number Theory Problem Set 2 #4.

Corollary. Let $a$ and $b$ be integers. Then there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$ if and only if $(a,b)=1$ i.e. $a$ and $b$ are relatively prime.

Corollary. Let $a,a',b\in\mathbb{Z}$. If $(a,b)=1$ and $(a',b)=1$, then $(aa',b)=1$.

Proof. Since $(a,b)=1$ and $(a',b)=1$, there exist $x,y,x',y'\in\mathbb{Z}$ such that $ax+by=1$ and $a'x'+by'=1$. Now,
 \begin{align*}
  1&=(ax+by)(a'x'+by')\\
   &=aa'xx'+b(axy'+a'x'y+byy')
 \end{align*}
Hence, $(aa',b)=1$.

Theorem 2. If $a,b$ and $c$ are integers such that $(a,b)=1$ and $a|bc$, then $a|c$.

Proof. Since $(a,b)=1$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=1$. So, we obtain $acx+bcy=c$. Since $a|ac$ and $a|bc$, $a|c$.

Remark. $a|bc$ does not necessarily imply that $a|b$ or $a|c$. For example, $6|36=4\cdot 9$ but $6\not|4$ and $6\not|9$. However, the following theorem holds.

Theorem. If $p$ is a prime number and $p|ab$, then $p|a$ or $p|b$.

Proof. Let $p$ be a prime number and $p|ab$. Suppose that $p\not|a$ and $p\not|b$. Since $p$ is prime and $p\not|a$, $(p,a)=1$ and so $px+ay=1$ for some $x,y\in\mathbb{Z}$. Now, $p|pbx+aby=b$ but this is a contradiction to the assumption that $p\not|b$. Therefore, $p|a$ or $p|b$.

The following proof is essentially the same as the above proof. But instead of proving the statement indirectly by contradiction, it proves the statement directly. It is always good to practice different ways of proving a statement.

Proof. Let $p$ be a prime number and $p|ab$. If $p|a$, we are done. Suppose that $p\not|a$. Then since $p$ is prime, $(p,a)=1$ and so $px+ay=1$ for some $x,y\in\mathbb{Z}$. Now, $p|pbx+aby=b$. This completes the proof.

Theorem. If $a$ and $b$ are integers and $(a,b)=d$, then $\frac{a}{d}$ and $\frac{b}{d}$ are relatively prime.

Proof. Since $(a,b)=d$, there exist $x,y\in\mathbb{Z}$ such that $ax+by=d$. Dividing the equation by $d$, we obtain
 $\frac{a}{d}x+\frac{b}{d}y=1$. By theorem 1, this implies that $\left(\frac{a}{d},\frac{b}{d}\right)=1$.

Example. Consider the equation $9x+24y=15$. Since $(9,24)=3$ and $3|15$, from theorem 1, we know that a solution exist. First, we can find a solution to $9x+24y=3$ using the Euclidean algorithm as seen before.
 \begin{align*}
  24&=9\cdot 2+6\\
   9&=6\cdot 1+3\\
   6&=3\cdot 2+0
 \end{align*}
Thus,
\begin{align*}
   3&=9-6\cdot 1\\
    &=9-(24-9\cdot 2)\cdot 1\\
    &=9\cdot 3+24\cdot(-1)
\end{align*}
Hence, $x'=3$ and $y'=-1$ is a solution to $9x+24y=3$ and thereby $x=5x'=15$ and $y=5y'=-5$ is a solution to $9x+24y=15$. Finding a solution is not a big deal. But there are other solutions. For instance, $x=-1$ and $y=1$ is also a solution to $9x+24y=15$. How do we find other solutions? We now turn our attention to this question.

Suppose that $(x_0,y_0)$ is a solution to
$$
 ax+by=c \tag{1}
$$
Then
$$
 ax_0+by_0=c \tag{2}
$$
Subtracting (2) from (1), we obtain
$$
a(x-x_0)=b(y_0-y) \tag{3}
$$
Let $d=(a,b)$. Dividing (3) by $d$, we obtain
$$
\frac{a}{d}(x-x_0)=\frac{b}{d}(y_0-y) \tag{4}
$$
This means that $\frac{a}{d}|\frac{b}{d}(y_0-y)$. Since $\left(\frac{a}{d},\frac{b}{d}\right)=1$, by theorem 2, $\frac{a}{d}|y_0-y$ and so, $y_0-y=\frac{a}{d}t$ for some $t\in\mathbb{Z}$. From (4) we also obtain $x-x_0=\frac{b}{d}t$. Therefore, $x$ and $y$ are written as
$$
  x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t \tag{5}
$$
where $t\in\mathbb{Z}$. Conversely, any $(x,y)$ in the form (5) satisfies the equation (1).
$$a\left(x_0+\frac{b}{d}t\right)+b\left(y_0-\frac{a}{d}t\right)=ax_0+by_0=c$$

Theorem 3. Suppose that $a\ne 0$, $b\ne 0$, and $c$ are integers. Let $(x_0,y_0)$ be a particular solution to $ax+by=c$. Then all solutions to $ax+by=c$ are given by
 $$x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$$
 where $t\in\mathbb{Z}$ and $(a,b)=d$.

Example. In preceding example, we found $(x_0,y_0)=(15,-5)$. So by theorem 3, all solutions to $9x+24y=15$ are given by
$$x=15+8t,\ y=-5-3t$$
where $t\in\mathbb{Z}$.

Example. Find all positive integers $x,y$ such that $4x+6y=100$.

Solution. $(4,6)=2$ and $2|100$, so a solution exists.
$6=4\cdot 1+2$ i.e. $2=4\cdot (-1)+6\cdot 1$. $x_0=-50$ and $y_0=50$ is a particular solution to $4x+6y=100$. By theorem 3, all solutions are given by
$$x=-50+3t,\ y=50-2t$$
where $t\in\mathbb{Z}$. Since $x$ and $y$ are required to be positive, we find that $17\leq t\leq 24$. The following table shows all those solutions.
$$
\begin{array}{|c||c|c|c|c|c|c|c|c|}
\hline
t & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24\\
\hline
x & 1 & 4 & 7 & 10 & 13 & 16 & 19 & 22\\
\hline
y & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2\\
\hline
\end{array}
$$

Example. A man paid 11.37 dollars for some 39-cent pens and 69-cent pens. How many of each did he buy?

Solution. The problem is equivalent to solving the equation
$$
39x+69y=1137 \tag{6}
$$
where $x$ and $y$ are nonnegative integers. $(39,69)=3$ and $3|1137$, so the equation has a solution. Solving the equation (6) is equivalent to solving
$$
13x+23y=379 \tag{7}
$$
where $x$ and $y$ are nonnegative integers. Since $(13,23)=1$, by the Euclidean algorithm, one can find a solution $x'=-7$ and $y'=4$ to $13x+23y=1$. $x_0=379x'=-2653$ and $y_0=379\cdot y'=1516$ is then a solution to (7). By theorem 3, all integer solutions to (7) are given by
$$x=-2653+23t,\ y=1516-13t,\ t\in\mathbb{Z}$$
From the conditions $x\geq 0, y\geq 0$, we obtain the inequality $115\frac{8}{23}\leq t\leq 116\frac{8}{23}$. There is only one integer $t=116$ that satisfies the inequality. $x=-2653+23\cdot 116=15$ and $y=1516-13\cdot 116=8$. So, the man bought 15 39-cent pens and 8 69-cent pens.

The Binomial Asset Pricing Model: One-Period Binomial Model

In this note, we model stock prices in discrete time, assuming that at each step the price per share of stock will be one of two possible values determined by the outcome of a coin toss.

Let $S_0$ be the initial stock price. We introduce two numbers  $u$ and $d$  with $0<d<u$ such that the stock price will be either $dS_0$ or $uS_0$ at the next period. Suppose that we are tossing a coin and when we get a Head ($H$) the stock price goes up and when we get a Tail ($T$), the price goes down. Denote the price at time $1$ by $S_1(H)=uS_0$ if the toss results in $H$ and by $S_1(T)=dS_0$ if the toss results in $T$. After the second toss the price will be one of
\begin{align*}
 S_2(HH)&=uS_1(H)=u^2S_0,\ S_2(HT)=dS_1(H)=duS_0,\\
 S_2(TH)&=uS_1(T)=udS_0,\ S_2(TT)=dS_1(T)=d^2S_0
\end{align*}
Suppose that the 3rd toss is the last one. Then
$$\Omega=\{HHH, HHT, HTH, THH, THT, TTH, TTT\}$$
is the set of all possible outcomes of the three tosses. $\Omega$ is called the sample space for the experiment and each $\omega\in\Omega$ is called a sample point.

We now introduce a money market with interest $r$. We take $r$ to be the interest rate for both borrowing and lending. One dollar invested in the money market at time $0$ will yield $(1+r)$ dollars at time $1$. One dollar borrowed from the money market at time $0$ will result in a debt of $(1+r)$ dollars at time $1$.

In this model, we assume no arbitrage. So, we require that $0<d<1+r<u$ for one-period binomial model. If $d\geq 1+r$, one can start with no money and borrow from the money market to buy the stock. Even in the case of a tail, the stock at time $1$ will be worth enough to pay off the money market debt. This provides an arbitrage. On the other hand, if $u\leq r+1$, one can sell the stock short and invest the proceeds in the money market. Even in the case of a head, the cost of replacing it at time $1$ will be less than or equal to the value of the money market investment. This again provides an arbitrage.

We now consider a European call option, which confers on its owner the right but not the obligation to buy one share of the stock at time $1$ for the strike price of $K$. We assume that $S_1(T)<K<S_1(H)$. If we get a tail, the option expires worthless. If we get a head, the option can be exercised and yields a profit of $S_1(H)-K$. This situation can be described as saying the option at time $1$ is worth $(S_1-K)^+$ where $(S_1-K)^+=\max\{S_1(\omega_1)-K,0\}$.

Example. Let $S_0=4$, $u=2$, $d=\frac{1}{2}$, and $r=\frac{1}{4}$. Then $S_1(H)=8$ and $S_1(T)=2$. Suppose the strike price of the European call option is $K=5$. Suppose we begin with the initial wealth $X_0=1.20$ and buy $\Delta_0=\frac{1}{2}$ shares of stock at time $0$. Since the stock costs $4$ per share at time $0$, we must use our initial wealth $X_0=1.20$ and borrow an additional $0.80$ to buy $\frac{1}{2}$ shares of stock. This leaves us with a cash position $X_0-\Delta_0S_0=-0.80$ (i.e. a debt of $0.80$ to the money market). At time $1$, our cash position will be $(1+r)(X_0-\Delta_0S_0)=-1$. On the other hand, at time $1$ we will have stock valued at either $\frac{1}{2}S_1(H)=4$ or $\frac{1}{2}S_1(T)=1$. If the coin toss results in a head, the value of our portfolio of stock and money market account at time $1$ will be
 $$X_1(H)=\frac{1}{2}S_1(H)+(1+r)(X_0-\Delta_0S_0)=3$$
 If the coin toss results in a tail, the value of our portfolio at time $1$ will be
 $$X_1(T)=\frac{1}{2}S_1(T)+(1+r)(X_0-\Delta_0S_0)=0$$
 In either case, the value of the portfolio agrees with the value of the option at time $1$, which is either $(S_1(H)-5)^+=3$ or $(S_1(T)-5)^+=0$. We have replicated the option by trading in the stock and money markets.

In the one-period model, a derivative security is a security that pays $V_1(H)$ at time $1$ if the coin toss results in $H$ and pays $V_1(T)$ at time $1$ if the coin toss results in $T$. We want to determine the price $V_0$, i.e. how much the option is worth at time $0$. Suppose that we begin we begin with wealth $X_0$ and buy $\Delta_0$ shares of stock at time $0$. This leaves us with a cash position $X_0-\Delta_0S_0$. The value of our portfolio of stock and money market account at time $1$ is
\begin{align*}
 X_1&=\Delta_0S_1+(1+r)(X_0-\Delta_0S_0)\\
 &=(1+r)X_0+\Delta_0(S_1-(1+r)S_0)
\end{align*}
We want to choose $X_0$ and $\Delta_0$ so that $X_1(H)=V_1(H)$ and $X_1(T)=V_1(T)$. Replication of the derivative security requires that
\begin{align*}
 (1+r)X_0+\Delta_0(S_1(H)-(1+r)S_0)&=V_1(H) \tag{1}\\
 (1+r)X_0+\Delta_0(S_1(T)-(1+r)S_0)&=V_1(T) \tag{2}
\end{align*}
Subtracting (2) from (1), we have
$$V_1(H)-V_1(T)=\Delta_0(S_1(H)-S_1(T))$$
Solving this for $\Delta_0$ we obtain
$$
 \Delta_0=\frac{V_1(H)-V_1(T)}{S_1(H)-S_1(T)} \tag{3}
$$
(3) is called the delta-hedging formula. (1) along with (3) can be solved for $X_0$ as
$$
X_0=\frac{1}{1+r}\left[\frac{1+r-d}{u-d}V_1(H)+\frac{u-(1+r)}{u-d}V_1(T)\right] \tag{4}
$$
Introducing new variables $a$ and $b$ such that $u=1+a$ and $d=1+b$, (4) can be written as
$$
 X_0=\frac{1}{1+r}\left[\frac{r-b}{a-b}V_1(H)+\frac{a-r}{a-b}V_1(T)\right] \tag{5}
$$
To summarize, if an agent begins with wealth $X_0$ given by (5) and at time $0$ buys $\Delta_0$ shares of stock given by (3), then at time $1$, if the coin toss results in $H$, the agent will have a portfolio worth $V_1(H)$, and if the coin toss results in $T$, the portfolio will be worth $V_1(T)$. The agent hedged a short position in the derivative security. The derivative security that pays $V_1$ at time $1$ should be priced at
$$
 V_0=\frac{1}{1+r}\left[\frac{r-b}{a-b}V_1(H)+\frac{a-r}{a-b}V_1(T)\right] \tag{6}
$$
at time $0$. This price allows the seller to hedge the short position in the claim.

Let
$$
p=\frac{r-b}{a-b}\ \mathrm{and}\ q=\frac{a-r}{a-b} \tag{7}
$$
Then $p+q=1$, and (5) and (6) can be written as
$$
V_0=X_0=\frac{1}{1+r}[pV_1(H)+qV_1(T)] \tag{8}
$$
Alternatively, (8) can be written as
$$
 V_0=\frac{1}{1+r}[p(S_0(a+1)-K)^++(1-p)(S_0(b+1)-K)^+] \tag{9}
$$
Can $p$ be interpreted as a probability? Suppose that the stock price goes up from $S_0$ to $uS_0$ with probability (Note this $q$ is different from $q$ in (7)) $q$ and it goes down from $S_0$ to $dS_0$ with probability $1-q$. If investors were risk-neutral, the expected rate of return on the stock would be the riskless interest rate, so we have
$$q(uS_0)+(1-q)(dS_0)=(1+r)S_0$$
Solving this equation for $q$, we obtain
$$q=\frac{1+r-d}{u-d}=p$$
Hence, the value of the call can be interpreted as the expectation of its discounted future value in a risk-neutral world.

A Glossary of Finance:

1. Arbitrage: Arbitrage is the simultaneous purchase and sale of the same or similar asset in different markets in order to profit from tiny differences in the asset's listed price. It exploits short-lived variations in the price of identical or similar financial instruments in different markets or in different forms. 
2. derivative:  The term derivative refers to a type of financial contract whose value is dependent on an underlying asset, group of assets, or benchmark. A derivative is set between two or more parties that can trade on an exchange or over-the-counter (OTC). These contracts can be used to trade any number of assets and carry their own risks. Prices for derivatives derive from fluctuations in the underlying asset. These financial securities are commonly used to access certain markets and may be traded to hedge against risk. Derivatives can be used to either mitigate risk (hedging) or assume risk with the expectation of commensurate reward (speculation). Derivatives can move risk (and the accompanying rewards) from the risk-averse to the risk seekers. 
3. European call option: A European option is a version of an options contract that limits execution to its expiration date. In other words, if the underlying security such as a stock has moved in price, an investor would not be able to exercise the option early and take delivery of or sell the shares. Instead, the call or put action will only take place on the date of option maturity.
4. hedge: To hedge, in finance, is to take an offsetting position in an asset or investment that reduces the price risk of an existing position. A hedge is therefore a trade that is made with the purpose of reducing the risk of adverse price movements in another asset. Normally, a hedge consists of taking the opposite position in a related security or in a derivative security based on the asset to be hedged. Derivatives can be effective hedges against their underlying assets because the relationship between the two is more or less clearly defined. Derivatives are securities that move in correspondence to one or more underlying assets. They include options, swaps, futures, and forward contracts. The underlying assets can be stocks, bonds, commodities, currencies, indexes, or interest rates. It's possible to use derivatives to set up a trading strategy in which a loss for one investment is mitigated or offset by a gain in a comparable derivative. 
5. Option:  The term option refers to a financial instrument that is based on the value of underlying securities such as stocks, indexes, and exchange traded funds (ETFs). An options contract offers the buyer the opportunity to buy or sell-depending on the type of contract they hold-the underlying asset. Unlike futures, the holder is not required to buy or sell the asset if they decide against it. Each options contract will have a specific expiration date by which the holder must exercise their option. The stated price on an option is known as the strike price. Options are typically bought and sold through online or retail brokers. 
6. Short position: A short, or a short position, is created when a trader sells a security first with the intention of repurchasing it or covering it later at a lower price. A trader may decide to short a security when she believes that the price of that security is likely to decrease in the near future. There are two types of short positions: naked and covered. A naked short is when a trader sells a security without having possession of it. However, that practice is illegal in the U.S. for equities. It is banned fully in India and other countries. A covered short is when a trader borrows the shares from a stock loan department; in return, the trader pays a borrowing rate during the time the short position is in place. In the futures or foreign exchange markets, short positions can be created at any time. 
7. Short selling: Short selling is an investment or trading strategy that speculates on the decline in a stock or other security's price. It is an advanced strategy that should only be undertaken by experienced traders and investors.
   

Complex Line Integrals 1: Complex Line Integrals

Let $f(z): \mathcal{R}\longrightarrow\mathbb{C}$ be a piecewise continuous function defined in a domain $\mathcal{R}$ and let $C$ be the differentiable curve $\gamma(t): [a,b]\longrightarrow\mathcal{R}$. Here we assume that $\gamma(t)$ is differentiable on an open interval containing $[a,b]$. The complex line integral of $f(z)$ along the curve $C$, $\int_Cf(z)dz$ is defined to be
$$
\int_Cf(z)dz=\int_a^bf(\gamma(t))\gamma'(t)dt
$$

The complex line integral of $f(z)$ along the curve $C$ satisfies the following properties.

Theorem.
\begin{align*}
\int_Cz_0f(z)dz&=z_0\int_Cf(z)dz \tag{1}\\
\int_C[f(z)+g(z)]dz&=\int_Cf(z)dz+\int_Cg(z)dz \tag{2}
\end{align*}
These two properties (1) and (2) imply that $\int_Cf(z)dz$ is linear.

Let $-C$ denote the same curve as $C$ with opposite orientation. Let $C$ be $\gamma(t): [a,b]\longrightarrow\mathcal{R}$. Then $-C$ is defined by $\gamma(\tau)$ where $\tau=a+b-t$.
\begin{align*}
\int_{-C}f(z)dz&=\int_b^a f(\gamma(\tau))\gamma'(\tau)d\tau\\
&=-\int_a^bf(\gamma(t))\gamma'(t)dt\\
&=-\int_Cf(z)dz
\end{align*}
Hence, we have
$$
\int_{-C}f(z)dz=-\int_Cf(z)dz
$$

Suppose that $C$ is a path that consists of a path $C_1$:  $\gamma(t)$, $a\leq t\leq c$ followed by a path $C_2$: $\gamma(t)$, $c\leq t\leq b$. Then
\begin{align*}
\int_{C_1}f(z)dz+\int_{C_2}f(z)dz&=\int_a^cf(\gamma(t))\gamma'(t)dt+\int_c^bf(\gamma(t))\gamma'(t)dt\\
&=\int_a^bf(\gamma(t))\gamma'(t)dt\\
&=\int_Cf(z)dz
\end{align*}
Hence, we have
$$
\int_Cf(z)dz=\int_{C_1}f(z)dz+\int_{C_2}f(z)dz
$$

Example. Evaluate the integral $\int_C\bar z dz$ where $C$ is the right half of the circle $|z|=2$.

Solution. Let $C$: $\gamma(\theta)=2e^{i\theta}$, $-\frac{\pi}{2}\leq\theta\leq\frac{\pi}{2}$. Then
\begin{align*}
\int_C\bar z dz&=\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}\overline{2e^{i\theta}}(2e^{i\theta})'d\theta\\
&=4i\int_{-\frac{\pi}{2}}^{\frac{\pi}{2}}d\theta=4\pi i
\end{align*}

Remark. The result in the preceding example can be used to evaluate $\int_C\frac{1}{z}dz$ where $C$ is the same path in the example.
\begin{align*}
\int_C\frac{1}{z}dz&=\int_C\frac{\bar z}{z\bar z}dz\\
&=\int_C\frac{\bar z}{|z|^2}dz\\
&=\frac{1}{4}\int_C\bar z dz\ (|z|=2)\\
&=\pi i
\end{align*}

Example. Let $C_1$ denote the path $OAB$ and $C_2$ denote the path $OB$ in figure 1. 

Figure 1. Path dependence

Evaluate the integrals $\int_{C_1}f(z)dz$ and $\int_{C_2}f(z)dz$, where $f(z)=y-x-i3x^2$ ($z=x+iy$).

Solution. The path $OAB$ can be represented by
$$
\gamma(t)=\left\{\begin{array}{ccc}
it & \mbox{if} & 0\leq t\leq 1\\
(t-1)+i & \mbox{if} & 1\leq t\leq 2
\end{array}
\right.
$$
Thus,
\begin{align*}
\int_{C_1}f(z)dz&=\int_0^1f(\gamma(t))\gamma'(t)dt+\int_1^2f(\gamma(t))\gamma'(t)dt\\
&=i\int_0^1tdt+\int_1^2[2-t-i3(t-1)^2]dt\\
&=\frac{1-i}{2}
\end{align*}
Alternatively, the path $OA$ can be represented by $z=0+iy$, $0\leq y\leq 1$, while the path $AB$ can be represented by $z=x+i$, $0\leq x\leq 1$. Hence, we have
\begin{align*}
\int_{C_1}f(z)dz&=\int_{\overline{OA}}f(z)dz+\int_{\overline{AB}}f(z)dz\\
&=i\int_0^1ydy+\int_0^1(1-x-i3x^2)dx\\
&=\frac{1-i}{2}
\end{align*}
$C_2$ can be represented by $z=x+ix$, $0\leq x\leq 1$ and
\begin{align*}
\int_{C_2}f(z)dz&=\int_0^1-i3x^2(1+i)dx\\
&=3(1-i)\int_0^1x^2dx\\
&=1-i.
\end{align*}
As seen in this example, while the two paths $C_1$ and $C_2$ have the same initial and terminal points, the integrals $\int_{C_1}f(z)dz$ and $\int_{C_2}f(z)dz$ have different values. This means that the line integrals are in general depend on the paths.

Homology: Homology Groups

Definition. Let $K$ be an $n$-dimensional simplicial complex. The $r$-th homology group $H_r(K)$, $0\leq r\leq n$, associated with $K$ is defined by
$$H_r(K)=Z_r(K)/B_r(K)$$

In the last theorem here, we have seen that $B_r(K)\subset Z_r(K)$, so the definition of a homology group makes sense.

The $r$-th homology group $H_r(K)$ can be written as the set of equivalence classes
$$H_r(K)=\{[z]: z\in Z_r(K)\}$$
where $[z]=z+B_r(K)$. Each equivalence class $[z]$ of an $r$-cycle $z\in Z_r(K)$ is called a homology class. Two $r$-cycles $z$ and $z'$ are in the same equivalent class if and only if $z-z'\in B_r(K)$. In this case, we say $z$ is homologous to $z'$ and write $z\sim z'$.

We are interested in studying homology groups because they are topological invariants as seen in the following theorem.

Theorem 1. Let $X$ be homeomorphic to $Y$ and let $(K,f)$ and $(L,g)$ be triangulations of $X$ and $Y$ respectively. Then we have
$$H_r(K)\cong H_r(L),\ r=0,1,2,\cdots$$
In particular, if $(K,f)$ and $(L,g)$ are two triangulations of $X$, then
$$H_r(K)\cong H_r(L),\ r=0,1,2,\cdots$$
Here, $\cong$ means "is isomorphic to" of course.

One can speak of homological groups of a topological space $X$ which is not necessarily a simplicial complex as long as it is triangulable. For an arbitrary triangulation $(K,f)$, $H_r(X)$ is defined to be
$$H_r(X):=H_r(K),\ r=0,1,2,\cdots$$

Example. Let $K=\{p_0\}$. Since $\dim K=0$, $H_r(K)=0$ for all $r\geq 1$. The $0$-chain is $C_0(K)=\{ip_0: i\in\mathbb{Z}\}\cong\mathbb{Z}$. $Z_0(K)=C_0(K)$ and $B_0(K)=0$ (since $K$ has no $1$-simplexes). Thus,
$$H_0(K)=Z_0(K)/B_0(K)\cong\mathbb{Z}$$

Theorem 2. If $K$ is a contractible space i.e. if it has the homotopy type of a single point then
$$
H_r(K)=\left\{\begin{array}{ccc}
0 & \mbox{if} & r\ne 0\\
\mathbb{Z} & \mbox{if} & r=0
\end{array}\right.
$$

If $K$ is a $2$-dimensional space, then $K$ is contractible if and only if it has no holes.

Exercise. Let $K=\{p_0,p_1\}$. Compute the homology groups of $K$ to confirm that $H_0(K)=\mathbb{Z}\oplus\mathbb{Z}$ and $H_r(K)=0$ for all $r\geq 1$.

Exercise. Let $K=\{p_0,p_1,(p_0p_1)\}$. Compute the homology groups of $K$ to confirm that $H_0(K)=\mathbb{Z}$ and $H_r(K)=0$ for all $r\geq 1$.

Example. Let $K=\{p_0,p_1,p_2,(p_0p_1),(p_1p_2),(p_2p_0)\}$. $K$ is a triangulation of $S^1$. Since $\dim K=1$, $H_r(K)=0$, $\forall r\geq 2$. $C_0(K)=Z_0(K)=\mathbb{Z}\oplus\mathbb{Z}\oplus\mathbb{Z}$.
\begin{align*}
B_0(K)&=\{l\partial_1(p_0p_1)+m\partial_1(p_1p_2)+n\partial_1(p_2p_0): l,m,n\in\mathbb{Z}\}\\
&=\{l(p_1-p_0)+m(p_2-p_1)+n(p_0-p_2): l,m,n\in\mathbb{Z}\}\\
&=\{(n-l)p_0+(l-m)p_1+(m-n)p_2:l,m,n\in\mathbb{Z}\}
\end{align*}
Note that $(n-l)+(l-m)+(m-n)=0$. Define $f:Z_0(K)\longrightarrow\mathbb{Z}$ by $f(ip_0+jp_1+kp_3)=i+j+k$. Then $f$ is an onto homomorphism.
\begin{align*}
ip_0+jp_1+kp_3\in\ker f&\Leftrightarrow i+j+k=0\\
&\Leftrightarrow ip_0+jp_1+kp_3\in b_0(K)
\end{align*}
Hence, $\ker f=B_0(K)$ and $H_0(K)=Z_0(K)/B_0(K)\cong\mathbb{Z}$. Since there are no $2$-simplexes, $B_1(K)=0$. $C_1(K)=\mathbb{Z}\oplus\mathbb{Z}\oplus\mathbb{Z}$. Let $z\in Z_1(K)\subset C_1(K)$. Then
$z=i(p_0p_1)+j(p_1p_2)+k(p_2p_0)$ for some $i,j,k\in\mathbb{Z}$. Then
\begin{align*}
\partial_1z&=i(p_1-p_0)+j(p_2-p_1)+k(p_0-p_2)\\
&=(k-i)p_0+(i-j)p_1+(j-k)p_2=0\\
&\Rightarrow i=j=k
\end{align*}
Hence,
$$Z_1(K)=\{i[(p_0p_1)+(p_1p_2)+(p_2p_0)]: i\in\mathbb{Z}\}\cong\mathbb{Z}$$
since it is generated by a single $1$-chain $(p_0p_1)+(p_1p_2)+(p_2p_0)$, and $H_1(K)=Z_1(K)=\mathbb{Z}$.

Remark. $L=\{p_0,p_1,p_2,p_3,(p_0p_1),(p_1p_2),(p_2p_3),(p_3p_0)\}$ is a simplicial complex whose polyhedron is an oriented square. Since a square is homeomorphic to a circle, $L$ is also a triangulation of $S^1$. However, it is a less economical triangulation of $S^1$ than $K$ in the preceding example. By theorem 1, $H_r(L)\cong H_r(K)$ for all $r\geq 0$, i.e. $H_0(L)=H_1(L)=\mathbb{Z}$ and $H_r(L)=0$ for all $r\geq 2$.

Example. Let $K=\{p_0,p_1,p_2,(p_0p_1),(p_1p_2),(p_2p_0),(p_0p_1p_2)\}$.

Figure 1. A Contractible Simplicial Complex

 $K$ has no holes so it is contractible. By theorem 2, $H_0(K)=\mathbb{Z}$ and $H_r(K)=0$, $\forall r\geq 1$.

 

The Gaussian Integral

 The Gaussian integral is not only important in mathematics but is also extremely important in studying physics, for example, quantum mechanics, quantum field theory, and statistical mechanics. Let us begin with the most simple Gaussian integral
$$G=\int_{-\infty}^\infty e^{-x^2}dx$$
This is not an easy integral to calculate because there is no closed form antiderivative of the function $e^{-x^2}$. However, it can be done easily if we extend it to an integral in two-dimensions as
\begin{align*}
G^2&=\int_{-\infty}^\infty e^{-x^2}dx\int_{-\infty}^\infty e^{-y^2}dy\\
&=\int_{-\infty}^\infty\int_{-\infty}^\infty e^{-(x^2+y^2)}dxdy
\end{align*}
Now, in term of the polar coordinates, $x=r\cos\theta$, $y=r\sin\theta$ and the area element is $dA=rdrd\theta$, so $G^2$ can be written as
\begin{align*}
G^2&=\int_0^{2\pi}\int_0^\infty re^{-r^2}drd\theta\\
&=\pi
\end{align*}
The integral $\int_0^\infty re^{-r^2}dr$ can be easily evaluated using the substitution $u=-r^2$ and its value is $\frac{1}{2}$. Now, we obtain
$$G=\int_{-\infty}^\infty e^{-x^2}dx=\sqrt{\pi}$$
From this you can evaluate more complicated Gaussian integrals using a simple substitution and/or some algebra. For example, $\int_{-\infty}^\infty e^{-ax^2}dx$ for a positive real number $a$ can be evaluated easily by a simple substitution $u=\sqrt{a}x$:
\begin{align*}
\int_{-\infty}^\infty e^{-ax^2}dx&=\frac{1}{\sqrt{a}}\int_{-\infty}^\infty e^{-u^2}du\\
&=\sqrt{\frac{\pi}{a}} \tag{1}
\end{align*}
If $a=\frac{1}{2}$, then $\int_{-\infty}^\infty e^{-\frac{1}{2}x^2}dx=\sqrt{2\pi}$. Normally one will have to use the integration by parts to calculate $\int_{-\infty}^\infty x^2e^{-x^2}dx$ or $\int_{-\infty}^\infty x^4e^{-x^2}dx$. There is a neat trick of evaluating such integrals by differentiating (1) with respect to $a$:
$$\frac{d}{da}\int_{-\infty}^\infty e^{-ax^2}dx=-\int_{-\infty}^\infty x^2e^{-ax^2}dx$$
and
$$\frac{d}{da}\sqrt{\frac{\pi}{a}}=-\frac{1}{2a}\sqrt{\frac{\pi}{a}}$$
Thus, we have
$$
\int_{-\infty}^\infty x^2e^{-ax^2}dx=\frac{1}{2a}\sqrt{\frac{\pi}{a}} \tag{2}
$$
For $a=1$, we obtain
$$\int_{-\infty}^\infty x^2e^{-x^2}dx=\frac{\sqrt{\pi}}{2}$$
Differentiating (2) with respect to $a$ leads to
$$
\int_{-\infty}^\infty x^4e^{-ax^2}dx=\frac{3}{4a^2}\sqrt{\frac{\pi}{a}} \tag{3}
$$
For $a=1$, we obtain
$$
 \int_{-\infty}^\infty x^4e^{-x^2}dx=\frac{3}{4}\sqrt{\pi} \tag{4}
$$
I learned this trick from the book Quantum Field Theory in a Nutshell by Anthony Zee. Another important variation is
$$
\int_{-\infty}^\infty e^{-ax^2+bx}dx \tag{5}
$$
This integral can be evaluated from (1) with a little bit of algebra. First, by completing the square, we write
\begin{align*}
-ax^2+bx&=-a\left(x^2-\frac{b}{a}x\right)\\
&=-a\left(x^2-\frac{b}{a}x+\left(-\frac{b}{2a}\right)^2-\left(-\frac{b}{2a}\right)^2\right)\\
&=-a\left(x-\frac{b}{2a}\right)^2+\frac{b^2}{4a}
\end{align*}
Now, (5) is evaluated as
\begin{align*}
\int_{-\infty}^\infty e^{-ax^2+bx}dx&=\int_{-\infty}^\infty e^{-a\left(x-\frac{b}{2a}\right)^2+\frac{b^2}{4a}}dx\\
&=e^{\frac{b^2}{4a}}\int_{-\infty}^\infty e^{-a\left(x-\frac{b}{2a}\right)^2}dx\\
&=e^{\frac{b^2}{4a}}\int_{-\infty}^\infty e^{-au^2}du\ \left[u=x-\frac{b}{2a}\right]\\
&=e^{\frac{b^2}{4a}}\sqrt{\frac{\pi}{a}}
\end{align*}

This time let us try to calculate
$$
\int_{-\infty}^\infty\int_{-\infty}^\infty\int_{-\infty}^\infty (x^2+y^2+z^2)e^{-(x^2+y^2+z^2)}dxdydz \tag{6}
$$
You stumble upon this type of integral, for example, in a derivation of the Maxwell-Boltzmann statistics in the form of
$$\int d^3p\frac{p^2}{2m}\exp\left(-\beta\frac{p^2}{2m}\right)$$
The integral (6) can be easily evaluated using the spherical coordinates:
\begin{align*}
x&=r\sin\theta\cos\phi\\
y&=r\sin\theta\sin\phi\\
z&=r\cos\theta\\
\end{align*}
where
$$0\leq r<\infty,\   0\leq\theta\leq\pi,\ 0\leq\theta\leq 2\pi$$
The volume element in the spherical coordinates is $dV=r^2dr\sin\theta d\theta d\phi$, so
\begin{align*}
\int_{-\infty}^\infty\int_{-\infty}^\infty\int_{-\infty}^\infty (x^2+y^2+z^2)e^{-(x^2+y^2+z^2)}dxdydz&=\int_0^{2\pi}\int_0^\pi\int_0^\infty r^4e^{-r^2}dr\sin\theta d\theta d\phi\\
&=\frac{3}{2}\pi\sqrt{\pi}
\end{align*}
We obtain
$$\int_0^\infty r^4e^{-r^2}dr=\frac{3}{8}\sqrt{\pi}$$
using (4).

Marginal Functions

 Let $C(x)$, $R(x)$, and $P(x)$ denote, respectively, the total cost function, the total revenue function, and the total profit function.

Definition.

• $C(x+1)-C(x)$, the cost of producing the $x+1$st item,  is called the marginal cost at production level $x$.
• $R(x+1)-R(x)$, the revenue derived by the producer when $x+1$ items are sold, is called the marginal revenue at $x$.
• $P(x+1)-P(x)$, the producer's profit due to the $x+1$st item, is called marginal profit at $x$.
  

Let $E(x)$ be an economic function which represents any of the total cost, revenue, and profit functions and we assume that it is differentiable. In many real applications, the approximation
$$E'(x)\approx E(x+1)-E(x)$$
or
$$E'(x)\approx E(x)-E(x-1)$$
is valid. That is, $E'(x)$ is approximately the marginal economic function at level $x$ or level $x-1$.

Example. Given that the cost, in dollar, of producing $x$ short wave radios is $C(x)=x^2+80x+3500$,

1. Find the cost of producing; (a) the 100th radio; (b) the 101st radio.
2. Find $C'(100)$ and interpret this.
   

Solution.

1.  (a) It is the marginal cost at level 99, $C(100)-C(99)=279$ dollars. (b) It is the marginal cost at level 100, $C(101)-C(100)=281$ dollars. 
2. $C'(x)=2x+80$, so $C'(100)=280$ dollars. This can be used to approximate the marginal cost at level 99 or at 100. In either case, the error is 1 dollar and the percentage error in the approximation is 0.36.
   

Definition. The average cost function $\bar C(x)$ is defined by
$$\bar C(x)=\frac{C(x)}{x}$$

Example. Suppose that the relationship between price of and demand for a certain type of large color television set is given by the demand equation $10p+x=10000$, where $p$ is the per unit price in dollars, and $x$ is the number of sets demanded. If the producer's cost is $C(x)=60x+3000$,

1. Determine the revenue function.
2. Determine the marginal revenue function.
3. Determine the profit function.
4. Determine the marginal profit function.
5. What is the price for each color television when the marginal profit is zero?
6. Sketch the profit function, drawing the tangent line when the marginal profit is zero. What does this profit represent?
7. What can you conclude about the profit at the price obtained in 5?
   

Solution.

1. Solving the demand equation for price, we find $$p=-0.1x+1000$$ and so the revenue function is given by $$R(x)=px=-0.1x^2+1000x$$

2. The marginal revenue function at $x$ is $R(x+1)-R(x)$ but for practical purposes, it can be replaced by the approximation $R'(x)=-0.2x+1000$.

3. \begin{align*}P(x)&=R(x)-C(x)\\&=-0.1x^2+400x-3000\end{align*}

4. $P'(x)=-0.2x+400$.

5. When $P'(x)=-0.2x+400=0$, $x=2000$ i.e. the production level when the marginal profit is zero is 2000. The corresponding price per color television unit is $p=-0.1(2000)+1000=800$.

6.

 

 7. At $p=800$ ($x=2000$), the profit is maximized and the maximum value is $P(2000)=397000$ dollars.

In the preceding example, the profit is maximized when the marginal profit is zero. This is not a coincidence. The marginal profit is
$$P'(x)=R'(x)-C'(x)$$
If $P'(x)=0$, $R'(x)=C'(x)$ i.e. the marginal revenue equals the marginal cost. This means that the cost of producing one more item equals the revenue obtained by producing it, so there is no gain to be made by making the next item. As long as the marginal cost is less than the marginal revenue, it pays to keep producing more items. When the marginal cost becomes equal to the marginal revenue, it is time to stop producing more items.