**3**

votes

**1**answer

765 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

540 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

894 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

369 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

804 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

357 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

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

**2**answers

558 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

**3**answers

632 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

**1**answer

639 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

**1**answer

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

**1**answer

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

**3**answers

395 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

**1**answer

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

**0**

votes

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

677 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

**2**answers

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

**2**answers

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

**3**

votes

**1**answer

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

**1**answer

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

**1**answer

320 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

**2**answers

711 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

**3**answers

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

**1**answer

851 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

**3**answers

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

**1**answer

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

**5**answers

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

**2**answers

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

**2**answers

439 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

**1**answer

610 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

**1**answer

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