@article{FISCHER2003121,
    Abstract = {Let C be a class of relational structures. We denote by fC(n) the number of structures in C over the labeled set {0,{\ldots},n−1}. For any C definable in monadic second-order logic with unary and binary relation symbols only, E. Specker and C. Blatter showed that for every m∈N, the function fC satisfies a linear recurrence relation modulo m, and hence it is ultimately periodic modulo m. The case of ternary relation symbols, and more generally of arity k symbols for k⩾3, was left open. In this paper we show that for every m there is a class of structures Cm, which is definable even in first-order logic with one quaternary (arity four) relation symbol, such that fCm is not ultimately periodic modulo m. This shows that the Specker--Blatter Theorem does not hold for quaternary relations, leaving only the ternary case open.},
    Author = {Fischer, Eldar},
    File = {The Specker–Blatter theorem does not hold for quaternary relations - 1-s2.0-S009731650300075X-main.pdf},
    ISSN = {0097-3165},
    Journal = {Journal of Combinatorial Theory, Series A},
    Number = {1},
    Pages = {121-136},
    Title = {The Specker--Blatter theorem does not hold for quaternary relations},
    URL = {https://www.sciencedirect.com/science/article/pii/S009731650300075X},
    Volume = {103},
    Year = {2003},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S009731650300075X},
    bdsk-url-2 = {https://doi.org/10.1016/S0097-3165(03)00075-X},
    date-added = {2023-08-26 08:37:40 +0200},
    date-modified = {2023-08-26 08:37:40 +0200},
    doi = {10.1016/S0097-3165(03)00075-X}
}

@article{FISCHER2003121, Abstract = {Let C be a class of relational structures. We denote by fC(n) the number of structures in C over the labeled set {0,{\ldots},n−1}. For any C definable in monadic second-order logic with unary and binary relation symbols only, E. Specker and C. Blatter showed that for every m∈N, the function fC satisfies a linear recurrence relation modulo m, and hence it is ultimately periodic modulo m. The case of ternary relation symbols, and more generally of arity k symbols for k⩾3, was left open. In this paper we show that for every m there is a class of structures Cm, which is definable even in first-order logic with one quaternary (arity four) relation symbol, such that fCm is not ultimately periodic modulo m. This shows that the Specker--Blatter Theorem does not hold for quaternary relations, leaving only the ternary case open.}, Author = {Fischer, Eldar}, File = {The Specker–Blatter theorem does not hold for quaternary relations - 1-s2.0-S009731650300075X-main.pdf}, ISSN = {0097-3165}, Journal = {Journal of Combinatorial Theory, Series A}, Number = {1}, Pages = {121-136}, Title = {The Specker--Blatter theorem does not hold for quaternary relations}, URL = {https://www.sciencedirect.com/science/article/pii/S009731650300075X}, Volume = {103}, Year = {2003}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S009731650300075X}, bdsk-url-2 = {https://doi.org/10.1016/S0097-3165(03)00075-X}, date-added = {2023-08-26 08:37:40 +0200}, date-modified = {2023-08-26 08:37:40 +0200}, doi = {10.1016/S0097-3165(03)00075-X} }