Conjecture on generalized Fibonacci growth rates below 2n2^n

About 7 years old · traced to

Let MM be an ω\omega-categorical structure with growth rate fM(n)f_M(n), and for k∈Nk\in\mathbb{N} let the generalized Fibonacci numbers be defined by

Fn,k=∑i=1kFn−i,k,F_{n,k}=\sum_{i=1}^{k}F_{n-i,k},

with Fn,k=0F_{n,k}=0 for n<0n<0 and F0,k=1F_{0,k}=1.

Generalized Fibonacci growth conjecture. If

fM(n)<2np(n)f_M(n)<\frac{2^n}{p(n)}

for every polynomial p(n)p(n), then there is some k∈Nk\in\mathbb{N} such that

lim⁡n→∞Fn,k1/n=lim⁡n→∞fM(n)1/n.\lim_{n\to\infty}F_{n,k}^{1/n}=\lim_{n\to\infty}f_M(n)^{1/n}.

The claim aims to determine the possible exponential growth constants in the range just below 2n2^n; the source describes this subcase as more approachable and records the assertion as still conjectural.

References

Primary source

Samuel Braunfeld, “Monadic stability and growth rates of ω-categorical structures”, arXiv:1910.04380 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.