The Gini Index of an Integer Partition

Grant Kopitzke Department of Mathematics University of Wisconsin, Milwaukee Milwaukee, WI 53211 USA

                       kopitzk3@uwm.edu

Abstract

The Gini index is a number that attempts to measure how equitably a resource is distributed throughout a population, and is commonly used in economics as a measurement of inequality of wealth or income. The Gini index is often defined as the area between the Lorenz curve of a distribution and the line of equality, normalized to be between zero and one. In this fashion, we define a Gini index on the set of integer partitions and show that it is closely related to the second elementary symmetric polynomial, and the dominance order on partitions. We conclude with a generating function for the Gini index, and discuss how it can be used to find lower bounds on the width of the dominance lattice.

1 Introduction

In part one of his 1912 book “Variabilità e Mutabilità” (Variability and Mutability), the statistician Corrado Gini formulated a number of different summary statistics; among which was what is now known as the Gini index — a measure that quantifies how equitably a resource is distributed throughout a population. Referring to “the” Gini index can be misleading, as no fewer than thirteen formulations of his famous index appeared in the original publication [?]. Since then, many others have appeared in a variety of different fields.

The Gini index is usually defined using the Lorenz curve. In “Methods of Measuring the Concentration of Wealth”, Lorenz defined this curve in the following fashion. Consider a population of people amongst whom is distributed some fixed amount of wealth. Let L(x) be the percentage of total wealth possessed by the poorest x percent of the population. The graph y = L(x) is the Lorenz curve of the population [?].

It is clear from this definition that L(0) = 0 (i.e., none of the people have none of the wealth), L(1) = 1 (all of the people have all of the wealth), and L is non-decreasing. Since any population of people must have finite size n, the function L(x) as defined above would appear to be a discrete function on the set \{\frac{k}{n} : k ∈ ℤ and 0 ≤ k ≤ n\}. However, in practice L is often made continuous on [0, 1] by linear interpolation [?].

If each person possesses the same amount of wealth, then the Lorenz curve for this distribution is the line y = x, which we call the “line of equality”. The area between the line of equality and the Lorenz curve of a wealth distribution provides a measurement of the wealth inequality in that population.

Figure 1: Area between the line of equality and a typical Lorenz curve

The maximum possible area of \frac{1}{2} arises from the distribution in which one person controls all of the wealth (L(1) = 1, and L(x) = 0 for all x ≠ 1). The Gini index of a distribution is then defined by calculating the area between the line of equality and Lorenz curve of the distribution, and normalizing this area to be between zero and one.

G = 2 ∫_{0}^{1} (x − L(x))dx

In this paper we consider distributions of a discrete indivisible resource in a finite population, where the amount of that resource is equal to the number of people in the population. There is a natural one-to-one correspondence between the set of such distributions with n people, and the set of partitions of n. We will then define the Gini index of a integer partition in a similar fashion as above; for a comparable Gini index defined on a partition of a set, see [?].

2 Preliminaries

2.1 Partitions and Young diagrams

A partition, λ, of a positive integer n (sometimes written as λ ⊢ n) is a sequence (λ_{1}, λ_{2}, …, λ_{ℓ}) of ℓ ≤ n non-increasing positive integers such that ∑_{i=1}^{ℓ} λ_{i} = n. The λ_{i} (1 ≤ i ≤ ℓ) are called the “parts of λ”. To avoid repeating parts, it is sometimes useful to write a partition as (λ_{1}^{a_{1}}, λ_{2}^{a_{2}}, …, λ_{ℓ}^{a_{ℓ}}) to represent λ_{i} repeating a_{i} times. In this case, we have that ∑_{i=1}^{ℓ} a_{i}λ_{i} = n, and λ_{i} ≠ λ_{j} for all i ≠ j. This notation will be used in the proof of Proposition 4. In order to make the length of λ (the number of parts) equal to n, one can “pad out” the partition by adding n − ℓ zeros to the end. For example, the partition (4, 3, 1, 1) of 9 is equivalent to (4, 3, 1, 1, 0, 0, 0, 0, 0). This technique will be used when defining the Lorenz curve of a partition.

A Young diagram is a finite collection of boxes arranged in left-justified rows, with a weakly decreasing number of boxes in each row [?]. Integer partitions are in one-to-one correspondence with Young diagrams in the following way: if λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) is a partition of n then the Young diagram of shape λ has λ_{1} boxes in its first row, λ_{2} boxes in its second row, etc. For example, if λ = (4, 3, 1, 1), then the Young diagram of shape λ is

.

The conjugate partition λ̃ of λ is the partition of n obtained by reflecting the Young diagram of λ across its main diagonal. As in the previous example, if λ = (4, 3, 1, 1), then the Young diagram of λ̃ is

,

hence λ̃ = (4, 2, 2, 1). Conjugation is clearly a bijection on the partitions of n.

The dominance order is a partial order on the set of partitions of n. If λ = (λ_{1}, λ_{2}, …, λ_{n}) and μ = (μ_{1}, μ_{2}, …, μ_{n}) are partitions of n, then μ ⪯ λ if

∑_{i=1}^{k} μ_{i} ≤ ∑_{i=1}^{k} λ_{i}

for all k ≥ 1. Conjugation of partitions is an antiautomorphism on the dominance lattice of partitions of n [?]. In other words, if μ ⪯ λ, then λ̃ ⪯ μ̃. We will write μ ≺ λ if μ ⪯ λ and μ ≠ λ, and will let P_{n} denote the partially ordered set of partitions of n with respect to dominance.

For a fixed positive integer n, an antichain in P_{n} is a subset of P_{n} in which all partitions are pairwise incomparable. A maximum antichain is an antichain of maximal cardinality. The length of the maximum antichain is also known as the width of the lattice. The width of P_{n} \underline{A076269} is currently an open problem.

2.2 The second elementary symmetric polynomial

The second elementary symmetric polynomial, e_{2}, in n variables, x_{1}, x_{2}, … x_{n}, is defined

e_{2}(x_{1}, x_{2}, …, x_{n}) = ∑_{1≤i<j≤n} x_{i}x_{j}.

For example, if λ = (4, 3, 1, 1) is a partition of 9, then

e_{2}(λ) = (4(3 + 1 + 1) + 3(1 + 1) + 1(1)) = 27.

We will make use of the following result.

Lemma 1. If λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) is a partition of a positive integer n, then

e_{2}(λ) = \binom{n + 1}{2} − ∑_{i=1}^{ℓ} \binom{λ_{i} + 1}{2}.

Proof. Let λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) be a partition of n. Note that ∑_{i=1}^{ℓ} λ_{i} = n. Then

e_{2}(λ) = ∑_{1≤i<j≤ℓ} λ_{i}λ_{j}

= \binom{n + 1}{2} − ( ∑_{1≤i<j≤ℓ} ( − λ_{i}λ_{j}) + \binom{n + 1}{2})

= \binom{n + 1}{2} − \frac{1}{2} ( ∑_{1≤i<j≤ℓ} ( − 2λ_{i}λ_{j}) + n(n + 1))

= \binom{n + 1}{2} − \frac{1}{2} ( ∑_{1≤i<j≤ℓ} ( − 2λ_{i}λ_{j}) + (∑_{i=1}^{ℓ} λ_{i}) (∑_{j=1}^{ℓ} λ_{j} + 1))

= \binom{n + 1}{2} − \frac{1}{2} ( ∑_{1≤i<j≤ℓ} ( − 2λ_{i}λ_{j}) + ∑_{i=1}^{ℓ} (λ_{i}^{2} + λ_{i}) + ∑_{1≤i<j≤ℓ} (2λ_{i}λ_{j}))

= \binom{n + 1}{2} − \frac{1}{2} (∑_{i=1}^{ℓ} λ_{i}(λ_{i} + 1))

= \binom{n + 1}{2} − (∑_{i=1}^{ℓ} \binom{λ_{i} + 1}{2}) .

3 The Gini index of an integer partition

As previously stated, we restrict our study of the Gini index to finite populations where the amount of a discrete indivisible resource is equal to the size of the population. In other words, there is one of said resource available for each person. The distributions of n of such a resource amongst n people is in one-to-one correspondence with the integer partitions of n.

For example, if there are 4 dollars in a population of 4 people, then the partition (3, 1) of 4 would correspond to one person having 3 dollars, one person having 1 dollar, and the two remaining people having nothing. Whereas the partitions (1, 1, 1, 1) and (4) correspond to completely equitable and completely inequitable distributions, respectively.

Given a partition λ = (λ_{1}, …, λ_{n}) of a positive integer n (padded with zeros on the tail, if necessary), the Lorenz curve of λ, L_{λ} : [0, n] ⟶ [0, n], is defined as L_{λ}(0) = 0, and L_{λ}(x) = ∑_{i=n−k+1}^{n} λ_{i}, where 1 ≤ k ≤ n is the unique positive integer such that x ∈ (k −1, k]. In other words, for k from 1 to n, the Lorenz curve of λ on the interval (k − 1, k] is the sum of the last k parts of λ, i.e., λ_{n} + λ_{n−1} + ⋯ + λ_{n−k+1}. Since total equality corresponds to the flat partition (1^{n}), using the above definition for the Lorenz curve of a partition, we find that the line of equality is given by y = ⌈x⌉.

Figure 2: The line of equity (dashed) and the Lorenz curve of the partition (3,2,1) of 6 (solid).

The standard Gini index is calculated by finding the area between the line of equality and the Lorenz curve, and normalizing. In a similar fashion, we define the Gini index, g, of a partition λ = (λ_{1}, …, λ_{n}) of n by

