7
$\begingroup$

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<a_{\text{len}(a)}\leq n,\sum_{i=1}^{\text{len}(a)}a_i = n\Bigr\}. \tag{2}$$ 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).

$\endgroup$
0

1 Answer 1

7
+50
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Very nice answer. (+1) $\endgroup$ Commented Sep 19, 2022 at 7:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .