The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
170 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
1answer
296 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
376 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 ...
5
votes
3answers
396 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 ...
0
votes
0answers
281 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
2answers
407 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
4answers
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
0answers
106 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
120 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 ...
7
votes
2answers
436 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
1answer
509 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
0answers
194 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
2answers
481 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
2answers
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
2answers
376 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
2answers
379 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 ...
42
votes
3answers
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
0answers
186 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
144 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
1answer
414 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
0answers
435 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 ...
13
votes
4answers
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
1answer
834 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
2answers
218 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 ...
17
votes
4answers
1k 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
1answer
775 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
1answer
460 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
5answers
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
5answers
4k 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 ...
11
votes
2answers
525 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
2answers
629 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
2answers
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 ...
22
votes
1answer
937 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
2answers
881 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
1answer
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 ...
10
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
689 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
434 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
870 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
347 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
783 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
336 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
931 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
528 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
617 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
584 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 ...
13
votes
1answer
600 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
374 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 ...