Skip to main content
3 of 4
added 8 characters in body

A parity counting problem for subsets over finite fields

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)=2^{o(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^{o(|S|)}, \forall T\ne \emptyset$.