Consider a $d$-dimensional linear subspace $V\subseteq\mathbb{F}_p^n$, and its intersection with subcubes of form $S_1\times\cdots\times S_n$, where $S_1,\ldots,S_n$ are arbitrary size-$s$ subsets of $\mathbb{F}_p$. I want to bound the size of the intersection $$M=\max_{S_1,\ldots,S_n}|V\cap S_1\times\cdots\times S_n|$$ An obvious upper bound is $M\leq s^d$, but for some specific $V$ I expect much better bounds.
The parameters I'm interested in are, for instance, $d=n^{1/2}$, $s=2^{\log^2 n}$ and $p=2^{\log^{100} n}$.
The specific $V$ I have in mind is Reed-Solomon codes, i.e. each point in $V$ represents the evaluations of a degree-$(d-1)$ polynomial on $\mathbb{F}_p$. In this case, for very small $s$ we have a much better bound on $M$: By counting the tuples $(x,y,i)$ with $x,y\in V$ and $x_i=y_i$, we get that $M\leq s^2$ when $s<n/d$. However this does not work for the parameters listed above. What is the best bound we can get for Reed-Solomon codes?
- Notice that when $S_1=\cdots=S_n=\mathbb{F}_s$ is a subfield, and the $n$ points being evaluated at are also contained in $\mathbb{F}_s$, we indeed have $M=s^d$. So let us assume that the evaluation points are optimally chosen, or even directly assume $p$ is a prime number to avoid this scenario.
More generally, can we get strong bounds like $M\leq 2^{\mathrm{polylog}(n)}$ for any explicitly constructed $V$?
Even more generally, what about explicitly constructed subsets $V\subseteq\mathbb{F}_p^n$ of size $p^d$? Notice that for a random subset $V$, it is easy to show that $M\leq O(s)$ with high probability.
Side question: What about $V$ being a random $d$-dimensional linear (or affine) subspace? This is not as easy as the random subset case, but I still expect $M$ is small with high probability.
Let's talk a little bit about the applications as requested. This is related to several problems in theoretical computer science, the most closely related one being static data structure lower bounds.
Consider the task of storing the element $x\in V$ (e.g. storing a degree-$(d-1)$ polynomial) in $r$ bits with little or no redundancy, so $r=(1+o(1))\cdot d\log p$. We want that each coordinate $x_i\in\mathbb{F}_p$ can be recovered (e.g. asking for the evaluation of the polynomial) by querying only $q$ stored bits, and our goal is to prove a lower bound on $q$. Ideally we want to show that $q$ should be in the same order as $d$, but for the parameters I listed above, showing any polynomial bound $q=\Omega(n^\epsilon)$ is fine.
The approach is to randomly fix most of the $r$ bits, and leave only $O(r/q\cdot \log s)$ bits free, so that for each $i\in[n]$, there are at most $\log s$ free bits left among the ones queried to decide $x_i$. That means each $x_i$ has at most $s$ possibilities, corresponding to the set $S_i$. We can then bound $q$ using $M$ via $$2^{r-O(r/q\cdot \log s)}\cdot M\geq p^d$$ which gives $$q\geq \Omega(d\log p\log s/\log M).$$ If we have a good upper bound on $M$, we have a good lower bound on $q$. The trivial bound $M\leq s^d$ is not good as it only gives $q\geq \Omega(\log p)$ which is also trivial.
When $s$ is small, the bound $M\leq s^2$ is good enough to give a bound close to optimal, and this is essentially done in Gál & Miltersen. But with larger $s$, the bound could be applied to more general scenarios, such as when each $x_i$ is given $O(\log s)$ bits of hints for free, which is a model that captures the sequential computation of $x$ with $O(\log s)$ bits of memory. This is the reason I wonder if we can still have good bounds on $M$ for larger $s$.
