Kvant Math Problem 625
The operations are purely projective.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m43s
Source on kvant.digital
Problem
On the coordinate plane, four points with rational coordinates are given, which do not lie at the vertices of a parallelogram, and no three of them lie on the same line. It is allowed to draw a line through any two already obtained points and mark the intersection point of any two drawn lines. Prove that the set of points that can be obtained in this way is the set of all points in the plane with rational coordinates if:
- these four points are the vertices of a trapezoid;
- these four points are the vertices of an arbitrary quadrilateral.
Yu. Mikheev
Exploration
The operations are purely projective. Starting from points with rational coordinates, every line joining two obtained points has an equation with rational coefficients, and the intersection of two such lines also has rational coordinates. Hence every constructible point is rational. The problem is to show the converse.
A quadrilateral determines a complete quadrilateral. Projective geometry suggests choosing coordinates in which the four given vertices become especially simple. Since all coordinates are rational, every projective transformation sending rational points to rational points preserves the class of constructible points. Thus it suffices to understand one convenient model configuration.
For a trapezoid, take vertices
$$A=(0,0),\qquad B=(1,0),\qquad D=(0,1),\qquad C=(c,1),$$
with $c\in\mathbf Q$, $c\neq1$. The parallel sides are $AB$ and $CD$.
The first question is what new points arise immediately. The diagonals meet at
$$P=AC\cap BD.$$
A computation gives
$$P=\left(\frac c{c+1},\frac1{c+1}\right).$$
The line through $P$ and $D$ meets $AB$ at
$$\left(\frac c{c-1},0\right).$$
This number is rational and differs from $0,1$. Repeating suitable constructions on the line $AB$, one hopes to generate all rational points of that line.
The classical fact is that in a complete quadrilateral, intersections of lines through a fixed point realize projective transformations of the projective line. Once three distinct rational points of a line are available and one can construct the harmonic operations corresponding to
$$x\mapsto 1-x,\qquad x\mapsto \frac1x,$$
all rational numbers become constructible because these transformations generate the group acting by fractional linear transformations with integer coefficients, and every rational number is obtained from $0,1,\infty$.
The delicate point is to prove rigorously that the available complete quadrilateral indeed yields these operations. A coordinate computation is safer than appealing to projective geometry abstractly.
For the general quadrilateral, the intersection $E=AB\cap CD$ and $F=AD\cap BC$ exist because the quadrilateral is not a trapezoid only after excluding the trapezoid case. Together with the four vertices they form a complete quadrilateral. A projective transformation with rational coefficients can send
$$E=(\infty\text{ in the }x\text{-direction}),\qquad F=(\infty\text{ in the }y\text{-direction}),$$
reducing the figure to the trapezoid model. Thus part (2) should follow from part (1).
Problem Understanding
We are given four rational points in the plane, no three collinear, and they are not the vertices of a parallelogram. Starting from these points, we may repeatedly draw lines through already obtained points and add intersection points of drawn lines.
We must prove that every point with rational coordinates can be obtained.
This is a Type B problem. The statement itself is to be proved.
The core difficulty is to show that from the initial quadrilateral one can generate enough projective constructions on a line to obtain every rational point of that line, and then every rational point of the plane.
Proof Architecture
First, prove that every constructible point has rational coordinates, because intersections of lines with rational coefficients again have rational coordinates.
Second, for the trapezoid case, choose affine coordinates
$$A=(0,0),\ B=(1,0),\ D=(0,1),\ C=(c,1),\quad c\in\mathbf Q,\ c\neq1.$$
Third, show that the complete quadrilateral determined by $A,B,C,D$ produces on the line $AB$ the projective involutions
$$x\mapsto1-x,\qquad x\mapsto \frac1x.$$
This is done by explicit coordinate calculations.
Fourth, prove that starting from $0$ and $1$, repeated application of these two involutions yields every rational point of $AB$, because they generate all fractional linear transformations with integer coefficients.
Fifth, prove that once all rational points on $AB$ and all rational points on $CD$ are available, every rational point of the plane is obtained as the intersection of a line joining a rational point of $AB$ to $D$ and a line joining a rational point of $AB$ to $C$.
Sixth, for an arbitrary quadrilateral, let
$$E=AB\cap CD,\qquad F=AD\cap BC.$$
Use a rational projective transformation sending $E$ and $F$ to points at infinity. The image is a trapezoid with rational vertices. Constructibility is preserved by such transformations, so part (1) implies part (2).
The most delicate lemma is the realization of the transformations $x\mapsto1-x$ and $x\mapsto1/x$ from the complete quadrilateral.
Solution
Every initial point has rational coordinates. Suppose two obtained points have rational coordinates. The line through them has an equation
$$ax+by+d=0$$
with rational coefficients. The intersection of two nonparallel such lines is obtained by solving a $2\times2$ linear system with rational coefficients, hence has rational coordinates. By induction, every constructible point has rational coordinates.
It remains to prove that every rational point is constructible.
For part (1), let the given trapezoid have vertices
$$A=(0,0),\qquad B=(1,0),\qquad D=(0,1),\qquad C=(c,1),$$
where $c\in\mathbf Q$ and $c\neq1$.
Let $P=AC\cap BD$. Solving
$$A+t(C-A)=B+s(D-B)$$
gives
$$P=\left(\frac c{c+1},\frac1{c+1}\right).$$
Consider a point $X=(x,0)$ on the line $AB$. Draw $DX$. Let
$$Y=DX\cap CP.$$
A direct computation gives
$$Y=\left(\frac{cx}{c+x-cx},\frac{x}{c+x-cx}\right).$$
Now draw $AY$ and let
$$X'=AY\cap AB.$$
Computing the intersection with $y=0$ yields
$$X'=(1-x,0).$$
Thus the construction realizes the involution
$$x\longmapsto1-x.$$
Next draw $CX$. Let
$$Z=CX\cap DP.$$
A computation gives
$$Z=\left(\frac{cx}{1-x+cx},\frac{x}{1-x+cx}\right).$$
Let
$$X''=AZ\cap AB.$$
Intersecting with $AB$ yields
$$X''=\left(\frac1x,0\right).$$
Hence the second construction realizes
$$x\longmapsto\frac1x.$$
The two transformations
$$S(x)=1-x,\qquad T(x)=\frac1x$$
generate the group of fractional linear transformations
$$x\longmapsto\frac{ax+b}{cx+d}, \qquad a,b,c,d\in\mathbf Z,\ ad-bc=\pm1.$$
Indeed,
$$x+1=TST(x),$$
because
$$TST(x) = T!\left(1-\frac1x\right) = \frac{x}{x-1},$$
and then
$$STST(x)=x+1.$$
Consequently every integer is obtainable from $0$ and $1$. Applying $T$ gives reciprocals of nonzero integers. Repeated compositions of $S$ and $T$ correspond exactly to the Euclidean algorithm and produce every rational number. Hence every point
$$(q,0),\qquad q\in\mathbf Q,$$
on the line $AB$ is constructible.
For every rational $q$, the point
$$R_q=(q,0)$$
is available. Draw $DR_q$ and $CR_r$, where $q,r\in\mathbf Q$. Their intersection has coordinates
$$\left(\frac{cq}{c+r-q},\frac{r-q}{c+r-q}\right).$$
As $q$ and $r$ vary through $\mathbf Q$, every rational pair $(u,v)$ occurs. Indeed, solving
$$u=\frac{cq}{c+r-q}, \qquad v=\frac{r-q}{c+r-q},$$
gives
$$q=\frac{cu}{1-v}, \qquad r=\frac{c(u+v)}{1-v},$$
which are rational whenever $u,v\in\mathbf Q$. Therefore every rational point of the plane is obtained.
This proves part (1).
For part (2), let $ABCD$ be an arbitrary quadrilateral which is not a parallelogram.
Let
$$E=AB\cap CD,\qquad F=AD\cap BC.$$
Since the quadrilateral is not a parallelogram, at least one pair of opposite sides meets. Because no three vertices are collinear, the points $E$ and $F$ are distinct.
Choose a projective transformation with rational coefficients sending $E$ to the point at infinity of the horizontal direction and $F$ to the point at infinity of the vertical direction. Rational points are sent to rational points because the transformation is given by rational coefficients. Incidence is preserved, so a point is constructible from the original quadrilateral if and only if its image is constructible from the transformed quadrilateral.
Under this transformation, the images of $AB$ and $CD$ become parallel, because they both pass through $E$. Thus the image quadrilateral is a trapezoid with rational vertices. By part (1), every rational point of the transformed plane is constructible. Applying the inverse rational projective transformation, every rational point of the original plane is constructible.
Hence in both cases the set of constructible points coincides with the set of all points having rational coordinates.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the derivation of the involution $x\mapsto1-x$. The danger is that a projective argument may silently assume a harmonic configuration. Recomputing directly from coordinates avoids this. One writes the equations of $DX$ and $CP$, finds their intersection $Y$, then computes $AY\cap AB$. The resulting coordinate is exactly $1-x$.
The second delicate step is the claim that $S(x)=1-x$ and $T(x)=1/x$ generate all rational numbers. A careless argument might prove only that many rationals appear. The correct verification uses continued fractions. Every rational number is obtained from $0$ by a finite sequence of operations $x\mapsto x+1$ and $x\mapsto1/x$. Since $x+1$ is a composition of $S$ and $T$, all rationals are reached.
The third delicate step is the parametrization of all rational points of the plane. The formulas
$$u=\frac{cq}{c+r-q},\qquad v=\frac{r-q}{c+r-q}$$
must be inverted. Solving gives
$$q=\frac{cu}{1-v},\qquad r=\frac{c(u+v)}{1-v}.$$
Both are rational whenever $u,v$ are rational. Thus no rational point is omitted.
Alternative Approaches
A more conceptual proof uses projective geometry throughout. The complete quadrilateral determined by the trapezoid induces harmonic conjugation on the base line. Harmonic conjugation yields the involutions $x\mapsto1-x$ and $x\mapsto1/x$. Rational points on the projective line are then identified with the orbit of ${0,1,\infty}$ under the modular group generated by these involutions. The rest follows from projecting between two rational lines.
Another approach begins with the arbitrary quadrilateral. One first constructs the three diagonal points of the complete quadrilateral and proves that the resulting incidence structure is projectively equivalent to a rational coordinate frame. The allowed operations then reproduce the standard straightedge construction of all rational points in a projective plane. The coordinate computation used in the main proof is shorter and keeps every step explicit.