Quantifying noninvertibility in discrete dynamical systems

DOI10.37236/9475MaRDI QIDQ2200430zbMATH OpenOpenAlexFDO

Authors Colin Defant, James Propp

Publication date 21 September 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2002.07144

zbMATH Keywords

Bulgarian solitaire mapCarolina solitaire mapdegree of noninvertibility

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of partitions of integers (05A17) Combinatorial dynamics (types of periodic orbits) (37E15) Iteration theory, iterative and composite equations (39B12) Random iteration (37H12)

Abstract: Given a finite set $X$ and a function $f:XoX$, we define the degree of noninvertibility of $f$ to be $displaystyleextdeg(f)=frac1|X|su{m}_{xinX}|f^{-1}(f(x))|$. This is a natural measure of how far the function $f$ is from being bijective. We compute the degrees of noninvertibility of some specific discrete dynamical systems, including the Carolina solitaire map, iterates of the bubble sort map acting on permutations, bubble sort acting on multiset permutations, and a map that we call "nibble sort." We also obtain estimates for the degrees of noninvertibility of West's stack-sorting map and the Bulgarian solitaire map. We then turn our attention to arbitrary functions and their iterates. In order to compare the degree of noninvertibility of an arbitrary function $f:XoX$ with that of its iterate $f^k$, we prove that [max_{substack{f:X o X\ |X|=n}}frac{ ext{deg}(f^k)}{ ext{deg}(f)^gamma}=Theta(n^{1-1/2^{k-1}})] for every real number $gammageq2-1/2^{k-1}$. We end with several conjectures and open problems.

Recommendations

• The expected degree of noninvertibility of compositions of functions and a related combinatorial identity
• Pre-image entropy
• Nondegenerate functions and permutations
• Measure of noninvertibility of minimal maps
• Discrete, sequential dynamical systems

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 3226601 (Why is no real title available?)
• scientific article; zbMATH DE number 5181756 (Why is no real title available?)
• scientific article; zbMATH DE number 3073237 (Why is no real title available?)
• 30 years of Bulgarian solitaire
• A survey of stack-sorting disciplines
• Asymptotic formulae for partition ranks
• Combinatorics of permutations
• Counting 3-stack-sortable permutations
• Descent polynomials for permutations with bounded drop size
• Postorder Preimages
• Preimages under the stack-sorting algorithm
• Random mappings with constraints on coalescence and number of origins
• The biHecke monoid of a finite Coxeter group and its representations.
• The cycling of partitions and composition under repeated shifts

Cited in

(9)

• Preimages under the bubblesort operator
• Troupes, cumulants, and stack-sorting
• Necessary conditions for the invertibility of linear discrete dynamical systems
• The expected degree of noninvertibility of compositions of functions and a related combinatorial identity
• The minimal sum of squares over partitions with a nonnegative rank
• Troupes, cumulants, and stack-sorting
• On the estimate of the distance to non-invertibility
• scientific article; zbMATH DE number 7632585 (Why is no real title available?)
• Fertilitopes

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Quantifying noninvertibility in discrete dynamical systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200430)