Lower bound on the element distinctness problem The element distinctness problem asks whether any two elements of the input
sequence $&lt;x_1,\ldots,x_n&gt;$ are equal? This problem has a lower bound of
$\Omega(n \log n)$ in the algebraic decision tree model when the $x_i$'s are
real numbers. My question is what is the lower bound if we restrict the $x_i$'s
to positive integers?
Such a lower bound for integer inputs is indeed known, and is not just a trivial consequence of the result for the reals:


  A. C.-C. Yao, Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains, SIAM J. Comput., 20(4), 655–668.


Rather, Yao has to re-prove the Milnor-Thom-Oleinik-Petrovski bound on the number of connected components of a semi-algebraic variety over $\mathbb{R}$ more or less from scratch to get it to work over $\mathbb{Q}$, where the notion of connectedness is a bit thornier. He also needs to assume that the problem is scale-invariant and "rationally dispersed" (see the paper), and only counts connected components of nonzero measure. These technical conditions already hint that it is not a simple consequence of the result over the reals.