User:Charles R Greathouse IV/Properties

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

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 are those with gcd(a(m), a(n)) = a(gcd(m, n)).
• Ward's property C is possessed by (divisibility) sequences with an auxiliary sequence v(n) such that $a(n)=\prod _{d|n}v(d).$
• Rigid divisibility sequences 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 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\neq n.$
• Superrigid divisibility sequences 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.
• D-finite sequences are defined by a recurrence which is polynomial in the term number. They are a strict superset of the C-finite sequences. It has been estimated that over 25% of the sequences in the OEIS are D-finite. These sequences are also called holonomic or P-recursive.
• Multiplicity sequences are those with lcm(a(m), a(n)) = a(lcm(m, n)).
• Quasi-multiplicative sequences are those for which a(m)a(n) = a(mn)a(1) when m and n are coprime. When a(1) = 1 these sequences are multiplicative.
• Hypo-multiplicative 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 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.)

There are also nice closure properties. Some sequences are closed under multiplication, for example. Related is the notion of a primitive sequence, which is formed from the least elements of such a sequence by which the others can be filled in from the relevant closure property. For example, the primitive abundant numbers A091191 are those abundant numbers which have only non-abundant divisors. The abundant numbers can be reconstituted from this sequence by their closure property (multiplication by arbitrary positive integers).

Certain combinatorial properties would be nice:

• Complete sequences
• Additive bases and their order
• Eventually-complete sequences (finitely many exceptions)—note that this is sometimes called merely "complete"
• 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 10-automatic, and a number of sequences (primes, 2^n-1, etc.) are 2-automatic, essentially regular when expressed in the appropriate base. 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 who call such sets asymptotically equal. Examples in the OEIS:

• A000027, A001477, A003995, A003997, A003999, A004434, A008319, A009005, A009056, A011760, A020705, A020710, A020715, A020719, A020722, A020723, A020725, A023443, A023444, A023445, A023446, A023447, A023448, A023449, A023450, A023451, A023452, A023453, A023454, A023455, A023456, A023457, A025051, A028253, A028310, A055495, A061094, A065475, A075567, A078137, A078907, A087156, A097950, A099135, A099136, A102815, A107820, A114637, A123122, A124867, A133043, A143616, A157319, A160811, A171463, A171526, A171891, A171892, A171893, A171950, A174724, A178915, A181440, A190482, A194768, A194769 are the natural numbers after some point
• A010727, A035613, A021040, A186684 are all 7 after some point
• A000040, A004139, A006005, A008578, A045319, A045344, A046022, A051948, A065091, A066050, A078138, A083249, A090417, A108719, A113029, A116974, A137922, A140461, A140475, A158611, A160656, A161346, A161428, A161839, A162786, A162788, A162789, A162790, A162792, A168546, A171525, A171577, A173135, A175787, A182986, A215848 contain all sufficiently large primes (and finitely many nonprimes)
• A000926, A000769, A001228, A001272, A002267, A005848, ... contain no members after a certain point

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