# `quasi'-periodic functions on N

Discussion in 'Math Research' started by Clemens Grabmayer, Jun 6, 2007.

1. ### Clemens GrabmayerGuest

In connection with work concerning the problem of deciding
productivity for (co-)recursive stream definitions
( cf. http://fspc282.few.vu.nl/productivity/ in the framework
of project "Infinity": http://fspc282.few.vu.nl/infinity/ )
we are interested in non-decreasing, and in particular,
"quasi-periodic" functions on the natural numbers (see definition below)
and have devised algorithms for computing their composition,
fixed points, as well as pointwise minima and maxima (on "eventually
periodic representations").

Also, we constructed an algorithm for computing the pointwise minimum
and maximum of all non-decrasing functions on the naturals that are
described by the edge-label sequences of infinite paths in finite,
directed graphs with natural number labeled edges (again see below for
more details).

Because in particular the last mentioned problem appears quite `natural'
to us, we wonder whether it has been studied, and possibly solved,
before. At the moment we are not aware of work in a similar direction,
but would like to learn about related work of others.

==============================================
The problem described in a little more formal detail
==============================================

By N we denote the natural numbers including zero.

There is an obvious bijective correspondence between non-decreasing
functions f: N -> N and infinite sequences over N: every such function f
is mapped to the sequence
[f(0), f(1) - f(0), f(2) - f(1), ..., f(i+1) - f(i),...] ;
conversely, every infinite sequence [a_0, a_1, a_2, ... ] in N
is mapped to the function on N with values a_0, a_0 + a_1,
a_0 + a_1 + a_2,... on the values 0,1,2, ... , respectively.

We call a non-decreasing function f on N "quasi-periodic" if it
corresponds to an eventually periodic infinite sequence on N.
Furthermore, we call an expression like [7,8,13,<7,12>] an eventual
periodic representation of the infinite sequence [7,8,13,7,12,7,12,...].

By a "rooted, directed graph with natural number labeled edges" we mean
a triple G = (V,E,r) consisting of a set V of vertices, a vertex r in V
called the "root", and a set E of natural number labeled edges, a subset
of V x N x V. Such a graph is finite if both of the sets V and E are
finite. For an edge e = (v,n,w) we call v the "source", w the "target",
and n the "label" of e.

We established the following lemma.

LEMMA. Let G = (V,E,r) be a finite, rooted, directed graph with natural
number labeled edges. Suppose that every vertex in G is the source of
at least one edge.
Let pmin, pmax: N -> N be defined as the pointwise minimum, and resp.
the pointwise maximum, of the set of non-decreasing functions on N that
correspond to edge-label sequences of infinite paths in G from the
root.(*)
Then pmin and pmax are quasi-periodic functions. Also, eventually
periodic representations of pmin and pmax can be computed
algorithmically from the input of G.

(*) Note that pmin and pmax themselves do not have to correspond to
edge-label sequences of infinite paths in G.

In the proof, which is not difficult, we use Higman's lemma to guarantee
the existence of loops of vertical `strips' of respectively lowest
points corresponding to vertex-visits in the graphs of all functions
on N that are generated by edge-label sequences of infinite paths in G.

==============================================

We would be very thankful for any indications or references to known
work dealing with this problem or similar ones.

Many thanks for any hints on this!

Joerg Endrullis
Clemens Grabmayer

Clemens Grabmayer, Jun 6, 2007