Intersections of translates of finite sets of integers

Question

I am searching for a result in the literature that I am sure must be known, but I just fail to find it.

Let us starts with a simple example: Let $A, B\subset \mathbb{Z}$ be a finite sets of integers such that $|A|=|B|=2m+1$ and denote by $I$ the set $\{-m,...,m\}$. I want to show that for all $k,l \geq 0$ we have $$\sum_{|i|\leq k, |j|\leq l}|(A+i)\cap(B+j)|\leq \sum_{|i|\leq k, |j|\leq l}|(I+i)\cap(I+j)|.$$

And, more generally, for any finite collection of sets $A_1,\ldots,A_t$ of the same odd cardinality $2m+1$ and all numbers $i_1,\ldots, i_t\geq 0$ we have $$\sum_{|j_1|\leq i_1,\ldots, |j_t|\leq i_t}|(A_1+j_1)\cap\ldots \cap(A_t+j_t)|\leq \sum_{j_1|\leq i_1,\ldots, |j_t|\leq i_t}|(I+j_1)\cap\ldots \cap(I+j_t)|.$$

Thank you for your attention!

Seva · Accepted Answer · 2015-12-01 13:05:26Z

For the case $t=2$, letting $A_1:=A$, $A_2:=-B$, $A_3:=[-k,k]$, and $A_4:=[-l,l]$, the sum in the left-hand side counts the number of quadruples $(a_1,a_2,a_3,a_4)\in A_1\times A_2\times A_3\times A_4$ with $a_1+a_2+a_3+a_4=0$. It is known that this number is maximized, over all quadruples $(A_1,A_2,A_3,A_4)$ of sets of prescribed odd cardinality, when each set $A_i$ is a block of consecutive integers centered at $0$. This is a partular case of the rearrangement inequalities due to Gabriel, Hardy, and Littlewood; see this paper (particularly Theorem 1) for generalizations, references, and the historical background.

This answers your question in the case where $t=2$. For $t>2$, the inequality you are asking about may well be unknown, and yet it should be possible to prove it using the same approach as in the case $t=2$ (basically, by a smart induction, removing simultaneously elements from the sets $A_i$).

$\begingroup$ Dear Seva, thank you very much - this is most helpful! $\endgroup$

TOM
– TOM

2015-12-03 05:45:15 +00:00
Commented Dec 3, 2015 at 5:45 — TOM
– TOM, Commented Dec 3, 2015 at 5:45

Stack Exchange Network

Intersections of translates of finite sets of integers

1 Answer 1

You must log in to answer this question.

Intersections of translates of finite sets of integers

1 Answer 1

You must log in to answer this question.

Related