I have stumbled upon this problem in a Number Theory book and got stuck with it.
The problem states:
Given the set $(1,2,...,N)$, Prove that if $N$ is large enough one can choose a subset of at least $N^{0.63}$ integers such that no $3$ elements chosen form an arithmetic progression.
The problem reminds me a lot of Szemerédi's Theorem, but not quite the same. Also you are not supposed to use that here, since the book has that in a later chapter.
The difficult part is that I have no clue where $0.63$ is coming from and it just makes searching for a solution or strategy way harder.
Anyone has a clue on this?
Alright. Here is what I got till now. So if we consider the numbers in base $3$ that only use $0,1$-s we get a good set. By this I mean that these numbers will not have an arithmetic progression, this can be checked easily. Now to have a bound on how many numbers are there like this we can consider that if $n$ has $3^{k-1}$ as it's highest digit in base $3$, then we can say $n^{0.63}<n^{log_3(2)}<(3^k)^{log_3(2)}=2^k$, and we can create $2^k$ numbers that have $3^{k-1}$ as their highest digit in base $3$. However this argument only holds true if $n$ is a certain type, namely all of these numbers that we can create are smaller than $n$, so $n$ is greater than $1111...1$ $(k)$ $1$-s in base $3$. But this is not exactly what the problem asks. I get that this gives infinitely many good $n$-s, like $n=4$ is a good choice, but we need something like a limit from where all numbers are good don't we?
Also I still have no idea what to make of the fact that $0.63<1-\dfrac{1}{e}$