You are currently browsing the monthly archive for juin 2017.

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}).