## Hot answers tagged arithmetic-progression

99

The Green-Tao is true for any subset of the primes of positive relative density; the primes in a fixed arithmetic progression to modulus $d$ have relative density $1/\phi(d)$.

29

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

29

The answer is yes. Here is another example,
$$
x=2021231^2, \qquad d=82153503191760.
$$
Then
$$
x+d=9286489^2, \qquad
x+2d=12976609^2, \qquad
x+4d=18240049^2.
$$
Basically, write $x=X^2$, $x+d=Y^2$, $x+2d=Z^2$, and $x+4d=W^2$. Eliminating $x$ and $d$ reduces to the two equations:
$$
X^2-2Y^2+Z^2=0, \qquad
3X^2-4Y^2+W^2=0.
$$
This pair of equations defines a ...

23

It is a theorem of Ben Green that every subset of the primes of positive relative density contains a progression of length three. As an immediate consequence, the set of primes $A$ which are not the first term in a progression of primes of length three has density zero (otherwise $A$ would contain a length three progression, a contradiction).
Ben's proof ...

23

Yes, this can be done, provided that k is at least 3. A typical example is given in this paper: http://arxiv.org/abs/math/0701240 . (This uses a slightly older Fourier-based method of Ben that predates his work with me, but is definitely in the same spirit - Ben's paper was very inspirational for our joint work.)
For k=2, unfortunately, the type of ...

22

