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$
  • $\begingroup$ Should it be $\textrm{Bias}(T,b)$? Otherwise, what is $b$? $\endgroup$ – Max Alekseyev Aug 7 '14 at 6:49
  • $\begingroup$ Sorry for this problem. $b$ is an element in ${\mathbb F}_p$. Thank you. $\endgroup$ – Joe Franklin Aug 7 '14 at 7:03
  • $\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$ – Gjergji Zaimi Aug 7 '14 at 8:58
  • $\begingroup$ @Joe: So, do you claim that the bias of $T$ does not depend on the choice of $b$? $\endgroup$ – Max Alekseyev Aug 7 '14 at 13:02
  • $\begingroup$ @Gjergji: Great! Did you get an explicit bound on $c$? $\endgroup$ – Joe Franklin Aug 7 '14 at 13:13
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)}$.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Joe Franklin Aug 11 '14 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$ – Kevin P. Costello Aug 11 '14 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$ – Joe Franklin Aug 11 '14 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$ – Joe Franklin Aug 11 '14 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$ – Gjergji Zaimi Aug 11 '14 at 3:53

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.