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.
237
We take for our probability space : the unit interval equipped with the Lebesgue measure defined on , the Borel subsets of and let be an invertible measure preserving transformation, that is is a bimeasurable bijection of some Borel set of full measure so that and for every .
Suppose also that is ergodic in the sense that the only -invariant Borel sets have either zero- or full measure ().
Birkhoff’s ergodic theorem says that for every integrable function ,
The present exercise is concerned with the possibility of generalizing this. Throughout, is an arbitrary ergodic, measure-preserving transformation as above.
Warm-up 1
Show that if is measurable, and
then converges in 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 is as in Warm-up 1, then measurable with bounded so that .
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].
Problem
Show that there is a measurable function satisfying so that
converges in a.s.
The existence of such 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 .
Jon Aaronson (Tel Aviv University, Israel)
238
Let be a probability space and a sequence of independent and identically distributed (i.i.d.) random variables on . Assume that there exists a sequence of positive numbers such that for every , , and . Prove that if for each , then
Comment. The desired statement says that if such a sequence exists, then satisfies the (generalized) Strong Law of Large Numbers (SLLN) when averaged by . If for every , 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 . 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)
239
In Beetown, the bees have a strict rule: all clubs must have exactly membees. Clubs are not necessarily disjoint. Let be the smallest number of clubs that it is possible for the 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
for some constant .
Rob Morris (IMPA, Rio de Janeiro, Brasil)
240
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 .
Bhargav Narayanan (Rutgers University, Piscataway, USA)
241
Consider the following sequence of partitions of the unit interval : First, define to be the partition of into two intervals, a red interval of length and a blue one of length . Next, for any , define to be the partition derived from by splitting all intervals of maximal length in , each into two intervals, a red one of ratio and a blue one of ratio , just as in the first step. For example consists of three intervals of lengths (red), (red) and (blue), the last two are the result of splitting the blue interval in . The figure below illustrates , from top to bottom.
Let and consider the -th partition .
Choose an interval in uniformly at random. Let be the probability you chose a red interval, does the sequence converge? If so, what is the limit?
Choose a point in uniformly at random. Let be the probability that the point is colored red, does the sequence converge? If so, what is the limit?
Yotam Smilansky (Rutgers University, NJ, USA)
242
Prove that there exist and such that if are increasing events of independent boolean random variables with for all , then
(What is the smallest that you can prove?)
Here is an “increasing event” if whenever , then the vector obtained by changing any coordinates of from to still lies in .
A useful fact is Harris inequality, which says that for increasing events and of boolean random variables, .
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 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 with a power of , and odd. We define a transformation on 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 , if we were to set
the orbits are finite.
We point out that it is not hard to show that 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 , every odd integer lies in one of the arithmetic progressions
Definition. A sequence of odd integers is equidistributed in the odd 2-adics if for every , , the proportion of in is . “Proportion” means the relative density.
Now define
where and are odd integers, , .
243*
Conjecture A. For any natural odd numbers the orbit of under is either finite or equidistributed in the odd 2-adics.
Consequence: All the orbits of 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 is . The idea now is to observe that for large , the effect of applying 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 . Here as usual denotes the largest integer less than . We have
But for ,
so that for the orbit of will be infinite.
244*
Conjecture B. For any , the orbit under 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 defined by
We expect the same phenomenon: orbits that are either finite or equidistributed. Little numerical work has been done on this conjecture.
III Solutions
226
Let stand for the space of complex column-vectors, and let stand for the space of complex matrices.
The inner product of is defined as
Therefore is linear in and conjugate linear in .
Let be complex matrices. Write them as
with .
Then it is immediate from the definition of matrix multiplication that
Show the following relation:
where each product is a rank-one matrix in .
T. Ando (Hokkaido University, Sapporo, Japan)
Solution by the proposer
Consider the canonical orthonormal basis in ;
Then it suffices to prove the identity in the assertion for the case
and
In this case
while
as expected.
Also solved by John N. Daras (Athens, Greece), Muhammad Thoriq (Yogyakarta, Indonesia), and Socratis Varelogiannis (France)
227
Let and be two distinct primes with and a group of exponent for which the map defined by , for all , is an endomorphism. Show that 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 defined by is an endomorphism for all with .
First, it is not hard to see that implies that , for all . Then we observe that
It is also easy to show that
Using the latter, we see that
for all . We just showed that is an endomorphism of . We proceed by showing that is also an endomorphism.
For every , we have
In the above chain of equalities we just used that and are endomorphisms. We previously mentioned (1) that the middle terms commute, which shows that is an endomorphism of .
Observe that for all we have
which implies that . It follows that belongs to the center of , for any .
We are now ready to prove our claim. Let for some . Then
The claim is proved.
Since , by the Chinese Remainder Theorem we know that there is an integer such that
We therefore have that the map defined by is an endormorphism. However, for all , since is the exponent of . Now, since is an endomorphism of , it follows that for all we have .
Remark. The conclusion also holds if and are not prime. One just needs to have a finite exponent such that and are coprime.
Also solved by Mihaly Bencze (Romania), Tomek Jedrzejak (University of Szczecin, Poland), and Efstathios S. Louridas (Athens, Greece)
228
Let be a group with the property that there is an integer such that the map is injective and the map
is a surjective endomorphism. Prove that 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
Using the above, we see that for all . On the other hand,
We just showed that
Now, using the surjectivity of we obtain that for every there is such that , that is . The relation (2) can be written as , for all . From this relation we get
that is
This is equivalent to
hence and the conclusion follows from the injectivity of the map .
Also solved by John N. Daras (Athens, Greece), Tomek Jedrzejak (University of Szczecin, Poland), Muhammad Thoriq (Yogyakarta, Indonesia), and Socratis Varelogiannis (France)
229
Let and be two matrices over a field . We say that and are similar if there exists an invertible matrix such that .
Let and be two similar invertible matrices over the field of rational numbers . Assume that for some integer , we have Then and 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 having three elements satisfying
Let us show that .
By way of contradiction we assume that the order of is . Since and are conjugate, the order of is also . The cases and are trivial, so we assume that .
Let denote the greatest common divisor of two integers and . The order of is and the order of is . Since and are conjugate, their orders coincide. Therefore, . Thus, since and are coprime, we obtain that
This implies that there exists a natural number , which is coprime with and such that . Note that . Therefore,
Since the order of is , divides . Let be the smallest prime divisor of . Then the integers and are coprime. Hence there exist such that . Observe also that
Therefore, , and so
We have arrived at a contradiction, which proves that .
Now let us come back to the original problem. Since and are similar, there exists an invertible matrix such that . Let be the subgroup of generated by and . Let be such that , ,,. Then .
Recall that a group is called residually finite if for every non-trivial element there exists a finite quotient of such that the image of in is non-trivial. Observe that the group is residually finite (consider the natural maps from to , where are prime numbers coprime with ). Therefore we conclude that the group is also residually finite.
If is not the identity matrix, then there exists a finite quotient of such that the image of in is not trivial. But this contradicts what we proved at the beginning. Thus , so also , 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 we could assume that the matrices and in the problem are considered over an arbitrary field . 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)
230
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 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 nails.
Dawid Kielak (Mathematical Institute, University of Oxford, UK)
Solution by the proposer
Let us start with nails. Wrapping a loop around two nails in some way is equivalent to choosing an element of . Of course, this fundamental group is the free group of rank , 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 of . The condition that the picture is supposed to fall when any of the nails is removed means that the image of in and in has to be trivial. We immediately recognise that does the trick.
For three nails, we can take
The solution easily generalises to nails.
Also solved by Mihaly Bencze (Romania), and George Miliakos (Sparta, Greece)
231
Given a natural number and a field , let be the full matrix algebra over . A matrix is said to be centrosymmetric if
for . Let denote the set of all centrosymmetric matrices in . Then is a subalgebra of , called centrosymmetric matrix algebra over of degree . 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 reads as follows.
Does 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
Strategy
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 , a practical way is to look for a decomposition of 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 , denoted . Then and have equivalent module categories, and therefore they have the same number of nonisomorphic indecomposable modules.
Technique
Let be the identity matrix in , be the matrix with -entry and other entries , and
Then . Calculations show that, for ,
, , where is the Kronecker symbol,
as left ideals, and
dim;
and, for ,
, , where is the Kronecker symbol, and
as left ideals, and
dim.
Thus
and
Further calculations lead to
Answer
We give quiver presentations of (see [12 C. Xi and S. Yin, Cellularity of centrosymmetric matrix algebras and Frobenius extensions. Linear Algebra Appl.590, 317–329 (2020) ]).
Clearly, . If char, then and . If char, 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.
has exactly nonisomorphic indecomposable module.
If ch, then has exactly nonisomorphic indecomposable modules for all .
If ch, then has exactly nonisomorphic indecomposable modules for all , and has exactly nonisomorphic indecomposable modules for all .
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 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 be the largest modulo value among all its coefficients. If the argument of the polynomial is greater than , then the value of the polynomial is greater than . To prove this, consider the calculation of the polynomial
by the Horner scheme.
At the first step we calculate
and it is obvious that In fact even if it does not exceed in absolute value.
At the second step we calculate
and again it is obvious that
The same holds in the following steps.
At the last step we compute
and finally obtain 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
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 . In terms of known constants its value is:
Here is Catalan’s constant defined by .
We first establish a number of preliminary results before evaluating the integral. The th harmonic number is defined by
By convention, . 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 is the Euler–Mascheroni constant. This allows the harmonic numbers to be analytically continued to all . 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) ])
Replacing with 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
By applying (3), in terms of harmonic numbers this can be expressed as
which reduces to
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
Showing this we have
where we have made use of the partial fraction decomposition of
Reindexing the second sum we have
Reindexing the infinite sum and the finite sum yields
with the desired result then following on application of (3).
The second Cauchy product for power series is
Showing this we have
where (3) has been used. The desired result then follows after a reindexing of .
Turning our attention to the integral we have
Here the interchange made between the summation and the integration is permissible due to Fubini’s theorem. Using the variable change 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 with 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
We now find each of these five sums. For the first of these, setting in (8) we see that
For the second of the sums, , integrating (9) with respect to from to we see that
Using the variable change before integrating by parts produces
The integral that has now appeared can be evaluated as follows. Recalling Euler’s famous log-sine integral
and let
Using the variable change in gives
Thus
Also
Substituting we obtain
Integrating by parts gives
where we used the definition of Catalan’s constant. Solving for yields
Thus
The third sum comes directly from the Maclaurin series expansion for evaluated at . Here
The four sum is related to the Maclaurin series expansion for . Here
For the fifth and final sum
where again the definition for Catalan’s constant has been used. Combining the values found for all five sums into (13) we find
as announced.
Some comments on the general case (part (b) of the question)
Denoting the integral in (b) by where is an integer, following the identical procedure that led to (11) we find
Using such an approach, the general problem therefore boils down to expressing in terms of harmonic numbers whose indices are of integer rather than fractional order before evaluating each of the resulting series. Unfortunately, how this can be achieved for cases when is currently not clear to me, suggesting that to find , we may need a different approach from the one we used to find .
We would like to invite you to submit solutions to the proposed problems and/or ideas on the open problems. Send your solutions by email to Michael Th. Rassias, Institute of Mathematics, University of Zürich, Switzerland, michail.rassias@math.uzh.ch.
We also solicit your new problems, together with their solutions, for the next “Solved and Unsolved Problems” column, which will be devoted to the topic of Game Theory.
References
- 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)
- D. Tanny, A zero-one law for stationary sequences. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete30, 139–148 (1974)
- D. Volný and B. Weiss, Coboundaries in L0∞. Ann. Inst. H. Poincaré Probab. Statist.40, 771–778 (2004)
- G. Baumslag, A non-cyclic one-relator group all of whose finite quotients are cyclic. J. Austral. Math. Soc.10, 497–498 (1969)
- A. Malcev, On isomorphic matrix representations of infinite groups. Rec. Math. [Mat. Sbornik] N.S.8 (50), 405–422 (1940)
- A. Aitken, Determinants and matrices. Oliver and Boyd, Edinburgh (1939)
- A. R. Collar, On centrosymmetric and centroskew matrices. Quart. J. Mech. Appl. Math.15, 265–281 (1962)
- L. Datta and S. D. Morgera, On the reducibility of centrosymmetric matrices – applications in engineering problems. Circuits Systems Signal Process.8, 71–96 (1989)
- I. J. Good, The inverse of a centrosymmetric matrix. Technometrics12, 925–928 (1970)
- T. Muir, A treatise on the theory of determinants. Revised and enlarged by William H. Metzler, Dover Publications, Inc., New York (1960)
- J. R. Weaver, Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors. Amer. Math. Monthly92, 711–717 (1985)
- C. Xi and S. Yin, Cellularity of centrosymmetric matrix algebras and Frobenius extensions. Linear Algebra Appl.590, 317–329 (2020)
- 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)
- C. I. Vălean, (Almost) impossible integrals, sums, and series. Problem Books in Mathematics, Springer, Cham (2019)
Cite this article
Michael Th. Rassias, Solved and unsolved problems. Eur. Math. Soc. Mag. 119 (2021), pp. 57–66
DOI 10.4171/MAG/14