Let $A$ be a finite set of non-negative integers and write $I_k$ for the set ${0,1,\ldots,k-1}$. Form all possible l-wise intersections $(A+k_1)\cap \ldots \cap (A+k_l)$, where each $k_i$ runs through all values of the set $I_k$ (thus giving us $k^l$ of such intersections). Given an integer $0<t<|A|$, I want to maximize the number of intersections with cardinality at least $t$. Is it true that the optimal set $A$ is $\{0,1,\ldots,|A|-1\}$?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
This is not true without some extra assumptions even in the simplest case where $l=2$ and $t=1$.
In this case you count pairs $(k_1,k_2)\in[0,k-1]^2$ with $(A+k_1)\cap(A+k_2)\ne\varnothing$; that is, with $k_1-k_2\in A-A$. Consider, for instance, the situation where $n:=|A|\approx 2k^{1/2}$. If $A$ is a block of $n$ consecutive integers, then for $k_1-k_2\in A-A$ to hold you need $|k_1-k_2|<n$, and there are fewer than $2nk\approx 4k^{3/2}$ pairs $(k_1,k_2)$ with this property. At the same time, if instead you choose $A$ to have $[-k,k]\subseteq A-A$ (which is possible in view of the assumption $n:=|A|\approx 2k^{1/2}$), then all $k^2$ possible pairs $(k_1,k_2)$ will satisfy $k_1-k_2\in A-A$.
