Magazine Cover
Download article (PDF)

This article is published open access.

MAG119pp. 57–66

Solved and unsolved problems

  • Michael Th. Rassias

    University of Zürich, Switzerland

Probability theory is nothing but common sense reduced to calculation.

Pierre-Simon Laplace (1749–1827)

The present column is devoted to Probability Theory and related topics.

I Six new problems – solutions solicited

Solutions will appear in a subsequent issue.


We take for our probability space (X,m)(X,m): the unit interval X=[0,1]X=[0,1] equipped with the Lebesgue measure mm defined on B(X)\mathcal{B}(X), the Borel subsets of XX and let (X,m,T)(X,m,T) be an invertible measure preserving transformation, that is T:X0X0T:X_{0}\to X_{0} is a bimeasurable bijection of some Borel set X0B(X)X_{0}\in\mathcal{B}(X) of full measure so that and m(TA)=m(T1A)=m(A)m(TA)=m(T^{-1}A)=m(A) for every AB(X)A\in\mathcal{B}(X).

Suppose also that TT is ergodic in the sense that the only TT-invariant Borel sets have either zero- or full measure (AB(X), TA=A  m(A)=0,1A\in\mathcal{B}(X),\ TA=A\ \Rightarrow\ m(A)=0,1).

Birkhoff’s ergodic theorem says that for every integrable function f:XRf:X\to\mathbb{R},

1nk=0n1fTkn E(f):=Xfdm a.s.\tfrac{1}{n}\sum_{k=0}^{n-1}f\circ T^{k}\xrightarrow[n\to\infty]{}\ \mathbb{E}(f):=\int_{X}fdm\ \text{a.s.}

The present exercise is concerned with the possibility of generalizing this. Throughout, (X,m,T)(X,m,T) is an arbitrary ergodic, measure-preserving transformation as above.

Warm-up 1

Show that if f:XRf:X\to\mathbb{R} is measurable, and

m([limnk=0n1fTk<])>0,m\left(\biggl[\varlimsup_{n\to\infty}\bigg|\sum_{k=0}^{n-1}f\circ T^{k}\bigg|<\infty\biggr]\right)>0,

then 1nk=0n1fTk\tfrac{1}{n}\sum_{k=0}^{n-1}f\circ T^{k} converges in R\mathbb{R} a.s.

Warm-up 1 is [1 P. Hagelstein, D. Herden and A. Stokolos, A theorem of Besicovitch and a generalization of the Birkhoff Ergodic Theorem. Proc. Amer. Math. Soc. Ser. B8, 52–59 (2021) , Lemma 1]. For a multidimensional version, see [1 P. Hagelstein, D. Herden and A. Stokolos, A theorem of Besicovitch and a generalization of the Birkhoff Ergodic Theorem. Proc. Amer. Math. Soc. Ser. B8, 52–59 (2021) , Conjecture 3].

Warm-up 2

Show that if f:XRf:X\to\mathbb{R} is as in Warm-up 1, then  g, h:XR\exists\ g,\ h:X\to\mathbb{R} measurable with hh bounded so that f=h+ggTnf=h+g-g\circ T^{n}.

Warm-up 2 is established by adapting the proof of [3 D. Volný and B. Weiss, Coboundaries in L0∞. Ann. Inst. H. Poincaré Probab. Statist.40, 771–778 (2004) , Theorem A].


Show that there is a measurable function f:XRf:X\to\mathbb{R} satisfying E(f)=\mathbb{E}(|f|)=\infty so that

1nk=0n1fTk\tfrac{1}{n}\sum_{k=0}^{n-1}f\circ T^{k}

converges in R\mathbb{R} a.s.

The existence of such ff for a specially constructed ergodic measure-preserving transformation is shown in [2 D. Tanny, A zero-one law for stationary sequences. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete30, 139–148 (1974) , example b]. The point here is to prove it for an arbitrary ergodic measure preserving transformation of (X,m)(X,m).

Jon Aaronson (Tel Aviv University, Israel)


Let (Ω,F,P)\left(\Omega,\mathcal{F},\mathbb{P}\right) be a probability space and {Xn:n1}\left\{X_{n}:n\geq 1\right\} a sequence of independent and identically distributed (i.i.d.) random variables on Ω\Omega. Assume that there exists a sequence of positive numbers {bn:n1}\left\{b_{n}:n\geq 1\right\} such that bnnbn+1n+1\frac{b_{n}}{n}\leq\frac{b_{n+1}}{n+1} for every n1n\geq 1, limnbnn=\lim_{n\rightarrow\infty}\frac{b_{n}}{n}=\infty, and n=1P(Xnbn)<\sum_{n=1}^{\infty}\mathbb{P}\left(\left|X_{n}\right|\geq b_{n}\right)<\infty. Prove that if Sn:=j=1nXjS_{n}:=\sum_{j=1}^{n}X_{j} for each n1n\geq 1, then

limnSnbn=0 almost surely.\lim_{n\rightarrow\infty}\frac{S_{n}}{b_{n}}=0\text{ almost surely}.

Comment. The desired statement says that if such a sequence {bn:n1}\left\{b_{n}:n\geq 1\right\} exists, then {Xn:n1}\left\{X_{n}:n\geq 1\right\} satisfies the (generalized) Strong Law of Large Numbers (SLLN) when averaged by {bn:n1}\left\{b_{n}:n\geq 1\right\}. If XnL1(P)X_{n}\in L^{1}\left(\mathbb{P}\right) for every n1n\geq 1, then the desired statement follows trivially from Kolmogorov’s SLLN, since in that case, with probability one, we have


