## Hot answers tagged arithmetic-progression

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

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

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

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

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

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

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

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

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

12

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

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

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

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

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

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

10

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.

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

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

10

For $x\leq\phi(q)$ the estimate $\pi(x,a,q)\ll\frac{1}{\phi(q)}\frac{x}{\log x}$ would imply $\pi(x,a,q)\ll\frac{1}{\log x}$, i.e. $\pi(x,a,q)=0$ for large $x$ which is clearly false. So a bound you envision can only hold for $x$ slightly above $\phi(q)$. On the other hand, for any $\epsilon>0$, the Brun-Titchmarsh inequality implies
...

9

OK so take the unique tree on 3 vertices. Claim: you can't encode this with an arithmetic progression (AP). For if the AP is $a,a+d,a+2d$ then (because we have two edges) either vertices 1 and 2 are joined, or vertices 2 and 3 are joined (or both). Hence there is some $p>1$ such that either $p$ divides both $a$ and $a+d$, or $p$ divides both $a+d$ and ...

9

It's best to split this up into two cases.
Case 1: $\chi(a) = 1$. Then for $\Re(s) > 1$,
$$\prod_{p \equiv a \pmod{q}} \left(1 - \frac{\chi(p)}{p^s}\right)^{-1} = \prod_{p \equiv a \pmod{q}} \left(1 - \frac{1}{p^s}\right)^{-1} = \sum_{n \in \left\langle \mathcal{P} \right\rangle} \frac{1}{n^s},$$
where $\left\langle \mathcal{P} \right\rangle$ is the ...

9

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

8

I think the uniform distribution mod1 of $\{p/\alpha\}$ is due to Vinogradov, and the asmptotic for primes in a Beatty sequence $\sim \frac{\pi(x)}{\alpha}$ is an immediate consequence. Indeed for $p$ to be equal to some $\lfloor k\alpha\rfloor$ it is equivalent to $1-\frac{1}{\alpha}<\frac{p}{\alpha}-\lfloor \frac{p}{\alpha}\rfloor<1$. So you just ...

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