The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
98 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
101 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
362 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
483 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
182 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
425 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 ...
5
votes
2answers
956 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
357 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
336 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 ...
40
votes
3answers
5k 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
120 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
138 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
296 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
0answers
342 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
795 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
191 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
717 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
414 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
1k 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$ ...
21
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
500 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) + ...
1
vote
2answers
551 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
977 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
902 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
816 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
650 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
412 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
854 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
341 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
775 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
327 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
909 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
512 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
603 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
566 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
582 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
368 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
284 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
1answer
417 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
7
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
247 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
574 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 ...
9
votes
2answers
688 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 ...
3
votes
3answers
331 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 $h$ elements of $B$ and $R_{B,h}(n)$ the number of ways to write $n$ as the sum of $h$ DISTINCT elements of ...