8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Lev Borisov Mar 3 '17 at 12:07
  • $\begingroup$ 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. $\endgroup$ – SiRichel Mar 4 '17 at 1:06
  • $\begingroup$ Never mind, I completely misunderstood the question. Thank you! $\endgroup$ – Lev Borisov Mar 4 '17 at 1:31
2
+50
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Distinct and neither contained in the other, of course. $\endgroup$ – LSpice Mar 6 '17 at 22:52
  • $\begingroup$ 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$. $\endgroup$ – SiRichel Mar 7 '17 at 2:02
  • $\begingroup$ @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. $\endgroup$ – Will Sawin Mar 7 '17 at 4:42
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – SiRichel Mar 7 '17 at 4:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.