Skip to main content
MathOverflow

Return to Answer

Changed formatting of density calculation for clarity.
Source Link
Thomas Bloom
Thomas Bloom
  • 7k
  • 1
  • 39
  • 59

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 or contains $0$, thus any $k$-term progression in $\mathbb Z$ takes all possible values in the last nonconstant digit.

The intersection with $[k^n]$ has density $(k-1)/k^n \approx e^{-n/k}$$(\frac{k-1}{k})^n \approx e^{-n/k}$, letting us take $n \approx k \log 2$, for a lower bound of $k^{ k (\log 2-o(1))}$, which is superexponential in $k$.

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 or contains $0$, thus any $k$-term progression in $\mathbb Z$ takes all possible values in the last nonconstant digit.

The intersection with $[k^n]$ has density $(k-1)/k^n \approx e^{-n/k}$, letting us take $n \approx k \log 2$, for a lower bound of $k^{ k (\log 2-o(1))}$, which is superexponential in $k$.

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 or contains $0$, thus any $k$-term progression in $\mathbb Z$ takes all possible values in the last nonconstant digit.

The intersection with $[k^n]$ has density $(\frac{k-1}{k})^n \approx e^{-n/k}$, letting us take $n \approx k \log 2$, for a lower bound of $k^{ k (\log 2-o(1))}$, which is superexponential in $k$.

Source Link
Will Sawin
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

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 or contains $0$, thus any $k$-term progression in $\mathbb Z$ takes all possible values in the last nonconstant digit.

The intersection with $[k^n]$ has density $(k-1)/k^n \approx e^{-n/k}$, letting us take $n \approx k \log 2$, for a lower bound of $k^{ k (\log 2-o(1))}$, which is superexponential in $k$.