3
$\begingroup$

We consider the $n$-dimenstional finite vector space $\mathbb{F}_2^{n}$ over the finite field of two elements. For a subset $A\subseteq \mathbb{F}_2^{n}$ of even size $|A|=2m$ and a linear form $l\in(\mathbb{F}_2^{n})^*$ let us say that $l$ bisects $A$, if $$|\{a\in A\ |\ l(a)=0\}|=|\{a\in A\ |\ l(a)=1\}|\,\,\,\,(=m). $$ Equivalently, for a subspace $L\leq \mathbb{F}_2^{n}$ of dimension $n-1$ (i.e. $|L|=2^{n-1}$), let us say that $L$ bisects $A$, if $$|A\cap L|=|A\setminus L|\,\,\,\,(=m). $$ How many subsets $A\subseteq \mathbb{F}_2^{n}$ of size $|A|=2m$ are there which are bisected by some suitable linear form (equivalently: by some subspace of dimension $n-1$)?

An alternative problem which I'm interested in (and which is maybe easier to solve??) is:

Determine the limit $$\lim_{n\rightarrow\infty}\frac{|\{A\subseteq \mathbb{F}_2^{n}|\,|A| \text{ is even and $A$ is bisected}\}|}{|\{A\subseteq \mathbb{F}_2^{n}|\,|A| \text{ is even}\}|}. $$ (Clearly, $|\{A\subseteq \mathbb{F}_2^{n}|\,|A| \text{ is even}\}|=2^{2^n-1}$.)

(My calculations seem to support the conjecture that the limit equals 1.)

$\endgroup$
3
  • $\begingroup$ Do you know any non-bisectable subset of even size? $\endgroup$ Aug 30, 2015 at 10:56
  • $\begingroup$ @Ilya: Yes, the smallest examples I found are some subsets of size 6 in $\mathbb{F}_2^4$. $\endgroup$
    – user50982
    Aug 30, 2015 at 13:18
  • $\begingroup$ For example (writing vectors as rows): $A:=\{(0,0,0,0),(1,0,0,0),(0,1,0,0),(1,0,1,0),(1,1,0,1),(1,0,1,1)\}\subseteq \mathbb{F}_2^4$ is not bisectable by a subspace of dimension 3. $\endgroup$
    – user50982
    Aug 30, 2015 at 13:29

1 Answer 1

3
$\begingroup$

The probability that a random subset is bisected by a fixed linear subspace is

$$ \frac{ \sum_{k=0}^{2^{n-1}}\binom{2^{n-1}}{k}^2}{2^{2^n-1}} = \frac{\binom{2^n}{2^{n-1}} }{2^{2^n-1} } $$

Using the asymptotic

$$\binom{N}{N/2} \approx \frac{ C 2^{N}} { \sqrt N} $$

for some constant $C$, we obtain

$$\approx \frac{2 C}{ \sqrt{ 2^{n} } }$$

for some constant $C$. (By $\approx$ I mean they are equal up to multiplication by $1+o(1)$ )

There are $2^n-1$ linear subspaces, so the expected total number of bisecting subsets is large, roughly $2C 2^{n/2}$.

Given two transverse subspaces, they divide $\mathbb F_2^n$ into four equal sets, and the probability that they both bisect is

$$\frac{\sum_{k=0}^{2^{n-2}} \sum_{l=0}^{2^{n-2}}\binom{2^{n-2}}{k}^2\binom{2^{n-2}}{l}^2}{ 2^{2^n-1}} =\frac{\binom{2^{n-1}}{2^{n-2}}^2 }{2^{2^n-1} } $$

using the same asymptotic:

$$ \approx \frac{ \left( \frac{ C 2^{2^{n-1}}}{\sqrt{ 2^{n-1}}}\right)^2 } { 2^{2^n-1}} = \frac{ 4 C^2} { 2^n } $$

So the probabilities that two different linear subspaces bisect a set are approximately independent. This means that the expected value of the square of the number of linear subspaces that bisect is roughly $( 2 C 2^{n/2} )^2$.

Let $X$ be this number, viewed as a random variable.

Because $E[X^2] \approx E[X]^2$, the variance of $X$ is $o ( E[X]^2)$, so the standard deviation is $o(E[X])$ so by Chebyshev's inequality the probability that $X$ is $0$ is $o(1)$.

This implies that the limiting probability of at least one bisecting subspace exists approaches $1$, as you predict.

$\endgroup$
6
  • $\begingroup$ Could you explain how you obtained the first equation? $\endgroup$
    – kodlu
    Aug 29, 2015 at 10:31
  • $\begingroup$ @kodlu Sure. Using $\binom{n}{k}= \binom{n}{n-k}$, and then it counts the number of subsets of subsets of $[2^n]$ of size $2^{n-1}$ in a transparent manner - by counting, for each $k$, the number of subsets with $k$ elements in the first half and $2^{n-1}-k$ elements in the second half. $\endgroup$
    – Will Sawin
    Aug 29, 2015 at 12:12
  • $\begingroup$ @Will: Thanks for your answer! In your comment explaining the first equation I don't get why you work with $2^{n-1}-k$. It's $k$ elements of $A$ in the first half and again $k$ elements in the second. Still, your first formula is correct. Also, its not "subsets of subsets", right? I will try and check the rest of your proof now. $\endgroup$
    – user50982
    Aug 30, 2015 at 9:08
  • $\begingroup$ @Will: You mean "...so the expected total number of bisecting subspaces is large...", right? $\endgroup$
    – user50982
    Aug 30, 2015 at 10:01
  • $\begingroup$ @user50982 The only reason to work with $2^{n-1}-k$ is to give a bijective proof of the first formula. I'm sure there's multiple ways to obtain it. And yes, I mean subspaces. $\endgroup$
    – Will Sawin
    Aug 30, 2015 at 12:36

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.