An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants $k>2$. Specifically, the best known upper bound is $O(N^{(3/4)-1/(2^{k+2}-4)})$ (Belovs, FOCS 2012), while the best known lower bound for $k >= 2$ is $\Omega(N^{2/3} + N^{(3/4)-1/(2k)})$ (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018).
For any constant $k >= 4$, we improve the lower bound to $\Omega(N^{(3/4)-1/(4k)})$. This yields, for example, the first proof that $4$-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree.
As a secondary result, we give a simple construction of an approximating polynomial of degree $O(N^{3/4})$ that applies whenever $k <= polylog(N)$.