and hence


must converge to 0 under the assumptions on {bn:n1}\left\{b_{n}:n\geq 1\right\}. Therefore, the desired statement can be viewed as an alternative to Kolmogorov’s SLLN for i.i.d. random variables that are not integrable.

Linan Chen (McGill University, Montreal, Quebec, Canada)


In Beetown, the bees have a strict rule: all clubs must have exactly kk membees. Clubs are not necessarily disjoint. Let b(k)b(k) be the smallest number of clubs that it is possible for the nk2n\geq k^{2} bees to form, such that the set of clubs has the property that no matter how the bees divide themselves into two teams to play beeball, there will always be a club all of whose membees are on the same team. Prove that

2k1b(k)Ck22k2^{k-1}\leq b(k)\leq Ck^{2}\cdot 2^{k}

for some constant C>0C>0.

Rob Morris (IMPA, Rio de Janeiro, Brasil)


NN agents are in a room with a server, and each agent is looking to get served, at which point the agent leaves the room. At any discrete time-step, each agent may choose to either shout or stay quiet, and an agent gets served in that round if (and only if) that agent is the only one to have shouted. The agents are indistinguishable to each other at the start, but at each subsequent step, every agent gets to see who has shouted and who has not. If all the agents are required to use the same randomised strategy, show that the minimum time expectation to clear the room is N+(2+o(1))log2NN+\bigl(2+o(1)\bigr)\log_{2}N.

Bhargav Narayanan (Rutgers University, Piscataway, USA)


Consider the following sequence of partitions of the unit interval II: First, define π1\pi_{1} to be the partition of II into two intervals, a red interval of length 1/31/3 and a blue one of length 2/32/3. Next, for any m>1m>1, define πm+1\pi_{m+1} to be the partition derived from πm\pi_{m} by splitting all intervals of maximal length in πm\pi_{m}, each into two intervals, a red one of ratio 1/31/3 and a blue one of ratio 2/32/3, just as in the first step. For example π2\pi_{2} consists of three intervals of lengths 1/31/3 (red), 2/92/9 (red) and 4/94/9 (blue), the last two are the result of splitting the blue interval in π1\pi_{1}. The figure below illustrates π1,,π4\pi_{1},\ldots,\pi_{4}, from top to bottom.

Let mNm\in\mathbb{N} and consider the mm-th partition πm\pi_{m}.

  1. Choose an interval in πm\pi_{m} uniformly at random. Let RmR_{m} be the probability you chose a red interval, does the sequence (Rm)mN(R_{m})_{m\in\mathbb{N}} converge? If so, what is the limit?

  2. Choose a point in II uniformly at random. Let AmA_{m} be the probability that the point is colored red, does the sequence (Am)mN(A_{m})_{m\in\mathbb{N}} converge? If so, what is the limit?

Yotam Smilansky (Rutgers University, NJ, USA)


Prove that there exist c<1c<1 and ϵ>0\epsilon>0 such that if A1,,AkA_{1},\dots,A_{k} are increasing events of independent boolean random variables with Pr(Ai)<ϵ\Pr(A_{i})<\epsilon for all ii, then

Pr(exactly one of A1,,Ak occurs)c.\Pr(\text{exactly one of $A_{1},\dots,A_{k}$ occurs})\leq c.

(What is the smallest cc that you can prove?)

Here A{0,1}nA\subset\{0,1\}^{n} is an “increasing event” if whenever xAx\in A, then the vector obtained by changing any coordinates of xx from 00 to 11 still lies in AA.

A useful fact is Harris inequality, which says that for increasing events AA and BB of boolean random variables, Pr(AB)Pr(A)Pr(B)\Pr(A\cap B)\geq\Pr(A)\operatorname{\Pr}(B).

I learned of this problem from Jeff Kahn.

Yufei Zhao (MIT, Cambridge, USA)

II Open problems

Equidistributed orbits in 2-adic integers

by Hillel Furstenberg (Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Israel)

The Collatz problem, also known as the 3x+13x+1 problem is very well known. We will formulate a general conjecture motivated by the Collatz problem, as well as another related conjecture. Both have to do with ordinary integer sequences which should be regarded as subsequences of the 2-adics. First some notation. Every positive integer can be written as x=g(x)h(x),x=g(x)h(x), with g(x)g(x) a power of 22, and h(x)h(x) odd. We define a transformation on N={1,2,3,}\mathbb{N}=\{1,2,3,\ldots\} by


The mysterious phenomenon is that every orbit seems to reach the fixed point 1. The Collatz problem is to prove this. Probability enters as a heuristic explanation of why the orbit is finite, always reaching some cycle. A more “robust” phenomenon is that for any odd bb, if we were to set


the orbits are finite.

We point out that it is not hard to show that bb can be chosen so that the corresponding transformation has as many distinct cycles as we like. Nevertheless it seems that all orbits are finite. We propose a still more general conjecture which implies this. For this we need the notion of “equidistribution in the odd 2-adics”.

If we fix a natural number kk, every odd integer lies in one of the 2(k1)2^{(k-1)} arithmetic progressions

Pj,k=j+2kZ,j=1,3,5,,2k1.P_{j,k}=j+2^{k}Z,\quad j=1,3,5,\ldots,2^{k}-1.

