HOME

TheInfoList



OR:

In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Math ...
, Størmer's theorem, named after Carl Størmer, gives a finite bound on the number of consecutive pairs of
smooth numbers In number theory, an ''n''-smooth (or ''n''-friable) number is an integer whose prime factors are all less than or equal to ''n''. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 72 and 15750 = 2 × 32 × 5 ...
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.


Statement

If one chooses a
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. ...
P=\ of
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
s then the -smooth numbers are defined as the set of integers :\left\ that can be generated by products of numbers in . Then Størmer's theorem states that, for every choice of , there are only finitely many pairs of consecutive -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 3''k'' Pell equations, in each one finding only the smallest solution. A simplified version of the procedure, due to
D. H. Lehmer Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory. Lehmer refined Édouard Lucas' work in the 1930s and ...
, 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''1 = 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 :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 ''xi, yi'' be the generated solutions, for ''i'' in the range from 1 to max(3, (''pk'' + 1)/2) (inclusive), where ''pk'' is the largest of the primes in ''P''. 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 -smooth numbers (in music theory, giving the superparticular ratios for just tuning) let ''P'' = . 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 − 2''y''2 = 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 (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''2 − 6''y''2 = 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 ''x''2 − 10''y''2 = 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''2 − 12''y''2 = 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''2 − 20''y''2 = 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''2 − 30''y''2 = 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''2 − 60''y''2 = 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,(''pk''+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, ... . The largest integer from all these pairs, for each ''k'', is :2, 9, 81, 4375, 9801, 123201, 336141, 11859211, ... . OEIS also lists the number of pairs of this type where the larger of the two integers in the pair is square or
triangular A triangle is a polygon with three edges and three vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC. In Euclidean geometry, any three points, when non-collinear, ...
, as both types of pair arise frequently.


Generalizations and applications

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


In mathematics

used Størmer's method to prove
Catalan's conjecture Catalan's conjecture (or 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 at Paderborn University. The integers 23 and 32 are ...
on the nonexistence of consecutive
perfect power In mathematics, a perfect power is a natural number that is a product of equal natural factors, or, in other words, an integer that can be expressed as a square or a higher integer power of another integer greater than one. More formally, ''n' ...
s (other than 8,9) in the case where one of the two powers is a
square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
. proved that every number ''x''4 + 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 equation In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to ...
s, or by providing more general
divisibility In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
criteria for the solutions to Pell equations.In particular see , , , , and . 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 In music, just intonation or pure intonation is the tuning of musical intervals as whole number ratios (such as 3:2 or 4:3) of frequencies. An interval tuned in this way is said to be pure, and is called a just interval. Just intervals (and ...
, 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. Furthermore, superparticular ratios are very important in just tuning theory as they represent ratios between adjacent members of the harmonic series. Størmer's theorem allows all possible superparticular ratios in a given limit to be found. For example, in the 3-limit (
Pythagorean tuning Pythagorean tuning is a system of musical tuning in which the frequency ratios of all intervals are based on the ratio 3:2.Bruce Benward and Marilyn Nadine Saker (2003). ''Music: In Theory and Practice'', seventh edition, 2 vols. (Boston: M ...
), the only possible superparticular ratios are 2/1 (the
octave In music, an octave ( la, octavus: eighth) or perfect octave (sometimes called the diapason) is the interval between one musical pitch and another with double its frequency. The octave relationship is a natural phenomenon that has been refer ...
), 3/2 (the
perfect fifth In music theory, a perfect fifth is the musical interval corresponding to a pair of pitches with a frequency ratio of 3:2, or very nearly so. In classical music from Western culture, a fifth is the interval from the first to the last of five ...
), 4/3 (the
perfect fourth A fourth is a musical interval encompassing four staff positions in the music notation of Western culture, and a perfect fourth () is the fourth spanning five semitones (half steps, or half tones). For example, the ascending interval from C to th ...
), and 9/8 (the
whole step In Western music theory, a major second (sometimes also called whole tone or a whole step) is a second spanning two semitones (). A second is a musical interval encompassing two adjacent staff positions (see Interval number for more detai ...
). 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 In classical music, a third is a musical interval encompassing three staff positions (see Interval number for more details), and the major third () is a third spanning four semitones. Forte, Allen (1979). ''Tonal Harmony in Concept and P ...
), 6/5 (the
minor third In music theory, a minor third is a musical interval that encompasses three half steps, or semitones. Staff notation represents the minor third as encompassing three staff positions (see: interval number). The minor third is one of two com ...
), 10/9 (the
minor tone In Western music theory, a major second (sometimes also called whole tone or a whole step) is a second spanning two semitones (). A second is a musical interval encompassing two adjacent staff positions (see Interval number for more detai ...
), 16/15 (the
minor second A semitone, also called a half step or a half tone, is the smallest musical interval commonly used in Western tonal music, and it is considered the most dissonant when sounded harmonically. It is defined as the interval between two adjacent no ...
), 25/24 (the minor semitone), and 81/80 (the
syntonic comma In music theory, the syntonic comma, also known as the chromatic diesis, the Didymean comma, the Ptolemaic comma, or the diatonic comma is a small comma type interval between two musical notes, equal to the frequency ratio 81:80 (= 1.0125 ...
). All are musically meaningful.


Notes


References

* * * * * * * * * * * * * {{DEFAULTSORT:Stormers theorem Mathematics of music Theorems in number theory