Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

An arithmetic progression is a (possibly infinite) sequence of numbers such that the difference between consecutive terms is always the same value.

5
votes
1answer
290 views

Does every prime $p$ appear in a $p$-term arithmetic progression of primes? [duplicate]

This is a follow-up to an earlier question. The answer to that question was found on this page. The discussion on OEIS seems to suggest that, for any prime $p$, there should exist a $p$-length ...
29
votes
4answers
3k views

Is there an 11-term arithmetic progression of primes beginning with 11?

i.e. does there exist an integer $C > 0$ such that $11, 11 + C, ..., 11 + 10C$ are all prime?
10
votes
1answer
231 views

A weak form of the Erdős-Turán conjecture

This question is motivated by the answer of Gowers to the question Erdos Conjecture on arithmetic progressions. Question. (1)-Suppose $A \subset \mathbb{N}$ is such that Lim$_n$ $log(n) \cdot |A \...
1
vote
0answers
33 views

Catch simple arithmetic progression with spiral bijection [closed]

Consider the simple arithmetic progression ($s, z \in \mathbb{Z}$): $a_1 = s$ $a_{n+1} = a_n + z = s + n\cdot z$ Can somebody devise a procedure (another progression) $b_n$ so that there exists a $...
2
votes
0answers
41 views

Closed set containing infinite arithmetic progressions of ANY gap

Let $A\subseteq [0,\infty)$ be a set containing infinite arithmetic progressions of ANY gap, that is, for any $d>0$, there is $t>0$ such that $t+kd\in A$ for all $k\in \mathbb N$. Molter and ...
6
votes
0answers
151 views

Is a stronger version of the Erdős-Turan conjecture on arithmetic progessions reasonable? (And related questions.)

Define the size, possibly $\infty$, of a set $S\subseteq \mathbb{N}$ as $|S|=\sum\limits_{n\in S} \frac{1}{n}$. Then the Erdős-Turan conjecture states that if $|S|=\infty$, S must contain arbitrarily ...
1
vote
0answers
83 views

large arithmetic progression modulo p (II)

Is it possible to construct a $B$ $\subseteq$ $Z_p(=Z/pZ)$ of cardinal $cp^{\frac{1}{3}}$, for some constant $c$, such that there exists an arithmetic progression of size $c_1p^{\frac{2}{3}}$, for ...
1
vote
0answers
60 views

On strengthening of Dirichlet box principle in particular tensor product situations?

