Størmer's theorem

Template:Short description In number theory, Størmer's theorem, named after Carl Størmer, gives a finite bound on the number of consecutive pairs of smooth numbers that exist, for a given degree of smoothness, and provides a method for finding all such pairs using Pell equations. It follows from the Thue–Siegel–Roth theorem that there are only a finite number of pairs of this type, but Størmer gave a procedure for finding them all.Template:Sfnp

Statement

If one chooses a finite set $P=\{p_1,p_2,\dots p_k\}$ of prime numbers then the Template:Mvar-smooth numbers are defined as the set of integers

$\{p_1^{e_1}{p}_2^{e_2}\cdots p_k^{e_k}\mid e_i\in \{0,1,2,\dots \}\}$

that can be generated by products of numbers in Template:Mvar. Then Størmer's theorem states that, for every choice of Template:Mvar, there are only finitely many pairs of consecutive Template:Mvar-smooth numbers. Further, it gives a method of finding them all using Pell equations.

The procedure

Størmer's original procedure involves solving a set of roughly Template:Math Pell equations, in each one finding only the smallest solution. A simplified version of the procedure, due to D. H. Lehmer,Template:Sfnp is described below; it solves fewer equations but finds more solutions in each equation.

Let Template:Mvar be the given set of primes, and define a number to be Template:Mvar-smooth if all its prime factors belong to Template:Mvar. Assume Template:Math; otherwise there could be no consecutive Template:Mvar-smooth numbers, because all Template:Mvar-smooth numbers would be odd. Lehmer's method involves solving the Pell equation

$x^2-2q{y}^2=1$

for each Template:Mvar-smooth square-free number Template:Mvar other than Template:Mvar. Each such number Template:Mvar is generated as a product of a subset of Template:Mvar, so there are Template:Math Pell equations to solve. For each such equation, let Template:Math be the generated solutions, for Template:Mvar in the range from 1 to Template:Math (inclusive), where Template:Math is the largest of the primes in Template:Mvar.

Then, as Lehmer shows, all consecutive pairs of Template:Mvar-smooth numbers are of the form Template:Math. Thus one can find all such pairs by testing the numbers of this form for Template:Mvar-smoothness.

Lehmer's paper furthermore showsTemplate:Sfnp that applying a similar procedure to the equation

$x^2-D{y}^2=1,$

where Template:Mvar ranges over all Template:Mvar-smooth square-free numbers other than 1, yields those pairs of Template:Mvar-smooth numbers separated by 2: the smooth pairs are then Template:Math, where Template:Math is one of the first Template:Math solutions of that equation.

Example

To find the ten consecutive pairs of {2,3,5}-smooth numbers (in music theory, giving the superparticular ratios for just tuning) let P = {2,3,5}. There are seven P-smooth squarefree numbers q (omitting the eighth P-smooth squarefree number, 2): 1, 3, 5, 6, 10, 15, and 30, each of which leads to a Pell equation. The number of solutions per Pell equation required by Lehmer's method is max(3, (5 + 1)/2) = 3, so this method generates three solutions to each Pell equation, as follows.

• For q = 1, the first three solutions to the Pell equation x² − 2y² = 1 are (3,2), (17,12), and (99,70). Thus, for each of the three values x_i = 3, 17, and 99, Lehmer's method tests the pair (x_i − 1)/2, (x_i + 1)/2 for smoothness; the three pairs to be tested are (1,2), (8,9), and (49,50). Both (1,2) and (8,9) are pairs of consecutive P-smooth numbers, but (49,50) is not, as 49 has 7 as a prime factor.
• For q = 3, the first three solutions to the Pell equation x² − 6y² = 1 are (5,2), (49,20), and (485,198). From the three values x_i = 5, 49, and 485 Lehmer's method forms the three candidate pairs of consecutive numbers (x_i − 1)/2, (x_i + 1)/2: (2,3), (24,25), and (242,243). Of these, (2,3) and (24,25) are pairs of consecutive P-smooth numbers but (242,243) is not.
• For q = 5, the first three solutions to the Pell equation x² − 10y² = 1 are (19,6), (721,228), and (27379,8658). The Pell solution (19,6) leads to the pair of consecutive P-smooth numbers (9,10); the other two solutions to the Pell equation do not lead to P-smooth pairs.
• For q = 6, the first three solutions to the Pell equation x² − 12y² = 1 are (7,2), (97,28), and (1351,390). The Pell solution (7,2) leads to the pair of consecutive P-smooth numbers (3,4).
• For q = 10, the first three solutions to the Pell equation x² − 20y² = 1 are (9,2), (161,36), and (2889,646). The Pell solution (9,2) leads to the pair of consecutive P-smooth numbers (4,5) and the Pell solution (161,36) leads to the pair of consecutive P-smooth numbers (80,81).
• For q = 15, the first three solutions to the Pell equation x² − 30y² = 1 are (11,2), (241,44), and (5291,966). The Pell solution (11,2) leads to the pair of consecutive P-smooth numbers (5,6).
• For q = 30, the first three solutions to the Pell equation x² − 60y² = 1 are (31,4), (1921,248), and (119071,15372). The Pell solution (31,4) leads to the pair of consecutive P-smooth numbers (15,16).

Number and size of solutions

Størmer's original result can be used to show that the number of consecutive pairs of integers that are smooth with respect to a set of k primes is at most 3^k − 2^k. Lehmer's result produces a tighter bound for sets of small primes: (2^k − 1) × max(3,(p_k+1)/2).Template:Sfnp

The number of consecutive pairs of integers that are smooth with respect to the first k primes are

1, 4, 10, 23, 40, 68, 108, 167, 241, 345, ... Template:OEIS.

The largest integer from all these pairs, for each k, is

2, 9, 81, 4375, 9801, 123201, 336141, 11859211, ... Template:OEIS.

OEIS also lists the number of pairs of this type where the larger of the two integers in the pair is square Template:OEIS or triangular Template:OEIS, as both types of pair arise frequently.

The size of the solutions can also be bounded: in the case where Template:Mvar and Template:Math are required to be Template:Mvar-smooth, thenTemplate:Sfnp

$\log (x)<M(2+\log (8S))\sqrt{2S}-\log (4),$

where Template:Math and Template:Mvar is the product of all elements of Template:Mvar, and in the case where the smooth pair is Template:Math, we haveTemplate:Sfnp

$\log (x-1)<M(2+\log (4S))\sqrt{S}-\log (2).$

Generalizations and applications

Louis Mordell wrote about this result, saying that it "is very pretty, and there are many applications of it."

In mathematics

Template:Harvtxt used Størmer's method to prove Catalan's conjecture on the nonexistence of consecutive perfect powers (other than 8,9) in the case where one of the two powers is a square.

Template:Harvtxt proved that every number x⁴ + 1, for x > 3, has a prime factor greater than or equal to 137. Størmer's theorem is an important part of his proof, in which he reduces the problem to the solution of 128 Pell equations.

Several authors have extended Størmer's work by providing methods for listing the solutions to more general diophantine equations, or by providing more general divisibility criteria for the solutions to Pell equations.

Template:Harvtxt describe a computational procedure that, empirically, finds many but not all of the consecutive pairs of smooth numbers described by Størmer's theorem, and is much faster than using Pell's equation to find all solutions.

In music theory

In the musical practice of just intonation, musical intervals can be described as ratios between positive integers. More specifically, they can be described as ratios between members of the harmonic series. Any musical tone can be broken into its fundamental frequency and harmonic frequencies, which are integer multiples of the fundamental. This series is conjectured to be the basis of natural harmony and melody. The tonal complexity of ratios between these harmonics is said to get more complex with higher prime factors. To limit this tonal complexity, an interval is said to be n-limit when both its numerator and denominator are n-smooth.Template:Sfnp Furthermore, superparticular ratios are very important in just tuning theory as they represent ratios between adjacent members of the harmonic series.Template:Sfnp

Størmer's theorem allows all possible superparticular ratios in a given limit to be found. For example, in the 3-limit (Pythagorean tuning), the only possible superparticular ratios are 2/1 (the octave), 3/2 (the perfect fifth), 4/3 (the perfect fourth), and 9/8 (the whole step). That is, the only pairs of consecutive integers that have only powers of two and three in their prime factorizations are (1,2), (2,3), (3,4), and (8,9). If this is extended to the 5-limit, six additional superparticular ratios are available: 5/4 (the major third), 6/5 (the minor third), 10/9 (the minor tone), 16/15 (the minor second), 25/24 (the minor semitone), and 81/80 (the syntonic comma). All are musically meaningful.

References

• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal