In mathematics, a discrete logarithm is an integer solving the equation , where and are elements of a group. Discrete logarithms are thus the group-theoretic analogue of ordinary logarithms…
Cayley graphs are abstract visualizations of groups which have application in the identifying optimal algorithms for solving discrete logarithm problems.
In simplest terms, the Cayley graph shows all the elements of a group and how the action of the generators of the group transforms one element to another.
A discrete logarithm can readily be understood as the number of times one applies self interacts element in order to get to element . For the infinite group of integers, if and are known, then has a unique value. However, if the group is finite, then may very well have an infinite number of values. The set of infinite values is the driver behind why discrete logarithms play a major role in public encryption schemes such as ElGamal
Certain directed versions of Paley graphs, Paley digraphs, have an interesting role in understanding the problem of minimizing losses in conference call networks. Paley digraphs can be used to represent antisymmetric conference matrices.
The work on conference matrices was done by Vitold Belevitch whose family fled Russia to escape the communists during the Bolshevik revolution. Through his work on telephony, he discovered that loss-less conferencing was only really possible for even-port networks (e.g. divisible by 2) and even more importantly, not all even-port networks were loss-less.
What is even more peculiar, is that Belevitch was able to provide a statistical interpretation of Zipf’s law in terms of Taylor series expansions.
Zipf’s law is a simple statement that the rank of word in a language multiplied by its frequency equals some constant value.
When one looks at the distribution of word frequency for a language, for an infinite word language the distribution is best described by the Riemann Zeta function.
So here is the interesting path we have described in reverse order:
The Riemann Zeta function describes the distribution of word frequency for a language that is governed by Zipf’s law which was discovered to be statistically describable in terms of Taylor series by Belevitch, who also discovered conference matrices as a means to describe loss-less teleconference configurations, that can also be represented by Paley digraphs, which are special types of Cayley graphs, and are used to also represent cyclic groups which are used in public key cryptography because of the difficulty in determining discrete logarithms for finite discrete groups. The punch line, which I have not discussed before, is all cyclic groups are Abelian (commuting), and the Riemann Zeta function has an interesting role in the number of cyclic groups for some group order n.
So here we have done some interesting path tracing connecting to applications of the Riemann Zeta function, a worthwhile adventure for a 100th blog post me thinks.
Some additional reading on the related group isomorphism problem can be found here.
Addendum: Cayley tables are often used to represent groups (basically, they are multiplication tables). However the Cayley graph lends itself to be best represented by a weighted graph, such as a distance table especially since Cayley graphs have weighted edges. More on this later.