Definition. A sequence SS of odd integers is equidistributed in the odd 2-adics if for every jj, kk, the proportion of SS in Pj,kP_{j,k} is (1/2)(k1)(1/2)^{(k-1)}. “Proportion” means the relative density.

Now define


where aa and bb are odd integers, a>2a>2, b>0b>0.


Conjecture A. For any natural odd numbers a,b,x,a,b,x, the orbit of xx under Ta,bT_{a,b} is either finite or equidistributed in the odd 2-adics.

Consequence: All the orbits of T3,bT_{3,b} are finite.

To prove this one shows that the assumption of an infinite equidistributed orbit leads to a contradiction. This follows from the fact that on account of equidistribution, the expectation of logg(x)\log g(x) is log4\log 4. The idea now is to observe that for large xx, the effect of applying T3,bT_{3,b} is – on the average – multiplying by 3 and dividing by 4. This can be made precise to show that an equidistributed, infinite orbit is an impossibility.

The next conjecture involves equidistribution in the full compact group of 2-adics. Define R(x)=3[x/2]R(x)=3[x/2]. Here as usual [z][z] denotes the largest integer less than zz. We have

R(0)=R(1)=0, R(2)=3, R(3)=3.R(0)=R(1)=0,\ R(2)=3,\ R(3)=3.

But for x>3x>3,


so that for x>3,x>3, the orbit of xx will be infinite.


Conjecture B. For any x>3x>3, the orbit under RR is equidistributed in the 2-adics.

In particular, this would imply that in every such orbit, even and odd integers appear with the same frequency. However, we are unable to verify this for any orbit.

Here too we can consider RaR_{a} defined by

Ra(x)=a[x/2], for odd a.R_{a}(x)=a[x/2],\quad\text{ for odd }a.

We expect the same phenomenon: orbits that are either finite or equidistributed. Little numerical work has been done on this conjecture.

III Solutions


Let Cn{\mathbb{C}}^{n} stand for the space of complex columnnn-vectors, and let Mn{\mathbb{M}}_{n} stand for the space of complex n×nn\times n matrices.

The inner product xy\langle x|y\rangle of x,yCnx,y\in{\mathbb{C}}^{n} is defined as

xy=xy(matrix product).\langle x|y\rangle=x^{*}y\quad(\text{matrix product}).

Therefore xy\langle x|y\rangle is linear in yy and conjugate linear in xx.

Let A,BA,B be n×mn\times m complex matrices. Write them as

A=[a1,,am]andB=[b1,,bm]A=[a_{1},\ldots,a_{m}]\quad{\rm and}\quad B=[b_{1},\ldots,b_{m}]

with aj,bjCn (j=1,2,,m)a_{j},b_{j}\in{\mathbb{C}}^{n}\ (j=1,2,\ldots,m).

Then it is immediate from the definition of matrix multiplication that

AB=[ajbk]j,k=1m  Mm.A^{*}B=\bigl[\langle a_{j}|b_{k}\rangle\bigr]_{j,k=1}^{m}\ \in\ {\mathbb{M}}_{m}.

Show the following relation:

AB=j=1majbj  MnAB^{*}=\sum_{j=1}^{m}a_{j}b_{j}^{*}\ \in\ {\mathbb{M}}_{n}

where each product ajbj (j=1,,n)a_{j}b_{j}^{*}\ (j=1,\ldots,n) is a rank-one matrix in Mn{\mathbb{M}}_{n}.

T. Ando (Hokkaido University, Sapporo, Japan)

Solution by the proposer

Consider the canonical orthonormal basis in Cn{\mathbb{C}}^{n};


Then it suffices to prove the identity in the assertion for the case

A=[0,,0,ej(p),0,,0], 1jn,  1pmA=\bigl[0,\ldots,0,\overset{(p)}{e_{j}},0,\ldots,0\bigr],\quad\exists\ 1\leq j\leq n,\ \exists\ 1\leq p\leq m


B=[0,,0,ek(q),0,,0], 1kn,  1qmB=\bigl[0,\ldots,0,\overset{(q)}{e_{k}},0,\ldots,0\bigr],\quad\exists\ 1\leq k\leq n,\ \exists\ 1\leq q\leq m

In this case

AB = δp,qejekAB^{*}\ =\ \delta_{p,q}e_{j}e_{k}^{*}



as expected.

Also solved by John N. Daras (Athens, Greece), Muhammad Thoriq (Yogyakarta, Indonesia), and Socratis Varelogiannis (France)


Let pp and qq be two distinct primes with q>pq>p and GG a group of exponent qq for which the map fp:GGf_{p}:G\to G defined by fp(x)=xpf_{p}(x)=x^{p}, for all xGx\in G, is an endomorphism. Show that GG is an abelian group.

Dorin Andrica and George Cătălin Ţurcaş (Babeş-Bolyai University, Cluj-Napoca, Romania)

Solution by the proposer

We first prove the following auxiliary result.

Claim. The map fk:GGf_{k}:G\to G defined by fk(x)=xkf_{k}(x)=x^{k} is an endomorphism for all kZk\in\mathbb{Z} with k1(modp(p1))k\equiv 1\pmod{p(p-1)}.

First, it is not hard to see that (xy)p=xpyp(xy)^{p}=x^{p}y^{p} implies that (yx)p1=xp1yp1(yx)^{p-1}=x^{p-1}y^{p-1}, for all x,yGx,y\in G. Then we observe that

(xy)(p1)2=(yp1xp1)p1=x(p1)2y(p1)2,x,yG.(xy)^{(p-1)^{2}}=(y^{p-1}x^{p-1})^{p-1}=x^{(p-1)^{2}}y^{(p-1)^{2}},\quad\forall x,y\in G.

