Two families with odd intersections of their sets Let $\mathcal{A}$, $\mathcal{B}$ be families of subsets of $\{1,2,\ldots,n\}$ such that $|A \cap B|$ is odd for all $A \in \mathcal{A}$, $B \in \mathcal{B}$. Prove that $|\mathcal{A}||\mathcal{B}| \leq 2^{n-1}$.
So I know how to establish a bound if instead $|A \cap B|$ is even. One can treat $\mathcal{A}$, $\mathcal{B}$ to be maximal and considers the characteristics vectors of the sets in these families, over the field $\mathbb{F}_2$ $-$ in this case, it is easy to check that if $A, A' \in \mathcal{A}$, then the symmetric difference $A\triangle A'$ is also in $\mathcal{A}$ (this does not work for the '$|A \cap B|$ is odd' case -- in fact, if $A, A' \in \mathcal{A}$ then the symmetric difference is certainly NOT in $\mathcal{A}$) and so the sets of vectors in $\mathcal{A}$ (and analogously in $\mathcal{B}$) form subspaces of $\mathbb{F}_2^n$. By the evenness condition (by taking inner products) we see that these subspaces intersect trivially and we finish off easily to get a (tight) bound $2^n$.
But what do we do in the case of oddness? I am given the following hint: "Fix $A_0, B_0$ and consider $\mathcal{A}'= \{A\triangle A_0: A \in \mathcal{A}\}$, perhaps its union with $\mathcal{A}'\cup \mathcal{A}$ and similarly for $\mathcal{B}$". I tried to form some subspaces as above but unfortunately all my ideas break down.
Any help appreciated!
 A: In your argument for the even case, you can't conclude that the subspaces intersect trivially. Over $\mathbb F_2$, orthogonality (in the sense of vanishing inner products) doesn't imply trivial intersection; in fact every vector with an even number of $1$s is orthogonal to itself. What you can conclude, however, is that orthogonality to the subspace $\mathcal A$ of dimension $k$ imposes $k$ linearly independent linear constraints on $\mathcal B$, and hence the dimension of $\mathcal B$ can be at most $n-k$.
In the odd case, again assume maximality, and pick some vector $A_0\in\mathcal A$ (I think this is what the hint means, even though it's not explicitly stated that $A_0$ is in $\mathcal A$) and form $\mathcal{A}'= \{A\triangle A_0: A \in \mathcal{A}\}$. Since $A_0$ has odd overlap with all elements of $\mathcal B$, $A\triangle A_0$ has even overlap with all elements of $\mathcal B$. Thus we can apply the considerations from the even case to $\mathcal A'$ and $\mathcal B$.
From the maximality of $\mathcal A$ and $\mathcal B$, we can conclude that they are affine subspaces (since adding any difference between two of their elements to a third (that is, forming the symmetric difference between the three) again yields a vector with odd overlap with the entire other family). Since $\mathcal A'$ is a translated version of the affine space $\mathcal A$ and contains the origin, it's a subspace, say, of dimension $k$. So the affine space $\mathcal B$ fulfils $k$ linearly independent linear constraints, and thus lies in a subspace of dimension at most $n-k$. But it doesn't contain the origin. Hence its dimension is lower than that of this subspace, that is, at most $n-k-1$.
