  The Element Distinctness problem is to decide whether each character of an
input string is unique. The quantum query complexity of Element Distinctness is
known to be $\Theta(N^{2/3})$; the polynomial method gives a tight lower bound
for any input alphabet, while a tight adversary construction was only known for
alphabets of size $\Omega(N^2)$.
  We construct a tight $\Omega(N^{2/3})$ adversary lower bound for Element
Distinctness with minimal non-trivial alphabet size, which equals the length of
the input. This result may help to improve lower bounds for other related query
problems.

Quantum Physics