The Expected Degree of Noninvertibility of Compositions of Functions

Sela Fried^{1} Department of Computer Science Ben-Gurion University of the Negev David Ben-Gurion Blvd 1 Be’er Sheva Israel

                  friedsela@gmail.com

Abstract

Recently, Defant and Propp defined the degree of noninvertibility of a function f: X → Y between two finite nonempty sets by deg(f) = \frac{1}{|X|} ∑_{x∈X} |f^{−1}(f(x))|. We obtain an exact formula for the expected degree of noninvertibility of the composition of t functions for every t ∈ ℕ. Subsequently, we use the expected value to quantify a strengthening of a sort of a submultiplicativity property of the degree of noninvertibility. Finally, we generalize an equivalent formulation of the degree of noninvertibility and obtain a combinatorial identity involving the Stirling numbers of the first and second kind.

1 Introduction

Recently, Defant and Propp [1] defined the degree of noninvertibility of a function f: X → Y between two finite nonempty sets by

deg(f) = \frac{1}{|X|} ∑_{x∈X} |f^{−1}(f(x))|,

1The author is a postdoctoral fellow in the Department of Computer Science at the Ben-Gurion University of the Negev and a teaching fellow in the Department of Computer Science at the Israel Academic College in Ramat Gan.

as a measure of how far f is from being injective. For example, if f is k-to-1 for 1 ≤ k ≤ |X|, then deg(f) = k. In particular, if f is injective (resp., constant), then deg(f) = 1 (resp., deg(f) = |X|). A major part of their work was devoted to the computation of the degrees of noninvertibility of specific discrete dynamical systems (i.e., functions f: X → X), such as the Carolina solitaire map and the bubble sort map, to name a few. Turning their attention to arbitrary functions, they studied, from an extremal point of view, the connection between the degrees of noninvertibility of functions and those of their iterates.

The main objective of this work is the calculation of the expected degree of noninvertibility of a random function, or, more generally, of the composition of t random functions, for every t ∈ ℕ, thereby providing a probabilistic perspective on this new notion. The expected value is subsequently used to quantify a strengthening of a sort of a submultiplicativity property of the degree of noninvertibility. Additionally, an equivalent formulation of the degree of noninvertibility is generalized, yielding a combinatorial identity involving the Stirling numbers of the first and second kind.

We begin with a detailed presentation of our results. Section 3 contains their proofs. In Section 4 we show how the degrees of noninvertibility of several specific dynamical systems, considered by Defant and Propp [1], compare with the expected value. All the sets in this work are tacitly assumed to be nonempty and of finite sizes.

2 Main results

Let t ∈ ℕ to be used throughout this work.

Definition 1. Let X_{1}, …, X_{t+1} be t + 1 sets of sizes n_{1}, …, n_{t+1}, respectively. We denote the expected degree of noninvertibility of the composition of t functions between X_{1}, …, X_{n} by D(X_{1}, …, X_{t+1}), i.e.,

D(X_{1}, …, X_{t+1}) = \frac{1}{∏_{s=1}^{t} n_{s+1}^{n_{s}}} ∑_{\begin{matrix}f_{s}: X_{s}→X_{s+1} \\ 1≤s≤t \end{matrix}} deg(f_{t} ∘ ⋯ ∘ f_{1}).

Our first main result is an exact formula for the expected degree of noninvertibility of the composition of t random functions.

Theorem 2. Let X_{1}, …, X_{t+1} be t + 1 sets of sizes n_{1}, …, n_{t+1}, respectively. Then

D(X_{1}, …, X_{t+1}) = \frac{∏_{s=1}^{t+1} n_{s} − ∏_{s=1}^{t+1}(n_{s} − 1)}{∏_{s=2}^{t+1} n_{s}}.

In particular, if all the sets are equal, we obtain the following result.

Corollary 3. Let X be a set of size n. Then

D( \overbrace{X, …, X}^{t+1 times} ) = \frac{n^{t+1} − (n − 1)^{t+1}}{n^{t}} .

Thus,

lim_{n→∞} D( \overbrace{X, …, X}^{t+1 times} ) = t + 1.

