Hi, my name is Filip Mazowiecki, and this is joint work with Mikaia Kadiya, Kishar Papperman, Mihai Pilipchuk, and Zorro Senizar. I will present our work on polynomial recursive

sequences. Here's the outline of the talk. It's divided into three parts. First, I will give some basic definitions about recursive sequences. Then I will show the main proof of the paper. And in the end, I will discuss the applications of the results in the theory of weighted automata. So the most famous recursive sequence is the Fibonacci sequence, where you fix the

first two elements of 0 and 1. And then every other element of the sequence is defined as the sum of two previous elements. Another famous recursive sequence are the Catalan numbers, where before you fixed the first two elements, and then each other element is defined as the sum on the right, which is quite different from the sum in the Fibonacci

sequence. Now, Catalan numbers are known for many combinatorial interpretations. That's why they're a very famous example. And in general, one of the classes I will be interested in in this talk are linear recursive sequences over rational numbers, where the definition is as follows. You fix some k,

and for this k, you fix the first k elements of the sequence. These are the u0 to uk minus 1. And then you fix k rational numbers. These are the numbers a1 to ak. And now every element of the sequence, which is not the first k element, is defined by

the sum on top using the coefficients of a1 to ak and using the previous k elements of the sequence. So for example, if you want to define the Fibonacci sequence like this, then k equals 2, a1 and a2 are 1, and the first two elements of the sequence are defined as 0 and 1.

Another example are Catalan numbers, because if you remember from the previous slide, the sum was quite different. And in fact, we will see that it's impossible to define Catalan numbers using this definition later in the talk.

So here's the definition. We say that a sequence is linear recursive if there exists a linear form L, like here, such that every element in the sequence un plus k is defined by this linear form. So what I mean by this, it's just a reformulation of this definition, that for example, the Fibonacci sequence is defined by the linear form that

sums x1 and x2. Later, like I said, we will see that Catalan numbers do not admit such a linear form. So the first question you might ask yourself, is it possible to restrict the recursion

depth of these sequences to 1? The answer is no, because then as you can see, by definition, such sequences are only geometric sequences. And for example, the Fibonacci sequence is not a geometric sequence. So in order to have a definition which has recursion depth only 1, we will consider a

different definition, which is a system of linear sequences. So as an example, consider again the Fibonacci sequence, where we will use one extra sequence, gn. And the idea is that this sequence intuitively is the sequence of Fibonacci, but shifted by

1. So now we fix the initial values of f and g, and these are the first two elements of the Fibonacci sequence. And then the recursion of f and g is defined as follows, that since g is shifted, the sequence f shifted by 1, then f is defined by g. And

the recursion for the sequence g follows from the definition of the Fibonacci sequence. Now in general, if we want to define a sequence using a system of linear sequences, then we do as follows. We have some k sequences, we fix the initial value of all of them, and then we have a linear

form to update each element, which is not the first element, to use the previous elements, but you can use any of the previous elements of the k sequences. And then we define the sequence which is defined by this system as the first sequence in this system. So it is well known that

these two definitions of linear recursive sequences and sequences definable by linear systems are equivalent. So one implication is obvious. It follows essentially from the way I presented the Fibonacci sequence in the previous slide, and you can easily show this for any sequence defined as a linear recursive sequence. The other implication is not obvious,

I will not present it during this talk, but if you don't know this implication, then you can consider an example. It's fun to try to prove that the sequence a n equals n squared can be defined as a linear recursive sequence. So on the bottom, you can see that this sequence can

be defined as a system of linear sequences where you need two extra sequences, pn equals n, and cn which is constantly equal to 1. Now let me define a second class of sequences, which is called polynomial recursive sequences, where the main example is the sequence a n, which is n factorial. And as you may know, to define the sequence, we need one extra sequence

bn, which is n plus 1. And then whenever you want to update a n, you just need to multiply the previous value by n. And this is how you get n factorial. So first, let me remark that

this sequence n factorial is asymptotically 2 to the power n log n. And if you know linear recursive sequences, then you might know that asymptotically, they're bounded by a constant to the power n. So we know that n factorial is not a linear recursive sequence. So this is not in the class that was defined before. So in general, the definition is as follows.

It's very similar to the definition of linear recursive sequences. We say that a sequence is a polynomial recursive sequence, if you can define it by a system of sequences like before. But now instead of having linear updates, we have polynomials to update them. So we

fix the initial values as before. But then each sequence is defined by polynomials on the previous elements of the sequences. And from this definition, it's quite clear that this generalizes the previous definition of linear recursive sequences.

