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

<p>Claim 1: <span class="math-container">$\mathbb{E}_{C}\big[ \frac{|C\cap S|}{|C|} \big]=\frac{|S|}{|\mathbb{F}|^m}$</span> where <span class="math-container">$C$</span> is a random curve in <span class="math-container">$P$</span>. </p>

<p>Proof: <span class="math-container">$\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} $</span></p>

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

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

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

<p>[1] <a href="https://madhu.seas.harvard.edu/papers/1997/arora-journ.pdf" rel="nofollow noreferrer">https://madhu.seas.harvard.edu/papers/1997/arora-journ.pdf</a> </p>

CC BY-SA 4.0
2020-03-22T09:27:34.403Z
Thanks a lot, it clarified the argument in a very nice way!
Don Fanucci
CC BY-SA 4.0
2020-03-20T14:26:37.813Z
2020-03-20T21:49:15.847Z
2020-03-20T21:49:15.847Z
A.2
<p>I am reading the proof from <a href="https://www.cs.princeton.edu/~arora/pubs/thesis.pdf" rel="nofollow noreferrer">here</a> and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn't figure it out myself.</p>

<p>In page 67 (when proving a claim that is used for soundness of local decoding of low degree polynomials procedure), the writers use a "fact" A.9 (regarding "Well   Distribution Lemma in Curves") that is located in page 156.</p>

<p>The proof is very short and I cannot grasp it. </p>

<p>Moreover, the statement seems to be incorrect by the following example:</p>

<p>Let <span class="math-container">$S=\{x_1\}$</span>, then <span class="math-container">$\forall$</span> curve <span class="math-container">$C\in P(\langle x_1,\dots,x_k\rangle)$</span> we have <span class="math-container">$|C\cap S|\geq 1$</span> as <span class="math-container">$C$</span> is a <strong>multiset</strong>, so
<span class="math-container">$$\mathbb{E}\left[\frac{|C\cap S|}{|C|}\right]\geq\mathbb{E}\left[\frac{1}{|C|}\right]&gt;\frac{1}{|\mathbb{F}|^m}=\frac{|S|}{|\mathbb{F}|^m}$$</span>
Maybe, I miss something in the statement of the lemma...</p>

<p>I will appreciate any help in understanding this problem.</p>

CC BY-SA 4.0
2020-03-18T17:58:53.543Z
@A.2 So, how is it later combined with the averaging principle? I mean, how does your statement helps in proving the claim in page 67? And do u understand the proof for it?
Don Fanucci
CC BY-SA 4.0
2020-03-18T23:49:29.027Z
@A.2 The lemma in question is explicitly stated in terms of "the **average** of $|C\cap S|$, among all curves $C\in P(\langle x_1,\dot, x_k\rangle)$" (emphasis mine), not probabilities, though.
Clement C.
CC BY-SA 4.0
2020-03-20T05:49:31.007Z
@A.2 Thanks! If you upload your comments as an answer, I will accept it.
Don Fanucci
<cc.complexity-theory><algebra><pcp>
Technical lemma about curves used in original proof of PCP theorem
Don Fanucci
# Technical lemma about curves used in original proof of PCP theorem

(Asked by: username_0 on 2020-03-18)

I am reading the proof from [here](https://www.cs.princeton.edu/~arora/pubs/thesis.pdf) and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn't figure it out myself.

In page 67 (when proving a claim that is used for soundness of local decoding of low degree polynomials procedure), the writers use a "fact" A.9 (regarding "Well Distribution Lemma in Curves") that is located in page 156.

The proof is very short and I cannot grasp it.

Moreover, the statement seems to be incorrect by the following example:

Let $S=\{x\_1\}$, then $\forall$ curve $C\in P(\langle x\_1,\dots,x\_k\rangle)$ we have $|C\cap S|\geq 1$ as $C$ is a **multiset**, so
$$\mathbb{E}\left[\frac{|C\cap S|}{|C|}\right]\geq\mathbb{E}\left[\frac{1}{|C|}\right]>\frac{1}{|\mathbb{F}|^m}=\frac{|S|}{|\mathbb{F}|^m}$$
Maybe, I miss something in the statement of the lemma...

I will appreciate any help in understanding this problem.

**Tags:** cc.complexity-theory, algebra, pcp
> **Comments:**
> **username_0**: @A.2 So, how is it later combined with the averaging principle? I mean, how does your statement helps in proving the claim in page 67? And do u understand the proof for it?  
> **username_1**: @A.2 The lemma in question is explicitly stated in terms of "the **average** of $|C\cap S|$, among all curves $C\in P(\langle x_1,\dot, x_k\rangle)$" (emphasis mine), not probabilities, though.  
> **username_0**: @A.2 Thanks! If you upload your comments as an answer, I will accept it.  

---

## 1 answers

### Answer by username_2 on 2020-03-20. Score: 5 | Accepted answer

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.

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>

> **Comments:**
> **username_0**: Thanks a lot, it clarified the argument in a very nice way!  

---

