<p>Such a lower bound for integer inputs is indeed known, and is not just a trivial consequence of the result for the reals:</p>

<blockquote>
  <p>A. C.-C. Yao, <a href="http://dx.doi.org/10.1137/0220041">Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains</a>, SIAM J. Comput., 20(4), 655–668.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2016-07-19T03:30:52.300Z
2016-07-19T03:30:52.300Z
Joshua Grochow
<p>This was also done, independently, by Lubiw and Racz in 1991.  See <a href="http://www.sciencedirect.com/science/article/pii/089054019190034Y">http://www.sciencedirect.com/science/article/pii/089054019190034Y</a> .</p>

CC BY-SA 3.0
2016-07-19T13:06:00.680Z
2016-07-19T13:06:00.680Z
Jeffrey Shallit
<p>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?  </p>

CC BY-SA 3.0
2016-07-15T14:46:13.377Z
I may be missing something, but I don't think it makes a difference since there is a positive integer input in any of the $n!$ connected components of NO instances, and the algebraic decision tree must still separate them.
Sasho Nikolov
CC BY-SA 3.0
2016-07-19T03:31:46.363Z
@SashoNikolov: It is conceivable that having to only solve the problem on integer instances might be easier than solving it on all real instances. Also, the proof for the reals uses the notion of "connected component" in a pretty crucial way, so it's certainly not obvious that the proof carries over. Nonetheless, such a lower bound for the integers is known (see my answer).
Joshua Grochow
CC BY-SA 3.0
2016-07-19T14:30:55.187Z
@JoshuaGrochow thanks! I was pretty I was missing something.
Sasho Nikolov
CC BY-SA 3.0
2016-07-25T06:38:25.900Z
Thanks a lot. The comments helped me understand the nuances one needs to be aware of when the domain changes from reals to integers.
Sadguru
<decision-trees>
Lower bound on the element distinctness problem
Sadguru
# Lower bound on the element distinctness problem

(Asked by: username_0 on 2016-07-15)

The element distinctness problem asks whether any two elements of the input
sequence $$ 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?

**Tags:** decision-trees
> **Comments:**
> **username_1**: I may be missing something, but I don't think it makes a difference since there is a positive integer input in any of the $n!$ connected components of NO instances, and the algebraic decision tree must still separate them.  
> **username_2**: @SashoNikolov: It is conceivable that having to only solve the problem on integer instances might be easier than solving it on all real instances. Also, the proof for the reals uses the notion of "connected component" in a pretty crucial way, so it's certainly not obvious that the proof carries over. Nonetheless, such a lower bound for the integers is known (see my answer).  
> **username_1**: @JoshuaGrochow thanks! I was pretty I was missing something.  
> **username_0**: Thanks a lot. The comments helped me understand the nuances one needs to be aware of when the domain changes from reals to integers.  

---

## 2 answers

### Answer by username_2 on 2016-07-19. Score: 6 | Accepted answer

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](http://dx.doi.org/10.1137/0220041), 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.


---

### Answer by username_3 on 2016-07-19. Score: 6

This was also done, independently, by Lubiw and Racz in 1991. See <http://www.sciencedirect.com/science/article/pii/089054019190034Y> .


---

