2

For my master thesis in computer science, I've got stuck at a point where I have to express $\alpha$ as a function of $\varepsilon$, when I know that

$$\frac{\alpha}{\log_2(4\alpha)} > 96\varepsilon^{-1}$$

for $0 < \varepsilon < 1$. I have tried to move this around a lot, but keep having either both $\alpha$ and $\log_2\alpha$ being part of the equation or both $2^\alpha$ and $\alpha$, e.g. I can get it to be

$$2^\alpha > (4\alpha)^{96\varepsilon^{-1}}$$

but do not know how to proceed from here. Any help is appreciated.

For the ones into computer science, this has to do with finding the sparcification constant when $k = 3$, but for everybody else I guess this is just a pure math question.

Also, I'm not quite sure which tags to give this. Please comment if you know.

Lorenzo B.
  • 2,252
AstridNeu
  • 43
  • 2

1 Answers1

5

The solution of $$\frac{\alpha}{\log_2(4\alpha)} = 96\,\varepsilon^{-1}$$ is given in terms of Lambert function $$\alpha=-\frac{96 }{\varepsilon \log (2)}W\left(-\frac{\log (2)}{384} \varepsilon \right)$$

To evaluate it, since the argument is small $(\lt 0.002)$, use the series expansion $$W(x)=x-x^2+\frac{3 x^3}{2}-\frac{8 x^4}{3}+O\left(x^5\right)$$ or, even better, the Padé Approximant $$W(x)=\frac{x+\frac{4 }{3}x^2}{1+\frac{7 }{3}x+\frac{5 }{6}x^2}$$

Since $0 \leq \varepsilon\leq 1$, you can have a very good approximation using Taylor again to get $$\alpha=\frac{1}{4}+\frac{ \log (2)}{1536}\varepsilon+\frac{\log ^2(2)}{393216}\varepsilon^2+\frac{ \log ^3(2)}{84934656}\varepsilon^3+O\left(\varepsilon ^4\right)$$

Update

Thinking more about the problem, I think that we could have avoided Lambert function. Let $\beta=4\alpha$ and rewrite the equation as $$\varepsilon=\frac{384}{\log (2)}\frac{ \log (\beta )}{\beta }$$ Expanding the rhs as a Taylor series built at $\beta=1$, this would give $$\varepsilon=\frac{384 (\beta -1)}{\log (2)}-\frac{576 (\beta -1)^2}{\log (2)}+\frac{704 (\beta -1)^3}{\log (2)}+O\left((\beta -1)^4\right)$$ and then, using series reversion $$\beta=1+\frac{\log (2)}{384} \varepsilon +\frac{ \log ^2(2)}{98304}\varepsilon ^2+\frac{\log ^3(2)}{21233664}\varepsilon ^3 +O\left(\varepsilon ^4\right)$$ and, then, the same $$\alpha=\frac{1}{4}+\frac{ \log (2)}{1536}\varepsilon+\frac{\log ^2(2)}{393216}\varepsilon^2+\frac{ \log ^3(2)}{84934656}\varepsilon^3+O\left(\varepsilon ^4\right)$$

Claude Leibovici
  • 260,315
  • This seems to be what I'm looking for (although I will probably have to use quite some time before I understand it). Thanks. – AstridNeu May 25 '18 at 11:24
  • I have been trying to understand this all weekend but still have some missing pieces. As far as I understand from reading about Lambert W, I have to turn my formula into $\frac{\log2}{384}\varepsilon = \frac{-\alpha\log2}{96}\varepsilon \cdot e^{\frac{-\alpha\log2}{96}\varepsilon}$ in order to get the expression for $\alpha$ that you provided me with. I have had no luck with this despite my efforts (which are to long for a comment). Am I even trying to do the right thing? (continues...) – AstridNeu May 28 '18 at 11:55
  • (...continued) I also can not get the "almost perfect" solution to work. Setting $\varepsilon = 0.5$ (just as an example), this gives me $\alpha \approx -0.2498$ but then $\frac{\alpha}{\log_2(4\alpha)} \approx \frac{-0.2498}{\log_2(4*-0.2498)} \neq 192 = 96/0.5 = 96\varepsilon^{-1}$. What am I missing?

    Sorry for my mathematical gaps.

     – AstridNeu May 28 '18 at 11:55
  • As a comment to your addition of the table: I do not require much accuracy, as what I need is a formula (not a value) for $\alpha$ that makes my inequality true no matter the choice of $\varepsilon$, but still keeps $\alpha$ as small as possible. On the contrary, complexity theory is a rather inaccurate science compared to mathematics, and I would be better suited with a formula for $\alpha$ that was simple rather than accurate, as long as it keeps $\alpha$ on the right side. I should probably have specified this in the original question, but having the exact answer I can get to this myself. – AstridNeu May 28 '18 at 12:50
  • @AstridNeu. I am sorry. I noticed typo's in my answer. I fix it now. – Claude Leibovici May 29 '18 at 04:23
  • @AstridNeu. If you use $\varepsilon = 0.5$, the expansion leads to $a=0.2502259398$ and $\frac{\alpha}{\log_2(4\alpha)} \approx 192.00000073$ – Claude Leibovici May 29 '18 at 04:44
  • Perfect. It all makes sense now and now I can also see how to get from my formula to your formula for $\alpha$. This was of great help to me. Thanks. – AstridNeu May 29 '18 at 11:15
  • @AstridNeu. Be sure I really apologize for the typo's. Being myself almost blind, my wife uses to check for this kind of mistakes. Unfortunately for you, she was absent when I worked your problem. Cheers. – Claude Leibovici May 29 '18 at 13:59