Kai Tan

The complex dynamics of the baker’s map and its variants in infinite-precision mathematical domains and quantum settings have been extensively studied over the past five decades. However, their behavior in finite-precision digital computing remains largely unknown. This paper addresses this gap by investigating the graph structure of the generalized two-dimensional baker’s map and its higher-dimensional extension, referred to as HDBM, as implemented on the discrete setting in a digital computer. We provide a rigorous analysis of how the map parameters shape the in-degree bounds and distribution within the functional graph, revealing fractal-like structures intensify as parameters approach each other and arithmetic precision increases. Furthermore, we demonstrate that recursive tree structures can characterize the functional graph structure of HDBM in a fixed-point arithmetic domain. Similar to the 2-D case, the degree of any non-leaf node in the functional graph, when implemented in the floating-point arithmetic domain, is determined solely by its last component. We also reveal the relationship between the functional graphs of HDBM across the two arithmetic domains. These findings lay the groundwork for dynamic analysis, effective control, and broader application of the baker’s map and its variants in diverse domains.

Understanding the underlying graph structure of a nonlinear map over a particular domain is essential in evaluating its potential for real applications. In this paper, we investigate the structure of the associated functional graph of Chebyshev permutation polynomials over a ring $\mathbb {Z}_{p^{k}}$ , with p being a prime number greater than three, where every number in the ring is considered as a vertex and the existing mapping relation between two vertices is regarded as a directed edge. Based on some new properties of Chebyshev polynomials and their derivatives, we disclose how the basic structure of the functional graph evolves with respect to parameter k. First, we present a complete and explicit form of the length of a path starting from any given vertex. Then, we show that the functional graph’s strong patterns indicate that the number of cycles of any given length always remains constant as k increases. Moreover, we rigorously prove the rules on the elegant structure of the functional graph and verify them experimentally. Our results could be useful for studying the emergence mechanism of the complexity of a nonlinear map in digital computers and security analysis of its cryptographic applications.