Tags

Categories

TODO

# 群论

• 封闭
• 结合律
• 单位元
• 逆元

## 阿贝尔群(abelian or commutative)

$a\circ b=b\circ a$

• 封闭
• 单位元
• 逆元

## cyclic group(循环群)

• 存在一些$a\in G$使得$G=\langle a\rangle$
• order of $a$:满足$a^n=e$的最小正整数$n$
• 循环群是阿贝尔群
• 循环群的子群是循环群
• $C_{\infty}\cong\mathbb{Z}(\mathbb{Z},+),C_n\cong\mathbb{Z}_n$
• 无限循环群$C_{\infty}$
• $|g^k|=\infty$
• 生成元:$g,g^{-1}$
• 子群:$\langle g^k\rangle,k\in\mathbb{N}$
• 有限循环群$C_n$
• 生成元:$g^k,\gcd(k,n)=1$

## symmetric group(对称群)

$|S_n|=n!$

## permutation group

• $S_n$的子群是permutation group

## cycle

• cycle of length $k$:$\sigma(a_k)=a_1$
• $\sigma,\tau$是$S_X$中不相交的cycles,那么$\sigma\tau=\tau\sigma$
• transpositions:长度为2的cycle
• $(a_1,a_2,…,a_n)=(a_1a_n)(a_1a_{n-1})…(a_1a_3)(a_1a_2)$

## alternating group(交代群)

• even permutations

## dihedral group(二面体群)

• $D_n$是$S_n$的一个阶为$2n$的子群

## cosets(陪集)

• $g\in G$
• 左陪集:$gH=\{gh:h\in H\}$
• 右陪集:$Hg=\{hg:h\in H\}$
• 令$H$是$G$的子群,$g_1,g_2\in G$,以下条件等价:
1. $g_1H=g_2H$
2. $Hg_1^{-1}=Hg_2^{-1}$
3. $g_1H\subset g_2H$
4. $g_2\in g_1H$
5. $g_1^{-1}g_2\in H$
• index of $H$ in $G$:$H$在$G$中左陪集数$[G:H]$

TODO

## isomorphism(同构)

• 无限循环群同构于$\mathbb{Z}$
• $n$阶有限循环群同构于$\mathbb{Z}_n$
• $p$阶($p$为质数)群同构于$\mathbb{Z}_p$

## external direct products(外直积)

$G\times H:(g_1,h_1)(g_2,h_2)=(g_1\cdot g_2,h_1\circ h_2)$

• 令$(g,h)\in G\times H$,$g,h$的阶各为$r,s$,那么$(g,h)$在$G\times H$中的阶为$s,r$的最小公倍数

## internal direct products(内直积)

• $G$是$H$和$K$的内直积:
• $G=HK=\{hk:h\in H,k\in K\}$
• $H\cap K=\{e\}$
• $hk=kh$
• 若$G$是$H$和$K$的内直积,$G\cong H\times K$

## 正规子群

$H$是$G$的子群,$H$ is normal:$\forall g\in G,gH=Hg$

• 令$N$是$G$子群,以下等价
1. $N$ normal in $G$
2. $\forall g\in G,gNg^{-1}\subset N$
3. $\forall g\in G,gNg^{-1}=N$

TODO

## Homomorphisms(同态)

• 令同态映射$\phi:G\to H$,kernel:$\phi(\{e\})^{-1}$($G$的正规子群)

## 同构定理

• natural/canonical homomorphism:
• $H$是$G$的正规子群,定义$\phi:G\to G/H$ by $\phi(g)=gH$
• 第一同构定理
• 如果$\psi:G\to H$是同态映射且$K=\ker\psi$,那么$K$ is normal in $G$
• 令$\phi:G\to G/K$为canonical homomorphism,那么存在唯一的同构映射$\eta:G/K\to\phi(G)$ such that $\psi=\eta\phi$
• 第二同构定理
• $H$是$G$的子群,且$N$是$G$的正则子群,那么:
• $HN$是$G$的子群
• $H\cap N$是$H$的正规子群
• $H/H\cap N\cong HN/N$

TODO

# 数论

## 欧拉函数

$\phi(n):\le n$正整数中与$n$互质的数的个数

• $\phi(n)=n\prod(1-\dfrac{1}{p}),p$是$n$的质因子,不重复
• 若$m,n$互质,$\phi(mn)=\phi(m)\phi(n)$
• 若$n$为质数,$\phi(n)=n-1$

## 求解模线性方程

• 当且仅当$d|b$时,$ax\equiv b(\mod n)$有解,$d=\gcd(a,n)$
• 对任意正整数$a,n$,如果$d=\gcd(a,n)$,则在$\mathbb{Z}_n$中
1. $\langle a\rangle=\langle d\rangle=\{0,d,2d,…,((n/d)-1)d\}$
2. $|\langle a\rangle|=n/d$

## 中国余数定理

• $n_1,n_2…n_k$两两互质,且$n=n_1n_2…n_k$,则对任意整数$a_1,a_2…a_k$,关于$x$的方程组$x\equiv a_i(\mod n_i),i=1,2…k$有唯一解
• $n_1,n_2…n_k$两两互质,且$n=n_1n_2…n_k$,则对所有整数$x,a$:$x\equiv a(\mod n_i),i=1,2…k$当且仅当$x\equiv a(\mod n_i)$

## 元素的幂

• 欧拉定理:$\forall n > 1,a^{\phi(n)}\equiv1(\mod n),a\in\mathbb{Z}_n^{*}$
• 费马定理:$p$是素数,则$a^{p-1}\equiv1(\mod p),a\in\mathbb{Z}_n^{*}$

## RSA

1. 选两个素数$p\not=q$
2. $n=pq$
3. 选与$\phi(n)$互质的小奇数$e$
4. 计算模$\phi(n)$下$e$的乘法逆元$d$
5. 公开$e,n$

## 代数编码

• $(n,m)$-block code:$m$位编码成$n$位
• 矩阵$H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)的$null space($Null(H)$):使得$Hx=0$的$x$集合
• canonical parity-check matrix:$H=(A|I_m)$
• standard generator matrix:$G=(\dfrac{I_{n-m}}{A})$
• $\{y:Gx=y,x\in\mathbb{Z}_2^k\}=C=Null(H),((n,k)$-block code)
• $HG=0$
• $y\in C$当且仅当$Hy=0$
• $C$是single error-correcting code当且仅当$H$没有全0的column且$H$任意两columns都不相同
• syndrome of $x$(校验子):$Hx$
• 对$r$行(校验位长度)的汉明奇偶校验矩阵,其列数至多$2^r-1$(除去0),设信息位长度为$k$,则$2^r-1\ge k+r$

# NPC理论

## 判定问题$(L,U,\Sigma)$

• input: An $x\in U$
• output: ‘yes’ if $x\in L$, ‘no’ otherwise

## 最优化问题$(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$

• input: $L_I$的问题实例
• constraints: 对于$x\in L_I$的约束条件$M(x)$
• costs: cost函数
• goal: maximum/minimun

## NP完全性

• co-NP:{$L|L^C\in$NP}
• $L_1\le_PL_2$:$x\in L_1$当且仅当$f(x)\in L_2$
• NP-hard:
1. 不一定是NP
2. 所有NP可以约化到它
• $L_2\in P,L_1\le_PL_2$则$L_1\in P$
• $L’\in$NPC,$L’\le_PL$则$L$是NP难度的

## 3-CNF可满足性$\le_P$团问题

• 建图:
1. 对每个子句$C=(x\vee y\vee z)$,将$x,y,z$以3元组的形式加入到点集$V$
2. 对所有$V$中来自不同3元组的两个点$u,v$,若$u$不是$v$的非,则建边$(u,v)$
• 3-CNF可满足$\to$规模为$k$的团:
• 每个3元组中至少会有一个文字为真,在每个3元组中选一个这样的顶点,组成规模为$k$的集合$V’$
• 因为$k$个顶点对应的文字不可能互补,所以两两之间有边,所以$V’$是团
• 规模为$k$的团$\to$3-CNF可满足
• $k$个顶点对应的文字两两互不为补,令这些顶点对应的文字为真

## 团问题$\le_P$顶点覆盖问题

• 建图:
• 根据输入$G$建立补图$\bar{G}$
• $G$有规模为$k$的团$\to\bar{G}$有规模为$|V|-k$的顶点覆盖:
• 设$G$包含规模为$k$的团$V’$
• 对$\bar{G}$中任意一条边$(u,v)$,$(u,v)\not\in G$,所以$u,v$至少一个不在团$V’$中,即$u,v$至少一个在$V-V’$中,即$u,v$两点被点集$V-V’$覆盖,所以$V-V’$能覆盖$\bar{G}$中的所有顶点
• $\bar{G}$有规模为$|V|-k$的顶点覆盖$\to G$有规模为$k$的团:
• 设$\bar{G}$包含规模为$|V|-k$的顶点覆盖$V’$
• 对$G$中任意2个顶点$u,v$,若$u\not\in V’$且$v\not\in V’$,那么$G$中一定有边$(u,v)$,所以任意$u,v\in V-V’$存在边$(u,v)$,所以$V-V’$是团

## 哈密顿回路问题$\le_P$旅行商问题

• 建图:
• 对于输入$G$,建立完全图$G’$,定义费用$c(i,j)=\begin{cases} 0\quad(i,j)\in E\\ 1\quad(i,j)\not\in E\\ \end{cases}$
• $G$有哈密顿回路$\to G’$中有费用至多为0的回路:
• $G’$中有费用至多为0的回路$\to G$有哈密顿回路:

## 3-CNF可满足性$\le_P$子集和问题

• 建模:
1. 输入含$n$个变量,$k$个子句
2. 集合$S$为$2k+2n$个$k+n$位10进制数的集合(高$n$位对应$n$个变量,低$k$为对应$k$个子句):
1. 对于每个变量$x$,在$S$中构建2个数$v,v’$:
1. $v,v’$对应$x$的那一位为1
2. 对所有子句$C$,若$C$包含$x$,则$v$对应的$C$那一位为1,若$C$包含$\lnot x$,则$v’$对应$C$的那一位为1
2. 对于每个子句$C$,在$S$中构建两个数$s,s’$:
1. $s$对应$C$的那一位为1
2. $s’$对应$C$的那一位为2
3. 目标:选取$S’\subseteq S$,其中所有数之和$t$高$n$位全为1,低$k$位全为$4$
• 3-CNF可满足$\to$存在$S’\subseteq S$和为$t$:
1. 若变量$x_i=1$则将$v_i$包含进$S’$,否则将$v_i’$包含进$S’$:$t$的高$n$位为全1
2. 现在$t$的低$k$位每一位可能为$1,2,3$,再对每一个集合$\{s_j,s_j’\}$选取一个非空集合,使得$t$在对应子句$C_i$的位置为4
• 存在$S’\subseteq S’$和为$t\to$3-CNF可满足:
1. 因为$t$的高$n$位全为1,那么每对$v_i,v_i’$,$S’$都只包含2者之1
2. 若$v_i\in S’$,$x_i$置1,否则置0
3. TODO

# 随机化算法

## 拉斯维加斯算法

• $Prob(A(x)=F(x))=1$
• $Prob(A(x)=?)=1-Prob(A(x)=F(x))\le\dfrac{1}{2}$

## 蒙特卡洛算法

• one-sided-error:
1. $x\in L,Prob(A(x)=1)\ge1/2$
2. $x\not\in L,Prob(A(x)=0)=1$
• two-sided-error:
1. $Prob(A(x)=F(x))\ge1/2+\varepsilon$
• unbounded-error:
1. $Prob(A(x)=F(x)) > \dfrac{1}{2}$
oj复习

## 素数判定

### p3383

• 增大步长
• Miller-Rabin

## KMP

### poj3461

Algorithmics-for-Hard-Problems

# 2

## 2.3

### Definition 2.3.1.2

Let $\Sigma$ be an alphabet. A word over $\Sigma$ is any finite sequence of symbols of $\Sigma$. The empty word $\lambda$ is the only word consisting of zero symbols. The set of all words over the alphabet $\Sigma$ is denoted by $\Sigma^{*}$

### Definition 2.3.1.3

The length of a word $w$ over an alphabet $\Sigma$, denoted by $|w|$, is the number of symbols in $w$. For every word $w\in\Sigma^{*}$, and every symbal $a\in\Sigma$, $\sharp_{a}(w)$ is the number of occurrences of the symbol $a$ in the word $w$

### Definition 2.3.1.4

Let $\Sigma$ be an alphabet. Then, for any $n\in\mathbb{N}$
$$\Sigma^n=\{x\in\Sigma^{*}||x|=n\}$$
We define $\Sigma^+=\Sigma^{*}-\{\lambda\}$

### Definition 2.3.1.5 (concatenation)

For every word $w\in\Sigma^{*}$, we define

• $w^0=\lambda$, and
• $w^{n + 1}=w\cdot w^n=ww^n$ for every positive integer $n$

### Definition 2.3.1.9 (language)

Let $\Sigma$ be an alphabet, Every set $L\subseteq\Sigma^{*}$ is called a language over $\Sigma$. The complement of the language $L$ according to $\Sigma$ is $L^C=\Sigma^{*}-L$

