Skip to main content
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 ...
Joel David Hamkins's user avatar
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....
Terry Tao's user avatar
  • 114k
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$ ...
Greg Martin's user avatar
  • 12.8k
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 $$ \...
Alexander Kalmynin's user avatar
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\...
Ofir Gorodetsky's user avatar
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 $...
Keith Kearnes's user avatar
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 ...
Wlod AA's user avatar
  • 4,786
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$). ...
John Griesmer's user avatar
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 ...
Aaron Meyerowitz's user avatar
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 ...
Seva's user avatar
  • 23k
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 ...
Renan's user avatar
  • 121
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 ...
Robert Israel's user avatar
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&...
Mark Lewko's user avatar
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 ...
Wojowu's user avatar
  • 28.2k
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 ...
Will Sawin's user avatar
  • 148k
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 ...
Thomas Bloom's user avatar
  • 7,013
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 ...
Greg Martin's user avatar
  • 12.8k
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\...
Zach Hunter's user avatar
  • 3,499
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 ...
Wlod AA's user avatar
  • 4,786
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 ...
Ryan Alweiss's user avatar
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 ...
zeb's user avatar
  • 8,688
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&...
Ofir Gorodetsky's user avatar
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 $\...
Thomas Bloom's user avatar
  • 7,013
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$ ...
Fedor Petrov's user avatar
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 ...
Taras Banakh's user avatar
  • 41.8k
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 ...
Thomas Bloom's user avatar
  • 7,013
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=\...
Fedor Petrov's user avatar
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 ...
bof's user avatar
  • 13.4k

Only top scored, non community-wiki answers of a minimum length are eligible