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 onedimensional 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?

$\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 twodimensional 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$– SiRichelNov 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^{d1}$...) $\endgroup$– Ilya BogdanovNov 12, 2016 at 19:18

$\begingroup$ Yes, thanks. I'm not interested in $S$ contained in a lowdimension subspace of $\mathbb{F}_{\leq d}[x,y]$. Question updated. $\endgroup$– SiRichelNov 12, 2016 at 19:58

1$\begingroup$ I did not get it. The condition is not trivially true by picking Q=P? $\endgroup$– Joao CostalongaNov 12, 2016 at 22:43
1 Answer
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.

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