Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This was an optional h.w. problem:

You are at the origin in $\mathbb{Z}\times\mathbb{Z}$. There are trees of a fixed finite radius at each point in $\mathbb{Z}\times\mathbb{Z}$ (other than the origin).

How far can you see?

This was asked in (I think), the context of the Stone-Weierstrass Theorem. So I have been thinking there must be some distance where the diameters of the trees visually converge and you get a polynomial approximation of a visual boundary.

Thanks for your kindness to reply.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

I don't know the exact answer, but I can derive a hopefully reasonable upper bound.

Consider a line of sight in the direction $\alpha$. By the symmetries (dihedral group of order 8) we can assume that $0\le\alpha\le\pi/4$. Let $\rho=\tan\alpha$ be the slope of this line, so we are looking along the line $L:y=\rho x$.

Pick an integer $N$ such that $N-1>1/r$. The line $L$ intersects the vertical lines $x=i$, $i=1,2,\ldots,N$ at points $P_i=(i,i\rho)$. [Edit: A silly but potentially confusing typo was here as I had written $N\rho$ in place of $i\rho$ ] Let us consider the fractional parts of the $y$-coordinates of these points. For the point $P_i$ this is $y_i=\{i\rho\}=i\rho-[i\rho]$. The numbers $y_1,y_2,\ldots,y_N\in [0,1)$. Let's put these $N$ numbers into $N-1$ buckets according to the value of $[(N-1)y_i]\in\{0,1,\ldots,N-2\}$. By the pigeon hole principle at least two number, say $y_k$ and $y_\ell$ end up in the same bucket. Without loss of generality we can assume that $k>\ell$. Then $|y_k-y_\ell|\le1/(N-1)<r$. But we also have $$ y_k-y_\ell\equiv y_{k-\ell} \pmod1. $$ (or $y_k-y_\ell$ differs from $y_{k-\ell}$ by an integer). Therefore the point $P_{k-\ell}$ is within distance $r$ of a point of $\mathbf{Z}\times\mathbf{Z}$. Obviously here $0<k-\ell\le N$.

We have shown that this line will get blocked at a distance at most $N\sqrt{1+\tan^2\alpha}\le \sqrt2 N$. Here $N=1+\lceil(1/r)\rceil$, so we have shown that the maximum distance $d=d(r)$ that we can see satisfies the inequality $$ d(r)\le\sqrt2\left(1+\lceil\frac1r\rceil\right). $$

share|improve this answer
    
A good bound for $d(r)$! –  André Nicolas Jul 8 '11 at 22:53
    
@user6312: Dunno :-) I just saw that the first lemma of Diophantine appoximation can be used here to get a bound that probably is correct up to a constant multiplier. I should have guessed that this is a known problem. Thanks for the links. –  Jyrki Lahtonen Jul 9 '11 at 5:42
    
I have been remiss in not properly thanking you. Please also accept my apologies. Best, Andrew –  Andrew Sep 15 '11 at 21:38

This the famous Polya Orchard Problem.

The link is to a thorough discussion by Honsberger, marred a little by the fact that it comes from Google Books. The discussion is quite elementary.

Another detailed discussion can be found here. Somewhat more machinery is used.

I do not know of a connection with the Stone-Weierstrass Theorem, but that could very well be due to my weaknesses in analysis.

share|improve this answer
    
Thanks. I am only a self-studier (sorry to hide behind that). In taking a look at those sources, it seems the orchard has a given radius rather than being the entire ZxZ. Does that make a difference? –  Andrew Jul 8 '11 at 20:42
    
No difference. Typically, a relationship is found between radius $r$ of trees and maximum radius $R$ of an orchard such that you can see some part of its boundary from the origin. You will note that Lahtonen gave a quick nice argument that says roughly $Rr <\sqrt{2}$. The references I gave basically improve the $\sqrt{2}$ to $1$, and I think one cannot do better. You can google Polya Orchard Problem for other papers. So to repeat, $R$ is basically max. line of sight distance. –  André Nicolas Jul 8 '11 at 22:07
    
Thanks again. People are so generous here. –  Andrew Jul 8 '11 at 22:32

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.