Tuesday, May 6, 2025

Diophantine Limits of Quantum Probability Amplification

Grover’s algorithm is usually described geometrically as a repeated rotation. Here we reinterpret those rotations as a Diophantine approximation problem on the circle — placing Grover’s amplitude amplification under the lens of the Three Gap Theorem. This reveals that the quality of alignment with the marked state is governed by the continued fraction properties of the rotation angle θ, linking quantum search to the deep regularities of irrational rotations.

The application of Grover's quantum search algorithm to solve specific Diophantine equations within bounded integer ranges is a known demonstration of its utility, hinting at an intrinsic link between quantum computation and number theory. However, this article posits a far more profound connection: the probability amplification mechanism central to Grover's algorithm inherently shares qualitative limitations and structural parallels with concepts from Diophantine approximation, particularly illuminated by the Three Gap Theorem (TGT).

The Three Gap Theorem (also known as the Steinhaus Conjecture) is a remarkable result in number theory. It states that for any irrational number \(\alpha\) and any positive integer \(n\), the set of fractional parts \(\{k\alpha\}\) (i.e., \(k\alpha \bmod 1\)) for \(k = 1, 2, ..., n\), when ordered on the unit interval \([0,1)\), partitions this interval into subintervals of at most three distinct lengths. If exactly three lengths occur, the largest is always the sum of the other two. This theorem reveals an astonishing regularity in a seemingly simple iterative process.

Crucially, the TGT is deeply intertwined with the theory of continued fractions. The continued fraction expansion of \(\alpha\) provides the key to understanding the sequence of gap lengths and their evolution as \(n\) increases. Specifically, the denominators of the convergents of \(\alpha\)'s continued fraction mark the values of \(n\) where the structure of these gaps undergoes significant reorganization. Thus, the "approximability" of \(\alpha\) by rational numbers—a central concern of Diophantine approximation and characterized by its continued fraction—directly governs the pattern of gaps.

Grover's algorithm, when viewed geometrically, performs a series of rotations within a two-dimensional Hilbert space spanned by the initial uniform superposition state \(|s⟩\) and the marked (target) state \(|w⟩\). Each "Grover iteration," composed of an oracle call followed by a diffusion operation (which can be seen as an inversion about the mean of amplitudes), effectively rotates the quantum state vector by a specific angle \(\theta\) towards \(|w⟩\). This rotation angle is given by \(\theta = 2\arcsin(\sqrt{M/N})\), where \(N\) is the total number of states in the search space and \(M\) is the number of marked states. After \(r\) iterations, the cumulative rotation is \(r\theta\).

The core analogy proposed here is between this rotational dynamic in Grover's algorithm and the sequential principle of the TGT. The sequence of angular positions \(r\theta\) (modulo \(2π\)) on the unit circle (representing the quantum state's phase relative to \(|s⟩\) and \(|w⟩\)) mirrors the sequence \(n\alpha\) (modulo \(1\)) on the unit interval in the TGT. Consequently, the number-theoretic implications governing the distribution of \(n\alpha\) can be inherited to understand the behavior of \(r\theta\). We are not "approximating" the angle \(\theta\) itself in the Diophantine sense, but rather the quality of how \(r\theta\) "approximates" \(π/2\) (the angle required to align the state vector with \(|w⟩\) for maximal success probability) is subject to number-theoretic influences.

While there's an optimal number of iterations \(r_{opt} \approx \frac{\pi}{4} \sqrt{N/M}\)  for Grover's algorithm, continued iteration leads to the state vector rotating past \(|w⟩\), decreasing the success probability, only to approach it again later. The TGT, with its complex patterns of gap restructuring, suggests that subsequent near-alignments with \(|w⟩\) will not necessarily be progressively better or occur at simply predictable intervals. The precise quality of these subsequent "good" iteration counts could be dictated by the Diophantine properties of the angle \(\theta\).

This implies that the continued fraction convergents of \(\theta\) (which is itself a function of \(N\) and \(M\)) might reveal not just \(r_{opt}\), but also subsequent, potentially less optimal but still significant, iteration numbers where the state vector comes close to \(|w⟩\). The "approximability" of \(\theta\) plays a critical role:

  • If \(N\) and \(M\) are such that \(\theta\) is a "badly approximable" number (like the golden ratio, characterized by small, bounded partial quotients in its CF), the sequence \(r\theta \bmod 2\pi\)  will be very evenly distributed. This might mean achieving extremely high precision (very close alignment to \(|w⟩\)) is "harder," or that the probability of success degrades more slowly around \(r_{opt}\), or that subsequent good alignments are more spread out. This suggests a fundamental limit on the "quality" of amplification achievable for a given number of iterations, dictated by \(\theta\)'s Diophantine nature.
  • Conversely, if \(\theta\) is very well-approximated by a rational \(p/q\) with a small denominator \(q\), then after \(q\) iterations, \(q\theta\) might be very close to a multiple of \(\pi\), leading to either a very good or very poor alignment, depending on the numerator \(p\).

Therefore, the choice of \(N\) (the search space size, related to qubit count) becomes paramount, as it directly influences \(\theta\) and thus its Diophantine character. Selecting an \(N\) that results in a \(\theta\) with a "favorable" first CF convergent might yield the fastest high-probability result. However, an \(N\) leading to a badly approximable \(\theta\) (e.g., if \(\sqrt{M/N}\) is related to the golden ratio) might represent a scenario where the algorithm is robust but achieves its peak probability more "gently" and might offer fewer opportunities for significantly better alignments with further iterations.

This perspective doesn't claim to find algorithms faster than Grover's \(O(\sqrt{N})\) for unstructured search, as that bound is proven optimal. Instead, it suggests that the intricate dance of probabilities in Grover's algorithm is choreographed by deep number-theoretic principles. Understanding these principles could lead to a more nuanced comprehension of the algorithm's behavior across different problem sizes and solution densities, potentially informing choices of \(N\) or strategies for problems where multiple near-optimal iteration counts are relevant. The intertwined nature of quantum mechanics, search, and number theory suggests a rich tapestry of connections still waiting to be fully explored.


Number Theory (TGT) | Quantum Search (Grover)
Irrational slope \(\alpha\) | Rotation angle \(\theta = 2\arcsin(\sqrt{M/N})\)
Sequence \(\{n\alpha \bmod 1\}\) | Sequence \(\{r\theta \bmod 2\pi\}\)
Convergents \(p/q\) | Approx alignments \(r\theta \approx \pi/2\)
Gap restructurings | Peaks/dips in success probability
Badly approximable \(\alpha\) (golden ratio, etc.) | “Flat” amplification curve, robust but slower fall-off


Examples:


Sunday, March 30, 2025

Dual Group Structures in Diophantine Approximations

From the MLA(Mesopotamian Logarithm Algorithm) for logarithmic convergents, a similar property appears in other irrationals when analyzed in their corresponding space.


Logarithm Case Recap:

Irrational: \(\alpha = \log_b(a)\)

Convergent: \(p/q \approx \log_b(a) \Rightarrow q \times log_b(a) \approx p \Rightarrow a^q \approx b^p\)

Sequence: \(r_x = a^x \times b^{y_x}\) reduced to \([1, b)\). This is like looking at \(a^x\) "modulo \(b\)" multiplicatively. \(y_x\) tracks the 'overflow' exponent of \(b\). (This highlights the absence of a standard shorthand notation for multiplicative modulus; see link)

Sorted Sequence: Sorting \(r_x\) for \(x=1\ldots q\) gives indices \(x_k\).

Structure: \(x_k\) forms \(\mathbb{Z}/q\mathbb{Z}\) (gen \(p^{-1} \mod q\)), \(y_{x_k}\) forms \(q\) terms of \(\mathbb{Z}/p\mathbb{Z}\) (gen \(q^{-1} \mod p\)).


(Dual cyclic structure at convergents)

Let \(\alpha \in \mathbb{R}\setminus \mathbb{Q}\) with continued fraction convergent \(p/q\). Consider the rotation sequence \(r_x = \{x\alpha\}\in [0,1),\quad x=1,\dots,q\),

and let \(\sigma\) be the permutation that sorts \(r_x\) in increasing order: \(r_{\sigma(1)} < r_{\sigma(2)} < \cdots < r_{\sigma(q)}\).

Then:

(Index cycle) \(\sigma\) is an arithmetic progression modulo \(q\): \(\sigma(k) \equiv k\cdot p^{-1} \pmod q\),

where \(p^{-1}\) is the multiplicative inverse of \(p\) modulo \(q\).


(Overflow cycle / floor terms) Writing \(x\alpha = y_x + r_x\) with \(y_x=\lfloor x\alpha\rfloor\), the sequence \(y_{\sigma(k)}\) (as \(k=1,\dots,q\)) takes exactly two adjacent values that differ by 1 and forms \(q\) samples from a cycle in \(\mathbb{Z}/p\mathbb{Z}\) whose step is \(q^{-1}\pmod p\).


(Gap control) The consecutive differences \(r_{\sigma(k+1)}-r_{\sigma(k)}\) take two values (the “short” and “long” gaps) determined by \(p/q\); this is the Three Gap Theorem specialized at a convergent, where only two gaps appear across the first \(q\) points.
 
Proof sketch

Because \(p/q\) is a convergent, \(\|q\alpha-p\|\) is minimal in its range. The return map of the rotation by \(\alpha\) to the set of \(q\) points partitions the circle into two gap lengths. (TGT gives gap sizes.)


The order of the points is governed by the congruence \(x\alpha \approx x\frac{p}{q}\) modulo \(1\), so sorting by \(x\alpha\) matches sorting by \(xp/q\) modulo \(1\). The residues \(xp \bmod q\) run through \(\mathbb{Z}/q\mathbb{Z}\) in steps of \(p\), hence the sorting permutation is
\(\sigma(k)\equiv k\cdot p^{-1}\ (\bmod q)\). (This gives gap order.)


The floor/overflow terms satisfy \(y_{\sigma(k+1)}-y_{\sigma(k)} \in \{\lfloor p/q\rfloor, \lceil p/q\rceil\}\),

and, tracked modulo \(p\), they advance by \(q^{-1}\) because
\(q\alpha\approx p\) forces \(p\) steps in \(\alpha\)-space to coincide with \(q\) wraps. This yields the dual \(\mathbb{Z}/p\mathbb{Z}\) cycle.
 
(Logarithmic case via an isomorphism)

Let \(a,b>1\) and set \(\beta=\log_b{a}\). Define the multiplicative sequence \(R_x \;=\; a^x\, b^{-y_x} \in [1,b),\qquad y_x=\big\lfloor x\beta\big\rfloor\).

Then \(R_x = b^{\{x\beta\}}\). Hence ordering the \(R_x\) is the same as ordering \(\{x\beta\}\), and all claims of the Theorem transfer with \(\alpha=\beta\):

Sorting indices are \(\sigma(k)\equiv k\cdot p^{-1}\ (\bmod q)\) for any convergent \(p/q\) of \(\beta\).

The overflow exponents \(y_{\sigma(k)}\) form \(q\) samples from a \(\mathbb{Z}/p\mathbb{Z}\) cycle with step \(q^{-1}\ (\bmod p)\).

The MLA’s “stack-and-fold” is just rotation on the circle in log-coordinates, so its consecutive outputs are convergents whenever you use windows aligned with denominators \(q\).


Every Diophantine approximation problem generates a dual pair of cyclic group structures, one indexed by the convergent’s denominator, one by its numerator. a lattice of relationships between \((p,q)\) and their inverses modulo each other. It's not just about inequalities, but about explicit dynamical group actions tied to each irrational. For irrational \(\alpha\), from the overflow sequence of its natural dynamical action produces exactly the convergents of its continued fraction.



Trigonometric Case (Angle)

Irrational: We need an irrational quantity related to the angle. Let's use \(\alpha = \theta / (2\pi)\). (assuming \(\theta\) is not a rational multiple of \(2\pi\)).

Convergent: \(p/q \approx \theta / (2\pi) \Rightarrow q \times \theta / (2\pi) \approx p \Rightarrow q\theta ≈ 2\pi p\). This means \(q\) rotations by \(\theta\) is close to \(p\) full \(2\pi\) rotations.

Sequence: What's the equivalent of \(a^x \mod 1:b\)? The natural analogue for angles is \(x\theta \mod 2\pi\). Let \(r_x = (x\theta) \pmod{2\pi}\). This sequence lives in \([0, 2\pi)\).

What is \(y_x\) ? It's the number of full rotations removed: \(xθ = y_x \times 2\pi + r_x\). So, \(y_x = \lfloor x\theta / (2\pi)\rfloor\).

Sorted Sequence: Sort \(r_x\) for \(x=1\ldots q\) to get indices \(x_k\).

Structure: \(x_k\) forms \(\mathbb{Z}/q\mathbb{Z}\) (gen \(p^{-1} \mod q\)), \(y_{x_k}\) forms \(q\) terms of \(\mathbb{Z}/p\mathbb{Z}\) (gen \(q^{-1} \mod p\)).




This directly mimics the log case by replacing the multiplicative group \((\mathbb{R}^+, \cdot)\) modulo \(b\) with the additive group \(\mathbb{R} \mod 2\pi\) (the circle group \(S^1\)). The relationship \(q\theta \approx 2\pi p\) is the direct analogue of \(a^q \approx b^p\). The Three Gap Theorem describes the structure of the sorted \(r_x\) values (the points \(x\theta \mod 2\pi\) on the circle), and their ordering is intimately linked to the continued fraction convergents \(p/q\). The generators likely arise from the relationship \(q(p'/q') - p(q'/q') = \pm \)1 between consecutive convergents.


(Need to test which inverse/element works. The structure \(p_{n-1} q_n - p_n q_{n-1} = (-1)^n\) from continued fractions is key here, likely determining the specific generators.)

Tuesday, November 5, 2024

Interval Reduction (Multiplicative mod)

This page is dedicated to the interval reduction operation, a foundational concept in music theory that I’ve explained briefly in other articles where it often plays a key role. Interval reduction is a universal yet frequently misunderstood process, with "octave reduction" as one specific example. Here, I offer a formal definition and consistent mathematical notation for interval reduction, aligning it with the notation developed for the interval matrix. This approach provides a basis for broader generalization in music analysis and tuning theory.

Essentially, this is a shorthand notation for the multiplicative counterpart of the regular (additive) modulus.

Note on Ratio Notation: In music theory literature, ratios and fractions are often used interchangeably, particularly when discussing relationships like string length, frequencies, harmonics, or subharmonics. This overlap can lead to ambiguity, especially when referring to intervals without specifying direction. For instance, while octave equivalence remains clear across notations (1:2, 2:1, 1/2, 2/1), we may lose the specific octave reference—whether above or below—if this is not explicitly noted. Even worse with 2:3, 3:2, 2/3, 3/2, without specifying we can't be sure if it's a fifth or a fourth.

To address this, we follow the convention that treats ratios like 4:5:6 as indicative of pitch relationships, where each number represents a multiple of a fundamental (1). For example, in this format, 4:5:6 represents a major chord as the intervals 1/1, 5/4 and 6/4=3/2.

Examples:
- Octave (second harmonic): Ratio 1:2, Fraction 2/1, Decimal 2
- Second Subharmonic: Ratio 2:1, Fraction 1/2, Decimal 0.5
- Fifth: Ratio 2:3, Fraction 3/2, Decimal 1.5
- Fourth (below unison): Ratio 3:2, Fraction 2/3, Decimal 0.666...

This notation standard helps clarify both direction and pitch relationships, reducing ambiguity when discussing intervals and chords across different contexts.

Interval Definition:
To avoid ambiguity, interval here refers specifically to a musical interval, where values represent multiples of a fundamental frequency, typically normalized to a unison. When referring to a mathematical range, such as \((1,2]\), we will use the term space.
This distinction helps clarify references to musical intervals, such as the octave (a frequency multiplier with a value of 2), as distinct from the octave space, defined as any interval \((a,2a]\) for \(a \in \mathbb{R^+}\).


Interval Reduction

Definition:
Interval Reduction is a scaling transformation that maps a positive real number \(x\) within the bounds of a specified space, denoted \((1,b]\), by repeatedly multiplying or dividing \(x\) by \(b\), until \(x\) falls within \((1,b]\). Here, \(b,x \in \mathbb{R}^+ \) with \(x \notin (1,b]\).

Notation:
The interval reduction operation can be represented as a mapping into a modular "interval space." We use the following notation to generalize this process concisely:

Using the mod operator:
\[x \bmod 1:b = [x] \] where \([x]\) represents the equivalence class or representative of \(x\) within the \((1,b]\) space.

This notation mirrors modular arithmetic while specifying that it applies to interval reduction:
\[ x \equiv [x] \pmod {1:b} \] To capture all equivalence classes in a similar form:
\[ xb^n \equiv [x] \pmod {1:b},\, n \in \mathbb{Z} \] This expression shows that the fifth 2:3 is the class representative in octave space of the third harmonic (1:3), the sixth (1:6), twelfth (1:12), (1:24), (1:48), and so on, with respect to unison.

Example Application:

For \( x=48, b=2\):
\[48 \bmod 1:2 = 1.5 = 3/2 \text{ (Fifth)}\] Normalization for Other Ranges:

To perform interval reduction in ranges other than \((1,b]\), normalize the space as follows:

\(x \bmod a:b ⇒ x \bmod 1:b/a \)

For example, with \(x=7, a=4, b=5\):
\[7 \bmod 4:5 = 7 \bmod 1:5/4 = 1.174\ldots\]This approach is particularly clear for rational values in the space. We avoid directly writing \(7 \bmod 5/4\) to prevent confusion with traditional modular arithmetic; using ratio notation, \(7 \bmod 4:5\) explicitly denotes interval modularity, simplifying it as \(7 \bmod 1:5/4\). For spaces involving irrational values, we write the ratio starting from 1, such as \(5 \bmod 1:\sqrt{2}\), to maintain clarity.

The process can also be expressed explicitly using logarithms and the classic mod operator:
\[ x \bmod a:b = (b/a)^{log_{b/a}(x) \bmod 1} \] Example:
\[5 \bmod 1:2 = 2^{log_2(5) \bmod 1} = 5/4 = 1.25 \text{ (Major third)}\] In this case, we map the fractional part of the logarithm (base 2) of 5 into the octave cycle.

(The following clarifies the notation I used earlier, which appears in videos and some texts that may be found on the web, but is now deprecated)

While interval reduction is not a strict mathematical function—relying on iterative scaling rather than a single closed-form—it can be expressed as a function, especially within octave space. This space is particularly relevant to music theory as it relates to chroma equivalence and pitch grouping in human perception. Here, the "octave reduction" is the chroma function:
\[\Xi(x) = x \bmod 1:2 = 2^{log_2(x) \bmod 1}\] This function is a special case of our interval reduction process, where b = 2. This "octave reduction" maps any positive number to its equivalent within the octave cycle, representing its chroma.
We can extend this idea to define a general chroma function \(\Xi_{1:b}(x)\), where 'b' defines the specific interval space: \[\Xi_{1:b}(x) = x \bmod 1:b\] Example, for \( x = 7, b = 5/4\): \[\Xi_{4:5}(7) = 1.17440512\] Therefore, \(\Xi_{1:b}(x)\) effectively represents interval reduction within a given space. The chroma function \(\Xi(x)\), previously used in my work, is a specific case of this more generalized interval reduction function that without parameters, defaults to octave space.

The choice of notation can depend on context. For example, if one simply needs to find the chroma of a pitch within a tuning system, the compact chroma function provides a straightforward approach. However, the modular notation for interval reduction clarifies the process when building tuning systems and can also be applied in other mathematical contexts. For instance, in \( x \bmod 1:b = [x]\), the modularity is evident by viewing the operation as \(x \bmod 1:b = x/b^n\) , where \(n\) is the integer that scales \(x\) into the space \((1,b]\). While our primary interest may be in the result, here [x], the value of \(n\) and the sequences it generates with various inputs form the basis of the logarithm algorithm I introduced in [link].

Coding:
Most programming languages support logarithmic functions, so the chroma function can be implemented concisely. For example, in Python:

import math

def chroma(x):
    return 2 ** (math.log2(x) % 1)

This implementation uses logarithmic reduction to map x to its equivalent within the octave space (1,2]. However, for a more generalized approach that applies to any interval space (1,b], here’s the Python code to perform interval reduction for x mod 1:b :

