Skip to main content
MathOverflow

Return to Question

added 187 characters in body
Source Link
Zach Hunter
Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24

We write $[N]$ to denote $\{1,\dots,N\}$. We say a set $S$ is $k$-AP-free if it lacks non-trivial arithmetic progressions of length $k$.

We define the 2-color van der Waerden number, $w(2;k)$, to be the largest integer $N$ where $[N]$ can be partitioned into two $k$-AP-free sets. For general $k$, the best lower bound is $w(2;k)\ge 2^k/k^{o(1)}$ and is achieved by essentially using a uniformly random partition (and then using LLL to ensure a secondary correction phase succeeds).

I am curious about a related quantity. Let $d(1/2,k)$ be the largest $N$ where there exists a $k$-AP-free set $S\subset [N]$ with $|S| \ge N/2$. By pigeonhole, we have that $d(1/2,k) \ge w(2;k)$.

Questions

Do we know if $d(1/2,k)\gg 2^k$, or is the inequality above the limit of our knowledge currently? Edit: actually, it’s straight-forward to prove $d(1/2,k) \ge 2^k/(e^2+o(1))$ by probabilistic method (first include each element with prob $1/2+1/k$ then delete a member of each $k$-AP).

Is it reasonable to suspect $d(1/2,k) \le (2+o(1))^k$ (i.e. that for this density we can’t do much better than random)? I think such an upper bound is expected for $w(2;k)$.

We write $[N]$ to denote $\{1,\dots,N\}$. We say a set $S$ is $k$-AP-free if it lacks non-trivial arithmetic progressions of length $k$.

We define the 2-color van der Waerden number, $w(2;k)$, to be the largest integer $N$ where $[N]$ can be partitioned into two $k$-AP-free sets. For general $k$, the best lower bound is $w(2;k)\ge 2^k/k^{o(1)}$ and is achieved by essentially using a uniformly random partition (and then using LLL to ensure a secondary correction phase succeeds).

I am curious about a related quantity. Let $d(1/2,k)$ be the largest $N$ where there exists a $k$-AP-free set $S\subset [N]$ with $|S| \ge N/2$. By pigeonhole, we have that $d(1/2,k) \ge w(2;k)$.

Questions

Do we know if $d(1/2,k)\gg 2^k$, or is the inequality above the limit of our knowledge currently?

Is it reasonable to suspect $d(1/2,k) \le (2+o(1))^k$ (i.e. that for this density we can’t do much better than random)? I think such an upper bound is expected for $w(2;k)$.

We write $[N]$ to denote $\{1,\dots,N\}$. We say a set $S$ is $k$-AP-free if it lacks non-trivial arithmetic progressions of length $k$.

We define the 2-color van der Waerden number, $w(2;k)$, to be the largest integer $N$ where $[N]$ can be partitioned into two $k$-AP-free sets. For general $k$, the best lower bound is $w(2;k)\ge 2^k/k^{o(1)}$ and is achieved by essentially using a uniformly random partition (and then using LLL to ensure a secondary correction phase succeeds).

I am curious about a related quantity. Let $d(1/2,k)$ be the largest $N$ where there exists a $k$-AP-free set $S\subset [N]$ with $|S| \ge N/2$. By pigeonhole, we have that $d(1/2,k) \ge w(2;k)$.

Questions

Do we know if $d(1/2,k)\gg 2^k$, or is the inequality above the limit of our knowledge currently? Edit: actually, it’s straight-forward to prove $d(1/2,k) \ge 2^k/(e^2+o(1))$ by probabilistic method (first include each element with prob $1/2+1/k$ then delete a member of each $k$-AP).

Is it reasonable to suspect $d(1/2,k) \le (2+o(1))^k$ (i.e. that for this density we can’t do much better than random)? I think such an upper bound is expected for $w(2;k)$.

Source Link
Zach Hunter
Zach Hunter
  • 3.5k
  • 2
  • 11
  • 24

Can we do better than random when constructing dense $k$-AP-free sets

We write $[N]$ to denote $\{1,\dots,N\}$. We say a set $S$ is $k$-AP-free if it lacks non-trivial arithmetic progressions of length $k$.

We define the 2-color van der Waerden number, $w(2;k)$, to be the largest integer $N$ where $[N]$ can be partitioned into two $k$-AP-free sets. For general $k$, the best lower bound is $w(2;k)\ge 2^k/k^{o(1)}$ and is achieved by essentially using a uniformly random partition (and then using LLL to ensure a secondary correction phase succeeds).

I am curious about a related quantity. Let $d(1/2,k)$ be the largest $N$ where there exists a $k$-AP-free set $S\subset [N]$ with $|S| \ge N/2$. By pigeonhole, we have that $d(1/2,k) \ge w(2;k)$.

Questions

Do we know if $d(1/2,k)\gg 2^k$, or is the inequality above the limit of our knowledge currently?

Is it reasonable to suspect $d(1/2,k) \le (2+o(1))^k$ (i.e. that for this density we can’t do much better than random)? I think such an upper bound is expected for $w(2;k)$.