1

Suppose we have two finite sets $A,B\subset\mathbb Z$. I am interested in an upper bound on the number of translations of $B$ by integers that have nonzero intersections with $A$ i.e. $$T(A,B):=\lvert\{k\in\mathbb Z~|~A\cap(B+k)\not=\emptyset\}\lvert.$$

One obviously has $T(A,B)\leq\text{diam}(A)+\text{diam}(B)-1$ where diam denotes the diameter of a set. I was wondering: What is a good bound on $T(A,B)$ in terms of $\lvert A\lvert$ and $\lvert B\lvert$?

Andrés E. Caicedo
  • 79,201
Dominik
  • 434
  • 2
  • 11

1 Answers1

0

It is clear that $T(A,B)\le |A||B|$.

And this upper bound is achievable. Let $B=\{1,2,3,\dots,b\}$. Let $A$ be a set of $a$ elements such that the distance between any two elements of $A$ is greater than $b$. Then $T(A,B)=ab$.

André Nicolas
  • 507,029