  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).
