Graph Structure of Chebyshev Permutation Polynomials over Binary and Ternary Adic Rings

• URL: http://arxiv.org/abs/2605.21819v1
• Date: Wed, 20 May 2026 23:39:55 GMT
• Title: Graph Structure of Chebyshev Permutation Polynomials over Binary and Ternary Adic Rings
• Abstract summary: We investigate the graph structure of Chebyshev permutations over the ring $bbZ_2k13k$.<n>We show that, despite the complexities introduced by the binary and ternary components, the graph exhibits strong regularities.<n>Our results extend previous studies over prime-power rings, offering insights into the emergence of complexity in digital nonlinear maps.
• Score: 6.769253525763681
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding the functional graph of a nonlinear map over a finite domain is crucial for analyzing its dynamical complexity and potential applications in cryptography and pseudorandom generation. In this paper, we investigate the graph structure of Chebyshev permutation polynomials over the ring $\mathbb{Z}_{2^{k_1}3^{k_2}}$, where $k_1$ and $k_2$ are positive integers and $0\in\{k_1, k_2\}$. Each element of the ring is regarded as a vertex, and the mapping relation defined by the polynomial corresponds to a directed edge. Building on new properties of Chebyshev polynomials modulo powers of $2$ and $3$, we provide an explicit characterization of path lengths and cycle structures in the functional graph. We show that, despite the complexities introduced by the binary and ternary components, the graph exhibits strong regularities, including a constant number of cycles of a given length and predictable branching patterns as $k_1$ and $k_2$ increase. Our results extend previous studies over prime-power rings, offering insights into the emergence of complexity in digital nonlinear maps and supporting the security analysis of their cryptographic applications.

Related papers

• Cycle-Structure Generating Functions for Special Breakpoint Graphs [0.0]
  Breakpoint graphs originate in comparative genomics, where their alternating cycles encode relationships between genomes.<n>We study a constrained class of three-colored breakpoint graphs associated with permutations and develop cycle-refined generating functions for two extremal families.<n>The results determine the leading and constant-order moments entering the Rényi entropy expansion, with the projective-plane contribution giving the finite-size constant correction.
  arXiv  Detail & Related papers  (2026-08-31T13:29:37Z)
• Computational aspects of the Volterra Signature [0.0]
  We introduce efficient algorithms for the Volterra signature kernel.<n>All algorithms are implemented in the publicly available JAX-based package "tensordev"<n>We show that the number of factors in matrix-valued kernels of the form $K(t,s)=sum_p k_p(t-s)A_p$ do not increase the complexity in $J$ and $N$.
  arXiv  Detail & Related papers  (2026-05-18T13:46:47Z)
• Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory [0.5156484100374059]
  Quantum signal processing is a powerful framework in quantum algorithms, playing a central role in Hamiltonian simulation and related applications.<n>We characterize the achievable bases in terms of their orthogonality or biorthogonality with respect to a functional admitting an integral representation.<n>Explicit expressions for the quantum signal processing angles are derived for families of sequences.
  arXiv  Detail & Related papers  (2026-05-06T18:00:26Z)
• Quantum Algorithms for Approximate Graph Isomorphism Testing [0.0]
  We study the quantum query complexity of approximate graph isomorphism testing.<n>We present a quantum algorithm based on MNRS quantum walk search over the product graph $(G,H)$ of the two input graphs.
  arXiv  Detail & Related papers  (2026-03-03T06:43:41Z)
• Stationarity and Spectral Characterization of Random Signals on Simplicial Complexes [45.01439616647312]
  We propose a probabilistic framework for random signals defined on simplicial complexes.<n>Specifically, we generalize the classical notion of stationarity.<n>We empirically demonstrate the practicality of these benefits through multiple synthetic and real-world simulations.
  arXiv  Detail & Related papers  (2026-02-03T03:31:10Z)
• Positive maps and extendibility hierarchies from copositive matrices [4.914288166307964]
  This work introduces and systematically studies a new convex cone of PCOP (pairwise copositive)<n>We establish that this cone is dual to the cone of PCP (pairwise completely positive) and, critically, provides a complete characterization for the positivity of the broad class of covariant maps.
  arXiv  Detail & Related papers  (2025-09-18T17:54:09Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Building manifolds from quantum codes [0.0]
  We construct the first examples of power law $mathbbZ$ systolic freedom. We give an efficient randomized algorithm to construct a weakly fundamental cycle basis for a graph. We use this result to trivialize the fundamental group of the manifold we construct.
  arXiv  Detail & Related papers  (2020-12-03T20:36:50Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  We study the power of graph neural networks (GNNs) via their ability to count attributed graph substructures. We distinguish between two types of substructure counting: inducedsubgraph-count and subgraphcount-count, and both positive and negative answers for popular GNN architectures.
  arXiv  Detail & Related papers  (2020-02-10T18:53:30Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.