It is also easy to show that

xpyp1=yp1xp,x,yG.x^{p}y^{p-1}=y^{p-1}x^{p},\quad\forall x,y\in G.

Using the latter, we see that


for all x,yGx,y\in G. We just showed that fp(p1)f_{p(p-1)} is an endomorphism of GG. We proceed by showing that fp2p+1f_{p^{2}-p+1} is also an endomorphism.

For every x,yGx,y\in G, we have

(xy)p2p+1=(xy)p(xy)(p1)2=xpypx(p1)2y(p1)2.(xy)^{p^{2}-p+1}=(xy)^{p}\cdot(xy)^{(p-1)^{2}}=x^{p}\cdot y^{p}\cdot x^{(p-1)^{2}}\cdot y^{(p-1)^{2}}.

In the above chain of equalities we just used that fpf_{p} and fp(p1)f_{p(p-1)} are endomorphisms. We previously mentioned (1) that the middle terms commute, which shows that fp2p+1f_{p^{2}-p+1} is an endomorphism of GG.

Observe that for all x,yGx,y\in G we have


which implies that xp2py=yxp2px^{p^{2}-p}y=yx^{p^{2}-p}. It follows that xp2px^{p^{2}-p} belongs to the center of GG, for any xGx\in G.

We are now ready to prove our claim. Let k=1+mp(p1)k=1+mp(p-1) for some mZm\in\mathbb{Z}. Then


The claim is proved.

Since gcd(q,p(p1))=1\gcd\bigl(q,p(p-1)\bigr)=1, by the Chinese Remainder Theorem we know that there is an integer nn such that

