16
$\begingroup$

A subset $S$ of $\mathbb{R}^n$ is "bounded away from integer points" if for some positive $\epsilon$ every point in $S$ lies at a distance of at least $\epsilon$ from $\mathbb{Z}^n$. For example the line $x+y=1/2$ in $\mathbb{R}^2$ is bounded away from integer points, but the curve $x^2+y=1/2$ is not, because the points $(n+\frac{1}{4n},-n^2-\frac{1}{16n^2})$ for $n=1,2,\ldots$ lie on this curve.

Question: Can anyone give an algorithm to determine whether a system of polynomial equations with real algebraic coefficients cuts out a subset $S$ of $\mathbb{R}^n$ that is bounded away from integer points? Is there a simple description of all such subsets $S$?

Remark: I have a vague notion that if $S$ is bounded away from integer points then this must be ``trivially'' verifiable, perhaps because $S$ projects on a linear affine subset of $\mathbb{R}^n$ that is obviously bounded away from integer points, but this is little more than guesswork. I don't actually know that the problem is decidable, but I would be surprised if it were not.

UPDATE: (I'll use this section to collect my latest thoughts on the problem.)

The situation is fairly transparent in $\mathbb{R}^2$, and the real problem is how things generalize to higher dimensions. Let $S$ be as above. Let $\lfloor\cdot\rfloor$ be the floor function, which will be applied to points coordinatewise. Then I propose the following conjecture:

There exists some translate of $S$ bounded away from integer points if and only if the set of all points $\lfloor p\rfloor$ for $p\in S$ is contained in a finite union of linear-affine subspaces of $\mathbb{R}^n$ (which will be defined over the rationals).

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ There are examples other than hyperplanes: consider the hyperbola in $\mathbb{R}^2$ whose asymptotes are lines $x=1/2$ and $y=1/2$. $\endgroup$
    – Boris Bukh
    Commented Jan 28, 2011 at 13:43
  • $\begingroup$ Interesting question, but I'm not sure I share your optimism. Is there any reason why this problem should be considered over the reals (versus, say, bounded away from the Gaussian integers over the complexes)? $\endgroup$
    – Thierry Zell
    Commented Jan 28, 2011 at 16:09
  • $\begingroup$ @Thierry: I suspect that the problems is decidable only because I can't find any hard-to-verify examples of sets bounded away from integer points. For example in the plane we have certain lines with rational slope, and examples like Boris mentioned in his comment, such as $(x-1/2)(y-1/2)=1$, where the branches at infinity are asymptotic to certain lines with rational slope. I don't know any more subtle examples. Does the problem get harder in higher dimensions? I don't know. As for the Gaussians and the complexes, maybe this boils down to the same problem... I'll have to think about that. $\endgroup$
    – Sidney Raffer
    Commented Jan 28, 2011 at 16:42
  • $\begingroup$ A trivial but rather large set of examples that I think has gone unmentioned would be bounded sets, e.g., that determined by $x^2+y^2=3$. $\endgroup$
    – Gerry Myerson
    Commented Jan 29, 2011 at 5:28
  • $\begingroup$ @Gerry: Yes, and by quantifier elimination over real closed fields, we can recognize all such examples algorithmically. So only unbounded sets pose a problem $\endgroup$
    – Sidney Raffer
    Commented Jan 29, 2011 at 6:08

1 Answer 1

Reset to default
2
$\begingroup$

This is not a really an answer, but you might want to look at the papers

MR1852803 (2002e:11085) Vâjâitu, Marian(R-AOS); Zaharescu, Alexandru(R-AOS) Integer points near hyperelliptic curves. (French summary) C. R. Math. Acad. Sci. Soc. R. Can. 23 (2001), no. 3, 84–90. 11J25 (11D75 11G30)

and

MR1689552 (2001a:11117) Huxley, M. N.(4-WALC-SM) The integer points close to a curve. III. Number theory in progress, Vol. 2 (Zakopane-Kościelisko, 1997), 911–940, de Gruyter, Berlin, 1999. 11J54 (11P21)

The latter seems particularly relevant to your specific question.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Igor. If you have a link to Huxley's paper I could sure use it.... I have no way around the paywalls at present. $\endgroup$
    – Sidney Raffer
    Commented Jan 28, 2011 at 17:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .