MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Definition: Let $h$ be a polynomial in $n$ variables, then : $\gamma(h,r,R):=\{ v \in \mathbb{Z}^{n} : \vert h(v) \vert \leq r, \Vert v \Vert < R \}$

Let $\omega : \mathbb{Z}^{n} \to \{ 0 , 1\}$ be a function.

Definition : $\omega$ is algebraically normal if for all $h$ polynomial and $\forall r \geq 0$ s. t. $\vert \gamma(h,r,\infty) \vert = \infty$ : $$ \lim\limits_{R \to \infty} \frac{\vert \omega^{-1}(0) \cap \gamma(h,r,R) \vert}{\vert \gamma(h,r,R) \vert} = \frac{1}{2} $$

Is there such an algebraically normal function $\omega$, for all $n \geq 2$ ?

Remark on groups : This question could be generalized by replacing $\mathbb{Z}^{n}$ by a countable subset of an Euclidean space $\mathbb{R}^{n}$ or an Hyperbolic space $\mathbb{H}^{n}$ (which are diffeomorphic), or also a separable Hilbert space $H$ (by taking $h$ a polynomial in finitely many variables). As an application, a coarsely embeddable finitely generated group $\Gamma$ (with its word metric) into $\mathbb{R}^{n}$, $\mathbb{H}^{n}$ or $H$, could be called algebraically normal if there is such an embedding, admitting an algebraically normal function $\omega$.
The question becomes : Is there an algebraically normal group ?

share|cite|improve this question
Cross-posted on MSE – Sebastien Palcoux Aug 6 '13 at 10:46
When you say "real algebraic curve", do you mean "function defined by an ordered pair of polynomials"? That is not the usual definition of real algebraic curve. – S. Carnahan Aug 6 '13 at 13:27
@S.Carnahan, I mean a function from $\mathbb{R}$ to $\mathbb{R}^{2}$ whose range is the zeros of a polynomial in two variables or defined by an ordered pair of polynomials in one parameter. Is there a name for this class of curves ? – Sebastien Palcoux Aug 6 '13 at 14:20
Your second case essentially contains your first: If $f(t)$ and $g(t)$ are two polynomials in one parameter, then there is a nonzero polynomial $h$ so that $h(f(t), g(t))=0$. Moreover, the real points of $h(x,y)=0$ will be the image of $(f,g)$, plus finitely many additional points. – David Speyer Aug 6 '13 at 18:49
I believe I have a proof that there is no coloring for $\mathbb{Z}^2$; see update below. – David Speyer Aug 13 '13 at 0:42
up vote 2 down vote accepted

$\def\ZZ{\mathbb{Z}}\def\RR{\mathbb{R}}$I suspect this is false! At least, I'll show that a similar statement is false for $\ZZ^4$ and I'll sketch how I think a similar construction should work for $\ZZ^2$.

Fix a coloring $\omega : \ZZ^4 \to \{ 0, 1 \}$. Define a directed graph whose vertices are quadruples $(p,q,p',q') \in \ZZ_{\geq 0}^4$ obeying $p q' - q p' = \pm 1$, $p \leq p'$, $q \leq q'$ and where there is an edge $(p,q, p', q') \to (p', q', p'', q'')$ if there is a positive integer $a$ such that $(p'', q'') = a (p', q') + (p,q)$.

Case 1 There is some vertex $(p,q,p',q')$ all of whose descendents are of the opposite color from it.

Then, for $a > 0$, the sequence of vertices $(p', q', a p' + p, a q'+q)$ is monochromatic. We can describe points of the form $(p', q', a p' + p, a q'+q)$ as $$\left\{ (w,x,y,z) : (w-p')^2 + (x-q')^2 + \left( p' (z-q) - q' (y-p) \right)^2 < 1 \right\}.$$ (Since $\det \left( \begin{smallmatrix} p & p' \\ q & q' \end{smallmatrix} \right) = \pm 1$, we see that $GCD(p',q')=1$ so the condition that $a$ is integral comes for free.) So, if we following this inequality in the direction of large $z$, all the points have the same color.

Case 2 There is an infinite monochromatic path starting from $(1,0,0,1)$.

Let the vertices on this path be $(p_{n-1}, q_{n-1}, p_n, q_n)$ with $$(p_{n+1}, q_{n+1}) = a_n (p_n, q_n) + (p_{n-1}, q_{n-1}).$$

Let $\alpha$ be the value of the continued fraction $a_0+1/(a_1+1/(a_2+1/(\cdots)))$. Then $p_i/q_i$ are the convergents of $\alpha$. (A good reference for all the facts I am using about continued fractions is Chapter X in Hardy and Wright, Introduction to the Theory of Numbers.)

We now quote Theorem 172 from Hardy and Wright:

Suppose that $\zeta$ is a real number $>1$, that $P$, $Q$, $R$, $S$ are integers with $Q>S>0$ and $PS-QR = \pm 1$, and $\alpha = (P \zeta+R)/(Q \zeta+S)$. Then $P/Q$ and $R/S$ are consecutive convergents of $\alpha$. Conversely, if $P/Q$ and $R/S$ are consecutive convergents in lowest terms, then there is a $\zeta$ such that these conditions hold.

Although Hardy and Wright don't point it out, the condition $PS-QR = \pm 1$ forces $GCD(P,Q) = GCD(R,S)=1$, so we get to conclude not only that $P/Q = p_n/q_n$ and $R/S = p_{n+1}/q_{n+1}$ as fractions, but actually that $(P,Q,R,S) = (p_n, q_n, p_{n+1}, q_{n+1})$. Also, they don't state the converse, but they are proving it.

We restate the hypotheses of their theorem:

The quadruple $(P,Q,R,S)$ is of the form $(p_n, q_n, p_{n+1}, q_{n+1})$ if and only if $Q>S>0$, $PS-QR = \pm 1$ and $(R-\alpha S)/(Q\alpha - P) > 1$.

We can rewrite $u>1$ as $|1-(u-1)/(1+(u-1)^2)| < 1$ so

The quadruple $(P,Q,R,S)$ is of the form $(p_n, q_n, p_{n+1}, q_{n+1})$ if and only if $Q>S>0$ and $$ ((PS-QR)^2-1)^2 + (1-(u-1)/(1+(u-1)^2))^2 <1$$ where $u = (R-\alpha S)/(Q\alpha - P)$.

This is an inequality of rational functions, but $F/G < 1$ is equivalent to $FG < G^2$. So we have a polynomial inequality with real coefficients which, together with $Q>S>0$, encodes that $(P,Q,R,S)$ is of the form $(p_n, q_n, p_{n+1}, q_{n+1})$. By construction, this means that as we go to $\infty$ along points satisfying this polynomial inequality and lying in the cone $Q>S>0$, we will see only one color for $\omega$.

If we wanted to work the same trick for $\ZZ^2$, we would need an inequality for two variables which forces $(p,q)$ to be of the form $p_n/q_n$. Theorem 184 in Hardy and Wright looks good:

If $\left| \alpha - \frac{p}{q} \right| < \frac{1}{2 q^2}$, then $p/q$ is a convergent.

But it's a trap! This forces $p/q = p_n/q_n$, but it doesn't force $p/q$ to be in lowest terms. I suspect sufficient cleverness could route around this, but I didn't see how.

UPDATE This is also false for $\ZZ^2$. I don't have the energy to write down a complete proof, but here is the sketch.

Case 1 There are slopes $0 < m_1 < m_2$ and a radius $R$ such that the region $$\left\{ (x,y) : m_1 < \frac{y}{x} < m_2, \ x^2+y^2 > R^2, \ GCD(x,y)=1 \right\}$$ is monochromatic. Then we can find a fraction $p/q$ with $m_1 < p/q < m_2$. All points on the line $py-qx=1$ for $y>>0$ will lie in the above region, so we have a monochromatic ray.

Case 2 Every region as above is bi-colored.

Mimicing fedja's argument here, recursively build an $a$ so that all sufficiently large solutions to $|x^5 - a^5 y^5| <1$ have the same color.

share|cite|improve this answer
Thank you @DavidSpeyer for this very nice answer ! Do you suspect the non-existence of an "algebraically normal" coloring for $\mathbb{Z}^{4}$ independent of the choice of a coarse embedding (see the remarks on groups) ? If so, the group $\mathbb{Z}^{4}$ would be non-"algebraically normal". Do you suspect the existence of "algebraically normal" groups ? – Sebastien Palcoux Aug 8 '13 at 20:31

It is possible that the OP intended $h$ to have integer coefficients. If so, the answer is yes. More generally, the answer is "yes" if we restrict $h$ to any countable list of polynomials.

Let $p: \mathbb{Z}^2 \to \mathbb{Z}_{\geq 0}$ be an injective polynomial; such polynomials are constructed here. I will show that, if we restrict $h$ to a countable list of polynomials, then $(1/2) + (1/2) (-1)^{\lfloor \phi p(x,y) \rfloor}$ works for almost all real numbers $\phi$.

We have the following Theorem of Bernstein:

If $b_n$ is a sequence of distinct integers then, for almost all $\theta$, the sequence $\theta b_n \bmod 1$ is equidistributed.

(Bernstein's paper is in German, but the statement is repeated on the Wikipedia page for equidistributed.) Since a union of countably many sets of measure zero is of measure zero, this shows:

Let $\mathcal{B}$ be a countable collection of sequences of distinct integers. (I.e. each sequence in $\mathcal{B}$ is a sequence of distinct integers.) Then, for almost all $\theta$, for all $(b_1, b_2, \ldots)$ in $\mathcal{B}$, the sequence $\theta b_n \bmod 1$ is equidistributed.

For every polynomial $h$ with integer coefficients, and every integer $r$, such that there are infinitely many solutions to $|h(x,y)| \leq r$, order those solutions in order of increasing $x^2+y^2$, breaking ties in some manner. Applying $p$ then turns this into a sequence of distinct integers. Find $\theta$ as above and put $\phi = 2\theta$. Then the integer $\lfloor \phi p(x,y) \rfloor$ is equally often even and odd in each of these sequences.

share|cite|improve this answer

Your Answer


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.