A parity counting problem for subsets over finite fields

Question

Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$. For a subset $T\subseteq {\mathbb F}_p$, define $$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb F}_p,b)|,$$ where $$N_e( {\mathbb F}_p,b)=\# \{ D\subseteq {\mathbb F}_p | \sum_{x\in D}x=b, |D\cap T|\equiv 0 \bmod 2 \}$$ and $$N_o( {\mathbb F}_p,b)=\#\{ D\subseteq {\mathbb F}_p| \sum_{x\in D}x=b, |D\cap T|\equiv 1 \bmod 2 \}.$$

My question: is there any method to prove $$Bias(T)\leq 2^{(1/2+o(1))p}, \forall T \ne \emptyset$$ for $|T|\sim p/2$? Thank you very much.

The exponential sum approach by Shparlinski can be used to show $$Bias(T)\leq 2^{0.8413p}.$$

When $|T|$ is very small, say for example, $|T|=o(p)$, or very large $(|T|=p-o(p))$, this conjecture can be solved by our sieving counting argument.

Take the simplest example, $T={\mathbb F}_p$, and we count that $$N_e({\mathbb F}_p, b)=\sum_{k\ne 0, 2\mid k} {1\over p}{p\choose k}\pm 1=\frac { 2^{p-1}-1}p\pm 1,$$ $$N_o({\mathbb F}_p, b)=\sum_{k\ne p, 2\not\mid k} {1\over p}{p\choose k}\pm 1=\frac {2^{p-1}-1}p\pm 1,$$ and thus $$Bias({\mathbb F}_p) \leq 2.$$

Generally we may define $$Bias_S(T)=|N_e(S,b)-N_o(S,b)|$$ similarly for $S\subseteq {\mathbb F}_p$ and propose the same conjecture $Bias_S(T)=2^{(1/2+o(1)|S|}, \forall T\ne \emptyset$.

Answer 1

Let's identify the elements of $\mathbb F_p$ with $\lbrace 0,1,2,\dots ,p-1\rbrace$. After fixing $T\subset \mathbb F_p$ and $b$, the Bias can be read off the following generating function $$f_{T,b}(x)=x^{p-b}\prod_{i=0}^{p-1} \left(1+(-1)^{\chi(i)}x^i\right),$$ where $\chi(i)=1$ if $i\in T$, and $\chi(i)=0$ otherwise.

In fact $\operatorname{Bias}(T,b)=\frac{1}{p}\left|\sum_{i=0}^{p-1} f_{T,b}(\omega^i)\right|$, where $\omega$ is a primitive $p$th root of unity. Notice for example that if $0\in T$, then the Bias evaluates to zero (adding/removing zero gives a bijection between even/odd sets).

To disprove your conjecture we can look at the set $T=\lbrace t | \frac{p}{4} \leq t \leq \frac{3p}{4}\rbrace$, and set $b=0$. Using that $\prod_{i=0}^{p-1}(1+\omega^i)=2$, we can say $$\operatorname{Bias}(T,0)=\frac{2}{p}|\sum_{i=0}^{p-1}\prod_{t\in T} \frac{(1-\omega^{it})}{(1+\omega^{it})}|.$$ From here you can check that: (1) every term in the sum is nonnegative, so we may ignore the absolute value (2) the term for $i=1$ is $\left(\prod_{t\in T} \frac{1-\cos(2\pi t/p)}{1+\cos(2\pi t/p)}\right)^{1/2}>(1+\sqrt{2})^{p/8}=2^{O(p)}$.