Quantifying noninvertibility in discrete dynamical systems

DOI10.37236/9475zbMATH Open1475.37045arXiv2002.07144OpenAlexW3083469310MaRDI QIDQ2200430FDOQ2200430

Authors: Colin Defant, James Propp 

Publication date: 21 September 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorics of permutations
• Asymptotic formulae for partition ranks
• A survey of stack-sorting disciplines
• The biHecke monoid of a finite Coxeter group and its representations.
• Random mappings with constraints on coalescence and number of origins
• Title not available (Why is that?)
• Descent polynomials for permutations with bounded drop size
• Title not available (Why is that?)
• Counting 3-stack-sortable permutations
• Preimages under the stack-sorting algorithm
• Postorder Preimages
• Title not available (Why is that?)
• The cycling of partitions and composition under repeated shifts
• 30 years of Bulgarian solitaire

Cited In (9)

• 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
• Title not available (Why is that?)
• Fertilitopes
• Preimages under the bubblesort operator
• Troupes, cumulants, and stack-sorting

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)