abstract debate of pairwise independent started in the meeting

[עודד גולדרייך‎]

The following post refers to a side issue that arose at the end
of our last meeting (re pairwise independent samples).
Please do *not* feel obliged to read farther unless you are truly
interested in that "marginal" debate...


Recall that I introduced the sequence of pairwise independent
random variables $r_1,...,r_n$ such that $r_i=s_0+\alpha_i s_1$,
where the $\alpha_i$'s are distinct element in a finite field $F$,
and $s_0,s_1$ are uniformly and independently selected in $F$
(and all arithmetic operations refer to the field $F$).

I said that if $g:F\to\{0,1\}$ is non-constant
and if the $r_i$'s *were* totally independent,
then the sequence $g(r_1),...,g(r_n)$ would
have had $2^n$ possible values.
However, I noted that for the above (pairwise independent) $r_i$'s,
there may be less possibilities for the sequence of $g$-values.
But I failed to give a nice example...


Recall that I wanted to have a non-constant function $g$
such that when the $r_i$'s are pairwise independent as above
the sequence $g(r_1),...,g(r_n)$ would
have only $\poly(n)$ possible values.
Note that the proof of Thm 2.5.2 provides such an example,
but it is for a *different* sequence of pairwise independent
elements...

Let's go back to the above pairwise independent sequence.
As noted by Hillary,
the sequence of $g$-values may have at most $|F|^2$ possibilities
(as per all choices of $s_0,s_1$), and this yields a $\poly(n)$ bound
in case $F$ is small (e.g., $|F|=n$), but I seek a general result
that holds also for large $F$.

Following is a cumbersome example that relates to the special case
in which $F$ is an extension field; specifically,
suppose that $F=K^2$ for some finite field $K$,
and further assume that $\alpha_1,...,\alpha_2\in K$
(i.e., they are in the base field).
Now, define $g:F\to\{0,1\}$ such that $g(x)=1$ iff $x\in K$.
I claim that the sequence of $g$-values can have at most $n+2$
possibilities. Furthermore:

Claim: For $\alpha_1,...,\alpha_2\in K$ and any $s_0,s_1\in F$
one of the following three cases hold.
1. For every $i\in[n]$ it holds that $s_0+\alpha_i s_1 \in K$.
2. For every $i\in[n]$ it holds that $s_0+\alpha_i s_1 \in F-K$.
3. There exists a unique $i\in[n]$ such that $s_0+\alpha_i s_1 \in K$.

Note that Case 1 occurs when $s_0,s_1\in K$,
whereas Case 2 occurs iff exactly one $s_j$ is in $K$.
Prove that Case 3 occurs iff both $s_0,s_1$ are in $F-K$.

Hint: For $\alpha_i$'s as above, it is instructive to
view the values $r_i=s_0+\alpha_i s_1$ as 2-dim vectors over $K$,
where $\alpha_i$'s are scalars (in $K$) and $s_0,s_1,r_i \in K^2$
(are viewed as 2-dim vectors).

[עודד גולדרייך‎]

A much simpler example is provided next.
Recall that we refer to the sequence of pairwise independent

random variables $r_1,...,r_n$ such that $r_i=s_0+\alpha_i s_1$,
where the $\alpha_i$'s are distinct element in a finite field $F$,
and $s_0,s_1$ are uniformly and independently selected in $F$
(and all arithmetic operations refer to the field $F$).

Let us consider $g:F\to\{0,1\}$ such that $g(x)=1$ iff $x\neq0$
(i.e., $g(x)=0$ iff $x=0$). Then, the sequence of $g$-values
can has $n+2$ possibilities.

Claim: For any $\alpha_1,...,\alpha_n\in F$ and any $s_0,s_1\in F$

one of the following three cases hold.

1. For every $i\in[n]$ it holds that $s_0+\alpha_i s_1=0$.
2. For every $i\in[n]$ it holds that $s_0+\alpha_i s_1\neq 0$.
3. There exists a unique $i\in[n]$ such that $s_0+\alpha_i s_1=0$

Note that Case 1 occurs when $s_0=s_1=K$,
whereas Case 2 occurs iff exactly one $s_j$ equals zero
(e.g., if $s_1=0$ then $r_i=s_0+\alpha_i s_1 = s_0$,
whereas if $s_0=0$ then $r_i=\alpha_i s_1).
Observe that Case 3 occurs if both $s_0,s_1$ are non-zero,
since in this case $s_0+\alpha_i s_1=0$ implies $s_0=-\alpha_i s_1$.