How can you find small denominators inside triangles? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T20:44:24Z http://mathoverflow.net/feeds/question/94 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/94/how-can-you-find-small-denominators-inside-triangles How can you find small denominators inside triangles? Scott Morrison 2009-10-04T20:19:43Z 2009-11-07T06:43:46Z <p><a href="http://math.berkeley.edu/~dranjan/" rel="nofollow">Darsh</a> asked over at the <a href="http://scratchpad.wikia.com/wiki/20qs" rel="nofollow">20 questions seminar</a>:</p> <p>Take a triangle in R^2 with coordinates at rational points. Can we find the smallest denominator point in the interior? (Consider denominator of an element of Q^2 to be the lcm of the denominators of the coordinates.) (Hint: you can do the 1-d version using continued fractions.) </p> http://mathoverflow.net/questions/94/how-can-you-find-small-denominators-inside-triangles/100#100 Answer by Ilya Nikokoshev for How can you find small denominators inside triangles? Ilya Nikokoshev 2009-10-04T22:13:37Z 2009-10-05T00:13:57Z <p>Here's an example algorithm that finds the smallest denominator point in the interior:</p> <ol> <li>Take the triangle's center and denote D to be its denominator.</li> <li>Find all horizontal lines with y-coordinate's denominator not greater than D and that have a chance of intersecting your triangle.</li> <li>Same for vertical lines.</li> <li>Intersect these line families, select points inside your triangle and minimize their denominator.</li> </ol> <p>This does look like an <em>unsatisfying</em> algorithm, but then your problem might benefit from being phrased in a different way, perhaps </p> <ul> <li>Can we find the smallest denominator point in the interior using some beautiful O(D) algorithm? </li> </ul> <p>(where, presumably, D is the final answer)</p> http://mathoverflow.net/questions/94/how-can-you-find-small-denominators-inside-triangles/4429#4429 Answer by Agol for How can you find small denominators inside triangles? Agol 2009-11-06T20:20:17Z 2009-11-07T06:43:46Z <p><img src="http://latex.mathoverflow.net/png?%24%28a%5Fi%2Fc%5Fi%2Cb%5Fi%2Fc%5Fi%29%20%5Cin%20%5Cmathbb%7BR%7D%5E2%2C%20i%3D1%2C2%2C3%24" alt="$(a\sb i/c\sb i,b\sb i/c\sb i) \in \mathbb{R}^2, i=1,2,3$" title="" /></p> <p>One way to interpret the problem is as an integer programming problem in 3-dimensions. If one has 3 points <img src="http://latex.mathoverflow.net/png?%24%28a%5Fi%2Fc%5Fi%2Cb%5Fi%2Fc%5Fi%29%20%5Cin%20%5Cmathbb%7BR%7D%5E2%2C%20i%3D1%2C2%2C3%24" alt="no-alt-text" title="" /> (see above) with <img src="http://latex.mathoverflow.net/png?%24gcd%28a%5Fi%2C%20b%5Fi%2C%20c%5Fi%29%20%3D1%24" alt="$gcd(a\sb i, b\sb i, c\sb i) =1$" title="" /> and <img src="http://latex.mathoverflow.net/png?%24c%5Fi%20%3E%200%24" alt="$c\sb i \geq 1$" title="" />, then take the three lattice points <img src="http://latex.mathoverflow.net/png?%24P%5Fi%3D%28a%5Fi%2C%20b%5Fi%2C%20c%5Fi%29%20%5Cin%20%5Cmathbb%7BZ%7D%5E3%24" alt="$P\sb i=(a\sb i, b\sb i, c\sb i) \in \mathbb{Z}^3$" title="" />.</p> <p>Take the cone C spanned by positive integer combinations of $P_i$ (this is the projective region sitting above the triangle). Then one wants to find the lattice point of http://latex.mathoverflow.net/png?%24%5Cmathbb%7BZ%7D%5E3%24) inside the interior of this cone with smallest z-coordinate. This may be interpreted as an integer linear programming problem. However, I don't know enough about integer programming to know if this will help ([Scarf" /> seems to have thought about precisely this problem, but doesn't address the computational complexity). The following gives one possible approach, but might not be any better than Nikokoshev's approach except in certain regimes. </p> <p>These vectors generate a sublattice <img src="http://latex.mathoverflow.net/png?%24%5CLambda%20%5Csubset%20%5Cmathbb%7BZ%7D%5E3%24" alt="$\Lambda \subset \mathbb{Z}^3$" title="" /> of index D, where D is the determinant of the matrix <img src="http://latex.mathoverflow.net/png?%24%5BP%5F1%2CP%5F2%2CP%5F3%5D%24" alt="$[P\sb 1,P\sb 2,P\sb 3]$" title="" />, and is the volume of the parallelpiped F spanned by these vectors. One can see that a lattice vector in this cone with minimal z-coordinate must lie in this F, since F is a fundamental domain for the action of <img src="http://latex.mathoverflow.net/png?%24%5CLambda%5Ccap%20C%24" alt="$\Lambda\cap C$" title="" />. A brute-force approach is to compute the finite abelian group <img src="http://latex.mathoverflow.net/png?%24%5Cmathbb%7BZ%7D%5E3%2F%5CLambda%24" alt="$\mathbb{Z}^3/\Lambda$" title="" />, finding a basis (which will consist of at most 2 vectors since <img src="http://latex.mathoverflow.net/png?%24P%5Fi%24" alt="$P\sb i$" title="" /> is primitive). Then translate these vectors into the fundamental domain F, and take enough positive linear combinations to generate all coset representatives of <img src="http://latex.mathoverflow.net/png?%24%5Cmathbb%7BZ%7D%5E3%2F%5CLambda%24" alt="$\mathbb{Z}^3/\Lambda$" title="" /> inside C. Then subtract elements from the positive semigroup <img src="http://latex.mathoverflow.net/png?%24%5CLambda%5Ccap%20C%24" alt="$\Lambda\cap C$" title="" />, until you find all coset representatives in the fundamental domain F, and find the one with minimal z-coordinate. This approach should be pretty effective when D is small or the group <img src="http://latex.mathoverflow.net/png?%24%5Cmathbb%7BZ%7D%5E3%2F%5CLambda%24" alt="$\mathbb{Z}^3/\Lambda$" title="" /> is cyclic, but I'm not sure how the size of D correlates with the size of the final solution. For example, if <img src="http://latex.mathoverflow.net/png?%24D%3D1%24" alt="$D=1$" title="" />, then the minimal vector will be <img src="http://latex.mathoverflow.net/png?%24P%5F1%2BP%5F2%2BP%5F3%24" alt="$P\sb 1+P\sb 2+P\sb 3$" title="" /> with denominator <img src="http://latex.mathoverflow.net/png?%24c%5F1%2Bc%5F2%2Bc%5F3%24" alt="$c\sb 1+c\sb 2+c\sb 3$" title="" />. If <img src="http://latex.mathoverflow.net/png?%24D%5Cgeq%202%24" alt="$D\geq 2$" title="" />, the minimal denominator will be <img src="http://latex.mathoverflow.net/png?%24%3C%28c%5F1%2Bc%5F2%2Bc%5F3%29%2F2%24" alt="$&lt;(c\sb 1+c\sb 2+c\sb 3)/2$" title="" /> by the symmetry of F. </p>