Three-gap theorem

From HandWiki
Jump to: navigation, search

In mathematics, the three-gap theorem, three-distance theorem, or Steinhaus conjecture states that if one places n points on a circle, at angles of θ, 2θ, 3θ ... from the starting point, then there will be at most three distinct distances between pairs of points in adjacent positions around the circle. When there are three distances, the largest of the three always equals the sum of the other two.[1] Unless θ is a rational multiple of π, there will also be at least two distinct distances.

This result was conjectured by Hugo Steinhaus, and proved in the 1950s by Vera T. Sós, János Surányi (hu), and Stanisław Świerczkowski. Its applications include the study of plant growth and musical tuning systems, and the theory of Sturmian words.


End-on view of a plant stem in which consecutive leaves are separated by the golden angle

In phyllotaxis (the theory of plant growth), it has been observed that each successive leaf on the stems of many plants is turned from the previous leaf by the golden angle, approximately 137.5°. It has been suggested that this angle maximizes the sun-collecting power of the plant's leaves.[2] If one looks end-on at a plant stem that has grown in this way, there will be at most three distinct angles between two leaves that are consecutive in the cyclic order given by this end-on view.[3] In the figure, the largest of these three angles occurs three times, between the leaves numbered 3 and 6, between leaves 4 and 7, and between leaves 5 and 8. The second-largest angle occurs five times, between leaves 6 and 1, 9 and 4, 7 and 2, 10 and 5, and 8 and 3. And the smallest angle occurs only twice, between leaves 1 and 9 and between leaves 2 and 10. (This phenomenon has nothing to do with the golden ratio; the same property, of having only three distinct gaps between consecutive points on a circle, happens for any other rotation angle, and not just for the golden angle.)[3]

A geometric view of the tones of the Pythagorean tuning as points on a circle, showing the Pythagorean comma (the gap between the first and last points of the path) as the amount by which this tuning system fails to close up to a regular dodecagram. The edges between the points of the circle are the perfect fifths from which this tuning system is constructed.

In music theory, this theorem implies that if a tuning system is generated by some number of consecutive multiples of a given interval, reduced to a cyclic sequence by considering two tones to be equivalent when they differ by whole numbers of octaves, then there are at most three different intervals between consecutive tones of the scale.[4][5] For instance, the Pythagorean tuning is constructed in this way from multiples of a perfect fifth. It has only two distinct intervals representing its semitones,[6] but if it were extended by one more step then the sequence of intervals between its tones would include a third shorter interval, the Pythagorean comma.[7]

In the theory of Sturmian words, the theorem implies that the words of a given length n that appear within a given Sturmian word have at most three distinct frequencies. If there are three frequencies, then one of them must equal the sum of the other two.[8]

History and proof

The three-gap theorem was conjectured by Hugo Steinhaus, and its first proofs were published in the late 1950s by Vera T. Sós,[9] János Surányi (hu),[10] and Stanisław Świerczkowski.[11] Several later proofs have also been published.[12][13][14][15][16]

The following simple proof is due to Frank Liang. Define a gap (an arc of the circle between adjacent points of the given set) to be rigid if rotating that gap by an angle of θ does not produce another gap of the same length. Each rotation by θ increases the position of the gap endpoints in the placement ordering of the points, and such an increase cannot be repeated indefinitely, so every gap has the same length as a rigid gap. But the only ways for a gap to be rigid are for one of its two endpoints to be the last point in the placement sequence (so that the corresponding point is missing from the rotated gap) or for another point to land in its rotated copy. An endpoint can only be missing if the gap is one of the two gaps on either side of the last point in the placement ordering. And a point can only land within the rotated copy if it is the first point in the placement ordering. So there can be at most three rigid gaps, and at most three lengths of gaps. Additionally, when there are three, the rotated copy of a rigid gap that has the first point in it is partitioned by that point into two smaller gaps, so in this case the longest gap length is the sum of the other two.[17][18]

A closely related but earlier theorem, also called the three-gap theorem, is that if A is any arc of the circle, then the integer sequence of multiples of θ that land in A has at most three gaps between sequence values. Again, if there are three gaps then one is the sum of the other two.[19][20]

See also


  1. Allouche, Jean-Paul; Shallit, Jeffrey (2003), "2.6 The Three-Distance Theorem", Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, pp. 53–55, ISBN 9780521823326, 
  2. Adam, John A. (2011), A Mathematical Nature Walk, Princeton University Press, pp. 35–41, ISBN 9781400832903, 
  3. 3.0 3.1 van Ravenstein, Tony (1987), "Number sequences and phyllotaxis", Bulletin of the Australian Mathematical Society 36 (2): 333, doi:10.1017/s0004972700026605 
  4. Carey, Norman (2007), "Coherence and sameness in well-formed and pairwise well-formed scales", Journal of Mathematics and Music 1 (2): 79–98, doi:10.1080/17459730701376743 
  5. Narushima, Terumi (2017), Microtonality and the Tuning Systems of Erv Wilson: Mapping the Harmonic Spectrum, Routledge Studies in Music Theory, Routledge, pp. 90–91, ISBN 9781317513421, 
  6. Strohm, Reinhard; Blackburn, Bonnie J., eds. (2001), Music as Concept and Practice in the Late Middle Ages, Volume 3, Part 1, New Oxford history of music, Oxford University Press, p. 252, ISBN 9780198162056, 
  7. Benson, Donald C. (2003), A Smoother Pebble: Mathematical Explorations, Oxford University Press, p. 51, ISBN 9780198032977, 
  8. Lothaire, M. (2002), "Sturmian Words", Algebraic Combinatorics on Words, Cambridge: Cambridge University Press, ISBN 978-0-521-81220-7, 
  9. "On the distribution mod 1 of the sequence [math]\displaystyle{ n\alpha }[/math]", Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 1: 127–134, 1958 
  10. Surányi, J. (1958), "Über die Anordnung der Vielfachen einer reelen Zahl mod 1", Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 1: 107–111 
  11. "On successive settings of an arc on the circumference of a circle", Fundamenta Mathematicae 46 (2): 187–189, 1959, doi:10.4064/fm-46-2-187-189 
  12. Halton, John H. (1965), "The distribution of the sequence [math]\displaystyle{ \{n\xi\}\,(n=0,\,1,\,2,\,\ldots) }[/math]", Proc. Cambridge Philos. Soc. 61 (3): 665–670, doi:10.1017/S0305004100039013 
  13. Slater, Noel B. (1967), "Gaps and steps for the sequence [math]\displaystyle{ n\theta \bmod 1 }[/math]", Proc. Cambridge Philos. Soc. 63 (4): 1115–1123, doi:10.1017/S0305004100042195 
  14. van Ravenstein, Tony (1988), "The three-gap theorem (Steinhaus conjecture)", Journal of the Australian Mathematical Society, Series A 45 (3): 360–370, doi:10.1017/S1446788700031062 
  15. Mayero, Micaela (2000), "The three gap theorem (Steinhaus conjecture)", Types for Proofs and Programs: International Workshop, TYPES'99, Lökeberg, Sweden, June 12–16, 1999, Selected Papers, Lecture Notes in Computer Science, 1956, Springer, pp. 162–173, doi:10.1007/3-540-44557-9_10, ISBN 978-3-540-41517-6 
  16. Marklof, Jens; Strömbergsson, Andreas (2017), "The three gap theorem and the space of lattices", American Mathematical Monthly 124 (8): 741–745, doi:10.4169/amer.math.monthly.124.8.741 
  17. Liang, Frank M. (1979), "A short proof of the [math]\displaystyle{ 3d }[/math] distance theorem", Discrete Mathematics 28 (3): 325–326, doi:10.1016/0012-365X(79)90140-7 
  18. Shiu, Peter (2018), "A footnote to the three gaps theorem", American Mathematical Monthly 125 (3): 264–266, doi:10.1080/00029890.2018.1412210 
  19. Slater, N. B. (1950), "The distribution of the integers [math]\displaystyle{ N }[/math] for which [math]\displaystyle{ \theta N\lt \phi }[/math]", Proc. Cambridge Philos. Soc. 46 (4): 525–534, doi:10.1017/S0305004100026086 
  20. Florek, K. (1951), "Une remarque sur la répartition des nombres [math]\displaystyle{ n\xi\, (\operatorname{mod} 1) }[/math]", Colloq. Math. 2: 323–324