Number of linearly bisected subsets in finite vector space $F_2^n$

Question

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

Answer 1

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.