Computing the measure of the projection on the torus of a semialgebraic set

Question

Let $V \subseteq \mathbb{R}^n$ be a set cut out by a system of finitely many polynomial equations and inequalities with integer coefficients. Let $W$ be the set of all points in the box $[0,1]^n$ that are congruent mod 1 to some point of $V$. I would like to know whether or not there is an algorithm for determining if a given rational number is equal to, greater than or less than the Lebesgue measure of $W$. There may not be one, in light of this argument, which proves, in effect, that there is no algorithm to determine if $W=[0,1]^n$.

Note that one can effectively produce arbitrarily accurate lower bounds on the measure of $W$, by breaking up $V$ into small pieces and translating more and more of these pieces to $[0,1]^n$. The problem is, I don't see how to get arbitrarily accurate upper bounds on the measure of $W$.

Answer 1

I think that you can solve the problem at least for bounded $V$.

As far as I understand, $w\in W$ if and only if there exists $v\in V$ such that $w_i=frac(v_i)$, for any $1\leq i\leq n$, and such that $v\geq 0$. (Or something like this, as I can give different interpretations of what $\mod 1$ should mean.) Here $frac(.)$ denotes the function taking the fractional part. OK, this function is not semialgebraic (i.e. its graph is not a semialgebraic set).

However, if your $V$ is bounded, then you can replace $frac(.)$ with a semialgebraic function. Then your $W$ becomes semialgebraic, and you can do all sorts of things with $W$, and in particular decide your question algorithmically.

Otherwise, you might try doing something along the lines of the theory of $o$-minimal structures (i.e. roughly speaking allow more functions than just polynomials). Although perhaps this is doomed to fail, I don't know.

Answer 2

Update: I didn't see the "congruent mod 1" part. Sorry, my answer below probably won't be of much help. It was just for a set in the cube $[0,1]^n$ cut out by a system of inequalities. But still it is different question to ask if a measure is computable or if it is a certain rational.

By "cut out", I assume you mean there is a list of polynomial inequalities your set must satisfy.

I believe this measure is computable. You mention you can compute the measure from below. (The general principle is that a $\Sigma^0_1$ set has a lower-semicomputable measure, and $\{x\in[0,1]^n \mid p_1(x) < 0\ \wedge\ ...\ \wedge\ p_k(x) < 0 \}$ is a $\Sigma^0_1$ set.) But this set has a measure zero boundary (correct?), so the compliment can also be computed from below. So you can compute the measure of the set.

As for the question about determining if the answer is a rational, in general you can't determine if a computable number is a rational or if it is equal to a specific rational. (Let $x_n = 1+2^{-T(n)}$ where $T(n)$ is the length of time it takes the Turing machine $n$ to halt.)

However, you can if you can symbolically calculate that number. Take for instance the area under a polynomial with integer coefficients---just use calculus to solve for the answer. I am not sure off hand if this naturally extends to multivariate calculus, or if somehow Hilbert's 10 Problem comes in. (I'd be embarrassed if it was basic and something I should have learned in undergrad!)