65
votes
Accepted
A game on integers
I claim that Player A has a winning strategy in your game, and furthermore, it is a winning strategy for her simply to play the smallest available number.
Let me consider the game along with several ...
36
votes
Accepted
A proof of Van der Waerden's theorem using a weakened form of Szemeredi's theorem
As (implicitly) observed already in Szemerédi's celebrated paper
Szemerédi, Endre, On sets of integers containing no (k) elements in arithmetic progression, Acta Arith. 27, 199-245 (1975). ZBL0303....
28
votes
Accepted
What is the status on this conjecture on arithmetic progressions of primes?
Yes, this is unknown; it is even unknown (as GH from MO suspected in a comment) whether $P(p) \ge 3$ always. An equivalent statement to $P(p) \ge 3$ is that there exists an integer $x>0$ such $p+x$ ...
19
votes
Accepted
Are there any papers about this observation of the distribution of the zeros of the zeta function?
This is called Landau's formula. More precisely, if we extend the von Mangoldt function $\Lambda(n)$ to the function $\Lambda:\mathbb R_+\to \mathbb R$ by $\Lambda(x)=0$ for non-integer $x$, then
$$
\...
17
votes
Accepted
Sums of two squares in arithmetic progressions
The first result in this direction seems to be due to R. A. Smith, ``The Circle Problem in an Arithmetic Progression,'' Can. Math. Bull. 11 (2), 175–184 (1968). He showed that if we write
$$\sum _{n\...
14
votes
Accepted
Is it possible that the number of $\mathcal{T}$-algebras is an arithmetic progression?
Is it possible that the number of $\mathcal{T}$-algebras is an arithmetic progression?
Here is a near miss: Let $\mathcal{V}$ be the variety of $\mathbb Z_2$-sets. These may be thought of as algebras $...
13
votes
Is there an 11-term arithmetic progression of primes beginning with 11?
Siemion Fajtlowicz has been promoting the topic of $p$-long arithmetic progressions of primes which start with $p$ during 1993-4 (or longer). He and his colleague Micha Hofri got an $11$-long ...
13
votes
Accepted
A set with positive upper density whose difference set does not contain an infinite arithmetic progression
Let $\langle x\rangle$ denote the fractional part of a real number $x$ (i.e. $\langle x \rangle := x- \lfloor x\rfloor $, where $\lfloor x\rfloor $ is the greatest integer less than or equal to $x$).
...
12
votes
A game on integers
Joel's answer uses heavy machinery to give a much stronger result. Below is a strong result for $k=1$ using heavy computations (not mine.)
My suspicion is that for the question as asked there might ...
12
votes
Smallest set such that all arithmetic progression will always contain at least a number in a set
Considering the complement of $P$ in $[1,100]$, you are asking how large can a subset of $[1,100]$ be given that it does not contain any $10$-term arithmetic progression. The more general question
...
12
votes
Does every big polyomino contain a big arithmetic progression?
Alternative proof to Zachs, with best bound: The answer is no, and the largest $k$ possible is $k=4$.
The proof is due to a theorem by Dekking from 1978:
There exists a sequence on two symbols in ...
11
votes
Smallest set such that all arithmetic progression will always contain at least a number in a set
Using a tabu search procedure, I have found a solution for $|P|=17$, namely ${1, 11, 18, 25, 31, 32, 33, 36, 44, 51, 58, 65, 69, 70, 77, 84, 91}$. I don't know if this is optimal.
EDIT: Found a ...
11
votes
Accepted
Prime-like numbers that avoid Green-Tao?
This is likely impossible.
Indeed the largest sets known to be free of arbitrarily long arithmetic progressions asymptotically satisfy $| [ A \cap [1, n] | \lesssim_{k} n / \log^{k} n$ for all $k&...
10
votes
Accepted
Homogeneous van der Waerden
This is false already for $k=2,n=4$. Color an integer $m$ according to the parity of the exponent of $2$ in the prime factorization. Among $i+1,i+2,i+3,i+4$ at least one number is odd, and at least ...
10
votes
Accepted
Can we do better than random when constructing dense $k$-AP-free sets
We can take the set of all numbers in base $k$ that don't contain the digit $0$, for $k$ prime.
This is $k$-term-progression-free since every $k$-term progression in $\mathbb F_k$ is either constant ...
9
votes
A reformulation of Erdős conjecture on arithmetic progressions
This question is basically asking how good greedy-type constructions of sets without long arithmetic progressions can be. The answer is actually pretty terrible.
Firstly, as you note, if $f_k(n)$ is ...
9
votes
Infinitely many primes in particular progressions
Chen's theorem says that there are infinitely many numbers $k$ such that $k-2$ is prime and $k$ is either prime or the product of two primes ("$k$ is a $P_2$ number").
This theorem can be modified ...
9
votes
Accepted
Does every big polyomino contain a big arithmetic progression?
The answer is no. I will construct a connected subset $S\subset \Bbb{Z}^2$ without arbitrarily long arithmetic progressions. Since the grid is locally finite, $S$ must contain an infinite path $P\...
8
votes
Is there an 11-term arithmetic progression of primes beginning with 11?
For the sake of easy education let me mention the first simplest step toward finding $p$-long arithmetic progressions of primes which start with $p$.
Let $q$ be an arbitrary prime. Then the ...
8
votes
Accepted
Is there any relationship between Szemerédi's theorem and Sunflower conjecture?
I do not know of a direct connection to Roth or Szemerédi over the integers. However, the paper
N. Alon, A. Shpilka and C. Umans, On Sunflowers and Matrix Multiplication, 2012 IEEE 27th Conference ...
8
votes
Accepted
Binary words that are nonconstant on long arithmetic progressions
Any Sturmian word will work for Question 1. Before I prove this, I can't resist giving the standard example: the Fibonacci word. The Fibonacci word is defined as the fixed point of the iterative ...
8
votes
Accepted
Where odious numbers meet arithmetic progressions
Yes, we even know that the density of such $n$ is the expected one.
A. O. Gelfond proved in 1968, in a short paper ("Sur les nombres qui ont des propriétés additives et multiplicatives données&...
8
votes
Accepted
Does Szemerédi's theorem hold for sets with positive upper Banach density?
Yes. As Martin says, this is often how the theorem is stated. It also follows immediately from the also common finitary form:
For all $\delta>0$ and $k\geq 1$, if $N$ is large enough depending on $\...
7
votes
Accepted
Partitioning the positive integers into finitely many arithmetic progressions
Any progression (if they are all infinite, of course, but otherwise the statement is clearly wrong) should have its initial term $a$ not greater than the difference $d$. Indeed, if $a>d$, and $a-d$ ...
7
votes
Accepted
Extension of Dirichlet's Arithmetic Progression Theorem
Consider the arithmetic progressions $2+3\mathbb N$ and $1+5\mathbb N$ and observe that if $2+3k$ is prime, then $k$ is odd. On the other hand, if $1+5k$ is prime, then $k$ should be even. So, for any ...
7
votes
A weak form of the Erdős-Turán conjecture
The answer to both questions is almost certainly yes, but this has not been proven. It remains an open question even for progressions of length 3 (although the current bounds are pretty close).
For ...
7
votes
A set with positive upper density whose difference set does not contain an infinite arithmetic progression
A similar to John Griesmer's example is the set $S:=\{\lfloor n\alpha\rfloor,n=1,2,\ldots\}$, where $\alpha>100$ is an irrational number. Note that $\lfloor n\alpha\rfloor-\lfloor k\alpha\rfloor=\...
7
votes
Infinite set intersection with arithmetic progressions
If $A$ is an infinite subset of $\mathbb N$, a random subset $X\subseteq\mathbb N$ will satisfy the condition $|A\cap X|=|A\cap X^c|=\aleph_0$ with probability one. Inasmuch as there are only ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
arithmetic-progression × 171nt.number-theory × 110
co.combinatorics × 54
prime-numbers × 52
additive-combinatorics × 49
analytic-number-theory × 33
reference-request × 15
ramsey-theory × 5
prime-number-theorem × 5
sequences-and-series × 4
open-problems × 4
conjectures × 4
graph-theory × 3
set-theory × 3
discrete-geometry × 3
infinite-combinatorics × 3
divisors-multiples × 3
sumsets × 3
lo.logic × 2
measure-theory × 2
ds.dynamical-systems × 2
fourier-analysis × 2
asymptotics × 2
ergodic-theory × 2
forcing × 2