Master's internship

If you are looking for an internship for your Master's studies and would like to work with me on block random matrices, incompatibility of quantum measurements, non-commutative Sinkhorn scaling algorithms, random density matrices, or any other topic in random matrix theory or quantum information theory, write me an email. There is the possibility to continue on to a PhD thesis on similar topics at the end of the Master's project.

Posted in open positions | Leave a comment

The joint distribution of marginals of multipartite random quantum states

Together with Stephane Dartois and Luca Lionni, we have a new preprint on the arXiv, On the joint distribution of the marginals of multipartite random quantum states. The paper is about the joint distribution of the set of (twisted) marginals of random multipartite quantum states. We study mainly random Wishart tensors, which, after normalization, yield multipartite random quantum states, so our work can also be seen as a contribution to the theory of random tensors.

Start with 2n copies of a finite dimensional complex Hilbert space, say \mathbb C^n. Consider X \in (\mathbb C^N)^{\otimes 2n} a random complex Gaussian tensor, that is a vector of size N^{2n} with i.i.d. standard complex Gaussian entries. for a subset I \in \{1,2, \ldots, 2n\} of cardinality n, we define the marginal

 \displaystyle W_{I} := [\mathrm{id}_I \otimes \operatorname{Tr}_{\hat I}](XX^*)

obtained by partial tracing the tensor legs belonging to \hat I, the complementary set of I. Moreover, we allow for twisted marginals: for a permutation \sigma \in \mathcal S_n, let

 \displaystyle W_{I, \sigma}:= P_\sigma^{-1} W_I P_\sigma,

where P_\sigma permutes the tensor legs as follows:

 \displaystyle P_\sigma e_1 \otimes \cdots \otimes e_n = e_{\sigma(1)} \otimes \cdots \otimes e_{\sigma(n)}.

We prove the following result.

Theorem 1 The set of  {{2n}\choose{n}} n! twisted marginals W_{I,\sigma} are asymptotically free as N \rightarrow \infty. In other words, they jointly converge in distribution to a family of free standard free Poisson elements.


Recall that a free Poisson (or a Marchenko-Pastur) random variable has distribution

 \displaystyle \mathrm{d}\mathrm{MP}_c=\max (1-c,0)\delta_0+\frac{\sqrt{(b-x)(x-a)}}{2\pi x} \; \mathbf{1}_{[a,b]}(x) \, \mathrm{d}x,

where c>0 is a positive parameter (in our result, c=1). We display below the density (red curve) and numerical simulations for c=1

and for c=5

The message of our main theorem is that although the (overlapping) marginals are correlated random variables, their distributions become asymptotically free as the size of the individual Hilbert spaces grows to infinity.

The freeness result proven in the balanced asymptotical regime (the tensor factors scale in the same way) fails in the unbalanced asymptotical regime (some of the tensor factors have fixed dimensions, whereas others grow to infinity). We emphasize this fact in a particular situation, for n=2 (4-partite tensors). Write W_{ABCD} = XX^*, where

 \displaystyle X \in \mathbb C^N \otimes \mathbb C^m \otimes \mathbb C^m \otimes \mathbb C^{\lfloor cN \rfloor},

and A,B,C,D denote, respectively, the four tensor factors above. It is natural to consider the joint distribution of the marginals W_{AB},W_{AC}, which are not asymptotically free anymore:

Theorem 2 As N \rightarrow \infty and c,m are fixed, the marginals W_{AB},W_{AC} have the following asymptotical free cumulants:

 \displaystyle \kappa(w_{f(1)}, w_{f(2)}, \ldots, w_{f(p)}) = cm^{-\mathrm{alt}(f)},

where f \in \{AB, AC\}^p is an arbitrary word in the letters AB, AC, and \mathrm{alt}(f) is the number of different consecutive values of f, counted cyclically:

 \displaystyle \mathrm{alt}(f) := |\{a \, : \, f(a) \neq f(a+1)\}|,

where f(p+1):=f(1).


