1
$\begingroup$

Related to this question and possibly the open problem of the exponential time hypotheses.

Let $A$ be rational number, $0 < A < 1$.

For positive integer $n$, define the sequence $a(1,A)=1$ and $(n,A)=n *a(\lfloor (1-A) n\rfloor,A)$.

What are asymptotics and upper bounds for $a(n,A)$?

We are especially interested in finding out when it is that $a(n,A)$ is $\exp(o(n))$, small oh on purpose.

Related OEIS sequence suggests the growth is closely to $n^{\log{n}}$.

Based on numerical evidence, we conjecture that solution will be of the form

$$\lim_{n \to \infty}{\frac{\log a(n,A)}{\log{n^{\log{n}}}}}.$$

for all $A$.

$\endgroup$

1 Answer 1

1
$\begingroup$

Define the sequence $n_k$ via the recursive formula $n_0=n$ and $n_{k+1}=\lfloor(1-A)n_k \rfloor$. As $0<A<1$, the sequence is decreasing. Let $M$ be the largest solution of inequality $n_M\geq 1$. First of all, by the definition of $a(n,A)$ we have $$ \ln a(n_k,A)=\ln n_k+\ln a(n_{k+1},A), $$ therefore $$ \ln a(n,A)=\sum_{k\leq M}\ln n_k. $$ Let us now study the asymptotics of $n_k$. By the definition of the floor function, for all $k$ there is some constant $0\leq \theta_k<1$ with $$ n_{k+1}=(1-A)n_k-\theta_k. $$ Applying this formula several times we see that $$ n_k=n(1-A)^k-\theta_0(1-A)^{k-1}-\theta_1(1-A)^{k-2}-\ldots-\theta_{k-1}. $$ Since the geometric series converges, we get $$ n_k=n(1-A)^k+O\left(\frac{1}{A}\right), $$ where the constant in $O$ is absolute (in fact, always at most $1$). This means, first of all, that for $k\leq M$ we have $$ \ln n_k=\ln(n(1-A)^k+O_A(1))=\ln n+k\ln(1-A)+O_A\left(\frac{(1-A)^{-k}}{n}\right). $$ Hence $$ \ln a(n,A)=\sum_{k\leq M}(\ln n+k\ln(1-A)+O\left(\frac{(1-A)^{-k}}{n}\right))= $$ $$ M\ln n+\frac{M^2+M}{2}\ln(1-A)+O\left(\frac{1}{n}\sum_{k\leq M}(1-A)^{-k}\right). $$ The sum in $O$ can be estimated by the largest term, so it is $O(n^{-1}(1-A)^M)=O(1)$. We are left with the question on asymptotics of $M$.

Now, by definition of $M$, we have $1\leq n_M<\frac{1}{1-A}$. This means that the quantity $$ n(1-A)^M $$ is bounded from above and from below (because the $O(1/A)$ term is always non-positive), hence $$ M=-\frac{\ln n}{\ln(1-A)}+O(1). $$ This means that for $n\to +\infty$ we have $$ \ln a(n,A)\sim \alpha(A)\ln^2 n=\alpha(A)\ln n^{\ln n}, $$ where $$ \alpha(A)=\frac{1}{2\ln^2(1-A)}-\frac{1}{\ln(1-A)}. $$ EDIT: The last formula should actually be $$ \alpha(A)=-\frac{1}{2\ln(1-A)}, $$ I missed the $\ln(1-A)$ factor.

$\endgroup$
4
  • $\begingroup$ Many thanks for the answer! $\endgroup$
    – joro
    Commented Aug 8, 2021 at 11:51
  • $\begingroup$ Do you think this gives subexponential solution for the linked question about MIS in graph? $\endgroup$
    – joro
    Commented Aug 8, 2021 at 13:28
  • $\begingroup$ @joro Corrected, thanks. As for the linked question: I don't know what you can get from my answer here. $\endgroup$ Commented Aug 9, 2021 at 12:44
  • $\begingroup$ I killed the bug in my code, you appear right. Thanks again :) $\endgroup$
    – joro
    Commented Aug 9, 2021 at 16:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .