Vieta jumping

Template:Short description In number theory, Vieta jumping, also known as root flipping, is a proof technique. It is most often used for problems in which a relation between two integers is given, along with a statement to prove about its solutions. In particular, it can be used to produce new solutions of a quadratic Diophantine equation from known ones. There exist multiple variations of Vieta jumping, all of which involve the common theme of infinite descent by finding new solutions to an equation using Vieta's formulas.

History

Vieta jumping is a classical method in the theory of quadratic Diophantine equations and binary quadratic forms. For example, it was used in the analysis of the Markov equation back in 1879 and in the 1953 paper of Mills.Template:Sfn

In 1988, the method came to the attention to mathematical olympiad problems in the light of the first olympiad problem to use it in a solution that was proposed for the International Mathematics Olympiad and assumed to be the most difficult problem on the contest:

Let Template:Math and Template:Math be positive integers such that Template:Math divides Template:Math. Show that $\frac{a^2+b^2}{ab+1}$ is the square of an integer.

Arthur Engel wrote the following about the problem's difficulty: Template:Quote

Among the eleven students receiving the maximum score for solving this problem were Ngô Bảo Châu, Ravi Vakil, Zvezdelina Stankova, and Nicușor Dan. Emanouil Atanassov (from Bulgaria) solved the problem in a paragraph and received a special prize.

Standard Vieta jumping

The concept of standard Vieta jumping is a proof by contradiction, and consists of the following four steps:

1. Assume toward a contradiction that some solution (Template:Math) exists that violates the given requirements.
2. Take the minimal such solution according to some definition of minimality.
3. Replace some Template:Math by a variable x in the formulas, and obtain an equation for which Template:Math is a solution.
4. Using Vieta's formulas, show that this implies the existence of a smaller solution, hence a contradiction.

Example

Problem #6 at IMO 1988: Let Template:Math and Template:Math be positive integers such that Template:Math divides Template:Math. Prove that Template:Math is a perfect square.

1. Fix some value Template:Math that is a non-square positive integer. Assume there exist positive integers Template:Math for which Template:Math.
2. Let Template:Math be positive integers for which Template:Math and such that Template:Math is minimized, and without loss of generality assume Template:Math.
3. Fixing Template:Math, replace Template:Math with the variable Template:Math to yield Template:Math. We know that one root of this equation is Template:Math. By standard properties of quadratic equations, we know that the other root satisfies Template:Math and Template:Math.
4. The first expression for Template:Math shows that Template:Math is an integer, while the second expression implies that Template:Math since Template:Math is not a perfect square. From Template:Math it further follows that Template:Math, and hence Template:Math is a positive integer. Finally, Template:Math implies that Template:Math, hence Template:Math, and thus Template:Math, which contradicts the minimality of Template:Math.

Constant descent Vieta jumping

The method of constant descent Vieta jumping is used when we wish to prove a statement regarding a constant Template:Math having something to do with the relation between Template:Math and Template:Math. Unlike standard Vieta jumping, constant descent is not a proof by contradiction, and it consists of the following four steps:

1. The equality case is proven so that it may be assumed that Template:Math.
2. Template:Math and Template:Math are fixed and the expression relating Template:Math, and Template:Math is rearranged to form a quadratic with coefficients in terms of Template:Math and Template:Math, one of whose roots is Template:Math. The other root, Template:Math is determined using Vieta's formulas.
3. For all Template:Math above a certain base case, show that Template:Math and that Template:Math is an integer. Thus, while maintaining the same Template:Math, we may replace Template:Math with Template:Math and repeat this process until we arrive at the base case.
4. Prove the statement for the base case, and as Template:Math has remained constant through this process, this is sufficient to prove the statement for all ordered pairs.

Example

Let Template:Math and Template:Math be positive integers such that Template:Math divides Template:Math. Prove that Template:Math.

