Let $V=\mathbb{F}_p^n$ be a vector space over a finite prime field. One knows then which subsets $A\subset V$ satisfy $A+A=A$, the sets that are stable under addition: these are the kernels of linear maps, that is, each such set $A$ is the zero set of a bunch of linear forms.

Now we consider a two-coordinates analogous problem, that is, we consider a set $A\subset V\times V$ and define the sets

$\displaystyle{P\stackrel{V}{+}P= \{(x,y_1+ y_2)\mid (x,y_1),(x,y_2)\in P\}}$

and $P\stackrel{H}{+}P$, V and H meaning vertical and horizontal. What are the sets that satisfy both $P\stackrel{V}{+}P=P$ and $P\stackrel{H}{+}P=P$? Call such a set a transverse set. Natural exemples are cartesian products of vector spaces (which we shall call rectangles) as well as zero sets of bilinear forms. More generally, a set of the form $\displaystyle{\{(x,y)\in W_1\times W_2\mid Q_1(x,y)=\cdots=Q_r(x,y)=0\}}$ for some subspaces $W_2,W_2\leq V$ and some bilinear forms $Q_i$ is horizontally and vertically closed. Call such a set a bilinear set, and call its codimensions the codimensions of the subspaces and the number of bilinear forms required (the dimension of the space of bilinear forms vanishing on it). What is the relationship between transverse sets and bilinear sets? Are all transverse sets essentially bilinear sets?

For a transverse set $P\subset V\times V$ and $x\in V$, let $P_x$ be the fiber above x. Thus $P=\bigcup_x \{x\}\times P_x$ and $P_x$ is a vector space. Actually $P_x$ depends only the projective class $[x]\in P(V)$. Moreover, the stability under horizontal operations is equivalent to the property that if $[z]$ is on the projective line spanned by $x$ and $y$, we have $P_z\supset P_x\cap P_y$.

The codimension 1 case

Suppose $P_0=V$ and each subspace $P_x$ has codimension at most 1. Write $P_x=\xi(x)^\perp$ with $\xi(x)\in P(V)$ some vector uniquely defined up to homothety. It is easy to see that the set of $x$ such that $P_x=V$ is a vector subspace which we call $W$. Furthermore, if $x-y\in W$, we have $\xi_x=\xi_y$, so that $\xi$ descends to an injective map on $V/W$. Thus it is enough to study the case where $P_x$ has codimension exactly one unless $x=0$. In other words, we have a map $\xi : P(V)\rightarrow P(V)$ satisfying the property that if $z$ is on the projective line spanned by $x$ and $y$, then $\xi_{z}$ lies on the projective line spanned by $\xi_x$ and $\xi_y$. Thus $\xi$ maps projective lines into lines. Actually it can be quickly checked that such a map is either bijective or constant on each single projective line.

If we suppose it is injective, too, then by the fundamental theorem of projective geometry, we conclude that it is a projective map. Thus it is induced by a linear map $\xi : V\rightarrow V$. Hence writing $Q(x,y)=\xi(x)\cdot y$, we have shown that $P$ is the zero set of the bilinear form $Q$.

In general $\xi$ is far from being injective. It can for instance be constant on $P(V)$ (equal to $H^\perp$ for some hyperplane $H$). In this case $P=\{0\}\times V\cup V\times H$. This is neither a rectangle, nor the zero form of a quadratic form, because if it was, $\xi$ could be taken linear, and because $\xi_x=0\leftrightarrow x=0$, it should be injective. In fact, if it is the intersection of zero sets of a family of bilinear forms, there needs to be $n$ bilinear forms in this family, such as the forms $x_iy_n=0$ if (wlog) $H$ is the hyperplane $y_n=0$. However $P$ obviously contains a very large rectangle.

These are actually the only cases: such a map $\xi$ is either injective or constant. Indeed, if $P(V)$ is just a line, it’s obvious, so suppose $\dim V\geq 3$. Suppose that $\xi$ maps projective lines into lines (in the sense above) but is neither injective nor constant. That is, there exist two distinct points $x,y$ such that $\xi_x=\xi_y$, and a third point $z$ satisfying $\xi_z\neq \xi_x$. This implies that $x,y,z$ span a projective plane. Take a point $w\neq y,z$ on the line spanned by $y,z$. Because $\xi$ is a bijection on both lines $(yz),(xz)$, you can find $w'\neq x,z$ on $(xz)$ such that $\xi_w=\xi_{w'}\neq \xi_x$. Now consider the intersection $u=(ww')\cap (xy)$. Then  you have $\xi_u=\xi_x=\xi_y\neq \xi_w$, so that on the line $(ww')$, the map $\xi$ is neither constant nor injective, which is absurd.

Arbitrary codimension

A more general potential counterexample, communicated to me by Ben Green, is a set of the form $P=\bigcup_{i=0}^r V_i\times W_i$ where $V_i, W_i$ are sequences of increasing (resp. decreasing) subspaces.  Thus for $x\in V$, we have $P_x=W_{i(x)}$ where $i(x)=\min\{i\mid x\in V_i\}$. Again you can make it a bilinear set, but you need atrociously many bilinear forms.

However it contains a large rectangle. In fact, $\dim V_i\leq n-(r-i)$ while $\dim W_i=n-i$ so that the density of $P$ is at most $(r+1)p^{-r}\ll p^{-r/2}$. Thus $r\ll \log\delta^{-1}$. Finally by the pigeonhole principle, one of the cartesian products $V_i\times W_i$ have density at least $\delta/\log\delta^{-1}$.

In general, we have a vector space $P_x=A_x^\perp$. Suppose for instance each $A_x$ has codimension 2. If we manage to find maps $x\mapsto \xi_1(x),\xi_2(x)$ such that $\xi_i(x+y)\in\text{span} (\xi_i(x),\xi_i(y))$ for each $i,x,y$, we are in good shape. Though it is not clear how to show that such a consistent choice of bases can be made…

The conjecture

If a $A\subset V\times V$ has cardinality at least $\delta \lvert V\rvert ^2$, it contains a bilinear set of (linear and bilinear) codimensions $c(\delta)=O(\log^{O(1)}\delta^{-1})$.