The difference with the previous situation is that the amount of ''fresh'' randomness in the marginals W_{AB},W_{AC} is relatively small (fixed m vs. N \rightarrow \infty), and not enough to ensure the asymptotical freeness. The natural framework to tackle such situations is that of freeness with amalgamation, and we shall study these cases in some future work.

Posted in new-paper | Tagged , , , , | Leave a comment

Counting meanders

We have, with Moto Fukuda, a new paper on the arXiv, Enumerating meandric systems with large number of components, which deals with the enumeration of meandric systems.

In combinatorics, a meander on 2n points is a closed, self-avoiding plane curve, which intersects a given line 2n times. Below, the meanders of a river (Rio Cauto, in Cuba) and a mathematical meander are represented.

rio-cauto m1

The following more general objects are considered in the literature.

Definition 1 A meandric system on 2n points with r connected components is a collection of r non-intersecting closed curves, which cross a given line 2n times. A meander is a meandric system with 1 component.

Below are represented two meandric systems on 6 points, with 2, respectively 3 connected components.

m2 m3

One easily recognizes the diagrams above and below the horizontal line: these are non-crossing pairings, a subclass of non-crossing partitions. Non-crossing pairings on 2n points are known to be in bijection with (general) non-crossing partitions on n points, through an operation called fattening; in the picture below, the same meanders as above are depicted, together with the corresponding non-crossing partitions on n=3 points; see how the meander (red) is a ``fattening'' of the pair of non-crossing partitions (black).

mm2 mm3

In our paper, we study meandric systems on 2n points with n-r connected components, for some fixed parameter r. We obtain the general form of the generating function for the number M_n^{(n-r)} of such meanders, with exact expressions for r \leq 6. Some trivial observations can be made right from the start. First, we have seen that meandric systems are in bijection with pairs of non-crossing partitions. Since non-crossing partitions are counted by Catalan numbers, we have

 \displaystyle \sum_{c=1}^n M_n^{(c)} = \mathrm{Cat}_n^2.

Note also that meandric systems with a maximal number of connected components (see the example on the right in the previous two pictures) correspond to the case where the two non-crossing partitions \alpha, \beta defining the meander are equal \alpha = \beta, and thus

 \displaystyle M_n^{(n)} = \mathrm{Cat}_n.

To compute the numbers M_n^{(n-1)}, it is not hard to see that the two non-crossing partitions \alpha and \beta must be somehow ``close''. To make this precise, we consider another key bijection, the one between non-crossing partitions and the so-called geodesic permutations. In his seminal work Some properties of crossings and partitions, Biane realized that non-crossing partitions are in bijection with the following set of permutations

 \displaystyle \mathcal S_n^{NC} := \{\alpha \in \mathcal S_n \, : \, \|\alpha\| + \|\alpha^{-1} \pi \| = \|\pi \| = n-1\},

where \pi is the full-cycle permutation \pi = (1 2 \cdots n) and \| \cdot \| is the length function of permutations: \|\alpha\| is the minimal number of transpositions which multiply to \alpha. All these ideas are discussed in Lecture 23 of the excellent monograph of Nica and Speicher. In this framework, it has been known for some time that meanders on 2n points with c connected components are in bijection with the set

 \displaystyle \{ \alpha, \beta \in \mathcal S_n^{NC} \, : \, \|\alpha^{-1}\beta\| = n-c\}.

In particular, for c = n-1, only pairs of geodesic permutations which differ by only one transposition contribute; one can easily show then

 \displaystyle M_n^{(n-1)} = 2 \binom{2n}{n-2}.

In our paper, we use the moment-cumulant formula from Free Probability Theory to show that, for fixed r, the generating function for the number of meanders on 2n points with n-r connected components

 \displaystyle F_r(t) = \sum_{n=r+1}^\infty M_n^{(n-r)}t^n,

after the change of variables t=w/ (1+w)^2, reads

 \displaystyle F_r(t) = \sum_{n=r+1}^\infty M_n^{(n-r)} \frac{w^n}{(1+w)^{2n}} = \frac{w^{r+1}(1+w)}{(1-w)^{2r-1}} P_r(w),

