# 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)\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$.

• Should it be $\textrm{Bias}(T,b)$? Otherwise, what is $b$? – Max Alekseyev Aug 7 '14 at 6:49
• Sorry for this problem. $b$ is an element in ${\mathbb F}_p$. Thank you. – Joe Franklin Aug 7 '14 at 7:03
• I'm not sure if my calculations are correct, but picking $T$ to be the elements in the interval $(\frac{p}{4},\frac{3p}{4})$ should give you a bias $~2^{cp}$ for $b=0$. – Gjergji Zaimi Aug 7 '14 at 8:58
• @Joe: So, do you claim that the bias of $T$ does not depend on the choice of $b$? – Max Alekseyev Aug 7 '14 at 13:02
• @Gjergji: Great! Did you get an explicit bound on $c$? – Joe Franklin Aug 7 '14 at 13:13

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)}$.
• Very good example and thank you very much. I am so sorry that I made a typo on the magnitude of $Bias(T)$. The right conjecture should be: is there any method to prove $$Bias(T)=2^{(1/2+p(1))p}, \forall T\ne \emptyset$$ for $|T|\sim p/2$? Of course we can still ask for which kind of $T$ $$Bias(T)=2^{o(p)}.$$ – Joe Franklin Aug 11 '14 at 2:38
• Is the 1/2 by analogy with a sum of random $\pm 1$ terms, or is there some other reason as well? – Kevin P. Costello Aug 11 '14 at 2:43
• @Kevin: Yes, it's by the analogy with a sum of random coin flipping. If for all $T$, $Bias(T)\leq 2^{o(p)}$, this will lead a contradiction to the bounds on small biased set. – Joe Franklin Aug 11 '14 at 2:48
• @Joe, the same method still applies. For any $T$ the terms in the sum above are bounded by $2^{o(1)+p/2}$. – Gjergji Zaimi Aug 11 '14 at 3:53