%% LyX 1.5.6 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.

\input{crypto_preamble.tex}
\usepackage{hyperref}
 % needed for chunk1
\usepackage{boxedminipage}
 % needed for chunk3

\makeatother

\usepackage{babel}

\begin{document}
\handout{0368.4163 Randomness and Computation} {Ronitt Rubinfeld} {04
March 2009} {Spring 2009} {Lecture 1} % title
 { D{}. Sotnikov} 


\section*{The Erdos Probabilistic Method}

In order to prove the existence of a mathematical objec with desirable properties,
is enough to define appropriate probability space and to show that a random
point in the space is a mathematical object with the desirable properties with
positive probability thus one can conclude that such a mathematical object exists.
The important point is that this method of proof is nonconstructive so it does
not create an example of object. (http://en.wikipedia.org/wiki/Probabilistic\_method)

\begin{description}
\item [{{Example 1:}}]~


Let $S$ be a set of objects and $s_{1},...,s_{m}\subseteq S$ each $s_{i}$
is of size $l\geq2$. Can we 2-color $S$ so that each $s_{i}$ has one of each
color? 

\item [{Claim:}] In the global case the answer is \textbf{No} but for special case
$m<2^{l-1}$ the answer is \textbf{Yes}. 
\item [{Theorem 1:}] If $m<2^{l-1}$ exist proper 2-coloring such that each $s_{i}$
has one of each color.
\item [{Remark.}] Recall the union bound: $Pr[A\bigcup B]\leq Pr[A]+Pr[B]$
\item [{{Proof of the Theorem 1:}}]~

\begin{itemize}
\item Randomly color elements of $S$ to red/blue colors
\item $\forall i\quad Pr[s_{i}\; monochromatic]=\dfrac{1}{2^{l}}+\dfrac{1}{2^{l}}=\dfrac{2}{2^{l}}=\dfrac{1}{2^{l-1}}$
(the probability to color all $l$ elements to same color is $\dfrac{1}{2^{l}}$
and we have 2 colors)
\item $Pr[\exists i\; s.t.\; s_{i}\; monochromatic]\leq\underset{i=1}{\overset{m}{\sum}}Pr[s_{i}\; monochromatic]\leq\dfrac{m}{2^{l-1}}<1$
(union bound) 
\item $Pr[all\; s_{i}'s\; properly\; colored]=1-Pr[\exists i\; s.t.\; s_{i}\; monochromatic]>0$
\end{itemize}
$\Longrightarrow$exists setting of colors which gives proper coloring

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\square$

\item [{Definition:}] For $A$ a subset of positive integers, $A$ is sum-free if
$\nexists a_{1},a_{2},a_{3}\in A$ s.t. $a_{1}+a_{2}=a_{3}$.
\item [{{Example 2:}}]~


Let $B$ be a set of positive integers. Is it always exists a subset $A$ of
$B$ such taht $A$ is sum-free and the size of $A$ is $>\frac{|B|}{3}$ ?

\end{description}
For example for the set $B=\{1,...,n\}$ two different subsets that satisfy
the claim: $A=odd\; integers$ and $A'=\{\frac{n}{2}+1,...,n\}$, such that
the size of each of them is $\approx\frac{n}{2}$.\\
\\
\\
\\


\begin{description}
\item [{Theorem:}] {[}Erdos] $\forall B=\{b_{1},...,b_{n}\}$ exists sum-free $A\subseteq B$
s.t. $|A|>\frac{n}{3}$.
\item [{Remark.}]~

\begin{itemize}
\item $\mathbb{Z}_{p}=\#'s\; mod\; p=\{0..p-1\}$
\item $\mathbb{Z}_{p}^{*}=\#'s\; mod\; p\; relative\; prime\; to\; p=\{1..p-1\}$
\end{itemize}
\item [{{Proof of the Erdos Theorem:}}]~

\begin{itemize}
\item w.l.o.g. $b_{n}$ is the maximal value of $B$.
\item Pick prime $p>2\cdot b_{n}$ s.t. $p\equiv2\,(mod\,3)$ (such number always
exists, see the Dirichlet's theorem on arithmetic progressions\\
http://en.wikipedia.org/wiki/Dirichlet\%27s\_theorem\_on\_arithmetic\_progressions)
\item $p=2k+3$ for some integer $k$.
\item let $C=\{k+1,...,2k+1\}$, $C$ is sum-free even $mod\: p$ because 

\begin{itemize}
\item $(k+1)+(k+1)=2k+2>2k+1$ 
\item $(2k+1)+(2k+1)=4k+2=k\:(mod\: p)=k<k+1$. 
\end{itemize}
\item $\frac{|C|}{p-1}=\frac{k+1}{3k+1}>\frac{1}{3}$
\item Pick $x\in_{R}\{1..p-1\}=\mathbb{Z}_{p}^{*}$ 

\begin{itemize}
\item $\forall i\quad let\; d_{i}\leftarrow x\cdot b_{i}\,(mod\, p)$
\item $A_{x}\leftarrow\{b_{i}\; s.t.\; d_{i}\in C\}$
\end{itemize}
\end{itemize}
Now for finish the proof we need to show:

\begin{itemize}
\item $\forall x$ $A_{x}$ is sum-free
\item $\exists x\; s.t.\;|A_{x}|>\frac{n}{3}$
\end{itemize}
\item [{{Claim 1:}}] $\forall x$ $A_{x}$ is sum-free
\item [{{Proof of the Claim 1:}}] In the way of contradiction, suppose that $\exists b_{i},b_{j},b_{k}\in A_{x}$
s.t. $b_{i}+b_{j}=b_{k}$ this implies that also $b_{i}+b_{j} \equiv b_{k} (mod p)$,
multiply both sides by $x$ and get $x\cdot b_{i}+x\cdot b_{j}=x\cdot b_{k}\,(mod\, p)$
but $x\cdot b_{i},x\cdot b_{j},x\cdot b_{k}\in C$ contradiction to the fact
that $C$ is sum-free.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\square$

\item [{Fact:}] $\forall y\in\mathbb{Z}_{p}^{*}$ and $\forall i$ there exists
exactly one $x\in\mathbb{Z}_{p}^{*}$ s.t. $y\equiv x\cdot b_{i}\,(mod\, p)$,
i.e., $\forall y\; Pr[b_{i}\; maps\; to\; y]=\frac{1}{p-1}$ 
\item [{Proof of the Fact:}] $\mathbb{Z}_{p}^{*}$ is group $b_{i}\in\mathbb{Z}_{p}^{*}$
so exists $b_{i}^{-1}\in\mathbb{Z}_{p}^{*}$so exists $x=y\cdot b_{i}^{-1}\in\mathbb{Z}_{p}^{*}$.
If $x_{1}\cdot b_{i}\equiv x_{2}\cdot b_{i}\:(mod\: p)$ $\Rightarrow$multiply
both sides at from $b_{i}^{-1}$ at the right and get $x_{1}\equiv x_{2}\:(mod\: p)$.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\square$

\item [{{Claim 2:}$\exists x\; s.t.\;|A_{x}|>\frac{n}{3}$}]~
\item [{{Proof of the Claim 2:}}]~

\begin{itemize}
\item From the fact that we just proved, we get that $\forall i$ $|C|$ choices of
$x$ make $x\cdot b_{i}\in C$
\item let define the indicator function $\sigma_{i}=\begin{cases}
1 & if\: x\cdot b_{i}\in C\\
0 & otherwise\end{cases}$
\item $E[\sigma_{i}]=Pr[\sigma_{i}=1]=\frac{|C|}{p-1}>\frac{1}{3}$
\item $E[|A_{x}|]=E[\Sigma\sigma_{i}]=\Sigma(E[\sigma_{i}])>\frac{n}{3}$ (by the
linearity of expectation)
\end{itemize}
$\Rightarrow$$\exists x\; s.t.\;|A_{x}|>\frac{n}{3}$ because if for all the
x's $|A_{x}|\leq\frac{n}{3}$ then $\underset{x}{max}$$|A_{x}|\leq\frac{n}{3}$
and then expectation is less equal then $\frac{n}{3}$ in contradiction to $E[|A_{x}|]>\frac{n}{3}$.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\square$\end{description}

\end{document}