Our second main result is concerned with a sort of a submultiplicativity property of the degree of noninvertibility [1, Theorem 3.4], according to which, if X is a set of size n and f, g: X → X are two functions, then

deg(f ∘ g) ≤ \sqrt{n}\sqrt{deg(f)} deg(g).  (1)

This inequality is strengthened in the following theorem. Subsequently, Corollary 3 is used to quantify the improvement.

Theorem 4. Let X, Y, and Z be three sets and let g: X → Y and f: Y → Z be two functions. Then

deg(f ∘ g) ≤ max_{z∈Z} |f^{−1}(z)| deg(g).  (2)

That Theorem 4 is a strengthening of (1), in the case that X = Y = Z, follows from the following Lemma.

Lemma 5. Let X be a set of size n and let Y be an additional set. Let f: X → Y be a function. Then

max_{y∈Y} |f^{−1}(y)| ≤ \sqrt{n}\sqrt{deg(f)}.

To quantitatively compare between (1) and (2) (still assuming X = Y = Z), we notice that, by Corollary 3, the order of the expectation of \sqrt{n}\sqrt{deg(f)} is Θ(\sqrt{n}). On the other hand, the order of the expectation of max_{x∈X} |f^{−1}(x)| is Θ (\frac{log(n)}{log(log(n))}), a result due to Gonnet [2] (see also the references in \underline{A208250} in the On-Line Encyclopedia of Integer Sequences (OEIS) [4]).

To motivate our last main result, notice that, if f: X → Y is a function between two sets X and Y, then

deg(f) = \frac{1}{|X|} ∑_{y∈Y} |f^{−1}(y)|^{2}.

This identity, which is easy to prove and which we shall freely use throughout this work, opens the door for a generalization: For p ∈ ℕ, let

deg(f, p) = \frac{1}{|X|} ∑_{y∈Y} |f^{−1}(y)|^{p}.

We obtain an exact formula for the expected value of deg(f, p). It involves the Stirling numbers of the first and second kind, denoted by \left[{n \atop k}\right] and \left\{{n \atop k}\right\}, respectively (e.g., [3, pp. 243–253]).

Theorem 6. Let p ∈ ℕ and let X and Y be two sets of sizes n and m, respectively. Then

\frac{1}{m^{n}} ∑_{f: X→Y} deg(f, p) = \frac{1}{m^{p−1}} ∑_{k=1}^{p} \left\{{p \atop k}\right\} (∑_{j=1}^{k}(−1)^{k−j}\left[{k \atop j}\right]n^{j−1}) m^{p−k}.

3 The proofs

Before we begin, let us introduce some notation to reduce clutter. We denote the set of nonnegative integers by ℕ_{0}. Let m, n ∈ ℕ. Bold face letters stand for vectors, i.e., k = (k_{1}, …, k_{n}). We define O(m, n) = {k ∈ ℕ_{0}^{n} : ∑_{i=1}^{n} k_{i} = m}. If k, ℓ ∈ ℕ_{0}^{n}, we let k^{ℓ} stand for ∏_{i=1}^{n} k_{i}^{ℓ_{i}}. We denote by mult(k) the multinomial coefficient corresponding to k ∈ O(m, n), i.e., mult(k) = \binom{m}{k_{1},...,k_{n}}. Finally, if p ∈ ℕ and k ∈ ℕ_{0}^{n}, then the p-norm of k is denoted by ||k||_{p}, i.e., ||k||_{p}^{p} = ∑_{i=1}^{n} k_{i}^{p}. We set ||k||_{0}^{0} = n.

The proof of Theorem 2 relies on the following lemma.

Lemma 7. Let X_{1}, …, X_{t+1} be t + 1 sets of sizes n_{1}, …, n_{t+1}, respectively. Then

D(X_{1}, …, X_{t+1}) = \frac{1}{n_{1} ∏_{s=1}^{t} n_{s+1}^{n_{s}}} ∑_{\begin{matrix}k^{(s)}∈O(n_{s},n_{t+1}) \\ 1≤s≤t \end{matrix}} (∏_{r=1}^{t} mult(k^{(r)})(k^{(r+1)})^{k^{(r)}}) ||k^{(1)}||_{2}^{2},

where k^{(t+1)} = (\overbrace{1, …, 1}^{n_{t+1} times}).

Proof. Assume that X_{t+1} = {x_{1}, …, x_{n_{t+1}}}, and, for every 1 ≤ s ≤ t, let f_{s}: X_{s} → X_{s+1}. For every 1 ≤ i ≤ n_{t+1}, we define iteratively: X_{i}^{(t)} = f_{t}^{−1}(x_{i}), k_{i}^{(t)} = |X_{i}^{(t)}| and, for 1 ≤ s ≤ t − 1, we set X_{i}^{(s)} = f_{s}^{−1}(X_{i}^{(s+1)}), k_{i}^{(s)} = |X_{i}^{(s)}|. Then (f_{t} ∘ ⋯ ∘ f_{1})^{−1}(x_{i}) = X_{i}^{(1)}. Thus, |(f_{t}∘⋯∘f_{1})^{−1}(x_{i})| = k_{i}^{(1)}. Now, for every 1 ≤ s ≤ t−1, there are exactly mult(k^{(s)})(k^{(s+1)})^{k^{(s)}} functions g: X_{s} → X_{s+1} such that |g^{−1}(X_{i}^{(s+1)})| = k_{i}^{(s)}, 1 ≤ i ≤ n_{t+1}.

Proof of Theorem 2. We proceed by induction on t. For the induction step we shall need the following identity, from which we shall also deduce the case t = 1: Let m, n ∈ ℕ and k ∈ ℕ_{0}^{n}. Put r = ∑_{i=1}^{n} k_{i}. We claim that

∑_{ℓ∈O(m,n)} mult(ℓ)k^{ℓ}||ℓ||_{2}^{2} = m(m − 1)r^{m−2}||k||_{2}^{2} + mr^{m}.  (3)

Indeed,

∑_{ℓ∈O(m,n)} mult(ℓ)k^{ℓ}||ℓ||_{2}^{2}

= ∑_{i=1}^{n} ∑_{ℓ∈O(m,n)} mult(ℓ)k^{ℓ}ℓ_{i}^{2}

= ∑_{i=1}^{n} ( ∑_{\begin{matrix}ℓ∈O(m,n) \\ ℓ_{i}=1 \end{matrix}} mult(ℓ)k^{ℓ}ℓ_{i}^{2} + ∑_{\begin{matrix}ℓ∈O(m,n) \\ ℓ_{i}≥2 \end{matrix}} mult(ℓ)k^{ℓ}ℓ_{i}^{2})

= ∑_{i=1}^{n} (mk_{i}(r − k_{i})^{m−1} + m ∑_{\begin{matrix}ℓ∈O(m,n) \\ ℓ_{i}≥2 \end{matrix}} \binom{m − 1}{ℓ_{1}, …, ℓ_{i} − 1, …, ℓ_{n}}k^{ℓ}(ℓ_{i} − 1 + 1))

= ∑_{i=1}^{n} (mk_{i}(r − k_{i})^{m−1} + k_{i}^{2}m(m − 1) ∑_{ℓ∈O(m−2,n)} mult(ℓ)k^{ℓ} + mk_{i} ∑_{\begin{matrix}ℓ∈O(m−1,n) \\ ℓ_{i}≥1 \end{matrix}} mult(ℓ)k^{ℓ})

= m ∑_{i=1}^{n} k_{i}((r − k_{i})^{m−1} + k_{i}(m − 1)r^{m−2} + ∑_{ℓ∈O(m−1,n)} mult(ℓ)k^{ℓ} − ∑_{\begin{matrix}ℓ∈O(m−1,n) \\ ℓ_{i}=0 \end{matrix}} mult(ℓ)k^{ℓ})

= m ∑_{i=1}^{n} k_{i} ((r − k_{i})^{m−1} + k_{i}(m − 1)r^{m−2} + r^{m−1} − (r − k_{i})^{m−1})

= m(m − 1)r^{m−2}||k||_{2}^{2} + mr^{m}. Let t = 1. Then, using Lemma 7,

