Number of values of diversity indices

DefinitionNumber of values of the Gini–Simpson index#✓fully proved

For a natural number \(N\), \(\gamma(N)\) is the number of distinct values of \(a_1^2 + \dots + a_k^2\) over all finite sequences \((a_1, \dots, a_k)\) of natural numbers with \(a_1 + \dots + a_k = N\).

For \(N \ge 1\), the Gini–Simpson index of a sample of size \(N\) with type counts \(a_1, \dots, a_k\) is \(1 - \sum_i (a_i / N)^2\), so \(\gamma(N)\) is the number of possible values of the Gini–Simpson index across all samples of size \(N\).

noncomputable def giniSimpsonCount (N : ℕ) : ℕ :=
  Set.ncard {s : ℕ | ∃ l : List ℕ, l.sum = N ∧
    (l.map (fun a => a ^ 2)).sum = s}

Used by 4

Used byAsymptotics of the number of Gini–Simpson values · Quadratic lower bound on the number of Gini–Simpson values · Triangular-number lower bound on the number of Gini–Simpson values · Upper bound on the number of Gini–Simpson values

DefinitionNumber of values of the Shannon index#✓fully proved

For a natural number \(N\), \(\sigma(N)\) is the number of distinct real numbers \(-\sum_{i=1}^{k} (a_i / N) \log (a_i / N)\) over all finite sequences \((a_1, \dots, a_k)\) of natural numbers with \(a_1 + \dots + a_k = N\), where a term with \(a_i = 0\) counts as \(0\) (the convention \(0 \log 0 = 0\)).

For \(N \ge 1\), this is the number of possible values of the Shannon index across all samples of size \(N\).

noncomputable def shannonCount (N : ℕ) : ℕ :=
  Set.ncard {v : ℝ | ∃ l : List ℕ, l.sum = N ∧
    v = -(l.map (fun a => ((a : ℝ) / N) * Real.log ((a : ℝ) / N))).sum}

Used by 2

Used byUpper bound on the number of Shannon values · The number of Shannon values grows faster than every polynomial

TheoremUpper bound on the number of Gini–Simpson values#●ready to prove

Let \(\gamma(N)\) be the number of distinct values of \(a_1^2 + \dots + a_k^2\) over all finite sequences \((a_1, \dots, a_k)\) of natural numbers with \(a_1 + \dots + a_k = N\) (for \(N \ge 1\), the number of possible values of the Gini–Simpson index across samples of size \(N\)). Then for every natural number \(N\),

\[\gamma(N) \le \tfrac{1}{2} N^2 - \tfrac{1}{2} N + 1.\]

theorem_wanted giniSimpsonCount_le (N : ℕ) :
    (giniSimpsonCount N : ℚ) ≤ (1 / 2) * N ^ 2 - (1 / 2) * N + 1

Sources

• Bradley K. Moon and Noah A. Rosenberg, "Integer Sequences for Diversity Statistics", Proposition 4.

Uses 1

Statement usesNumber of values of the Gini–Simpson index

TheoremTriangular-number lower bound on the number of Gini–Simpson values#●ready to prove

Let \(\gamma(N)\) be the number of distinct values of \(a_1^2 + \dots + a_k^2\) over all finite sequences \((a_1, \dots, a_k)\) of natural numbers with \(a_1 + \dots + a_k = N\) (for \(N \ge 1\), the number of possible values of the Gini–Simpson index across samples of size \(N\)). Let \(m\) and \(r\) be natural numbers with \(r \le m\), and let \(N = \binom{m+1}{2} + r\). Then

\[\tfrac{1}{3} m (m^2 + 3r - 1) + 1 \le \gamma(N).\]

theorem_wanted giniSimpsonCount_ge_triangular (N m r : ℕ)
    (hN : N = (m + 1) * m / 2 + r) (hr : r ≤ m) :
    (1 / 3) * (m : ℚ) * ((m : ℚ) ^ 2 + 3 * r - 1) + 1 ≤
      (giniSimpsonCount N : ℚ)

Sources

• Bradley K. Moon and Noah A. Rosenberg, "Integer Sequences for Diversity Statistics", Proposition 5.

Uses 1

Statement usesNumber of values of the Gini–Simpson index

TheoremQuadratic lower bound on the number of Gini–Simpson values#●ready to prove

Let \(\gamma(N)\) be the number of distinct values of \(a_1^2 + \dots + a_k^2\) over all finite sequences \((a_1, \dots, a_k)\) of natural numbers with \(a_1 + \dots + a_k = N\) (for \(N \ge 1\), the number of possible values of the Gini–Simpson index across samples of size \(N\)). Then for every natural number \(N\),

\[\tfrac{1}{2} \left( \lfloor N^2 / 5 \rfloor - N \right) \le \gamma(N).\]

theorem_wanted giniSimpsonCount_ge (N : ℕ) :
    (((N ^ 2 / 5 : ℕ) : ℚ) - N) / 2 ≤ (giniSimpsonCount N : ℚ)

Sources

• Bradley K. Moon and Noah A. Rosenberg, "Integer Sequences for Diversity Statistics", Proposition 6.

Uses 1

Statement usesNumber of values of the Gini–Simpson index

TheoremAsymptotics of the number of Gini–Simpson values#●ready to prove

Let \(\gamma(N)\) be the number of distinct values of \(a_1^2 + \dots + a_k^2\) over all finite sequences \((a_1, \dots, a_k)\) of natural numbers with \(a_1 + \dots + a_k = N\) (for \(N \ge 1\), the number of possible values of the Gini–Simpson index across samples of size \(N\)). Then \(\gamma(N) / N^2 \to 1/2\) as \(N \to \infty\), that is, \(\gamma(N) \sim \tfrac{1}{2} N^2\).

theorem_wanted giniSimpsonCount_asymp :
    Filter.Tendsto
      (fun N : ℕ => (giniSimpsonCount N : ℝ) / (N : ℝ) ^ 2)
      Filter.atTop (nhds (1 / 2))

Sources

• Bradley K. Moon and Noah A. Rosenberg, "Integer Sequences for Diversity Statistics", Proposition 7.

Uses 1

Statement usesNumber of values of the Gini–Simpson index

TheoremUpper bound on the number of Shannon values#●ready to prove

Let \(\sigma(N)\) be the number of distinct real numbers \(-\sum_{i=1}^{k} (a_i / N) \log (a_i / N)\) over all finite sequences \((a_1, \dots, a_k)\) of natural numbers with \(a_1 + \dots + a_k = N\), where a term with \(a_i = 0\) counts as \(0\) (for \(N \ge 1\), the number of possible values of the Shannon index across samples of size \(N\)). Then for every natural number \(N \ge 1\),

\[\sigma(N) \le \exp\left(\pi \sqrt{2/3} \sqrt{N}\right).\]

theorem_wanted shannonCount_le (N : ℕ) (hN : 1 ≤ N) :
    (shannonCount N : ℝ) ≤
      Real.exp (Real.pi * Real.sqrt (2 / 3) * Real.sqrt N)

Sources

• Bradley K. Moon and Noah A. Rosenberg, "Integer Sequences for Diversity Statistics", Proposition 8.

Uses 1

Statement usesNumber of values of the Shannon index

TheoremThe number of Shannon values grows faster than every polynomial#●ready to prove

Let \(\sigma(N)\) be the number of distinct real numbers \(-\sum_{i=1}^{k} (a_i / N) \log (a_i / N)\) over all finite sequences \((a_1, \dots, a_k)\) of natural numbers with \(a_1 + \dots + a_k = N\), where a term with \(a_i = 0\) counts as \(0\) (for \(N \ge 1\), the number of possible values of the Shannon index across samples of size \(N\)). Then for every nonzero polynomial \(q\) with real coefficients, \(\sigma(N) / |q(N)| \to \infty\) as \(N \to \infty\).

theorem_wanted shannonCount_superpolynomial
    (q : Polynomial ℝ) (hq : q ≠ 0) :
    Filter.Tendsto
      (fun N : ℕ => (shannonCount N : ℝ) / |q.eval (N : ℝ)|)
      Filter.atTop Filter.atTop

Sources

• Bradley K. Moon and Noah A. Rosenberg, "Integer Sequences for Diversity Statistics", Theorem 9.

Uses 1

Statement usesNumber of values of the Shannon index

2 fully proved6 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.