×

The ring of \(k\)-regular sequences. (English) Zbl 0774.68072

Summary: [See also the review of the preliminary version in Zbl 0742.11012.]
The automatic sequence is the central concept at the intersection of formal language theory and number theory. It was introduced by A. Cobham (1969, 1972), and has been extensively studied by G. Christol et al. (1980) and other writers. Since the range of automatic sequences is finite, however, their descriptive power is severely limited.
In this paper, we generalize the concept of automatic sequence to the case where the sequence can take its values in a (possibly infinite) ring \(R\); we call such sequences \(k\)-regular. (When \(R\) is finite, we obtain automatic sequences as a special case.) We argue that \(k\)-regular sequences provide a good framework for discussing many “naturally occurring” sequences, and we support this contention by exhibiting many examples of \(k\)-regular sequences from numerical analysis, topology, number theory, combinatorics, analysis of algorithms, and the theory of fractals.
We investigate the closure properties of \(k\)-regular sequences. We prove that the set of \(k\)-regular sequences forms a ring under the operations of term-by-term addition and convolution. Hence, the set of associated formal power series in \(R[[X]]\) also forms a ring.
We show how \(k\)-regular sequences are related to \(\mathbb{Z}\)-rational formal series. We give a machine model for the \(k\)-regular sequences. We prove that all \(k\)-regular sequences can be computed quickly.
Let the pattern sequence \(e_ P(n)\) count the number of occurrences of the pattern \(P\) in the base-\(k\) expansion of \(n\). Morton and Mourant (1989) showed that every sequence over \(\mathbb{Z}\) has a unique expansion as a sum of pattern sequences. We prove that this “Fourier” expansion maps \(k\)-regular sequences to \(k\)-regular sequences. In particular, the coefficients in the expansion of \(e_ P(an+b)\) form a \(k\)-automatic sequence. Many natural examples and some open problems are given.

MSC:

68Q45 Formal languages and automata
11B83 Special sequences and polynomials
11B85 Automata sequences
16W60 Valuations, completions, formal power series and related constructions (associative rings and algebras)
68R15 Combinatorics on words

Citations:

Zbl 0742.11012

Software:

ALGOL 60
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

1’s-counting sequence: number of 1’s in binary expansion of n (or the binary weight of n).
Gould’s sequence: a(n) = Sum_{k=0..n} (binomial(n,k) mod 2); number of odd entries in row n of Pascal’s triangle (A007318); a(n) = 2^A000120(n).
Sorting numbers: maximal number of comparisons for sorting n elements by binary insertion.
Evil numbers: nonnegative integers with an even number of 1’s in their binary expansion.
Stern’s diatomic series (or Stern-Brocot sequence): a(0) = 0, a(1) = 1; for n > 0: a(2*n) = a(n), a(2*n+1) = a(n) + a(n+1).
a(0) = 0, a(1) = 1, a(2n) = a(n), a(2n+1) = a(n+1) - a(n).
a(n) = cost of minimal multiplication-cost addition chain for n.
Factor complexity (number of subwords of length n) of the Golay-Rudin-Shapiro binary word A020987.
Number of entries in n-th row of Pascal’s triangle not divisible by 3.
Number of entries in first n rows of Pascal’s triangle not divisible by 3.
Josephus problem: a(2*n) = 2*a(n)-1, a(2*n+1) = 2*a(n)+1.
Sorting numbers: number of comparisons in Batcher’s parallel sort.
Loxton-van der Poorten sequence: base-4 representation contains only -1, 0, +1.
Number of subwords of length n in infinite word generated by a -> aab, b -> b.
Length of longest chain of subgroups in S_n.
If 2n = Sum 2^e_i, a(n) = Sum e_i.
Distance to largest power of 2 less than or equal to n; write n in binary, change the first digit to zero, and convert back to decimal.
Partial sums of floor(log_2(k)) (= A000523(k)).
Alternating bit sum for n: replace 2^k with (-1)^k in binary expansion of n.
0 iff n is of the form 4^a*(8k+7), otherwise 1.
Number of positive integers <= n which are the sum of 3 squares.
If n = pqr...st in binary, a(n) = value of continuant [p,q,r,...,s,t].
1 iff n is of the form 4^m*(8k+7).
Numerator of the Reingold-Tarjan sequence, denominator=A072404.
Denominator of the Reingold-Tarjan sequence, numerator=A072403.
a(n) = L(n) + a(L(n)), where L(n) = n - 2^floor(log_2(n)) (A053645).
First differences of A006282.
Random Fibonacci tree defined with the pair(1,1).
a(2n) = a(n) + a(n+1) + n (n > 1), a(2n+1) = a(n) + a(n-1) + 1 (n >= 1) with a(0) = a(1) = 1 and a(2) = 2.

