Linear functions: definition
Let's define a linear function as one expressible as an untyped λ-calculus term with the added restriction that no lambda argument can be used twice.
Linear functions: example
Many functions can be defined that way. For example, the successor of a binary string (interpreted as an integer) could be defined as (in Idris):
data Bit = O | I succ : List Bit -> List Bit succ bits = case bits of b :: bs => (case b of O => \ bs0 => I :: bs0 I => \ bs1 => O :: succ bs1) bs  => 
That function is linear in the above sense because it could be translated to the linear untyped λ-calculus. Pattern-matching could be expressed with Scott-encodings, and we avoided using the argument
bs twice with extra lambdas. Of course, recursion isn't expressible on that language (the Y-combinator and similar require non-linear arguments), so this definition is actually illegal, but, if we unrolled that function a few levels deep, we could still implement a
succ : Vect K Bit -> Vect K Bit, for bit lists of bounded depth
K. That's OK for the purpose of the question. Let's assume a fixed finite
K and abbreviate
Vect K Bit as
Given an arbitrary linear (in the sense above) function
f : Bits -> Bits, can the non-linear function
repeatF : Integer -> Bits -> Bits, which applies
n times to a bit-string, always be implemented in polynomial (or at least sub-exponential) time with respect to the size of the binary integer
n, and such that its code size grows at most polynomially when we increase
K? In other words, is the running time of computing $f^n(x)$ polynomial in $n$? I care only about the dependence on $n$; you can think of the size of $x$ as fixed.
For the example function defined above,
succ, the answer is yes. Of course, if we define
repeat(n,x) naively, then it'll take exponential time with respect to
repeatSucc : Integer -> List Bit -> List Bit repeatSucc 0 x = x repeatSucc n x = succ (repeatSucc (n - 1) x)
But by noticing that
repeatSucc n x is equivalent to addition, we can implement it in polynomial time and space with known addition algorithms. This makes me wonder whether something similar is true for all functions
f defined in the style above (or, of course, how we can prove that's not the case).
I'm analyzing the complexity of
repeatF(n, x) with respect to
n, which is a binary non-negative integer and could be potentially infinite. The input
x has constant size, but that is irrelevant, it is just the initial state of the iteration. You can't build a finite size lookup table for a potentially infinite argument. Even if you could, the size of
repeatF is limited by a polynomial function of the constant depth
K, so you can't fit a lookup table for the entire image. I'm, less formally, in essence, asking if, for any "simple" linear function like
succ, there is a succinct algorithm to compute its repeated application quickly. Please, consider this informal intuition if my concrete formalization has further issues.