Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
    
How hard is it to see that you can compute the measure of $V$? –  Andrej Bauer Jul 30 '12 at 14:29
    
@Andrej. Now that you mention this, I don't know, and this after a month of digging around in the literature and posting your comment as an MO question mathoverflow.net/questions/106862/… to which there were no responses, except in the case that V is bounded. Maybe no one knows how to estimate the volume of a general semialgebraic set from above. –  SJR Sep 22 '12 at 9:16

2 Answers 2

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.

share|improve this answer

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!)

share|improve this answer
    
Jason, The problem is this: Suppose, given $V$, I want to approximate the measure of $W$ with an error of no more than, say, a millionth. I have absolutely no idea how to do this in general, even though, as mentioned in the problem, I can effectively write down a sequence of rational numbers that converges to the measure of $W$. Moreover, ominously, one can't say too much about what $W$ looks like without bumping into Hilbert's Tenth Problem. –  SJR Jul 1 '12 at 19:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.