# Is there an algebraically normal function from $\mathbb{Z}^{n}$ to $\{ 0 , 1\}$?

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 ?

-
Cross-posted on MSE –  Sébastien 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 ? –  Sébastien 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

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

-
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 ? –  Sébastien 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.

-