# Lower bound on a number theoretic function

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$.)
• 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. – Steve Flammia Nov 7 '13 at 21:55
• 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...? – Greg Martin Nov 7 '13 at 22:10
• 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. – Steve Flammia Nov 7 '13 at 22:54
• 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!).... – Greg Martin Nov 8 '13 at 1:10