1. If Template:Math dividing Template:Math implies that Template:Math divides 1, and hence the positive integers Template:Math, and Template:Math. So, without loss of generality, assume that Template:Math.
2. For any Template:Math satisfying the given condition, let Template:Math and rearrange and substitute to get Template:Math. One root to this quadratic is Template:Math, so by Vieta's formulas the other root may be written as follows: Template:Math.
3. The first equation shows that Template:Math is an integer and the second that it is positive. Because Template:Math and they are both integers, Template:Math, and hence Template:Math; As long as Template:Math, we always have Template:Math, and therefore Template:Math. Thus, while maintaining the same Template:Math, we may replace Template:Math with Template:Math and repeat this process until we arrive at the base case.
4. The base case we arrive at is the case where Template:Math. For Template:Math to satisfy the given condition, Template:Math must divide Template:Math, which implies that Template:Math divides 2, making Template:Math either 1 or 2. The first case is eliminated because Template:Math. In the second case, Template:Math. As Template:Math has remained constant throughout this process of Vieta jumping, this is sufficient to show that for any Template:Math satisfying the given condition, Template:Math will always equal 3.

Geometric interpretation

Vieta jumping can be described in terms of lattice points on hyperbolas in the first quadrant. The same process of finding smaller roots is used instead to find lower lattice points on a hyperbola while remaining in the first quadrant. The procedure is as follows:

1. From the given condition we obtain the equation of a family of hyperbolas that are unchanged by switching Template:Math and Template:Math so that they are symmetric about the line Template:Math.
2. Prove the desired statement for the intersections of the hyperbolas and the line Template:Math.
3. Assume there is some lattice point Template:Math on some hyperbola and without loss of generality Template:Math. Then by Vieta's formulas, there is a corresponding lattice point with the same Template:Math-coordinate on the other branch of the hyperbola, and by reflection through Template:Math a new point on the original branch of the hyperbola is obtained.
4. It is shown that this process produces lower points on the same branch and can be repeated until some condition (such as Template:Math) is achieved. Then by substitution of this condition into the equation of the hyperbola, the desired conclusion will be proven.

Example

This method can be applied to problem #6 at IMO 1988: Let Template:Math and Template:Math be positive integers such that Template:Math divides Template:Math. Prove that Template:Math is a perfect square.

1. Let Template:Math and fix the value of Template:Math. If Template:Math, Template:Math is a perfect square as desired. If Template:Math, then Template:Math and there is no integral solution Template:Math. When Template:Math, the equation Template:Math defines a hyperbola Template:Math and Template:Math represents an integral lattice point on Template:Math.
2. If Template:Math is an integral lattice point on Template:Math with Template:Math, then (since Template:Math is integral) one can see that Template:Math. This proposition's statement is then true for the point Template:Math.
3. Now let Template:Math be a lattice point on a branch Template:Math with Template:Math and Template:Math (as the previous remark covers the case Template:Math). By symmetry, we can assume that Template:Math and that Template:Math is on the higher branch of Template:Math. By applying Vieta's Formulas, Template:Math is a lattice point on the lower branch of Template:Math. Let Template:Math. From the equation for Template:Math, one sees that Template:Math. Since Template:Math, it follows that Template:Math. Hence the point Template:Math is in the first quadrant. By reflection, the point Template:Math is also a point in the first quadrant on Template:Math. Moreover from Vieta's formulas, Template:Math, and Template:Math. Combining this equation with Template:Math, one can show that Template:Math. The new constructed point Template:Math is then in the first quadrant, on the higher branch of Template:Math, and with smaller Template:Math,Template:Math-coordinates than the point Template:Math we started with.
4. The process in the previous step can be repeated whenever the point Template:Math has a positive Template:Math-coordinate. However, since the Template:Math-coordinates of these points will form a decreasing sequence of non-negative integers, the process can only be repeated finitely many times before it produces a point Template:Math on the upper branch of Template:Math; by substitution, Template:Math is a square as required.

See also

• Vieta's formulas
• Proof by contradiction
• Infinite descent
• Markov number
• Apollonian gasket

External links

• Vieta Root Jumping at Brilliant.org
• Template:Cite journal