Question about polynomials over finite fields

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)}$?

• What's wrong with taking $A$ and $B$ to be sets of nonzero multiples of some specific but rather general polynomials $f$ and $g$? These should be of size $|\mathbb F|-1$, and the restrictions to any line would be of the same size? – Lev Borisov Mar 3 '17 at 12:07
• This does not work. For any $f,g\in\mathbb{F}_{\leq d}[x,y]$ which are not multiples of each other, most $\ell\subset\mathbb{F}$ will be so that $f|_\ell\neq\alpha\cdot g|_\ell$ for all $\alpha\in\mathbb{F}$. Indeed, there are roughly $|\mathbb{F}|^2$ lines and only $|\mathbb{F}|$ choices for $\alpha$, so if $\forall\ell\exists\alpha$ st $f|_\ell=\alpha\cdot g|_\ell$, then there is some $\alpha$ for which $\text{}^\#\{\ell:f|_\ell=\alpha\cdot g|_\ell\}\geq|\mathbb{F}|$. This implies that $f=\alpha\cdot g$ as distinct $f,g\in\mathbb{F}_{\leq d}[x,y]$ agree on at most $d$ lines. – SiRichel Mar 4 '17 at 1:06
• Never mind, I completely misunderstood the question. Thank you! – Lev Borisov Mar 4 '17 at 1:31

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.

• Distinct and neither contained in the other, of course. – LSpice Mar 6 '17 at 22:52
• This is nice. It shows that $A$ and $B$ of size $|\mathbb{F}|^{\mathcal{O}(d)}$ exist which satisfy the criterion. Follow-up question remains: do there exist such $A$ and $B$ of size $|\mathbb{F}|^{\mathcal{O}(1)}$. In your construction, the image of $A$ under "restrict to $\ell$" maps will be all degree $d$ polys defined on $\ell$. – SiRichel Mar 7 '17 at 2:02
• @SiRichel If you have a construction in degree $d$, you have a constrction in all greater degrees. You can even disguise it by multiplying $A$ and $B$ by a fixed polynomial and then translating by a fixed polynomial. – Will Sawin Mar 7 '17 at 4:42

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.

• Yes this shows that any $A,B$ must have size at least $|\mathbb{F}|^{\Omega(1)}$. @Will Sawin's answer above gives a construction of $A,B$ of size $|\mathbb{F}|^{\mathcal{O}(d)}$. The follow-up question asks for $A,B$ of size $\mathbb{F}|^{\mathcal{O}(1)}$. I am not thinking of $d$ as constant here: $|\mathbb{F}|$ and $d$ are both functions of some underlying parameter $n$ and needn't be constant. – SiRichel Mar 7 '17 at 4:22