In here Lemma $4$ says: If $1\leq t_1,\dots,t_s<p$ satisfy $\prod_{i=1}^sT_i > p^{s−1}$ then given any integers $a_1,\dots,a_s$ there is an integer $t$ coprime to $p$ such that $$\min_{ k\in\...
0
votes
0answers
119 views

Counting sum of RSA type semiprimes in an arithmetic progression?

http://www.dms.umontreal.ca/~andrew/PDF/SquaresinAPs.pdf says that we can get $N^{2/3}$ squares in arithmetic progression $qn+a$ where $n\in\{0,1,\dots,N\}$ holds and this has been improved to $N^{3/5}...
0
votes
0answers
110 views

What relation does this problem have to Number Field Sieve?

In here Small geometric progression modulo N it is asked 'Must there exist a 5-term geometric progression $\lbrace a_0,a_1,a_2,a_3,a_4\rbrace$ (mod $N$) such that each term is $O(N^{2/3})$? We also ...
0
votes
0answers
704 views

On a number theoretic problem

Motivation: This problem comes from attempts to build a decoder for On a number theoretic problem coming from multiuser coding? and other related ramifications. Are there integers $a,b,|U|,|V|$, $N$...
1
vote
1answer
164 views

Generalized notion of divisor function?

Divisor function $d(n,m)$ counts the number of $q\in\Bbb N$ with $b<q<m$ such that $n\bmod q\equiv0$. Given $b>0$ what is the correct asymptotic, probabilistic and average case behavior of ...
1
vote
1answer
116 views

Tighter upper bound for $\sum_{i=1}^kA_i\log(\frac{A_i}{e})$

What is the tightest upper bound one can obtain for the following expression $$\sum_{i=1}^kA_i\log(\frac{A_i}{e})$$ subject to $\sum_{i = 1}^k A_i = C$ in terms of $C$ and $k$? A very loose upper ...
1
vote
0answers
151 views

Write {1,…,3n} as the disjoint union of arithmetic progressions of length 3 and steps 1, 2,…,n

For $n \equiv 0, 1, 2 \pmod 9$, write $\{\,1,\dots,3n\,\}$ as the disjoint union of arithmetic progressions $A_1, A_2,\dots,A_n$ of length 3, where $A_i$ has step $i$.
3
votes
0answers
54 views

What's known about $X$ when $|X(n) + X(n)| < kn$, $n \in \mathbb{N}$, absolute constant $k$?

Let $X$ be an infinite sequence of integers$$x_1 < x_2 < x_3 < \ldots,$$and let $X(n)$ be the set$$\{x_1, x_2, \ldots, x_n\}.$$ Question. What is known about $X$ when we have$$|X(n) + X(n)| &...
1
vote
1answer
332 views

Essential clarifications on application of pigeonhole principle

In here Lemma $4$ using pigeonhole says: For $T_1,\dots,T_s\in\Bbb R$ with $1\leq T_1,\dots,T_s<p$ and $\prod_{i=1}^sT_i > p^{s−1}$ and any integers $a_1,\dots,a_s$ there is an integer $t$ ...
-1
votes
1answer
190 views

Solutions to a diophantine system

What is the smallest $\gamma_1,\gamma_2,\gamma_3>0$ such that given coprime $p,q=\Theta(\ell)$ and integer $t\geq3$ there are coprime $m,n=\Theta(\ell^{t-1})$ with $(mn,pq)=1$, $\alpha_i\in\Bbb Z$ ...
4
votes
0answers
455 views

Rational points on the unit circle

Is anything known about any of the following questions about rational points on the unit circle? By “double point” I mean an element of $2C$, where $C$ is the group of rational points on the unit ...
3
votes
1answer
180 views

(Extremal) arithmetic combinatorics in non-abelian groups

Roth's Theorem states that any subset $A$ of $\{1, \dots, n\}$ with no solution to the equation $$x + y = 2z,\, (x, y, z) \in A^3,\, x \neq y$$ has size $o(n)$. Similar results hold when dealing with ...
2
votes
2answers
323 views

About consecutive integers covered by arithmetic progressions

Help me please to solve the following problem. There are $n$ arithmetic progressions of the form: $$(2i+1)k + x_i,~~~~ i = 1,\ldots,n, k \geq 0$$ Initial integer terms $x_i \geq 0$ are varying. ...
8
votes
1answer
340 views

Largeness and arithmetic progression properties of generic reals

Consider the following properties for a subset $A$ of $\mathbb{N}$: (1) $A$ is large: $\sum_{n \in A}$$ 1\over n$$=\infty,$ (2) $A^\infty=\limsup \frac{|A \cap \{ 1, \dots, n\}|}{n} >0$, (3) $A_\...
4
votes
0answers
317 views

The original proof of Szemerédi's Theorem

Nowadays there are plenty of different proofs of the celebrated Szemerédi's Theorem but for historical reasons I would like to read and understand the original proof. The proof is very tricky and, for ...
1
vote
0answers
101 views

Consecutive integers divisible by consecutive small numbers

Given $n$, what is the largest set of consecutive integers in $[n,2n]$ can we have so that each integer is divisible by a distinct element from $[\log n,2\log n]$ (no partiular order)? So apriori I am ...
8
votes
1answer
328 views

Primes in arithmetic progression with a moduli equal to a power of 2

I am currently looking for a result stronger than Siegel-Walfisz theorem, which gives an upper bound on the error term $|\pi(x,a,b)-\frac{\pi(x)}{\phi(a)}|$ for particular $a$. The Siegel Walfisz is ...
7
votes
1answer
387 views

Subsets of [1..N] with no three-term arithmetic progressions and no large gaps

Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow ...
6
votes
1answer
356 views

A kind of anti-Ramsey result

In contrast to classic results for arithmetic progressions of arbitrary length in one set at least of any finite partition of $\mathbb N$, it is easy to construct a partition in two sets of integers $...
1
vote
1answer
209 views

Primes in simultaneous arithmetic progressions

Suppose we're given four positive integers $a$, $b$, $c$, $d$ such that $a$ and $b$ are coprime, and $c$ and $d$ are coprime. Is there a non-negative integer $k$ such that both $ak+b$ and $ck+d$ are ...
7
votes
1answer
562 views

Bounded gaps between primes in arithmetic progressions

Has Zhang's work on bounded gaps between primes been extended to the following theorem? For any arithmetic progression $an+b,\gcd(a,b)=1$, there is a constant $H$ (depending only on $a$) such that ...
5
votes
1answer
357 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
1answer
489 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$ ...
11
votes
2answers
930 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
0answers
354 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, ..., ...
4
votes
1answer
263 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 ...
1
vote
1answer
346 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
1answer
665 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 ...
2
votes
0answers
411 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 $\ \...
5
votes
2answers
496 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 $$\alpha=0....
8
votes
4answers
2k 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
0answers
119 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
1answer
143 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 ...
9
votes
1answer
641 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 ...
6
votes
2answers
924 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 ...
0
votes
0answers
231 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,\, q\...
6
votes
2answers
819 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 ...
1
vote
0answers
393 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
1answer
182 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\}$ ...
8
votes
2answers
529 views

Are there five consecutive primes in arithmetic progression?

For example 3 consecutive primes in arithmetic progression 3,5,7 distance 2 151,157,163 distance 6 4 consecutive primes in arithmetic progression ...
0
votes
1answer
2k 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 ...
9
votes
2answers
519 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 ...
13
votes
1answer
1k 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 $$Q_a(...