D(X_{1}, X_{2}) = \frac{1}{n_{1}n_{2}^{n_{1}}} ∑_{k^{(1)}∈O(n_{1},n_{2})} mult(k^{(1)})||k^{(1)}||_{2}^{2}
=^{(3)} \frac{n_{1}(n_{1} − 1)n_{2}^{n_{1}−2}n_{2} + n_{1}n_{2}^{n_{1}}}{n_{1}n_{2}^{n_{1}}}

= \frac{n_{1} + n_{2} − 1}{n_{2}}

= \frac{n_{1}n_{2} − (n_{1} − 1)(n_{2} − 1)}{n_{2}}.

Suppose that the claim holds for t ∈ ℕ. Using Lemma 7 and the induction hypothesis, we have D(X_{1}, …, X_{t+2})

= \frac{1}{n_{1} ∏_{s=1}^{t+1} n_{s+1}^{n_{s}}} ∑_{\begin{matrix}k^{(s)}∈O(n_{s},n_{t+2}) \\ 1≤s≤t+1 \end{matrix}} (∏_{r=1}^{t+1} mult(k^{(r)})(k^{(r+1)})^{k^{(r)}}) ||k^{(1)}||_{2}^{2}

= \frac{1}{n_{1} ∏_{s=1}^{t+1} n_{s+1}^{n_{s}}} ∑_{\begin{matrix}k^{(s)}∈O(n_{s},n_{t+2}) \\ 2≤s≤t+1 \end{matrix}} (∏_{r=2}^{t+1} mult(k^{(r)})(k^{(r+1)})^{k^{(r)}}) ∑_{k^{(1)}∈O(n_{1},n_{t+2})} mult(k^{(1)})(k^{(2})^{k^{(1)}}||k^{(1)}||_{2}^{2}

=^{(3)} \frac{1}{n_{1} ∏_{s=1}^{t+1} n_{s+1}^{n_{s}}} ∑_{\begin{matrix}k^{(s)}∈O(n_{s},n_{t+2}) \\ 2≤s≤t+1 \end{matrix}} (∏_{r=2}^{t+1} mult(k^{(r)})(k^{(r+1)})^{k^{(r)}}) (n_{1}(n_{1} − 1)n_{2}^{n_{1}−2}||k^{(2)}||_{2}^{2} + n_{1}n_{2}^{n_{1}})

= \frac{n_{1}n_{2}^{n_{1}} ∏_{s=2}^{t+1} n_{s+1}^{n_{s}}}{n_{1} ∏_{s=1}^{t+1} n_{s+1}^{n_{s}}} + \frac{n_{1} − 1}{n_{2}^{2} ∏_{s=2}^{t+1} n_{s+1}^{n_{s}}} ∑_{\begin{matrix}k^{(s)}∈O(n_{s},n_{t+2}) \\ 2≤s≤t+1 \end{matrix}} (∏_{r=2}^{t+1} mult(k^{(r)})(k^{(r+1)})^{k^{(r)}}) ||k^{(2)}||_{2}^{2}

= 1 + (n_{1} − 1)\frac{∏_{s=2}^{t+2} n_{s} − ∏_{s=2}^{t+2}(n_{s} − 1)}{n_{2} ∏_{s=3}^{t+2} n_{s}}

= \frac{∏_{s=1}^{t+2} n_{s} − ∏_{s=1}^{t+2}(n_{s} − 1)}{∏_{s=2}^{t+2} n_{s}}.

Proof of Corollary 3. We have

D( \overbrace{X, …, X}^{t+1 times} ) = \frac{n^{t+1} − (n − 1)^{t+1}}{n^{t}}

= \frac{1}{n^{t}} ∑_{s=0}^{t}(−1)^{s}\binom{t + 1}{s + 1}n^{t−s}

= t + 1 + ∑_{s=1}^{t}(−1)^{s}\binom{t + 1}{s + 1}\frac{1}{n^{s}}

and the assertion follows.

Remark 8. The coefficients in the sum ∑_{s=0}^{t}(−1)^{s}\binom{t+1}{s+1}n^{t−s} correspond to the t + 1th row of Pascal’s triangle with alternating signs, omitting the first 1. For example, for t = 1, 2, and 3, the sum has the form

2n − 1,
3n^{2} − 3n + 1, and
4n^{3} − 6n^{2} + 4n − 1,

respectively.

Only a small modification of the proof of [1, Theorem 3.4] is necessary to prove Theorem 4. We give the full proof for completeness.

Proof of Theorem 4. Let z_{1}, …, z_{r} ∈ Z be such that f(g(X)) = {z_{1}, …, z_{r}}. For every 1 ≤ i ≤ r, let k_{i} = |f^{−1}(z_{i})| and let y_{i1}, …, y_{ik_{i}} ∈ Y be such that f^{−1}(z_{i}) = {y_{i1}, …, y_{ik_{i}}}. Furthermore, for 1 ≤ i ≤ r and 1 ≤ j ≤ k_{i}, let ℓ_{ij} = |g^{−1}(y_{ij})|. We have

deg(f ∘ g) = \frac{1}{n} ∑_{i=1}^{r} |g^{−1}(f^{−1}(z_{i}))|^{2}

= \frac{1}{n} ∑_{i=1}^{r} (∑_{j=1}^{k_{i}} ℓ_{ij})^{2}

≤^{(a)} \frac{1}{n} ∑_{i=1}^{r} k_{i} ∑_{j=1}^{k_{i}} ℓ_{ij}^{2}

≤ max_{z∈Z} |f^{−1}(z)| \overbrace{\frac{1}{n} ∑_{i=1}^{r} ∑_{j=1}^{k_{i}} ℓ_{ij}^{2}}^{=^{(b)}deg(g)}

= max_{z∈Z} |f^{−1}(z)| deg(g),

where in (a) we used the Cauchy-Schwarz inequality and (b) is due to the fact that

g(X) ⊆ f^{−1}(f(g(X))) = {y_{ij} : 1 ≤ i ≤ r, 1 ≤ j ≤ k_{i}}.

Proof of Lemma 5. Assume that Y is of size m. Applying the inequality ||x||_{∞} ≤ ||x||_{2}, which holds for every x ∈ ℝ^{m}, on the vector in ℝ^{m}, whose entries correspond to the sizes of the preimages under f of all the elements of Y, we obtain

max_{y∈Y} |f^{−1}(y)| ≤ \sqrt{∑_{y∈Y} |f^{−1}(y)|^{2}} = \sqrt{n}\sqrt{\frac{1}{n} ∑_{y∈Y} |f^{−1}(y)|^{2}} = \sqrt{n}\sqrt{deg(f)}.

Proof of Theorem 6. We proceed by induction on p and prove that, for every m, n ∈ ℕ and p ∈ ℕ_{0}, we have

∑_{k∈O(n,m)} mult(k)||k||_{p}^{p}

= \begin{cases}nm^{n−(p−1)} ∑_{k=1}^{p} \left\{{p \atop k}\right\} (∑_{j=1}^{k}(−1)^{k−j}\left[{k \atop j}\right]n^{j−1}) m^{p−k}, & if p ≥ 1; \\ m^{n+1}, & otherwise. \end{cases}

The cases p = 0, 1 or n = 1 are immediate. Suppose that the assertion holds for every m, n ∈ ℕ and every 0 ≤ r ≤ p. Assume that n ≥ 2. We have

∑_{k∈O(n,m)} mult(k)||k||_{p+1}^{p+1}

= n ∑_{i=1}^{m} ∑_{\begin{matrix}k∈O(n,m) \\ k_{i}≥1 \end{matrix}} \binom{n − 1}{k_{1}, …, k_{i} − 1, …, k_{m}}(k_{i} − 1 + 1)^{p}

= n ∑_{r=0}^{p} \binom{p}{r} ∑_{i=1}^{m} ∑_{\begin{matrix}k∈O(n,m) \\ k_{i}≥1 \end{matrix}} \binom{n − 1}{k_{1}, …, k_{i} − 1, …, k_{m}}(k_{i} − 1)^{r}

= n ∑_{r=0}^{p} \binom{p}{r} ∑_{k∈O(n−1,m)} mult(k)||k||_{r}^{r}

=^{(c)} n ∑_{r=1}^{p} \binom{p}{r}(n − 1)m^{n−r} ∑_{k=1}^{r} \left\{{r \atop k}\right\} (∑_{j=1}^{k}(−1)^{k−j}\left[{k \atop j}\right](n − 1)^{j−1}) m^{r−k} + nm^{n}

= nm^{n−t} ∑_{k=1}^{p} \overbrace{∑_{r=k}^{p} \binom{p}{r}\left\{{r \atop k}\right\}}^{^{=^{(d)}}\left\{{p+1 \atop k+1}\right\}} (∑_{j=1}^{k}(−1)^{k−j}\left[{k \atop j}\right] \overbrace{(n − 1)^{j}}^{=∑_{l=0}^{j} \binom{j}{l}(−1)^{l}n^{j−l}}) m^{p−k} + nm^{n}

= nm^{n−p} ∑_{k=1}^{p} \left\{{p + 1 \atop k + 1}\right\} (\overbrace{∑_{j=1}^{k} ∑_{l=0}^{j}(−1)^{k+l−j}\binom{j}{l}\left[{k \atop j}\right]n^{j−l}}^{=^{(e)}∑_{j=0}^{k}(−1)^{k−j} \left[{k+1 \atop j+1}\right]n^{j}}) m^{p−k} + nm^{n−p}m^{p}

= nm^{n−p} (∑_{k=1}^{p} \left\{{p + 1 \atop k + 1}\right\} (∑_{j=0}^{k}(−1)^{k−j}\left[{k + 1 \atop j + 1}\right]n^{j}) m^{p−k} + m^{p})

= nm^{n−p} ∑_{k=1}^{p+1} \left\{{p + 1 \atop k}\right\} (∑_{j=1}^{k}(−1)^{k−j}\left[{k \atop j}\right]n^{j−1}) m^{p+1−k},

where, in (c), we used the induction hypothesis, (d) is due to [3, Eq. (6.15)], and (e) follows after several algebraic manipulations, together with [3, Eq. (6.16)].

4 The limiting behavior of the degrees of noninvertibility of several specific dynamical systems

Let X be a set of size n. By Corollary 3, the expected degree of noninvertibility of a dynamical system f: X → X tends to 2, as n → ∞. Defant and Propp [1] established the degrees of noninvertibility of several specific dynamical systems. Table 1 below summarizes their limiting behavior. Interestingly, in the cases where the limit is finite, it is not far from the expected value.

5 Acknowledgments

We thank the anonymous referee for the careful reading of the manuscript and for the helpful suggestions. We are also grateful to J. Propp for suggesting us the consideration of compositions of functions.

The dynamical system f  The set X  lim_{n→∞} deg(f) Remarks
Bubble sort (for permutations)  Sym(n)  ∞
Stack-sorting  Sym(n)  ∞
Nibble sort (for permutations)  Sym(n)  4e − 9  ≈ 1.873
Nibble sort (for binary words)  {0, 1}^{n}  3/2
Binary chip-firing on an n + 1-cycle  {0, 1}^{n}  3/2
Bulgarian solitaire  partitions of n  3  conjectured
Carolina solitaire  compositions of n  ∞

Table 1: The limiting behavior of the degrees of noninvertibility of several specific dynamical systems, established by Defant and Propp [1].

References

[1] C. Defant and J. Propp, Quantifying noninvertibility in discrete dynamical systems, Electron. J. Combin. 27 (2020), Article P3.51.

[2] G. H. Gonnet, Expected length of the longest probe sequence in hash code searching, J. ACM 28 (1981), 289–304.

[3] R. L. Graham, D. E. Knuth, O. Patashnik, and S. Liu, Concrete Mathematics, Addison-Wesley, 1989.

[4] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, OEIS Foundation Inc.,

   https://oeis.org.

2010 Mathematics Subject Classification: Primary 05A99; Secondary 37A99.

Keywords: degree of noninvertibility, dynamical system, Stirling number.

(Concerned with sequences \underline{A074909} and \underline{A208250}.)

Received September 8 2022; revised version received October 10 2022; October 12 2022; October 21 2022. Published in Journal of Integer Sequences, October 25 2022.

Return to Journal of Integer Sequences home page.