Erdos Conjecture on arithmetic progressions

Question

Introduction:

Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.

Question:

I was wondering how one might go about categorizing or generating the divergent series of the form in the introduction above. I'm interested in some particular techniques and I list some examples below:

If we let $S$ be the set of such divergent series: $S=\left[ A: \sum_{n\in A}\frac{1}{n}=\infty, \ A\in\mathbb{N} \right]$, what kind of operations are there that would make S a group, or at the very least a semigroup? I'm rather vague on what the operatons should be for a reason, because although I presume trivial operations exist, their usefulness in understanding the members of $S$ would be questionable.

Alternately, can one look at these divergent sums through the technique of Ramanujan summation (think: $1+2+3+\ldots =^R -\frac{1}{12}$, $R$ emphasizing Ramanujan summation)? The generalizations of Ramanujan summation (a good reference here ) allow one to assign values to some of these series and give some measure of what kind of divergence is occurring. Moreover, basic series manipulations that hold for convergent series tend to carry over to Ramanujan summation, so can one perhaps look at the set $S$ above as a set of equivalence classes in the sense of two elements being equivalent if they share the same Ramanujan summation constant.

Thanks in advance for any input!

Answer 1

Most of the point of this answer is to promote a piece of terminology:

Three years ago I first taught a number theory course at UGA in which I made the following definition: a subset $A$ of the positive integers is substantial if

$\sum_{n \in A} \frac{1}{n} = \infty$.

A little bit of discussion of this concept occurs in Section 4 of

http://alpha.math.uga.edu/~pete/4400primes.pdf

I do mention the Erdos(-Turan?) conjecture about arithmetic progressions in substantial sets. For the purpose of constructing examples, possibly the remark I make about any set with positive upper density being substantial will be of most use to you.

Those notes don't contain a proof of that, but a proof of this and more can be found in a very (very!) nice final project done in this class by (then) undergraduate Alex Rice. Sadly he never gave me an electronic copy in a form that I was able to upload to my webpage. If you want to see his writeup, let me know and I'll bug him about this again: the winds of fate have blown him around a bit, but he is now again a UGA (graduate) student taking a number theory course from me.

Finally, to answer one of your questions in a cheap way: yes, the set of substantial subsets of $\mathbb{Z}^+$ certainly forms a semigroup under union. This seems like a completely unhelpful observation, but who knows...

Answer 2

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

Answer 3

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!

Answer 4

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

Answer 5

An idea that I came up with is that if the conjecture is true, then there would be a finite upper bound on how big the sum could be if the set had no arithmetic progression of length k, lets call this upper bound f(k). Obviously f(1)=0, as if there are any members then there is an arithmetic progression of that length. f(2)=1 (using the set {1}), as adding more numbers would result in an arithmetic progression of length two or more. I am currently working on f(3)