{n1(mod[)]p(p1),n2(modq).\left\{\begin{array}{l}n\equiv 1\pmod{[}\big]{p(p-1)},\\ n\equiv 2\pmod{q}.\end{array}\right.

We therefore have that the map fn:GGf_{n}:G\to G defined by fn(x)=xnf_{n}(x)=x^{n} is an endormorphism. However, xn=x2x^{n}=x^{2} for all xGx\in G, since qq is the exponent of GG. Now, since f2(x)=x2f_{2}(x)=x^{2} is an endomorphism of GG, it follows that for all x,yGx,y\in G we have (yx)2=y2x2yxyx=y2x2xy=yx(yx)^{2}=y^{2}x^{2}\Leftrightarrow yxyx=y^{2}x^{2}\Leftrightarrow xy=yx.

Remark. The conclusion also holds if pp and qq are not prime. One just needs GG to have a finite exponent qq such that qq and p2pp^{2}-p are coprime.

Also solved by Mihaly Bencze (Romania), Tomek Jedrzejak (University of Szczecin, Poland), and Efstathios S. Louridas (Athens, Greece)


Let (G,)(G,\cdot) be a group with the property that there is an integer n1n\geq 1 such that the map fn:GG,fn(x)=xnf_{n}:G\to G,f_{n}(x)=x^{n} is injective and the map

fn+1:GG,fn+1(x)=xn+1f_{n+1}:G\to G,f_{n+1}(x)=x^{n+1}

is a surjective endomorphism. Prove that GG is an abelian group.

Dorin Andrica and George Cătălin Ţurcaş (Babeş-Bolyai University, Cluj-Napoca, Romania)

Solution by the proposer

From the second hypothesis we have


which implies that

(yx)n=xnynfor all x,yG.(yx)^{n}=x^{n}y^{n}\quad\text{for all }x,y\in G.

Using the above, we see that x(yx)n=xn+1ynx(yx)^{n}=x^{n+1}y^{n} for all x,yGx,y\in G. On the other hand,

x(yx)n=(xy)nx=ynxn+1for all x,yG.x(yx)^{n}=(xy)^{n}x=y^{n}x^{n+1}\quad\text{for all }x,y\in G.

We just showed that

xn+1yn=ynxn+1for all x,yG.x^{n+1}y^{n}=y^{n}x^{n+1}\quad\text{for all }x,y\in G.

Now, using the surjectivity of fn+1f_{n+1} we obtain that for every zGz\in G there is xGx\in G such that fn+1(x)=zf_{n+1}(x)=z, that is xn+1=zx^{n+1}=z. The relation (2) can be written as zyn=ynzzy^{n}=y^{n}z, for all y,zGy,z\in G. From this relation we get

y(xy)n=(xy)nyfor all x,yG,y(xy)^{n}=(xy)^{n}y\quad\text{for all }x,y\in G,

that is


This is equivalent to


hence (yx)n=(xy)n(yx)^{n}=(xy)^{n} and the conclusion follows from the injectivity of the map fnf_{n}.

Also solved by John N. Daras (Athens, Greece), Tomek Jedrzejak (University of Szczecin, Poland), Muhammad Thoriq (Yogyakarta, Indonesia), and Socratis Varelogiannis (France)


Let AA and BMatk(K)B\in\operatorname{Mat}_{k}(K) be two matrices over a field KK. We say that AA and BB are similar if there exists an invertible matrix CGLk(K)C\in\operatorname{GL}_{k}(K) such that B=C1ACB=C^{-1}AC.

Let AA and BGLk(Q)B\in\operatorname{GL}_{k}(\mathbb{Q}) be two similar invertible matrices over the field of rational numbers Q\mathbb{Q}. Assume that for some integer ll, we have Al+1B=BAl.A^{l+1}B=BA^{l}. Then AA and BB are the identity matrices.

Andrei Jaikin-Zapirain (Departamento de Matemáticas, Universidad Autónoma de Madrid and Instituto de Ciencias Matemáticas, CSIC-UAM-UC3M-UCM, Spain) and Dmitri Piontkovski (Faculty of Economic Sciences, Moscow Higher School of Economics, Russia)

Solution by the proposer

Consider first a finite group GG having three elements x,y,zx,y,z satisfying

y=z1xzandxl+1y=yxl.y=z^{-1}xz\quad\text{and}\quad x^{l+1}y=yx^{l}.

Let us show that x=y=1x=y=1.

By way of contradiction we assume that the order of xx is n>1n>1. Since xx and yy are conjugate, the order of yy is also nn. The cases l=0l=0 and l=1l=-1 are trivial, so we assume that l0,1l\neq 0,-1.

Let GCD(a,b)\operatorname{GCD}(a,b) denote the greatest common divisor of two integers aa and bb. The order of xlx^{l} is n/GCD(n,l){n}/{\operatorname{GCD}(n,l)} and the order of xl+1x^{l+1} is n/GCD(n,l+1){n}/{\operatorname{GCD}(n,l+1)}. Since xlx^{l} and xl+1x^{l+1} are conjugate, their orders coincide. Therefore, GCD(n,l)=GCD(n,l+1)\operatorname{GCD}(n,l)=\operatorname{GCD}(n,l+1). Thus, since ll and l+1l+1 are coprime, we obtain that


This implies that there exists a natural number q>1q>1, which is coprime with nn and such that qll+1(modn)ql\equiv l+1\pmod{n}. Note that yxly1=xlqyx^{l}y^{-1}=x^{lq}. Therefore,


Since the order of xlx^{l} is nn, nn divides qn1q^{n}-1. Let pp be the smallest prime divisor of nn. Then the integers nn and p1p-1 are coprime. Hence there exist a,bZa,b\in\mathbb{Z} such that an+b(p1)=1an+b(p-1)=1. Observe also that

qnqp11(modp).q^{n}\equiv q^{p-1}\equiv 1\pmod{p}.

Therefore, qan+b(p1)1(modp)q^{an+b(p-1)}\equiv 1\pmod{p}, and so

llqan+b(p1)lql+1(modp).l\equiv l\cdot q^{an+b(p-1)}\equiv l\cdot q\equiv l+1\pmod{p}.

We have arrived at a contradiction, which proves that x=y=1x=y=1.

Now let us come back to the original problem. Since AA and BB are similar, there exists an invertible matrix CGLk(Q)C\in\operatorname{GL}_{k}(\mathbb{Q}) such that B=C1ACB=C^{-1}AC. Let FF be the subgroup of GLk(Q)\operatorname{GL}_{k}(\mathbb{Q}) generated by AA and CC. Let mm be such that AA, A1A^{-1},CC,C1GLk(Z[1m])C^{-1}\in\operatorname{GL}_{k}\bigl(\mathbb{Z}[\frac{1}{m}]\bigr). Then FGLk(Z[1m])F\leq\operatorname{GL}_{k}\bigl(\mathbb{Z}[\frac{1}{m}]\bigr).

Recall that a group HH is called residually finite if for every non-trivial element hHh\in H there exists a finite quotient GG of HH such that the image of hh in GG is non-trivial. Observe that the group GLk(Z[1m]\operatorname{GL}_{k}(\mathbb{Z}[\frac{1}{m}] is residually finite (consider the natural maps from GLk(Z[1m])\operatorname{GL}_{k}(\mathbb{Z}[\frac{1}{m}]) to GLk(Fp)\operatorname{GL}_{k}(\mathbb{F}_{p}), where pp are prime numbers coprime with mm). Therefore we conclude that the group FF is also residually finite.

If AA is not the identity matrix, then there exists a finite quotient GG of FF such that the image of AA in GG is not trivial. But this contradicts what we proved at the beginning. Thus AA, so also BB, are the identity matrices.

Remark. The problem is inspired by a result of Baumslag [4 G. Baumslag, A non-cyclic one-relator group all of whose finite quotients are cyclic. J. Austral. Math. Soc.10, 497–498 (1969) ] where he constructed a two-generator one-relator group having only cyclic finite quotients. Instead of Q\mathbb{Q} we could assume that the matrices AA and BB in the problem are considered over an arbitrary field KK. In this case the problem can be solved using a theorem of Malcev [5 A. Malcev, On isomorphic matrix representations of infinite groups. Rec. Math. [Mat. Sbornik] N.S.8 (50), 405–422 (1940) ] where he proved that any finitely generated group linear over a field is residually finite.

Also solved by John N. Daras (Athens, Greece), George Miliakos (Sparta, Greece), and Moubinool Omarjee (Paris, France)


We are trying to hang a picture on a wall. The picture has a piece of string attached to it forming a loop, and there are 33 nails in the wall that we can wrap the string around. We want to hang the picture so that it does not fall down, but it will upon the removal of any of the 33 nails.

Dawid Kielak (Mathematical Institute, University of Oxford, UK)

Solution by the proposer

Let us start with 22 nails. Wrapping a loop around two nails in some way is equivalent to choosing an element of π1(C{0,1})\pi_{1}(\mathbb{C}\smallsetminus\{0,1\}). Of course, this fundamental group is the free group F2=F(a,b)F_{2}=F(a,b) of rank 22, with generators corresponding to loops going around one of the nails.

If the picture is not to fall down, we need a non-trivial element xx of F2F_{2}. The condition that the picture is supposed to fall when any of the nails is removed means that the image of xx in F2/ ⁣a ⁣ZF_{2}/\langle\!\langle a\rangle\!\rangle\cong\mathbb{Z} and in F2/ ⁣b ⁣ZF_{2}/\langle\!\langle b\rangle\!\rangle\cong\mathbb{Z} has to be trivial. We immediately recognise that x=[a,b]x=[a,b] does the trick.

For three nails, we can take

[[a,b],c]F(a,b,c)π1(C{0,1,2}).\bigl[[a,b],c\bigr]\in F(a,b,c)\cong\pi_{1}(\mathbb{C}\smallsetminus\{0,1,2\}).

The solution easily generalises to nn nails.

Also solved by Mihaly Bencze (Romania), and George Miliakos (Sparta, Greece)


Given a natural number nn and a field kk, let Mn(k)M_{n}(k) be the full n×nn\times n matrix algebra over kk. A matrix (aij)Mn(k)(a_{ij})\in M_{n}(k) is said to be centrosymmetric if


for 1i,jn1\leq i,j\leq n. Let Cn(k)C_{n}(k) denote the set of all centrosymmetric matrices in Mn(k)M_{n}(k). Then Cn(k)C_{n}(k) is a subalgebra of Mn(k)M_{n}(k), called centrosymmetric matrix algebra over kk of degree nn. Centrosymmetric matrices have a long history (see [6 A. Aitken, Determinants and matrices. Oliver and Boyd, Edinburgh (1939) , 10 T. Muir, A treatise on the theory of determinants. Revised and enlarged by William H. Metzler, Dover Publications, Inc., New York (1960) ]) and applications in many areas, such as in Markov processes, engineering problems and quantum physics (see [7 A. R. Collar, On centrosymmetric and centroskew matrices. Quart. J. Mech. Appl. Math.15, 265–281 (1962) , 8 L. Datta and S. D. Morgera, On the reducibility of centrosymmetric matrices – applications in engineering problems. Circuits Systems Signal Process.8, 71–96 (1989) , 9 I. J. Good, The inverse of a centrosymmetric matrix. Technometrics12, 925–928 (1970) , 11 J. R. Weaver, Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors. Amer. Math. Monthly92, 711–717 (1985) ]). In the representation theory of algebras, a fundamental problem for a finite-dimensional algebra is to know if it has finitely many nonisomorphic indecomposable modules (or in other terminology, representations). In our case, the concrete problem on Cn(k)C_{n}(k) reads as follows.

Does Cn(k)C_{n}(k) have finitely many nonisomorphic indecomposable modules? If yes, what is the number?

Changchang Xi (School of Mathematical Sciences, Capital Normal University, Beijing, and College of Mathematics and Information Science, Henan Normal University, Xinxiang, China)

Solution by the proposer


To solve the problem, we use the fact that two algebras have the same number of nonisomorphic indecomposable modules if their module categories are equivalent. In our case of Cn(k)C_{n}(k), a practical way is to look for a decomposition of Cn(k)C_{n}(k) as a direct sum of indecomposable left ideals, and then take the direct sum of representives for each isomorphism classes of indecomposable left ideals. The endomorphism algebra of this direct sum of representives is called the basic algebra of Cn(k)C_{n}(k), denoted B0(n,k)B_{0}(n,k). Then Cn(k)C_{n}(k) and B0(n,k)B_{0}(n,k) have equivalent module categories, and therefore they have the same number of nonisomorphic indecomposable modules.


Let InI_{n} be the identity matrix in Mn(k)M_{n}(k), eije_{ij} be the n×nn\times n matrix with (i,j)(i,j)-entry 11 and other entries 00, and

fi=eii+en+1i,n+1i for 1in.f_{i}=e_{ii}+e_{n+1-i,n+1-i}\text{ for $1\leq i\leq n$.}

Then fiCn(k)f_{i}\in C_{n}(k). Calculations show that, for n=2mn=2m,

  1. In=f1++fmI_{n}=f_{1}+\cdots+f_{m}, fifj=δijfif_{i}f_{j}=\delta_{ij}f_{i}, where δij\delta_{ij} is the Kronecker symbol,

  2. Cn(k)f1Cn(k)f2Cn(k)fmC_{n}(k)f_{1}\simeq C_{n}(k)f_{2}\simeq\cdots\simeq C_{n}(k)f_{m} as left ideals, and

  3. dimk(C2m(k)=2m2{}_{k}(C_{2m}(k)=2m^{2};

and, for n=2m+1n=2m+1,

  1. In=f1++fm+em+1,m+1I_{n}=f_{1}+\cdots+f_{m}+e_{m+1,m+1}, fifj=δijfif_{i}f_{j}=\delta_{ij}f_{i}, where δij\delta_{ij} is the Kronecker symbol, and

  2. Cn(k)f1Cn(k)fmC_{n}(k)f_{1}\simeq\cdots\simeq C_{n}(k)f_{m} as left ideals, and

  3. dimk(C2m+1(k)=2m2+2m+1{}_{k}(C_{2m+1}(k)=2m^{2}+2m+1.





Further calculations lead to

B0(2m,k)C2(k),  B0(2m+1,k)C3(k)   for all m1.B_{0}(2m,k)\simeq C_{2}(k),\;B_{0}(2m+1,k)\simeq C_{3}(k)\;\text{ for all }m\geq 1.


We give quiver presentations of B0(n,k)B_{0}(n,k) (see [12 C. Xi and S. Yin, Cellularity of centrosymmetric matrix algebras and Frobenius extensions. Linear Algebra Appl.590, 317–329 (2020) ]).

Clearly, B0(1,k)=k  B_{0}(1,k)=k\;\bullet. If char(k)2(k)\neq 2, then B0(2,k)=k()B_{0}(2,k)=k(\bullet\quad\bullet) and B0(3,k)k()B_{0}(3,k)\simeq k(\bullet\quad\bullet). If char(k)=2(k)=2, then From these quiver presentations of the basic algebras, we can draw their Auslander–Reiten quivers and gain a complete answer to the above problem.

  1. C1(k)C_{1}(k) has exactly 11 nonisomorphic indecomposable module.

  2. If ch(k)2(k)\neq 2, then Cn(k)C_{n}(k) has exactly 22 nonisomorphic indecomposable modules for all n2n\geq 2.

  3. If ch(k)=2(k)=2, then C2m(k)C_{2m}(k) has exactly 22 nonisomorphic indecomposable modules for all m1m\geq 1, and C2m+1(k)C_{2m+1}(k) has exactly 55 nonisomorphic indecomposable modules for all m1m\geq 1.

An additional interesting problem (not intimately connected to Algebra)

Intervals of monotonic changes in a polynomial are located between the roots of its derivative. A derivative of a polynomial is also a polynomial, although of a lesser degree. Using these considerations, construct an algorithm for calculating the real roots of the quadratic equation. Improve it to calculate the real roots of a polynomial of the third, fourth and generally arbitrary degree.

Igor Kostin (Moscow, Russian Federation)

Solution by the proposer

We assume that the coefficient at x2x^{2} of the square polynomial is greater than zero. We need to find the derivative of this polynomial.

This is a linear function and we can easily find its root. Let us denote it by xmin.

It is clear that if the value of the initial square polynomial at xmin is greater than zero, then such a polynomial has no real roots. Otherwise, we will look for an argument xref such that this polynomial is greater than zero. An easy way to find such an argument is to step back from xmin by some step and check the value of the polynomial in such a step.

If the calculated value of the polynomial is greater than zero, then the search is completed, otherwise we will continue to retreat, each time doubling the value of the step of the retreat. Having obtained xref, we find the root by the standard dichotomy method, dividing in half the segment between xmin and xref.

It is convenient to end the dichotomy process when, in the machine representation, the point dividing the segment in half coincides with one of the ends of the original segment. Due to the finite precision of real numbers, this will happen sooner or later on any computer.

We repeat the above method for calculating the root twice, departing from xmin in different directions.

It is now clear that in order to calculate the roots of a polynomial of third degree, one must first calculate its derivative polynomial and find the roots of this square polynomial.

These roots will determine the boundaries of the intervals of monotonic changes in the initial polynomial of third degree. The roots of this initial polynomial will be found by the dichotomy method on the segments of monotonic variation calculated in this way.

It is clear that the ladder of the described possibilities rises, in principle, to a polynomial of an arbitrarily large degree. Of course, the complete solution to this problem should be a computer program that implements the verbal instructions listed here. In practice, the capabilities of such an algorithm are limited in that the counting time increases with the degree of the original polynomial.

Finally, we note that the xref points replacing the infinity value for the boundaries of the segments of the monotonicity of the polynomial can be calculated in a less primitive way than the step-by-step search with doubling of the step considered above. We normalize the polynomial so that the coefficient of the highest power of the argument is equal to one.

Let MM be the largest modulo value among all its coefficients. If the argument xx of the polynomial is greater than M+2M+2, then the value of the polynomial is greater than 11. To prove this, consider the calculation of the polynomial


by the Horner scheme.

At the first step we calculate


and it is obvious that p[1]>1.p[1]>1. In fact even if k[n1]<0,k[n-1]<0, it does not exceed MM in absolute value.

At the second step we calculate


and again it is obvious that p[2]>1.p[2]>1.

The same holds in the following steps.

At the last step we compute


and finally obtain p(x)>1.p(x)>1. Thus, if one needs to set a representative value of the polynomial with an infinite value of the argument, one should take the argument equal to M+2.M+2.

Solution to part (a) of Open problem 137* proposed by Ovidiu Furdui (Romania), September 2014 Issue of the EMS Newsletter

Solution by Seán M. Stewart (Bomaderry, NSW, Australia)

Denote the integral to be found in (a) by II. In terms of known constants its value is:

I=8ππ28+π2log2+2(log2)26log22G.I=8-\pi-\frac{\pi^{2}}{8}+\frac{\pi}{2}\log 2+2(\log 2)^{2}-6\log 2-2\mathbf{G}.

Here G\mathbf{G} is Catalan’s constant defined by n=0(1)n(2n+1)2\sum_{n=0}^{\infty}\frac{(-1)^{n}}{(2n+1)^{2}}.

We first establish a number of preliminary results before evaluating the integral. The nnth harmonic number is defined by

Hn=k=1n1k,nN.H_{n}=\sum_{k=1}^{n}\frac{1}{k},\quad n\in\mathbb{N}.

By convention, H00H_{0}\equiv 0. The harmonic numbers satisfy the following recurrence relation


In terms of the harmonic numbers the following finite sum can be written as


The harmonic numbers are related to the digamma function by (see entry 5.4.14 in [13 F. W. J. Olver, D. W. Lozier, R. F. Boisvert and C. W. Clark (eds.), NIST Handbook of mathematical functions. U.S. Department of Commerce, National Institute of Standards and Technology, Washington, DC; Cambridge University Press, Cambridge (2010) ])


Here γ\gamma is the Euler–Mascheroni constant. This allows the harmonic numbers to be analytically continued to all xR,x1,2,3,x\in\mathbb{R},x\neq-1,-2,-3,\ldots. The functional relation for the digamma function is


For half-integer arguments the digamma function takes the values (see entry 5.4.15 in [13 F. W. J. Olver, D. W. Lozier, R. F. Boisvert and C. W. Clark (eds.), NIST Handbook of mathematical functions. U.S. Department of Commerce, National Institute of Standards and Technology, Washington, DC; Cambridge University Press, Cambridge (2010) ])

ψ(n+12)=γ2log2+2k=1n12k1.\psi\left(n+\frac{1}{2}\right)=-\gamma-2\log 2+2\sum_{k=1}^{n}\frac{1}{2k-1}.

Replacing nn with n+12n+\frac{1}{2} in (4) we see that


where we have made use of the functional for the digamma function. In view of (6) we may rewrite this as

Hn+12=2log2+22n+1+2k=1n12k1=2log2+2k=1n+112k1.H_{n+\frac{1}{2}}=-2\log 2+\frac{2}{2n+1}+2\sum_{k=1}^{n}\frac{1}{2k-1}=-2\log 2+2\sum_{k=1}^{n+1}\frac{1}{2k-1}.

By applying (3), in terms of harmonic numbers this can be expressed as

Hn+12=2H2n+2Hn+12log2,H_{n+\frac{1}{2}}=2H_{2n+2}-H_{n+1}-2\log 2,

which reduces to

Hn+12=2H2n+1Hn2log2,H_{n+\frac{1}{2}}=2H_{2n+1}-H_{n}-2\log 2,

after the recurrence relation for the harmonic numbers is applied to each of the harmonic number terms that appear.

Two results from Cauchy products for power series will prove useful. The first is

arctan2(x)=n=1(1)nn(H2n12Hn)x2n,x1.\arctan^{2}(x)=-\sum_{n=1}^{\infty}\frac{(-1)^{n}}{n}\left(H_{2n}-\frac{1}{2}H_{n}\right)x^{2n},\qquad|x|\leqslant 1.

Showing this we have


where we have made use of the partial fraction decomposition of

1(2k+1)(2n2k+1)=12(n+1)(2k+1)12(n+1)(2k2n1).\frac{1}{(2k+1)(2n-2k+1)}\\ =\frac{1}{2(n+1)(2k+1)}-\frac{1}{2(n+1)(2k-2n-1)}.

Reindexing the second sum knkk\mapsto n-k we have


Reindexing the infinite sum nn1n\mapsto n-1 and the finite sum kk1k\mapsto k-1 yields


with the desired result then following on application of (3).

The second Cauchy product for power series is

xarctanx1+x2=n=1(1)n+1(H2n12Hn)x2n,x<1.\frac{x\arctan x}{1+x^{2}}=\sum_{n=1}^{\infty}(-1)^{n+1}\left(H_{2n}-\frac{1}{2}H_{n}\right)x^{2n},\quad|x|<1.

Showing this we have

xarctanx1+x2=x2(n=0(1)nx2n)(n=0(1)nx2n2n+1)\displaystyle\frac{x\arctan x}{1+x^{2}}=x^{2}\left(\sum_{n=0}^{\infty}(-1)^{n}x^{2n}\right)\cdot\left(\sum_{n=0}^{\infty}\frac{(-1)^{n}x^{2n}}{2n+1}\right)

where (3) has been used. The desired result then follows after a reindexing of nn1n\mapsto n-1.

Turning our attention to the integral II we have

I=01log(1x2)n=1(1)nx2nndx\displaystyle I=-\int_{0}^{1}\log(1-x^{2})\sum_{n=1}^{\infty}\frac{(-1)^{n}x^{2n}}{n}\,dx

Here the interchange made between the summation and the integration is permissible due to Fubini’s theorem. Using the variable change xxx\mapsto\sqrt{x} leads to


From the well-known result of (see, for example, [14 C. I. Vălean, (Almost) impossible integrals, sums, and series. Problem Books in Mathematics, Springer, Cham (2019) , p. 2, Eq. (1.4)])


replacing nn with n+12n+\frac{1}{2} we see that


allowing us to rewrite the integral appearing in (10) as


In view of (7) this can be rewritten as


From the partial fraction decomposition of


and the recurrence relation for the harmonic numbers, (12) may be expressed as

I=2n=1(1)nn(H2n12Hn)4n=1(1)n2n+1(H2n12Hn)\displaystyle I=2\sum_{n=1}^{\infty}\frac{(-1)^{n}}{n}\left(H_{2n}-\frac{1}{2}H_{n}\right)-4\sum_{n=1}^{\infty}\frac{(-1)^{n}}{2n+1}\left(H_{2n}-\frac{1}{2}H_{n}\right)
+2(1log2)n=1(1)nn+4(log21)n=1(1)n2n+1\displaystyle\qquad+2\left(1-\log 2\right)\sum_{n=1}^{\infty}\frac{(-1)^{n}}{n}+4\left(\log 2-1\right)\sum_{n=1}^{\infty}\frac{(-1)^{n}}{2n+1}