def interval_reduction(x, b):
    # Ensure inputs are positive real numbers and x is outside (1, b]
    if x <= 0 or b <= 1 or (1 < x <= b):
        raise ValueError("Ensure x > 0, b > 1, and x is not within (1, b].")

    # Apply interval reduction by scaling x within the (1, b] range
    while x > b:
        x /= b
    while x <= 1:
        x *= b
       
    return x

Tuesday, August 20, 2024

The Interval Matrix


DRAFT
This article introduces the concept of the interval matrix from a traditional music theory perspective, alongside a software tool designed to create and visualize these matrices. In this context, intervals refer to proportions or ratios between numbers.

The interval matrix is built from all possible representations of a set's values under an equivalence relation, using each element as a base, resulting in a numerical or geometrical table—a matrix—that represents this expansion.

These matrices are not initially intended for conventional matrix operations; the focus lies in the geometric structure that emerges from different sets and their elements' relationships.

Interval Matrix software. Prime numbers up to 19(set to periodic), with equivalence 1:2 (octave-space)
\(\mathbf{Ä}_{1:2}(P_{19})\)


For an infinite set, the matrix cannot be fully generated. However, if the set has a repeating pattern (period), a minimal generating set can be identified. The matrix is then built and completed using this minimal set, (n-by-n) as seen in a common musical tuning system (a set of pitches or rhythms used to create or perform music).

This period typically becomes the primary equivalence relation (equave) parameter in the set's function for constructing the matrix and analyzing the intervals within.

The matrix can be constructed for a finite set that isn't meant to repeat. For example, in music, this approach can be used to analyze notes on an instrument where there's no indication to continue calculating additional pitches. This method applies to any finite set. In a finite matrix, each row contains one element less than the previous row.

Set and matrix construction:

For analyzing a set \(S\) that is already normalized and within the desired range—such as in any pre-calculated musical tuning system—the set remains unaltered, and the matrix is built directly \(\mathbf{A}(S)\). The only required parameter is its periodicity: Is the given set a minimal generating set of an infinite set, or does it represent a fixed, finite number of elements?

Most examples here will use periodic matrices. To denote matrix periodicity or non-periodicity, we might use different notation, such as \(\mathbf{Ä}\) for periodic matrices and \(\mathbf{A}\) for non-periodic ones.

The generalization of the interval matrix construction allows us to relate different sets and reductions, enabling us to find congruences between systems. The reduction function (which corresponds to the chroma function when the space is the octave, 1:2) for a real matrix, where the set consists of any real numbers, operates as follows:

The absolute value of each element is taken, and the function then returns this value, reduced or remapped (if necessary) by an equivalence relation:

For a value \(s_x\) larger or smaller than the chosen equivalence relation \(r\), it is reduced to a new element \(\tilde{s}_x\) by applying the operation:

\(\tilde{s}_x = |s_x| \bmod 1:r\)

(This uses the mod symbol because it effectively returns the intervallic remainder. This process involves repeatedly multiplying or dividing \(s_x\) by \(r\) until \(s_x\) falls into \((1, r]\) space. This page has details about interval reduction.)

Since the matrix is defined by reinterpreting the set values with each element as the base, all rows inherently start with 1. Consequently, the reduction, or normalization, is consistently performed as \(\bmod 1:r\)

Optional: A constant \(\delta\) may be applied to each element of the set before performing the base change.(this in relevant for other uses explained in other article)

The reduction can be notated and performed for sets \(S_{1:r}\) without considering any matrix. It can also be used in constructing the matrix, \(\mathbf{A}_{1:r}(S)\), which implies both reduction and base shifting.

Example: If \(S\) = {1, 2, 3, 5}, then \(S_{1:2}\) ​= {1, 3/2, 5/4, 2}, and \(\mathbf{Ä}_{1:2}(S)\) would yield [{...},{...},{...},{...}]. (reduced and periodic)

Interval Matrix Definitions:

  • Full Interval Matrix: \(\mathbf{A} = \mathbf{A}_{s_n}^{\delta}\)
    This matrix uses the last or largest element of its generating set as the equivalence relation.
  • Local Interval Matrix: \(\mathbf{A}_{s_i}^{\delta}\)
    This matrix uses any element within the generating set as the equivalence relation, except for the largest one.
  • External Interval Matrix: \(\mathbf{A}_{x}^{\delta}\)
    This matrix uses a value outside the generating set as the equivalence relation. 


A full interval matrix built from a periodic set is inherently a symmetric matrix.

A full or local interval matrix is not "useful" for isotropic sets (where the chosen period or relation is a member of the set). This leads to identical and overlapping shifts of the elements.

Musical Interpretation:
For example, the 12-tone equal temperament \(\text{12ed2}\) guitar is an interval matrix (incomplete) representing the infinite set generated by the constant \(2^{1/12}\). Each row is shifted by five elements from the previous row (except between \(\text{G}\) and \(\text{B}\), where the shift is four). The matrix is trivial for this set's intervallic analysis, as columns (frets) are always aligned regardless of the shift or element taken as base.

Interval matrices are tipically shifted by one element until they are complete.

Consider this group: \(\langle 2, 3 \mid 3^2 = 1 \rangle \). This represents a set of infinite fifths and octaves. One of its minimal generating sets is \(S\) = (1, 3/2, 2]. The resulting matrix \(\mathbf{Ä}_{1:2}(S)\) has only two rows:

(1,  3/2,  2]
(1,  4/3,  2]

Interval Matrix Accumulation: \(\text{Acc}(\mathbf{A}(S))\)

This is a new set with all the representations of the elements under the set equivalence relation, which unfiltered, might repeat values, helping to find prevalent proportions. Isotropic sets always have an accumulation identical to any of their matrix rows. (The accumulation is a vectorization or flattening of the matrix)

In this case, the infinite set generated by \(\langle 2, 3 \mid 3^2 = 1\rangle\) = { ..., 1/2, 2/3, 1, 3/2, 2, ...} has an interval accumulation (under the equivalence 1:2):  (1, 4/3, 3/2, 2].

The distinction between full, local and external interval accumulations reflects the matrix type.

For example, consider a local matrix \(\mathbf{A}_{1:2}(S)\) constructed from the set {1, 2, 3, 4} in octave space (with an equivalence relation of 1:2). The local accumulation would be:

\(\text{Acc}(\mathbf{A}_{1:2}(S))\) = {1, 4/3, 3/2, 2} (filtered, with non-repeated values)

To obtain the global or full accumulation, the space is set to the largest element in the set. Thus, the matrix built from the set {1, 2, 3, 4} under the equivalence relation 1:4 would yield:

\(\text{Acc}(\mathbf{A}(S))\) = {1, 4/3, 3/2, 2, 3, 8/3, 4} (filtered)

For larger and more complex sets, the accumulation also provides a method for finding a possible natural mode of the set, if any.

Let’s take the pentatonic \(\langle 2, 3 \mid 3^5 = 1 \rangle\)
a minimal generating set is { (1, 9/8, 81/64, 3/2, 27/16, 2/1] }, its full matrix (omitting 1):

{9/8,  81/64, 3/2,    27/16, 2/1}
{9/8,    4/3, 3/2,    27/16, 2/1}
{9/8,    4/3, 3/2,    16/9,  2/1} Natural Mode
{32/27,  4/3, 3/2,    16/9,  2/1}
{32/27,  4/3, 128/81, 16/9,  2/1}

The natural mode of any set is the particular representation that includes the most frequent values appearing after shifts; it is the most faithful or weighted representation of the set.


How the Interval Matrix App Works

It accepts a list of numbers, treating them always as a minimal generating set(for now).

If the list/set is an already a reduced tuning system, the matrix is full and the equave(period, interval of equivalence) parameter should initially be set to match that of the set, typically the last and largest value. It does not adjust it automatically.

The matrix displays for each element in each row: the original value inserted, the reduced value(if it was reduced), a delta value(if it was displaced), and a rational approximation of the value.

The delta value comes from the delta parameter, usually 0. This value is added to every element in the original set before the rest of the calculations. This is useful for understanding how a minimal set, while maintaining its original absolute difference between members, shapes through this change.

For example, you can start with period/equave 1:2, and this set {1,2,3} reduces to {1, 3/2, 2}, but with delta = 3, it becomes {4, 5, 6}, and reduced, {1, 5/4, 3/2, (2)}.

Prime numbers up to 19. Delta = -1, octave-space.
\(\mathbf{Ä}_{1:2}^{-1}(P_{19})\)

The rational approximation has an adjustable tolerance value.

On top of the interval matrix, there is a configurable equal division ruler that helps with intervallic/ratio measures.

The chroma matrix has a fixed equivalence relation of an octave and, by default, starts at red. You can select whether the chromas displayed are absolute or relative to each row. When selecting relative, the full spectrum located in the bottom UI expands to display all the possible chroma shifts. (The full spectrum isn’t really "full"—you set a maximum space to occupy, with a logical maximum of the human hearing range.)

This last part is the most important when dealing with musical tuning systems; practical tuning systems have a simpler chroma matrix.

Unlike Scala files, the 1 must be inserted (remove it to understand what happens). You can, if you want, omit the equave in this list; it will be added (invisibly) from the equave parameter. However, it’s useful to keep it too, for example, when analyzing a non-octave tuning using an equave 3 (tritave). You can omit it, but if you want to inspect these intervals reduced to an octave, you might want to keep it and track it. So if when the set has an element equal to the equave, you will find two identical rows in the matrix.

Future Development

If you paid close attention to the code of this app and the SFINX app, you may have noticed that they use the same engine. That’s because, as I have pointed out, a guitar is essentially an interval matrix by string length.

My goal is to finally reunite both apps—SFINX was developed to aid in the graphic and diagram generation of scales for microtonal guitars, while the Interval Matrix was developed ideally for geometric analysis of sets and chromas.

(DRAFT)

Link to the apps:

jbcristian.github.io/xeneize/




Thursday, August 8, 2024

Pythagorean Scale ≅ Z/12Z ⊕ Z

Pythagorean Scale and Group Theory

The Pythagorean Scale and related tuning systems across cultures exhibit a clear group-theoretic structure, specifically forming finitely generated abelian groups. This analysis reveals that the algorithmic basis of these scales not only defines their musical properties but also implicitly encodes a method for approximating logarithms, as explored in a companion study. This suggests that early music theory, across diverse traditions, may represent a proto-group-theoretic framework with unexpected computational capabilities.

I. The Pythagorean Scale

The Pythagorean Scale is one of the most well-known tuning systems from antiquity and continues to influence Western music theory. While similar intervals and generative methods are found in other cultures (1), the scale remains a fundamental example within the broader Pythagorean framework of number and harmony. Musicians beginning their study of tuning theory often learn about the Pythagorean Scale as a precursor to modern equal temperament (12EDO). However, this characterization is not entirely accurate (2).

A multitude of tuning systems has existed since antiquity, and in modern times, many more have emerged due to the ease of implementation and experimentation with synthesizers and computers. While some contemporary tuning systems employ sophisticated mathematical concepts, group theory is frequently applied to both tuning definitions and musical analysis. Despite the prevalence of textbooks linking music to algebraic structures, the Pythagorean Scale itself has not been explicitly identified as an instance of group-theoretic structure in either musicological or mathematical literature.

Ancient theorists did not conceptualize musical intervals as elements of an algebraic group. Instead, they developed practical tuning methods that implicitly embody group-theoretic principles, driven by the acoustical properties of intervals and human perceptual preferences. Still, it is accurate to describe the Pythagorean Scale (and its cross-cultural analogs) as one of the oldest implicit examples of a finitely generated abelian group (FGAG). This retroactive classification underscores the universality of mathematical patterns in music, even when the underlying theory remained undiscovered for millennia.

This study shows that the group structure is inherent to the algorithm used to construct the scale, as reflected in modern interpretations found in numerous music theory textbooks and historical references (e.g., Boethius, Ptolemy, Guido d'Arezzo, Vincenzo Galilei).

It is important to acknowledge that this analysis presents a specific perspective on the Pythagorean Scale, focusing on its algorithmic structure. Historically, the scale has been interpreted through various lenses, including harmonic theory, philosophical considerations, and perceptual studies. This paper does not seek to invalidate those interpretations but rather to provide a complementary perspective rooted in group theory. The focus remains on the mathematical properties of the algorithm itself, independent of any particular musical application or aesthetic judgment.

Some may argue that labeling ancient tuning systems with modern algebraic terminology is anachronistic without explicit recognition of group axioms. However, in mathematics, it is common practice to retroactively classify structures once their properties are understood. For example, ancient symmetries are now described using group theory.

The following sections will review the historical context, examine the algorithmic generation of the scale, and formalize it using group theory, revealing a direct correspondence.

II. Historical Context & Algorithmic Generation

Many tuning systems share a common foundation, historically referred to as "chaining/stacking and reducing/folding" or its linguistic equivalents (e.g., "encadenamiento y cancelación" in Spanish). This method, exemplified in the Pythagorean tuning system, involves repeatedly adding intervals (specifically, perfect fifths) and reducing the results by octaves (a 1:2 ratio). This principle finds parallels in ancient Mesopotamian and Chinese musical systems, suggesting a universal approach to generating scales and temperaments.

The Chinese sanfen sunyi system, also known as the shí’èr lǜ (十二律) or "twelve-pitch" system, documented in texts such as the Lüshi Chunqiu and the Huainanzi, involves successively raising a pitch by a perfect fifth and then lowering it by an octave. This process closely resembles the "chaining/stacking and reducing/folding" method and results in a twelve-tone scale strikingly similar (identical) to the Pythagorean system. This historical evidence suggests that the concept of generating scales through interval manipulation was present in ancient Chinese musical thought, even if not formalized in group-theoretic terms.

Similarly, recent translations of cuneiform tablets from ancient Mesopotamia (3) reveal sophisticated tuning practices. These tablets describe step-by-step scale generation and document modal relationships as cyclic permutations of interval sequences. This implicit understanding of group-like structures highlights the mathematical depth of early musical systems.

The Algorithm

The Pythagorean tuning algorithm is introduced here in its most common interpretation. While historically (or folklorically) Pythagoras is said to have derived the scale from a monochord, bells, or even hammers (4), the fundamental method remains consistent regardless of the starting point. The arithmetic operations are adjusted accordingly for either string-length or frequency-based interpretations. This study adopts the frequency-based interpretation, as modern music theory represents tuning systems as sets of frequency multiples and provides clear mathematical notation for these operations.

The algorithm can be understood as follows:

1. Establish octave equivalence: Pitches at twice the frequency (or half the string length) are perceived as equivalent, forming a cyclic structure with the ratio 1:2. 
2. Generate new pitches using the perfect fifth (3/2): This interval is derived from the third harmonic (3/1), reduced to the octave range. 
3. Stack fifths and fold back into the octave: Iteratively applying the fifth and reducing by octaves when necessary.

For simplicity, examples use the Pythagorean pentatonic scale, corresponding to the first five notes obtained from the method.

Pythagorean Pentatonic Scale Construction:

- Initial notes: {1/1 (Unison), 2/1 (Octave)}

- Generate the first fifth: 1/1 * 3 = 3/1 → Reduced to 3/2

- Compute another: (3/2) * 3 = 9/2 → Reduced to 9/8

- Compute next: (9/8) * 3 = 27/8 → Reduced to 27/16

- Continue iterating…

Stopping at five iterations for the pentatonic, the resulting scale in ascending order is:

{ 1, 9/8, 81/64, 3/2, 27/16, 2/1 }

\(2^0 \times 3^{0  \bmod 5}\)\(2^{-3} \times 3^{ 2 \bmod 5}\)\(2^{-6} \times 3^{4 \bmod 5}\)\(2^{-1} \times 3^{1  \bmod 5}\) \(2^{-4} \times 3^{3 \bmod 5}\)\(2^1 \times 3^{5  \bmod 5}\)
19/881/643/2 27/162/1

This set embodies the distinct elements of the pentatonic group, excluding octave duplicates.

(Note: The scale is often shifted using a different base, such as 9/8, yielding {1, 9/8, 4/3, 3/2, 16/9, 2/1}. Due to its cyclical nature, the starting point is relative.)

Since the octave serves as a period, the generated set is duplicated to extend the scale across an instrument’s range.

Some may argue that historical theorists, such as Guido d'Arezzo, worked with a fixed number of pitches without explicitly considering infinite extension. However, as musical practice expanded, scales were extended using the underlying infinite representation inherent in the algorithm.

It becomes evident that the algorithm simultaneously generates the group and selects a subset.

A more concise representation of the algorithm considers the exponential sequence {3^0, 3^1, 3^2, ...}, reduced modulo 1:2, and ordered by size. \(r_x = a^x \times b^{y_x} \in [1, b)\).

III. Group-Theoretic Formulation

Defining the Generators

As the algorithm implies, every pitch in the Pythagorean Scale, whether the full 12-tone system or the pentatonic subset or any k-cycle, can be expressed as products of powers of its fundamental generators: the octave (2) and the perfect fifth (3).

These two harmonics serve distinct roles:
- The octave (2/1) functions as a free generator, unrestricted in its powers.
- The fifth (3/2) is constrained by a modular cycle in the pentatonic case, specifically, a 5-cycle.

Thus, each pitch in the pentatonic scale can be represented as a product of powers of these generators. Using standard group notation:
\[
\text{Pentatonic} = \langle 2, 3 \,|\, 3^5 \equiv 1 \rangle
\] where any pitch \( p \) can be written as:
\[
 p = 2^n \cdot 3^{m \bmod 5}, \quad \text{with } n, \; m \in \mathbb{Z}
\] This notation aligns with standard finitely generated abelian group (FGAG) representations, analogous to:
\[
G = \langle a, b \,|\, b^k = 1 \rangle.
\] Group Properties

The structure of the Pythagorean scale follows naturally from the algorithmic process of stacking fifths and reducing by octaves:

- Commutativity: Since multiplication in the frequency domain is commutative, the group operations inherit this property.
- Identity: The unison (1/1) acts as the identity element, represented as \( 2^0 \cdot 3^0 = 1 \).
- Inverses: The group inherently contains inverse elements due to the modular restriction.
- Closure: Any two pitches \( p_1 = 2^{n_1} \times 3^{k_1 \bmod 5} \) and \( p_2 = 2^{n_2} \times 3^{k_2 \bmod 5} \) multiply as:
\[
p_1 \cdot p_2 = 2^{n_1 + n_2} \times 3^{(k_1 + k_2) \bmod 5}
\]Since exponents of 3 are taken modulo 5, results remain within the defined group, ensuring closure.

Structural Clarification

The Pythagorean scale, and its cyclic subsets like the pentatonic, are not built from arbitrary powers of 2 and 3. Instead, each pitch class is of the form: \(p = 2^n \cdot 3^{m \bmod k}, \quad \text{with } n \in \mathbb{Z},\; m \in \mathbb{N_0},\; k \in \mathbb{N}\).

This definition differs crucially from the unrestricted "3-limit tuning group" \(\langle 2, 3 \rangle \subset \mathbb{Q}^+\), where both exponents range freely over \(\mathbb{Z}\), and the resulting structure is infinitely generated and not bounded within an octave.

Here, the modulo operation on the exponent of \(3\) constrains it to a cyclic subgroup of order \(k\), making the set of pitch classes isomorphic to: \(\mathbb{Z}/k\mathbb{Z} \oplus \mathbb{Z}\), which is a finitely generated abelian group: a product of a finite cyclic group (mod-k fifths) and the infinite cyclic group generated by octave shifts.

The operation remains standard multiplication in \(\mathbb{Q}^+\),
But the set is closed under modular identification of one of the generators, resulting in a well-structured group.

Notes:
1.  The 3-Limit is Dense: The set \(P = \{ 2^n \times 3^m \,|\, n, m \in \mathbb{Z} \}\) under standard multiplication is a group (isomorphic to \(\mathbb{Z} \oplus \mathbb{Z}\)), but it represents all possible intervals generated solely by octaves and perfect fifths/fourths. It's dense within the positive rationals and doesn't represent a discrete scale with a repeating structure.
2.  The \(\mod k\) Creates the Scale Structure: The crucial step in defining a specific Pythagorean scale (like the 12-tone or 5-tone) is imposing the cyclic identification \(3^k \sim 1\) (modulo octaves). This is what limits the distinct pitch classes derived from the \(3\) generator to \(k\) consecutive possibilities.


IV. Cultural Analogs

While the FGAG structure has been demonstrated for the Pythagorean scale, other historical tuning systems require careful consideration. For example, the Chinese temperament has a rich and multifaceted history. While many musicologists equate it with the Pythagorean system, some disagree. Given its nuances, a rigorous classification of its group structure needs a separate study.

The Sanfen Sunyi method (三分损益法, c. 500 BCE), which constructs scales by alternating multiplication by \(3/2\) and division by \(3\) (equivalent to multiplying by \(2/3\)), followed by octave reduction. This process explicitly generates a cyclic subgroup of \( \mathbb{Q}^+/\langle 2 \rangle \), aligning with FGAG structures.

A more challenging case is the Mesopotamian tuning system, dating back to 2500 BCE. Cuneiform tablets describe tuning procedures that cyclically permute intervals, akin to generating cosets in a quotient group. While less explicit than the Pythagorean or Chinese systems, this suggests an intuitive grasp of modular arithmetic and group-like structures.

The key controversy lies in interpretation: these tablets do not explicitly reference octaves, fifths, or the numbers 2 and 3. Instead, reconstructions rely on geometric depictions of tuning procedures for the lyre.

Algorithmic Basis of the Structure

The group structure arises naturally from the algorithm rather than any inherent musical qualities. The selection of generators and modular constraints is parametric rather than fundamental. For instance, in this video [link], the scale demonstrated is constructed using the same framework but employs different generators. Instead of the octave and fifth, it uses the golden ratio (phi) and the square root of 5 as the period. \[ \langle \sqrt{5}, \sqrt{\phi} \,|\, \sqrt{\phi}^{10} \equiv 1 \rangle \]
This insight has direct applications in modern music theory, which already incorporates algebraic methods.

Note: different theoretical schools often introduce overlapping terminology. Some branches of xenharmonic music theory, for example, employ group-like concepts but hesitate to fully embrace the existing mathematical framework. The frequent disclaimer that "this group is not a group in the mathematical sense" only adds unnecessary complexity. In reality, both set theory and group theory already provide comprehensive tools for analyzing musical structures, from noise to harmonic organization.

Not all tuning systems can be fully described as groups.

While this study focuses on well-structured cases, many historical systems do not rely on the same principles and may be better understood as sets rather than algebraic groups. However, group theory remains a powerful tool for analyzing ancient musical structures, and many lesser-studied tuning systems may reveal even deeper mathematical properties.

Additionally, while the algorithm itself is simple, it provides a remarkably robust framework, aligning with well-classified FGAG structures. A forthcoming (7) extends this algorithm, revealing that it is one condition away from functioning as a logarithm calculator.

Revisiting ancient mathematical and musical traditions continues to enrich both fields, with potential applications in modern tuning theory, digital synthesis, and mathematical musicology.

V. Conclusion

This study has demonstrated that the Pythagorean scale—and its cross-cultural analogs—exhibits a clear group-theoretic structure. This is not merely a retroactive classification; rather, it underscores the universal and enduring nature of these structures across musical traditions.

The supplementary study, Mesopotamian Logarithm Algorithm, hints at even deeper historical roots, suggesting that ancient musicians may have unwittingly applied mathematical principles that would only be formalized millennia later.

(draft)

VI. Extra:

Isomorphism

The pentatonic group is isomorphic to the direct sum of:
- A cyclic group of order 5 (capturing the modulo constraint on powers of 3).
- An infinite cyclic group (capturing the free octave generator).

Thus,
\[
\langle \text{Pentatonic} \rangle \cong \mathbb{Z}/5\mathbb{Z} \oplus \mathbb{Z}.
\]Defining the mapping:
\[
\varphi(p) = (k \bmod 5, n) \quad \text{for } p = 2^n \times 3^{k \bmod 5}.
\]
For any two pitches \( p_1 = 2^{n_1} \times 3^{k_1 \bmod 5} \) and \( p_2 = 2^{n_2} \times 3^{k_2 \bmod 5} \),
\[
p_1 \cdot p_2 = 2^{n_1 + n_2} \times 3^{(k_1 + k_2) \bmod 5}
\] Applying the mapping:
\[
\varphi(p_1 \cdot p_2) = ((k_1 + k_2) \bmod 5, n_1 + n_2).
\]
In \( \mathbb{Z}/5\mathbb{Z} \oplus \mathbb{Z} \), the operation is component-wise addition:
\[
\varphi(p_1) + \varphi(p_2) = ((k_1 \bmod 5, n_1) + (k_2 \bmod 5, n_2)) = ((k_1 + k_2) \bmod 5, n_1 + n_2).
\]
Since \( \varphi(p_1 \cdot p_2) = \varphi(p_1) + \varphi(p_2) \), the mapping preserves group structure, proving the isomorphism.

Thus, the pentatonic scale is structurally identical to \( \mathbb{Z}/5\mathbb{Z} \oplus \mathbb{Z} \), confirming its classification as a finitely generated abelian group.


Extended Applications of Group Theory

Invariance Under Transposition

Transposition—shifting all pitches by a fixed interval—corresponds to group translation. For instance, transposing by a perfect fifth (\(3/2\)) maps to the transformation:
\[
(m, n) \mapsto (m+1 \bmod 5, n)
\]
in \( \mathbb{Z}/5\mathbb{Z} \oplus \mathbb{Z} \). The invariance of this operation under the group structure confirms the isomorphism, reinforcing the robustness of this algebraic model.


Excluding Specific Harmonic Classes


The classic diatonic group is defined as:
\[
D = \langle 2, 3, 5 \mid 3^4 \equiv 1, \, 5^2 \equiv 1 \rangle.
\]
Initially, every note has a major third. To exclude the major third of "Re" (\(D\)), we identify the subgroup:
\[
H = \langle 2^n \cdot 3^3 \cdot 5 \rangle,
\]
which represents this interval. By forming the quotient group \( D/H \), we impose the relation:
\[
3^3 \cdot 5 = 1.
\]
This effectively removes the "Re" major third while preserving other intervals. This demonstrates how quotient groups can selectively eliminate harmonic classes within a tuning system’s algebraic structure.



\( \text{Golden Harmonics} = \langle \sqrt{\phi}, \sqrt{5}\,|\, (\sqrt\phi)^{10} \equiv 1\rangle \)

Saturday, August 3, 2024

Mesopotamian Logarithm Algorithm

It's been some time since I wrote this article, and upon re-reading it, I’d like to clarify something to avoid potential misinterpretation: I’ve named it the Mesopotamian Logarithm Algorithm because the algorithm and visualizations I used are inspired by Mesopotamian music theory. While I analyze some of the cuneiform tablets and replicate their logic, this is a modified version of their scale generation method. It is not a claim that they used this process for calculating logarithms.
Draft: MLA.pdf there is an error in the algorithm description, see the code for clarity!

Logarithmic Convergents: A Musical Algorithm Reveals Dual Group Structures

This paper introduces the Mesopotamian Logarithm Algorithm (MLA), a method for computing logarithmic convergents inspired by traditional musical scale construction techniques. Diverging from standard continued fraction approaches, the MLA utilizes a musically intuitive "chaining and reduction" process, driven by the identification of musical commas (near-alignments), to determine convergents of \(\log_b(a)\) without explicit logarithm computation. A central contribution of this work is the discovery that this algorithm, rooted in historical practice, unveils a fundamental dual cyclic group structure underlying the convergents. Specifically, for a convergent \(p/q\), the exponents associated with the algorithm's sorted intermediate terms generate the cyclic groups \(\mathbb{Z}/p\mathbb{Z}\) and \(\mathbb{Z}/q\mathbb{Z}\) via modular inverses (\(p^{-1} \mod q\) and \(q^{-1} \mod p\), respectively). Optimized for musical analysis, the MLA thus not only provides a practical tool but also bridges ancient tuning methodologies with contemporary algebraic structures, offering novel perspectives on both.

Introduction

The computation of logarithms via continued fractions is a well-established mathematical technique. However, an analogous process is evident in musical tuning theory, wherein scales are generated through the iterative stacking and reduction of intervals within a defined period (e.g., the octave). This paper introduces the Mesopotamian Logarithm Algorithm (MLA), a methodology grounded in the traditional "chaining and reduction" technique prevalent in Pythagorean, Chinese (sanfen-sunyi), and Mesopotamian music theory. While exhibiting superficial similarities to established continued fraction algorithms, such as Shanks' logarithm algorithm, this approach adopts a distinctly musical framework. Rather than computing intermediate terms of the continued fraction, MLA operates on musical intervals, directly identifying convergents of the logarithm, thereby circumventing its explicit calculation. Specifically, MLA generates convergents by identifying musical commas(1), which are small rational intervals signifying near-cyclical alignment.

(1): In Western music theory, commas denote relative intervals (e.g., \(4/3\) from \(3/2\) to \(2/1\)); here, the algorithm targets the comma indicating near alignment of the base and argument sequences.

Although the algorithm may not demonstrate superior computational efficiency across all scenarios, it incorporates a range of optimizations within its design.

Beyond its musical and computational utility, MLA reveals inherent group structures within the exponent sequences, establishing a connection between historical musical intuition and modern algebraic concepts. This paper focuses on the algorithm's design, its mathematical implications, and its relevance to music theory.

Algorithm Description

The Mesopotamian Logarithm Algorithm (MLA) identifies convergents of \(\log_b(a)\) for \(b > 1\), \(a > 0\), by iteratively generating a sequence of reduced terms \(r_x\) without directly computing logarithms. For each step \(x = 0, 1, 2, \ldots\):
  • Chain and Fold: Compute \(r_x = a^x \cdot b^{y_x}\), where \(y_x\) is an integer chosen such that \(r_x \in [1, b)\). This adjusts \(a^x\) by multiplying or dividing by powers of \(b\), and the total number of adjustments across all steps is tracked as \(p = \sum |y_x|\).
  • Bounds and Commas: Maintain dynamic bounds \(L\) (initially 1) and \(U\) (initially \(b\)). After computing \(r_x\), if \(L < r_x < U\), calculate the commas \(c_0 = r_x / L\) and \(c_1 = U / r_x\). Evaluate the ratio: \[  \text{Ratio} = \frac{\max(c_0, c_1) - 1}{\min(c_0, c_1) - 1}   \] If this ratio is less than 2, a convergent \(p/q\) is identified, where \(q = x + 1\).
  • Update Bounds}: If the ratio condition is satisfied, update the bounds: set \(L = r_x\) if \(r_x < H\), or \(U = r_x\) if \(r_x > H\), where \(H = b / r_1\) is the initial comma established after the first step.
Optimization: MLA avoids storing the full sequence of \(r_x\) values by dynamically updating \(L\) and \(U\), and it chains computations from the reduced \(r_x\) to prevent the need for large exponents, preserving numerical precision.

Theoretical Basic: Connection to The Three Gap Theorem

The heuristic threshold of 2 for this ratio finds its justification in the principles of the Three-Gap Theorem (Steinhaus Theorem) concerning the distribution of points \(n\alpha \mod 1\). The theorem dictates that the gaps between consecutive sorted points \((k\alpha) \mod 1\) for \(k = 1, \ldots, N\) take on at most three distinct lengths, and the specific structure of these gaps changes predictably as \(N\) increases, particularly as it passes values corresponding to the denominators \(q\) of the continued fraction convergents \(p/q\) of \(\alpha\).

The MLA operates analogously in a multiplicative setting, examining the sequence \(r_x = a^x b^{y_x}\) within \([1, b)\), akin to \((x \times log_b(a)) \mod 1\). While a full analysis would track all gaps between all sorted \(r_x\) terms generated so far, the MLA employs dynamic bounds \(L\) and \(U\) for efficiency. These bounds track the immediate multiplicative neighbors of the potential next term's location, effectively focusing on the local region where the most significant gap subdivision is anticipated when approaching a new convergent.

The insertion of a term \(r_x\) corresponding to a new convergent p/q is precisely the moment that triggers a structural reorganization of the gaps, often involving the subdivision of the largest existing gap type. The ratio condition \((max(c_0, c_1) - 1) / (min(c_0, c_1) - 1) < 2\), applied locally to the interval \([L, U]\) split by \(r_x\), acts as an efficient proxy for detecting this event. It identifies when the subdivision of this critical local region becomes relatively balanced (neither new multiplicative gap \(c_0\) or \(c_1\) is disproportionately larger than the other). This balanced local subdivision is an indicator that the global gap structure is undergoing the characteristic reorganization associated with reaching a best rational approximation \(p/q\), signalling that a convergent has been found.

Therefore, the MLA leverages the underlying principles of uniform distribution and gap structure described by the Three-Gap Theorem, but uses a localized, efficient test. It identifies convergents by detecting the balanced subdivision event characteristic of their appearance, operating directly on the multiplicative sequence \(a^x b^{y_x}\) without needing explicit logarithms or tracking all intermediate gaps. This unique approach simultaneously facilitates the discovery of the dual cyclic group structures within the exponents (\(p\) and \(q\)) associated with these identified convergents.

Dual Group Structures

The MLA’s sequence of reduced terms \(r_x\) for each \(p/q\) unveils cyclic group structures in the exponents:
  • \(x\)-Sequence: When \(r_x\) values are sorted by magnitude, their corresponding exponents \(x_k\) form the cyclic group \(\mathbb{Z}/q\mathbb{Z}\), generated by \(p^{-1} \mod q\). For the convergent \(19/12\) of \(\log_2(3)\), \(q = 12\), \(p = 19\), \(p^{-1} = 7 \mod 12\), yielding the sequence \(0, 7, 2, 9, 4, 11, 6, 1, 8, 3, 10, 5\).  
  • \(y\)-Sequence: The exponents \(y_{x_k}\) (adjustments by powers of \(b\)), taken modulo \(p\), form the first \(q\) elements of \(\mathbb{Z}/p\mathbb{Z}\), generated by \(q^{-1} \mod p\). For \(19/12\), \(q^{-1} = 8 \mod 19\), producing \(0, -11, -3, -14, -6, -17, -9, -1, -12, -4, -15, -7\).  
This duality emerges from the approximation \(a^q \approx b^p\), linking the algorithm’s musical origins to modular arithmetic.

\( \approx r_x \) Ratio \( x \) \( y_x \)
1.000 1 0 0
1.068 2048:2187 7 -11
1.125 8:9 2 -3
1.201 16384:19683 9 -14
1.266 64:81 4 -6
1.352 131072:177147 11 -17
1.424 512:729 6 -9
1.500 2:3 1 -1
1.602 4096:6561 8 -12
1.688 16:27 3 -4
1.802 32768:59049 10 -15
1.898 128:243 5 -7
Reduced chain for \(\log_2(3)\), \(r_x = 3^x \cdot 2^{y_x}\), \(q=12\)


Visualizations and Applet

The following figures, generated by an extended MLA implementation, replicate the interval and scale generation logic of Mesopotamian tablet CBS1766, exposing group-theoretic properties through geometric dials. This emulation draws the same figure for any \(log_b(a\times b^k)\) highlighting the algorithm’s focus on periodic, fractional components rather than the integer part.

Figure 1: Visualizes the convergent \(7/12\) for \(\log_2(3/2)\). A 12-sided regular polygon represents \(\mathbb{Z}/12\mathbb{Z}\), with vertices labeled 1 to 12 counterclockwise. Inside, an irregular 7-pointed star (heptagram) connects the first 7 elements generated by 7 modulo 12, tracing the outer sequence \(\{12, 7, 2, 9, 4, 11, 6\}\). These correspond to exponents \(x\) in the first 7 of 12 terms of \((3/2)^x \cdot 2^y\) folded into \([1, 2]\). The inner star is labeled \(\{7, 4, 1, 5, 2, 6, 3\}\), representing exponents \(y\) in \(\mathbb{Z}/7\mathbb{Z}\) with generator 4. The final connection from 6 to 12 (outer) is dashed, indicating an incomplete cycle of the group.

7-pointed star within a 12-sided polygon for \(7/12\) of \(\log_2(3/2)\).



Figure 2: Shows the convergent 6/23 for \(\log_3(4/3)\). A 23-sided regular polygon represents \(\mathbb{Z}/23\mathbb{Z}\), labeled 1 to 23 counterclockwise. Inside, a 6-sided irregular polygon connects the points \(\{23, 4, 8, 12, 16, 20\}\), the first 6 exponents generated by 4 modulo 23, corresponding to sorted terms \(r_x = (4/3)^x \cdot 3^{y_x}\) in \([1, 3)\). This contrasts with Figure 1's overlapping heptagram, as the lines here do not intersect, highlighting the algorithm's flexibility across different bases and periods.

6-sided polygon within a 23-sided polygon for \(6/23\) of \(\log_3(4/3)\).


Music Theory Insights

In musical contexts, the denominators of logarithmic convergents represent equal divisions of a base interval \(b\), approximating intervals generated by powers of \(a\) within \([1, b)\). However, not all convergents are equally effective for this purpose. For example, while \(\frac{65}{41}\) follows \(\frac{19}{12}\) as a convergent of \(\log_2(3)\), a 41-fold equal division of the octave (\(2^{1/41}\)) poorly approximates the sequence of 41 reduced fifths (\(3^x \cdot 2^{y_x}\)). In contrast, the subsequent convergent \(\frac{84}{53}\) yields a more accurate alignment. A variant of MLA replaces the ratio threshold of 2 with the golden ratio (\(\phi \approx 1.618\)) to select convergents with uniformly distributed commas, enhancing their utility for microtonal approximations.

Figure 3: visualizes interval alignment for three convergents of \(\log_2(3)\), with rows A, B, and C:
  • A: 12-EDO: The interval \([1, 2]\) with the first 12 terms of \(3^x \cdot 2^{y_x} \in [1, 2]\) (blue) aligns closely with 12 equal divisions (red, step size \(2^{1/12}\)), reflecting the phase coherence of \(\frac{19}{12}\) in standard equal temperament.
  • B: 41-EDO: The first 41 terms (blue) diverge significantly from 41 equal divisions (red, step size \(2^{1/41}\)), indicating the poor approximation of \(\frac{65}{41}\) due to non-uniform comma distribution.
  • C: 53-EDO: The first 53 terms (blue) align well with 53 equal divisions (red, step size \(2^{1/53}\)), demonstrating the efficacy of \(\frac{84}{53}\).    
The geometric contrast underscores that \(\frac{19}{12}\) and \(\frac{84}{53}\) outperform \(\frac{65}{41}\), with the latter exhibiting greater error and reduced suitability for musical tuning due to its irregular comma distribution.

Geometric Representation of Interval Alignment


Conclusion and Future Directions

This paper introduced the Mesopotamian Logarithm Algorithm (MLA), a different method for computing logarithmic convergents rooted in the "chaining and reduction" principles observed in ancient musical scale construction across various cultures. By operating directly on interval relationships and identifying musical commas, the MLA bypasses explicit logarithm evaluation, offering a computationally distinct approach compared to conventional continued fraction algorithms like Shanks'. Its optimization for musical applications, focusing on the sequence of reduced terms within a base interval (e.g., the octave), reflects historical tuning practices.

Beyond its practical utility in generating musically relevant approximations, the most interesting contribution of this work lies in unveiling the inherent algebraic structure encoded within the algorithm's process. For a given logarithmic convergent \(p/q\) of \(log_b(a)\), the MLA implicitly reveals a dual cyclic group structure within the exponents. Specifically, when the intermediate terms \(r_x = a^x b^{y_x}\) (reduced to the interval \([1, b)\)) are sorted by magnitude, their corresponding a-exponents \((x)\) generate the cyclic group \(\mathbb{Z}/q\mathbb{Z}\) via \(p^{-1} \mod q\), while the associated b-exponents \((y_x)\) map to the initial elements of \(\mathbb{Z}/p\mathbb{Z}\) with generator \(q^{-1} \mod p\). This discovery establishes a formal bridge between the iterative, intuitive procedures of historical tuning systems and the abstract framework of modern group theory.

The implications of this connection are potentially far-reaching. For music theory, it provides a new algebraic lens through which to analyze scale generation and comma distribution, and the underlying mathematical coherence of tuning systems. For mathematics, it offers a concrete algorithmic context for observing these dual group structures related to Diophantine approximation of logarithms.

Future research stemming from this work presents several compelling avenues:

Generalization to Other Irrationals: A primary direction is to investigate whether this dual cyclic group structure is a more general phenomenon associated with continued fraction convergents \(p/q\) of other irrational numbers. Exploring analogues for sequences derived from approximations of constants like \(\theta/(2\pi)\) (related to trigonometric functions and rotations on the circle group \(S^1\)) or other fundamental irrationals could reveal similar underlying algebraic patterns. This involves defining appropriate "reduction" processes and analyzing the resulting index and 'overflow' sequences.

Analysis of Historical Systems: The group-theoretic framework developed here could be applied to analyze other historical mathematical and musical systems. Examining algorithms like Ptolemy's geometric tuning methods or other ancient approximation techniques through this lens might uncover similar, or perhaps distinct, algebraic structures, deepening our understanding of their mathematical foundations.

Algorithmic Refinements and Applications: Further exploration of MLA variants, such as incorporating different comma selection criteria (e.g., the golden ratio threshold) for optimizing comma distribution in microtonal contexts, warrants investigation. Connections to uniform distribution theory and dynamical systems may also yield further insights.

In summary, the MLA serves not only as an efficient algorithm tailored for musical contexts but also as a potent example of how practical, historically-inspired procedures can illuminate fundamental mathematical structures. It underscores the deep, often hidden, connections between music, mathematics, and the history of computation, opening fertile ground for future interdisciplinary exploration.

A  Python Implementation
This implementation ignores integer convergents and provide musical meaningful approximations.

def mla(a, b, max_q):
    if b <= 1 or a <= 0:
        return []
    if a == 1:
        return ["0/1"]  # log_b(1) = 0
    if a == b:
        return ["1/1"]  # log_b(b) = 1
    if a < 1: #handles a in (0,1)
        a = 1 / a
        results = mla(a, b, max_q)
        return [f"-{p.split('/')[0]}/{p.split('/')[1]}" if '/' in p else f"-{p}" for p in results]
    results = []
    link, lower, upper = a, 1, b
    p, q = 1, 1
    while q < max_q:
        while link < 1:
            link *= b; p += 1
        while link > b:
            link /= b; p += 1
        if q == 1:
            H = b / link; p += p - 1
        q += 1
        if link == b:
            results.append(f"{p-1}/1"); break
        if lower < link < upper:
            commas = [link/lower, upper/link]
            if (max(commas) - 1) / (min(commas) - 1) <= 2:
                results.append(f"{p}/{q}")
            lower, upper = (link, upper) if link < H else (lower, link)
        link *= a
    return results


-------

old article:

A Musical Approach to Convergents of Continued Fractions

This article explores a method for calculating logarithms deeply rooted in musical principles first documented in ancient Mesopotamian cuneiform tablets. While superficially similar to existing methods involving continued fractions, such as Shanks' logarithm algorithm, this approach takes a fundamentally musical perspective. Instead of directly computing intermediate terms of the continued fraction, it operates on musical intervals, directly identifying convergents of the logarithm, bypassing its computation, that is, the algorithm directly generate convergents without calculating the logarithm first. This connection between music and logarithms emerges from the traditional musical concept of the "comma." Although this algorithm might not surpass existing methods in efficiency across all cases, it incorporates various optimizations within its design. What makes this algorithm particularly intriguing is the surprisingly early demonstration of modern mathematical concepts in the context of ancient Mesopotamian music theory.


Musical Theory Background

Music theory is a diverse field with various schools of thought, ranging from traditional to experimental approaches. This diversity mirrors the essence of music itself, which defies a singular, absolute definition. At its core, music is deeply connected with human expression, art, and culture. Despite philosophical differences, certain processes in music, particularly in tuning theory, are universally grounded in mathematical concepts.

A commonly used technique for constructing tuning systems, known as "chaining/stacking and reducing/folding," forms the basis of the algorithm discussed in this article. This approach has been utilized by various cultures throughout history, notably in the Pythagorean scale. Documented by Boethius, Ptolemy, and others, this scale was later expanded upon by the medieval music theorist Guido d'Arezzo. Remarkably, this identical pitch calculation and scale generation process is also found in Chinese music theory under the name sanfen-sunyi, or up-down generation in English. And an even earlier application of this method is apparent in Mesopotamian music, highlighting the universality of interval reduction and equivalence concepts.

While these three distinct cultures developed and recorded this system, they likely influenced one another through historical interactions like Greek visits to Egypt or Magi priests traveling to China. Similar scales have been discovered in other geographically distant cultures. Although the process wasn't explicitly documented, pre-Columbian American and West African instruments feature diatonic or pentatonic scales.

The Mesopotamian Musical Tuning System

This ancient civilization not only calculated the same 3-limit 12-tone system, the diatonic scale, and its modes, but their methods and visualizations align with modern mathematical concepts from group theory and modular arithmetic, incorporating intervals and class matrices. A comprehensive analysis of cuneiform tablets, their translations, and their relation to cosmology extends far beyond the scope of this text. For a detailed study, refer to this excellent paper on the topic. Here i provide a concise overview pertinent to the algorithm.

The tablet features a dial and a table, both of which have modern counterparts in music theory. The table corresponds to what we now call a "class matrix," used for analyzing chords, scales, modes, and tuning patterns on instruments. This is the same purpose it serves on the tablet. It differs from the "interval matrix," which doesn't indicate exact pitches but rather their classes after construction. The dial serves as another method for displaying interval relationships, similar to the circle of fifths.  Many modern virtual synthesizers utilize a similar user interface for displaying microtonal scales.

While the tablet doesn't explicitly mention octaves (1:2) or fifths (2:3), the dial displays the names of the strings on a lyre. A corresponding tablet provides step-by-step instructions for tuning this lyre to achieve all the diatonic scale modes found in the table. This suggests a clear understanding of string length ratios and harmonics, a concept further supported by the earliest lutes, which also featured movable frets.

There is, however, no consensus on the regularity of the heptagon star depicted on the tablet. If the points were equidistant, the tuning instructions would be incorrect and unnecessary, as the scales would be congruent. In my opinion, the heptagon star is irregular, and the double circle within which it is inscribed likely represents an octave – a common practice in dial user interfaces to indicate the period.

It's crucial to recognize that we are considering three heptagon stars. One is regular, and rotating it leads to an identical star, which would correspond to 7-EDO (7 equal divisions of the octave) if octaves were our focus. The other two are irregular, with minimal differences, barely perceptible in a perfect graphic, which emerge from the comma. We are comparing the 3-limit 12-tone system and the 12-tone temperament. Studying these congruences involves the use of interval matrices, which lies outside the initial goal of this text.  We will revisit this topic after explaining the "chain" and "reduce" operations.

The tablet shows three possible star shapes. The first, a regular heptagon, corresponds to 7edo. Tuning instructions suggest adjusting two strings to achieve different modes, which in 7edo results in arriving at notes already present, effectively removing notes rather than changing step sizes. These instructions don’t apply to this star, which involves locating the tritone, transforming it to a fifth, and relocating the tritone on another string, keeping five strings in tune with a different base to achieve a new diatonic mode.
The second star, irregular, is constructed by connecting seven points on a 12-sided polygon by fifths, returning to the origin in the last step. This generates the first seven elements in Z/12Z+ with generator 7. The instructions apply to this star and the group perspective. Starting with a set generated by 7: {7, 2, 9, 4, 11, 6, 1}, shifting all elements by -2 results in five numbers remaining the same: {5, 0, 7, 2, 9, 4, 11}.
The third star, another irregular shape, is generated in the circle group with generator log2(3). The group is infinite, and seven steps are drawn, with the last step highlighting the Pythagorean comma misalignment. There is no direct evidence that Mesopotamians knew this exact value; their theory was more practical than technical. The second star is the most likely representation.
While these historical materials might predate the formalization of group theory in modern math, CBS1766 reveals how a similar understanding of musical principles, utilizing cyclical patterns, generators, and group shifts, might have already existed in Mesopotamian musical practices.


Interval/Ratio Reduction

Considering the inverse relationship between string length and frequency, the process remains similar regardless of the starting point, with arithmetic operations adjusted accordingly. I will utilize the frequency interpretation and Western music terminology (octave, fifth, third, scale, tuning, comma, etc.)

While the generalization of this scaling operation is not limited to specific values and can even extend to complex numbers, musical intervals are real numbers, often rational. For pitch calculations, we categorize them into subharmonics \((0,1)\), fundamental \([1]\), and harmonics \((1, +∞)\). The concept of interval reduction stems from human perception and the notion of octave equivalence, which aligns with the modern concept of chroma, recognizing pitches in a 1:2 ratio as possessing the same "color."

For example, we identify the fifth (2:3) as a representative of the third harmonic (1:3) but reduced to the octave (1:2). Similarly, a major third (4:5) is the octave representative of the fifth harmonic (1:5).  Reduction separates intervals, or numbers, into classes. The fifth (2:3) not only represents the third harmonic (1:3) in octave space, but it also represents the sixth (1:6), twelfth (1:12), twenty-fourth (1:24), etc.

This universal operation in music can be represented using various notations. In modern music theory, this may be notated with the mod operator, as it returns a remainder – in this case, a ratio or intervallic remainder.

The classic mod operator can be defined as:

\(a \bmod b = \tilde{a}\),
Subtract \(b\) from \(a\) until \(a < b\). For example: \(14 \bmod 5 = 4\).

The normalized ratio mod operator can be defined as:

\(a \bmod 1:b = \tilde{a}\),
Multiply or divide \(a\) by \(b\) until \(a\) falls within the range \((1, b]\).  For example: \(48 \bmod 1:2 = 1.5\).

This bears a strong resemblance to the first part of Shanks' algorithm (although there is no evidence of his interest in music theory).  He describes this aspect of the process for integers \(b > a > 1\) as finding \(a^n < b < a^{n+1}\), essentially the same reduction or scaling process: \(2^5 < 48 < 2^6\), so  \( 48/2^5 = 1.5\)

Generalizing reduction, it can be seen as a mapping, transforming a number into another range. While you can perform this operation with other ranges, normalization is required.  For example, \(7 \bmod 4:5\) is calculated as \(7 \bmod 1:5/4 = 1.12\).

The Chain/Stack

The chaining operation mathematically corresponds to an exponential sequence.  A chain of third harmonics, expressed in terms of frequency ratios, is represented by \(\{3^0, 3^1, 3^2, 3^3, 3^4, \ldots\}\).  These numbers, as musical intervals, form a 1:3 ratio, representing consecutive third harmonics: \(\{1, 3, 9, 27, 81, \ldots\}\).

The 12-tone Pythagorean/Chinese/Mesopotamian scale, constructed in this manner, is known in modern theory as the 3-limit 12-tone system. It chains 12 fifths (or third harmonics) and reduces them by the octave. Its tempered/truncated modern version is the 12-EDO (12 equal divisions of the octave) or 12-tone equal temperament, created to compensate for the emergence of commas – a crucial component of the algorithm in both Shanks' and Mesopotamian methods.

Commas

