# How to prove the following resummation identity for Erdős–Borwein constant?

Question: How to prove

$$\sum_{m=1}^{\infty}\left(1-\prod_{j=m}^{\infty}(1-q^j)\right) = \sum_{n=1}^{\infty}\frac{q^n}{1-q^n} \tag{1}$$ for all $$q \in \mathbb{C}$$ such that $$\left|q\right| < 1$$?

Below are some observations about the question.

Observation 1: The right hand side of (1) is known as (an example of a) Lambert series. For $$q=1/2$$ it is equal to Erdős–Borwein constant (A065442).

Observation 2. Numerical evidence: According to numerical evaluation lhs and rhs of (1) match up to $$10^{-16}$$. According to Wolfram Mathematica lhs and rhs of (2) match (as series in $$q$$) modulo $$q^{1001}$$.

Observation 3. Equivalent statements: The following statements are equivalent (thus, you can prove any one of these to answer the question).

1. Equation (1) is true for all $$q\in\mathbb{C}$$ s.t. $$\left|q\right| < 1$$.

2. Equation (1) is true as a formal series in $$q$$.

3. For a positive integer $$n$$ denote by $$d(n)$$ the number of divisors of $$n$$ ($$d$$ is known by the name of the divisor function). Denote by $$P(n|\text{distinct})$$ the set of partitions of $$n$$ into distinct integers, i.e. $$P(n|\text{distinct}) = \Bigl\{a = (a_1,\dots,a_{\text{len}(a)}):\\a_i\in\mathbb{N}, 1\leq a_1<\dots The claim is that for every integer $$n\geq 1$$ we have $$\sum_{a\in P(n|\text{distinct})}(-1)^{\text{len}(a)-1}a_1 = d(n).$$

4. Consider $$p$$ being an integer power of a prime, and positive integer $$n$$, let $$\mathbb{F}_p$$ be the finite field with $$p$$ elements, let $$V=\mathbb{F}_p^n$$ be the $$n$$-dimensional vector space over that field. Consider a black box $$B$$, which when queried returns a random vector $$v\in V$$ (with equal probabilities). Consider the following 2-stage process.

Stage 1: "Span". In this stage we query $$B$$ for vectors $$v_1,\dots,v_k$$ until $$\text{span}\{v_1,\dots,v_k\} = V$$.

Stage 2: "Linear dependence". In this stage we query $$B$$ for vectors $$v_1,\dots,v_k$$ until they are linearly dependent. That is, until there are numbers $$n_1,\dots,n_k \in \mathbb{F}_p$$ s.t. $$\sum_{i=1}^k n_i v_i = 0$$ and at least one of $$n_i$$ is non-zero.

It can be proven that this process (the total of 2 stages) takes on average $$2n+1+C_{p}+O(np^{-n})$$ queries to the black box.

The claim is that for infinitely many $$p$$ we have $$C_p = 0$$.

5. For any integer $$p$$ equal to an integer power of a prime we have $$C_p = 0$$.

Observation 4. Relationship to the Simon's problem: The process described in #4 of observation 3 above is related to the Simon's problem for $$n+1$$ qubits. For $$p=2$$ the number of queries in stage 1 is equal to the number of queries to the oracle needed by the quantum algorithm, while the number of queries in stage 2 is equal to the number of queries needed by the best classical algorithm for linear oracles (where there is no quantum advantage).

This can be deduced from the following result (known to Cauchy): $$\sum_{n=0}^\infty z^n\prod_{k=1}^n\frac1{1-q^k}=\prod_{n=0}^\infty\frac1{1-zq^n}$$ for $$q,z\in\mathbb{D}:=\{w\in\mathbb{C}:|w|<1\}$$, shown as follows: for a fixed $$q$$, the RHS $$f(z)$$ is analytic on $$\mathbb{D}$$ and satisfies $$f(qz)=(1-z)f(z)$$, which we solve using power series; this gives the LHS. (See this answer of mine for more references.)
After multiplication by $$\prod_{n=1}^\infty(1-q^n)$$, this is written as $$\sum_{n=0}^\infty z^n\left(1-\prod_{k=n+1}^\infty(1-q^k)\right)=\frac1{1-z}\left(1-\prod_{n=1}^\infty\frac{1-q^n}{1-zq^n}\right).$$
Now we just take $$z\to1$$: the LHS becomes the one we want, and for a fixed $$q\in\mathbb{D}$$, with $$g(z):=\prod_{n=1}^\infty\frac{1-q^n}{1-zq^n}\implies\frac{g'(z)}{g(z)}=\sum_{n=1}^\infty\frac{q^n}{1-zq^n},$$ the RHS becomes $$\lim\limits_{z\to1}\big(1-g(z)\big)/(1-z)=g'(1)$$; here we use $$g(1)=1$$.