Complete asymptotic type-token relationship for growing complex systems with inverse power-law count rankings

1. Problem Statement

Complex systems, ranging from linguistic corpora and animal communication to ecological networks and socioeconomic data, often exhibit Zipf's Law: an inverse power-law relationship between the frequency (count) of a type ($S$) and its rank ($r$), expressed as $S \sim r^{-\alpha}$.

A related empirical observation is Heaps' Law, which describes how the number of distinct types ($N$) grows sublinearly with the total number of tokens ($t$) in a system, typically as $N \sim t^\beta$ where $0 < \beta < 1$.

The Core Question: Is there a fundamental, deterministic mathematical relationship between Zipf's Law (rank-frequency) and Heaps' Law (type-token growth) in finite, growing systems?
The Gap: Previous work, notably by L¨u et al. (2010), attempted to derive this relationship but relied on integral approximations that failed in specific regimes (specifically $\alpha = 1$ and $\alpha \gg 1$). The existing models often assumed stochastic growth mechanisms or sampling processes, obscuring whether the relationship is an emergent property of the power-law distribution itself.

2. Methodology

The authors propose an idealized, deterministic growing system model to derive the exact asymptotic relationship without relying on stochastic sampling or specific physical mechanisms.

• Model Definition:
  • The system grows in discrete time steps $t = 1, 2, 3, \dots$.
  • The count of the $r$-th type at time $t$ is defined as $S_{r,t,\alpha} = \lfloor \frac{1}{2} + G_{t,\alpha} r^{-\alpha} \rfloor$, where $G_{t,\alpha}$ is a growth factor ensuring the total token count equals $t$.
  • Types are ordered by arrival time; a type is "created" when its count rounds up to 1.
• Analytical Approach:
  • To avoid the computational difficulty of the floor operator, the authors approximate the count ranking as a continuous function: $S_{r,t,\alpha} \approx S_{1,t,\alpha} r^{-\alpha}$ for $1 \le r \le N_{t,\alpha}$.
  • They enforce two boundary conditions:
    1. The most recently arrived type (rank $N_{t,\alpha}$) has a count of 1.
    2. The sum of all fractional counts equals the total time $t$.
  • This leads to the equation: $t \approx N_{t,\alpha}^\alpha H_{N_{t,\alpha}}^{(\alpha)}$, where $H_n^{(\alpha)}$ is the generalized harmonic number.
• Key Mathematical Tool:
  • Instead of using the standard integral approximation for the harmonic sum (which causes errors), the authors employ the Euler-Maclaurin expansion to approximate $H_{N_{t,\alpha}}^{(\alpha)}$ with high precision.
  • This allows them to derive a unified asymptotic expression valid for all $\alpha \ge 0$.

3. Key Contributions

1. Unified Asymptotic Expression: The authors derive a single, exact asymptotic formula (Eq. 13) relating total tokens $t$ and distinct types $N_{t,\alpha}$ that is valid for all values of the scaling exponent $\alpha$.
   $$t \sim \frac{1}{1-\alpha}N_{t,\alpha} + \zeta(\alpha)N_{t,\alpha}^\alpha$$
   (Where $\zeta(\alpha)$ is the Riemann zeta function).
2. Correction of Previous Work: They identify and correct the errors in the L¨u et al. (2010) derivation. Specifically, the integral approximation used previously fails for $\alpha > 1$ (underestimating system size by a factor of $\alpha-1$) and is inaccurate for $\alpha \approx 1$.
3. Deterministic Origin of Heaps' Law: The study demonstrates that Heaps' Law is not an independent phenomenon or a result of stochastic growth mechanisms. Instead, it emerges solely as a consequence of the system adhering to an inverse power-law count ranking (Zipf's Law).
4. Regime-Specific Solutions: The paper provides explicit limiting forms for three critical regimes:
   • $\alpha \ll 1$: Linear growth ($N \sim t$).
   • $\alpha = 1$: Logarithmic correction ($N \sim t / \ln t$).
   • $\alpha \gg 1$: Power-law growth ($N \sim t^{1/\alpha}$).

4. Results

The derived relationship (Eq. 13) and its limiting forms (Eq. 20 and 21) were validated against the discrete harmonic sum model:

• For $\alpha \ll 1$: The system behaves linearly, $t \sim \frac{1}{1-\alpha}N_{t,\alpha}$. As $\alpha \to 0$, $N \approx t$.
• For $\alpha = 1$: The relationship involves the Euler-Mascheroni constant ($\gamma_0 \approx 0.577$). The number of types scales as $N_{t,1} \sim \frac{t}{\ln t + \gamma_0 - \ln(\ln t + \gamma_0)}$. This corrects the divergence found in simpler approximations.
• For $\alpha \gg 1$: The exponential term dominates. The relationship simplifies to $t \sim N_{t,\alpha}^\alpha$, or $N_{t,\alpha} \sim t^{1/\alpha}$.
  • Critical Finding: The previous integral approximation suggested $t \sim \frac{1}{\alpha-1}N^\alpha$, which is incorrect. The authors show that for steep power laws (e.g., $\alpha = 10, 15$), the integral method underestimates the required system size $t$ by nearly an order of magnitude.
• Visual Validation: Figure 1 and Figure 2 demonstrate that the new expansion (Eq. 13) fits the discrete data perfectly across all $\alpha$ values, whereas the older approximation (Eq. 10) deviates significantly in the $\alpha \ge 1$ regimes.

5. Significance

• Theoretical Unification: The paper establishes a rigorous, mechanism-independent link between Zipf's Law and Heaps' Law. It proves that if a system grows with a power-law rank distribution, a specific type-token scaling law must emerge.
• Correction of Literature: It resolves long-standing inaccuracies in the mathematical derivation of these scaling laws, particularly for systems with steep distributions (high $\alpha$), which are common in real-world data like music popularity, book sales, and wealth distribution.
• Methodological Advancement: By utilizing the Euler-Maclaurin expansion rather than simple integration, the authors provide a more robust mathematical framework for analyzing discrete, growing complex systems.
• Implications for Complex Systems: The findings suggest that the "sublinear" growth of vocabulary or species diversity (Heaps' Law) is a direct statistical consequence of the "heavy-tailed" nature of frequency distributions (Zipf's Law), rather than a result of specific biological or linguistic growth mechanisms. This simplifies the modeling of diverse complex systems, from linguistics to urban planning.