Let $n$ be a positive odd integer, let $$n_j = \Bigl\{\frac{n}{2^{j+1}}\Bigr\}\,,$$ where $\{x\}$ denotes the fractional part of $x$, and finally let $k = \lceil \log_2 n\rceil$. Consider the function $$ f(n) = \prod_{j=1}^{k} \bigl[1- 4n_j(1-n_j)\bigr]\,. $$ Each term in this product is bounded in the interval $(0,1)$, so $f(n)$ will tend to $0$ for large $n$. My question is how one can

Prove that $f(n) \ge \frac{c}{n^a}$ for some absolute positive constants $a$, $c$.

It is easy to show (using bounds on the fractional part) that there exist $a,c>0$ such that $$ f(n) \ge \frac{c}{n^{a \log n}} \,, $$ so that the product decays only subexponentially slowly, but a heuristic argument as well as numerics indicates that the true scaling is actually a much slower inverse polynomial. The heuristic argument is, roughly, that the terms in the product are highly correlated, and if one term is small, the following term must be large. I have been unable to leverage this into a proof, however.

I indicated in the title that this is a "number theoretic" function because the behavior depends heavily on the bit-wise structure of $n$, and it has some interesting fractal features as a result.


Numerical experimentation suggests that the fastest-decaying values occur at $n_k=[2^k/3]$, where $[\cdot]$ indicates rounding off to the nearest integer. These integers have binary expansion $101010\cdots$. It probably is possible to work out very good bounds for $f(n_k)$. Numerically, we seem to have $f(n_k)$ asymptotic to a constant times $1/n_k^\alpha$ where $\alpha = \log 9/\log 2$.

(Similarly, the slowest-decaying values are almost surely $m_k = 2^k-1$, for which we seem to have $f(m_k) \sim c/m_k^2$ for some constant $c$.)

  • $\begingroup$ Thanks Greg! Yes, I have also noticed that the binary expansion is alternating at the local minima, i.e. those in the interval $(2^{k-1},2^k)$, and the asymptotic constant follows. What I'm stuck on is how to prove that this is the right decay. The problem is that I don't know how to bound the behavior of sequences which are close in Hamming distance in a satisfactory way. $\endgroup$ – Steve Flammia Nov 7 '13 at 21:55
  • $\begingroup$ I imagine you would use bounds on the derivative of $\log(1-4x(1-x))$ to show that changing a single bit of $n$ only changes each term in the sum defining $\log f(n)$ by a controllable amount, and hence that $f(n)$ changes only by a controllable amount (since these various error form a quickly converging sequence). Exponentiating, this shows that changing one bit of $n$ only changes $f(n)$ by a controllable percentage. And on from there, hopefully...? $\endgroup$ – Greg Martin Nov 7 '13 at 22:10
  • $\begingroup$ My fear is that there are no good bounds on that derivative. If you change the last bit to make $n$ an even number, then $f(n)$ immediately goes to zero. So the function is very delicate, it seems. I'll have to give it a try though. $\endgroup$ – Steve Flammia Nov 7 '13 at 22:54
  • $\begingroup$ Yes, certainly the derivative is not bounded on $(0,1)$, and a number ending in the bits $\dots011111111$ or $\dots1000000001$ will hit this function in the scary region. Presumably the contribution from the bad-derivative part is compensated for by the fact that all the stuff that led up to it was really nice, as for $2^k-1$. But yeah, it's not obvious to me how to proceed (otherwise I'd've done it!).... $\endgroup$ – Greg Martin Nov 8 '13 at 1:10

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.