Question about polynomials over finite fields

Question

This is a special case of this question.

Let $\mathbb{F}$ be a finite field and $\mathbb{F}_{\leq d}[x,y]$ the set of bivariate polynomials over $\mathbb{F}$ of degree at most $d\ll|\mathbb{F}|$. Do there exist non-empty, disjoint subsets $A,B\subset\mathbb{F}_{\leq d}[x,y]$ such that for all pairs $(\ell,P)$, where $\ell\subset\mathbb{F}^2$ is a line, and $P$ is a univariate polynomial of degree at most $d$ defined on $\ell$ we have: $$\Big|\{Q\in A:Q|_\ell=P\}\Big|=\Big|\{Q\in B:Q|_\ell=P\}\Big|.$$

Follow-up Question: Do there exist $A,B\subset\mathbb{F}_{\leq d}[x,y]$ satisfying the above and also $|A|=|B|=|\mathbb{F}|^{\mathcal{O}(1)}$?

Answer 1

The condition that $A$ and $B$ are nonempty disjoint can be replaced with the condition that they are distinct, as we may just replace $A$ and $B$ with $A \cap (A - B)$ and $B \cap (A- B)$ respectively.

Let $q = |\mathbb F|$.

Let $A$ and $B$ be two random linear subspaces of the space of polynomials of degree $\leq d$ each of codimension $k$. As long as $0< k < { d+2 \choose 2}$, with high probability $A$ and $B$ are distinct. As long as $A$ and $B$ intersect transversely the space of polynomials vanishing on $\ell$, the number of elements of $A$ and $B$ taking a given fixed value on $\ell$ is $ q^{ {d+2 \choose 2} - k - (d+1)}$.

Equivalently, this happens when the perpendicular spaces of $A$ and $B$ intersect only at $0$ the space of linear forms on degree $d$ polynomaials that factor through reduction to $\ell$. Each nonzero linear form has a probability of $$\frac{(q^k-1) }{ q^{ {d+2 \choose 2}} -1}$$ of being in the perpendicular subspace, and there are at most $(q^{d+1}-1)$ nontrivial linear forms that factor through restriction to each of $q (q+1)$ lines, so as long as

$$ q(q+1) (q^{d+1}-1) \frac{(q^k-1) }{ q^{ {d+2 \choose 2}} -1}< 1$$

with high probability $A$ and $B$ are transverse to all these linear subspaces. This happens when $k<{d+2 \choose 2} - d-3$. So it looks to me like even random $d+4$-dimensional subspaces will do the job.

Answer 2

The condition clearly implies $|A|=|B|$. (Fix a line $\ell$ and sum over all univariate polynomials on $\ell$.) Also, if $A$ and $B$ satisfy the condition and $p=p(x,y)$ is any bivariate polynomial of degree at most $d$, then $A+p=\{q+p \mid q \in A\}$ and $B+p$ also satisfy the condition.

Suppose $0 \in A$. For every line $\ell$, $B$ contains a polynomial that vanishes identically on $\ell$. There are $|\mathbb{F}|^2+|\mathbb{F}| = O(|\mathbb{F}|^2)$ lines in $\mathbb{F}^2$, and at most $d|B|$ linear factors of polynomials in $B$. So to meet the condition and be disjoint from $A$, we must have $|A|=|B|\geq (|\mathbb{F}|^2+|\mathbb{F}|)/d$.

Now, what do you want in the follow-up question? Is $d$ fixed and $|\mathbb{F}| \to \infty$? If so, then since $|A|=|B|$ is certainly no more than $|\mathbb{F}[x,y]_{\leq d}| = |\mathbb{F}|^{\binom{d+2}{2}} = |\mathbb{F}|^{O(1)}$, then the follow-up question doesn't make sense to me. (It doesn't add any new condition to the original question.)

If you are asking for $|A|=|B|=O(|\mathbb{F}|)$ (with $d$ fixed and $|\mathbb{F}| \to \infty$) then no, $|B| \geq (|\mathbb{F}|^2+|\mathbb{F}|)/d = O(|\mathbb{F}|^2)$.

This doesn't answer the original question but I hope it sheds some light on the follow-up question.