# Arbitrarily long arithmetic progressions

Are there arbitrarily long arithmetic progressions in which all the prime factors of all the terms are at most $N$, for some $N$? Assume all the terms are positive and the sequence of terms is increasing.

I have proved that no such infinite sequence exists. Note the $N$ may vary from AP to AP. For infinite sequences let $\{a+nd\}_{n\ge 0}$ be the AP. $\text{gcd}(a,d)=s$ then $a+nd=s(x+ny)$ for some $x,y$ with $\text{gcd}(x,y)=1$ then by Dirichlet's theorem $\{x+ny\}_{n\ge 0}$ has infinitely many primes. Thus we have the prime factors of the sequence is unbounded and hence done. But I was thinking about this claim but nothing came in mind. Could someone help? Thanks a lot.

• Your proof, based on Dirichlet's theorem, only shows that no infinite arithmetic progression exists with all the terms supported on primes at most $N$. This statement has a simpler proof by noting that the reciprocal sum of any infinite arithmetic progression diverges, while the reciprocal sum of the numbers supported on primes at most $N$ equals $\prod_{p\leq N}(1-1/p)^{-1}$. I don't see how to extend these proofs from infinite arithmetic progressions to arbitrary long ones. Jun 22 '14 at 22:56
• I think that Felipe Voloch's answer is the only correct argument so far that settles the original question. A good reference for the underlying Siegel-Mahler theorem is Lang's paper available at numdam.org/numdam-bin/fitem?id=PMIHES_1960__6__27_0 (see top of page 28 there). Jun 22 '14 at 23:35
• Now we have two more elementary arguments, one by The Masked Avenger, and a more explicit version by Lucia. Jun 23 '14 at 8:41
• I just gave an elementary argument (a supplement to the ones given already) that for any $k$ there is $m$ such that no arithmetic progression of length $m$ is supported on $k$ distinct primes. Jun 23 '14 at 10:11
• In fact Lucia's argument combined with Iwaniec's bound on Jacobsthal's function yields $m\ll k^2(\log k)^2$. Thanks to Lucia and The Masked Avenger for their arguments and comments! Jun 23 '14 at 18:07

A simple proof is available as well. Pick p coprime to d and let t be such that td=1 mod p. Then, mod p, t times the arithmetic progression looks like a sequence of consecutive integers. Thus its length has to be less than p to avoid one of the terms being a multiple of p, which means the original progression also has to have fewer than p terms. So the collection of primes dividing a set of arbitrarily long arithmetic progressions must be infinite.

It has been noted by GH from MO that the above overlooks some subtleties; the following is more inspired by Euclid, and should leave no doubt remaining.

Let A be a set of arbitrarily long nonconstant arithmetic progressions. Thus for any integer m, we can find a member of A and extract from that (wlog) a positive increasing arithmetic progression of the form a +kd where a and d are coprime and k goes from 0 to m. Pick a finite set of primes M, set m equal to a large multiple of their product (so at least twice the product of primes of M) and then choose from A a progression and derive the progression a +kd with the properties above. I will show the existence of a prime divisor which is not in M and divides a member of the progression.

