We prove that the map sending A to A^n, where A is a k×k matrix with non-negative integer coefficients, is definable by a bounded arithmetic formula. As a consequence functions obtained by linear recurrence relations with non-negative integer coefficients are definable by bounded formulas. These include the Fibonacci sequence as well as functions of polynomial growth rate. It turns out that it is impossible to mimic the well known definition of the exponential map by bounded formulas. A combinatorial approach based on counting the number of solutions of linear diophantine equations is instead used.
Linear recurrence relations are Delta_0-definable
BERARDUCCI, ALESSANDRO;
1999-01-01
Abstract
We prove that the map sending A to A^n, where A is a k×k matrix with non-negative integer coefficients, is definable by a bounded arithmetic formula. As a consequence functions obtained by linear recurrence relations with non-negative integer coefficients are definable by bounded formulas. These include the Fibonacci sequence as well as functions of polynomial growth rate. It turns out that it is impossible to mimic the well known definition of the exponential map by bounded formulas. A combinatorial approach based on counting the number of solutions of linear diophantine equations is instead used.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.