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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

Improve this answer
$\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$ 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$ 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.