5
$\begingroup$

I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows:

$$a_1 = 1, a_2 = 2$$ $$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$

Apparently, Knuth was able to prove that the sequence grows at least like $2.28^n$. Unfortunately, any hint of the proof seems to be lost or never published, as all reference cite "personal communication". I'd like to know the rationale.

While I don't need to know the sequence exactly, lower order terms have some importance. For example, the difference between a growth rate of $n^{\Omega(1)} c^n$ verses $c^n / n^{\Omega(1)}$ would be significant (although I think I have a proof sketch that the first case is impossible, it would be nice to check). I'm also interested in the initial conditions $a_1=2, a_2=7$.

So far, I've mostly just tried playing around the with generating function of the sequence, but I haven't gotten anywhere. A reference for applying generating function techniques to recurrence problems involving squares etc. of previous terms would be appreciated! I'm not sure what other techniques would be useful.

Background: [1] introduced a family of stable marriage instances which provide the best known lower bounds for the maximum number of stable matchings possible for some problem instance. [2] is the first source I could find to mention the number $2.28$. [3] generalizes the family created in [1] somewhat but doesn't do better than $2.28^n$.

[1] Irving, Robert W., and Paul Leather. "The complexity of counting stable marriages." SIAM Journal on Computing 15.3 (1986): 655-667.

[2] Pittel, Boris. β€œOn Likely Solutions of a Stable Marriage Problem.” The Annals of Applied Probability, vol. 2, no. 2, 1992, pp. 358–401. JSTOR, www.jstor.org/stable/2959755.

[3] Edward G Thurber. Concerning the maximum number of stable matchings in the stable marriage problem.Discrete Mathematics, 248(1-3):195–219, 2002.

Solution

I wrote up Professor Shor's solution here!

$\endgroup$
  • 1
    $\begingroup$ The sequence $a_1=2$, $a_2 = 7$ grows like $s^n$ for a different value of $s$. Empirically, it seems to be around 4.19. $\endgroup$ – Peter Shor Aug 7 '19 at 18:13
10
$\begingroup$

Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily.

First, let's notice that for $b_n=a_{2^n}$, we have the recurrence

$$b_n = 3b_{n-1}^2 - 2b_{n-2}^4.$$

Now, let's assume that $b_n = r s^{2^n}$. The equation becomes

$$r s^{2^n} = 3 r^2 s^{2^n} - 2 r^4 s^{2^n},$$

and $s^{2^n}$ factors out. Solving the equation $r = 3r^2 - 2r^4$, we find two positive roots, $r = 0.366 = \frac{1}{2}(\sqrt{3}-1)$ and $r= 1$. Let $r_0$ be the smaller of these roots.

Suppose we could show that $\frac{b_{n-1}^2}{b_n} = r_0$. Then we can show by induction that $b_n=r_0 s^{2^n}$ for some value of $s$. Suppose this is true for some value $n$. Then \begin{align} b_{n+1} &= \frac{b_{n}^2}{r_0} = \frac{\left(r_0 s^{2^n}\right)^2}{r_0} = r_0 s^{2^{n+1}}. \end{align}

In fact, we won't quite show this; what we will show is that $\frac{b_{n-1}^2}{b_n}$ goes to $r_0$ as $n$ goes to $\infty$. With some analysis (given in an appendix), we can complete the proof that $b \approx r_0 s^{2^n}$ for some value of $s$. The actual value of $s$ depends on the initial conditions, and the only way I know to get it is computationally. Maple seems to say that $s$ is around 2.280142. If you start with $a_1=2$, $a_2=7$, Maple gives $s \approx $ 4.189425.

Why does $\frac{b_{n-1}^2}{b_n}$ go to $r_0$? Take the recurrence, and divide $b_{n-1}^2$ by both sides. This gives

$$ \frac{b_{n-1}^2}{b_n} = \frac{1}{3-2\left(\frac{b_{n-2}^2}{b_{n-1}}\right)^2},$$ or, letting $t_n = b_{n-1}^2/b_n$, $$t_n=\frac{1}{3-2 t_{n-1}^2}.$$ This has three fixed points, but the only attractive point is $r_0$, and $t_n$ approaches this point from any initial value except the two other fixed points.

Appendix:

Here is a sketch of the argument that if $\lim_{n\rightarrow \infty} t_n = r_0$, then $s$ exists. We'll consider an approximation to $s$ based on $b_n$. Let $$s_n = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}.$$ Then $$\frac{s_n}{s_{n-1}} = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}\left(\frac{r_0}{b_{n-1}}\right)^{\frac{2}{2^{n}}} = \left( \frac{b_nr_0}{b_{n-1}^2}\right)^{\frac{1}{2^n}} = \left( \frac{r_0}{t_n}\right)^{\frac{1}{2^{n}}} . $$ If $\lim_{n \rightarrow \infty} t_n = r_0$, this equation implies that $$ \prod_{m=n}^\infty \frac{s_{m+1}}{s_m} \rightarrow 1 \quad \mathrm{as} \quad n \rightarrow \infty,$$ and thus that $s =\lim_{n\rightarrow \infty} s_n $ exists.

But in order to show that $b_n$ grows like $r_0 s^{2^n}$ as $n \rightarrow \infty$, you need not just that $s_n$ converges, but that it converges quickly. The exponent on $\frac{r_0}{t_n}$ above takes care of that. What we would like to show is that $$\lim_{n\rightarrow\infty} \frac{s^{2^n}}{s_n^{2^n}} = 1.$$

But $$ \frac{s^{2^n}}{s_n^{2^n}} = \prod_{m=n}^{\infty} \left(\frac{s_{m+1}}{s_m}\right)^{2^{n}} = \prod_{m=n}^{\infty} \left(\frac{r_0}{t_{m+1}}\right)^{\frac{1}{2^{m+1}}2^{n}} \approx \left(\frac{r_0}{t_{n}}\right)^{2^n\left(\sum\limits_{m=n}^\infty \frac{1}{2^{m+1}}\right)}= \frac{r_0}{t_n},$$ which goes to $1$ as $n \rightarrow \infty$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Brilliant! Thanks a lot Professor Shor. Mind if I type this up in a bit more detail and add it to the OEIS page on the sequence? oeis.org/A005154 $\endgroup$ – Clay Thomas Aug 8 '19 at 18:42
  • $\begingroup$ @Clay: Please do. Also, I didn't write it up, but you can get rigorous bounds on how far off the estimate 2.280142 is using these techniques; this estimate was obtained from the formula $𝑏_𝑛 \approx π‘Ÿ_0𝑠^{2^𝑛}$, and you can show that it converges to $s$ really fast. $\endgroup$ – Peter Shor Aug 8 '19 at 19:00
  • $\begingroup$ @Clay: Specifically, my last equation lets you find out how estimate how far the estimate for $s$ (2.280142) is off. You could easily get many more decimal places. $\endgroup$ – Peter Shor Aug 9 '19 at 12:36
  • $\begingroup$ Ah I see. We have both a recurrence for $t_n$ and $s_n = s_{n-1} (r_0 / t_n)^{1/2^n}$ allowing us to easily calculate $s$, and we know that $s_n \ge s \ge s_n (r_0 / t_n)^{1/2^n}$, giving very fast (at least $(1 + O(1/2^n)$) convergence! $\endgroup$ – Clay Thomas Aug 9 '19 at 15:13

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.