\documentclass[10pt]{article} \usepackage{amssymb} \newtheorem{define}{Definition} %\newcommand{\Z}{{\mathbb{Z}}} %\usepackage{psfig} \oddsidemargin=0.15in \evensidemargin=0.15in \topmargin=-.5in \textheight=9in \textwidth=6.25in \newcommand{\plurality}{{\rm plurality}} \begin{document} \input{preamble.tex} %{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name} \lecture{3}{February 15, 2006}{Ronitt Rubinfeld}{David Shin} %%%% body goes in here %%%% \section{Linearity testing (continued)} We begin with some definitions and notation from last time. Throughout these notes, $G$ will always represent a finite group, and $F$ will represent a (not necessarily finite) group. \begin{definition} A function $f: G \rightarrow F$ is {\em linear} if $f(x)+f(y)=f(x+y)$ $\forall x,y \in G$ (also referred to as a {\em homomorphism}). \end{definition} \begin{definition} The {\em probability of group law failure} of a function $f: G \rightarrow F$ is $\Pr_{x,y}[f(x)+f(y)\neq f(x+y)]$. We use $\delta_f$ to denote this probability. \end{definition} \begin{definition} A function $f: G \rightarrow F$ is {\em $\epsilon$-linear} if there exists a linear function $g : G \rightarrow F$ s.t. $\Pr_x[f(x)=g(x)] \geq 1-\epsilon$. Let $\epsilon_f$ denote the smallest value of $\epsilon$ for which the given inequality holds. \end{definition} Recall the $\epsilon$-linear testing problem: we wish to determine whether a function $f: G \rightarrow F$ is $\epsilon$-linear. The algorithm should adhere to the following specifications: \begin{enumerate} \item If $f$ is linear, it should output $pass$ with probability 1. \item If $f$ is not $\epsilon$-linear, it should output $fail$ with high probability. \end{enumerate} The proposed test from last time was the following: \medskip \noindent \textbf{Algorithm $A$} \\ \DO~$r$ times:\\ \indent pick $x,y\in_R G$\\ \indent \IF~$f(x)+f(y)\neq f(x+y)$ output $fail$\\ output $pass$ \medskip It is straightforward to show by the sampling theorem that we referred to last time as the ``gap bound'' that if we set $r=\frac{c}{\delta}\log\frac{1}{\beta}$, algorithm $A$ outputs $pass$ with probability 1 if $f$ is linear, and outputs $fail$ with probability at least $1-\beta$ if $\delta_f \geq \delta$.\footnote{Using Chernoff bounds, one can actually distinguish the case when $f$ is $\epsilon'$-linear from the case when $f$ is not even $\epsilon''$-linear for constants $\epsilon'<\epsilon''$ in a similar number of samples.} To complete the analysis of this algorithm, then, we must simply establish some relationship between $\delta_f$ and $\epsilon_f$. Such a relationship, however, is not as straightforward as one might expect. To illustrate, Coppersmith's example from last time shows that $\epsilon_f$ can be as big as $1/3$ when $\delta_f = 2/9$, while the following theorem, which we will not prove, implies that $\epsilon_f$ must be smaller than $1/9$ if $\delta_f < 2/9$: \begin{theorem}[Coppersmith] If $\delta_f < 2/9$, then $f$ is $\delta/2$-linear. \end{theorem} One might capture this unusual phenomenon by stating that the function $$\alpha(\delta) = \sup_{\delta_f \leq \delta} \epsilon_f$$ is discontinuous, where the supremum is taken over all groups $G$ and all functions $f$ with domain $G$. Instead of proving Coppersmith's stronger result, we prove the following: \begin{theorem} If $\delta_f < 1/16$, then $f$ is $2\delta_f$-linear. \end{theorem} \begin{remark} Professor Rubinfeld points out that the first proof of this kind applied only to infinite groups. As more proofs came along (using a variety of techniques), they increased in generality with respect to the domains that they applied to - next came finite cyclic groups, then finite abelian groups, and finally finite non-abelian groups. Later results decreased in generality with respect to the domains, but applied to more general ranges of $\delta$. \end{remark} \begin{proof} We introduce some further definitions and notation. For any function $q: G \rightarrow F$, let $\plurality_{s}[q(s)]$ denote the element of $F$ that occurs most often in the multiset obtained by applying $q$ to each element of $G$. Ties are broken arbitrarily. Then, define the function $g : G \rightarrow F$ by $g(x)=\plurality_y[f(x+y)-f(y)]$. Finally, call an element $x\in G$ {\em $\rho$-good} if $\Pr_y[g(x)=f(x+y)-f(y)] > 1-\rho$. We now give some claims. \begin{quote} \begin{claim}\label{claim1} If $\rho<1/2$, then $\Pr_x[x \hbox{ is } \rho\hbox{-good and } g(x)=f(x)] > 1-\delta_f/\rho$. \end{claim} \begin{claim}\label{claim2} If $\rho<1/4$ and $x,y$ are $\rho$-good, \begin{enumerate} \item $x+y$ is $2\rho$-good \item $g(x)+g(y)=g(x+y)$. \end{enumerate} \end{claim} \begin{claim}\label{claim3} If $\delta_f <1/16$, then $x$ is $4\delta_f$-good $\forall x$. \end{claim} Before we prove these claims, let us see how we can use them to prove the theorem. If $\delta_f<1/16$, Claim \ref{claim3} implies that $x$ is $4\delta_f$-good for all $x \in G$. If we set $\rho$ to any number between $4\delta_f < 1/4$ and $1/2$, then, Claim \ref{claim1} implies that $\Pr_x[g(x)=f(x)] > 1-\delta_f/\rho$. In particular, setting $\rho$ arbitrarily close to $1/2$ yields $\Pr_x[g(x)=f(x)] > 1-2\delta_f$. Finally, since $4\delta_f<1/4$, Claim \ref{claim2} implies that $g$ is in fact linear. These last two facts imply that $f$ is $2\delta_f$-linear as desired. We now proceed with the proofs of the claims. \begin{proofof}{Claim \ref{claim1}} Suppose $\rho<1/2$. Let $\alpha_x = \Pr_y[f(x)\neq f(x+y)-f(y)]$. Note that if $\alpha_x < 1/2$, then $f(x)=f(x+y)-f(y)$ with probability strictly greater than 1/2; i.e., $f(x) = \plurality_y[f(x+y)-f(y)] = g(x)$. If $\alpha_x < \rho$, then, we have that $x$ is $\rho$-good. It suffices to show that $\Pr[\alpha_x \geq \rho] < \delta_f/\rho$. But this follows directly from Markov's inequality\footnote{Markov's inequality states that for any positive random variable $Y$ and constant $a>0$, $\Pr[Y\geq a\cdot \E[Y]] \leq 1/a$.}, since \begin{eqnarray*} \E[\alpha_x] &=& \frac{1}{|G|} \sum_{x\in G} \Pr_y[f(x)\neq f(x+y)-f(y)] \\ &=& Pr_{x,y} [f(x)\neq f(x+y)-f(y)] \\ &=& \delta_f. \end{eqnarray*} \end{proofof} \begin{proofof}{Claim \ref{claim2}} Assume that $\rho<1/4$ and that $x,y$ are $\rho$-good. This means that \begin{eqnarray} \label{eq1}\Pr_z[g(y)\neq f(y+z)-f(z)] &\leq& \rho \\ \label{eq2}\Pr_z[g(x)\neq f(x+y+z)-f(y+z)] &\leq& \rho \end{eqnarray} The latter equation simply follows from the fact that for any fixed $y$, the distribution of $z+y$ over uniformly chosen $z$ is again uniform. Now let $h = g(x)+g(y)$. With some basic manipulation, we find: \begin{eqnarray} \nonumber && \Pr_z[h \neq f(x+y+z)-f(z)] \\ \nonumber &=& \Pr_z[g(x)+g(y) \neq (f(x+y+z)-f(y+z))+(f(y+z)-f(z))] \\ \label{union}&\leq& \Pr_z[g(x) \neq f(x+y+z)-f(y+z)] + \Pr_z[g(y) \neq f(y+z)-f(z)] \\ \label{use12}&\leq& 2\rho. \end{eqnarray} Here, (\ref{union}) follows from the union bound, and (\ref{use12}) follows from (\ref{eq1}) and (\ref{eq2}). Thus, we have that $\Pr_z[h = f(x+y+z)-f(z)] \geq 1-2\rho > 1/2$, implying that $g(x+y)=h=g(x)+g(y)$ and that $x+y$ is $2\rho$-good. \end{proofof} \begin{proofof}{Claim \ref{claim3}} Let $x$ be fixed. Claim \ref{claim2} implies that if there exists some $y$ such that $y$ and $x-y$ are both $2\delta_f$-good, then $x$ is $4\delta_f$-good. It suffices to show that such a $y$ must exist. We use the probabilistic method. Applying Claim \ref{claim1} twice with $\rho=2\delta_f$ with the union bound, we find $$\Pr_y[y \hbox{ and } x-y \hbox{ are } 2\delta_f\hbox{-good}] > 1-\frac{\delta_f}{2\delta_f} - \frac{\delta_f}{2\delta_f} = 0.$$ Here, we are again making use of the fact that for any fixed $y$, the distribution of $z+y$ over uniformly chosen $z$ is again uniform. \end{proofof} \end{quote} This proves the three claims, and hence proves the theorem. \end{proof} \paragraph{Testing properties of convolutions of distributions} As an aside, observe that if we let $\mathcal{F}$ denote the distribution induced by selecting $x\in_R G$ and outputting $f(x)$, then the linearity condition ($f(x+y)=f(x)+f(y)$) can be expressed as $\mathcal{F} = \mathcal{F} * \mathcal{F}$; i.e., $\mathcal{F}$ is equal to its own self-convolution. It can be shown that the only distributions that satisfy this relationship are distributions that are uniform over a subgroup of $G$ (including the distribution that puts all weight on zero and the uniform distribution). It can also be shown that tests for $\epsilon$-linearity are intimately related to the problem of testing whether a distribution $\mathcal{F}$ is {\em approximately} equal to its self convolution (according to some well chosen metric). \section{Fourier Representations} In this setting, we focus on functions $f:G\rightarrow F$ with $G=\{\pm1\}^n$ and $F=\{\pm1\}$. Our group operator will be component-wise multiplication (represented by $\cdot$). %In addition, we define the {\em inner product} of $x$ and $y$, notated %$\langle x,y\rangle$, as $\prod_i x_iy_i$. It turns out that there are exactly $2^n$ linear functions from $G$ to $F$. Namely, for each subset $S \subseteq [1\ldots n]$, the function $\chi_S(x) = \prod_{i\in S} x_i$ is linear. One can easily check that these functions are in fact linear. What happens if we apply a single iteration of algorithm $A$ to test the linearity of a function $f$ in this setting? It is easy to see that $$f(x)f(y)f(x\cdot y) = \cases{1 & \hbox{if test passes} \cr -1 & \hbox{if test fails}}$$ This suggests the introduction of an indicator function: $$f'(x,y) = \frac{1-f(x)f(y)f(x\cdot y)}{2} = \cases{0 & \hbox{if test passes} \cr 1 & \hbox{if test fails,}}$$ giving us the nice relation $$\Pr[\hbox{algorithm $A$ fails}] = E_{xy}[f'(x,y)].$$ At this point, we must turn to the tools of Fourier analysis. For now, we lay out some of the basic concepts. We begin with widening our current framework to include functions $f:G \rightarrow F$ with $F=\mathbb{R}$ ($G$, as before, is $\{\pm1\}^n$). If we let $\mathbb{G}$ represent the set of all such linear functions, it turns out that $\mathbb{G}$ is a vector space with dimension $2^n$. We can characterize this vector space with the obvious basis $\{e_a(x)\}_{a\in G}$, where $$e_a(x) = \cases{1 & \hbox{if $x=a$} \cr 0 & \hbox{else}}.$$ A less obvious, but more useful basis, is $\{\chi_S\ |\ S \subseteq [1\ldots n]\}$. We conclude these notes by proving orthnormality of this proposed basis (but not the required spanning property). First, we need some notion of an inner product. For this, we define the inner product of $f$ and $g$ to be $$\langle f,g \rangle = \frac{1}{2^n}\sum_{x\in\{\pm1\}^n} f(x)g(x).$$ One can easily verify that this satisfies the required properties of an inner product (namely, linearity, symmetry, and positive definiteness). \begin{quote} \begin{claim} $\langle \chi_S,\chi_S\rangle = 1$ for all $S \subseteq [1\ldots n]$. \end{claim} \begin{proof} Note that $\langle \chi_S,\chi_S\rangle = \frac{1}{2^n}\sum_x \chi_S^2(x)$. Since $\chi_S^2 \equiv 1$, the sum reduces to $\sum_x 1 = 2^n$, which gives the desired result. \end{proof} \begin{claim} $\langle \chi_S,\chi_T\rangle = 0$ for all $S,T \subseteq [1\ldots n]$ with $S \neq T$. \end{claim} \begin{proof} Note that \begin{eqnarray*} \langle \chi_S,\chi_T\rangle &=& \frac{1}{2^n}\sum_x \chi_S(x)\chi_T(x) \\ &=& \frac{1}{2^n}\sum_x \prod_{i\in S} x_i \prod_{j\in T} x_j \end{eqnarray*} Now, we may write $S \cup T$ as the disjoint union $S \cup T = (S\cap T) \cup \Delta$, where $\Delta \neq \emptyset$. Additionally, if we define the {\em $\Delta$-conjugate} of $x$, $\Delta(x)$, to be the element of $G$ taken by switching the $\min(\Delta)$-th coordinate of $x$, we may note that summing over all $x$ is equivalent to summing over all $\Delta(x)$. This is because $G$ can be partitioned into $\Delta$-conjugate pairs. The sum then becomes \begin{eqnarray*} && \frac{1}{2^n}\sum_x \prod_{i\in S \cap T} x_i^2 \prod_{j\in \Delta} x_j \\ &=& \frac{1}{2^n}\sum_x \prod_{j\in \Delta} x_j \\ &=& \frac{1}{2^{n+1}}\bigg(\sum_x \prod_{j\in \Delta} x_j + \sum_x \prod_{j\in \Delta} \Delta(x)_j \bigg) \\ &=& \frac{1}{2^{n+1}}\sum_x (1+(-1))\prod_{j\in \Delta \atop j \neq \min(\Delta)} 2x_j \\ &=& 0. \end{eqnarray*} \end{proof} \end{quote} \end{document}