## Hot answers tagged arithmetic-progression

103

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

25

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

24

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

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

18

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

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

15

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

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

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

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

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

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

12

Nice question! I happened to be thinking about some similar things a few weeks ago. Here is what I found:
Cohen and random reals:
Cohen and random reals have just about any Ramsey-theoretic property you could want. In fact, they will satisfy the conclusion of the central sets theorem, which implies automatically that they will also satisfy the conclusions ...

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

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

EDIT, September 2015. This material has come up again. Note that, in post and comments, i simply report things I found. I also did a computer program because I was curious about what might be the best possible behavior. It is probably time for a follow-up question.
Odd. There is an article about this in the October M.A.A. Monthly, pages 737-742, by R. ...

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

There's a short-cut in Roth's approach if one only cares to get $o(N)$. Adolf Hildebrand told me so, and here is my shortest writeup.
Notation: Let $r(N),\rho(N)$ be the largest cardinality and density of a subset of $[N]$ that is free of 3-term APs, and let $\rho=\lim \rho(N)$, which must exist since $r(N+M)\leq r(N)+r(M)$. Let $A\subset [N]$ witness ...

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

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

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

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

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