The arithmetic-progression tag has no wiki summary.

**44**

votes

**3**answers

6k views

### Is a “non-analytic” proof of Dirichlet's theorem on primes known or possible?

It is well-known that one can prove certain special cases of Dirichlet's theorem by exhibiting an integer polynomial $p(x)$ with the properties that the prime divisors of $\{ p(n) | n \in \mathbb{Z} ...

**0**

votes

**0**answers

142 views

### arithmetic progressions with few primes

Is this true ?
Let $\beta_0$ be a positive number. One may find $\beta>\beta_0$, $0<\lambda<1$, and infinitely many $q>1$ so that there exists an arithmetic progression of step $q$, $a_1, ...

**5**

votes

**3**answers

503 views

### Any rigorous way to claim that sums with repeat summands are few?

Let $B \subset \mathbb{Z}^+$. Define $r_{B,h}(n)$ to be the number of ways of writing $n$ as the sum of $h$ elements of $B$ and $R_{B,h}(n)$ the number of ways to write $n$ as the sum of $h$ DISTINCT ...

**2**

votes

**1**answer

200 views

### Siegel-Walfisz for the Möbius function

I am working through the proof of the Bombieri-Vinogradov theorem in Analytic Number Theory (Iwaniec, Kowalski). My problem is that on page 424, it is said that $\mu(m)$ satisfies $D_f(x;q,a)\ll ...

**6**

votes

**1**answer

454 views

### Adding sets not containing arithmetic progressions of length three by forcing

Consider the following forcing notion: conditions in $\mathbb{P}$ are pairs $(s, N),$ where:
1) $s\in 2^{<\omega}$,
2) $N\in \mathbb{N}$,
3) (by identifying $s$ with a subset of $lh(s)$) $s$ ...

**8**

votes

**2**answers

590 views

### Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression.
I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid
...

**6**

votes

**0**answers

324 views

### Large sets not containing arithmetic progressions of length 3 in intervals