So let's consider more examples. So the first one was in the previous slide, n factorial. A second example is a sequence where you start with 2. And every time afterwards, the new element is a square of 2, the previous elements. This way, you can define the sequence 2 to power 2 to power n. And in fact, one can prove that if a sequence is

polynomially recursive, then in some way, this is the best you can do. So you can prove that asymptotically, these sequences are at most double exponential. Another example, which I will not show here, but it's homework, is that you can define a

sequence of Fibonacci sequences where the index is the n-th element of the Fibonacci sequence, so a composition of Fibonacci sequences. Another example is that you cannot define Catalan numbers as polynomial recursive sequences, which is what I will prove on this slide. So first, let me just note that Catalan numbers

can be equivalently defined as here shown. So there is no asymptotic argument, because we saw that polynomially recursive sequences or even linearly recursive sequences can define constants to power n. So here's the proof. The proof will be over integers.

So I will prove first that if a sequence is polynomially recursive, then if you look at its values modulo some number p, then this will give us an ultimately periodic sequence.

Here's the proof. So the proof is short. The idea is that since p is finite, then if you look at all elements in this system of sequences, u1, u2, up to uk, and you look at the n-th element, there is k of them. And for each of them, there is at most p possible

values. There are p to power k possible values in total. And since each such evaluation deterministically defines the next element in the sequence, at some point, we will have a loop. And this loop exactly means that the sequence is ultimately periodic. So the second step of

the proof is just that it's well known that Catalan numbers are odd if and only if the index n is of the form 2 to power m minus 1 for some number m. So if in the first step you take p equal 2, you will get a contradiction. Now the proof of a rational

number is more technical, and you can find it in the paper. OK. So now, if you remember, I gave two definitions for linear recursive sequences. And the natural question is whether for polynomial recursive sequences, you can do something similar. So you could try to define sequences using just one polynomial,

but the depth of the recursion would be bigger than 1, like any k. So the answer is that this is a fragment of polynomial recursive sequences. You can show that sequences defined like this also can be defined by a system of sequences. But it's

not equal. You can prove that, for example, the sequence in factorial cannot be defined like this. So it's a strict subclass. But let us notice the following thing. Let's consider the sequence in factorial. And let's take the quotient of two consecutive elements. And

then, as you know, if you do it for the two consecutive elements, then this differs by 1. Now, from this equality, you can write down a polynomial p, as written here,

such that from the equality in pink, you can see that if you plug in any element un, un1 plus 1, and un plus 2 of the sequence, then this polynomial will always evaluate to 0. This follows from this equality in pink. Now, this might seem like a contradiction with the

proposition in the middle. But the difference is that in this polynomial, the coefficient which corresponds to the biggest element of the sequence, un plus k, is nonlinear. So as you can see here, x3 is multiplied by x1. And we will use this here. We will say that a

sequence un admits a canceling polynomial if it has exactly that property from the previous slide. This polynomial p has to be non-zero, and it has k variables. And if you take any k consecutive elements of the sequence, and you evaluate this polynomial in these elements,

then you will always get 0. So one of the lemmas we prove in the paper is that if a sequence is polynomial recursive, then it does admit a canceling polynomial. Now, let me just remark that the converse is not true. And this can be seen very easily. So you can define

a polynomial with just one variable, x1. And it's x1 squared minus 1. And it's very easy to see that this polynomial is canceling for any sequence over the domain of minus 1 and 1. And in particular, such sequences don't have to be ultimately periodic. So as you can see,

again, this is not a characterization. This is only an implication. OK, now I'm ready to move to the second part of the talk, where I will give the main result that the sequence n to power n is not polynomially recursive. And before I go into the

details of the proof, let me just try to convince you that this is not a trivial problem, or at least we failed to prove it in an easy way. So first, you might think that maybe you could have some asymptotic argument that n factorial is not polynomially recursive.

Sorry, n to the n. Well, if you remember, then the sequence n factorial is polynomially recursive. And in fact, it's not hard to prove that 3 to power n factorial is also polynomially recursive. But then using steering approximations, you can see that n to the n is in between of these two sequences. And in fact, since we're over

the rational numbers, you can make these approximations more tight. So it's not clear how you would prove this using asymptotic arguments. Now, a second attempt would be to reuse the ideas of the proof and prove that Catalan numbers are not polynomially recursive.

Namely, one could try to use the property that polynomially recursive sequences are ultimately periodic. But again, if you try to use this and you take the n to the n of the values of the sequence n to the n modulo any prime number p,

you can prove that it's actually periodic with the period p times p minus 1. It follows from the little theorem. So the technique we will use to prove that n to the n is not polynomially recursive is using these canceling polynomials. And I will give

