Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

On page 21 of Daniel Bernstein's paper "Smaller decoding exponents: ball-collision decoding" he presents a proof that I have a few questions about.

$P,Q,R,L$ and $W$ are all positive and close to $0$, that is, much less than $1$.

First, he increases $Q$ from $0$ to $\delta$ and $L$ to $L-(1/2)\delta\log_{2}\delta$ for some small $\delta$ and states that these changes result in the quantity $L\log_{2}L-Q\log_{2}Q-(L-Q)\log_{2}(L-Q)$ increasing by $-\delta\log_{2}\delta+O(\delta)$. How does he get this result? I believe the $-\delta\log_{2}\delta$ term comes from $-Q\log_{2}Q$ but how does he simplify the changes to $L\log_{2}L-(L-Q)\log_{2}(L-Q)$?

Secondly he states that with these same increases the quantity $$(1-R-2L)\log_{2}(1-R-2L)-(W-2P-2Q)\log_{2}(W-2P-2Q)-(1-R-2L-(W-2P-2Q))\log_{2}(1-R-2L-(W-2P-2Q)) +2L\log_{2}L-2Q\log_{2}Q-2(L-Q)\log_{2}(L-Q)$$ increases by $$\delta\log_{2}\delta\log_{2}(e(1-R-2L))-\delta\log_{2}\delta\log_{2}(e(1-R-2L-(W-2P-2Q)))-2\delta\log_{2}\delta+O(\delta)$$ I'm guessing that $\delta\log_{2}\delta\log_{2}(e(1-R-2L))$ corresponds to $(1-R-2L)\log_{2}(1-R-2L)$ and likewise for the $(1-R-2L-(W-2P-2Q))$ term but I'm at a loss on how to get there. Obviously there's a bit of my first question in here as well.

As a sidenote, are there any good asymptotic analysis books you'd suggest? Thanks.

share|improve this question
I suspect all of your questions can be answered by using this: the change in $f(x)$ is roughly $f'(x)$ times the change in $x$, together with the two-variable version of this that involves partial derivatives. Try it, and see. If it works, write it up as an answer. Meanwhile, I think I'll do a little retagging. –  Gerry Myerson Apr 18 '12 at 4:07
Thanks Gerry, I'll give that a try and report back. –  Nick Apr 19 '12 at 4:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.