Kneser's theorem for codes and $\ell$-divisible set families

Abstract

A $k$-wise $\ell$-divisible set family is a collection $\mathcal{F}$ of subsets of $\{1,\dots ,n\}$ such that any intersection of $k$ sets in $\mathcal{F}$ has cardinality divisible by $\ell$. If $k=\ell =2$, it is well-known that $|\mathcal{F}|\le 2^{\lfloor n/2\rfloor }$. We generalise this by proving that $|\mathcal{F}|\le 2^{\lfloor n/p\rfloor }$ if $k=\ell =p$, for any prime number $p$. For arbitrary values of $\ell$, we prove that $4{\ell }^2$-wise $\ell$-divisible set families $\mathcal{F}$ satisfy $|\mathcal{F}|\le 2^{\lfloor n/\ell \rfloor }$ and that the only families achieving the upper bound are atomic, meaning that they consist of all the unions of disjoint subsets of size $\ell$. This improves upon a recent result by Gishboliner, Sudakov and Timon, that arrived at the same conclusion for $k$-wise $\ell$-divisible families, with values of $k$ that behave exponentially in $\ell$. Our techniques rely heavily upon a coding-theory analogue of Kneser's Theorem from additive combinatorics.

arXiv comment15 pages