Questions tagged [arithmetic-progression]
An arithmetic progression is a (possibly infinite) sequence of numbers such that the difference between consecutive terms is always the same value.
169
questions
15
votes
1
answer
1k
views
Arithmetic progressions in stopping time of Collatz sequences
Inspired by the question here, we did a few more simulations of numbers of some specific forms and noticed a pattern.
We consider the original $3n+1$ transform where we divide by $2$ if it's even and ...
- 259
2
votes
1
answer
256
views
Explanation about arithmetico-geometric progression (AGP) [closed]
So I came across a formula that looks like:
$x_n = \alpha x_{n-1} + \beta$
Since I don't have a strong mathematical background I didn't recognize it was an AGP and as I tried to express $x_n$ with ...
- 123
13
votes
2
answers
633
views
A reformulation of Erdős conjecture on arithmetic progressions
Erdős conjecture on arithmetic progressions states that if $S$ is a set of positive integers such that $c(S):=\sum_{n \in S} \frac{1}{n} = \infty$ (large set), then $ \forall \ell \ge 3$ the set $S$ ...
- 25.9k
12
votes
2
answers
720
views
Smallest set such that all arithmetic progression will always contain at least a number in a set
Let $S= \left\{ 1,2,3,...,100 \right\}$ be a set of positive integers from $1$ to $100$. Let $P$ be a subset of $S$ such that any arithmetic progression of length 10 consisting of numbers in $S$ will ...
- 169
9
votes
1
answer
973
views
Sums of two squares in arithmetic progressions
Let $r(n)$ denote the number of representations of $n$ as the sum of two squares. Are there any known results on $$\sum _{n\leq x\atop {n\equiv a(q)}}r(n)$$ and in particular is there an asymptotic ...
- 143
3
votes
1
answer
200
views
Gowers norms and three-term arithmetic progressions in the mean
Let $f:\mathbb{Z}^+\to \mathbb{C}$ be bounded. Say we are interested in studying how $f$ behaves in short three-term arithmetic progressions. It is very well-known that we can bound
$$\sum_{h\leq H} \...
- 535
1
vote
0
answers
67
views
Wieferich primes and arithmetic prgressions
Let $p$ be an odd prime number. Let $K$ be a number field with Galois group $G$ and $H$ be a subgroup of $G$ stable under conjugation. Then the Cebotarev density theorem gives that $$\mathcal{L}=\{\...
- 337
3
votes
1
answer
400
views
Covering integers by finitely many arithmetic progressions structure
Assume the positive integers $\mathbb{N}$ are partitioned as
$$\mathbb{N} = \cup_{i = 1}^n (a_i + b_i \mathbb{N})$$
where $a_i, b_i \in \mathbb{N}$. Prove that all such partitions are obtained by the ...
- 501
5
votes
0
answers
173
views
Large finite subsets of Euclidean space with no isosceles (or approximately isosceles) triangles
Here's a question in combinatorial geometry which feels very much like other questions I'm familiar with but which I can't see how to get a hold of. I'll actually propose two different questions on ...
- 19.1k
2
votes
1
answer
427
views
Partitioning the positive integers into finitely many arithmetic progressions
From Bóna's A Walk through Combinatorics:
Prove or disprove that if we partition the positive integers into finitely many arithmetic progressions then there will be at least one arithmetic ...
- 39
3
votes
2
answers
390
views
Infinitely many primes in particular progressions
I'm faced with the following problem on primes. Does someone have any clue? Is it (a reformulation of) an open problem?
Let $d$ be a positive integer, $d\geq 2$. By Dirichlet's theorem, there is an ...
- 33
2
votes
1
answer
295
views
Homogeneous van der Waerden
The Erdős Discrepancy Problem is whether in any two-coloring of the naturals for any $C$ there is a sequence $d, 2d, \ldots nd$ such that the difference of red and blue numbers in it is more than $C$.
...
- 18.4k
2
votes
1
answer
286
views
Extension of Dirichlet's Arithmetic Progression Theorem
Dirichlet's Arithmetic Progression Theorem states that:
Given $a, b\in\mathbb{Z^+}$ with $(a,b)=1$, then $a+kb$ is prime for an infinite number of $k\in\mathbb{Z^+}.$
For any given $a$ and $b$ let ...
- 1,226
1
vote
0
answers
148
views
Arithmetic progression of rationals
We know that the set of rational numbers is countable. For which $n$ can we order all rational numbers as $a_1,a_2,\dots$ so that every subsequence of length $n$ is not an arithmetic progression?
For ...
- 1,199
8
votes
2
answers
3k
views
Product of arithmetic progressions
Let $(a_1,a_2\ldots,a_n)$ and $(b_1,b_2,\ldots,b_n)$ be two permutations of arithmetic progressions of natural numbers. For which $n$ is it possible that $(a_1b_1,a_2b_2,\dots,a_nb_n)$ is an ...
- 1,199
2
votes
0
answers
67
views
Discrepancy related independent vector from tensor product?
Here discrepancy is from $(2.4)$ in https://www.ricam.oeaw.ac.at/files/people/siambook_nied.pdf given by 'The discrepancy $D_N(P) = D_N(x_l,\dots,X_N)$ of
the point set $P$ of $N$ points in $\mathbb Z^...
- 13.7k
1
vote
0
answers
53
views
Discrepancy bound of integer tensor product sequence?
Here discrepancy is from $(2.4)$ in https://www.ricam.oeaw.ac.at/files/people/siambook_nied.pdf given by 'The (extreme) discrepancy $D_N(P) = D_N(x_l,\dots,X_N)$ of
the point set $P$ of $N$ points in $...
- 13.7k
5
votes
1
answer
410
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 ...
- 4,124
29
votes
4
answers
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?
- 4,124
9
votes
1
answer
316
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
0
answers
58
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 $...
- 111
2
votes
0
answers
70
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 ...
- 751
6
votes
0
answers
245
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 ...
- 5,045
41
votes
3
answers
4k
views
A game on integers
$A$ and $B$ take turns to pick integers: $A$ picks one integer and then $B$ picks $k > 1$ integers ($k$ being fixed). A player cannot pick a number that his opponent has picked. If $A$ has $5$ ...
- 909
1
vote
0
answers
96
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
1
answer
229
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 ...
- 13.7k
1
vote
1
answer
221
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 ...
- 13
1
vote
0
answers
171
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
0
answers
64
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)| &...
- 31
2
votes
1
answer
421
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$ ...
user94040
-2
votes
1
answer
200
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$ ...
- 13.7k
26
votes
1
answer
1k
views
What is the status on this conjecture on arithmetic progressions of primes?
The Green-Tao theorem states that for every $n$, there is an arithmetic sequence of length $n$ consisting of primes.
For primes, $p$, let $P(p)$ be the maximum length of an arithmetic progression of ...
- 1,825
4
votes
0
answers
1k
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 ...
- 2,756
3
votes
1
answer
261
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 ...
- 1,543
2
votes
2
answers
381
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.
...
- 267
8
votes
1
answer
389
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
0
answers
526
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,543
1
vote
0
answers
116
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 ...
- 13.7k
8
votes
1
answer
419
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 ...
8
votes
1
answer
553
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 ...
- 19.1k
6
votes
1
answer
407
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 $...
- 3,560
3
votes
1
answer
347
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 ...
- 483
9
votes
1
answer
821
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 ...
- 27.4k
5
votes
1
answer
531
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 (\...
- 53
6
votes
1
answer
526
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
2
answers
1k
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
...
- 149k
6
votes
0
answers
375
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
1
answer
326
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 ...
- 7,573
1
vote
1
answer
367
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 ...
- 11
4
votes
1
answer
968
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 ...
- 1,831