Puri, Yash; Ward, Thomas Arithmetic and growth of periodic orbits. (English) Zbl 1004.11013 J. Integer Seq. 4, No. 2, Art. 01.2.1, 18 p. (2001). Summary: Two natural properties of integer sequences are introduced and studied. The first, exact realizability, is the property that the sequence coincides with the number of periodic points under some map. This is shown to impose a strong inner structure on the sequence. The second, realizability in rate, is the property that the sequence asymptotically approximates the number of periodic points under some map. In both cases we discuss when a sequence can have that property. For exact realizability, this amounts to examining the range and domain among integer sequences of the paired transformations \[ \text{Per}_n=\sum_{d|n}d~\text{Orb}_d;\qquad \text{Orb}_d=\tfrac{1}{n}\sum_{d|n}\mu(n/d)\text{Per}_d \qquad\text{ORBIT} \] that move between an arbitrary sequence of non-negative integers Orb counting the orbits of a map and the sequence Per of periodic points for that map. Several examples from the Encyclopedia of Integer Sequences [N. J. A. Sloane and S. Plouffe, Academic Press (1995; Zbl 0845.11001)] arise in this work, and a table of sequences from the Encyclopedia known or conjectured to be exactly realizable is given. Cited in 6 ReviewsCited in 15 Documents MSC: 11B83 Special sequences and polynomials 37C99 Smooth dynamical systems: general theory Keywords:integer sequences; exact realizability; periodic points; realizability in rate; paired transformations Citations:Zbl 0845.11001 Software:OEIS PDFBibTeX XMLCite \textit{Y. Puri} and \textit{T. Ward}, J. Integer Seq. 4, No. 2, Art. 01.2.1, 18 p. (2001; Zbl 1004.11013) Full Text: arXiv EuDML EMIS Online Encyclopedia of Integer Sequences: Period 2: repeat [0, 1]; a(n) = n mod 2; parity of n. Lucas numbers (beginning with 1): L(n) = L(n-1) + L(n-2) with L(1) = 1, L(2) = 3. a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.) Powers of 3: a(n) = 3^n. The squares: a(n) = n^2. Powers of 4: a(n) = 4^n. Powers of 5: a(n) = 5^n. Euler (or secant or ”Zig”) numbers: e.g.f. (even powers only) sec(x) = 1/cos(x). Powers of 6: a(n) = 6^n. Powers of 7: a(n) = 7^n. Sum of odd divisors of n. Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n]. Central binomial coefficients: binomial(2*n,n) = (2*n)!/(n!)^2. Number of sublattices of index n in generic 3-dimensional lattice. Powers of 8: a(n) = 8^n. Powers of 9: a(n) = 9^n. Powers of 11: a(n) = 11^n. Powers of 12. Powers of 13. Powers of 14. Powers of 15. Powers of 16: a(n) = 16^n. Powers of 17. Powers of 18. Powers of 19. Number of partially ordered sets (”posets”) with n labeled elements (or labeled acyclic transitive digraphs). Number of degree-n irreducible polynomials over GF(2); number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n; number of binary Lyndon words of length n. a(n) = sigma_2(n): sum of squares of divisors of n. sigma_3(n): sum of cubes of divisors of n. A Fielder sequence: a(n) = a(n-1) + a(n-2) + a(n-4). A Fielder sequence. A Fielder sequence. Number of irreducible polynomials of degree n over GF(5); dimensions of free Lie algebras. Number of degree-n irreducible polynomials over GF(7); dimensions of free Lie algebras. a(n) = binomial(2*n+1, n+1): number of ways to put n+1 indistinguishable balls into n+1 distinguishable boxes = number of (n+1)-st degree monomials in n+1 variables = number of monotone maps from 1..n+1 to 1..n+1. a(n+6) = -a(n+5) + a(n+4) + 3a(n+3) + a(n+2) - a(n+1) - a(n). a(n) = sign(n) if abs(n)<=3. a(n) = (3^n - 1)/2. Alternate Lucas numbers - 2. Characteristic function of nonprimes: 0 if n is prime, else 1. a(n) = binomial(3n,n). Number of aperiodic binary necklaces of length n with no subsequence 00, excluding the necklace ”0”. a(n) = denominator of Bernoulli(2n)/(2n). Denominators of Bernoulli numbers B_0, B_1, B_2, B_4, B_6, ... Number of 2n-bead black-white strings with n black beads and fundamental period 2n. Characteristic function of squares: a(n) = 1 if n is a square, otherwise 0. Powers of 10: a(n) = 10^n. Jacobsthal-Lucas numbers. Number of binary Lyndon words containing n letters of each type; periodic binary sequences of period 2n with n zeros and n ones in each period. Sum of the nonprime divisors of n. a(n) = 2^(n-1) + ((1 + (-1)^n)/4)*binomial(n, n/2). Number of ternary irreducible monic polynomials of degree n; dimensions of free Lie algebras. Number of irreducible polynomials of degree n over GF(4); dimensions of free Lie algebras. Number of irreducible polynomials of degree n over GF(8); dimensions of free Lie algebras. Number of irreducible polynomials of degree n over GF(9); dimensions of free Lie algebras. Number of aperiodic necklaces of n beads of 6 colors; dimensions of free Lie algebras. Number of aperiodic necklaces of n beads of 10 colors. Number of aperiodic necklaces of n beads of 11 colors. Number of aperiodic necklaces of n beads of 12 colors. ”CHK” (necklace, identity, unlabeled) transform of 1, 2, 3, 4, ... Sum of the square divisors of n. Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa. Pisot sequence L(3,5). a(n) = Sum_{d|n} binomial(n,d). The periodic point counting sequence for the toral automorphism given by the polynomial of (conjectural) smallest Mahler measure. The map is x -> Ax mod 1 for x in [0,1)^10, where A is the companion matrix for the polynomial x^10+x^9-x^7-x^6-x^5-x^4-x^3+x+1. Number of points of period n under the dual of the map x->2x on Z[1/6]. a(n) = 2^(n-2^ord_2(n)) (or 2^(n-A006519(n))). Number of orbits of length n under the map whose periodic points are counted by A000364. Number of orbits of length n under the map whose periodic points are counted by A000984. Number of orbits of length n under the map whose periodic points are counted by A001641. Number of orbits of length n under the map whose periodic points are counted by A001642. Number of orbits of length n under the map whose periodic points are counted by A001643. Number of orbits of length n under the automorphism of the 3-torus whose periodic points are counted by A001945. Number of orbits of length n under the map whose periodic points are counted by A005809. Number of orbits of length n under a map whose periodic points seem to be counted by A006953. Number of orbits of length n under a map whose periodic points are counted by A027306. Number of orbits of length n under a map whose periodic points are counted by A056045. Number of orbits of length n under the full 13-shift (whose periodic points are counted by A001022). Number of orbits of length n under the full 14-shift (whose periodic points are counted by A001023). Number of orbits of length n under the full 15-shift (whose periodic points are counted by A001024). Number of orbits of length n under the full 16-shift (whose periodic points are counted by A001025). Number of orbits of length n under the full 17-shift (whose periodic points are counted by A001026). Number of orbits of length n under the full 18-shift (whose periodic points are counted by A001027). Number of orbits of length n under the full 19-shift (whose periodic points are counted by A001029). Number of orbits of length n under the map whose periodic points are counted by A000670. Number of orbits of length n under the map whose periodic points are counted by A047863. Number of orbits of length n under the map whose periodic points are counted by A001350. A001067 appears to count the periodic points for a certain map. If so, then this is the sequence of the numbers of orbits of length n. The sequence A006863 (shifted by one) seems to be counting the periodic points for a map. If so, then this is the sequence of the numbers of orbits of length n. Number of orbits of length n in map whose periodic points are A000051. Number of orbits of length n in map whose periodic points are A059928. Number of orbits of length n in map whose periodic points come from A006954. Number of orbits of length n in map whose periodic points come from A059990. Number of orbits of length n in a map whose periodic points come from A059991. Number of orbits of length n under the map whose periodic points are counted by A061686. Number of orbits of length n under the map whose periodic points are counted by A061687. Number of orbits of length n under the map whose periodic points are counted by A061688. Number of orbits of length n under the map whose periodic points are counted by A061694. Number of orbits of length n under the map whose periodic points are counted by A061685. Number of orbits of length n under the map whose periodic points are counted by A061684. Number of orbits of length n under the map whose periodic points are counted by A061693. Denominators of the fixed point a=(a_1,a_2,...) of the transformation x’= fix(x) where fix(x)_n = Sum_{d|n} d x_d, i.e., fix(a)=a.