# Bounding the size of set systems if the parity of intersection sizes are fixed.

I have been stuck on the following for a while. Earlier parts of the question proved a few results that I think may be applicable.

Earlier Proven Results:

1. Suppose $$A_1, A_2 , ... , A_k$$ and $$B_1 , B_2, ... , B_k$$ are subsets of $$[n]$$ such that $$|A_i \cap B_i|$$ is even for all $$i$$ and $$|A_i \cap B_j|$$ is odd for all $$j\not=i$$. Then $$k \leq n$$

The questions

1. Let $$\mathcal{A} , \mathcal{B}$$ be two subsets of $$\mathcal{P}(n)$$ such that $$|A\cap B|$$ is even for all $$A \in \mathcal{A}$$, and $$B \in \mathcal{B}$$. Prove that $$|\mathcal{A}| |\mathcal{B} | \leq 2^n$$
2. Let $$\mathcal{A} , \mathcal{B}$$ be two subsets of $$\mathcal{P}(n)$$ such that $$|A\cap B|$$ is odd for all $$A \in \mathcal{A}$$, and $$B \in \mathcal{B}$$. Prove that $$|\mathcal{A}| |\mathcal{B} | \leq 2^{n-1}$$

We were provided the following hint:
Fix $$A_0\in\mathcal{A}$$ and $$B_0 \in \mathcal{B}$$. Let $$\mathcal{A}^{'}:= \{A\Delta A_0 :A \in \mathcal{A}\}$$ and $$\mathcal{B}^{'}:= \{B\Delta B_0 :B \in \mathcal{B}\}$$
Then consider families of the form $$\mathcal{A}^{'}$$ or $$\mathcal{A}^{'} \cup \mathcal{A}$$

My attempts
I didn't really get the hint. I tried to arrive at a contradiction by assuming the sizes were larger than the bound and contradict the parity of the intersections. No success.

This is an attempt to answer question 1.

Without loss of generality we can assume that $$\mathcal A$$ and $$\mathcal B$$ are maximal, in particular they contain $$\varnothing$$.

From the hint, it follows that $$A,A'\in\mathcal A$$ then $$A▵A'\in\mathcal A$$ and the same for $$\mathcal B$$.

Then $$\mathcal A$$ and $$\mathcal B$$ are both subgroups of $$\mathcal P(n)$$ w.r.t. the group operation $$\triangle$$.

Assume for the moment that $$\mathcal A\cap\mathcal B=\{\varnothing\}$$.

Let $$\mathcal C$$ be the subgroup generated by $$\mathcal A\cup\mathcal B$$.

By basic group theory, $$\mathcal C$$ is isomorphic to $$\mathcal A\times\mathcal B$$.

Thererefore $$|\mathcal A\times\mathcal B|\le |\mathcal P(n)|$$ which proves the inequality in question 1.

Finally when $$\mathcal A\cap\mathcal B$$ is a non trivial subgroup of $$\mathcal P(n)$$, reason similarly in the quotient group.