9
$\begingroup$

I'm trying to solve the following problem:

Let $\mathcal{A}, \mathcal{B} \subset \mathcal{P}(n)$ be two set systems such that $|A \cap B|$ is even for each $A \in \mathcal{A}, B \in \mathcal{B}$. Prove that $|\mathcal{A}||\mathcal{B}| \le 2^n$.

My idea for solving it is to construct an injection $f: \mathcal{A} \times \mathcal{B} \to \mathcal{P}(n)$, and I think the function given by $(A, B) \mapsto A \cup B$ should work. However, I am unsure how to prove this.

I've been looking at the symmetric difference of two sets in $\mathcal{A}$ to try and help with this (because I was given a hint to use this), but I can't make this work.

Does anybody have any clues?

$\endgroup$
6
  • $\begingroup$ I think $f: \mathcal{A} \times \mathcal{B} \to \mathcal{P}(n)$, will not be injective as $A \cap B = A' \cap B'$ for $A \neq A'$ and $B \neq B'$. Nice question. $\endgroup$
    – Shri
    Nov 20, 2017 at 17:10
  • $\begingroup$ See if you allow $|A \cap B| = 0$ then certainly $|\mathcal{A}||\mathcal{B}| \le 2^n$ will fail. Take $\mathcal{A}$ to consist of all sets which are subsets of even numbers and $\mathcal{B}$ to consist of all sets which are subsets of odd numbers. So every A should intersect with every B means they should have nonempty intersection. $\endgroup$
    – Shri
    Nov 20, 2017 at 17:23
  • $\begingroup$ @shrinit It doesn't fail. E.g. if $n$ is even, then $|\mathcal A|=2^{\frac{n}{2}}$ and, similar, $|\mathcal B|=2^{\frac{n}{2}}$ so $|\mathcal A||\mathcal B|=2^n$. $\endgroup$
    – user491874
    Nov 20, 2017 at 17:38
  • $\begingroup$ No... I am saying how many subsets of even numbers are there.. Uncountably many... Similarly for odd numbers. $\mathcal{P}(n)$ is set of all subsets of natural number. Isn't it? $\endgroup$
    – Shri
    Nov 20, 2017 at 17:43
  • 2
    $\begingroup$ If $\mathcal A=\{\{1,2\},\{3,4\}\}$ and $\mathcal B=\{\{1,2,3,4\}\}$ then the map $(A,B)\mapsto A\cup B$ will not be injective because $\{1,2\}\cup\{1,2,3,4\}=\{3,4\}\cup\{1,2,3,4\}.$ $\endgroup$
    – Dap
    Nov 22, 2017 at 22:26

1 Answer 1

9
+50
$\begingroup$

This can be proved using linear algebra over the field of two elements, $GF(2).$ Sets form a vector space over $GF(2)$ where symmetric difference is the vector addition. Suppose there are $k$ linearly independent sets in $\mathcal A.$ Let $\mathcal A'$ be a complementary vector space, so it has dimension $n-k.$ Each set $B\in\mathcal B$ defines a linear map $\mathcal A'\to GF(2)$ by $S\mapsto |S\cap B|$ mod $2.$ If $B,B'\in\mathcal B$ satisfy $|S\cap B|=|S\cap B'|$ mod $2$ for all $S\in\mathcal A',$ then by linearity and the fact that $|S\cap B|=|S\cap B'|$ mod $2$ for all $S\in\mathcal A$ we know that $|S\cap B|=|S\cap B'|$ mod $2$ for all $S.$ In particular $|\{i\}\cap B|=|\{i\}\cap B'|$ mod $2$ for all elements $i,$ which implies $B=B'.$ So the sets in $\mathcal B$ map injectively to the vector space of linear maps $\mathcal A'\to GF(2),$ which has dimension $n-k.$ So $|\mathcal A|\cdot|\mathcal B|\leq 2^k2^{n-k}=2^n.$

$\endgroup$
1
  • 2
    $\begingroup$ Thanks for the brilliant answer. I think the crucial observation (and the main takeaway for me here) is that, as you view subsets as vectors, the map $(A,B) \mapsto |A \cap B| (\mod 2)$ is a non-degenerate bilinear form on that vector space. Good to know! $\endgroup$
    – user491874
    Nov 23, 2017 at 23:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .