Størmer's theorem

From Wikipedia, the free encyclopedia

In mathematics, Størmer's theorem in number theory states that the set of integers

generated by a finite set of primes contains only finitely many pairs of consecutive integers; and gives a method of finding them all using Pell equations. It follows from the Thue–Siegel–Roth theorem that there are only a finite number of pairs of this type, but Carl Størmer gave a procedure for finding them all.

In the theory of musical tuning, Størmer's theorem means that there are only a finite number of superparticular ratios in a given prime limit; each such ratio is the larger of a consecutive pair divided by the smaller of the pair. For example, the only superparticular intervals in 3-limit Pythagorean tuning, that is, superparticular ratios for integers generated by the set of primes {2,3}, are 2/1, 3/2, 4/3, and 9/8. In 5-limit just tuning, based on the regular numbers generated by the set of primes {2,3,5}, the ten superparticular ratios are 2/1, 3/2, 4/3, 5/4, 6/5, 9/8, 10/9, 16/15, 25/24, and 81/80.

Contents 1 The procedure 2 Example 3 Counting solutions 4 Generalizations and applications 5 References

[edit] The procedure

Størmer's original procedure involves solving a set of roughly 3^k Pell equations, in each one finding only the smallest solution. We describe instead a simplified version of the procedure, due to Lehmer (1964), which solves fewer equations but finds more solutions in each equation.

Let P be the given set of primes, and define a number to be P-smooth if all its prime factors belong to P. We assume p₁ = 2; otherwise there can be no consecutive P-smooth numbers. In Lehmer's solution, we solve the Pell equation

x² − 2qy² = 1

for each P-smooth square-free number q other than 2. Each such number is generated as a product of a subset of P, so there are 2^k-1 Pell equations to solve. For each such equation, let x_i,y_i be the generated solutions, for i in the range [1,max(3,(p_k+1)/2)], where p_k is the largest of the primes in P.

Then, as Lehmer shows, all consecutive pairs of P-smooth numbers are of the form (x_i - 1)/2, (x_i + 1)/2. Thus one can find all such pairs by testing the numbers of this form for P-smoothness.

[edit] Example

Suppose we wish to find the 5-smooth numbers; that is, P = {2,3,5}. There are seven P-smooth squarefree numbers q to test (omitting the eighth P-smooth squarefree number, 2): 1, 3, 5, 6, 10, 15, and 30. For each of them, we generate three solutions to the Pell equation:

• For q = 1, the first three solutions to the Pell equation x² - 2y² = 1 are (3,2), (17,12), and (99,70). From (3,2) we get the pair of consecutive P-smooth numbers (1,2) and from (17,12) we get the pair of consecutive P-smooth numbers (8,9). (99,70) does not generate a pair of consecutive P-smooth numbers: (99+1)/2 = 50 is P-smooth, but (99-1)/2 = 49 is not.

• For q = 3, the first three solutions to the Pell equation x² - 6y² = 1 are (5,2), (49,20), and (485,198). From (5,2) we get the pair of consecutive P-smooth numbers (2,3) and from (49,20) we get the pair of consecutive P-smooth numbers (24,25).

• For q = 5, the first three solutions to the Pell equation x² - 10y² = 1 are (19,6), (721,228), and (27379,8658). From (19,6) we get the pair of consecutive P-smooth numbers (9,10).

• For q = 6, the first three solutions to the Pell equation x² - 12y² = 1 are (7,2), (97,28), and (1351,390). From (7,2) we get 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). From (9,2) we get the pair of consecutive P-smooth numbers (4,5) and from (161,36) we get 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). From (11,2) we get 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). From (31,4) we get the pair of consecutive P-smooth numbers (15,16).

[edit] Counting 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: M(2^k - 1), where M = max(3,(p_k+1)/2).

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, ... (sequence A002071 in OEIS).

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

2, 9, 81, 4375, 9801, 123201, 336141, 11859211, ... (sequence A117581 in OEIS).

OEIS also lists the number of pairs of this type where the larger of the two integers in the pair is square (sequence A117582 in OEIS) or triangular (sequence A117583 in OEIS), as both types of pair arise frequently.

[edit] Generalizations and applications

Chein (1976) 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.

Mabkhout (1993) 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. In particular see Cao (1991), Luo (1991), Mei and Sun (1997), Sun and Yuan (1989), and Walker (1967).

[edit] References