Let ${\mathbb N}$ denote the set of positive integers, let $A,B\subseteq \mathbb{N}$. For $n\in\mathbb{N}$ we set $n+A:=\{n+a: a\in A\}$. We say that $A$ is infinitely often in $B$ if the set $$\big\{n\in\mathbb{N}:(n+A)\subseteq B\big\}$$ is infinite. Moreover, for any $S\subseteq {\mathbb N}$ we set $\mu(S) = \lim \inf_{n\to\infty}\frac{|S\cap\{1,\ldots,n\}|}{n}.$

Question. If $B\subseteq \mathbb{N}$ and $\mu(B) > 0$, does the following statement always hold?

(S): For any $n\in \mathbb{N}$ there is $A\subseteq \mathbb{N}$ with $|A|=n$ and $A$ is infinitely often in $B$.

If not, is there a positive $r\in\mathbb{R}$ with $r<1$ such that whenever $B\subseteq \mathbb{N}$ has the property that $\mu(B)\geq r$ then (S) holds? (I will accept answers of the first question, but if it is negative, I would be interested in remarks concerning the latter question.)


1 Answer 1


Unless I'm missing something, the answer is yes (even if you replace "inf" with "sup").

I'm going to switch from sets to binary sequences for simplicity. We define $\mu(B)$ for an infinite binary sequence $B$ as $\mu(\{n: B(n)=1\})$. Fix $n\in\mathbb{N}$ and $B$ an infinite binary string with $\mu(B)=\epsilon>0$. In order to have $\mu(B)=\epsilon$ we must have for each $m$ that strings of length $m$ and with at least $\epsilon m$-many $1$s must occur infinitely often in the characteristic function of $B$. But there are only finitely many such strings, so one occurs infinitely often. Now take $m$ large enough that $\epsilon m>n$, and think about the corresponding string $\sigma$ - this is a finite binary string which occurs infinitely often in $B$ and has at least $n$-many $1$s.

Put another way, given a set $B$ with $\mu(B)>0$ and natural number $n$, there is a finite binary sequence $\sigma$ occurring containing at least $n$-many $1$s and occurring infinitely often in the characteristic function of $B$. WLOG $\sigma$ contains exactly $n$-many $1$s (otherwise, truncate appropriately). Now the set $$\{x: \sigma(x)=1\}$$ is the desired $A$.

  • $\begingroup$ In the third paragraph you first write $\mu(B)=\epsilon$, and immediately after $\mu(B)>\epsilon$. I think you want the first equality to be an inequality as well. $\endgroup$
    – Wojowu
    Jan 8, 2019 at 15:50
  • $\begingroup$ @Wojowu Yeah, I caught that at the same time. $\endgroup$ Jan 8, 2019 at 15:53
  • $\begingroup$ Beautiful @NoahSchweber - and lightning fast! $\endgroup$ Jan 8, 2019 at 15:54
  • 3
    $\begingroup$ Not a fascinating remark, but the proof also holds with a limsup in the definition of $\mu$. $\endgroup$
    – Pierre PC
    Jan 8, 2019 at 16:34
  • 2
    $\begingroup$ @PierrePC Indeed, and that's actually how I (mis)read the question. :P $\endgroup$ Jan 8, 2019 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.