The Six-Dimensional Tarski Problem is $\mathrm{\Omega }({\log }^{3}n)$-Hard

We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n{]}^d\to [n{]}^d$, where querying $x$ returns $f(x)$. For fixed $d\ge 2$, earlier work established a lower bound of $\mathrm{\Omega }((\log n{)}^2)$ and an upper bound of $O_d((\log n{)}^{\lceil (d+2)\mathrm{/}3\rceil })$ for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to $\text{Tarski}(n,d)={\mathrm{\Omega }}_d((\log n{)}^{2+\lfloor {\log }_3(d\mathrm{/}2)\rfloor })$. In particular, we obtain the optimal $\mathrm{\Theta }((\log n{)}^3)$ deterministic query complexity in six dimensions.