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.
160
questions
3
votes
0
answers
126
views
Szemerédi’s theorem in really dense sets
This question is inspired by Tao’s answer in this post. I have thought about this occasionally for several months without anything concrete.
Question:
Given $\delta>0$ and $k\ge 3$, let $N= N_k(\...
- 2,322
5
votes
0
answers
95
views
Multidimensional van der Waerden, bounds for squares
Given $r$, let $f(r)$ be the smallest $N$ such that for any $r$-coloring $C:\{1,\dots,N\}^2 \to \{1,\dots,r\}$, there exists $x,y,d\neq 0$ such that $C((x,y)) = C((x+d,y))= C((x,y+d))=C((x+d,y+d))$.
I ...
- 2,322
3
votes
1
answer
168
views
Infinite constructions in additive combinatorics
A huge part of the investigation in the area of additive combinatorics asks for the answer of the following question: given an arithmetic pattern (for instance, $x+y=2z$, or $x+y=z+t$, or $x+y=z$), ...
- 1,463
4
votes
0
answers
102
views
On Behrend's construction
Fix $\alpha>0$. Does there exist $\epsilon = \epsilon(\alpha)>0$ such that if $S\subset [N]:=\{1,\dots,N\}$ has $\ge \alpha N$ elements, then for any function $f:S\to [0,1]$, there exist some ...
- 2,322
3
votes
0
answers
169
views
Behrend's construction vs. Triangle removal lemma
I was reading Zhao's book "Graph theory and additive combinatorics" and on page 71 I came across Remark 2.5.4 which I'd like to understand.
Theorem 2.3.1 (Triangle removal lemma) For all $\...
- 246
3
votes
1
answer
124
views
Density of semiprimes in arithmetic progression
Let $n,a,b$ be integers such that $n$ and $a$ are coprime, and $n$ and $b$ are also coprime. According to the Prime number theorem for arithmetic progressions, the primes which are $a\mod n$ have the ...
- 443
4
votes
1
answer
323
views
Does Szemerédi's theorem hold for sets with positive upper Banach density?
We say that a set of natural numbers $A\subseteq \omega$ has positive upper density if $$\lim\sup_{n\to\infty}\frac{|A\cap n|}{n+1} > 0.$$
Szeméredi's theorem states that every $A\subseteq \omega$ ...
- 42.5k
3
votes
1
answer
300
views
Where odious numbers meet arithmetic progressions
Suggested by this problem:
Do the sets of all odious / evel numbers meet every infinite arithmetic progression?
A number is odious if it contains an odd number of digits $1$ in its binary ...
- 22.2k
0
votes
1
answer
182
views
Are there infinitely long arithmetic progressions in every increasing sequence of positive integers with bounded gaps between consecutive terms?
Suppose the largest gap is D>1 and at least two of the gaps 1,2,...,D appear infinitely many times. I think the answer is NO. But I find it difficult to formulate a necessary and sufficient ...
- 43
2
votes
0
answers
64
views
Bounds for Szemerédi’s theorem for GAP’s
Let a $(k,D)$-AP refer to sets of the form $\{n_0+l_1n_1+\dotsb +l_Dn_D: l_1,\dotsc,l_D \in [k]\}$ with cardinality $k^D$ (i.e. a proper $D$-dimensional GAP with width $k$).
Let $r(N,k,D)$ be the ...
- 2,322
5
votes
2
answers
199
views
Progressions in sumset or complement
Fix $\epsilon>0$.
For all large $N$, does there exist $A\subset [N]:=\{1,\dots,N\}$ such that both $A+A$ and $A^c:=[N]\setminus A$ lack arithmetic progressions of length $N^\epsilon$?
I am aware ...
- 2,322
2
votes
0
answers
54
views
Capset problem but considering differences with bounded support
For any dimension $D\ge 1$, we define the homomorphism $\phi: \Bbb{Z}^D\to (\Bbb{Z}/3\Bbb{Z})^D; \xi\mapsto \xi+3\Bbb{Z}^D$.
Given a set $A \subset \{0,1,2\}^D$, we define $S_A$ to be the set of $v \...
- 2,322
2
votes
1
answer
203
views
Averages of Möbius function in arithmetic progressions
It is mentioned in multiple occasions here that the bound
$$
\mathop{\sum_{n=1}^{N}}_{n\equiv a\mod l} \mu(n) = o(N)
$$
is equivalent to the prime number theorem in arithmetic progressions. But I am ...
- 487
3
votes
1
answer
146
views
Density for products of arithmetic progressions
Consider $k\geq 2$ biinfinite arithmetic progressions $\mathcal A_i=a_i+b_i\mathbb Z$ (for $i=1,\ldots,k$) in $\mathbb Z$.
(We suppose that $a_i$ and $b_i\geq 2$ are strictly positive integers.
One ...
- 15.9k
2
votes
0
answers
96
views
Conditional stronger bounds on Linnik theorem with prime power modulus
This post is related to questions asked here and here. However, I include the relevant background on least prime in arithmetic progressions presented here for benefit of the reader.
By Linnik's ...
- 1,000
0
votes
1
answer
164
views
The number of intersecting $k$-arithmetic progressions below $n$ is capped by $nk$
I found this as an exercise in the context of capping Van der Waerden numbers:
For a given arithmetic progression $S \subseteq [n] = \{1,...,n\}$ with $|S| = k$ there are at most $nk$ other such ...
- 1
0
votes
0
answers
161
views
Sum of squares squared in an arithmetic progression
Let $r(n)$ be the number of ways to write $n$ as a sum of two squares and $(a,q)=1$.
What is known about
$$
\sum_{n \le x,n \equiv a (\text{mod} \, q)} r(n)^2 \quad?
$$
I am looking for uniform ...
- 120
4
votes
1
answer
238
views
Generalizations of the Brun-Titchmarsh theorem
Let $\pi(x;q,a)$ count the number of primes $\leq x$ congruent to $a$ mod $q$. The Brun-Titchmarsh Theorem states that for all $q< x$, $(a,q)=1$, we have
$$
\tag{1}
\pi(x;q,a) \leq \frac{2x}{\...
- 1,476
5
votes
1
answer
221
views
Primes in arithmetic progressions: weak version of Linnik's theorem with prime power modulus?
Looking at a problem in representation theory I ran into a question on small primes in arithmetic progressions.
Let me begin with a short summary of results on small primes in arithmetic progressions. ...
- 704
4
votes
1
answer
209
views
Can we do better than random when constructing dense $k$-AP-free sets
We write $[N]$ to denote $\{1,\dots,N\}$. We say a set $S$ is $k$-AP-free if it lacks non-trivial arithmetic progressions of length $k$.
We define the 2-color van der Waerden number, $w(2;k)$, to be ...
- 2,322
0
votes
0
answers
93
views
Primes in residue classes [duplicate]
For which sets of residue classes are there easy elementary proofs that there are infinitely many primes in them, which don’t require the machinery of proofs of Dirichlet’s theorem?
Example: it’s ...
- 513
9
votes
3
answers
913
views
A set with positive upper density whose difference set does not contain an infinite arithmetic progression
For $S \subset \mathbb{N}$ define $S-S=\{x-y:x \in S, y \in S\}$.
As noted below there is a simple example showing that a set $S \subset \mathbb{N}$ with positive upper density has a sumset $S+S=\{x+y:...
- 4,552
17
votes
2
answers
2k
views
A proof of Van der Waerden's theorem using a weakened form of Szemeredi's theorem
Van der Waerden's theorem states that any colouring of the integers in a finite number of colours has monochromatic arithmetic progressions of arbitrary length. Szemerédi's Theorem is a dramatic ...
- 4,552
5
votes
0
answers
175
views
Showing that Fourier pseudorandomness is insufficient for $k=4$ case (four arithmetic progressions)
I wish to show that the Fourier pseudorandomness is insufficient to count the number of 4-term arithmetic progression.
Let $A \subset \mathbb{Z}/N\mathbb{Z}$ be a subset of a cyclic group $\mathbb{Z}/...
4
votes
1
answer
192
views
Remainder terms of congruence sums in sets of positive density
Let $\mathcal{A} \subset \mathbb{N}$ be an infinite sequence with positive density, in the sense that
$$
\tag{1}
\lim_{x\to\infty} \frac{|\mathcal{A} \cap x|}{x} = c > 0,
$$
and define the ...
- 1,476
0
votes
0
answers
85
views
Almost "dense" subsets of primes (and may be not only primes)
Based on Erdos idea, a subset of natural numbers is "dense" if the sum of its reciprocals is infinite, in such case it contains an infinite set of arithmetic progressions.
Prime numbers are &...
- 185
16
votes
2
answers
768
views
What tools should I use for this problem?
Suppose we have $d$ cylindrical metal bars, with radius $l$, attached orthogonal to a support in random places:
Now we have to attach bars with radius $k$ EVENLY SPACED, with distance $p$ between ...
- 438
6
votes
0
answers
242
views
A density result for arithmetic progressions
Note: By upper/lower density, we shall mean the upper/lower asymptotic density as given here.
Question:
For any subset $S \subset \mathbb N$ with positive upper density, does there exists a $\...
- 2,486
6
votes
0
answers
161
views
Plausible ways to discover higher order fourier analysis
Szemeredi's Theorem is a difficult theorem that falls into the category of not obviously foundational or widely applicable in itself but where the search for proofs have led to a number of ...
- 4,552
5
votes
0
answers
296
views
A question on infinite arithmetic progressions
I was working on a problem that consisted of deciding if the language a finite automaton (the alphabet of which is $\{0,1\}$ and the words accepted are binary encoded positive integers) contains an ...
- 51
13
votes
1
answer
1k
views
Are there any papers about this observation of the distribution of the zeros of the zeta function?
Choose some $x > 1$. Then
$$
\lim_{T\to\infty} \sum_{\Im(\rho)<T}\cos(\ln(x)\Im(\rho))=-\infty
$$ where $\rho$ ranges over all zeros of the zeta function iff $x$ is prime or the power of some ...
- 133
3
votes
0
answers
122
views
Does there always exist a monochromatic solution to ma+mb = nc+nd when m,n are coprime and N is coloured using 4 colours?
Let $m \ge 2 ,n \ge 2$ be positive integers which are coprime (that means that the greatest common divisor of $m,n$ is $1$).
Is it possible to paint the set $\mathbf{N}$ of all natural numbers using $...
- 802
7
votes
1
answer
210
views
Arithmetic progressions in inverse image of totient function
I noticed on the OEIS that there are various sequences (e.g. A050515-A050520) that describe arithmetic progressions whose totients are all equal. For example, we have
$$\varphi(\{1,2\}) = 1$$
$$\...
- 705
2
votes
1
answer
263
views
Primes in modular arithmetic progression
Fix a prime $p$.
I want to get $k<p$ primes $p_1<\dots<p_k$ such that at every $i\in\{1,\dots,k\}$ we have
$$p_i\equiv (2i+1+c)\bmod p$$ where $c$ is fixed and $2k+1+c<p$ holds.
For a ...
- 13.4k
4
votes
2
answers
243
views
Binary words that are nonconstant on long arithmetic progressions
Let $w=x_0 x_1 x_2 \ldots$ be an infinite word, where each $x_i\in \{0,1\}$. For each positive integer $k$ (thought of as the jump size of an arithmetic progression) and each residue $0\leq a \leq k-...
- 17.3k
1
vote
1
answer
162
views
What are the hypotheses we should add for the generalizations of Furstenberg recurrence theorem?
In my question here I suggest a possibility for generalization of Furstenberg recurrence theorem needing some hypothesis for that generalization to be hold in the side of convergence of the below ...
- 2,198
6
votes
1
answer
1k
views
Is there any relationship between Szemerédi's theorem and Sunflower conjecture?
I have observed some similar things between a reformulation of the Sunflower conjecture (see also conjecture 1.3 in Improved bounds for the sunflower lemma) and Szemerédi's theorem such that for ...
- 2,198
0
votes
0
answers
34
views
Minimum size integer accommodating some divisors within some prescribed gaps
Assume we pick $t$ uniformly random integers $l_1$ to $l_t$ independently from $1$ to $2^v$.
Assume $k_1$ through $k_t$ are similarly picked from $1$ to $2^r$.
What is the minimum size of non-...
- 1,776
1
vote
1
answer
164
views
Arithmetic progressions, given a prime
I have recently become interested in reading a little more on certain directions regarding primes in arithmetic progressions (AP). I would appreciate specific paper references (with the journal and ...
user137748
7
votes
1
answer
603
views
Prime-like numbers that avoid Green-Tao? [duplicate]
I would like to understand the conditions that support
the Green-Tao Theorem, which established that
the primes contain arbitrarily long arithmetic progressions.
I am wondering:
Q. Is it difficult ...
- 147k
4
votes
1
answer
198
views
Primes in arithmetic progressions above a given threshold
Given co-prime $a,b$, Dirichlet's theorem states that there are infinitely many primes in the arithmetic progression $M = \{ a + bn : n \in \mathbb N\}$. Linnik's theorem asserts that the first such ...
- 183
-1
votes
1
answer
127
views
Sufficient conditions on $ a_i,b_i$ for $a_1\phi(n)+b_1, \cdots, a_k\phi(n)+b_k$ to be simultaneously prime infinitely often?
I am really interested in sufficient conditions on $a_i, b_i$ guaranteeing that the linear forms $a_1\phi(n)+b_1,\dots, a_k\phi(n)+b_k$ become simultaneously prime for infinitely many positive ...
- 2,198
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
220
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
585
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$ ...
- 24.7k
12
votes
2
answers
686
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
928
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
190
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
64
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}=\{\...
- 297
3
votes
1
answer
316
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