%% 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\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}