where P_r(w) are polynomials of degree at most 3(r-1). With the help of a computer, we find these polynomials up to r=6. We show that such meandric systems are made of simple building blocks, called irreducible meanders. Irreducible meanders were introduced by Lando and Zvonkin here, and they were recently featured in Andu Nica's recent paper.

Let me close this post by mentioning what is probably the most important problem related to the enumeration of meanders (on which we do not touch upon): the asymptotic growth of meanders. This problem and the one we discuss in our paper sit at opposite ends of the spectrum with respect to the number of components.

The sequence of meandric numbers (M_n^{(1)})_n is conjectured to grow like

 \displaystyle M_n^{(1)} \sim C \rho^n n^{-\kappa},

for some constants C, \rho, \kappa. The exponential rate has been shown to satisfy 11.380 \leq \rho \leq 12.901. The polynomial speed is conjectured to be exactly \kappa = (29+\sqrt{145})/12.

The meandric numbers M_n^{(1)} have a very simple geometric interpretation: they count diameters in the metric space (\mathcal S_n^{NC}, \| \cdot \|):

 \displaystyle M_n^{(1)} = | \{ \alpha, \beta \in \mathcal S_n^{NC} \, : \, \|\alpha^{-1}\beta\| = n-1\} |.

The asymptotic behavior of the sequence M_n^{(1)} is largely open. Old and recent results suggest that solving this many-faceted problem might require some new insight or techniques.

Posted in new-paper | Tagged | Leave a comment

Bipartite unitary operators and quantum Latin squares

Tristan Benoist and I have just arXived our paper On bipartite unitary matrices generating subalgebra--preserving quantum operations. We characterize the set of bipartite unitary operators which give quantum operations preserving some subalgebra of the state space, independently of the state of the coupled environment. The main results in the paper deal with the cases of (block-)diagonal algebras and tensor algebras. I obtained similar results for different classes of quantum channels in a previous paper.

In this post I would like to discuss a marginal problem discussed in the preprint, that of quantum Latin squares. Latin squares are combinatorial objects which have received a lot of attention: they are simple but deep mathematical objects, and have found many applications, mainly in statistics, experience design, and information theory.

Definition 1 A n \times n Latin square is a matrix L \in M_n(\{1,2, \ldots, n\}) with the property that each row and each column of L are permutations of \{1,2,\ldots, n\}.

Here is an example of a Latin square of size 4:


We are interested in a ''vector space'' version of Latin squares, called quantum Latin squares, a notion introduced in the recent work of Musto and Vicary. The generalization is obtained via the classical information \leftrightarrow quantum information dictionary, where alphabets are replaced by vector spaces and letters by unit vectors in those spaces.

Definition 2 A n \times n quantum Latin square (QLS) is a 3-tensor X \in M_n(\mathbb C^n) with the property that the vectors in each row and each column of X form orthonormal bases of \mathbb C^n.

Below is an example of a 4 \times 4 QLS, taken from Musto and Vicary's paper, where \{e_1,e_2,e_3,e_4\} is a basis of \mathbb C^4.


One can make some trivial observations right off the bat. First, the elements of a QLS X must have unit Euclidean norm \|x_{ij}\| =1. The condition in the definition can be stated using the following matrices, having the vectors of X as columns

\begin{align*}  R_i &= \sum_{j=1}^n x_{ij}e_j^*\\ C_j &= \sum_{i=1}^n x_{ij}e_i^*, \end{align*}

for some fixed orthonormal basis \{e_1, \ldots, e_n\} of \mathbb C^n. Then, X is a QLS iff the 2n matrices R_1, \ldots R_n, C_1, \ldots, C_n are unitary operators. Moreover, using these matrices, we can define a natural ''distance'' function to the set \mathcal{QLS}_n of n \times n quantum Latin squares

 \displaystyle d(X)^2 = \sum_{i=1}^n \|R_iR_i^* - I_n\|_2^2 + \sum_{j=1}^n \|C_jC_j^* - I_n\|_2^2.

