Technical lemma about curves used in original proof of PCP theorem

Notation: Let $P(\langle x_1,\dots,x_k\rangle)$ the set of degree $k$ curves that evaluates to $x_1,\dots,x_k\in\mathbb{F}^m$ at the first $k$ field elements in $\mathbb{F}$ and we will use just $P$ as a shorthand for this set. Let $S$ be any subset of $ \mathbb{F}^m$. Below, we assume that multiplicity is taken into account when set cardinalities are computed and for any curve $C\in P$, $|C|:=|\{C(i) : k+1<i\leq \mathbb{F} \}|$.

Claim 1: $\mathbb{E}_{C}\big[ \frac{|C\cap S|}{|C|} \big]=\frac{|S|}{|\mathbb{F}|^m}$ where $C$ is a random curve in $P$.

Proof: $\mathbb{E}_{C}\big[ \frac{|C\cap S|}{|C|} \big]=\sum_{C'\in P}\Pr_{C}\big[C=C' \big]\cdot\Pr_{i}\big[C'(i) \in S\big]= \Pr_{C,i} \big[C(i)\in S \big]= \frac{|S|}{|F|^m} $

Here $C$ is a random curve in $P$ and $i$ is randomly sampled from $\{k+1,\dots,\mathbb{F} \}$. The last line holds because sampling a random curve from $P$ and then evaluating the curve at a random $i$ gives a random element from $\mathbb{F}^m$. To see why this is true consider the bipartite graph on $P\cup \mathbb{F}^m$ where for each $i\in \{k+1,\dots,\mathbb{F}\}$, each curve $C\in P$ has a neighbor $C(i)\in \mathbb{F}^m$. Its easy to check that this is a bi-regular graph. Thus, the distribution that samples a random $C$ and outputs a random neighbor $C(i)\in \mathbb{F}^m$ , is same as the distribution that randomly outputs an element from $\mathbb{F}^m$. The claim follows.

Remark 1: Claim 1 implies that if $|S|/|\mathbb{F}|^m\leq \delta$ then we must have $\Pr_{c}[\Pr_{i}[~c(i)\in \mathcal{S}] > \sqrt\delta] \leq \sqrt{\delta}$. This I believe is the claim (from the linked thesis) that OP refers to.

Remark 2: What happens if we just sample a random point $i$ from the entire field $\mathbb{F}$ instead of $\{k+1,\dots,\mathbb{F} \}$. Nothing will change much as it will incur a small(if $k\ll |\mathbb{F}|$) additive error of $k/|\mathbb{F}|$. In [1] below this error is there in the argument in page 38.

[1] https://madhu.seas.harvard.edu/papers/1997/arora-journ.pdf

Solved by user48449 (387 )
Mar 20, 2020 at 14:26