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 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$.

$\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 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 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 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 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.