5
$\begingroup$

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

$\endgroup$

1 Answer 1

8
$\begingroup$

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

$\endgroup$
7
  • $\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
    Commented Jan 8, 2019 at 15:50
  • $\begingroup$ @Wojowu Yeah, I caught that at the same time. $\endgroup$ Commented Jan 8, 2019 at 15:53
  • $\begingroup$ Beautiful @NoahSchweber - and lightning fast! $\endgroup$ Commented 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
    Commented Jan 8, 2019 at 16:34
  • 2
    $\begingroup$ @PierrePC Indeed, and that's actually how I (mis)read the question. :P $\endgroup$ Commented Jan 8, 2019 at 17:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .