7
$\begingroup$

We use the standard definition of natural density. We say a subset of $\mathbb N$ has full natural density if it has natural density $1$.

Question: Does every subset of the naturals with full natural density contain arbitrarily long geometric progressions?

Comments: Note that there are subsets of $\mathbb N$ with nonzero natural density that do not contain arbitrarily long geometric progressions. Indeed, the set of square-free integers has natural density $\frac{6}{\pi^2}$, but does not contain any three term geometric progression.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I'm unsure about the density version, but if the natural numbers are colored with a finite number $c$ of colors then there are arbitrarily long monochromatic geometric progressions: Take a desired length $n$, and apply the Hales–Jewett theorem on $n, c$ to obtain $H$. Now consider the set $S = \{ p_1^{i_1} p_2^{i_2} \cdots p_H ^{i_H} \mid \forall j, 1 \le i_j \le n \}$. Note that it is isomorphic to the $H$ dimensional $n \times n \times \cdots \times n$ hypercube, and a monochromatic line in the hypercube gives a monochromatic geometric progression of length $n$ in $S$. $\endgroup$
    – Daniel Weber
    Commented Oct 30 at 4:44
  • $\begingroup$ (cont.) This doesn't translate to the density version of the Hales–Jewett theorem because, as demonstrated by the square-free example, density in $\mathbb{N}$ doesn't imply density in sets like $\{ p_1^{i_1} p_2^{i_2} \cdots p_H ^{i_H} \mid \forall j, 1 \le i_j \le n \}$ $\endgroup$
    – Daniel Weber
    Commented Oct 30 at 4:45
  • $\begingroup$ @DanielWeber That is actually quite surprising. So it seems like colouring is quite a bit stronger than simply having sets with prescribed natural/upper density. $\endgroup$
    – Nate River
    Commented Oct 30 at 4:47
  • 1
    $\begingroup$ @Daniel yes realized that so deleted my comment - thanks for pointing it out; always the difference between infinite and arbitrarily large is something to consider carefully! $\endgroup$
    – Conrad
    Commented Oct 30 at 4:47

2 Answers 2

Reset to default
14
$\begingroup$

Assume that $S\subset\mathbb{N}$ has density $1$. Then, for any $m\in\mathbb{N}$, the density of $S\cap m\mathbb{N}$ is $1/m$, hence the density of $\mathbb{N}\cap m^{-1}S$ is $1$. It follows that for any $m_1,\dotsc,m_k\in\mathbb{N}$, the density of $\mathbb{N}\cap m_1^{-1}S\cap\dotsb\cap m_k^{-1}S$ is $1$. In particular, there exists $n\in\mathbb{N}$ such that $nm_1,\dotsc,nm_k\in S$. So any finite progression in $\mathbb{N}$ has a scaled version lying in $S$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Very nicely argued… $\endgroup$
    – Nate River
    Commented Oct 30 at 5:10
8
$\begingroup$

GH has already given an excellent qualitative answer, but for those interested in background and the quantitative aspects:

Rankin was (I believe) the first to consider the density of sets without $k$-term geometric progressions. There has been some work on this - see for example the paper 'On sequences without geometric progressions' (Integers 13 (2013), Paper No. A73) by Nathanson and O'Bryant for some further references.

To answer the initial question, there is a nice short argument due to Brown and Gordon (On sequences without geometric progressions, Mathematics of Computation, 1996) that proves that if $A$ has upper density $>1-2^{-k}$ then it contains a geometric progression of length $k$:

Suppose $A$ has no geometric progression of length $k$ and let $N$ be large. If $a<N/2^{k-1}$ is an odd number then at least one of $\{a,2a,\ldots,2^{k-1}a\}$ is missing from $A\cap \{1,\ldots,N\}$. There are $N/2^k$ many different such $a$, and each set is disjoint for different choices of $a$, and hence there are at least $N/2^k$ integers missing from $A\cap \{1,\ldots,N\}$ - therefore $\lvert A\cap [1,N]\rvert/N \leq 1-2^{-k}$.

Brown and Gordon also note that, as $k\to \infty$, the optimal density for a set without a $k$-term geometric progression converges to $1-2^{-k}$.

For fixed small $k$ there have been some improvements - most recently in the above paper of Nathanson and O'Bryant, who proved that if $A\subseteq \mathbb{N}$ has upper density $$ > 1-\frac{1}{2^k-1}-\frac{2}{5}\left(\frac{1}{5^{k-1}}-\frac{1}{6^{k-1}}\right)-\frac{4}{15}\left(\frac{1}{7^{k-1}}-\frac{1}{10^{k-1}}\right)$$ then $A$ contains a non-trivial geometric progression of length $k$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It is always a mystery to me how bounds like the last displayed one are obtained. Additive combinatorics is a fascinating field. $\endgroup$
    – Nate River
    Commented Oct 31 at 5:29

You must log in to answer this question.

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