This site is supported by donations to The OEIS Foundation.

User:Charles R Greathouse IV/Properties

From OeisWiki

Jump to: navigation, search

There are many useful properties that sequences can possess, as well as equivalence classes into which sequences can be grouped.

Contents

Sequence properties

This chart shows relationships between some common (and some less-common) properties. To wit:

  • Constant sequences have all the same term. They are (trivially) closed under pointwise addition and multiplication, but not under Dirichlet convolution.
  • Eventually constant sequences are constant sequences with some finite prefix. More generally, eventually foo sequences are foo sequences together with some finite prefix of zero or more terms.
  • Polynomials
  • Periodic sequences repeat some finite initial segment. They are closed under pointwise addition and multiplication (with period dividing the lcm of the periods), of which scalar multiplication is a special case. They are not closed under Dirichlet multiplication.
  • Quasipolynomials are sequences with an order m > 0 such that a(k), a(m+k), a(2m+k), ... is polynomial for every k. These generalize polynomials (for which m = 1) and periodic sequences (for which all polynomials are constant). They are closed under pointwise addition and multiplication (with period dividing the lcm of the orders), of which scalar multiplication is a special case. They are not closed under Dirichlet convolution.
  • Divisibility sequences are those with a(n) | a(mn). They are closed under pointwise multiplication (and hence scalar multiplication) but not under either pointwise addition or Dirichlet convolution.
  • Strong divisibility sequences[1] are those with gcd(a(m), a(n)) = a(gcd(m, n)).
  • Ward's property C[2][3] is possessed by (divisibility) sequences with an auxiliary sequence v(n) such that
a(n) = v(d).
d | n

  • Rigid divisibility sequences[4] are strong divisibility sequences with nonzero terms such that if a prime \scriptstyle p^e\parallel a(n) then \scriptstyle p^e\parallel a(m) whenever \scriptstyle p\mid a(m). Bliss, Fulan, Lovett, & Sommars[3] give an alternate characterization in terms of Ward's property C: \scriptstyle\prod_{d|n}v(d) is a rigid divisibility sequence if and only if \scriptstyle\gcd(v(m),v(n))=1 for all \scriptstyle m\ne n.
  • Superrigid divisibility sequences[4] are strong divisibility sequences with nonzero terms such that if a prime \scriptstyle p^e\parallel a(n) then \scriptstyle a(i)\equiv a(j)\pmod{p^{e+1}} whenever \scriptstyle i\equiv j\pmod n. Of course, superrigid divisibility sequences are rigid divisibility sequences. Rice gives examples of a class of polynomial recurrences which are superrigid divisibility sequences.
  • Geometric sequences are those in which the ratio between consecutive terms is constant; these are obviously also examples of sequences for which consecutive terms divide each other, which in turn are all divisibility sequences.
  • Completely multiplicative sequences are those for which a(mn) = a(m)a(n); they are both multiplicative (which requires that the relation hold only when m and n are coprime) and divisibility sequences with Ward's property C.
  • Strongly multiplicative sequences are multiplicative sequences where a(p^e) = a(p) for each e > 1. Like completely multiplicative sequences these have Ward's property C.
  • Linear recurrence relations are sequences with rational generating functions. They include (eventually) quasipolynomials, geometric sequences, and others. Zeilberger calls these C-finite sequences.
  • Multiplicity[5] sequences are those with lcm(a(m), a(n)) = a(lcm(m, n)).
  • Quasi-multiplicative[6][7][8] sequences are those for which a(m)a(n) = a(mn)a(1). When a(1) = 1 these sequences are multiplicative.
  • Hypo-multiplicative[6] sequences are a matrix-based extension of quasi-multiplicative sequences. Any sequence which can be represented as a linear combination of (quasi-)multiplicative sequences is hypo-multiplicative; the reverse implication has been neither proven nor disproven to my knowledge.
  • Semi-multiplicative[9][8] are sequences in which every nth term forms a quasi-multiplicative sequence and the others are 0.
  • Totient functions, in a general sense, are functions which are the convolution of a completely multiplicative function and the Dirichlet inverse of a completely multiplicative function. Alternatively, these are multiplicative functions for which \scriptstyle a(p), a(p^2), a(p^3), \ldots is a geometric series for each prime p. Consequently all strongly multiplicative and completely multiplicative sequences are also totient functions, and all integer totient functions are divisibility sequences. Examples include Euler's totient function A000010, the Möbius function A008683, the Dedekind psi function A001615, the Jordan functions (A007434, A059376, A059377, A059378, A069091, etc.), and the number of invertible 2 X 2 matrices mod n A000252.

Linear recurrence relations in which the recurrence and initial terms are known are automatically easy: new terms can be generated in time linear in their length, and arbitrary terms can be computed quickly (with O(1) precomputation time). But completely multiplicative (and hence multiplicative) sequences and strong divisibility (and hence divisibility) sequences, those with Ward's property C, and those for which a(n) | a(n+1) need not be easy—an obviously (?) sufficient condition is that arbitrary sequences can be encoded in them.

