| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

7. Near Arithmetic Progressions

Given $t,d\in\mathbb{N}$ and $w\in\mathbb{N}_0$, a $(t,d,w)$-progression is a set of the form \[ B(b,t,d,w):=\bigcup_{i=0}^{t-1}[b+id,b+id+w] \] for some $b\in\mathbb{N}_0$. A set $A\subseteq\mathbb{N}$ nearly contains a $(t,d,w)$-progression if there is a $(t,d,w)$-progression $B(b,t,d,w)$ such that $A\cap [b+id,b+id+w]\neq\emptyset$ for all $i=1,\ldots,t-1$.

Given $t\in\mathbb{N}$, let $g_t(n)$ be the largest element of $\{0,\frac{1}{n},\frac{2}{n},\ldots,1\}$ such that there is $A\subseteq[1,n]$ satisfying:
  1. $\frac{A\cap[1,n]}{n}\geq g_t(n)$, and
  2. $A$ does not nearly contain a $(t,d,w)$-progression, where $d$ is a power of $2$ and $\frac{w}{d}<\frac{d}{n}$.

    1.     A positive answer to the following conjecture would imply the Erdős-Turán conjecture: if $A\subseteq\mathbb{N}$ is such that $\sum_{a\in A}\frac{1}{a}$ diverges, then $A$ contains arbitrarily long finite arithmetic progressions (see chapter 15 of the workshop book).

      Add remark

      Conjecture 7.1.

      [Steven Leth] For all $t\in\mathbb{N}$ and sufficiently large $n$, \[ g_t(n)<\frac{1}{(\log n)^{\log \log n}}. \]

        •     It is known that for every $t\in\mathbb{N}$ and $\epsilon>0$, $g_t(n)>\frac{1}{n^\epsilon}$ for sufficiently large $n$. The following is a weaker form of the previous conjecture, which appears to still be interesting and is unresolved.

          Add remark

          Conjecture 7.2.

          [Steven Leth] For all $t,k\in\mathbb{N}$ and sufficiently large $n$, \[ g_t(n)<\frac{1}{(\log n)^k}. \]

              Cite this as: AimPL: Nonstandard methods in combinatorial number theory, available at http://aimpl.org/nscombinatorial.