Traditionally, the term "comma" refers to a small and "problematic" interval, a famous example is known as the "Pythagorean comma." This arises when constructing a scale using the octave (1:2) and the third harmonic (1:3).  After stacking and reducing 12 notes, the next calculated note almost returns to the starting point \(3^{12} \bmod 1:2 = 3^{12}/2^{19} = 531441/524288\), making the set of pitches nearly cyclical. This happens because no integers \(n\) and \(m\) exist such that \(2^n = 3^m\), as both 2 and 3 are prime numbers.

However, the concept of a comma has been expanded to define relative ratios within a set, not necessarily small. For example, in the set {1, 2, 3, 4, 5}, the consecutive commas are {1:2, 2:3, 3:4, 4:5}, representing the ratio between consecutive intervals but it can refer to any pair of intervals in the set. This includes consecutive intervals, but also, for instance, the comma 3:5, 2:4, 2:5, etc... within that set.

For this algorithm, we are focusing on detecting the traditional comma, indicating an almost-perfect alignment of the exponential sequences of the base and the argument. This alignment signifies the discovery of a convergent.

The Algorithm: Example and Convergents

Before explaining how convergents are obtained, some implications are examined. Although the examples might focus on \(\log_2(3)\), this is done for clarity and for those already familiar with the method. The 3-limit 12-tone scale will make it easier to follow, and then the general case is presented.

Let's examine \(\log_2(3)\) using the convergent \(\frac{19}{12}\), the octave (1:2), the third harmonic (1:3), and the chromatic scale.

Consider the denominator of the convergent as the order of an additive group \(\mathbb{Z/12Z}\) and the numerator as a generator (19%12 = 7) , the sequence of elements matches the exponents in the size-ordered reduced links in the chain of \(3^x\). Specifically, if you calculate the first 12 powers of \(3\), reduce them by \(1:2\), and order them by size as \((3^x \times 2^y)\), the sequence of \(x\)'s corresponds to the elements in \(\mathbb{Z/12Z}\) generated by \(7\). Similarly, the sequence of \(y\)'s corresponds to the first 12 elements in \(\mathbb{Z/19Z}\) generated by in this case \(8\). (See below)

                                                    log2(3)                                     log2(3/2)
~Decimal  Ratio           3 ^ x   *   2 ^ y    |  (3/2) ^ x   *   2 ^ (y%x)
1
1.014     524288:531441   3 ^ 12  *   2 ^ -19  |  (3/2) ^ 12  *   2 ^ -7    Comma
1.068     2048:2187       3 ^ 7   *   2 ^ -11  |  (3/2) ^ 7   *   2 ^ -4    
1.125     8:9             3 ^ 2   *   2 ^ -3   |  (3/2) ^ 2   *   2 ^ -1    
1.201     16384:19683     3 ^ 9   *   2 ^ -14  |  (3/2) ^ 9   *   2 ^ -5    ♂︎
1.266     64:81           3 ^ 4   *   2 ^ -6   |  (3/2) ^ 4   *   2 ^ -2    
1.352     131072:177147   3 ^ 11  *   2 ^ -17  |  (3/2) ^ 11  *   2 ^ -6    
1.424     512:729         3 ^ 6   *   2 ^ -9   |  (3/2) ^ 6   *   2 ^ -3    ♀︎
1.5       2:3             3 ^ 1   *   2 ^ -1   |  (3/2) ^ 1   *   2 ^  0    
1.602     4096:6561       3 ^ 8   *   2 ^ -12  |  (3/2) ^ 8   *   2 ^ -4
1.688     16:27           3 ^ 3   *   2 ^ -4   |  (3/2) ^ 3   *   2 ^ -1
1.802     32768:59049     3 ^ 10  *   2 ^ -15  |  (3/2) ^ 10  *   2 ^ -5
1.898     128:243         3 ^ 5   *   2 ^ -7   |  (3/2) ^ 5   *   2 ^ -2
2                         

\(\mathbb{Z/12Z}\) = 7,  2,  9, 4, 11, 6, 1,  8, 3, 10, 5, 0
\(\mathbb{Z/19Z}\) = -11, -3, -14, -6, -17, -9, -1, -12, -4, -15, -7, ...


Understanding the Setup

For \(\log_2(3)\), the convergent \(19/12\) gives us \(p = 19\) and \(q = 12\), where \(p\) and \(q\) are coprime. This convergent approximates \(\log_2(3) \approx 1.58496\), so \(3^{12} \approx 2^{19}\). We compute the first \(q\) powers of \(a\):
  • \(r_x = 3^x \cdot 2^{y_x}\), for \(x = 0, 1, \ldots, q-1 = 11\),
where \(y_x\) is chosen to “reduce” the value into the interval \([1, b) = [1, 2)\). Specifically:
  • \(y_x = -\lfloor x \log_2(3) \rfloor\),
ensuring \(r_x = 3^x \cdot 2^{y_x} \in [1, 2)\). We then sort these \(r_x\) values in increasing order, which permutes the indices \(x\) and their corresponding \(y_x\).

General Rule

For a convergent \(p/q\) of \(\log_b(a)\):
  • \(x\) sequence: Sorting \(r_x\) orders the fractional parts \(\{x \cdot \log_b(a)\} \approx \{x \cdot (p/q)\}\), giving \(x_k = k \cdot p^{-1} \mod q\), forming \(\mathbb{Z}/q\mathbb{Z}\) with generator \(p^{-1}\).
  • \(y\) sequence: The corresponding \(y_{x_k} = -\lfloor (k \cdot p^{-1} \mod q) \cdot \log_b(a) \rfloor\), when taken modulo \(p\), forms the first \(q\) elements of \(\mathbb{Z}/p\mathbb{Z}\) with generator \(q^{-1} \mod p\). This arises because \(y_x \approx -x \cdot (p/q)\), and the permutation by \(p^{-1}\) interacts with the approximation.

For \(19/12\):
  • \(q = 12\), \(p = 19\), \(p \equiv 7 \mod 12\), \(p^{-1} = 7\), \(x\): \(k \cdot 7 \mod 12\),
  • \(p = 19\), \(q = 12\), \(q^{-1} = 8 \mod 19\), \(y \mod 19\): \(k \cdot 8 \mod 19\).

In conclusion both sequences are group-related:
  • The \(x\) exponents form \(\mathbb{Z}/q\mathbb{Z}\) generated by \(p^{-1} \mod q\) (here, 7).
  • The \(y\) exponents, modulo \(p\), form the first \(q\) elements of \(\mathbb{Z}/p\mathbb{Z}\) generated by \(q^{-1} \mod p\) (here, 8).
The generator for the \(y\) sequence emerges from the inverse relationship due to \(a^q \approx b^p\), reflecting a duality in the convergent’s structure. For \(19/12\), it’s 8 because \(12^{-1} \equiv 8 \mod 19\).


This live demo calculates a few example convergents and renders a simple one, illustrating the tablet logic.


Obtaining Convergents

The implementation (detailed below) includes optimizations that may make its logic less clear. Here’s a simplified explanation:

It iteratively computes a chain of powers (exponential sequence) from the input value (the argument), and each "link" is reduced to fall within the interval range \((1, \text{base}]\). The distances between consecutive reduced links, the commas, are then passed to a condition: if the ratio of the normalized largest/smallest commas is less than \(2\), a convergent is found. The current step of the iteration provides the denominator, while the numerator is obtained by counting how many times the links were multiplied or divided until they fell within the range.

One optimization involves readjusting the upper and lower bounds of the links being evaluated, reducing the need to keep and test every comma except two. When commas pass, the previous reduced link approximates the comma between the first reduced link and the base. For clarity:

As an example take \(\log_2(10)\),

the first reduced link is \( 10^1/2^3 \), the comma ( \(H\) in the code) is \(\frac{2}{1} / \frac{10}{8} = \frac{8}{5} = 1.6 \)

As each convergent for \(\log_2(10) ≈ \frac{10}{3} ≈ \frac{93}{28} ≈ \frac{196}{59}\ldots\) indicates that,

\(10^{3}/2^{10} ≈ 10^{28}/2^{93} ≈ 10^{59}/2^{196} ≈ 1\) (progressively better)

The previous link added, indicates

\( 10^{2}/2^{6} ≈ 10^{27}/2^{89} ≈ 10^{58}/2^{192} ≈ 1.6 \),

And the next link, for example \( 10^{29} \bmod 1:2 = 10^{29} / 2^{96} ≈ \frac{10}{8} = 1.25\), approximates the first link again.

Knowing this the evaluated link becomes a new bound, lower or upper depending on which side of this value \(H\) fell.

Another optimization addresses precision, for example, to compute \(\log_2(5)\) as \(4495889/1936274\) using the simple logic explained above, you would need to calculate \(5^{1936274}\), which exceeds 32-bit integer limits. The solution is to continue the chain from its reduced link, preserving the order of commas and avoiding such exponents. This allows precision to be maintained longer.

Variations for Precision and Musical Applications

While the denominators in a convergent of \(\log_b(a)\) in music are used as an equal division of \(b\) approximating intervals generated by \(a\) in \(b\), not all work for this purpose. For example, the next convergent of \(\log_2(3)\) after \(\frac{19}{12}\) is \(\frac{65}{41}\), but 41 equal divisions of the octave don't approximate 41 consecutive reduced fifths. The subsequent convergent, \(\frac{84}{53}\), does function as needed. A variation of the algorithm uses the golden ratio (Φ) instead of 2 in the condition, selecting convergents that correspond only to uniformly distributed commas. Another way to visualize it is that a chain of \(2^{1/53}\) keeps a close approximation, in phase, with the powers of \(3\) up to \(3^{53}\) and powers of \(2\) up to \(2^{84}\).

41 fifths don't fill the octave:


as 12 fifths:


or 53 fifths:


Essentially, this variation ignores convergents with poor approximations, implicitly constructs additive groups, and identifies their generators.


Python Implementation




(Another slight optimization, which is not implemented, avoids the use of the min and max functions in every iteration when the condition is met. The indices of the minimum and maximum values, once found, remain the same. Therefore, these indices can be calculated in the first step and then reused. However, since the functions are performed on an array of two elements, saving any sort-like function has minimal impact on speed; it just interrupts the flow of the code.)
(DRAFT)

Diophantine Limits of Quantum Probability Amplification

Grover’s algorithm is usually described geometrically as a repeated rotation. Here we reinterpret those rotations as a Diophantine approxima...