References:

[1] Allouche, J.-P., Somme des chiffres et transcendance, Bull. Soc. Math. France, 110, 279-285 (1982) · Zbl 0508.10022
[2] Allouche, J.-P., Suites infinies à répétitions bornées, Sém. de Théorie des Nombres de Bordeaux (1983-1984), Exposé no. 20 · Zbl 0548.68069
[3] Allouche, J.-P., Automates finis en théorie des nombres, Exposition Math., 5, 239-266 (1987) · Zbl 0641.10041
[4] Allouche, J.-P., Note sur un article de Sharif et Woodcock, Sém. de Théorie des Nombres de Bordeaux, 1, 163-187 (1989), \(2^e\) série · Zbl 0714.12006
[5] Allouche, J.-P.; Morton, P.; Shallit, J., Pattern spectra, substring enumeration, and automatic sequences, Theoret. Comput. Sci., 94, 161-174 (1992) · Zbl 0753.11012
[6] Babbage, C., Observations on the application of machinery to the computation of mathematical tables, Memoirs of the Astronomical Society. (Babbage’s Calculating Engines (1982), Tomash Publishers: Tomash Publishers Los Angeles), 1, 311-314 (1822)
[7] Bellman, R.; Shapiro, H. N., On a problem in additive number theory, Ann. Math., 49, 333-340 (1948) · Zbl 0031.25401
[8] Berstel, J.; Reutenauer, C., Rational Series and Their Languages (1988), Springer: Springer Berlin · Zbl 0668.68005
[9] Blanchard, A.; Mendès France, M., Symétrie et transcendance, Bull. Sci. Math., 106, 325-335 (1982) · Zbl 0492.10027
[10] Brlek, S., Enumeration of factors in the Thue-Morse word, Discrete Appl. Math., 24, 83-96 (1989) · Zbl 0683.20045
[11] de Bruijn, N. G., On Mahler’s partition problem, Indag. Math., 10, 210-220 (1948) · Zbl 0030.34502
[12] de Bruijn, N. G., Some direct decompositions of the set of integers, Math. Tables Aids Comput., 18, 537-546 (1964) · Zbl 0126.27903
[13] Cheo, P.; Yien, S., A problem on the \(k\)-adic representations of positive integers, Acta. Math. Sinica, 5, 433-438 (1955) · Zbl 0068.26603
[14] Choffrut, C.; Schützenberger, M. P., Counting with rational functions, Theoret. Comput. Sci., 58, 81-101 (1988) · Zbl 0664.68057
[15] Christol, G.; Kamae, T.; Mendès France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. France, 108, 401-419 (1980) · Zbl 0472.10035
[16] Clements, G.; Lindström, B., A sequence of (± 1)-determinants with large values, Proc. Amer. Math. Soc., 16, 548-550 (1965) · Zbl 0138.01101
[17] Cobham, A., On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory, 3, 186-192 (1969) · Zbl 0179.02501
[18] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[19] Coquet, J., A summation formula related to the binary digits, Invent. Math., 73, 107-115 (1983) · Zbl 0528.10006
[20] van der Corput, J. C., Verteilungsfunktionen, Proc. Ned. Akad. v. Wet., 38, 813-821 (1935) · JFM 61.0202.08
[21] Davis, M., Hilbert’s tenth problem is unsolvable, Amer. Math. Monthly, 80, 233-269 (1973) · Zbl 0277.02008
[22] Dekking, M.; Mendès France, M.; van der Poorten, A., FOLDS!, Math. Intelligencer. Math. Intelligencer, Math. Intelligencer. Math. Intelligencer. Math. Intelligencer, Math. Intelligencer, Math. Intelligencer. Math. Intelligencer. Math. Intelligencer, Math. Intelligencer. Math. Intelligencer. Math. Intelligencer, Math. Intelligencer, Math. Intelligencer, Math. Intelligencer, 5, 5-195 (1983), Errata in
[23] Dijkstra, E. W., Selected Writings on Computing: a Personal Perspective (1982), Springer: Springer New York · Zbl 0497.68001
[24] Dubbey, J. M., The Mathematical Work of Charles Babbage (1978), Cambridge University Press · Zbl 0376.01002
[25] P. Dumas, Suite automatiques à valeurs dans un anneau commutatif, preprint.; P. Dumas, Suite automatiques à valeurs dans un anneau commutatif, preprint.
[26] Eilenberg, S., Automata, Languages, and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[27] Erdös, P.; Turán, P., On some sequences of integers, J. London Math. Soc., 11, 261-264 (1936) · JFM 62.1126.01
[28] Fine, N. J., Binomial coefficients modulo a prime, Amer. Math. Monthly, 54, 589-592 (1947) · Zbl 0030.11102
[29] Flajolet, P.; Ramshaw, L., A note on Gray code and odd-even merge, SIAM J. Comput., 9, 142-158 (1980) · Zbl 0447.68083
[30] Gilbert, E., Gray codes and paths on the \(n\)-cube, Bell Sys. Tech. J., 37, 815-826 (1958)
[31] Ginsburg, S.; Spanier, E. H., Bounded ALGOL-like languages, Trans. Amer. Math. Soc., 113, 333-368 (1964) · Zbl 0142.24803
[32] Glaisher, J. W.L., On the residue of a binomial-theorem coefficient with respect to a prime modulus, Quart. J. Pure Appl. Math., 30, 150-156 (1899) · JFM 29.0152.03
[33] Gould, H. W., Exponential binomial coefficients series, (Technical Report 4 (1961), Department of Mathematics, W. Virginia Univ.) · Zbl 0229.05018
[34] Graham, R.; Knuth, D.; Patashnik, O., Concrete Mathematics (1989), Addison-Wesley: Addison-Wesley Reading, MA
[35] Graham, R.; Yao, A.; Yao, F., Addition chains with multiplicative cost, Discrete. Math., 23, 115-119 (1978) · Zbl 0391.10039
[36] F. Gray, U.S. patent 2,632,058, March 17, 1953 (Filed November 13, 1947).; F. Gray, U.S. patent 2,632,058, March 17, 1953 (Filed November 13, 1947).
[37] Guy, R. K., Unsolved Problems in Number Theory (1981), Springer: Springer Berlin · Zbl 0474.10001
[38] Halton, J. H., On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math., 2, 84-90 (1960) · Zbl 0090.34505
[39] Harrison, M., Lectures on Linear Sequential Machines (1969), Academic Press: Academic Press New York · Zbl 0212.34002
[40] Holter, N. S.; Lakhtakia, A.; Varadan, V. K.; Varadan, V. V.; Messier, R., On a new class of planar fractals: the Pascal-Sierpinski gaskets, J. Phys. A: Math. Gen., 19, 1753-1759 (1986) · Zbl 0617.58040
[41] 29th International Math Olympiad-Solutions, Math. Mag., 62, 212 (1989)
[42] Jacobs, K.; Keane, M., 0-1-Sequences of Toeplitz type, Z. Wahrscheinlichkeitstheorie verw. Geb., 13, 123-131 (1969) · Zbl 0195.52703
[43] Knuth, D. E., An almost linear recurrence, Fib. Quart, 4, 117-128 (1966) · Zbl 0144.27502
[44] Knuth, D. E., Sorting and Searching, (The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0777.68012
[45] Knuth, D. E., Fundamental Algorithms, (The Art of Computer Programming, Vol. 1 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0191.17903
[46] Lakhtakia, A.; Messier, R., Self-similar sequences and chaos from Gauss sums, Comput. & Graphics, 13, 59-62 (1989)
[47] Lakhtakia, A.; Messier, R.; Varadan, V. K.; Varadan, V. V., Fractal sequences derived from the self-similar extensions of the Sierpinski gasket, J. Phys. A: Math. Gen., 21, 1925-1928 (1988)
[48] Lang, S., Algebra (1971), Addison-Wesley: Addison-Wesley Reading, MA
[49] Lehmer, D. H.; Mahler, K.; van der Poorten, A. J., Integers with digits 0 or 1, Math. Comp., 46, 683-689 (1986) · Zbl 0589.10004
[50] Levitt, K. N.; Green, M. W.; Goldberg, J., A study of the data communication problems in a self-repairable multiprocessor, Proc. AFIPS Conf., 32, 515-527 (1968)
[51] Liardet, P., Automata and generalized Rudin-Shapiro sequences, (Sem. Salzburg Universität (1989), C.N.R.S.,: C.N.R.S., Marseille), Publication 23, U.R.A. #225 · Zbl 0763.11010
[52] Lipton, R.; Zalcstein, Y., Word problems solvable in logspace, J. ACM, 24, 522-526 (1977) · Zbl 0359.68049
[53] Loxton, J. H.; van der Poorten, A. J., An awful problem about integers in base four, Acta Arith., 49, 193-203 (1987) · Zbl 0636.10003
[54] Loxton, J. H.; van der Poorten, A. J., Arithmetic properties of automata: regular sequences, J. Reine Angew. Math., 392, 57-69 (1988) · Zbl 0656.10033
[55] de Luca, A.; Varricchio, S., Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci., 63, 333-348 (1989) · Zbl 0671.10050
[56] Mahler, K., On a special functional equation, J. London Math. Soc., 15, 115-123 (1940) · JFM 66.0563.02
[57] Mahler, K., On the generating function of the integers with amissing digit, J. Indian Math. Soc., 15, 33-40 (1951) · Zbl 0043.05301
[58] Mauduit, C., Substitutions et ensembles normaux, Habilitation (1989), Marseille
[59] Mendès France, M.; van der Poorten, A. J., From geometry to Euler identities, Theoret. Comput. Sci., 65, 213-220 (1989) · Zbl 0682.10026
[60] Mendès France, M.; Shallit, J., Wire bending, J. Combin. Theory, A, 50, 1-23 (1989) · Zbl 0663.10056
[61] Morton, P.; Mourant, W., Paper folding, digit patterns, and groups of arithmetic fractals, Proc. London Math. Soc., 59, 253-293 (1989) · Zbl 0694.10009
[62] Moser, L., An application of generating series, Math. Mag., 35, 37-38 (1962) · Zbl 0134.27305
[63] Newman, D. J., On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc., 21, 719-721 (1969) · Zbl 0194.35004
[64] Newman, D. J.; Slater, M., Binary digit distribution over naturally defined sequences, Trans. Amer. Math. Soc., 213, 71-78 (1975) · Zbl 0324.10053
[65] Osbaldestin, A. H.; Shiu, P., A correlated digital sum problem associated with sums of three squares, Bull. London Math. Soc., 21, 369-374 (1989) · Zbl 0647.10011
[66] Prodinger, H., Non-repetitive sequences and Gray code, Discrete Math., 43, 113-116 (1983) · Zbl 0492.68058
[67] Rauzy, G., Suites à termes dans un alphabet fini, Sém. de Théorie des Nombres de Bordeaux, 25.01-25.16 (1982-1983), \(2^e\) série
[68] Reingold, E. M.; Tarjan, R. E., On a greedy heuristic for complete matching, SIAM J. Comput., 10, 676-681 (1981) · Zbl 0468.68072
[69] Reznick, B., A new sequence with many properties, Abs. Amer. Math. Soc., 5, 16 (1984)
[70] Reznick, B., Some extremal problems for continued fractions, Illinois J. Math., 29, 261-279 (1985) · Zbl 0562.10002
[71] Reznick, B., Some binary partition functions, (Berndt, B. C.; Diamond, H. G.; Halberstam, H.; Hildebrand, A., Analytic Number Theory, Proceedings of a Conference in Honor of Paul T. Bateman (1990), Birkhäuser: Birkhäuser Boston), 451-477
[72] de Rham, G., Un peu de mathématiques à propos d’une courbe plane, Elem. Math.. Elem. Math., Elem. Math., 2, 89-97 (1947)
[73] Salomaa, A.; Soittola, M., Automata-theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039
[74] Salon, O., Quelles tuiles! (Pavages apériodiques du plan et automates bidimensionnels), Sém. de Théorie des Nombres de Bordeaux, 1, 2, 1-25 (1989) · Zbl 0726.11020
[75] Schützenberger, M. P., On the definition of a family of automata, Inform. and Control, 4, 245-270 (1961) · Zbl 0104.00702
[76] Shiu, P., Counting sums of three squares, Bull. London Math. Soc., 20, 203-208 (1988) · Zbl 0616.10037
[77] Sloane, N. J.A., A Handbook of Integer Sequences (1973), Academic Press: Academic Press New York · Zbl 0286.10001
[78] Stern, M. A., Über eine zahlentheoretische Funktion, J. Reine Angew. Math., 55, 193-220 (1858) · ERAM 055.1457cj
[79] Strauss, N.; Shallit, J., Advanced Problem 6625, Amer. Math. Monthly, 97, 252 (1990)
[80] Tapsoba, T., Complexité de suites automatiques, (Thèse de troisième cycle (1987), Université d’Aix-Marseille II) · Zbl 0815.11015
[81] Wagstaff, S. S., The Schnirelmann density of the sums of three squares, Proc. Amer. Math. Soc., 52, 1-7 (1975) · Zbl 0309.10021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.