# How different can the bias of two polynomials be?

I'm trying to figure out how to approach the following question:

Let $$g,h$$ be polynomials over $$\mathbb{Z}_p$$ (for prime $$p$$) with $$n>1$$ variables. Denote by $$bias(g)=|\sum_{x\in \mathbb{Z}_p^n}e^{2\pi i \cdot g(x)/p}|$$ (and equivalently for $$h$$).

Suppose I know that $$bias(g)\ne bias(h)$$. Find a (non-trivial) lower bound on $$|bias(g)- bias(h)|$$.

Another variant for this problem is the following:

Given two vectors $$v_g,v_h\in \mathbb{Z}_p^n$$ that represent the histogram of these polynomials (a list of $$p$$ entries that specified how many times the polynomial evaluated to each element in the field), give (non-trivial) upper bound for $$||v_g-v_h||_1$$ given that the $$v_g\ne v_h$$.

This problem seems to have a "flavour" of something like the Schwartz-Zippel lemma, in the sense that (it may be that) "polynomials with different histogram/bias have very different histogram/bias" (in comparison to "non-identical polynomials are non-equal most of the time" of the Schwartz-Zippel lemma), but it seems to require different techniques. In particular, I don't think the Weil/Deligne bounds for exponential sums helps here.

Thanks!

• You can make polynomials take on any values you want, so this is just asking about sums of $p^n$ $p$-th roots of unity. Nov 17 '20 at 23:01

if accept square it several times, then use vanderport trick actrually we can have a good expension of $$|\operatorname{bias}(g)|^{2^{deg(g)}}$$, where $$\operatorname{bias}(g)=\left|\sum_{x \in Z_{p}^{n}} e^{2 \pi i \cdot g(x) / p}\right|$$, from this maybe we can gain some nontrivial lower estimate for $$|\operatorname{bias}(g)-\operatorname{bias}(h)|$$, if $$g\neq h$$. Just a example to expain what happen when $$deg(g)=2, g(x)=x^2+cx+d$$,
\begin{aligned} |\operatorname{bias}(g)|^2&=\operatorname{bias}(g) \overline{\operatorname{bias}(g)}\\ &=|\sum_{x \in Z_{p}^{n}} \sum_{y \in Z_{p}^{n}} e^{2 \pi(g(x)-y(y)) / p}| \\ &=|\sum_{x \in Z_{p}^{n}} \sum_{a \in Z_{p}^{n}} e^{2 \pi(g(x+a)-g(x)) / p}|\\&=|\sum_{a \in Z_{p}^{n}}\sum_{x \in Z_{p}^{n}} e^{2 \pi(2ax+a^2+ca) / p}| \end{aligned}
and with the last one we can get some nontrivial estimate for lowerbound. In fact the toy model problem for $$deg(f)=deg(g)=2$$ wiil be find a lower bound for, $$min_{c_1,c_2}(|\sum_{a \in Z_{p}^{n}}\sum_{x \in Z_{p}^{n}} e^{2 \pi(2ax+a^2+c_1a) / p}|-|\sum_{a \in Z_{p}^{n}}\sum_{x \in Z_{p}^{n}} e^{2 \pi(2ax+a^2+c_2a) / p}|)$$