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!
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$.