We prove that any subset $A \subseteq [3]^n$ with $3^{ -n}|A| \ge (\log\log\log\log n)^{ -c}$ contains a combinatorial line of length $3$, i.e., $x, y, z \in A$, not all equal, with $x_i=y_i=z_i$ or $(x_i,y_i,z_i)=(0,1,2)$ for all $i = 1, 2, \dots, n$. This improves on the previous best bound of $3^{ -n}|A| \ge \Omega((\log^* n)^{ -1/2})$ of [D.H.J. Polymath, Ann. of Math. 2012].
Categories: math.CO cs.CC