**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](http://en.wikipedia.org/wiki/Generating_set_of_a_group#Finitely_generated_group) $\Gamma$ (with its [word metric](http://en.wikipedia.org/wiki/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 ?



Is there an algebraically normal function from $\mathbb{Z}^{n}$ to $\{ 0 , 1\}$?
$\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](https://mathoverflow.net/a/139260/297), recursively build an $a$ so that all sufficiently large solutions to $|x^5 - a^5 y^5| <1$ have the same color.