Probably not, but a proof is hopeless. Ruzsa and Gyarmati have a preprint in which they construct such a subset of size something like $N/\log \log N$.
Even the colouring version (that is, finite colour the squares, does one of the classes contain a 3-term progression) is open. A very closely-related question (Schur's theorem in the squares) is explicitly ...

19

This question is extremely close to this one
Covering the primes by 3-term APs ?
though not exactly the same.
For much the same reasons as described in the answer given there, the answer to your question is almost certainly yes, but a proof is beyond current technology, exactly as you suggest. I'm not aware that the problem has a specific name.
To show ...

19

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

15

Dear Yui,
It's only slightly more than a casual remark. Our inability to find a better example is certainly a big reason for believing that Behrend's bound is correct. Julia Wolf and I slightly rehashed the proof of Behrend's bound
http://arxiv.org/abs/0810.0732
When formulated this way, I think the construction looks both fairly natural and fairly ...

14

Starting from the equations in my previous answer, we get, by multiplying them in pairs,
$$(x-y)x(x+y)(x+2y) + (x-y)x + (x+y)(x+2y) + 1 = (z_1 z_6)^2\,,$$
$$(x-y)x(x+y)(x+2y) + (x-y)(x+y) + x(x+2y) + 1 = (z_2 z_5)^2\,,$$
$$(x-y)x(x+y)(x+2y) + (x-y)(x+2y) + x(x+y) + 1 = (z_3 z_4)^2\,.$$
Write $u = z_1 z_6$, $v = z_2 z_5$, $w = z_3 z_4$ and take differences to ...

13

Well, any standard upper bound sieve (e.g. Selberg sieve, combinatorial sieve, beta sieve, etc.) will give this type of result. I'm not sure where you can find an easily citeable formulation, though. One can get this bound from Theorem D.3 of this paper of Ben and myself on page 67 (see in particular the remark at the bottom of that page). But this is ...

13

It is firmly expected that for every \epsilon > 0 each aritmetic progression with difference q and terms coprime with q will contain a prime <<{\epsilon} q^{1 + \epsilon}.
This is a direct consequence of a conjecture of H. L. Montgomery (not the one on pair correlations, another one), which implies both the GRH and the Elliott-Halberstam conjecture. ...

13

This was one of my favourite problems in high school. My proof went like this: if you look at the problem modulo n where n is the least common multiple of the differences of the arithmetic progressions then you can rephrase the problem as follows: if the vertices of a regular n-gon are partitioned into regular k-gons centered at the origin then two of them ...

13

The question whether there are infinitely many primes in some coprime residue class mod m
is stronger than asking whether there are infinitely many primes with given inertia index in the field of mth roots of unity, which is a special case of Chebotarev's density. The possibility of elementary proofs of the latter was discussed, as you know, over
here.
It ...

13

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

13

It is well-known that not only does the arithmetic progression $\{ak+b\}_{k \in \mathbb{Z}^{+}}$ contain infinitely many prime numbers, but also that the series of the reciprocals of those primes diverges. The answer to the OP's question can be obtained now from the following general result:
If $\{a_{i}\}_{i \in \mathbb{N}}$ is a strictly increasing ...

12

When $a=2$, the sum you want the asymptotics of is basically
$$
\frac12 \frac{\log n}n \sum_{p\le n} \frac{\phi(p-1)}{p-1} \sim \frac12 \frac1{\pi(n)} \sum_{p\le n} \frac{\phi(p-1)}{p-1},
$$
which is half the average value of the multiplicative function $\phi(n)/n$ on shifted primes $p-1$. The heuristic for evaluating this constant is as follows: recall that
...

12

Edit: {The answer to your question, "...do we already know that a positive binary form represents arbitrarily long arithmetic progressions?" is yes. See the second paragraph below.}
If the relative density exists, so does the Dirichlet density and they are equal. The converse is not true in general. For primes in a given arithmetic progression, both ...

11

Assign to each progression $A_i=(a_i+kb_i\mid k\in{\mathbb N})$, $1\le i\le n$, its generating series, $f_i(x)=\sum_{k=0}^\infty x^{a_i+kb_i}$. Then $f_i(x)=x^{a_i}/(1-x^{b_i})$. Note the series converges for $|x|<1$.
Now, since the $A_i$ partition ${\mathbb N}$, we have $\sum_{i=1}^n f_i(x)=1/(1-x)$. If all the $b_i$ are different, let $b$ be the ...

11

With your corrected question you are asking, in a strange way, for the number of arithmetic progressions of length 3 in A. There is a well-known example of Behrend of a set of size $n/\exp(c\sqrt{\log n})$ that contains no non-degenerate APs of length 3. So the answer to your question is no.
Edit: now that you have rephrased your question explicitly to be ...

11

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

11

Odd. There is an article about this in the October M.A.A. Monthly, pages 737-742, by R. Thangadurai and A. Vatwani. They give an elementary argument to show
$$ p \leq 2^{\phi(q) + 1} - 1.$$ The best unconditional result they report is T. Xylouris (2009),
$$ p \leq c_1 q^{5.2}$$ which improves a 1992 result of Heath-Brown.
Apparently Oesterle showed that ...

11

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

11

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.

11

Or just take all powers of $3$ and add to them all numbers that are congruent to $1$ modulo $3$.

11

As Felipe notes, the main term should be li(x)/\phi(q). Replacing this in your definition of $E(x,a,q)$ above we have that, the best that is know even on the GRH is that $E(x,a,q) = O(x^{1/2}\log x)$. This estimate doesn't get better when $q$ is large (compared to $x$) and a lot more is believed to be true. For instance Montgomery conjectures that $E(x,a,q) ...

10

You are essentially asking for quantitative estimates on Szemerédi's theorem, which states that the largest subset of $[1,n]$ without a k-term arithmetic progression has size $o(n)$. To be precise, let us define $r_k(n)$ to be the largest subset of [1,n] with no k-term arithmetic progression. Then a construction due to Behrend (essentially projecting a ...

10

Despite the comments to the question (including mine), this is a bit easier than it seems at first sight. We can show that $L_{\max}=2$ or $3$. Almost certainly we have $L_\max=3$. However, determining which of these is actually the case seems to be beyond current technology, according to this MO answer "Are all primes in a PAP-3?".
Showing that, $L_{\max} ...

10

A good way to find the result you mentioned is to search for Dirichlet's (prime number) theorem; while Dirichlet only proved the infinitude of the set in question, nowadays one will frequently find the more precise assertion you mentioned when this result is discussed.
A more common way to state it is that the number of primes congruent to $m$ modulo $n$ ...

10

You're probably thinking of the proof, via generating functions, due to D J Newman. I don't have a reference to the first appearance in print, but it's in his book, A Problem Seminar, problem 90, on page 18, with solution on page 100.
I suppose that when you state the problem you must require finitely many but at least two arithmetic progressions.

Only top voted, non community-wiki answers of a minimum length are eligible