Let $\Sigma_1$ and $\Sigma_2$ be alphabets, and let $L_1\subseteq\Sigma_1^{*}$ and $L_2\subseteq\Sigma_2^{*}$ be languages. The concatenation of $L_1$ and $L_2$ is
$$L_1L_2=L_1\circ L_2=\{uv\in(\Sigma_1\cup\Sigma_2)^{*}|u\in L_1 and\ v\in L_2\}$$

### Definition 2.3.1.10

Let $\Sigma=\{s_1,s_2…s_m\},m\ge1$, be an alphabet, and let $s_1 < s_2 < … < s_m$ be a linear ordering on $\Sigma$. We define the canonical ordering on $\Sigma^{*}$ as follows. For all $u,v\in\Sigma^{*}$
$$u < v\mbox{ if }|u| < |v|$$
$$\mbox{or }|u|=|v|,u=xs_iu’,\mbox{ and }v=xs_jv’$$
$$\mbox{for some }x,u’,v’\in\Sigma^{*},\mbox{ and }i < j$$

## 2.3.2

### Definition 2.3.2.1

A decision problem is a triple $(L, U, \Sigma)$ where $\Sigma$ is an alphabet and $L\subseteq U\subseteq\Sigma^{*}$. An algorithm $A$ solves(decides) the decision problem $(L, U, \Sigma^{*}$ if, for every $x\in U$

• $A(x)=1$ if $x\in L$, and
• $A(x)=0$ if $x\in U-L(x\not\in L)$

### Definition 2.3.2.2

An optimization problem is a 7-tuple $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$, where

• $\Sigma_I$ is an alphabet, called the input alphabet of $U$
• $\Sigma_O$ is an alphabet, called the output alphabet of $U$
• $L\subseteq\Sigma_I^{*}$ is the language of feasible problem instances
• $L_I\subseteq L$ is the language of the(actual) problem instances of $U$
• $M$ is a function from $L$ to (power set)$Pot(\Sigma_O^{*})$, and for every $x\in L$, $M(x)$ is some $x\in L$, assigns a positive real number cost($u,x$)
• cost is the cost function that, for every pair $(u,x)$, where $u\in M(x)$ for some $x\in L$, assigns a positive real number cost($u,x$)
• goal$\in${minimum,maximum}

For every $x\in L_I$, a feasible solution $y\in M(x)$ is called optimal for $x$ and $U$ if
$$cost(y,x)=goal\{cost(z,x)|z\in M(x)\}$$
For an optimal solution $y\in M(x)$, we denote cost($u,x$) by Opt$_U(x)$ ,$U$ is called maxmization problem if goal=maximum, and $U$ is a minimization problem if goal=minimum. In what follows Output$_U(x)\subseteq M(x)$ denotes the set of all optimal solutions for the instance $x$ of $U$

An algorithm $A$ is consistent for $U$ if, for every $x\in L_I$, the output $A(x)\in M(x)$. We say that an algorithm $B$ solves the optimization problem $U$ if

• $B$ is consistent for $U$, and
• for every $x\in L_1, B(x)$ is an optimal solution for $x$ and $U$

### Definition 2.3.2.3

Let $U_1=(\Sigma_I,\Sigma_O,L,L_{I,1},M,cost,goal)$ and $U_2=(\Sigma_I,\Sigma_O,L,L_{I,2},M,cost,goal)$ be two optimization problems. We say that $U_1$ is a subproblem of $U_2$ if $L_{I,1}\subseteq L_{I,2}$

### Theorem 2.3.3.3

There is a decision problem $(L,\Sigma_{bool})$ such that, for every algorithm $A$ deciding $L$, there exists another algorithm $B$ deciding $L$, such that
$$Time_B(n)=\log_2(Time_A(n))$$
for infinitely many positive integers $n$

### Definition 2.3.3.5

We define the complexity class $P$ of languages decidable in polynomial-time by
$$P=\{L=L(M)|M\mbox{ is a TM(an algorithm) with }Time_M(n)\in O(n^c)\mbox{ for some positive integer c}\}$$

A language (decision problem) $L$ is called tractable(practially solvable) if $L\in P$. A language $L$ is called intractable if $L\not\in P$

### Definition 2.3.3.6

Let $M$ be a nondeterministic TM(algorithm). We say that $M$ accepts a language $L, L = L(M)$, if

• for every $x\in L$, there exists at least one computation of $M$ that accepts $x$, and
• for every $y\not\in L$, all computations of $M$ reject $y$

For every input $w\in L$, the ** time complexity Time$_M(w)$ of $M$ on $w$ ** is the time complexity of the shortest accepting computation of $M$ on $w$. The time complexity of $M$ is the function Time$_M$ from $\mathbb{N}$ to $\mathbb{N}$ defined by
$$Time_M(n)=\max\{Time_M(x)|x\in L(M)\cap\Sigma^n\}$$

### Definition 2.3.3.7

Let $L\subseteq\Sigma^{*}$ be a language. An algorithm $A$ working on inputs from $\Sigma^{*}\times\{0,1\}$ is called a verifier for $L$, denoted $L=V(A)$, if
$$L=\{w\in\Sigma^{*}|A\mbox{ accepts }(w,c)\mbox{ for some }c\in\{0,1\}^{*}\}$$
If $A$ accepts $(w,c)\in\Sigma^{*}\times\{0,1\}$, we say that $c$ is a proof(certificate) of the fact $w\in L$

A verifier $A$ for $L$ is called a polynomial-time verifier if there exists a positive integer $d$ such that, for every $w\in L$, Time$_A(w,c)\in O(|w|^d)$ for a proof $c$ of $w\in L$

We define the class of polynomially verifiable languages as
$$VP=\{V(A)|A\mbox{ is a polynomial-time verifier}\}$$

### Definition 2.3.3.10

Let $L_1\subseteq\Sigma_1^{*}$ and $L_2\subseteq\Sigma_2^{*}$ be two languages. We say that $L_1$ is polynomial-time reducible to $L_2, L_1\le_pL_2$, if there exists a polynomial-time algorithm $A$ that computes a mapping from $\Sigma_1^{*}$ to $\Sigma_2^{*}$ such that, for every $x\in\Sigma_1^{*}$
$$x\in L_1\Leftrightarrow A(x)\in L_2$$
A is called the polynomial-time reduction from $L_1$ to $L_2$

• A language $L$ is called NP-hard if, for every $U\in NP,U\le_pL$
• A language $L$ is called NP-complete if
• $L\in NP$, and
• $L$ is NP-hard

### Lemma 2.3.3.11

If $L$ is NP-hard and $L\in P$, then P=NP

### Lemma 2.3.3.15

Sat$\le_{p}$Clique

### Lemma 2.3.3.16

Clique$\le_{p}$VC

### Lemma 2.3.3.19

3Sat$\le_{p}$Sol-0/1-LP

### Definition 2.3.3.21

NPO is the class of optimization problems, where $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)\in$NPO if the following conditions hold

• $L_I\in$P

• there exists a polynomial $p_U$ such that

• for every $x\in L_I$, and every $y\in M(x),|y|\le p_U(|x|)$, and
• there exists a polynomial-time algorithm that, for every $y\in\Sigma_O^{*}$ and every $x\in L_I$ such that $|y|\le p_U(|x|)$, decides whether $y\in M(x)$, and
• the function cost is computable in polynomial time

### Definition 2.3.3.23

PO is the class of optimization problems $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ such that

• $U\in$NPO, and
• there is a polynomial-time algorithm that, for every $x\in L_1$, computes an optimal solution for $x$

### Definition 2.3.3.24

Let $U=(\Sigma_1,\Sigma_O,L,L_1,M,cost,goal)$ be an optimization problem from NPO, We define the threshold language of $U$ as
$$Lang_U=\{(x,a)\in L_1\times\Sigma_{bool}^{*}|Opt_U(x)\le Number(a)\}$$
if goal=minimum, and as
$$Lang_U=\{(x,a)\in L_1\times\Sigma_{bool}^{*}|Opt_U(x)\ge Number(a)\}$$
if goal=maximum

We say that $U$ is NP-hard if Lang$_U$ is NP-hard

### Lemma 2.3.3.25

If an optimization problem $U\in$PO, then Lang$_U\in$P

# 4

## 4.2

### Definition 4.2.1.1

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ be an optimization problem, and let $A$ be a consistent algorithm for $U$. For every $x\in L_I$, the relative error $\varepsilon_A(x)$ of $A$ on $x$ is defined as
$$\varepsilon_A=\dfrac{|cost(A(x))-Opt_U(x)|}{Opt_U(x)}$$

• For any $n\in\mathbb{N}$, we define the relative error of $A$ as
$$\varepsilon_A(n)=\max\{\varepsilon_A(x)|x\in L_I\cap(\Sigma_I)^n\}$$

• For every $s\in L_I$, the approximation ratio $R_A(x)$ of $A$ on $x$ is defined as
$$R_A(x)=\max\{\dfrac{cst(A(x))}{Opt_U(x)},\dfrac{Opt_U(x)}{cost(A(x))}\}$$

• For any $n\in\mathbb{N}$, we define the approximation ratio of $A$ as
$$R_A(n)=\max\{R_A(x)|x\in L_I\cap(\Sigma_I)^n\}$$

• For any positive real $\delta > 1$, we say that $A$ is a $\delta$-approximation algorithm for $U$ if $R_A(x)\le\delta$ for every $x\in L_I$

• For every function $f:\mathbb{N}\to\mathbb{R}^+$, we say that $A$ si an $f(n)$-approximation algorithm for $U$ if $R_A(n)\le f(n)$ for every $n\in\mathbb{N}$

### Definition 4.2.1.6

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ be an optimization problem. An algorithm $A$ is called a polynomial-time approximation scheme (PTAS) for $U$ if for every input pair $(x,\varepsilon)\in L_I\times\mathbb{R}^+, A$ computes a feasible solution $A(x)$ with a relative error at most $\varepsilon$, and $Time_A(x,\varepsilon^{-1})$ can be bounded by a function that is polynomial in $|x|$.

If $Time_A(x,\varepsilon^{-1})$ can be bounded by a function that is polynomial in both $|x|$ and $\varepsilon^{-1}$, then we say that $A$ is a fully polynomial-time approximation scheme (FPTAS) for $U$

### Definition 4.2.3.1

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ and $\bar{U}=(\Sigma_I,\Sigma_O,L,L,M,cost,goal)$ be two optimization problems with $L_I\subset L$. A distance function for $\bar{U}$ according to $L_I$ is any function $h_L:L\to\mathbb{R}^{\ge0}$ satisfying the properties

1. $h_L(x)=0$ for every $x\in L_I$, and
2. $h$ is polynomial-time computable

Let $h$ be a distance function for $\bar{U}$ accoring to $L_I$. We define, for any $r\in\mathbb{R}^+$
$$Ball_{r,h}(L_I)=\{w\in L|h(w)\le r\}$$
Let $A$ be a consistent algorithm for $\bar{U}$, and let $A$ be an $\varepsilon$-approximation algorithm for $U$ for some $\varepsilon\in\mathbb{R}^{-1}$. Let $p$ be a positive real. We say that $A$ is p-stable according to $h$ if, for every real $0 < r \le p$, there exists a $\delta_{r,\varepsilon}\in\mathbb{R}^{> 1}$ such that $A$ is a $\delta_{r,\varepsilon}$-approximation for $U_r=(\Sigma_I,\Sigma_O,L,Ball_{r,h}(L_I),M,cost,goal)$

$A$ is stable according to $h$ if $A$ is $p$-stable according to $h$ for every $p\in\mathbb{R}^+$. We say that $A$ is unstable according to h if $A$ is not $p$-stable for any $p\in\mathbb{R}^+$

For every positive integer $r$, and every function $f_r:\mathbb{N}\to\mathbb{R}^{> 1}$ we say that $A$ is $(r,f_r(n))$-quasistable according to $h$ if $A$ is an $f_r(n)$-approximation algorithm for $U_r=(\Sigma_I,\Sigma_O,L,Ball_{r,h}(L_I),M,cost,goal)$

### Definition 4.2.3.6

Let $U=(\Sigma_I,\Sigma_O,L,Ball_{r,h}(L_I),M,cost,goal)$ and $\bar{U}=(\Sigma_I,\Sigma_O,L,L,M,cost,goal)$ be two optimization problems with $L_I\subset L$. Let $h$ be a distance function for $\bar{U}$ according to $L_I$, and let $U_r=(\Sigma_I,\Sigma_O,L,Ball_{r,h}(L_I),M,cost,goal)$ for every $r\in\mathbb{R}^+$. Let $A=\{A_{\varepsilon}\}_{\varepsilon > 0}$ be a PTAS for $U$

If for every $r > 0$ and every $\varepsilon > 0, A_{\varepsilon}$ is a $\delta_{r,\varepsilon}$-approximation algorithm for $U_r$, we say that the PTAS $A$ is stable according to $h$

If $\delta_{r,\varepsilon}\le f(\varepsilon)\cdot g(r)$, where

• $f$ and $g$ are some functions from $\mathbb{R}^{\ge0}$ to $\mathbb{R}^+$, and
• $\lim_{\varepsilon\to0}f(\varepsilon)=0$
then we say that the PTAS $A$ is superstable according to $h$

5

5.2

### Definition 5.2.2.10

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ be an optimization problem. For any positive real $\delta > 1$ a randomized algorithm $A$ is called a randomized $\delta$-approximation algorithm for $U$ if

1. $Prob(A(x)\in M(x))=1$, and
2. $Prob(R_A(x)\le\delta)\ge1/2 for every$x\in L_I

For every function $f:\mathbb{N}\to\mathbb{R}^+$, we say that $A$ is a randomized $f(n)$-approximation algorithm for $U$ if
$$Prob(A(x)\in M(x))=1\ and\ Prob(R_A(x)\le f(|x|))\ge1/2$$
for every $x\in L_I$

A randomized algorithm $A$ is called a randomized polynomial-time approximation scheme (RPTAS) for $U$ if there exists a function $p:L_I\times\mathbb{R}^+\to\mathbb{N}$ such that for every input $(x,\delta)\in L_I\times\mathbb{R}^+$:

1. $Prob(A(x,\delta)\in M(x))=1$ for every random choice $A$ computes a feasible solution of $U$
2. $Prob(\varepsilon_A(x,\delta)\le\delta)\ge1/2$ a feasible solution, whose relative error is at most $\delta$, is produced with the probability at least 1/2
3. $Time_A(x,\delta^{-1})\le p(|x|,\delta^{-1})$ and $p$ is a polynomial in $|x|$

If $p(|x|,\delta^{-1})$ is polynomial in both its arguments $|x|$ and $\delta^{-1}$, then we say that $A$ is a randomized fully polynomial-time approximation scheme (RFPTAS) for $U$

### Definition 5.2.2.11

Let $U=(\Sigma_I,\Sigma_O,L,L_I,M,cost,goal)$ be an approximation problem. For any positive real $\delta > 1$, a randomized algorithm $A$ is called a randomized $\delta$-expected approximation algorithm for $U$ if

1. $Prob(A(x)\in M(x))=1$
2. $E[R_A(x)]\le\delta$

for every $x\in L_I$

Discrete Mathematics for CS

### 2.2 Inverses and Greatest Common Divisors

#### Lemma 2.8

The equation
$$a{\cdot}_nx = 1$$
has a solution in $\mathbb{Z}_{n}$ if and only there exist integers $x$ and $y$ such that
$$ax + ny = 1$$

#### Corollary 2.10

If $a\in\mathbb{Z}_{n}$ and $x$ and $y$ are integers such that $ax + ny = 1$, then the multiplicative inverse of $a$ in $\mathbb{Z}_{n}$ is $x$ mod $n$

#### Lemma 2.11

Given $a$ and $n$, if there exist integers $x$ and $y$ such that $ax+ny=1$, then $\gcd(a,n)=1$

#### Lemma 2.13

If $j,k,q$, and $r$ are positive integers such that $k=jq+r$, then
$$\gcd(j,k) = \gcd(r,j)$$

• 本书版
• 算法导论版

#### Theorem 2.15

Two positive integers $j$ and $k$ have greatest common divisor 1 iff there are integers $x$ and $y$ such that $hx+ky=1$

Algorithms

## 31 数论算法

### 31.3 模运算

#### 欧拉函数

$\mathbb{Z}_n^*$的规模表示为$\phi(n)$,称为欧拉phi函数,满足下式
$$\phi(n)=n\prod_{\text{p:p是素数且p|n}}(1-\dfrac{1}{p})$$

### 31.4 求解模线性方程

#### 定理 31.20

$$\langle a\rangle=\langle d\rangle=\{0,d,2d,…,((n/d)-1)d\}$$

#### 推论 31.22

• 或者对模$n$有$d$个不同的解
• 或者无解
这里$d=\gcd(a,n)$

#### 定理 31.23

$$x_0=x’(b/d)\mod n$$

### 31.5 中国余数定理

#### 定理 31.27 中国余数定理

$$a\leftrightarrow(a_1,a_2,…,a_k)\qquad(31.27)$$

$$a_i=a\mod n_i$$

$$a\leftrightarrow(a_1,a_2,…,a_k)$$
$$b\leftrightarrow(b_1,b_2,…,b_k)$$

$$(a+b)\mod n\leftrightarrow((a_1+b_1)\mod n_1,…,(a_k+b_k)\mod n_k)$$
$$(a-b)\mod n\leftrightarrow((a_1-b_1)\mod n_1,…,(a_k-b_k)\mod n_k)$$
$$(ab)\mod n\leftrightarrow((a_1b_1)\mod n_1,…,(a_kb_k)\mod n_k)$$

#### 推论 31.28

$$x\equiv a_i(\mod n_i),i=1,2,…,k$$

#### 推论 31.29

$$x\equiv a(\mod n_i)$$
(其中$i=1,2,…,k$)当且仅当
$$x\equiv a(\mod n)$$

### 31.6 元素的幂

#### 定理 31.34

$$x^2\equiv1(\mod p^e)$$

## 34 NP完全性

### 34.4 NP完全性的证明

#### 公式可满足性

$$SAT=\{\langle\varphi\rangle: \text{\varphi是一个可满足的布尔公式}\}$$

#### 3-CNF-SAT 3-CNF可满足性

$$(x_1\vee\lnot x_1\vee\lnot x_2)\wedge(x_3\vee x_2\vee x_4)\wedge(\lnot x_1\vee\lnot x_3\vee\lnot x_4)$$

Abstract Algebra(人话版)

## Sage准备

• mac
1. 开启共享
2. Applications/SageMath-8.6.app/Contents/Resources/sage/sage

• 结合律
• 单位元存在
• 逆元存在
• 子群

• 封闭性
• 单位元存在性
• 逆元存在性

### 一般线性群

• $\mathbb{M}_2(\mathbb{R})$:所有$2\times2$矩阵
• $GL_2(\mathbb{R})$:$\mathbb{M}_2$中可逆矩阵.可逆矩阵构成一般线性群
• $A\in GL_2(\mathbb{R}),A^{-1}=\dfrac{1}{ad-bc} \begin{pmatrix} d & -b \\ • c & a \\ \end{pmatrix}$

### 循环群

• 存在一些$a\in G$使得$G=\langle a\rangle$
• $C_{\infty}\cong\mathbb{Z}(\mathbb{Z},+),C_n\cong\mathbb{Z}_n$
• 无限循环群$C_{\infty}$
• $|g^k|=\infty$
• 生成元:$g,g^{-1}$
• 子群:$\langle g^k\rangle,k\in\mathbb{N}$
• 有限循环群$C_n$
• 生成元:$g^k,\gcd(k,n)=1$

### 四元群$Q_8$

• $Q_8={\pm1,\pm I,\pm J,\pm K}$,其中

$$1= \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} I= \begin{pmatrix} 0 & 1 \\ -1 & 0 \\ \end{pmatrix} J= \begin{pmatrix} 0 & i \\ i & 0 \\ \end{pmatrix} K=\begin{pmatrix} i & 0 \\ 0 & -i \\ \end{pmatrix}$$

Sage中复数用CC表示,可用i/I

### 置换群$S_n$:

• 秩:$|S_n|=n!$

### 交代群$A_n$

• $S_n$的子群,偶排列,$|A_n|=\dfrac{n!}{2}$

### 陪集

• $H$是$G$的子群,$H$的左陪集:$gH=\{gh:h\in H\}$

• $H$是$G$的子群,index of $H=H$在$G$中左陪集的个数$=H$右陪集的个数,记作$[G:H]$

### 正规子群(Normal Subgroups)

• $H$是$G$的子群,$gH=Hg,\forall g\in G$
• 等价条件,设$N$是$G$的子群
• $N$是$G$的正规子群
• $\forall g\in G,gNg^{-1}\subset N$
• $\forall g\in G,gNg^{-1}=N$

### 商群(factor/quotient group)

• $N$是$G$的正规子群,商群$G/N$是$N$在$G$中左陪集的集合
• $aN,bN\in G/N,(aN)(bN)=abN$
• $G/N$的阶为$[G:N]$

### 同构 同态

• 同构:$(G,\cdot),(H,\circ)$单射且满射$\phi:G\to H$

$$\phi(a\cdot b)=\phi(a)\circ\phi(b),\forall a,b\in G$$

• 同态:$(G,\cdot),(H,\circ)$映射$\phi:G\to H$

$$\phi(a\cdot b)=\phi(a)\circ\phi(b),\forall a,b\in G$$

• 核(kernel):群同态$\phi:G\to H$,$e$是$H$的单位元,$G$的子群$\phi^{-1}({e})$是$\phi$的kernel

### null space

sage中null space使用kernel代替

Abstract Algebra

## 2. The Integers

### Theorem 2.10

Let $a$ and $b$ be nonzero integers. Then there exist integers $r$ and $s$ such that
$$\gcd(a,b)=ar+bs$$
Furthermore, the greatest common divisor of $a$ and $b$ is unique

## 3.Groups

### Theorem 3.23

In a group, the usual laws of exponents hold; that is, for all $g, h\in G$

1. $g^mg^n=g^{m+n}$ for all $m, n\in\mathbb{Z}$

2. $(g^m)^n=g^{mn}$ for all $m, n\in\mathbb{Z}$

3. $(gh)^n=(g^{-1}h^{-1})^{-n}$ for all $n\in\mathbb{Z}$. Furthermore, if $G$ is abelian, then $(gh)^n=g^nh^n$

### Proposition 3.30

A subset $H$ of $G$ is a subgroup if and only if it satisfies the following conditions

1. The identity $e$ of $G$ is in $H$

2. If $h_1, h_2\in H$, then $h_1h_2\in H$

3. If $h\in H$, then $h^{-1}\in H$

### Proposition 3.31

Let $H$ be a subset of a group $G$. Then $H$ is a subgroup of $G$ if and only if $H\not=\emptyset$, and whenever $g, h\in H$ then $gh^{-1}$ is in $H$

## 4.Cyclic Groups

### Remark 4.4

If we are using the “+” notations, as in the case of the integers under addition, we write $\langle a\rangle={na:a\in\mathbb{Z}}$

For $a\in G$, we call $\langle a\rangle$ the cyclic subgroup generated by $a$. If $G$ contains some element $a$ such that $G=\langle a\rangle$, then $G$ is a cyclic group. In this case $a$ is a generator of $G$.

If $a$ is an element of a group $G$, we define the order of $a$ to be the smallest positive integer $n$ such that $a^n=e$, and we write $|a|=n$. If there is no such integer $n$, we say that the order of $a$ is infinite and write $|a|=\infty$ to denote the order of $a$

### Corollary 4.14

The generators of $\mathbb{Z}_n$ are the integers r subch that $1\le r<n$ and gcd$(r, n)=1$

$\text{cis}(x)=\cos(x)+$i$\sin(x)$

### Proposition 4.20

Let $z=r\text{cis}\theta$ and $w=s\text{cis}\phi$ be two nozero compler numbers. Then $$zw=rs\text{cis}(\theta+\phi)$$

## 5. Permutation Groups

### Proposition 5.8

Let $\sigma$ and $\tau$ be two disjoint cycles in $S_X$. Then $\sigma\tau=\tau\sigma$

### Theorem 5.9

Every permutation in $S_n$ can be written as the product of disjpint cycles

### Lemma 5.14

If the identity is written is written as the product of r transpositions $$id=\tau_1\tau_2…\tau_r$$ then $r$ is an even number

### The Alternating Groups

One of the most important subgroups of $S_n$ is the set of all even permutations, $A_n$. The group $A_n$ is called the alternating group on n letters

### Theorem 5.16

The set $A_n$ is a subgroup of $S_n$

### Proposition 5.17

The number of even permutations in $S_n, n\ge2$, is equal to the number of odd permutations; hence, the order of $A_n$ is $\dfrac{n!}{2}$

### Dihedral Groups

We define the nth dihedral group to be the group of rigid motions of a regular n-gon. $D_n$ consists of all finite products of $r$ and $s$

$$D_n={1, r, r^2…r^{n-1}, s, sr, sr^2…sr^{n-1}}$$

## 6.Cosets and Lagrange’s Theorem

### Cosets

Let $G$ be a group and $H$ a subgroup of $G$. Define a left coset of $H$ with representative $g\in G$ to be the set $$gH={gh:h\in H}$$

### Lemma 6.3

Let $H$ be a subgroup of a group $G$ and suppose that $g_1,g_2\in G$. The following conditions are equivalent

1. $g_1H=g_2H$
2. $Hg_1^{-1}=Hg_2^{-1}$
3. $g_1H\subset g_2H$
4. $g_2\in g_1 H$
5. $g_1^{-1}g_2\in H$

### Theorem 6.4

Let $H$ be a subgroup of a group $G$. Then the left cosets of $H$ in $G$ partition $G$. That is, the group $G$ is the disjoint union of the left cosets of $H$ in $G$

### Remark 6.5

Let $G$ be a group and $H$ be a subgroup of $G$. Define the index of $H$ in $G$ to be the number of left cosets of $H$ in $G$. We will denote the index by $[G:H]$

### Theorem 6.10 Lagrange

