Small doubling, atomic structure and $\ell$-divisible set families

Small doubling, atomic structure and $\ell$-divisible set families, Discrete Analysis 2022:11, 16 pp.

The following fact is a well-known and simple illustration of the power of linear algebra in solving combinatorial problems. Let $\mathcal A$ be a collection of subsets of $\{1,2,\dots,n\}$ such that any two subsets in the collection have an intersection of even size. Then $|\mathcal A|\leq 2^{\lfloor n/2\rfloor}$, with equality attained if $\mathcal A$ consists of all sets $A$ that are unions of the sets $\{1,2\}, \{3,4\}, \dots$, where the last set in the sequence is $\{n-1,n\}$ if $n$ is even, and $\{n-2,n-1\}$ if $n$ is odd.

This can be proved by associating with each set $A$ its characteristic function, and regarding each function as an element of $\mathbb F_2^n$. If $x$ and $y$ are elements of $\mathbb F_2^n$, then we can define their scalar product $\langle x,y\rangle$ to be $\sum_{i=1}^nx_iy_i$, and the question we started with is then equivalent to asking how many vectors it is possible to choose if all scalar products are zero.

If $\mathcal A\subset\mathbb F_2^n$ and we choose a maximal linearly independent set $x^{1},\dots,x^{m}$ of $\mathcal A$, then every element $x$ of $\mathcal A$ satisfies $m$ linearly independent conditions $\langle x^i,x\rangle=0$, so $\mathcal A$ lives inside a subspace of codimension at least $m$ and therefore dimension at most $n-m$. It follows that $m\leq n-m$ and therefore that $m\leq\lfloor n/2\rfloor$, which gives the required bound on $|\mathcal A|$.

An obvious follow-up question is to ask what happens if the size of every intersection is a multiple of 3, or more generally of $\ell$ for some positive integer $\ell$. The obvious generalization of the construction above gives a lower bound of $2^{\lfloor n/\ell\rfloor}$, but the simple argument for the upper bound no longer works, and indeed in 1983 Frankl and Odlyzko constructed families that are considerably larger.

They also conjectured that the lower bound holds if one strengthens the hypothesis by assuming that larger intersections have sizes divisible by $\ell$. That is, they conjectured that for every $\ell$ there exists $k$ such that if $\mathcal A$ is a collection of subsets of $\{1,2,\dots,n\}$ such that any $k$ sets in $\mathcal A$ have an intersection of cardinality divisible by $\ell$, then $|\mathcal A|\leq 2^{\lfloor n/\ell\rfloor}$.

This paper proves the conjecture of Frankl and Odlyzko. Along the way, the authors prove a lemma of independent interest, the statement of which has a similar flavour to that of Freiman’s theorem – hence the phrase “small doubling” in the title of the paper. Given two vectors $x,y\in\{0,1\}^n$ write $x.y$ for their pointwise product, which corresponds to the intersection of the corresponding subsets of $\{1,2,\dots,n\}$. Also, given a subset $X\subset\{0,1\}^n$, write $\dim(X)$ for the dimension of the subspace spanned by $X$. The lemma concerns what can be said about $X$ if $\dim(X.X)$ is not much larger than $\dim(X)$ – more precisely, the assumption is that $\dim(X.X)-\dim(X)\leq h$ for some constant $h$.

A simple example of such a set is to take disjoint subsets $A_1,\dots,A_r$ of $\{1,2,\dots,n\}$ and to take the space $V$ of all vectors that are constant on each set $A_i$, and to add to it a subspace $W$ of dimension $\sqrt h$ of vectors supported outside $A_1\cup\dots\cup A_r$. The space $V+W$ has dimension $r+\sqrt h$, and the space $(V+W)(V+W)=V.V+W.W=V+W.W$ has dimension $r+\dim(W.W)$, which is at most $r+h$, since if $w_1,\dots,w_t$ is a basis of $W$, then the vectors $w_i.w_j$ are a basis of $W.W$.

The lemma proved by the authors is that, at least qualitatively speaking, all examples are of this kind. They show that if $\dim(X.X)-\dim(X)\leq h$, then there exist disjoint subsets $A_1,\dots,A_r\subset\{1,2,\dots,n\}$ with $r=\dim(X)$ such that every vector in $X$ is constant on each $A_i$, and the restrictions of the $x\in X$ to the complement of $A_1\cup\dots\cup A_r$ span a subspace of dimension at most $2h$.