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

168
questions

4
votes

2
answers

327
views

### Number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$

I was wondering about sets that do not contain any $3$-term AP, and came to know that the official name of such a set is Salem–Spencer set. I was considering the question of counting the number of ...

5
votes

1
answer

279
views

### Expected number of coin flips before you see a $k$-term arithmetic progression of heads

Let $\{X_i\}_{i \in \mathbb Z_+} $ be independent fair coin flips. Write $S := \{i \in \mathbb Z_+\, | \, X_i \text{ is heads}\}$, and define, for an integer $k \geq 3$,
$$Y := \inf \{n \in \mathbb N \...

-8
votes

2
answers

374
views

### Infinite set intersection with arithmetic progressions

Let $\mathcal{A}$ be the set of all arithmetic progressions in $\mathbb{N}$ i.e
\begin{align*}
\mathcal{A} = \{a + b\mathbb{N} : a,b\in\mathbb{N}, b\neq 0\}.
\end{align*}
Does there exist a set $X \...

1
vote

1
answer

297
views

### Goldbach conjecture reformulation [closed]

As thought, the question below is a reformulation of the goldbach conjecture.
$ S = \{K - ap \mid a \geq 3, p \text{ is prime} < K/2 \} $, where $ a $ is an odd integer greater than or equal to 3, ...

9
votes

2
answers

639
views

### Does every big polyomino contain a big arithmetic progression?

Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP.
Is it true that for every $k$ ...

5
votes

1
answer

147
views

### Beating trivial bound for $k$-AP-free sets in characteristic $k$

Given integers $k,n\ge 1$, I shall write $\Bbb{Z}_k^n := (\Bbb{Z}/k\Bbb{Z})^n$.
Fix $k\ge 3$. Let $r_k(\Bbb{Z}_k^n)$ denote the cardinality of the largest $A\subset \Bbb{Z}_k^n$, such that $A$ does ...

1
vote

0
answers

68
views

### Progressions in finite fields with bounded hamming weight

Given $k\ge 2$ and an additive set $S$ (understood to live some implicit group $G$), define $$\Delta_k(S) := \left\{ d \in G: \bigcap_{i=1}^k (S+i\cdot d) \neq \emptyset \right\} $$(i.e., this is the ...

3
votes

0
answers

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

4
votes

0
answers

137
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
votes

1
answer

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

3
votes

0
answers

159
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

245
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

199
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

341
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

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

1
vote

2
answers

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

1
vote

0
answers

76
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

246
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

1
answer

110
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

269
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

159
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

115
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

253
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

185
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

368
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

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

3
votes

1
answer

240
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

97
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

1k
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

195
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}/...

5
votes

1
answer

210
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

99
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

782
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

254
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

175
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

305
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

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

9
votes

1
answer

245
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

266
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

254
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

181
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

2k
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

35
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

173
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

624
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

212
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

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