Let $G$ be a finite group and let $H$ be a subgroup of $G$. Then $G/H=[G:H]$ is the number of distinct left cosets of $H$ in $G$. In particular, the number of elements in $H$ must divide the number of elements in $G$

### Corollary 6.11

Suppose that $G$ is a finite group and $g\in G$. Then the order of $g$ must divide the number of elements in $G$

### Corollary 6.12

Let $|G|=p$ with $p$ a prime number. Then $G$ is cyclic and any $g\in G$ such that $g\not=e$ is a generator

### Corollary 6.13

Let $H$ and $K$ be subgroups of a finite group $G$ such that $K\subset H\subset G$. Then $$[G:K]=[G:H][H:K]$$

### Proposition 6.15

The group $A_4$ has no subgroup of order 6

### Theorem 6.16

Two cycles $\tau$ and $\mu$ in $S_n$ have the same length if and only if there exists a $\sigma\in S_n$ such that $\mu=\sigma\tau\sigma^{-1}$

### Euler $\phi$-function

The Euler $\phi$-function is the map $\phi:\mathbb{N}\to\mathbb{N}$ defined by $\phi(n)=1$ for $n=1$, and, for $n>1$, $\phi(n)$ is the number of positive integers $m$ with $1\le m < n$ and $\gcd(m,n)=1$

### Theorem 6.18 Euler’s Theorem

Let $a$ and $n$ be integers such that $n>0$ and $\gcd(a,n)=1$. Then $a^{\phi(n)}\equiv1(\mod n)$

### Theorem 6.19 Fermat’s Little Theorem

Let $p$ be any prime number and suppise that $p\not|a(p$ does not divide $a$). Then $$a^{p-1}\equiv1(\mod p)$$

Furthermore, for any integer $b, b^p\equiv b(\mod p)$

## Algebraic Coding Theory

### weight

The weight $w(x)$ of a binary code word $x$ is the number of 1s in $x$, $w(x)=d(x,0)$

### Theorem 8.17

Let $x$ and $y$ be binary n-tuples. Then $w(x + y) = d(x, y)$

### Theorem 8.18

Let $d_{\min}$ be the minimum distance for a group code $C$. Then $d_{\min}$ is the minimum of all the nonzero weights of the nonzero codewords in $C$. That is
$$d_{\min}=\min{w(x):x\not=0}$$

### Theorem 8.21

Let $\mathbb{M}_{m\times n}$ denote the set fo all $m\times n$ matrices with entries in $\mathbb{Z}_2$. We do matrix operations as usual except that all our addition and multiplication operations occur in $\mathbb{Z}_2$. Define the null sppace of a matrix $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$ to be the set of all binary n-tuples $x$ such that $Hx=0$. We denote the null space of a matrix $H$ by Null$(H)$

Let $H$ be in $\mathbb{M}_{m\times n}(\mathbb{Z}_2)$. Then the null space of $H$ is a group code.

### Theorem 8.25

If $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$ is a canonical parity-check matrix, then Null$(H)$ consists of all $x\in\mathbb{Z}_2^n$ whose first $n-m$ bits are arbitrary but whose last $m$ bits are determined by $Hx=0$. Each of the last $m$ bits serves as an even parity check bit for some of the first $n-m$ bits. Hence, $H$ gives rise to an $(n,n-m)$-block code

### Theorem 8.26

Suppose that $G$ is an $n\times k$ standard generator matrix. Then $C={y:Gx=y for x\in\mathbb{Z}_2^k}$ is an $(n,k)$-block code. More specifically, $C$ is a group code

### Lemma 8.27

Let $H=(A|I_m)$ be an $m\times n$ canonical parity-check matrix and $G=(\dfrac{I_{n-m}}{A})$ be the corresponding $n\times(n-m)$ standard generator matrix. Then $HG=0$

### Theorem 8.28

Let $H=(A|I_m)$ be an $m\times n$ canonical parity-check matrix and let $G=(\dfrac{I_{n-m}}{A})$ be the $n\times(n-m)$ standard generator matrix associated with $H$. Let $C$ be the code generated by $G$. Then $y$ is in $C$ if and only if $Hy=0$. In particular, $C$ is a linear code with canonical parity-check matrix $H$

### Proposition 8.30

Let $e_i$ be the binary n-tuple with a 1 in the ith coordinate and 0’s elsewhere and suppose that $H\in\mathbb{M}_{m\times n}(\mathbb{Z}_2)$. Then $He_i$ is the ith column of the matrix $H$

### Theorem 8.31

Let $H$ be an $m\times n$ binary matrix. Then the null space of $H$ is a single error-detecting code if and only if no column of $H$ consists entirely of zeros

### Theorem 8.34

Let $H$ be a binary matrix. The null space of $H$ is a single error-correcting code if and only if $H$ does not contain any zero columns and no two columns of $H$ are identical

### Proposition 8.36

If $H$ is an $m\times n$ matrix and $x\in\mathbb{Z}_2^n$, then we say that the syndrome of $x$ is $Hx$

Let the $m\times n$ binary matrix $H$ determine a linear code and let $x$ be the received n-tuple. Write $x$ as $x=c+e$, where $c$ is the transmitted codeword and $e$ is the transmission error. The the syndrome $Hx$ of the received codeword $x$ is also the syndrome of the error $e$

### Proposition 8.43

Let $C$ be an $(n,k)$-linear code given by the matrix $H$ and suppose that $x$ and $y$ are in $\mathbb{Z}_2^n$. Then $x$ and $y$ are in the same coset of $C$ if and only if $Hx=Hy$. That is, two n-tuples are in the same coset if and only if their syndromes are the same

## Isomorphisms

### Isomorphism

If $G$ is isomorphic to $H$, we write $G\cong H$. The map $\phi$ is called an isomorphism

### Theorem 9.7

All cyclic groups of infinite order are isomorphic to $\mathbb{Z}$

### Theorem 9.8

If $G$ is a cylic group of order $n$, then $G$ is isomorphic to $\mathbb{Z}$

### Corollary 9.9

If $G$ is a group of order $p$, where $p$ is a prime number, then $G$ is isomorphic to $\mathbb{Z}_p$

### Theorem 9.12

Every group is isomorphic to a group of permutations

### Proposition 9.13

Let $G$ and $H$ be groups. The set $G\times H$ is a group under the operation $(g_1,h_1)(g_2,h_2)=(g_1g_1,h_1h_2)$ where $g_1,g_2\in G$ and $h_1,h_2\in H$

### External Direct Product

The group $G\times H$ is called the external direct product of $G$ and $H$. Notice that there is nothing special about the fact that we have used only two groups to build a new group. The direct product $$\prod^n_{i=1}G_i=G_1\times G_2…G_n$$ of the groups $G_1,G_2…G_n$ is defined in exactly the same manner. If $G=G_1=G_2…G_n$, we often write $G^n$ instead of $G_1\times G_2…G_n$

