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

146
questions

0
votes

0
answers

37
views

### On probability of equifactorable numbers in arithmetic progression

Let $T$ be a parameter.
Fix $r$ with $|r|<T^{2x}$ and $A$ where $A>0$ is of size $T^{2x}$ where $x\in\{0,1\}$.
Consider the set of integers of form
$$r+kA$$
where $|k|$ is of size $T^{4x}$ ($k$ ...

0
votes

0
answers

124
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

132
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

127
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

124
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

88
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

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

1
vote

0
answers

67
views

### Symmetric Prime Tuples in arithmetic progressions [closed]

Some time ago I made a post How to make a pair of six-sided dice whose sum is always a prime number? on Math.StackExchange. Now that I'm finishing my studies I decided to approach the problem again ...

16
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

164
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

179
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

72
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

735
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

230
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

155
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

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

0
votes

0
answers

39
views

### Number of $k$-progressions that share exactly $m$ elements with a fixed $k$-progression

Let $A$ be a subset of a an abelian group $Z$. (For the remainder of the question, one can think of $A=\{1,\ldots,n\}$ and $Z = {\bf Z}$ if one likes, but feel free to post answers with different ...

3
votes

0
answers

104
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

197
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

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

3
votes

2
answers

232
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

156
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

161
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

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

3
votes

1
answer

179
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

123
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

953
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

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

12
votes

2
answers

527
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

661
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

847
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

169
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

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

2
votes

1
answer

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

5
votes

0
answers

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

2
votes

1
answer

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

3
votes

2
answers

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

2
votes

1
answer

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

2
votes

1
answer

262
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
vote

0
answers

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

7
votes

2
answers

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

2
votes

0
answers

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

1
vote

0
answers

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

5
votes

1
answer

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

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?

9
votes

1
answer

302
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

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