Every classical latin square L can be seen as a quantum Latin square by using the same basis for all rows and columns: x_{ij} = e_{L_{ij}}. For n \geq 4, there exist moreover purely ''quantum'' examples, such as the one pictured above. The set of n \times n quantum Latin squares \mathcal{QLS}_n is a real algebraic variety, since the unitarity conditions for the matrices R_i and C_j can be expressed as polynomial equations in the 2n^3 variables \operatorname{Re}(x_{ij}), \operatorname{Im}(x_{ij}).

In our paper, QLS appear in connection to bipartite unitary operators U \in \mathcal U(n^2) with the property that for all ancilla space density matrices \beta \in M_{n}^{1,+}(\mathbb C), the quantum channel

 \displaystyle T_{\beta}(\rho) = [\operatorname{id} \otimes \operatorname{Tr}](U (\rho \otimes \beta)U^*)

leaves the diagonal subalgebra D_n \subseteq M_n(\mathbb C) invariant (see Theorem 4.4).

We raise the question of finding a natural probability measure of the set \mathcal{QLS}_n. We propose such a measure, based on a non-commutative analog of the Sinkhorn-Knopp algorithm (see here and here for the original papers). The following algorithm is discussed in our paper. Below, we make use of an operator \operatorname{Pol}, which returns the angular part of the polar decomposition: if X = UP is the polar decomposition of X, then \operatorname{Pol}(X) = U; in case the polar decomposition is not unique, one of the valid decompositions is considered.

  1. Input: The dimension n and an error parameter \varepsilon >0
  2. Start with x_{ij} independent uniform points on the unit sphere of \mathbb C^n.
  3. While X is \varepsilon-far from \mathcal{QLS}n, do the steps (4-6)
  4. \qquad Define the matrix Y by making the rows of X unitary:

     \displaystyle \forall i \in [n], \qquad y_{ij} = \operatorname{Pol}\left( \sum_{s=1}^n x_{is}e_s^* \right) \cdot e_j.

  5. \qquad Define the matrix Z by making the rows of Y unitary:

     \displaystyle \forall j \in [n], \qquad z_{ij} = \operatorname{Pol}\left( \sum_{s=1}^n y_{sj}e_s^* \right) \cdot e_i.

  6. \qquad X \leftarrow Z.
  7. Output: X, an \varepsilon-approximate QLS.

We conjecture that the algorithm above converges for almost any choice of the n^2 random points at step (2). We have some numerical evidence for this claim, as well as a convergence proof for a close variant of the problem, where we replace the vector entries of the matrix X by positive definite matrices (see the appendix of our paper).

The algorithm above was also discussed in a paper with Teo Banica on the quantum permutation group S_N^+; there, we were interested in the probability measure induced on \mathcal{QLS}_n by the uniform measure in step (2).

Finally, let me mention that there exists a different non-commutative generalization of the Sinkhorn algorithm, introduced by Gurvits in his paper where he shows that the weak membership problem for the set of separable states is NP-hard.

Posted in new-paper | Tagged | Leave a comment

Quantum Information semester in Paris, autumn 2017

I am one of the organizers of a 3-month semester on quantum information theory ad the Institut Henri Poincaré in Paris. Among other events, there will be a one-week workshop on Probabilistic techniques and Quantum Information Theory, Oct 23-27. Please register if you are interested in attending.

Posted in conferences | Tagged | Leave a comment

Seoul lectures on some applications of random matrices to quantum information theory

Last week, at the invitation of Hun Hee Lee, I gave a series of three lectures on some applications of random matrix theory to problems in quantum information theory. The notes are available here. After discussing the Marchenko–Pastur theorem, I present my result with Teo Banica on partial transposition of random quantum states; this is also the occasion to review some basic facts from free probability. The third lecture dealt with random quantum channels, and I covered the results I obtained with Serban Belinschi and Benoit Collins here and here.

Posted in conferences, lecture notes, quantum information theory, random matrices, random quantum states, talks | Leave a comment

Linear Matrix Inequalities, Semidefinite Programming and Quantum Information Theory, Toulouse 18-22 January 2016