### 9.17

Let $(g,h)\in G\times H$, If $g$ and $h$ have finite orders $r$ and $s$ respectively, then the order of $(g,h)$ in $G\times H$ is the least common multiple of $r$ and $s$

### Corollary 9.18

Let $(g_1,…,g_n)\in\prod G_i$. If $g_i$ has finite order $r_i$ in $G_i$, then the order of $(g_1,…,g_n)$ in $\prod G_i$ is the least common multiple of $r_1,…,r_n$

### Theorem 9.21

The group $\mathbb{Z}_m\times\mathbb{Z}_n$ is isomorphic to $\mathbb{Z}_{mn}$ if and only if $\gcd(m,n)=1$

### Corollary 9.22

Let $n_1,…,n_k$ be positive integers. Then $$\prod^k_{i=1}\mathbb{Z}_{n_i}\cong\mathbb{Z}_{n_1…n_k}$$ if and only if $\gcd(n_i,n_j)=1$ for $i\not=j$

### Corollary 9.23

If $$m=p_1^{e_1},…,p_k^{e_k}$$ where the $p_is$ are distinct primes, then

$$\mathbb{Z}_{m_{}}\cong\mathbb{Z}_{p_1^{e_1}}\times…\times\mathbb{Z}_{p_k^{e_k}}$$

## Internal Direct Products

### Internal Direct Product

Let $G$ be a group with subgroups $H$ and $K$ satisfying the following conditions

• $G=HK={hk:h\in H,k\in K}$
• $H\cap K={e}$
• $hk=kh$ for all $k\in K$ and $h\in H$

then $G$ is the internal direct product of $H$ and $K$

### Theorem 9.27

Let $G$ be the internal direct product of subgroups $H$ and $K$. Then $G$ is isomorphic to $H\times K$

### Theorem 9.28

The group $\mathbb{Z}_6$ is an internal direct product of subgroups $H_i$, where $i=1,2…n$. Then $G$ is isomorphic to $\prod_iH_i$

## 10 Normal Subgroups and Factor Groups

### Normal Subgroups

A subgroup $H$ of a group G is normal in $G$ if $gH=Hg$ for all $g\in G$. That is,a normal subgroup of a group $G$ is one in which the right and left cosets are precisely the same

### Theorem 10.3

Let $G$ be a group and $N$ be a subgroup of $G$. Then the following statements are equivalent

1. The subgroup $N$ is normal in G
2. Forall $g\in G, gNg^{-1}\subset N$
3. For all $g\in G, gNg^{-1}=N$

### Factor Groups

If $N$ is a normal subgroup of a group $G$, then the cosets of $N$ in $G$ form a group $G/N$ under the operation $(aN)(bN)=abN$. The group is called the factor or quotient group of $G$ and $N$

### Theorem 10.4

Let $N$ be a normal subgroup of a group $G$. The cosets of $N$ in $G$ form a group $G/N$ of order $G/N$

### Simple Groups

Groups with nontrivial normal subgroups are called simple groups

### Lemma 10.8

The alternating group $A_n$ is generated by 3-cycles for $n\ge3$

### Lemma 10.9

Let $N$ be a normal subgroup of $A_n$, where $n\ge3$. If $N$ contains a 3-cycle, then $N=A$

### Lemma 10.10

For $n\ge5$, every nontrivial normal subgroup $N$ of $A_n$ contains a 3-cycle

### Theorem 10.11

The alternating group $A_n$ is simple for $n\ge5$

## 11 Group Homomorphisms

### Homomorphisms

A homomorphism between groups $(G,\cdot)$ and $(H,\circ)$ is a map $\phi:G\to H$ such that $$\phi(g_1\cdot g_2)=\phi(g_1)\circ\phi(g_2)$$ for $g_1,g_2\in G$. The range of $\phi$ in $H$ is called the homomorphic image of $\phi$

### Proposition 11.4

Let $\phi:G_1\to G_2$ be a homomorphism of groups. Then

1. If $e$ is the identity of $G_1$, then $\phi(e)$ is the identity of $G_2$
2. For any element $g\in G_1, \phi(g^{-1})=[\phi(g)]^{-1}$
3. If $H_1$ is a subgroup of $G_1$, then $\phi(H_1)$ is a subgroup of $G_2$
4. If $H_2$ is a subgroup of $G_2$, then $\phi^{-1}(H_2)-{g\in G_1:\phi(g)\in H_2}$ is a subgroup of $G_1$. Furthermore, if $H_2$ is normal in $G_2$, then $\phi^{-1}(H_2)$ is normal in $G_1$

### Kernel

Let $\phi:G\to H$ be a group homomorphism and suppose that $e$ is the identity of $H$. By Proposition 11.4, $\phi^{-1}({e})$ is a subgroup of $G$. This subgroup is called the kernel of $\phi$ and will be denoted by $\ker\phi$

### Theorem 11.5

Let $\phi:G\to H$ be a group homomorphism. Then the kernel of $\phi$ is a normal subgroup of $G$

### Canonical Homomorphism

Let $H$ be a normal subgroup of $G$. Define the natural or canonical homomorphism $$\phi:G\to G/H$$ by $$\phi(g)=gH$$ This is indeed a homomorphism since $$\phi(g_1g_2)=g_1g_2H=g_1Hg_2H=\phi(g_1)\phi(g_2)$$ The kernel of this homomorphism is $H$

### Theorem 11.10 First Isomorphism Theorem

If $\phi:G\to H$ is a group homomorphism with $K=\ker\psi$, then $K$ is normal in $G$. Let $\phi:G\to G/K$ be the canonical homomorphism. Then there exists a unique isomorphism $\eta:G/K\to\psi(G)$ such that $\psi=\eta\phi$

### Theorem 11.12 Second Isomorphism Theorem

Let $H$ be a subgroup of a group $G$ (not necessarily normal in $G$) and $N$ a normal subgroup of $G$. Then $HN$ is a subgroup of $G, H\cap N$ is a normal subgroup of $H$, and $$H/N\cap N\cong HN/N$$

### Theorem 11.13 Correspondence Theorem

Let $N$ be a normal subgroup of a group $G$. Then $H\mapsto H/N$ is a one-to-one correspondence between the set of subgroups $H$ containing $N$ and the set of subgroups of $G/N$. Furthermore, the normal subgroups of $G$ containing $N$ correspond to normal subgroups of $G/N$

### Third Isomorphism Theorem

Let $G$ be a group and $N$ and $H$ be normal subgroups of $G$ with $N\subset H$. Then $$G/H\cong\dfrac{G/N}{H/N}$$

1 / 1