Suppose I want to construct an $N$-gon in the plane whose vertices are integer lattice points, and which is close to a regular $N$-gon (which means, the ratio of longest to the shortest side is within $\epsilon_1$ of $1,$ and the ratio of the largest to the smallest angle is within $\epsilon_2$ of $1$) The question is: is there any sort of reasonable upper/lower bound to the size (area or diameter) of such a thing? This is clearly related to diophantine approximation in the following way: take the "standard" regular $N$-gon (one whose vertices are $N$-th roots of unity,) and blow it up by a factor of $t$ until wall the vertices ($t$ times the roots of unity) are close to lattice points. How big does $t$ need to be in terms of some "closeness" bound?
-
1$\begingroup$ I'm not sure this is what you are asking for, but here is something very elementary : let $\ell(i,t)$ be the Gauss integer closest to $t\omega^i$ (with $\omega=e^{2i\pi/n}$). Then by the triangle inequality, you have that the length $d(i,i+1,t)$ between $\ell(i,t)$ and $\ell(i+1,t)$ satisfies the inequality $2t\pi/n-\sqrt{2}\leq d(i,i+1,t)\leq 2t\pi/n+\sqrt{2}$... Thus you can always find an $\sqrt{2}/m$ good approximation with integers of norm smaller than $m$ ... $\endgroup$– few_repsCommented Dec 5, 2013 at 18:40
-
$\begingroup$ @few_reps that is a nice observation! It does not deal with angles (though that is not too hard to correct by elementary geometry), but also, on general principles, I would expect the error term to be of order $1/m^2,$ not $1/m.$ $\endgroup$– Igor RivinCommented Dec 5, 2013 at 18:44
-
$\begingroup$ This would be kind of a miracle : even if you can approximate $\omega^i$ by elements $h_n^{(i)}/k_n^{(i)}$ for each $i$ with $N(\omega^i- h_n^{(i)}/k_n^{(i)}) <1/N(k_n^{(i)})^2$, (this is possible since $\mathbf Z[i]$ is euclidean) I can see no reason why the $k_n^{(i)}$'s could not be prime to each other ... $\endgroup$– few_repsCommented Dec 5, 2013 at 19:39
-
$\begingroup$ Lest anyone think it possible to get an $N$-gon with vertices all at integer lattice points in the plane: This is only possible when $N = 4$. Citation: Klobučar, D. (1998). On nonexistence of an integer regular polygon. Mathematical Communications, 3(1), 143-146. (From math.stackexchange.com/questions/568709/…) $\endgroup$– Benjamin DickmanCommented Dec 6, 2013 at 6:15
1 Answer
Probably Dirichlet's approximation theorem gives best possible answer for large $N$. We can only reduce the number of simultaneous approximations using symmetries of $N$-gon. For example for $8$-gon it is necessary to approximate only one number $1/\sqrt2$ among $8$ numbers $e^{2\pi ik/8}$ $(k=0,\ldots 7)$.
But starting from arbitrary $N$-gon inscribed into the unit circle we can find $t\le R$ such that $$|tx_1-a_1|\le\frac1{R^{\frac1{2N}}},|ty_1-b_1|\le\frac1{R^{\frac1{2N}}},\ldots |tx_N-a_N|\le\frac1{R^{\frac1{2N}}},|ty_N-b_N|\le\frac1{R^{\frac1{2N}}},$$ where $(x_1,y_1), \ldots, (x_N,y_N)$ are coordinates of initial $N$-gon. It means that we can achieve $\epsilon_1=\epsilon_2\asymp t^{-1-\frac1{2N}}$ in the circle of radius $t$ for infinitely many $t$.
If we want a better exponent, we can do the following. For arbitrary $N$ we can take $x_1=1$, $y_1=0$ (no approximation needed). The rest part of vertices is symmetrical. So for odd $N$ we need to approximate $(N-1)/2$ points ($N-1$ coordinates), for $N\equiv2\pmod4$ $(N-2)/4$ points ($(N-2)/2$ coordinates), for $N\equiv4\pmod8$ $(N-4)/8$ points, for $N\equiv0\pmod8$ $(N-2)/4$ points $1+(N-8)/8$ coordinates.
Also there is an algorithm (based on discrete Fourier transform) of complexity $O(t^2)$ which allows to find all best possible solutions in the circle of radius $t$. This algorithm was published in Algebra and number theory for mathematical schools. Collected problems (Russian, see page 138).
It is very simple. We need so specify only one vertex to define our regular $N$-gon. So we take all points $A_1=(x_1,y_1)$ such that $0\le y_1\le x_1\le t$. For each $A_1$ we define $A_2',\ldots,A_N'$ rotating $A_1$ around the origin, and $A_2,\ldots,A_N$ as nearest integer points to $A_2',\ldots,A_N'$. After that it necessary to check the quality of resulting $N$-gon. We can say that $A_1,\ldots,A_N$ are $N$ complex numbers and calculate discrete Fourier series. First Fourier coefficient gives main cycle ($|C_1|\approx |OA_1|$) and the rest part of Fourier series forms an error term.
-
$\begingroup$ So are you saying that for a regular $N$-gon one can get a better exponent? $\endgroup$ Commented Dec 6, 2013 at 4:23
-
$\begingroup$ And is there a reference for the algorithm? That sounds very interesting... $\endgroup$ Commented Dec 6, 2013 at 4:24
-
$\begingroup$ I've added the refference and algorithm description. Also exponents were corrected. $\endgroup$ Commented Dec 6, 2013 at 6:53
-
$\begingroup$ @Alexey : I did not know of the simultaneous approximation. I guess that if rather than doing it in $\mathbf R$ relatively to $\mathbf Z$ you do it in $\mathbf C$ relatively to $\mathbf Z[i]$, you can even obtain $\varepsilon_1\sim \varepsilon_2\sim t^{−1−1/N}$ ... $\endgroup$– few_repsCommented Dec 6, 2013 at 12:27
-
$\begingroup$ I agree that $\mathbb(Z}[i]$ is better. It allows to average over rotation. But in $\mathbb(R}$ we also can save at least half coordinates using symmetrical positions of initial $N$-gon. For best possible estimates we have to check everything more carefully. $\endgroup$ Commented Dec 6, 2013 at 13:38