I am organizing a week-long workshop in Toulouse, on topics of optimization problems in quantum information theory. Besides the usual research talks, there will be lectures by Aram Harrow, Jean Bernard Lasserre and Mihai Putinar on the topics of the workshop: linear matrix inequalities, semidefinite programming, and quantum information theory. We have still some free slots for talks, so contact me if you're interested.

Posted in conferences | Leave a comment

Quantum Thermodynamics and Quantum Information Theory, Toulouse, 9-11 September 2015

I am one of the organizers of the workshop Quantum Thermodynamics and Quantum Information Theory that will take place in Toulouse, from 9-11 September 2015. Participation is free and open, so email one of the organizers if you are interested in the workshop.

Posted in conferences | Leave a comment

Random subspaces of a tensor product (II)

In this short post, I would like to discuss a special case of the construction introduced in the first part of the series, that is compute the set K_{A_n}, where A_n \subset \mathbb C^n \otimes \mathbb C^n is the anti-symmetric subspace of the tensor product. This example plays an important role in the additivity problem for the minimum output entropy of quantum channels, as it was shown in [ghp].

1. Anti-symmetric vectors and matrices

For order two tensors x \in \mathbb C^n \otimes \mathbb C^n, there are only two symmetry classes, the symmetric and the antisymmetric vectors. The antisymmetric vectors form a vector space

A_n = \mathrm{span}\left \{ \frac{1}{\sqrt 2} (e_i \otimes e_j - e_j \otimes e_i) \, : \, 1 \leq i < j \leq n \right \}

where the vectors in the span can be shown to form an orthonormal basis of the \binom n 2-dimensional subspace A_n, whenever e_i form a basis of \mathbb C^n. Let P_n \in \mathcal M_{n^2}(\mathbb C) be the orthogonal projection on the subspace A_n. It is easy to see that P_n has entries in {0,\pm 1/2} and it looks as below (n=10). antisymmetric-10

Via the usual isomorphism \mathbb C^n \otimes \mathbb C^n \simeq \mathbb C^n \otimes (\mathbb C^n)^* = \mathcal M_n(\mathbb C), one can see antisymmetric tensors as antisymmetric (or skew-symmetric) matrices: one simply has to rearrange the n^2 complex coordinates of the tensor in an n \times n matrix, respecting the ordering of bases. Note that in this way we obtain antisymmetric (X^t = -X) and not anti-Hermitian (X^* = -X) elements.

2. Singular values of vectors in the antisymmetric subspace

It is well known that antisymmetric (complex) matrices can be 2-block diagonalized using orthogonal rotations

X = O \begin{bmatrix} 0 & \lambda_1 & & & & \\ -\lambda_1 & 0 & & & & \\ & & 0 & \lambda_2 & & \\ & & -\lambda_2 & 0 & & \\ & & & & \ddots & \\ & & & & & 0 \end{bmatrix}O^t.

The matrix in the middle has either diagonal blocks of size 2, as shown, or null diagonal elements. Hence, the non-zero eigenvalues of an antisymmetric matrix come in pairs  \{ \pm \lambda_i \}. Since antisymmetric matrices are normal, their singular values are just the moduli of the eigenvalues, so non-zero singular values have multiplicity at least 2. We conclude that

K_{A_n} \subset \left\{ (\lambda_1, \lambda_1, \lambda_2, \lambda_2, \ldots) \, : \, \lambda_i \geq 0, \, \sum_{i=1}^{\lfloor n/2 \rfloor} \lambda_i = 1/2\right \}.

Actually, it is easy to see we have equality, since the vector

 x_\lambda = \sum_{i=1}^{\lfloor n/2 \rfloor} \sqrt{ \lambda_i } (e_i \otimes e_{\lfloor n/2 \rfloor+i} - e_{\lfloor n/2 \rfloor+i} \otimes e_i)

is a unit norm element of A_n. We summarize everything in the following theorem, where \prec denotes the majorization relation.

Theorem 1. The set of all possible singular values of antisymmetric vectors inside \mathbb C^n \otimes \mathbb C^n is given by

K_{A_n} = \{ (\lambda_1, \lambda_1, \lambda_2, \lambda_2, \ldots) \in \Delta_n \, : \, \lambda_i \geq 0, \, \sum_{i=1}^{\lfloor n/2 \rfloor} \lambda_i = 1/2 \}.

In particular, the set K_{A_n} is convex and we have that \lambda \prec (1/2, 1/2, 0, \ldots, 0) for all \lambda \in K_{A_n}. Hence, the minimum entropy of a vector inside K_{A_n} is 1 bit.


[ghp] A. Grudka, M. Horodecki and L. Pankowski. Constructive counterexamples to the additivity of the minimum output Rényi entropy of quantum channels for all p>2. J. Phys. A: Math. Theor. 43 425304.

Posted in quantum information theory | Leave a comment


A couple of days ago, I remembered the following fun fact from my high-school days in Romania:


First, note that I am using the European notation for periodic decimal expansions (or repeating decimals). What you get is a periodic expansion, where all the two-digit numbers from 00 to 99, except 98, appear in the periodic part. Ok, there seems to be some magic going on here, let us try to understand what is happening.
First, note that 9801 = 99^2, so probably there's nothing special about the 2 in there. Indeed, try

 \frac{1}{9^2} = \frac{1}{81} = 0,(012345679).

Good, let us go ahead and generalize this a little more. The 9 in there is the number of fingers you are left with when you lose one, so the same should be true for creatures anatomically different (by the way, there is ice on Mercury, and maybe more !):

 \frac{1}{\text{E1}_{16}} = \frac{1}{\text{15}_{16}^2} = 0,(012345679\text{ABCDF})_{16}.

Before stating and proving a general result, let us discuss the easiest case (for us humans), 1/81. The idea comes from [cgo] and the starting point is the formula

 \sum_{n=1}^\infty nx^{n-1} = \frac{1}{(1-x)^2},

which is the power series expansion of (1-x)^{-2} around 0. For x=1/10, we get

  \begin{array}{rcl}  \frac{1}{9^2} &=& \frac{1}{10}^2 \left[ 1 + \frac{2}{10} + \frac{3}{10^2} + \cdots \right] \\&=& \left[ \frac{0}{10} + \frac{1}{10^2} + \frac{2}{10^3} + \cdots + \frac{7}{10^8} + \frac{8}{10^9} +  \right. \\&& \qquad \left.  + \frac{9}{10^{10}} + \frac{10}{10^{11}} + \frac{11}{10^{12}} + \frac{12}{10^{13}} + \cdots \right]. \end{array}

At this point, the expression above starts to look like a decimal expansion - the problem is that some of the numerators in the brackets are not digits! To get around this, write

  \begin{array}{rcl}\frac{10}{10^{11}} &=& \frac{1}{10^{10}} + \frac{0}{10^{11}} \\ \frac{11}{10^{12}} &=&\frac{1}{10^{11}} + \frac{1}{10^{12}} \\ \frac{12}{10^{13}} &=& \frac{1}{10^{12}} + \frac{2}{10^{13}} \\ &\cdots \end{array}

to get

\begin{array}{rcl} \frac{1}{9^2} &=& \left[ \frac{0}{10} + \cdots + \frac{7}{10^8} + \frac{8}{10^9} + \frac{9}{10^{10}} + \left( \frac{1}{10^{10}} + \frac{0}{10^{11}} \right ) + \right. \\ && \qquad \left.  + \left( \frac{1}{10^{11}} + \frac{1}{10^{12}}\right ) + \left( \frac{1}{10^{12}} + \frac{2}{10^{13}} \right ) + \cdots \right]  \\ &=& \left[ \frac{0}{10} + \cdots + \frac{7}{10^8} + \frac{8}{10^9} + \left(\frac{9}{10^{10}} + \frac{1}{10^{10}}\right ) + \left( \frac{0}{10^{11}} + \frac{1}{10^{11}} \right )  + \right. \\ && \qquad \left.  +  \left( \frac{1}{10^{12}}+\frac{1}{10^{12}} \right ) + \frac{2}{10^{13}} + \cdots \right] \\ &=& \left[ \frac{0}{10} + \cdots + \frac{7}{10^8} + \frac{8}{10^9} + \frac{10}{10^{10}} + \frac{1}{10^{11}}+\frac{2}{10^{12}}+\cdots \right] \\ &=& \left[ \frac{0}{10} + \cdots + \frac{7}{10^8} + \frac{8}{10^9} + \left( \frac{1}{10^{9}} +\frac{0}{10^{10}} \right)+ \frac{1}{10^{11}}+\frac{2}{10^{12}}+\cdots \right] \\ &=& \left[ \frac{0}{10} + \cdots + \frac{7}{10^8} + \frac{9}{10^9} + \frac{0}{10^{10}} + \frac{1}{10^{11}}+\frac{2}{10^{12}}+\cdots \right],\end{array}

