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
4 votes
2 answers
287 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 ...
Sayan Dutta's user avatar
5 votes
1 answer
259 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 \...
Nate River's user avatar
  • 4,802
-8 votes
2 answers
365 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 \...
Family Values's user avatar
1 vote
1 answer
287 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, ...
Felix Fowler's user avatar
9 votes
2 answers
632 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$ ...
domotorp's user avatar
  • 18.3k
5 votes
1 answer
145 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 ...
Zach Hunter's user avatar
  • 3,375
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 ...
Zach Hunter's user avatar
  • 3,375
3 votes
0 answers
172 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(\...
Zach Hunter's user avatar
  • 3,375
4 votes
0 answers
128 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 ...
Zach Hunter's user avatar
  • 3,375
2 votes
1 answer
205 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$), ...
Johnny Cage's user avatar
  • 1,543
3 votes
0 answers
152 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 ...
Zach Hunter's user avatar
  • 3,375
3 votes
0 answers
234 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 $\...
RFZ's user avatar
  • 298
3 votes
1 answer
186 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 ...
Riemann's user avatar
  • 537
4 votes
1 answer
339 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$ ...
Dominic van der Zypen's user avatar
3 votes
1 answer
317 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 ...
Seva's user avatar
  • 22.8k
1 vote
2 answers
331 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 ...
Kai Wang's user avatar
1 vote
0 answers
75 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 ...
Zach Hunter's user avatar
  • 3,375
5 votes
2 answers
238 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 ...
Zach Hunter's user avatar
  • 3,375
2 votes
1 answer
108 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 \...
Zach Hunter's user avatar
  • 3,375
2 votes
1 answer
264 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 ...
Krishnarjun's user avatar
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 ...
Roland Bacher's user avatar
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 ...
Hhhhhhhhhhh's user avatar
  • 1,032
0 votes
1 answer
241 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 ...
Potheker's user avatar
0 votes
0 answers
183 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 ...
toshi's user avatar
  • 130
4 votes
1 answer
344 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}{\...
Joshua Stucky's user avatar
5 votes
1 answer
289 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. ...
Steffen Kionke's user avatar
4 votes
1 answer
234 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 ...
Zach Hunter's user avatar
  • 3,375
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 ...
Joe Shipman's user avatar
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:...
Ivan Meir's user avatar
  • 4,762
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 ...
Ivan Meir's user avatar
  • 4,762
5 votes
0 answers
190 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}/...
Killua Zoldyck's user avatar
4 votes
1 answer
201 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 ...
Joshua Stucky's user avatar
0 votes
0 answers
97 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 &...
tzimie's user avatar
  • 185
16 votes
2 answers
781 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 ...
Diego Santos's user avatar
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 $\...
Nate River's user avatar
  • 4,802
6 votes
0 answers
170 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 ...
Ivan Meir's user avatar
  • 4,762
5 votes
0 answers
303 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 ...
Irmak Sağlam's 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 ...
Mr.Mustache Man's user avatar
3 votes
0 answers
130 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 $...
Aditya Guha Roy's user avatar
7 votes
1 answer
226 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$$ $$\...
Marcel K. Goh's user avatar
2 votes
1 answer
265 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 ...
Turbo's user avatar
  • 13.6k
4 votes
2 answers
253 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-...
Pace Nielsen's user avatar
1 vote
1 answer
179 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 ...
zeraoulia rafik's 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 ...
zeraoulia rafik's user avatar
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-...
VS.'s user avatar
  • 1,816
1 vote
1 answer
172 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
618 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 ...
Joseph O'Rourke's user avatar
4 votes
1 answer
211 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 ...
Christoph Haase's user avatar
-1 votes
1 answer
137 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 ...
zeraoulia rafik's user avatar
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 ...
Yuzuriha Inori's user avatar