# On the “infinitely often in” relation between subsets of $\mathbb{N}$

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

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$$.

• 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. – Wojowu Jan 8 '19 at 15:50
• @Wojowu Yeah, I caught that at the same time. – Noah Schweber Jan 8 '19 at 15:53
• Beautiful @NoahSchweber - and lightning fast! – Dominic van der Zypen Jan 8 '19 at 15:54
• Not a fascinating remark, but the proof also holds with a limsup in the definition of $\mu$. – Pierre PC Jan 8 '19 at 16:34
• @PierrePC Indeed, and that's actually how I (mis)read the question. :P – Noah Schweber Jan 8 '19 at 17:15