Lower bounds for algebraic computation trees with integer inputs

Let W ⊃ Rⁿ be scale-invariant and rationally dispersed, i.e., x member of W implies λx member of W for all real λ > 0; and the rationals are dense in both W and Rⁿ - W. It in shown that, in the algebraic computation tree model, the problem of deciding whether an input x member of Rⁿ with integer coordinates is a member of W has complexity Ω(log₂β(W) - 2n), where β(W) is the the number of connected components of W that are not of measure 0. This theorem can be used to prove tight lower bounds for the integral-constrained form of many basic problems, such as Element Distinctness, Set Disjointness, Finding Convex Hull, etc. Through further transformations, it leads to lower bounds for problems such as Integer Max Gap and Closest Pair of a simple polygon. The proof involves a nontrivial extension of the Milnor-Thom techniques for finding upper bounds on the Betti numbers of algebraic varieties.