# 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(\...

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

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$), ...

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

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 $\...

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

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

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

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

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

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

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

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

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

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

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}{\...

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

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

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

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

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

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

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

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

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 $\...

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

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

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

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

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$$
$$\...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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}=\{\...

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