1
$\begingroup$

Let $\mathbb{F}$ be a finite field and $S\subset\mathbb{F}_{\leq d}[x,y]$, a set of bivariate polynomials over $\mathbb{F}$ of degree at most $d\ll|\mathbb{F}|$. Assume the linear span of $S$ is all of $\mathbb{F}_{\leq d}[x,y]$. Let $L$ be the set of one-dimensional lines in $\mathbb{F}^2$. Suppose the following property holds: for any $P(x,y)\in S$ and $\ell\in L$, there exists $Q(x,y)\in S$ st $P|_\ell=Q|_\ell$. Can we lower bound $|S|$? $|S|=|\mathbb{F}|^{\Omega(d)}$ would be ideal. Is this even true?

$\endgroup$
4
  • $\begingroup$ If it's easier, I'd also be interested in a solution to the same problem one dimension up: $S\subset\mathbb{F}_{\leq d}[x,y,z]$ a set of trivariate polynomials, and $L$ the set of all two-dimensional affine subspaces of $\mathbb{F}^3$, guarantee is that for all $P\in S$ and $H\in L$, there exists $Q\in S$ st $P|_H=Q|_H$. $\endgroup$
    – SiRichel
    Nov 12, 2016 at 19:12
  • $\begingroup$ The set of all polynomials of degree at most 1 fits for every $d\geq 1$. Did you miss some condition? (If you need, you may multiply all of them by $x^{d-1}$...) $\endgroup$ Nov 12, 2016 at 19:18
  • $\begingroup$ Yes, thanks. I'm not interested in $S$ contained in a low-dimension subspace of $\mathbb{F}_{\leq d}[x,y]$. Question updated. $\endgroup$
    – SiRichel
    Nov 12, 2016 at 19:58
  • 1
    $\begingroup$ I did not get it. The condition is not trivially true by picking Q=P? $\endgroup$ Nov 12, 2016 at 22:43

1 Answer 1

3
$\begingroup$

Still, a required estimate is hopeless. Set $q=|\mathbb F|$.

Take into $S$ all polynomials of the form $k(\ell x+my+n)^d$ with $k,\ell,m,n\in\mathbb F$ (there are in fact $\Omega(q^3)$ such polynomials). They satisfy all the requirements. Indeed, if $ux+vy+w=0$ is an equation of some affine line, then $k(\ell x+my+n)^d$ and $k(\ell x+my+n+ux+vy+w)^d$ are equal on this line. Moreover, these polynomials span all the polynomials of degree $\le d$ by Vandermonde.

$\endgroup$
1
  • $\begingroup$ OK yeah looks like it's not true in general. Thanks. $\endgroup$
    – SiRichel
    Nov 12, 2016 at 20:49

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.