6
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$ Aug 7, 2014 at 8:58
  • $\begingroup$ @Gjergji: Great! Did you get an explicit bound on $c$? $\endgroup$ Aug 7, 2014 at 13:13

1 Answer 1

6
$\begingroup$

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)}$.

$\endgroup$
6
  • $\begingroup$ 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)}.$$ $\endgroup$ Aug 11, 2014 at 2:38
  • $\begingroup$ Is the 1/2 by analogy with a sum of random $\pm 1$ terms, or is there some other reason as well? $\endgroup$ Aug 11, 2014 at 2:43
  • $\begingroup$ @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. $\endgroup$ Aug 11, 2014 at 2:48
  • $\begingroup$ @Gjergji: Thank you again for your answer. Could you put this answer as a comment so that keep this problem unanswered? I shall then update my question. $\endgroup$ Aug 11, 2014 at 2:50
  • $\begingroup$ @Joe, the same method still applies. For any $T$ the terms in the sum above are bounded by $2^{o(1)+p/2}$. $\endgroup$ Aug 11, 2014 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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