\documentstyle[12pt]{article}
\setlength{\oddsidemargin}{-.75in}
\setlength{\evensidemargin}{-.75in}
\setlength{\textwidth}{7.8in}
\setlength{\topmargin}{-1.25in}
\setlength{\textheight}{10.5in}
\setlength{\parskip}{6pt}
\setlength{\parindent}{0in}
\pagestyle{\empty}

\begin{document}
\setlength{\baselineskip}{6pt}
{\scriptsize

number of unordered sets with repetition (r-things from n-set) = $\left( \begin{array}{c} n + r - 1 \\ r \end{array} \right) $ \par
number of solutions to: $x_1 + x_2 + \cdots + x_n = r$,  = $\left( \begin{array}{c} n + r - 1 \\ r \end{array} \right) $ \par

given {\bf a} letters to make {\bf b} letter words, number = $\left( \begin{array}{c} a + b - 1 \\ a \end{array} \right) $ \par



{\bf Euclid's Algorithm:}

\begin{tabular}{rlrl}
E.g.: gcd(2406,654) &
= gcd(654,444) since 2406 = 654x3 + 444 & 6 &
= 24 - 18x1 = 1x24 + (-1)x18 \\
 & = gcd(444,210) since 654 = 444x1 + 210 & &
= 24 + (-1)x(210-24x8) = (-1)x210 + 9x24 \\
 & = gcd(210,24) since 444 = 210x2 + 24 & &
= -210 + 9x(444-210x2) = 9x444 + (-19)x210 \\
 & = gcd(24,18) since 210 = 24x8 + 18 & &
= 9x444 + (-19)x(654-444x1) = (-19)x654 + 28x444 \\
 & = gcd(18,6) since 24 = 18x1 + 6 & &
= (-19)x654 + 28(2406-654x3) = 28x2406+ (-103) x 654 \\
 & = 6 since 18=6x3. & & \\
\end{tabular}

$X \rightarrow Y$ by $f$. Injective means $f(x_{1})=f(x_{2})
\rightarrow x_{1}=x_{2}$.  Surjective means $f(X)=Y$ (all elements of
$Y$ hit).  Bijective $\leftrightarrow$ has an inverse. \par
Surjection: every $y \in Y$ is a value $f(x)$ for {\it at least one} $x \in X$. \par
Injection:  every $y \in Y$ is a value $f(x)$ for {\it at most one} $x \in X$. \par
\vspace{0.3 in}

\begin{math}
\left( \begin{array}{c} n \\ k \end{array} \right) =
\frac{n!}{(n-k)!k!} \; \bullet \;
\left( \begin{array}{c} n \\ k \end{array} \right) =
\left( \begin{array}{c} n \\ n-k \end{array} \right) \; \bullet \;
\left( \begin{array}{c} n+1 \\ k \end{array} \right) =
\left( \begin{array}{c} n \\ k-1 \end{array} \right) +
\left( \begin{array}{c} n \\ k \end{array} \right)
\end{math}

{\bf Equivalence} classes partition $X$.  A partition is: $C_{x} \ni
\forall x \in X, \;  x \in$ one and only one ``block'' i.e.\ $C_{x} =
C_{y}$ if $x \sim y$.  A vector is an equivalence class of directed
line segments.\par
\vspace{0.1 in} {\bf notation (example):} $(a,b) \sim (c,d) \longleftrightarrow
ad=bc$;  Equivalence Class': $[(a,b)] = \{(ax,bx)| x \in Z, x\neq 0\}$; Representatives: $\{(a,b)|b>0, gcd(a,b)=1 \}$. \par


{\bf Congruence:} $a \equiv_{n} b \; n \in N$ means 1.\ $n | (a-b)$
2.\ $a=b+kn \; k \in Z$ 3.\ $a$ mod $n = b$ mod $n$.  Preserves + and
*.  $[x]$ is an equivalence class. $a^{-1}$ mod $n$ exists
$\leftrightarrow \; (a,n)=1$.  Proof: $ax \equiv_{n} 1 \;
ax_{0}=1+ny_{0} \; ax_{0} - ny_{0} = 1 \; (a,n) = 1$ (relatively
prime).

{\bf Fermat's Theorem:} for $p$ prime and $a$ not $\equiv_{p} 0
\rightarrow a^{p-1} \equiv_{p} 1$.  Proof:  $a$ and $p$ are relatively
prime; let $f$ be multiplication by $a$ is bijective (has an inverse).
Since they're both in $Z_{p}, \;  \{[1],[2],...[p-1]\} = 
\{[a],[2a],...,[a(p-1)]\}$ ($[0]$ goes to $[0]$ since $a$ is not
$\equiv_{p} 0$).  Multiply both sets together: $[a][2a][3a] \cdot
\cdot \cdot [a(p-1)] \equiv_{p} [1][2][3] \cdot \cdot \cdot [p-1] 
\rightarrow a^{p-1}[1][2] \cdot \cdot \cdot [p-1] \equiv_{p} [1][2]
\cdot \cdot \cdot [p-1] \rightarrow a^{p-1} \equiv_{p} 1.$ Q.E.D.

{\bf Cryptography:}  S = $\{ \leq 200$ digit decimal numbers $\}$.
$E_{A}$: public encryption algorithm.  $D_{A}$: secret decryption
algorithm.  For $B$ to send to $A$: $B: x \rightarrow B$ does $E_{A}
\rightarrow A$ does $D_{A} \rightarrow x: A$ or even better: $B: x
\rightarrow B $ does $D_{B} \rightarrow B $ does $E_{A} \rightarrow A$
does $D_{A} \rightarrow A $ does $E_{A} \rightarrow x: A$

{\bf RSA:} $p,q$ are 100 digit secret primes.  $n=pq$ is public.
$m=(p-1)(q-1)$ and is secret.  $e \ni (e,m)=1$ is public. $d \ni ed
\equiv_{m} 1$ is secret.  Then $E_{A}$ is $x^{e}$ mod $n \rightarrow
y$ and $D_{A}$ is $y^{d}$ mod $n \rightarrow x$.  It is therefore
necessary to prove: $x^{ed} \equiv_{n} x$.  Proof: $ed=1+rm \bullet
x^{ed}=x(x^{m})^{r} \bullet x^{m}=x^{(p-1)(q-1)} \bullet
x^{p-1}\equiv_{p}1 \bullet x^{q-1}\equiv_{q}1 \bullet
x^{(p-1)(q-1)}\equiv_{p}1 \bullet x^{(q-1)(p-1)}\equiv_{q}1 \bullet
x^{m}\equiv_{p}1 \bullet x^{m}\equiv_{q}1 \bullet p|x^{m}-1 \bullet
q|x^{m}-1 \bullet pq|x^{m}-1 \bullet x^{m}\equiv_{pq}1 \bullet
x^{m}\equiv_{n}1 \bullet x(x^{m})^{r}\equiv_{n}x$.  Q.E.D.

A quick way to calculate $x^{e}$: write $e$ in binary: $e_{k}2^{k} +
e_{k-1}2^{k-1} + \cdots + e_{0}$, where $e_{i}$ is either 0 or 1. $
x^{e}=x^{\Sigma e_{i}2^{i}} = \Pi x^{e_{i}2^{i}}$.  Successively
square $x: x, x^{2}, x^{4}, x^{2^{3}}, x^{2^{4}},...$ $k$ steps to
produce the squares.  $k$ steps to multiply $x^{e_{i}2^{i}}$'s
together.  $2^{k}\approx 1200$ steps.

{\bf Carmichael number:} composite $n=p_{1}p_{2}\cdots p_{k}
\ni (p_{i}-1)|(n-1) \forall i$ e.g.\ $561=3x11x17$.

{\bf Graph Theory:} $\delta(v)=$ the valency of $v$ = the number of
edges ending at $v$.  Let $V=\{v_{1},v_{2},...,v_{n}\}$ and
$E=\{e_{1},e_{2},...,e_{n}\}$.  A {\em Graph} has at most one edge
between vertices.  A {\em multigraph} can have repeated edges and
loops.  A {\em digraph} is a directed graph.  Multidigraph, weighted
screltgraph, etc.  A {\em Tree} has an unambiguous distance from any
vx.\ to any other vx., no cycles, is connected, and can be rooted.  A
{\em path} is a succession of adjacent vertices with no repititions.
A {\em walk} is the same as a path, but with repititions allowed.  A
{\em cycle} is a path except that the first and last vertices are the
same.  A {\em circuit} is a closed walk. {\em Planarity} refers to a
graph which can be drawn in the plane without ``apparent'' edge
crossings.  A planar graph has $r$ regions, $r-1$ of which are finite.
The boundries of the finite regions form a maximal set of independent
cycles.  \par

If graph r-valent, $r \cdot |V| = 2 \cdot |E|$. \par

$n=m+1$ (number of vertices = number of edges + 1) $\Leftrightarrow$
graph is a tree.

(number of independent cycles) $\rho=m-n+1$.  For planar graphs:
$r=m-n+2$.  Edge sides are both $=2m$ and $\geq 3r$ (@ least 3 edges per cycle).
Coloring: $\delta (v) \leq K$, $\forall \in G \longrightarrow _{x}(G) \leq K+1$. \par

{\bf Kuratowski's Theorem:} non-planar $\Leftrightarrow$ has a
subgraph which is $K_{3,3}$ or $K_{5}$ except for inessential vertices
(valence is 2).

{\bf Algebra:} Binary operation on set $S$: given $a,b\in S$ produces
$c\in S$ i.e.\ $(a,b) -*\rightarrow a*b$ i.e.\ an ordered pair
$\rightarrow$ element.  A function: $S^{2} \rightarrow S$.  An n-ary
operation would be: $S^{n} \rightarrow S$.

A {\bf \em Group}: is a set $G$ and a binary operation *, with the
following properties: 1.\ closure: $a*b \in G \; \forall a,b \in G$;
2.\ associativity: $(a*b)*c = a*(c*b) \; \forall a,b,c \in G$; 3.\
identity: $\exists e \in G \ni e*a=a*e=a \; \forall a\in G$; 4.\ inverse:
$\forall a\in G \; \exists b\in G \ni b*a=a*b=e$.  It also might be true
that the group is: 5.\ commutative (abelian): $a*b=b*a \; \forall a,b \in
G$; 6.\ finite.  There are three kinds of non-abelian groups:  1.\
matrices, 2.\ groups of permutations, 3.\ symmetries of geometric
objects.

The identity is unique.  Proof: let $e, e'$ be identities.
$e*e'=e=e'$.  The inverse is unique.  Proof: let $b, b'$ be inverses
to $a$, $(b*a)*b'=e*b'=b'$, but $b*(a*b')=b*e=b$.
$(xy)^{-1}=y^{-1}x^{-1}$.  Group tables are only for finite groups.
An alternative is generators and relations.  E.g.\ group is $D_{6}$;
generators are: $a=$ rot by $120^{o}$, and $b=$ flip across y axis;
relations are: $a^{3}=1 \; b^{2}=1 \; ba=a^{2}b.$  The {\em order} of
element $x$ is the smallest $n \ni x^{n}=1$.  $x^{k}=1 \Leftrightarrow
o(x)|k$.  There is only one 3-element group table ($C_3$).

{\bf Isomorphism of groups} is a map ($f$) between two groups which is
bijective and which preserves the composition law.  A {\em subgroup}
$H$ of group $G$ is a subset of $G$ which is also a group with the
same law of composition.

{\bf Lagrange's Theorem:}  $G$ is a finite group, and $H$ is a
subgroup $\rightarrow o(H)|o(G)$.  The {\em right coset} of $H$
determined by $a$ is $Ha$, i.e.\ $\{ha\} \; \forall h \in H$.

There is only one group of order $p$ ($p$ is prime).  Proof: pick any
$x\neq 1$ in $G$ (where $o(G)=p$).  Generate cyclic subgroup
$<\!x\!>$.  Since it's a subgroup, $o(<\!x!>)|o(G)$.  Since $p$ is
prime, $o(<\!x\!>)=o(G)$.  Therefore, $<\!x\!>=G$.

{\bf Cayley's Theorem:} Every finite group is pseudo-isomorphic to the
group of symmetries of a number of things equal to its order.  I.e.\
$G\simeq S_{n}$, where $n=o(G)$.  The mapping is injective, but not
surjective.  

{\bf Structure theorem:} For abelian groups only. $o(G)<\infty \; o(G)
= n = p_{1}^{e_{1}}p_{2}^{e_{2}} \cdots p_{n}^{e_{n}} \bullet G \simeq
G_{p_{1}^{e_{1}}}G_{p_{2}^{e_{2}}} \cdots G_{p_{n}^{e_{n}}} \bullet
G_{p^{e}} \simeq C_{p^{f_{1}}} \times C_{p^{f_{2}}} \times \cdots
\times C_{p^{f_{k}}}.$

{\bf Chinese remainder theorem} isomorphism:  $[C]_{n} \simeq
([C_1]_{n_{1}}, [C_{2}]_{n_{2}}, \ldots, [C_{k}]_{n_{k}})$ where $C
\equiv_{n_{1}} C_{1}$ and $n=n_{1} n_{2} \cdots n_{k}$ and
$n_{i}=p_{i}^{e_{i}}$.  To get back from the (...) form, find $x_{k}
\ni x_{k}\equiv_{n_{j}} 0$ if $j\neq k$ and 1 if $j=k$.  To do this,
set $x_{k}=a\Pi_{j\neq k} n_{j}$ for some $a$.  Then, $C = C_{1}x_{1}
+ C_{2}x_{2} + \cdots + C_{k}x_{k} \bmod n$.

{\bf Groups acting on sets:} group $G$ acts on set $S$.  $x\in S$.
$orbit(x) = \{ g(x) | g \in G \} \equiv Gx$.  Orbits partition $S$
under $G$; Proof: let $\sim$ be such that $x\sim y \rightarrow x,y$
same orbit.  $x \sim y \Leftrightarrow g(x)=y$ for some $g\in G$.
$[x]=Gx$ and equivalence classes always partition (see above).  The
{\em stability subgroup} (or {\em stabilizer}) is $G_x \equiv \{ g |
g(x)=x \}$.  Note that $Gx$ is a subset of $S$ and $G_x$ is a subgroup
of $G$.  $o(G) = o(G_x)\cdot o(Gx)$.  The proof involves creating a
bijective mapping $\phi: G - \phi \rightarrow Gx \ni g \rightarrow
g(x)$. $F(g)\equiv$ fixed point set of $ g = \{ x\in S | g(x)=x \}$.
{\bf Burnside's counting theorem:}  The number of orbits = the average
size of the fixed point sets = $\frac{1}{|G|}\sum_{g\in G}|F(g)|$.


{\bf Rings and Fields:}  A Ring is a set ($R$) and two binary operations +
and *, such that 1.\ $(R,+)$ is an abelian group (call the identity
0); 2.\ $R$ is associative with respect to *, $(ab)c=a(bc)$; 3. \ * has an
identity (call it 1); 4.\ the distributive property holds, $a(b+c) =
ab + ac$ and $(b+c)a = ba + ca$.  If $R$ is commutative, it's called
commutative, not abelian.  A commutative ring with cancelation
($ax=ay, a\neq 0 \rightarrow x=y$) is called an {\em Integral Domain}.
An integral domain with $\div$ (i.e.\ $a\neq 0 \rightarrow \exists
a^{-1} \ni aa^{-1}=1$) is a {\em Field}.  $Z_p$ is a field.

Isomorphism of rings is a bijective map: $R -f\rightarrow R' \ni
f(x+y)=f(x)+f(y)$ and $f(xy)=f(x)f(y)$.  The {\em units} of a ring are
$x \ni \exists x^{-1}$.  The units of a ring form a multiplicative
group with * called $R^{*}$.

{\bf Polynomials:} Coefficients must be a ring.  A polynomial is
therefore a sequence of elements of a ring.  $f(x)=(x-c)q+r \ni
\partial^0(r) < 1 \rightarrow r=f(c)$ (to prove, plug in $c$).
Substitution is a homomorphism: $h(x)=f(x)g(x) \rightarrow
h(c)=f(c)g(c)$.  Factor Theorem: $f(x)=(x-c)b(x) \Leftrightarrow
f(c))=0$.  A polynomial of degree $n$ over the field $F$ has at most
$n$ roots in $F$.  Proof by induction.

{\bf Finite fields other than $Z_p$:}  Enlarge $Z_p$ like enlarging
$R$ to $C$:  Find a polynomial with no roots.  Declare something to be
a root.  E.g. $Z_3$ has no root for $x^3 + 2x + 1 = 0$.  Define
$\beta$ to be a root of that: $\beta^3 = \beta + 2$.  Then the field
$F = \{ a_0 + a_1\beta + a_2\beta^2 | a_n \in Z_3 \}$. 

In any finite field the {\em characteristic} of $F$ is the order of
the multiplicative identity (1) with respect to addition. $(F,+)
\simeq Z_{p_1} \times Z_{p_2} \times \cdots \times Z_{p_k}$.  $F^* $
($F$ without 0) $\simeq$ the cyclic group of size $o(F^*)$.

{\bf Coding} is building in redundancy in order to detect and/or
correct errors.  $k$-bit message words $\rightarrow n$-bit transmitted
messages.  $V^k \rightarrow W^n$. $(x_0,x_1,\ldots,x_{k-1})
\rightarrow (z_0,z_1,\ldots,z_{n-1})$. $\vec{z}^T = G\vec{x}^T$, where
$G$ is a matrix, is a {\em linear code}.  $\delta \equiv$ the minimum
distance between any two distinct codewords.  If $\delta \geq e+1$,
then the code detects $e$ errors.  If $\delta \geq 2e+1$, then the
code corrects $e$ error.  Around codeword $\vec{c}$, there is an
$S_e(\vec{c})$ sphere of radius $e$ around of errors. $S_e(\vec{c})| =
\vec{c} + \vec{c} $ with 1 error $+ \vec{c} $ with two errors $ +
\cdots + \vec{c}$ with $e$ errors. $|S_e(\vec{c})| = 1 + n + \left(
\begin{array}{c} n \\ 2 \end{array} \right) + \cdots \left(
\begin{array}{c} n \\ e \end{array} \right)$.  Using a linear code
means: the set of codewords is a subgroup of $W^n$, $\partial(z_1,z_2) =
\|z_1 - z_2\| = z_i$ for some $i$, $\{$ all $
\partial(\vec{c}_1,\vec{c}_2)\} \simeq \{ $ all weights
$\|\vec{c}_i\|\}$, $\delta = $ minimum distance between codewords =
minimum weight of a codeword.  Basic Inequality: $|C| \cdot |S_e| \leq |W|$.
Perfect $\longleftrightarrow |C| \cdot |S_e| = |W|$.

{\bf The Hamming Code:} (syndrome mapping) $V^k - G \rightarrow W^n -
H \rightarrow S^{n-k}$.  Make $H$ such that $\vec{w}$ is a codeword
$\Leftrightarrow H\vec{w}^T=0$.  To correct one error: $\vec{w}^T =
G\vec{c}^T + \vec{e}^T \rightarrow H\vec{w}^T =$ the $i$th column of
$H$.  This limits the size of $H$ to such that it has unique columns.
The maximum width of $H$ is $2^{n-k}-1$.

The Hamming code ($n=7,k=4$) is $H =
\left[ \begin{array}{lllllll}
1 & 0 & 1 & 0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 
\end{array} \right] $ produces equations: $z_1=z_3+z_5+z_7,
z_2=z_3+z_6+z_7,z_4=z_5+z_6+z_7$, i.e.\ $z_1, z_2,$ and $z_4$ are the
check bits.

{\bf Polynomial codes:} The difference between this and linear codes
is that multiplication is for polynomials.  $G$ is now $g(x)$ a
polynomial multiplication from $V[x] \rightarrow W[x]$.  $g(x)$ is
irreducable of $F$ and degree $n-k$.  Since $g(x)$ is irreducible, it
has some ``roots'' which can be plugged into a received $w(x)$.  If
this is 0, then no errors.

The {\bf Reed-Solomon code} is a polynomial code.  For example, over
$F^* = <\!\alpha\!>$ without 0 (15 elements). An elements of the field
is are a polynomial of degree 3 in $\alpha$.  A message thing is a
polynomial in field elements.  $V^{11} - g(x) \rightarrow W^{15} - h(x)
\rightarrow S^4.  g(x) =
(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)$, corrects two errors. 
To correct another, add $(x-\alpha^5)(x-\alpha^6)$, etc.  $h(w(x)) =
(w(\alpha), w(\alpha^2), w(\alpha^3), w(\alpha^4)) = (0,0,0,0)
\Leftrightarrow g(x) | w(x) \rightarrow$ no errors.

{\bf Reed-Solomon-Hamming} ?

{\bf BCH code:} Over a finite field, but message things are lists of
elements, rather than lists of bits.  Message things are not
polynomials.  Coefficients are not in $Z_2$.  $g(x)$ is the smallest
polynomial over $Z_2$ with $\alpha, \alpha^2, \alpha^3,$ and $\alpha^4$ as
roots.  For example, for a field generator of $x^4+x+1$, this
polynomial is $(x^4+x+1)(x^4+x^3+x^2+x+1)$.

{\bf note: multiply permutations right to left!}

}
\end{document}