the proof in the next two slides. It will be by contradiction. So we assume that n to the n is polynomially recursive. And then from the lemma in the previous slide, we know that there exists a canceling polynomial.

And it's quite technical to do this. But you can rewrite this polynomial in such a way that this polynomial, if you plug it in into n to the n and k consecutive elements, then you will get a sum of polynomials pi multiplied by polynomials qi of n to power n.

And since it's a canceling polynomial, then this sum is equal to 0. Now, an important claim in the proof is that if you look at the sum and you take these values, modulus and prime number p, then you have the following claim that you can

replace the n in the sum in the basis with a number a and then the exponents with a number b such that a is any integer and b is any positive integer. Now, what is important in this claim is that before, we had just one n everywhere. And here, you can choose any a and any b,

which are completely independent, which we will use in the proof on the next slide. I will not prove this claim, but you can find it in the paper. So let me just summarize what we know to prove the contradiction. So we have this sum.

We know that it's equal to 0 modulo any prime number p. And something that I did not emphasize, but it's going to be important, is that these polynomials pi and qi are non-zero, and the polynomials qi are otherwise different. So let's fix some a and p,

and let's write down this sum for all b from 1 to l. You get l equations for each one for 1b. And in each equation, you have l elements of the sum. So I think I didn't mention this, but this l comes from the sum in the corner here. So we have l sums, and in each sum,

we have l elements of this sum. So you can write this down as a square matrix, which will look like this. Now, what is important about this matrix is that if you look at each column, it defines a geometric sequence. Now, such matrices are called square

Vandermonde matrices. And the property that we will use in this proof is that if you compute the determinant of such a matrix, then you get a non-zero polynomial in A, if and only if these polynomials qi were otherwise different and non-zero, which is exactly what we assumed, and it's highlighted in blue. So we know that this determinant is a non-zero

polynomial. But then this means that if we take the prime number p big enough, then this polynomial determinant of M of A will be non-zero for most A's, which means that this matrix will

be invertible for most A's. But if this matrix is invertible for most A's, then the only way that this equation is true is if this vector of p i's is equal to 0 for most of A's. But again, this gives us a contradiction because, as you can see, it's highlighted in blue that

these polynomials p i, they're non-zero. So if we take the prime number p big enough, then the number of zeros for each polynomial will be bounded by the degree of the polynomial. And it's impossible that these p i's are almost always 0. So this is the end of the proof.

Let me move to the last part of the talk. I will discuss the applications of this result and the theory of weighted automata. And actually, I will not define weighted automata. I will just say the following, that a weighted automaton over the semiring of rational numbers,

it's a function from the set of words to rational numbers. Now what's important for this talk is that if the size of the alphabet is 1, then you can think that this function assigns an element, a rational number to each word.

But now each word can be identified with its length. So you can think of this as a function from natural numbers to rational numbers, which you can also call them sequences. And now it's quite known, or you can just observe this almost by definition,

that then weighted automata and linear recursive sequences are the same classes of sequences if you have this assumption about the one-letter alphabet. So there's another class which is an extension of weighted automata called cost register automata.

And again, if you similarly assume that you have a one-letter alphabet, then the second class corresponds to the main class of the stack, the polynomial recursive sequences. Now just as a side mark, I would like to mention that these cost register automata,

they appear in many places, and particularly in papers about pushdown automata, papers about weighted automata, and papers about vector addition systems. So in this slide, I would like to discuss the application of our result. So you can see that

you have this class of weighted automata linear recursive sequences. And there is a nonlinear extension of these cost register automata. But this is not the only nonlinear extension of weighted automata. There is another one called weighted context re-grammars, which is usually studied in the context of learning. And there is also one more

called weighted monadic second-order logic, which is studied in the context of logical definitions of weighted functions. So as it happens, the two functions that we looked at in this paper, the Catalan numbers and n to the n, they belong to these two other

classes. So as a corollary of our theorem, we get that cost register automata are different nonlinear extensions of weighted automata than these two other classes. OK, so now let me just conclude the talk. In this paper, we investigated polynomial

recursive sequences. And the main results were that Catalan numbers and n to the n are not polynomial recursive. And there are some open problems left. Let me mention one, which is close to the previous slide. So from the previous slide,

it follows that weighted MSO is not contained in cost register automata. But one might ask whether the other inclusion is true. And a candidate example of that we think that would prove that there is no such inclusion is that you can look at the definition of

these composed Fibonacci sequences, which you can prove that they're polynomial recursive. But we conjecture that this cannot be defined by weighted MSO. So that's all. Thank you for your attention.