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?
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$– 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^{d-1}$...) $\endgroup$– Ilya BogdanovNov 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$– 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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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