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.
171 questions
6
votes
1
answer
243
views
Is it possible that the number of $\mathcal{T}$-algebras is an arithmetic progression?
For a single-sorted algebraic theory $\mathcal{T}$ denote by $t_n$ the number of $\mathcal{T}$-algebras with $n$ elements (up to isomorphism). Is there an example for $\mathcal{T}$ such that ...
- 63.1k
2
votes
1
answer
87
views
Explicit construction of integers with prescribed digit sum and residue class conditions
Let $q\geq 2$ be an integer, and $p,m\in \mathbb{N}$. Let $S_q$ be the function sum of digits in base $q$. If $\gcd(q-1,m)=1$, I was wondering if there is simple way to construct $k\in \mathbb{N}$ ...
- 23
2
votes
1
answer
71
views
APs in sumsets of exponential growing sequences
I posted this initially on SE, but after I didn't found a particular reference on it, I decided it would be more appropriate to post it here. A friend shared this observation with me and I thought ...
- 63
4
votes
2
answers
353
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 ...
- 791
5
votes
1
answer
297
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 \...
- 6,155
-8
votes
2
answers
410
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
325
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, ...
- 23
9
votes
2
answers
660
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$ ...
- 18.7k
5
votes
1
answer
151
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 ...
- 3,499
1
vote
0
answers
73
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,499
3
votes
0
answers
187
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(\...
- 3,499
4
votes
0
answers
157
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,499
2
votes
1
answer
224
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$), ...
- 1,561
3
votes
0
answers
167
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,499
3
votes
0
answers
327
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 $\...
- 330
4
votes
1
answer
251
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 ...
- 654
4
votes
1
answer
357
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$ ...
- 48.8k
3
votes
1
answer
334
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 ...
- 23k
1
vote
2
answers
389
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 ...
- 53
1
vote
0
answers
84
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 ...
- 3,499
5
votes
2
answers
268
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 ...
- 3,499
2
votes
1
answer
113
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 \...
- 3,499
2
votes
1
answer
300
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 ...
- 589
3
votes
1
answer
162
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 ...
- 17.9k
2
votes
0
answers
125
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 ...
- 1,042
0
votes
1
answer
295
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 ...
- 1
0
votes
0
answers
196
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 ...
- 130
4
votes
1
answer
460
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}{\...
- 1,990
5
votes
1
answer
322
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. ...
- 704
3
votes
1
answer
250
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 ...
- 3,499
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 ...
- 827
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:...
- 4,862
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 ...
- 4,862
5
votes
0
answers
215
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
214
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 ...
- 1,990
0
votes
0
answers
101
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 &...
- 185
16
votes
2
answers
797
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 ...
- 480
6
votes
0
answers
269
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,155
6
votes
0
answers
186
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 ...
- 4,862
5
votes
0
answers
313
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 ...
- 51
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 ...
- 133
3
votes
0
answers
137
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 $...
- 850
9
votes
1
answer
261
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$$
$$\...
- 807
2
votes
1
answer
273
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 ...
- 13.9k
4
votes
2
answers
259
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-...
- 18.7k
1
vote
1
answer
190
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 ...
7
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,826
1
vote
1
answer
177
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 ...
user137748
7
votes
1
answer
636
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 ...
- 151k