Now d may share some factors with the product of M, but as (a,d)=1, none of the factors of d will divide any of a +kd. To be safe, let us call M' that set of numbers in M which are coprime to d, and set their product to m'. So (m',d)=1, d is a unit mod m', and we can look at ta +tkd as k runs from 1 to m which is bigger than m'. As above, td=1 mod m'.

Modulo m', ta+tkd is ta+k, so ta+k is divisible by a factor of m' precisely when a+kd is. As a result, there are k bigger than m' and at most m such that a+kd is coprime with m'. But a+kd is bigger than m' and is coprime not just to m' but to the product of all primes in M. So it must have a prime factor outside of M. So A "contains" more primes than found in any finite set of prime factors.

Clear enough?

• Thanks this one is nice. And thanks to the other post I got to know about the nice theorem by Evertse, Schmidt and Schlikewei. +1. Jun 22 '14 at 16:11
• I made it simple by ignoring the character of d. But if d has all the primes below p as factors, then one of the first (two or three) terms has a prime factor about as big as p or bigger anyway, so a positive progression of length n should have a term divisible by a prime q at least as big as p, which is the largest prime less than n. Jun 22 '14 at 16:17
• For any arithmetic progression $a,a+d,\dots,a+(m-1)d$ supported on primes at most $N$, you prove that its length $m$ is less than $p$, where $p>N$ is the smallest prime not dividing $d$. How do we get a uniform bound (depending only on $N$) from here? I could not follow your comment above. Jun 22 '14 at 23:04
• @GHfromMO, noted. I hope the edit to follow satisfies you. Jun 23 '14 at 5:40

If $x,y,z$ are in arithmetic progression, then $x+z-2y=0$. By the S-unit theorem of Evertse, Schmidt and Schlikewei, this equation has only finitely many solutions in $x,y,z$ having all its prime factors in a fixed finite set (e.g. all primes at most $N$). So you can't have arbitrarily long arithmetic progressions of numbers of this form.

• Hi, could you cite me a reference for "S-unit theorem of Evertse, Schmidt and Schlikewei", I can't find it on the web. Thanks a lot. Jun 22 '14 at 15:41
• Actually, the Evertse, Schmidt and Schlikewei result is not needed and an older result of Siegel and Mahler is enough. mathoverflow.net/questions/87364/… Jun 22 '14 at 15:48

Here's an elementary proof that the length of an arithmetic progression is bounded in terms of $N$. Put $P= \prod_{p\le N} p$, and let $K$ denote the maximum difference between consecutive reduced residue classes $\pmod P$ (this is the Jacobsthal function). Clearly $K \le P$ (and of course much better bounds are known). Any $K$ consecutive numbers therefore contain one that is coprime to $P$.

Now we claim that any arithmetic progression of $N$-smooth numbers (all larger than $1$) has length at most $K$. Suppose $a+nq$ is such a progression with $a+nq$ being $N$-smooth for all $1\le n\le K$, and with all terms larger than $1$. First note that if $a$ and $q$ have a common factor $\ell$, then the arithmetic progression $a/\ell + nq/\ell$ also consists of $N$-smooth numbers. Thus we may assume that $a$ and $q$ are coprime.

Now suppose that $(q,P)= \ell$. Clearly the numbers $a+qn$ are all coprime to $\ell$ (since $(a,q)=1$). Choose $b$ such that $bq \equiv 1\pmod{P/\ell}$. Then the numbers $b(a+nq)$ when taken $\mod {P/\ell}$ constitute $K$ consecutive residue classes $\pmod{P/\ell}$ and therefore contain one residue class that is coprime to $P/\ell$. Therefore for some $1\le n\le K$ we have $(a+nq,P)=1$. This number $a+nq$ must have a prime factor larger than $N$.

Note: A small technicality was that we assumed that the elements in the progression were all larger than $1$. So there could be a progression of length $K$ if the progression starts with $1$.

• This is a more technical version of what I hoped to convey (which I did not see until after editing my answer). This should convince @GHfromMO if my words do not. Jun 23 '14 at 6:17
• Nice explicit argument. Jun 23 '14 at 8:40
• @Lucia could you emphasize a bit on Jacobsthal Function? I searched for it and got oeis.org/wiki/Jacobsthal_function which defines it somehow differently, I think. Could you please clarify? And I also don't see how $K\ge P$ is obvious. Thanks a lot. Jun 23 '14 at 12:40
• @shadow10: The OEIS article gives the right function. The bound $K\le P$ follows simply because any interval of $P$ integers contains $\phi(P)$ integers coprime to $P$. Jun 23 '14 at 12:48
• @shadow10 , searching for Jacobsthal's function on MathOverflow gives a number of hits as well as references to some recent contributions, epecially Thomas Hagedorn's paper in 2009. Jun 23 '14 at 17:42

This is a supplement to the elementary proofs given by The Masked Avenger and Lucia.

Theorem. For any $k$ there is $m$ such that no arithmetic progression of length $m$ is supported on $k$ distinct primes.

Proof. We prove by induction on $k$. For $k=0$ we can clearly take $m=2$. So let $k\geq 1$ and assume the statement for $k-1$ in place of $k$. That is, there is $m$ such that no arithmetic progression of length $m$ is supported on $k-1$ distinct primes. Consider an arithmetic progression of length $m'$ supported on the $k$ distinct primes $p_1,\dots,p_k$. Without loss of generality, the terms are coprime to the difference $d$. Observe that in any consecutive block of length $m$ in the progression, each prime $p_i$ occurs as a divisor by the induction hypothesis. Hence for $m'\geq m$ we get that $p_i\nmid d$, and for $m'\geq 2m$ we get that $p_i\mid kd$ for some $0<k<2m$. Combining the two statements, we infer that for $m'\geq 2m$ each $p_i$ is less than $2m$. Using Lucia's elementary argument, it follows that $m'<\prod_{p<2m}p<2^{4m}$. That is, for $m':=2^{4m}$ we get a contradiction, proving that no arithmetic progression of length $m'$ is supported on $k$ distinct primes.

Remarks (updated). The modern results on $S$-unit equations mentioned by Felipe Voloch yield an exponential bound on $m$. Lucia's argument combined with Iwaniec's bound on Jacobsthal's function yields directly $m\ll k^2(\log k)^2$, see Demonstratio Math. 11 (1978), 225–231. Weaker versions of this bound admit simple elementary proofs.

• That's a nice extension. Let me note here that my argument gives the bound of $J(n)$ (the Jacobsthal function) for the length of a progression of integers composed only of primes dividing $n$. Now we recall that the Jacobsthal function can be bounded just in terms of $\omega(n)$ (this was Jacobsthal's result, and the best known is Iwaniec's bound of $\omega(n)^{2+o(1)}$. In other words the length of the progression is at most $k^{2+o(1)}$. Jun 23 '14 at 13:13
• @Lucia: I use induction on the existence of $m=m(k)$. My crude argument, based on $J(n)\leq n$, gives that $m(k)<16^{m(k-1)}$, i.e. $m(k)$ is bounded by a tower of height $k$. Your refinement $J(n)\leq\omega(n)^{2+o(1)}$ gives that $m(k)<m(k-1)^{2+o(1)}$, i.e. $m(k)$ is bounded by $2^{(2+o(1))^k}$. The mentioned results on $S$-unit equations yield an exponential bound. Jun 23 '14 at 14:32
• But why not just use my proof. Doesn't it just give the Jacobsthal function as a bound? (And hence $k^{2+o(1)}$ as a uniform bound.) Jun 23 '14 at 14:36
• The arithmetic progression -1,0,1 suggests m=4 for k=0, or at least 3 if 0 is excluded/supports every prime. I like this inductive perspective. Jun 23 '14 at 15:46
• @GHfromMO: See for example this paper by H. Stevens: gdz.sub.uni-goettingen.de/dms/load/img/… Jun 23 '14 at 16:30