Erdos Conjecture on arithmetic progressions

I've never much liked Erdős's conjecture. Of course, I don't mean by that that I wouldn't love to solve it, or that I wouldn't be fascinated to know the answer. However, I think the precise form in which it is stated, with sums of reciprocals, gives it a mystique it doesn't quite deserve. The real question, it seems to me, is this: how large a subset of {1,2,...,n} can you have if it is to contain no arithmetic progression of length k? Erdős's conjecture is roughly equivalent to the statement that the best density you can get is no more than n/logn. (I won't bother to say what I mean by "roughly equivalent", but if you think about it you will see that a set with reasonably smoothly decreasing density can get up to a little bit less than n/logn before the sum of its reciprocals starts to diverge.)

Now there doesn't seem to be a strong heuristic argument that the right bound for this problem is about n/logn. Indeed, many people think that it is probably quite a lot lower than that. So there is something a bit arbitrary about Erdős's conjecture: it has a memorable statement, but there is no particular reason to think that it is a natural statement in the context of this problem. By contrast, if you ask what the correct density is in order to guarantee a progression of length k, then it's trivially a natural question, since it is asking for the best possible bound.

One could perhaps defend the conjecture as being the weakest neat conjecture of its kind that would imply that the primes contain arbitrarily long arithmetic progressions. And that would still be an extremely interesting consequence of a proof of the conjecture (or rather, the fact that there could be a purely combinatorial proof of the Green-Tao theorem would be an extremely interesting consequence).

For those interested, here is the most elementary proof that sets of the natural numbers of positive upper density necessarily have divergent reciprocal sums, r.e. Pete's discussion above.

Suppose $A \subset \mathbf{N}$ and $\displaystyle\limsup_{N \to \infty} \frac{|A\cap [1,N]|}{N} = \alpha > 0$.

Let $N_0=1$, and choose a sequence $N_k$ such that $N_k \geq \frac{4N_{k-1}}{\alpha}$ and $|A \cap [1,N_k)| \geq \frac{\alpha}{2}N_k$ for all $k \in \mathbf{N}$. $$\sum_{n \in A}\frac{1}{n}= \sum_{k=1}^{\infty}\sum_{n \in A\cap [N_{k-1},N_k)}\frac{1}{n} \geq \sum_{k=1}^{\infty}(|A\cap [1,N_k)|-N_{k-1})\frac{1}{N_k}$$ $$ \geq \sum_{k=1}^{\infty}(\frac{\alpha}{2}N_k - \frac{\alpha}{4}N_k) \frac{1}{N_k}=\sum_{k=1}^{\infty}\frac{\alpha}{4} \to \infty.$$ This is really just a generalization of the classical proof of the divergence of the harmonic series, where you group together progressively larger collections of consecutive terms that add to at least one-half. Hope this helps!

There is a way you can recast Erdős conjecture into a statement about certain inclusions among various compact left and two-sided ideals. Such topological-algebraic statements, and a few combinatorial statements, are proved by Neil Hindman in

"Some Equivalents of the Erdős Sum of Reciprocals Conjecture." European Journal of Combinatorics (1988) 9, no. 1, 39 -- 47.

Here is a brief sample of one of these topological-algebraic statements. Let $\beta\mathbb{N}$ denote the Stone-Čech compactification of the discrete space $\mathbb{N}$. We can extend the usual addition and multiplication operations on $\mathbb{N}$ to $\beta\mathbb{N}$ to make $(\beta\mathbb{N}, +)$ and $(\beta\mathbb{N}, \cdot)$ both into compact right-topological semigroups. (Right topological semigroup means that $(\beta\mathbb{N}, +)$ and $(\beta\mathbb{N}, \cdot)$ are both semigroups and for all $p$, $q \in \beta\mathbb{N}$ the maps $p \mapsto p+q$ and $p \mapsto p\cdot q$ are continuous.) To see how to actually perform this extension you can read section 3, pgs. 23-28, of this pdf document by Vitaly Bergelson. (However, Bergelson's construction makes $(\beta\mathbb{N}, +)$ into a compact left-topological semigroup.)

Let $L \subseteq \beta\mathbb{N}$. We say $L$ is a left ideal of $(\beta\mathbb{N}, +)$ if $L$ is nonempty and $\beta\mathbb{N} + L \subseteq L$. We define a right ideal of $(\beta\mathbb{N}, +)$ dually, and a (two-sided) ideal is both a left and right ideal. We define left, right, and two-sided ideals of $(\beta\mathbb{N}, \cdot)$ by simply replacing "$+$" with "$\cdot$" above.

Now define the following two subsets of $\beta\mathbb{N}$:

• $\mathcal{AP} = \{p \in \beta\mathbb{N} : A \hbox{ contains APs of arbitrary length for all } A \in p \}$
• $\mathcal{D} = \{p \in \beta\mathbb{N} : \sum_{n\in A} 1/n = \infty \hbox{ for all } A \in p\}$

It's known that $\mathcal{AP}$ is a compact two-sided ideal of $(\beta\mathbb{N}, +)$ and $(\beta\mathbb{N}, \cdot)$, and that $\mathcal{D}$ is a compact left ideal of $(\beta\mathbb{N}, +)$ and $(\beta\mathbb{N}, \cdot)$. Therefore (part of) the main result of Hindman's paper is the

Theorem. The following statements are equivalent.

(a) If $A\subseteq \mathbb{N}$ and $\sum_{n \in A} 1/n = \infty$, then A contains APs of arbitrary length.

(b) $\mathcal{D} \subseteq \mathcal{AP}$.

Of course the point here is that since $\mathcal{D}$ is a left ideal and $\mathcal{AP}$ is a two-sided ideal you would hope to have some nice theorems about inclusion relationships among various compact left, right, and two-sided ideals in $\beta\mathbb{N}$ to lean on. As far as I know, no one has attempted to attack Erdős conjecture from this topological-algebraic viewpoint.

Just to further illustrate the difficulties involved, let me mention that currently there is not even a "purely" topological-algebraic proof of Szemerédi's Theorem yet!

Let $\Delta = \{p \in \beta\mathbb{N} : \overline{d}(A) > 0 \hbox{ for all } A \in p\}$ and let $\Delta^* = \{p \in \beta\mathbb{N} : d^*(A) > 0 \hbox{ for all } A \in p\}$. Here $\overline{d}$ and $d^*$ are the upper asymptotic density and Banach Density. It's known that $\Delta$ is a compact left ideal of $(\beta\mathbb{N},+)$, and $\Delta^*$ is a compact two-sided ideal of $(\beta\mathbb{N}, +)$ and a compact left ideal of $(\beta\mathbb{N}, \cdot)$. In the above paper, Hindman shows that Szemerédi's Theorem is equivalent to each of the inclusions $\Delta \subseteq \mathcal{AP}$ and $\Delta^* \subseteq \mathcal{AP}$.

However, one possible approach to show Szemerédi's Theorem in a topological-algebraic "way" was shown not to work in the paper "Subprincipal Closed Ideals in $\beta\mathbb{N}$" by Dennis Davenport and Hindman. In this paper, they show that $\Delta^*$ intersects every closed ideal of $(\beta\mathbb{N},+)$; but, beyond that, not enough is known about inclusions among compact ideals to prove, algebraically, that $\Delta^* \subseteq \mathcal{AP}$.