4 E. FISCHER, T. KOTEK, AND J.A. MAKOWSKY (ii) Every Specker sequence a(n) is computable, and in fact it is in the count- ing class · PH, [49], where PH is the polynomial hierarchy and the input n is measured in unary presentation. Hence a(n) is computable in exponential time, and using polynomial space. (iii) The set of Specker sequences is closed under the point-wise operations of addition and multiplication. The same holds for MSOL-Specker se- quences. We shall discuss examples of sequences a(n) which have a combinatorial inter- pretation in great detail in Part 2. Among them we find the counting functions for trees, graphs, planar graphs, binomial coeﬃcients, factorials, and many more. The reader may want to consult the The On-Line Encyclopedia of Integer Sequences (OEIS) [1] which contains close to 200 000 integer sequences studied in the litera- ture. The non-monotonic sequence a(n) beginning with 1, 1, 1, 2, 5, 4, 7, 6, 7, 9, 11, 10, 13, 13, 13, 14, 17, 16, 19, 18, 19, 21, 23, 22, 25, 25, 25, 26, 29, 28, 31, 30, 31, 33, 35, 34, 37, 37, 37, 38, 41, (A085801) 23, 22, 25, 25, 25, 26, 29, 28, 31, 30, 31, 33, 35, 34, 37, 37, 37, 38, 41, 40, 43, 42, 43, 45, 47, 46, 49, 49, 49, 50, 53, 52, 55, 54, 55, 57, 59, 58, . . . appears there as Sequence A085801 which has an ordered combinatorial interpreta- tion as the maximum number of nonattacking queens on an (n × n) toroidal board. A more theoretical source is the erudite monograph [32]. To the best of our knowledge no systematic study of sequences a(n) which have a combinatorial interpretation has been undertaken so far. Notable exceptions are the cases where K is a graph property which is hereditary (closed under induced subgraphs) or monotone (closed under subgraphs), cf. [72, 5, 6, 4]. Problem 1. (i) Characterize the sequences of integers which have (pure) combinatorial interpretations under various restrictions imposed on K. What are the additional restrictions on the counting function besides those listed in Proposition 1.1? (ii) Characterize the L-Specker sequences for various sublogics of SOL. In this paper we investigate suﬃcient conditions for Specker sequences to satisfy linear recurrence relations. We also study the converse question: For a given class of linear recurrence relations REC, can we find a family of logical interpretations I such that every sequence in REC has a logical interpretation in I? 2. Linear recurrences We are in particular interested in linear recurrence relations which may hold over Z or Zm. Definition 2.1 (Recurrence relations). Given a sequence a(n) of integers we say a(n) is 4

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.