2
$\begingroup$

I have exactly the same problem as this person, which I will rewrite below:Topology and Arithmetic Progressions. The reason I'm posting this is that I'm stuck at a later stage than the OP of that post. So here's the problem:

Consider the following property of a subset $F$ of the set $ℕ$ of positive integers: there is $n ∈ ℕ$ such that $F$ contains no arithmetic progressions (APs) of length $n$. Prove that subsets with this property together with the whole $ℕ$ form a collection of closed subsets in some topology on $ℕ$.

You may need van der Waerden's theorem: For any $n \in \mathbb{N}$ there exists $N \in \mathbb{N}$ such that for all $A \subset \{1, \cdots, N\}$ either $A$ contains an arithmetic progression of length $n$ or $\{1, \cdots, N \} \setminus A$ contains an arithmetic progression of length $n$.

Here is my attempt:

It suffices to show that the subsets with the given property are closed under arbitrary intersection and finite union. For finite intersection, suppose that $\cap_i A_i$ is an intersection of sets with the given property. For every $i$, the set $A_i$ has an associated $n_i$ such that $A_i$ contains no APs of length $n_i$. Consider $n = min(n_i)$, we show that $\cap_i A_i$ does not contain APs of the length $n$. If it did, any such AP would be an AP for the set $A_i$ that corresponds to $n$, a contradiction. For finite union, by induction it suffices to show that the subsets are closed under binary unions.

For this suppose that $f_1$ and $f_2$ are subsets of $\mathbb{N}$ with the aforementioned property. Then we have associated $n_1, n_2 \in \mathbb{N}$ such that $f_1$ does not contain APs of length $n_1$ and ditto for $f_2$ and $n_2$. We choose $n = max(n_1, n_2)$. Without loss of generality we can assume $max(n_1,n_2) = n_1$, since the other case can be argued symetricallly. Suppose that $f_1 \cup f_2$ contained an AP of length $n$. This AP would have the form $\{a + (i - 1)d \ | \ i \in \{1, \cdots, n\} \}$ for some $a, d \in \mathbb{N}$. The indicies $i$ can be put into two sets $f_1'$ and $f_2'$ with the following two properties: Firstly, both $f_1'$ and $f_2'$ are subsets of $\{1, \cdots, n\}$, and we have $f_1' \cup f_2' = \{1, \cdots n\}$. Secondly, $f_1'$ is in bijection with $f_1$, where the forward map sends $i$ to its corresponding element of the AP namely $a + (n - 1)d$, and the same for $f_2'$ and $f_2'$. By van der Waerden's applied to $n$, there exists a $N \geq n$ such that either $f_1'$ contains an AP of length $n$, or $\{1, \cdots, N\}$ contains an arithmetic progression of length $n$. However the former case is impossible since $n = n_1$, so the AP in $f_1'$ would map to an AP in $f_1$ of length $n_1$ and we are given that this is not the case. So it suffices to consider the case where $\{1, \cdots, N\} \setminus f_1'$ contains an arithmetic progression of length $n$.

Here is where I'm stuck. How do I complete the proof? Hints are preferred to answers.

$\endgroup$

2 Answers 2

2
$\begingroup$

HINT: I would approach the union a bit differently. Let $f=f_1\cup f_2$, and suppose that $f$ is not closed; then it contains arbitrarily long arithmetic progressions. Suppose that $$\{a+kd:k=0,\ldots,\ell\}$$ is an arithmetic progession in $f$, where $\ell$ has yet to be determined (and remember that we can take $\ell$ to be as large as we want. Let $$I_1=\big\{k\in\{0,\ldots,\ell\}:a+kd\in f_1\big\}\;,$$ and let $I_2=\{0,\ldots,\ell\}\setminus I_1$. Show that if $I_1$ (I_2, respectively) contains an arithmetic progression of length $m$, then so does $f_1$ ($f_2$, respectively). Then use van der Waerden’s theorem to choose $\ell$ appropriately.

$\endgroup$
3
  • $\begingroup$ Dear @Brian M. Scott, could you please check if I finished the proof correctly: mathb.in/42134. $\endgroup$ Sep 1, 2015 at 12:53
  • $\begingroup$ I fixed a typo in the statement of van der Waerden's lemma: mathb.in/42136. $\endgroup$ Sep 1, 2015 at 13:24
  • $\begingroup$ Clarification of an assumption I made, mathb.in/42137. $\endgroup$ Sep 1, 2015 at 13:37
0
$\begingroup$

If $F, G$ both have this property then take $n = n_F + n_G$, then $F\cup G$ has no arithmetic progressions of length $n$. Proof: if it did then it would need an arithmetic progression of length $m \geq n_G$ in $G$ or one of length $m \geq n_F$ in $F$, which is impossible. Think of gluing together finite arithmetic progressions to see this. Thus the subsets with this property are closed under finite union.

Now if $F = \bigcap_i F_i$, let $F_i$ be a subset with no arithmetic progressions of length $n_i$. Then take $n = \min_i\{n_i\}$ which exists for any set of natural numbers. $F$ has no arithmetic progressions of length $n$ since it's the subset of such a set. QED.

Clearly $\varnothing$ is such a set. Add in the whole space $\Bbb{N}$ artificially, and you then have a topology.

$\endgroup$

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.