All Questions
24 questions
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
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.8k
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
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
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
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
13
votes
2
answers
674
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
743
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 ...
- 179
3
votes
1
answer
439
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 ...
- 501
2
votes
1
answer
297
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$.
...
- 18.8k
9
votes
1
answer
318
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 \...
- 32.1k
2
votes
1
answer
423
views
Essential clarifications on application of pigeonhole principle
In here Lemma $4$ using pigeonhole says:
For $T_1,\dots,T_s\in\Bbb R$ with $1\leq T_1,\dots,T_s<p$ and $\prod_{i=1}^sT_i > p^{s−1}$ and any integers $a_1,\dots,a_s$ there is an integer $t$ ...
user94040
1
vote
0
answers
118
views
Consecutive integers divisible by consecutive small numbers
Given $n$, what is the largest set of consecutive integers in $[n,2n]$ can we have so that each integer is divisible by a distinct element from $[\log n,2\log n]$ (no partiular order)? So apriori I am ...
- 13.9k
8
votes
1
answer
571
views
Subsets of [1..N] with no three-term arithmetic progressions and no large gaps
Let S be a subset of [1..N] containing no three-term arithmetic progression, and let h(S) be the size of the largest gap between two consecutive elements of S. By Roth's theorem, h(S) has to grow ...
- 19.2k
6
votes
0
answers
380
views
Large sets not containing arithmetic progressions of length 3 in intervals
Given a large enough natural number $N$, let $\Delta_N=\{A \subseteq [N, 2N]: A$ contains no arithmetic progressions of length $3 \},$ where for natural numbers $N<M$ we have $[N, M]=\{N, N+1, ..., ...
- 32.1k
12
votes
1
answer
2k
views
Squares in an arithmetic progression
Let $P(x;a,b) := \{an+b, 0\leq n \leq x \} $ denote an arithmetic progression. Further let $A(x;a,b)$ denote the number of elements of $P(x;a,b)$ that are squares. It's an old conjecture of Rudin ...
- 13k
13
votes
7
answers
3k
views
Special arithmetic progressions involving perfect squares
Prove that there are infinitely many positive integers $a$, $b$, $c$ that are consecutive terms of an arithmetic progression and also satisfy the condition that $ab+1$, $bc+1$, $ca+1$ are all perfect ...
- 625
6
votes
2
answers
1k
views
Inverse Length 3 Arithmetic Progression Problem for sets with positive upper density
It is a famous theorem of Roth, which Szemerédi famously generalized, that if a set of natural numbers has positive upper density then it contains arithmetic progressions of length $k$. The famous ...
- 26.9k
24
votes
4
answers
3k
views
What is the shortest route to Roth's theorem?
Roth first proved that any subset of the integers with positive density contains a three term arithmetic progression in 1953. Since then, many other proofs have emerged (I can think of eight off the ...
- 7,013
26
votes
5
answers
4k
views
Finitely many arithmetic progressions
A few years ago, somebody told me a lovely problem. I suspect there may be more to it (which I would be interested in learning), and would very much like to find a reference, it makes me uncomfortable ...
- 32.5k
28
votes
5
answers
9k
views
Erdos Conjecture on arithmetic progressions
Introduction:
Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.
Question:
I ...
- 4,952
15
votes
1
answer
835
views
Goldbach-type theorems from dense models?
I'm not a number theorist, so apologies if this is trivial or obvious.
From what I understand of the results of Green-Tao-Ziegler on additive combinatorics in the primes, the main new technical tool ...
- 12.6k
4
votes
2
answers
667
views
"half arithmetic progressions" in dense sets
Fix a positive real number d>0. Szemeredi's theorem implies that for every integer k, there exists an integer N(k,d) such that if A is a subset of the interval [1,N] with density greater than d >0, ...
- 13k