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

(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