Question: Suppose I have $n$ finite sets $A_1,\dots,A_n$ contained in some fixed set $S$, and I am given non-negative integers $N$ and $N_1,\dots,N_n$ such that each $A_i$ has cardinality $N$, and each $k$-tuple intersection has cardinality $\leq N_k$.
Can I use this to construct a good lower bound on the cardinality of $\bigcup_{i=1}^n A_i$?
Answer by Tim Gowers: I don't know your reason for asking this question, so it's unlikely that what I'm about to write will be helpful. Nevertheless, there's an easy method I like a lot for deducing a lower bound just from the knowledge that $N_2$ is small. It may be contained in what has been said above -- I haven't checked.
The idea is to think of each set $A_i$ as a $01$-valued function on a set of size $M$. We then look at the $\ell_ 2$ norm of $\sum_i A_i$. The square of the $\ell_ 2$ norm is $\sum_ {i,j}|A_ i \cap A_ j|$, which by assumption is at most $nN + n(n-1)N_2$. But we also have a lower bound: the $\ell_ 1$ norm of the sum is $nN$, from which it follows that the square of the $\ell_2$ norm is at least $(nN)^2/M$.
Putting these two bits of information together gives a lower bound for $M$ of $nN/(1+(n-1)N_2/N)$. So, for example, if $N_ 2 = cN$ for some smallish positive constant $c$, then the lower bound is roughly $N/c$.
This question has been asked in MathOverflow many years ago and really good answer has been given by professor Tim Gowers but some moments of his answer are unclear. I tried to write it down explicitly but I came across some obstacles so I'd be happy if you can help me to understand that!
Suppose that $M=\lvert X\rvert,$ where $X:=\cup_{i=1}^n A_i$ and for each $i=1,\dots,n$ consider $f_i:X\to \{0,1\}$ defined by $$f_i(x) = \begin{cases} 1, & \text{if }x\in A_i \\ 0, & \text{if }x\notin A_i \end{cases}.$$
We see that $\sum \limits_{x\in X}f_i(x)=|A_i|.$
What is the $\ell_2$ norm of $\sum \limits_{i=1}^n A_i$?
Can anyone explain how to obtain those bounds please?
We are thinking of $X$ as a measure space with the counting measure. Let $\mu$ be the counting measure. By definition, the $\ell_2$ norm of a function $g$ on $X$ with respect to $\mu$ is $\|g\|_2=\left(\int_X g(x)^2\,d\mu\right)^{1/2}$.
In this case, the function we are taking the $\ell_2$ norm of is $F=\sum_{i=1}^n f_i$, for the functions $f_1,\dots,f_n$ you defined. Therefore, the square of the $\ell_2$ norm is $$ \|F\|_2^2=\int_X \left(\sum_{i=1}^n f_i(x)\right)^2\,d\mu=\sum_{i=1}^n\sum_{j=1}^n \int_X f_i(x)f_j(x)\,d\mu=\sum_{i=1}^n\sum_{j=1}^n |A_i\cap A_j| $$ The reason that $\int_X f_i(x)f_j(x)\,\mu=|A_i\cap A_j|$ is the the $\{0,1\}$-valued function $f_i(x)\cdot f_j(x)$ is only $1$ when $x$ is in both $A_i$ and $A_j$.
It should be clear why $\sum_{i=1}^n\sum_{j=1}^n |A_i\cap A_j|\le nN+n(n-1)N_2$. When $i=j$, the contribution is $|A_i|=N$, and when $i\neq j$, the contribution is $|A_i\cap A_j|\le N_2$. We have now derived $$\|F\|_2^2\le nN+n(n-1)N_2.\tag1$$
Timothy Gowers then states that since the $\ell_1$ norm of $\sum_{i=1}^n f_i$ is $nN$, that the $\ell_2$ norm must be at least $(nN)^2/M$. This follows from the Cauchy Schwarz inequality, with respect to the usual inner product $\langle g,h\rangle =\int_X g(x)h(x)\,d\mu$ for functions on $X$. Namely, if we let $F=\sum_{i=1}^n f_i(x)$, and let $\bf 1$ be the constant function $1$, then applying Cauchy-Schwarz to $g=F$ and $h={\bf 1}$, we get $$ \langle F,{\bf 1}\rangle\le \|F\|_2\cdot \|{\bf 1}\|_2 $$ Noting that $\langle F, {\bf 1}\rangle=\int_X f(x)\cdot 1\,d\mu=nN$ and $\|{\bf 1}\|_2=\left(\int_X 1\,d\mu\right)^{1/2}=M^{1/2}$, the above lets you conclude $$\|F\|_2^2\ge (nN)^2/M.\tag2$$ Conclude by combining $(1)$ and $(2)$.