g(λ) = ∫_{0}^{n} (⌈x⌉ − L_{λ}(x)) dx

= \binom{n + 1}{2} − ∑_{i=1}^{n} iλ_{i}.

The ordinary Gini index is normalized to be between zero and one. For a fixed value of n, the function g attains its maximum value of \binom{n}{2} on the partition (n) of n. So the Gini index of a partition λ of n can be normalized by dividing g(λ) by \binom{n}{2}. As long as n, and g(λ) are both known, the normalized Gini index of λ can always be calculated in this fashion. With this in mind, we may disregard the normalization, and view g itself as the integer valued Gini index of a partition.

Our construction of g in conjunction with Lemma 1 yields some interesting results:

Proposition 2. If λ is an integer partition, then g(λ) = e_{2}(λ̃), where λ̃ is the conjugate partition of λ.

Proposition 3. Let λ and μ be partitions of n. If μ ≺ λ, then g(μ) < g(λ) and e_{2}(λ) < e_{2}(μ).

The normalized Gini index on ℝ^{n} restricted to P_{n} is equal to \frac{2g}{n^{2}} . Arnold et.al. [?] have shown that the normalized Gini index is strictly Schur convex, so Proposition 3 follows from this fact. A complete proof of Proposition 3 that does not utilize these facts will be given in section 5.

The converse of Proposition 3 does not hold, in general. However, the contrapositive provides us with an easily calculated lower bound on the width of P_{n}. For if λ, μ ∈ P_{n} are distinct partitions such that g(λ) = g(μ), then the partitions λ and μ are incomparable. Such lower bounds can be calculated using the generating function of g given in the following section.

4 Generating functions

It is often useful in Algebraic Combinatorics to record a discrete data set in the coefficients or powers of a formal power series. We call these power series “generating functions” for the data set. By “formal” we mean that the convergence of the series is immaterial. Any variables appearing in the series are taken as indeterminates rather than numbers. Alternatively, one may consider a formal power series as an ordinary power series that converges only at zero.

We define a generating function for the Gini index g(λ) of an integer partition λ by

G(q, x) = ∑_{n=1}^{∞} ∑_{λ⊢n} q^{(\binom{n+1}{2}−g(λ))}x^{n}.

Perhaps the most widely known example of a generating function is that of the integer partition function P (n), which counts the number of partitions of the integer n. For example, n = 4 has partitions

(1, 1, 1, 1), (2, 1, 1), (2, 2), (3, 1), and (4),

so P (4) = 5. It is well known [?] that P (n) has generating function

∏_{n=1}^{∞} \frac{1}{1 − x^{n}} = ∑_{n=0}^{∞} P (n)x^{n},

where P (0) is defined to be 1.

In light of our previous results, we obtain a similar equality for G(q, x).

Proposition 4.

∏_{n=1}^{∞} \frac{1}{1 − q^{\binom{n+1}{2}}x^{n}} − 1 = ∑_{n=1}^{∞} ∑_{λ⊢n} q^{(\binom{n+1}{2}−g(λ))}x^{n}.

The proof is provided in the following section.

We can use G(q, x) to find lower bounds on the width of P_{n} by calculating the cardinalities of the maximum level sets of g on P_{n}. In particular, the cardinality of the maximum level set of g on P_{n} will be the largest coefficient on the powers of q that form the coefficient of x^{n}. Expanding G(q, x) yields

∑_{n=1}^{∞} ∑_{λ⊢n} q^{(\binom{n+1}{2}−g(λ))}x^{n} = qx + (q^{2} + q^{3})x^{2} + (q^{3} + q^{4} + q^{6})x^{3}
+ (q^{4} + q^{5} + q^{6} + q^{7} + q^{10})x^{4}
+ (q^{5} + q^{6} + q^{7} + q^{8} + q^{9} + q^{11} + q^{15})x^{5}
+ (⋯ + 2q^{9} + ⋯)x^{6} + (⋯ + 2q^{10} + ⋯)x^{7}
+ (⋯ + 2q^{11} + ⋯)x^{8} + (⋯ + 3q^{15} + ⋯)x^{9}
+ · · · .

So the cardinalities of the maximum level sets of g are 1, 1, 1, 1, 1, 2, 2, 2, and 3, on P_{1} through P_{9}, respectively.

Let b(n) denote the cardinality of the maximal level set of g on P_{n} \underline{A337206}. Proposition 3 implies that b(n) ≤ a(n) for all positive integers n, where a(n) is the size of the maximum antichain in P_{n} \underline{A076269}. Early [?] showed that Ω (n^{−5/2}e^{π\sqrt{2n/3}}) ≤ a(n). It is currently

unknown how b(n) relates asymptotically to a(n) or n^{−5/2}e^{π\sqrt{2n/3}}. However, we conjecture that b(n) ≤ O (n^{−5/2}e^{π\sqrt{2n/3}}).