Størmer's theorem

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. [Størmer (1897).]

Application in music theory

In the theory of musical tuning, musical tones can be described as integer multiples of a fundamental frequency, and the multiples generated by products of small prime numbers are of particular importance: in Pythagorean tuning, only tones corresponding to integer multiples of the form 2^"i" × 3^"j" are allowed, while in just tuning, only the tones corresponding to numbers of the form 2^"i" × 3^"j" ×5^"k" are allowed, where "i", "j", and "k" may range over any non-negative integer value. The difference between one tone and another forms a musical interval that can be measured by the ratio between the two corresponding integers, and in music the superparticular ratios between consecutive integers are of particular importance.

Størmer's theorem implies that, for 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 note). 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). For just tuning, six additional superparticular ratios are available: 5/4, 6/5, 10/9, 16/15, 25/24, and 81/80; all are musically meaningful. [Halsey and Hewitt (1972) give a direct proof for this case, avoiding Størmer's more general method.]

Some modern musical theorists have developed "p"-limit musical tuning systems for primes "p" larger than 5; Størmer's theorem applies as well in these cases, and describes how to calculate the set of possible superparticular ratios for these systems.

Formal statement of the theorem

Formally, the theorem states that, if one chooses a finite set "P" = {"p"₁, ... "p_k"} of prime numbers and considers the set of integers

: $S = left{p_1^{e_1}p_2^{e_2}...p_k^{e_k}mid e_iin{0,1,2,ldots}
ight}$

that can be generated by products of numbers in "P", then there are only finitely many pairs of consecutive numbers in "S". 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 3^"k" Pell equations, in each one finding only the smallest solution. A simplified version of the procedure, due to D. H. Lehmer,Lehmer (1964).] 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 "p"₁ = 2; otherwise there can be no consecutive "P"-smooth numbers. Lehmer's method involves solving the Pell equation: $x^2-2qy^2 = 1$ for each "P"-smooth square-free number "q" other than 2. Each such number "q" 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.

Example

To find the ten consecutive pairs of {2,3,5}-smooth numbers 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"² - 2"y"² = 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"² - 6"y"² = 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: (3,2), (25,24), and (243,242). Of these, (3,2) and (25,24) are pairs of consecutive "P"-smooth numbers but (243,242) is not.

* For "q" = 5, the first three solutions to the Pell equation "x"² - 10"y"² = 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"² - 12"y"² = 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"² - 20"y"² = 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"² - 30"y"² = 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"² - 60"y"² = 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 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).

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, ... OEIS|id = A002071.The largest integer from all these pairs, for each "k", is:2, 9, 81, 4375, 9801, 123201, 336141, 11859211, ... OEIS | id = A117581.OEIS also lists the number of pairs of this type where the larger of the two integers in the pair is square OEIS|id = A117582 or triangular OEIS|id = A117583, as both types of pair arise frequently.

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).]

Notes

References

*cite journal
author = Cao, Zhen Fu
title = On the Diophantine equation ("ax^m" - 1)/("abx"-1) = "by"²
journal = Chinese Sci. Bull.
volume = 36
year = 1991
issue = 4
pages = 275–278
id = MathSciNet | id = 1138803

*cite journal
author = Chein, E. Z.
title = A note on the equation "x"² = "y^q" + 1
journal = Proceedings of the American Mathematical Society
volume = 56
year = 1976
pages = 83–84
doi = 10.2307/2041579
id = MathSciNet | id = 0404133
*cite journal
author = Halsey, G. D.; Hewitt, Edwin
title = More on the superparticular ratios in music
journal = American Mathematical Monthly
volume = 79
year = 1972
pages = 1096–1100
id = MathSciNet | id = 0313189
doi = 10.2307/2317424

*cite journal
author = Lehmer, D. H.
authorlink = D. H. Lehmer
year = 1964
title = On a Problem of Størmer
journal = Illinois Journal of Mathematics
volume = 8
pages = 57–79
id = MathSciNet | id = 0158849

*cite journal
author = Luo, Jia Gui
title = A generalization of the Störmer theorem and some applications
journal = Sichuan Daxue Xuebao
volume = 28
year = 1991
issue = 4
pages = 469–474
id = MathSciNet | id = 1148835

*cite journal
author = Mabkhout, M.
title = Minoration de "P"("x"⁴+1)
journal = Rend. Sem. Fac. Sci. Univ. Cagliari
volume = 63
year = 1993
issue = 2
pages = 135–148
id = MathSciNet | id = 1319302

*cite journal
author = Mei, Han Fei; Sun, Sheng Fang
title = A further extension of Störmer's theorem
journal = J. Jishou Univ. Nat. Sci. Ed.
volume = 18
year = 1997
issue = 3
pages = 42–44
id = MathSciNet | id = 1490505

*cite journal
author = Størmer, Carl
authorlink = Carl Størmer
title = Quelques théorèmes sur l'équation de Pell "x"² - "Dy"² = ±1 et leurs applications
journal = Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl.
volume = I
issue = 2
year = 1897

*cite journal
author = Sun, Qi; Yuan, Ping Zhi
title = On the Diophantine equations ("axⁿ" - 1)/("ax" - 1) = "y"² and ("axⁿ" + 1)/("ax" + 1) = "y"²
journal = Sichuan Daxue Xuebao
volume = 26
year = 1989
pages = 20–24
id = MathSciNet | id = 1059671

*cite journal
author = Walker, D. T.
title = On the diophantine equation "mX"² - "nY"2 = ±1
journal = American Mathematical Monthly
volume = 74
year = 1967
pages = 504–513
doi = 10.2307/2314877
id = MathSciNet | id = 0211954

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

Stormer — may refer to: * [http://steveebell.moonfruit.com Stormer] A group from west Yorkshire who recorded an album for Ringo Starr,at Tittenhurst Park *The Alvis Stormer, a military armored vehicle *The Land Rover Range Stormer, a concept car… … Wikipedia
Carl Størmer — Infobox Scientist name = PAGENAME box width = image width =150px caption = PAGENAME birth date = September 3, 1874 birth place = Skien death date = August 13, 1957 death place = residence = citizenship = nationality = Norwegian ethnicity = field … Wikipedia
List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… … Wikipedia
Pell's equation — is any Diophantine equation of the form:x^2 ny^2=1,where n is a nonsquare integer and x and y are integers. Trivially, x = 1 and y = 0 always solve this equation. Lagrange proved that for any natural number n that is not a perfect square there… … Wikipedia
Regular number — The numbers that evenly divide the powers of 60 arise in several areas of mathematics and its applications, and have different names coming from these different areas of study. As an example, 602 = 3600 = 48 times; 75, so both 48 and 75 are… … Wikipedia
Diophantine equation — In mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for… … Wikipedia
Catalan's conjecture — (occasionally now referred to as Mihăilescu s theorem) is a theorem in number theory that was conjectured by the mathematician Eugène Charles Catalan in 1844 and proven in 2002 by Preda Mihăilescu. 23 and 32 are two powers of natural numbers,… … Wikipedia
Syntonic comma — on C Play (help· … Wikipedia
Superparticular number — Superparticular numbers, also called epimoric ratios, are ratios of the form Thus: A superparticular number is when a great number contains a lesser number, to which it is compared, and at the same time one part of it. For example, when 3 and 2… … Wikipedia
Pythagorean interval — In musical tuning theory, a Pythagorean interval is a musical interval with frequency ratio equal to a power of two divided by a power of three, or vice versa. For instance, the perfect fifth with ratio 3/2 (equivalent to 31/21) and the perfect… … Wikipedia

Academic Dictionaries and Encyclopedias

Størmer's theorem

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Størmer's theorem

Look at other dictionaries:

Share the article and excerpts

Direct link