I'm trying to apply the polynomial method to a combinatorial problem. In one special case of the problem, I have an integer $N\geq 4$ and a set $D\subseteq\mathbb F_3^N$ with $|D|=3^{N-1}+1$. I have another set $E=\{e_1,e_2,\ldots,e_s\}\subseteq\mathbb F_3^N\setminus D$. Write $e_i=(a_{i1},a_{i2},\ldots,a_{iN})$ for all $1\leq i\leq s$. For $1\leq i\leq s$, let $$f_i(X_1,X_2,\ldots,X_N)=(X_1-a_{i1})(X_2-a_{i2})\cdots(X_N-a_{iN})\in\mathbb F_3[X_1,X_2,\ldots,X_N].$$ Finally, assume that there are distinct points $d_1,d_2,\ldots,d_s$ such that for all $1\leq i\leq s$, $f_i$ vanishes on all of $D\setminus\{d_i\}$ but does not vanish on $d_i$.
This seems to be a pretty strong restriction to place on the polynomials $f_1,f_2,\ldots,f_s$, especially if $s$ is large. Indeed, we are saying that $D$ is a fairly large set (it contains more than $1/3$ of the elements of $\mathbb F_3^N$) and that all of the polynomials $f_i$ "almost" vanish on $D$. By "almost," I mean that each $f_i$ fails to vanish on exactly one point in $D$. Moreover, the points $d_i$ where the polynomials $f_i$ fail to vanish are distinct.
I am wondering if it is possible to find a decent upper bound on $s$, preferably a bound that is much smaller than $N$. It might also be useful to have additional information about the set $D$, although I am really concerned with bounding $s$.
Something like$$\left({2\over3}\right)\left({3\over2}\right)^N$$is a lower bound for $s$, so it is much larger than you expected—$2^N$ is a simple upper bound as the polynomials are linearly independent multilinear polynomials. To get the lower bound you construct the vectors $e_i$ and the polynomials $f_i$ one by one, always making sure that $f_i$ vanished on all previous $e_j$ but not on $e_i$ and that all previous $f_j$ vanish on $e_i$. Since each polynomial $f_j$ of the form you have vanished on all points but $2^N$, it is easy to keep this process for some$$\left({2\over3}\right)\left({3\over2}\right)^N$$steps, and all polynomials will still vanish on enough points besides the points $e_i$ so you can define your $D$.
The detailed computation is omitted.