February, 2017

Solution:
Answer: 2048
Let $n=|S|$. Let the sets in $S$ be $s_{1}, s_{2}, \ldots, s_{n}$. We bound the sum $\sum_{1 \leq i<j \leq n}\left|\Delta\left(s_{i}, s_{j}\right)\right|$ in two ways. On one hand, by the condition we have the obvious bound
$$\sum_{1 \leq i<j \leq n}\left|\Delta\left(s_{i}, s_{j}\right)\right| \geq \binom{ n}{2} \delta m$$
On the other hand, for $1 \leq i \leq m$, let $t_{i}=\left|\left\{1 \leq j \leq n: i \in s_{j}\right\}\right|$. Then it is clear that
$$\sum_{1 \leq i<j \leq n}\left|\Delta\left(s_{i}, s_{j}\right)\right|=\sum_{k=1}^{m} t_{k}\left(n-t_{k}\right) \leq \frac{n^{2}}{4} m$$
by AM-GM. Therefore, we get the bound
$$\binom{n}{2} \delta m \leq \frac{n^{2}}{4} m \Rightarrow n \leq \frac{2 \delta}{2 \delta-1}=2048$$
To give a construction with $n=2048$, take $m=2047$. For the rest of this construction, we will be interpreting the integers $1,2, \ldots, m$ as 11-digit integers in binary. Given this interpretation, define a dot product $x \odot y$ of two positive integers $0 \leq x, y \leq m$ the following way. If $x=\left(x_{1} x_{2} \ldots x_{11}\right)_{2}, y=\left(y_{1} y_{2} \ldots y_{11}\right)_{2}$ in binary, then
$$x \odot y=\sum x_{i} y_{i} \quad(\bmod 2)$$
Now we can define the sets $s_{1}, s_{2}, \ldots, s_{2048}$. Define
$$s_{i}=\{1 \leq j \leq m:(i-1) \odot j=1 .\}$$
A computation shows that this construction works.

Some notes: here is the motivation behind the construction. We are treating the integers $0,1, \ldots, m$ as the vector space $V=\mathbb{F}_{2}^{11}$, and the sets $s_{i}$ correspond to linear functionals $f_{i}: V \rightarrow \mathbb{F}_{2}$. In particular, the function $f_{i}: V \rightarrow \mathbb{F}_{2}$ is simply defined as $f_{i}(x)=(i-1) \odot x$, which one can easily check to be linear. This construction corresponds to Hadamard matrices of size $2^{11}$.