# Linear combinations of low-degree polynomials with agreement guarantee

Let $\mathbb{F}$ be a finite field of odd characteristic and let $f:\mathbb{F}_{\leq d}[x,y]\rightarrow\mathbb{Z}$ map bivariate polynomials over $\mathbb{F}$ of degree at most $d\ll|\mathbb{F}|$ to the integers. Suppose $f$ is not identically zero. Suppose furthermore that for any line $\ell\subset\mathbb{F}^2$ and univariate $P$ defined on $\ell$: $$\sum_{Q:Q|_\ell=P}f(Q)=0,$$ where the sum is over bivariate $Q\in\mathbb{F}_{\leq d}[x,y]$ which, when restricted to $\ell$, equal $P$. Can one prove in this case, that $\text{Supp}(f)=\{Q\in\mathbb{F}_{\leq d}[x,y]:f(Q)\neq0\}$ must be large?

It is possible to show that $|\text{Supp}(f)|$ must be at least roughly $|\mathbb{F}|^2/d$ using that distinct $Q,Q'$ cannot agree on more than $d$ lines. However, I'm hoping a better bound (i.e., a bound which grows with $d$) might be possible as the linear conditions seem to give quite a bit more information than this "low-agreement" argument uses. A good bound in the special case when $f:\mathbb{F}_{\leq d}[x,y]\rightarrow\{0,\pm 1\}$ would also be interesting.

• How do we get such estimate? I count coincidences on the lines, on each of $|{\mathbb F}|^2+|{\mathbb F}|$ lines we get at least $k/2$ ($k=|{\rm Supp}\, f|$) coincidences, and for each of $\binom{k}2$ polynomials at most $d$ coincidences, thus $\binom{k}2d\geqslant \frac{k}2(|{\mathbb F}|^2+|{\mathbb F}|)$, $k\geqslant \frac{|{\mathbb F}|^2+|{\mathbb F}|}{d}+1$. – Fedor Petrov Feb 22 '17 at 6:52
• How may the bound grow with $d$? It is obviously decreasing by $d$, is not it? – Fedor Petrov Feb 22 '17 at 6:56
• Yes this is the low agreement argument. You are using only that for each line $\ell\subset\mathbb{F}^2$ and $Q\in\text{Supp}(f)$, there must exist $Q'\in\text{Supp}(f)$ st $Q|_\ell=Q'|_\ell$. However, an $f$ which satisfies all constraints requires more. If we think of $f$ as giving a $+/-$ sign to each $Q\in\text{Supp}(f)$, then satisfying all constraints requires that for each $Q$ and $\ell$ the number of $Q'\in\text{Supp}(f)$ with $+$ sign which agree with $Q$ on $\ell$ equals the number of such $Q'$ with $-$ sign. – SiRichel Feb 22 '17 at 15:37