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?



question about sets of polynomials with a special agreement guarantee
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.


