10
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – GH from MO
    Jun 22, 2014 at 22:56
  • 2
    $\begingroup$ 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). $\endgroup$
    – GH from MO
    Jun 22, 2014 at 23:35
  • $\begingroup$ Now we have two more elementary arguments, one by The Masked Avenger, and a more explicit version by Lucia. $\endgroup$
    – GH from MO
    Jun 23, 2014 at 8:41
  • $\begingroup$ 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. $\endgroup$
    – GH from MO
    Jun 23, 2014 at 10:11
  • $\begingroup$ 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! $\endgroup$
    – GH from MO
    Jun 23, 2014 at 18:07

4 Answers 4

16
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – shadow10
    Jun 22, 2014 at 16:11
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 22, 2014 at 16:17
  • 2
    $\begingroup$ 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. $\endgroup$
    – GH from MO
    Jun 22, 2014 at 23:04
  • 1
    $\begingroup$ @GHfromMO, noted. I hope the edit to follow satisfies you. $\endgroup$ Jun 23, 2014 at 5:40
13
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – shadow10
    Jun 22, 2014 at 15:41
  • 2
    $\begingroup$ Actually, the Evertse, Schmidt and Schlikewei result is not needed and an older result of Siegel and Mahler is enough. mathoverflow.net/questions/87364/… $\endgroup$ Jun 22, 2014 at 15:48
6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Jun 23, 2014 at 6:17
  • $\begingroup$ Nice explicit argument. $\endgroup$
    – GH from MO
    Jun 23, 2014 at 8:40
  • $\begingroup$ @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. $\endgroup$
    – shadow10
    Jun 23, 2014 at 12:40
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Lucia
    Jun 23, 2014 at 12:48
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 23, 2014 at 17:42
3
$\begingroup$

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.

$\endgroup$
10
  • 2
    $\begingroup$ 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)}$. $\endgroup$
    – Lucia
    Jun 23, 2014 at 13:13
  • 1
    $\begingroup$ @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. $\endgroup$
    – GH from MO
    Jun 23, 2014 at 14:32
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Lucia
    Jun 23, 2014 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 23, 2014 at 15:46
  • 2
    $\begingroup$ @GHfromMO: See for example this paper by H. Stevens: gdz.sub.uni-goettingen.de/dms/load/img/… $\endgroup$
    – Lucia
    Jun 23, 2014 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.