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

learn more… | top users | synonyms

11
votes
1answer
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
1answer
767 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
1answer
545 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
2answers
896 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
1answer
370 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
1answer
805 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
5answers
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
1answer
361 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
0answers
967 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
2answers
560 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)$}. $$ ...
2
votes
3answers
633 views

Arithmetic progressions of length 3 in subset of Z_n of size n^d

Let $A\subset\mathbb{Z}/n\mathbb{Z}$ such that: $|A|>n^{d}$ ($0< d <1$). Let $C=\{(x,y,2y-x)\in A\times A \times A\}$ be the set of $3$-term arithmetic progressions within $A$. [The ...
7
votes
1answer
644 views

Homogeneous arithmetic progressions in difference sets

I have a nasty feeling that I ought to be able to answer this question, but I've got other things to think about right now and I'm interested in the answer just so that I can reply to a mathematical ...
14
votes
1answer
635 views

Goldbach-type theorems from dense models?

I'm not a number theorist, so apologies if this is trivial or obvious. From what I understand of the results of Green-Tao-Ziegler on additive combinatorics in the primes, the main new technical tool ...
16
votes
1answer
1k views

Are all primes in a PAP-3?

Van der Corput [1] proved that there are infinitely many arithmetic progressions of primes of length 3 (PAP-3). (Green & Tao [2] famously extended this theorem to length $k$.) But taking this in ...
5
votes
3answers
396 views

Structure of nonaveraging sets of integers

A set of integers is said to be nonaveraging if it contains no three-term arithmetic progression. I call a nonaveraging subset of $\lbrace 1,2, \ldots ,n \rbrace$ optimal when it has maximal ...
6
votes
1answer
322 views

Distribution of a function in an arithmetic progression

I am going to have to borrow the opening passage from Bombieri, Friedlander, Iwaniec${}^*$ since they state this idea so well. In the following $\|f\|$ means $\big(\sum_{n\leqslant x} |f(n)|^2\big)^{1/...
0
votes
1answer
464 views

greatest common divisor of p-1 and q-1 [closed]

Hi there, Can we say that if $p$ and $q$ are distinct prime number diving $n$ $\Omega(gcd(p-1,q-1)) \leq \Omega(n)$ Where $\Omega(n)$ denotes the number of prime powers dividing $n$ Best rahmi
8
votes
1answer
1k views

Are most primes in a prime arithmetic progression of length at least 3?

Following the following two previous questions on mathoverflow: Are all primes in a PAP-3? and Covering the primes by 3-term APs ? I have attempted to show that infinitely many primes are in an ...
4
votes
1answer
261 views

non-asymptotic Bertrand-type theorems for arithmetic progression

It is well known that primes of form $4k+3$, call them $3=q_1 < q_2 < \dots$ satisfy $q_{n+1}/q_n\rightarrow 1$ (and even $q_n=\frac{n}{2\log n}(1+o(1))$). I would be glad to see results of ...
12
votes
2answers
684 views

Arithmetic progressions modulo $p$ under the squaring map

I feel that the following problem should be known, but I'm not sure where to look for it. Fix a real constant $\frac{1}{2} \ge \epsilon > 0$. For varying primes $p$, Let $A_p$ denote the set of ...
10
votes
2answers
772 views

What are the analytic properties of Dirichlet Euler products restricted to arithmetic progressions?

There are (at least) two ways of writing down the Dirichlet L-function associated to a given character χ: as a Dirichlet series $$\sum_{n=1}^\infty \frac{\chi(n)}{n^s}$$ or as an Euler product $$\...
8
votes
2answers
521 views

Primes in quasi-arithmetic progressions?

Suppose $\alpha > 1$ is irrational. Are there infinitely many primes of the form $\left\lfloor \alpha n \right\rfloor$? Is the number of $p \leq X$ of this form $\sim \alpha^{-1} X (\log{X})^{-1}$...
3
votes
1answer
1k views

Strengthening of Dirichlet's theorem on arithmetic progressions

Hello all, Dirichlet's famous theorem asserts that any arithmetic progression $\lbrace ax+b | x \in {\mathbb N}\rbrace$ contains infinitely many primes if a and b are relatively prime. I am ...
6
votes
1answer
737 views

Primes in arithmetic progressions

Denote by $\pi(x,a,q)$ the number of primes $p\le x$ of the form $p=qk+a$ and $E(x,a,q)=\phi(q)^{-1}\mathrm{Li}(x)-\pi(x,a,q)$. What is the strongest conjectured bound on $E(x,a,q)$ in terms of $x,q$?
1
vote
1answer
321 views

Do there exist sets of integers with arbitrarily large upper density which contains infinitely many elements that are not in an arithmetic progression of length 3?

Given that simply stipulating positive upper density is not sufficient to guarantee that all but finitely many members are in an arithmetic progression of length 3, that there indeed exists sets of ...
6
votes
2answers
715 views

Inverse Length 3 Arithmetic Progression Problem for sets with positive upper density

It is a famous theorem of Roth, which Szemerédi famously generalized, that if a set of natural numbers has positive upper density then it contains arithmetic progressions of length $k$. The famous ...
15
votes
3answers
2k views

What is the shortest route to Roth's theorem?

Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
16
votes
1answer
852 views

Covering the primes by arithmetic progressions

Define the length of a set of arithmetic progressions of natural numbers $A=\lbrace A_1, A_2, \ldots \rbrace$ to be $\min_i | A_i |$: the length of the shortest sequence among all the progressions. ...
11
votes
3answers
771 views

What does the computer suggest about the parity of p(n), for n in a fixed arithmetic progression?

Let p(n) be the number of partitions of n. A famous theorem of Euler allows one to compute the parity of p(n) quickly for quite large n. In: On the distribution of parity in the partition function, ...
42
votes
1answer
9k views

Is the Green-Tao theorem true for primes within a given arithmetic progression?

Ben Green and Terrence Tao proved that there are arbitrary length arithmetic progressions among the primes. Now, consider an arithmetic progression with starting term $a$ and common difference $d$. ...
17
votes
5answers
2k views

Finitely many arithmetic progressions

A few years ago, somebody told me a lovely problem. I suspect there may be more to it (which I would be interested in learning), and would very much like to find a reference, it makes me uncomfortable ...
3
votes
2answers
497 views

“half arithmetic progressions” in dense sets

Fix a positive real number d>0. Szemeredi's theorem implies that for every integer k, there exists an integer N(k,d) such that if A is a subset of the interval [1,N] with density greater than d >0, ...
6
votes
2answers
440 views

Smallest k-term AP of primes

Let $S(k)$ denote the smallest integer such that there exists a k-term arithmetic progression of primes among the integers $[1,S(k)]$. Green and Tao have an unpublished note that gives a very large ...
10
votes
1answer
613 views

Covering the primes by 3-term APs ?

Hello, the Green-Tao theorem says infinitely many k-term Arithmetic Progressions exist for any integer k. My question is: can we actually partition the primes into 3-term APs only (or is there a ...
7
votes
1answer
652 views

Upper bound for number of k-term arithmetic progressions in the primes

Normal heuristics give that number of k-term arithmetic progressions in [1,N] should be about \[c_k\frac{N^2}{\log^kN}\] for some constant $c_k$ dependent on k. ...