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.

Filter by
Sorted by
Tagged with
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$ ...
user avatar
  • 12.8k
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 ...
user avatar
  • 120
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}{\...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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:...
user avatar
  • 4,350
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 ...
user avatar
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 ...
user avatar
  • 4,350
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}/...
user avatar
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 ...
user avatar
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 &...
user avatar
  • 185
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 ...
user avatar
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 $\...
user avatar
  • 1,149
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 ...
user avatar
  • 4,350
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
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$$ $$\...
user avatar
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 ...
user avatar
  • 12.8k
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-...
user avatar
  • 14.8k
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 ...
user avatar
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 ...
user avatar
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-...
user avatar
  • 1,708
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 123
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$ ...
user avatar
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 ...
user avatar
  • 169
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 ...
user avatar
  • 143
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} \...
user avatar
  • 515
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}=\{\...
user avatar
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 ...
user avatar
  • 389
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 ...
user avatar
  • 18.6k
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 ...
user avatar
  • 39
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 ...
user avatar
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$. ...
user avatar
  • 17.1k
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 ...
user avatar
  • 1,206
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 ...
user avatar
  • 1,179
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 ...
user avatar
  • 1,179
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^...
user avatar
  • 12.8k
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 $...
user avatar
  • 12.8k
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 ...
user avatar
  • 3,686
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?
user avatar
  • 3,686
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 \...
user avatar
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 $...
user avatar