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.


  • 3
    $\begingroup$ 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. $\endgroup$ 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}|)$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.