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
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,393
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
  • 11.5k
6 votes

Infinite set intersection with arithmetic progressions

There are only a countable infinity of arithmetic progressions, so list them as $A_1,A_2,\dotsc$. Then write out a list in which each $A_i$ occurs infnitely many times, e.g., $A_1,A_1,A_2,A_1,A_2,A_3,...
Gerry Myerson's user avatar
4 votes
Accepted

Beating trivial bound for $k$-AP-free sets in characteristic $k$

I think that this is known. A good source to check recent things would be https://arxiv.org/abs/2211.02588.
domotorp's user avatar
  • 18.3k
4 votes
Accepted

Goldbach conjecture reformulation

$K$ exists with the required property if and only if the Goldbach conjecture is false. Assume first that $K$ has the property in the original post. Then $K\geq 6$, and for every prime $q\in[K/2,K]$, ...
GH from MO's user avatar
  • 98.2k
3 votes

Number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$

Fix a smallish integer $m$, and assume for simplicity that $n$ is a multiple of $m$. Break $\{1,\dots,n\}$ into $n/m$ consecutive intervals of $m$ consecutive integers each. Each such interval must ...
Greg Martin's user avatar
  • 12.7k
3 votes

Expected number of coin flips before you see a $k$-term arithmetic progression of heads

See Maximal Arithmetic Progressions in Random Subsets by Benjamini, Yadin and Zeitouni, ECP 12: 365-376 (2007) and the erratum in ECP 17: 1-1 (2012). See also the extensions in M.-Z. Zhao and H.-Z. ...
ofer zeitouni's user avatar
3 votes

Capset problem but considering differences with bounded support

Oh, in retrospect I was being stupid. Obviously $F(n,D)\le 3^n (r_3(\Bbb{F}_3^D)/3^D)$ (for $D\le n$); this because you look at the $D$-dimensional cosets, and note that their intersections with $A$ ...
Zach Hunter's user avatar
  • 3,393
2 votes

Number of Salem–Spencer subsets of $\{1,2,3,\dots ,n\}$

Let $r_3(N)$ denote the maximum cardinality of a $3$-AP subset of $\{1,\dots,N\}$. It clear that $T(N)\ge 2^{r_3(N)}$. Meanwhile, it was proved by Balogh, Liu, and Sharifzadeh that we have $T(N) \le 2^...
Zach Hunter's user avatar
  • 3,393
2 votes

Are there infinitely long arithmetic progressions in every increasing sequence of positive integers with bounded gaps between consecutive terms?

It is well known and easy to see (as in the old math.se question An example showing that van der Waerden's theorem is not true for infinite arithmetic progressions) that $\mathbb N$ can be partitioned ...
bof's user avatar
  • 11.5k

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