which is the announced formula. The general result can be stated as follows.

Proposition 1. Let b \geq 3 be a fixed basis. Then, when everything is written in basis b, for any n \geq 1, one has

 \begin{array}{rc}  \frac{1}{\overline{b-1} \, \overline{b-1}\cdots\overline{b-1} \, \overline{b-1}^{2}} = 0,(&00\cdots00 \\&00\cdots01 \\&00\cdots02 \\&\qquad \vdots\\ &\overline{b-1} \, \overline{b-1}\cdots\overline{b-1} \, \overline{b-4} \\ &\overline{b-1} \, \overline{b-1}\cdots\overline{b-1} \, \overline{b-3} \\ &\overline{b-1} \, \overline{b-1}\cdots\overline{b-1} \, \overline{b-1}), \end{array}

where each group containing \cdots in the expression above has n digits and \overline{x} denotes the digit 0 \leq x < b in basis b. Proof: We shall start from the RHS of the equation and work our way towards the LHS. Recall that a periodic decimal expansion in base b can be written as a fraction as follows:

 0,(\overline{x_{k-1}} , \overline{x_{k-2}} , \overline{x_{k-3}} \cdots \overline{x_{1}} , \overline{x_0} ) = \frac{\sum_{i=0}^{k-1} \overline{x_i} b^i}{ (b-1) \sum_{i=0}^{k-1} b^i}.

First, let us focus on the case n=1 and treat the general case at the end of the proof. In this particular case, the RHS of the equation in the statement is equal to

 0,(012\cdots \overline{b-3} , \overline{b-1}) = \frac{1+\sum_{i=0}^{b-2} (b-2-i)b^i}{(b-1)\sum_{i=0}^{b-2}b^i},

where the 1 in front of the sum stands for the fact that \overline{b-2} is replaced by \overline{b-1} as the last digit of the period. Using the formulas

  \begin{array}{rcl}  \sum_{i=0}^k b^i &=& \frac{b^{k+1}-1}{b-1}\\ \sum_{i=0}^k i b^i &=& \frac{b+b^{k+1}(kb-k-1)}{(b-1)^2}, \end{array}

we can write

  \begin{array}{rcl}  1+\sum_{i=0}^{b-2} (b-2-i)b^i &=& 1+(b-2)\frac{b^{b-1}-1}{b-1} - \\ && \quad - \frac{b+b^{b-1}[(b-2)b-(b-2)-1]}{(b-1)^2} \\ &=& \frac{b^{b-1}-1}{(b-1)^2}, \end{array}

from which the conclusion easily follows. For the general case, note that the following decimal expansion holds for groups \widetilde y_i of n digits:

 0,(\widetilde{y_{k-1}} , \widetilde{y_{k-2}} , \widetilde{y_{k-3}} \cdots \widetilde{y_{1}} , \widetilde{y_0} ) = \frac{\sum_{i=0}^{k-1} \widetilde{y_i} b^{ni}}{(b-1)\sum_{i=0}^{nk-1} b^i}.

The proof follows then the same steps as above.


[cgo] A. Cheer and D. Goldston, Explaining the decimal expansion of 1/81 using calculus. Mathematics and Computer Education, 25-3 (1991).

Posted in fun | 2 Comments