Other properties

There are many other properties that seem worth coding such as being monotone, additive, sub-/super-additive, or even "a rearrangement of \mathbb{N}". (For more on that last property, see "relationships between sequences" below.)

Certain combinatorial properties would be nice:

  • Complete sequences
  • Additive bases and their order
  • Eventually-complete sequences (finitely many exceptions)
  • Subcomplete sequences (sequences for which the sumset contains an infinite arithmetic progression)

Also it would be good to have information on the recognizability of sequences: A038772 is a regular language in decimal, and a number of sequences (primes, 2^n-1, etc.) are regular in unary. Similarly, when there are results showing that a particular sequence is/is not context-free, context-sensitive, or decidable/recursive this seems worth mentioning. (Almost all sequences in the OEIS should be at least recursively enumerable.)

Generating functions

Recurrence relations are one of the basic building blocks of integer sequences. For a current list of recurrence relations in the OEIS, see the recurrence section of the Index. I also have a list of quadratic polynomials in the OEIS.

It is often more convenient to think about these properties in terms of generating functions. For example, a sequence is periodic if and only if the denominator of its generating function divides some cyclotomic polynomial; this, in turn, can be decided by an algorithm of Bradford & Davenport (or any of a number of newer algorithms). If the denominator is given in lowest terms, the degree of the cyclotomic polynomial gives the period, so this solves #8 and #9. #3 is simply testing if the denominator is a power of (1-x), and finding the degree and leading terms is not difficult. (Other terms depend on the offset, but the leading term is invariant wrt offset changes.) #10 involves finding the roots of the denominator of the generating function, though more work is required if there are several roots of maximal absolute value.

Relationships between sequences

Categorizing sequences by cofinite equivalence (grouping sequences with finite Levenshtein distance; is there a standard name for this?) seems worthwhile. The analogous concept for sets is studied by Freedman & Sember[10] who call such sets asymptotically equal. Examples in the OEIS:

Open questions include A062972, A067126, A193339, A137669, A137670, A158008, A138889, A071621, A157996, A193461, A085265, A106317, A063884, A063904, A085265, A090461, A085267, A102352, A080693, A130696.

A broader classification would include sequences which differ only on sets of relative density 0, adding (for instance) A131645 to the equivalence class with A000040. A different classification (broader than the first, incomparable with the second) would allow linear transformations in addition to finite removals and additions, making [A005843] = [A005408].

Growth rates

Yet another classification scheme would group monotone sequences by their growth rates: polynomial, exponential, double-exponential, etc. Of course there are finer gradations: quadratic, linearithmic, etc.

Recurrence relations suggest many equivalence classes related to growth rate (or other characteristics):

  1. Sequences defined by some kind of recurrence
  2. Sequences defined by linear recurrence relations
  3. Polynomials
  4. Polynomials with a given leading term
  5. Polynomials of a given degree
  6. Polynomials with a given discriminant
  7. Quasipolynomials (sequences with an m such that a(m+k), a(2m+k), a(3m+k), ... is a polynomial for any k)
  8. Periodic sequences
  9. Periodic sequences with a given period
  10. Linear recurrence relations with exponential growth

References

  1. Clark Kimberling, Strong divisibility sequences with nonzero initial term, Fibonacci Quarterly 16:6 (1978), pp. 541-544.
  2. Morgan Ward, A note on divisibility sequences, Bull. Amer. Math. Soc. 45 (1939), pp. 334–336.
  3. 3.0 3.1 Nathan Bliss, Ben Fulan, Stephen Lovett, and Jeff Sommars, Strong divisibility, cyclotomic polynomials, and iterated polynomials, American Mathematical Monthly 120:6 (2013), pp. 519–536.
  4. 4.0 4.1 Brian Rice, Primitive prime divisors in polynomial arithmetic dynamics, Integers 7 (2007), A26, 16 pp.
  5. Piotr Zarzycki, On multiplicity sequences, Fibonacci Quarterly 35:1 (1997), pp. 9-10.
  6. 6.0 6.1 D. B. Lahiri, "Hypo-multiplicative number-theoretic functions", Aequationes Mathematicae 9:2-3 (1968), pp. 184-192.
  7. R. Sivaramakrishnan. Classical Theory of Arithmetic Functions. New York: Marcel Dekker, 1989
  8. 8.0 8.1 Pentti Haukkanen, On the Davison convolution of arithmetical functions, Canadian Mathematical Bulletin 32 (1989), pp. 467–473.
  9. David Rearick, "Semi-multiplicative functions", Duke Math. J. 33:1 (1966), pp. 49-53.
  10. A. R. Freedman and J. J. Sember, Densities and summability, Pacific J. Math. 95:2 (1981), pp. 293–305.
Personal tools