Elementary sequences, sub-Fibonacci sequences (Q686269)

A nondecreasing integer sequence \(x_ 1,x_ 2,\dots,x_ k\) with \(x_ 1=x_ 2=1\) and \(n \geq 2\) is said to be elementary if for all \(k \leq n\) \((x_ k>1 \Rightarrow x_ k=x_ i+x_ j\) for some \(i \neq j)\) and sub- Fibonacci if for all \(k \in \{3,\dots,n\}\) \((x_ k \leq x_{k-1}+x_{k- 2})\). These notions were motivated by questions of uniqueness of solutions for finite measurement structures [cf. the authors, IMA Vol. Appl. 17, 103-137 (1989; Zbl 0702.92024)]. The authors touch upon three complexes of questions (supported by rich computational underlying material) related to these sequences, however not answering most of them completely, thereby leaving a number of problems open. For instance, if \(E_ n\) is the set of all \(n\)-term elementary sequences and \(F_ n\) the set of all \(n\)-term sub-Fibonacci sequences then \(| E_ n |/ | F_ n | \to 0\) with \(| F_ n | = \alpha^{n^ 2(1+ o(1))/2}\), \(\alpha=(1+\sqrt 5)/2\). The second complex of results focuses on investigation of the length \(e(m)\) of a shortest elementary sequence whose last term is \(m\). This is a nondecreasing quantity. The previously proved lower bound \(k+1\) for \(e(m)\) with \(m\) between two adjacent Fibonacci numbers \(f_ k\) and \(f_{k+1}\) is improved to \(k+2\) for \(m \in(2f_{k-1}+f_{k-3}, f_{k+1})\). Finally, lower bounds for the maximum number of one-term extensions into \(E_{n+1}\) for an elementary sequence in \(E_ n\) is proved.