Given a large enough natural number $N$, let $\Delta_N=\{A \subseteq [N, 2N]: A$ contains no arithmetic progressions of length $3 \},$ where for natural numbers $N<M$ we have $[N, M]=\{N, N+1, ..., ...

**3**

votes

**1**answer

209 views

### Thin sets that are well-distributed over arithmetic progressions?

The primes do a nice job of intersecting an arithmetic progression $\{a+dn\}_{n=0}^\infty$ when $a$ and $d$ are coprime (see Dirichlet's theorem).
I would like a set of integers $S$ such that
the ...

**0**

votes

**1**answer

324 views

### Covering a finite subset of $\mathbb{N}$ with prime arithmetic progressions

Because of a problem I ran into I am trying to get a quick start in covering with arithmetic progressions.
First I want to say I am aware of this previously asked question:
Covering $\mathbb{N}$ with ...

**3**

votes

**1**answer

452 views

### Smallest prime in an arithmetic progression

Let $\{a_n\}_{n\in\mathbb{N}}$ be defined as $a_n = a + bn$ for some $a, b >0,(a, b) = 1$. Are there good bounds on the minimal $k$ s.t. $a_k$ is prime. It is well known that there are infinitely ...

**0**

votes

**0**answers

303 views

### Arithmetic progression and average of two prime numbers

Let $A=(a_n : n \in \mathbb{N})$ be the sequence given by:
$$
\ a_n = a_1 + (n - 1)d,\quad a_1,\ d,\ n \in \mathbb N,\quad d\gt a_1,\quad \gcd(a_1,\ d)=1.
$$
For all terms of $A$ greater than $\ ...

**3**

votes

**2**answers

441 views

### Primes from a Dirichlet sequence and an irrational number

From Dirichlet's theorem on arithmetic progressions, if $\text{gcd}(a,b)=1$ we know $\{ak+b\}_{k\ge 0}$ contains infinitely many primes. Let those primes be $p_1,p_2,\cdots$. Then the real
...

**7**

votes

**4**answers

1k views

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

**0**

votes

**0**answers

114 views

### Arithmetic progression and 3^m,3^{m+1} intervals

I'm trying to prove (or disprove) the following "conjecture".Given the following set of powers of two:
$$A = \{ x \mid x = 2^n \text{ and } 2^{n-1} < 3^m < x < 3^{m+1} < 2^{n+1}\}$$
...

**0**

votes

**1**answer

126 views

### Arithmetic progression and most significant digits in different bases

Given a number $x \geq 3$, let $b(x) \in \{0,1\}$ be the second most significant digit (bit) of its binary representation, and $t(x)\in \{1,2\}$ the most significant digit of its ternary ...

**6**

votes

**2**answers

541 views

### Sum of divisor function over arithmetic progression

I am trying to find an estimate for the following sum:
$$
\sum_{\substack{n \leq x \\ n \equiv k (m)}} d(n),
$$
where $d(n)$ is number of divisors of $n$. I found estimates for the case when $k$ and ...

**9**

votes

**1**answer

534 views

### 4 squares almost in an arithmetic progression

Does there exist infinitely many coprime pairs of integers x,d such that x, x+d, x+2d, x+4d are all square numbers?
One example would be 49,169,289,529. This is the only example I have found so far ...

**0**

votes

**0**answers

205 views

### Conjecture about distribution of primes in arithmetic progression

For my work, i need the following
Conjecture: Let $N$ large number such that exist a prime number $q$ and $A>\frac{1}{2}$ such that $N^{1/2}<N^{A}\leq q-1<N.$ Then $\forall a\in\left[1,\, ...

**6**

votes

**2**answers

521 views

### On the prime number theorem in arithmetic progression

The prime number theorem tells us that , if $\pi\left(x\right)$ denotes the number of primes less than or equal to $x$, we have $$\pi\left(x\right)\sim\frac{x}{\log x}.$$
In a similar manner ...

**6**

votes

**2**answers

1k views

### least prime in a arithmetic progression

Hello
Here I want to consider the simplest arithmetic progression $n\equiv 1\pmod{q}$ where $q$ is a prime. Is it true that we can find a prime $p\leq q^2$ in this arithmetic progression?
This ...

**5**

votes

**2**answers

396 views

### k-pseudorandom measures

In reading the paper of Green and Tao on arithmetic progressions within the primes, I became very interested in the notion of a k-pseudorandom measure discussed in that paper.
A measure here is a ...

**9**

votes

**2**answers

413 views

### Largest number of k-arithmetic progressions without a (k+1)-arithmetic progression

Suppose $A \subseteq \{1,\dots,n\}$ does not contain any arithmetic progressions of length $k+1$. What is the largest number of $k$-term arithmetic progressions that $A$ can have? (one may also wish ...

**0**

votes

**0**answers

241 views

### Greedy sequences without k-term arithmetic progressions

If $S_k$ is the greedy sequence with no length-k arithmetic subsequence, (ie $S_3$ = A003278 , $S_4$ = A005837 , $S_5$ = A020655 ), is it guaranteed that any other sequence $a$ with no length-k ...

**3**

votes

**1**answer

155 views

### Non-asymptotically densest progression-free sets

For the context of this question, a progression-free set is a subset of integers that does not contain length-three arithmetic progressions.
For large $N$, it is known that $[N] = \{1, \ldots, N\}$ ...

**0**

votes

**1**answer

581 views

### Intersection of two arithmetic progressions

Using elementary matrix row and column operations on the system of two diophantine equations, namely, $N=an+b$ and $N=cn+d$, where $n\in\mathbb{N}^0$, it can be shown that the intersection of these ...

**10**

votes

**0**answers

502 views

### What are the limits of the Erdős-Rankin method for covering intervals by arithmetic progressions?

To construct gaps between primes which are marginally larger than average, Erdős and Rankin covered an interval $[1,y]$ with arithmetic progressions with prime differences. A nice short exposition is ...

**14**

votes

**4**answers

1k views

### Arithmetic progressions without small primes

The following question came up in the discussion at How small can a group with an n-dimensional irreducible complex representation be? :
Is it known that there are infinitely many primes p for which ...

**13**

votes

**1**answer

877 views

### Small primes in arithmetic sequences

Fix an integer $a>1$. For $n \geq 1$ an integer, let $\pi_{n,1}(an)$ the number of primes
$p \leq an$ such that $p \equiv 1 \pmod{n}$, and $\pi(an)$ the number of all primes $p \leq an$. Let
...

**0**

votes

**2**answers

262 views

### sequences - recurrence relation [closed]

I have to find the expression of $(y_n)$ defined by :
$$y_{n+1}=a y_n+b z_n+c$$
where $(z_n)$ is an arithmetico-geometric sequence :
$$z_{n+1}=d z_n+e$$
and $a,b,c,d,e$ real numbers.
Thank you ...

**19**

votes

**4**answers

2k views

### Arithmetic progressions inside polynomial sets

There are at most 3 perfect squares in arithmetic progression (Fermat, Euler). It was shown in [1] that if $n>2$ there are no three term arithmetic progression consisting of nth powers.
Take a ...

**8**

votes

**1**answer

808 views

### Squares in an Arithmetic Progession

Let $P(x;a,b) := \{an+b, 0\leq n \leq x \} $ denote an arithmetic progression. Further let $A(x;a,b)$ denote the number of elements of $P(x;a,b)$ that are squares. It's an old conjecture of Rudin ...

**8**

votes

**1**answer

485 views

### On the least prime in arithmetic progressions

My question concerns the least prime (denoted $p(a, q)$) in the arithmetic progression $a \pmod q$ where $a$ and $q$ are coprime. Quite a time ago Linnik demonstrated that
$$p(a, q) \ll q^L$$
for ...

**12**

votes

**5**answers

2k views

### Special arithmetic progressions involving perfect squares

Some time ago the following rather easy problem appeared in an online publication called "Problems in Elementary NT" by Hojoo Lee:
Prove that there are infinitely many positive integers $a$, $b$, $c$ ...

**22**

votes

**5**answers

5k views

### Erdos Conjecture on arithmetic progressions

Introduction:
Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.
Question:
I ...

**12**

votes

**2**answers

564 views

### Mertens-like sum in arithmetic progressions

I find myself needing a good estiamate for $\sum_{p\le x,\, p\equiv a\mod q} 1/p$, perhaps something like
$$
\sum_{p\le x,\, p\equiv a\mod q} \frac1p = \frac{\log\log x}{\phi(q)} + b(q,a) + ...

**2**

votes

**2**answers

720 views

### Sum of Series Where Exponent is Sum of Arithmetic Progression

Hi,
How do i get the sum of such a sequence:
$1 + x^{-1} + x^{-3} + x^{-6} + ...$
where the exponents are actually sum of arithmetic progression. i.e.
$x^{-0} + x^{-(0 + 1)} + x^{-(0 + 1 + 2)} + ...

**12**

votes

**2**answers

1k views

### Arithmetic progressions in power sequences

In connection with this MO post (and without any applications / motivation whatsoever), here is an apparently difficult - but nice - problem.
For a non-zero real number $s$, consider the infinite ...

**23**

votes

**1**answer

985 views

### Arithmetic Progressions of Squares

Fermat may or may not have known that there are 3-term arithmetic progressions of squares (like $1^2, 5^2, 7^2$, and that there are no 4-term APs. Murky history aside, Keith Conrad has two pleasant ...

**15**

votes

**2**answers

993 views

### Roth's theorem and Behrend's lower bound

Roth's theorem on 3-term arithmetic progressions (3AP) is concerned with the value of $r_3(N)$, which is defined as the cardinality of the largest subset of the integers between 1 and N with no ...

**3**

votes

**1**answer

2k views

### Is there another proof for Dirichlet's theorem? [duplicate]

Possible Duplicate:
Is a “non-analytic” proof of Dirichlet’s theorem on primes known or possible?
Dirichlet's theorem on primes in arithmetic progression states that there ...

**11**

votes

**1**answer

2k views

### The Green-Tao theorem and positive binary quadratic forms

Some time ago I asked a question on consecutive numbers represented integrally by an integral positive binary quadratic form. It has occurred to me that, instead, the Green-Tao theorem may include a ...

**3**

votes

**1**answer

730 views

### Can every finite graph be represented by an arithmetic sequence of natural numbers?

(This is a follow-up to my previous questions Natural models of graphs?.)
Erdös in The Representation of a Graph by Set Intersections (1966) states:
Theorem. Let $G$ be an arbitrary
graph. Then ...

**6**

votes

**1**answer

492 views

### Minimum cardinality of a difference set in $R^n$

Cross-posted from http://math.stackexchange.com/questions/65195/minimum-cardinality-of-a-difference-set-in-mathbb-rn.
Given a finite set $S$ of $m$ points in $\mathbb R^n$ that do not all lie in the ...

**10**

votes

**2**answers

882 views

### What Dirichlet doesn't tell…

Let $n>1$ be an integer, and let us consider the set $P(n)$ of all prime numbers $p$ such that $p$ is not congruent to $1$ modulo $n$. Dirichlet's Density Theorem tells us that $P(n)$ has a natural ...

**4**

votes

**1**answer

357 views

### How large can a non-sumset be?

The theory of sumsets $A+B$ where $A$ and $B$ are finite subsets of an additive group $Z$ is extensively studied in additive combinatorics: finding long arithmetic progressions inside them, finding ...

**1**

vote

**1**answer

789 views

### Covering Systems of infinite sets of residue classes mod primes

Take an infinite set of distinct primes and a (edit: or 2 , etc.) residue class for every prime. For exammple you can take all the primes bigger than some prime or the primes of a specific form (i.e. ...

**4**

votes

**5**answers

1k views

### residue classes of primes, covering intervals and bounds on the different ways

Take the first $n$ primes $p_1,...,p_n$ and the primorial $P_n$ .Denote by $p_i$ every prime bigger than $p_n$ and smaller than $P_n$.
1) Is that true that there always be a number in any interval of ...

**6**

votes

**1**answer

346 views

### Bounds on the size of sets not containing a given finite pattern

Recall the following version of Szemerédi's Theorem: let $r_k(N)$ be the largest cardinality of a subset of $[N]:=\{1,\ldots, N\}$ which does not contain an arithmetic progression of length $k$. Then, ...

**2**

votes

**0**answers

950 views

### Fun question in additive combinatorics

It is easy to see that for a finite set of integers $A$ of cardinality $n$, the cardinality of the sumset $A+A$ satisfies
$$
2n-1\leq |A+A|\leq \frac{n(n+1)}{2}.
$$
The lower bound is essentially ...

**5**

votes

**2**answers

540 views

### Asymptotic Distribution of Primes

Given an integer $n$ and let $1\leq m\leq n$ be such that $n$ and $m$ are coprimes define
$$
\mathcal{N_{n,m}}:=\text{the set of primes $p$ such that $p\equiv{m}\hspace{0.1cm}\mathrm{mod}(n)$}.
$$
...