Størmer's theorem
In
Statement
If one chooses a finite set of prime numbers then the P-smooth numbers are defined as the set of integers
that can be generated by products of numbers in P. Then Størmer's theorem states that, for every choice of P, there are only finitely many pairs of consecutive P-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 3k Pell equations, in each one finding only the smallest solution. A simplified version of the procedure, due to D. H. Lehmer,[2] is described below; it 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. Assume p1 = 2; otherwise there could be no consecutive P-smooth numbers, because all P-smooth numbers would be odd. Lehmer's method involves solving the Pell equation
for each P-smooth
Then, as Lehmer shows, all consecutive pairs of P-smooth numbers are of the form (xi − 1)/2, (xi + 1)/2. Thus one can find all such pairs by testing the numbers of this form for P-smoothness.
Example
To find the ten consecutive pairs of
- For q = 1, the first three solutions to the Pell equation x2 − 2y2 = 1 are (3,2), (17,12), and (99,70). Thus, for each of the three values xi = 3, 17, and 99, Lehmer's method tests the pair (xi − 1)/2, (xi + 1)/2 for smoothness; the three pairs to be tested are (1,2), (8,9), and (49,50). Both (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 x2 − 6y2 = 1 are (5,2), (49,20), and (485,198). From the three values xi = 5, 49, and 485 Lehmer's method forms the three candidate pairs of consecutive numbers (xi − 1)/2, (xi + 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 x2 − 10y2 = 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 x2 − 12y2 = 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 x2 − 20y2 = 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 x2 − 30y2 = 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 x2 − 60y2 = 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).
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 3k − 2k. Lehmer's result produces a tighter bound for sets of small primes: (2k − 1) × max(3,(pk+1)/2).[2]
The number of consecutive pairs of integers that are smooth with respect to the first k primes are
The largest integer from all these pairs, for each k, is
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 the OEIS) or triangular (sequence A117583 in the OEIS), as both types of pair arise frequently.
Generalizations and applications
In mathematics
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 x4 + 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
Conrey, Holmstrom & McLaughlin (2013) 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
Størmer's theorem allows all possible superparticular ratios in a given limit to be found. For example, in the 3-limit (
Notes
- ^ Størmer (1897).
- ^ a b Lehmer (1964).
- ^ As quoted by Chapman (1958).
- ^ In particular see Cao (1991), Luo (1991), Mei & Sun (1997), Sun & Yuan (1989), and Walker (1967).
- ^ Partch (1974).
- ^ Halsey & Hewitt (1972).
References
- Cao, Zhen Fu (1991). "On the Diophantine equation (axm - 1)/(abx-1) = by2". Chinese Sci. Bull. 36 (4): 275–278. MR 1138803.
- JSTOR 769515.
- Chein, E. Z. (1976). "A note on the equation x2 = yq + 1". MR 0404133.
- Conrey, J. B.; Holmstrom, M. A.; McLaughlin, T. L. (2013). "Smooth neighbors". Experimental Mathematics. 22 (2): 195–202. MR 3047912.
- Halsey, G. D.; Hewitt, Edwin (1972). "More on the superparticular ratios in music". MR 0313189.
- MR 0158849.
- Luo, Jia Gui (1991). "A generalization of the Störmer theorem and some applications". Sichuan Daxue Xuebao. 28 (4): 469–474. MR 1148835.
- Mabkhout, M. (1993). "Minoration de P(x4+1)". Rend. Sem. Fac. Sci. Univ. Cagliari. 63 (2): 135–148. MR 1319302.
- Mei, Han Fei; Sun, Sheng Fang (1997). "A further extension of Störmer's theorem". Journal of Jishou University (Natural Science Edition) (in Chinese). 18 (3): 42–44. MR 1490505.
- ISBN 0-306-71597-X.
- Størmer, Carl (1897). "Quelques théorèmes sur l'équation de Pell et leurs applications". Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl. I (2).
- Sun, Qi; Yuan, Ping Zhi (1989). "On the Diophantine equations and ". Sichuan Daxue Xuebao. 26: 20–24. MR 1059671.
- Walker, D. T. (1967). "On the diophantine equation mX2 - nY2 = ±1". MR 0211954.