A rectangle in a Cartesian coordinate system

For students of class 11-12 (age 16+)
Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

A rectangle in a Cartesian coordinate system

Unread post by Zan » Fri Jun 29, 2012 4:32 pm

What are the necessary and sufficient conditions for the two numbers $a$ and $b$ so that it is possible to form a rectangle in a Cartesian coordinate system which does not contain points with integer coordinates?

User avatar
nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

Re: A rectangle in a Cartesian coordinate system

Unread post by nayel » Thu Jul 05, 2012 6:20 pm

Things to clarify:
1. What are $a$ and $b$? (I'm assuming the side-lengths of the rectangle?)
2. By "contain" do you mean contain inside or just on the boundary (or both)?

If $a,b$ are indeed the side-lengths, and by "contain" you mean contain inside or on the boundary, then a necessary and sufficient condition is
$c=\min\{a,b\}<1$. To show that it's necessary, suppose $c\ge 1$. Then any square with side-length $c$ contains a point with integer coordinates. For sufficiency, consider any rectangle two of whose vertices are $(0,y)$ and $(0,y+c)$, with $y$ chosen so that $y+c<1$. This rectangle doesn't contain any point with integer coordinates.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Re: A rectangle in a Cartesian coordinate system

Unread post by Zan » Fri Jul 06, 2012 12:22 am

If you rotate a square by $45°$ whose sides are a bit less than $\sqrt{2}$, it also doesn't contain a point.

User avatar
nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

Re: A rectangle in a Cartesian coordinate system

Unread post by nayel » Fri Jul 06, 2012 1:02 am

You're right, that was stupid of me. But I think replacing $1$ by $\sqrt 2$ in the first part works. Then for the second part we can use your rectangle.
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Re: A rectangle in a Cartesian coordinate system

Unread post by Zan » Wed Jul 11, 2012 10:46 am

Is anybody able to show the problem?

User avatar
nayel
Posts: 268
Joined: Tue Dec 07, 2010 7:38 pm
Location: Dhaka, Bangladesh or Cambridge, UK

Re: A rectangle in a Cartesian coordinate system

Unread post by nayel » Wed Jul 11, 2012 2:46 pm

What's wrong with the above solution?
"Everything should be made as simple as possible, but not simpler." - Albert Einstein

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Re: A rectangle in a Cartesian coordinate system

Unread post by Zan » Wed Jul 25, 2012 4:38 pm

Can you explain it alittle bit? It is too fast for me...

Zan
Posts: 16
Joined: Fri Jun 08, 2012 8:26 pm

Re: A rectangle in a Cartesian coordinate system

Unread post by Zan » Tue Aug 07, 2012 11:04 pm

nayel wrote:$c=\min\{a,b\}<1$. To show that it's necessary, suppose $c\ge 1$. Then any square with side-length $c$ contains a point with integer coordinates. For sufficiency, consider any rectangle two of whose vertices are $(0,y)$ and $(0,y+c)$, with $y$ chosen so that $y+c<1$. This rectangle doesn't contain any point with integer coordinates.[/hide]
How can you show that the conditions are necessary and sufficient?
Thank you in advance!

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: A rectangle in a Cartesian coordinate system

Unread post by Masum » Sat Oct 13, 2012 9:38 pm

I think we can't guarantee sufficiency so easily. It would be true for segment, not for a rectangle. We can find a bound for triangle easily. If a triangle with integer coordinates have no other integer points other than its vertices, it is called a primitive triangle(see Pick's Theorem). And for this triangle, we need to consider the consecutive terms of Farey sequence. Now, we know the sufficiency of lattice triangle. So, choose a triangle which lies strictly between this triangle. This is such a triangle. I think with some more work, I can find a similar construction of such a rectangle, but currently I can't. Also, this might not have a direct mathematical solution.
One one thing is neutral in the universe, that is $0$.

User avatar
Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm
Location: Dhaka,Bangladesh

Re: A rectangle in a Cartesian coordinate system

Unread post by Masum » Sat Oct 13, 2012 10:11 pm

Zan wrote:What are the necessary and sufficient conditions for the two numbers $a$ and $b$ so that it is possible to form a rectangle in a Cartesian coordinate system which does not contain points with integer coordinates?
I am modifying your problem so that we can find an answer. the way you are looking an answer is not proper. There is no legitimate definition of $a,b$ and so more ambiguities. Let's try to find the vertices of a rectangle which have no point inside it. A point with integer coordinate is called lattice point. Let's say the rectangle has vertices on integer points but no inner points is lattice.
We prove the following lemma:
Lemma:
The segment $L(A, B)$ with $A(x_1, y_1), B(x_2, y_2)$ contains $\gcd(|x_1-x_2|, |y_1-y_2|)$ lattice points.
Proof:
Let's count the number of points on the line which cuts the $X$-axis in $(a,0)$ and the $Y$-axis in $(0,b)$. Then it has the equation, \[\frac xa+\frac yb=1\]
We need to count the number of integer solutions to this equation. Say, $\gcd(a,b)=g,a=gm,b=gn$ with $\gcd(m,n)=1$. Then the equation reduces to, \[mx+ny=gmn\]
$m$ divides $gmn$ and $mx$, so $m$ divides $ny$ but $n$ and $m$ share no common factor. Therefore, $m|y$ and similarly $n|x$. Say, $x=mt, y=nu$. We have $t+u=g$. This equation has $g+1$ solutions. So, there will be total $g+1$ points including the origin. To count the number of lattice points on $L$, shift the origin to $(x_1,y_1)$. At this, the number of lattice points will be the same, even after rotation, it will be same.
Now, say the rectangle has vertices $(x_i,y_i)_{i=1}^4$. So, now the number of lattice point is equal to $\gcd(x_2-x_1,y_2-y_1)$. We define $G_i=\gcd(|x_i-x_{i+1}|, |y_i-y_{i+1}|)$ with $(x_{n+1}, y_{n+1})=(x_1,y_1)$. The number of lattice points on the rectangle will be(of-course you can extend it to any polynomial also) \[G=\sum_{i=1}^4G_i\]
This primitive rectangle must have an area of $1$. From Pick's theorem, \[A=I+\frac B2-1\]
\[1=0+\frac G2-1\Rightarrow G=4\Rightarrow\sum_{i=1}^4G_i=4\]
Since $G_i>0$, we can assume the solution, $G_1=G_2=G_3=G_4=1$. Again, the Farey sequence comes. Take four of them so that they make a rectangle. I mean you should consider a point from the sequence as $(y,x)$ if the fraction in the sequence is $\frac xy$.
One one thing is neutral in the universe, that is $0$.

Post Reply