Modular Dilogarithms Rich Schroeppel and Cheryl Beaver rschroe@sandia.gov & cbeaver@sandia.gov Sandia National Laboratories* April 2, 2002 revised April 10, 2002 [*] Sandia is a multiprogram laboratory operated by Sandia Corporation, a Lockheed Martin Company, for the United States Department of Energy under Contract DE-AC04-94AL85000. Abstract: We report on a generalization of the discrete logarithm, called the Modular Dilogarithm. The modular dilogarithm is a discrete analog of the Dilogarithm, a special function defined over the complex variables. The modular dilog satisfies the same functional equations as the complex dilog, including some equations involving discrete logarithms. There's no good reason for the modular dilog to exist at all -- all of our evidence is empirical. The modular dilog can be defined modulo a prime, or a prime power, or in a finite field. For modular dilogs defined modulo a prime P, the range of values seems to be modulo P^2-1. The modular dilog is harder to compute than the discrete log. Modular Trilogarithms may also exist. That's the Beauty of Science: Such a wholesale return of Conjecture, from a trifling investment of Fact. Mark Twain 1. Introduction We report on a generalization of the discrete logarithm, called the Modular Dilogarithm. The modular dilogarithm is a discrete analog of the Dilogarithm, a special function defined over the complex variables. The modular dilog satisfies the same functional equations as the complex dilog, including some equations involving discrete logarithms. The modular dilog can be defined modulo a prime, or a prime power, or in a finite field. For modular dilogs defined modulo a prime P, the range of values seems to be modulo P^2-1. The modular dilog is harder to compute than the discrete log. Modular Trilogarithms may also exist. Section 2 of this paper is a brief summary of the properties of the classical dilogarithm defined on the complex numbers. Section 3 gives an example of the Modular Dilogarithm, and shows which of the properties of the complex function carry over to the modular case. Section 4 explains how we compute modular dilogs. Section 5 discusses extensions to trilogs and some other directions. Section 6 contains some fancy algebra. Section 7 poses some questions that have been suggested by this discovery. The most important is "Why do these exist at all?" We have no proofs. All the work is empirical. 2. The Classical Dilogarithm Function Most of this material is drawn from Lewin[L81]. The complex dilogarithm Li2(z) may be defined by the power series Li2(z) = sum z^n / n^2 for n from 1 to infinity or by the integral Li2(z) = integral - log(1-t) / t dt for t from 0 to z The equivalence of the definitions is established by term-by-term integrating the power series for -log(1-t)/t. The power series converges within (and on) the unit circle |z|<=1. The Riemann sheet structure is complicated: The integrand is defined everywhere except t=0 and 1, and the singularity at 0 is removable on the principal sheet. The singularity at 1 is a log-spiral-staircase, and the non-principal sheets have simple poles at 0. The principal sheet is the complex plane with a branch cut along the positive real axis for x>1. The dilogarithm function was apparently first considered by Leibniz, shortly after calculus was discovered. It was later studied by Euler and Landen. Euler found that Li2(1) = zeta(2) = pi^2 / 6 Several simple functional equations were discovered: Li2(z) + Li2(-z) = Li2(z^2) / 2 This is obvious from adding up the power series for Li2(z) and Li2(-z). The z^odd terms cancel. The z^even terms are Li2(z^2)/2. A generalization of this trick gives Li2(z) + Li2(wz) + Li2(w^2 z) = Li2(z^3) / 3 where w = exp(2 pi i/3) is a complex cube-root of 1. Analogous results hold for higher roots of 1. The next two functional equations are established by differentiation. Li2(z) + Li2(1-z) = pi^2 / 6 - log(z) log(1-z) For complex z, the branches of the logarithms are chosen by walking from z = 1/2. Li2(z) + Li2(1/z) = - pi^2 / 6 - (log(-z))^2 / 2 For complex or positive z, the branch of the logarithm is selected by walking from z = -1. These functional equations are enough to compute Li2(z) anywhere in the complex plane (principal branch), by bringing z inside the unit circle and using the power series. Our work generally ignores branches, so we don't include the twiddle terms necessary for non-principal branches. The transformations z->1/z and z->1-z can be combined to generate a set of six related quantities whose dilogarithms differ by (or sum to) logarithmic terms: z, 1/z, 1-z, 1-1/z, 1/(1-z), z/(z-1). They can be arranged in a hexagon with alternate edges representing the two transformations. z ---- 1-z / \ / \ 1/z 1/(1-z) \ / \ / 1-1/z --- z/(z-1) For example, we can set z=1/3, and relate the value of Li2 at 1/3 to those at 2/3, 3/2, -1/2, -2, and 3. Manipulation of the functional equations allows closed-form values to be determined for Li2 at z = 1, -1, 1/2, and 1/phi and 1/phi^2, where phi = 1.618... is the golden ratio. Li2(1) = pi^2/6 Li2(-1) = - pi^2/12 Li2(1/2) = pi^2/12 - log(2)^2/2 Li2(1/phi) = pi^2/10 - log(phi)^2 Li2(1/phi^2) = pi^2/15 - log(phi)^2 In 1809, Spence made a major advance, a true leap of imagination. The dilogarithm is sometimes called Spence's function in his honor. He found a relationship equivalent to Li2(xy) = Li2(x) + Li2(y) + Li2((xy-x)/(1-x)) + Li2((xy-y)/(1-y)) + 1/2 (log((1-x)/(1-y)))^2 [5term] valid when x,y,xy<1, or if all the dilog arguments are inside the unit circle. Slight variations apply outside this range. This particular form of the functional equation is due to Hill. The equation is called 5term since it contains 5 dilogarithm terms. Subsequently, many authors have studied the dilogarithm and related functions, and produced an abundance (nay, a plethora) of functional equations. None can really be called simple, in contrast to the simple relationship for logarithms. Lewin [L58] contains a good summary of pre-1960 work, including a good bibliography. [L81] is an updated second edition. Lewin has edited a sampler of recent work [L91]. Other dilog functional equations have more terms and/or more variables, both with & without side conditions. Perhaps, all can be derived from the basic five-term functional equation. This question is open, with good mathematicians holding opposing opinions. Zagier [Z] thinks maybe 5term is complete. Considerable effort has gone into looking for functional equations without log terms, and into defining closely related functions without the singularities, or whose functional equations don't have the log terms. For example, the contributors to [L91] define the Bloch-Wigner Dilogarithm, and several versions of the Rogers Dilogarithm. Each formulation has its advantages and disadvantages; there's no clearly superior choice. A typical sacrifice is the analyticity of the new function. Like a wrinkle in a rug, the trouble spots can be moved around but not eliminated. The work described in this paper began with Newman's six-term symmetric functional equation for the co-dilogarithm, cLi2(x) = Li2(1-x). This equation has the nice property of containing no extra logarithm terms. 2 [ cLi2(x) + cLi2(y) + cLi2(z) ] = cLi2(xy) + cLi2(xz) + cLi2(yz) [6term] provided that x+y+z = xyz+2, or equivalently, 1/(1-x)+1/(1-y)+1/(1-z)=1. [This equation is also true for plain old logarithms, without any relationship among x,y,z except xyz/=0. Any multiple of log can be added to a solution of the functional equation to get another solution valid on the nonzero subdomain.] There doesn't seem to be an algebraic way to go from the six-term equation to the five-term equation. 3. Modular Dilogarithms We have invented/discovered the Modular Dilogarithm function, D(). The argument of D is an integer N modulo a prime P. The value is an integer D(N) modulo P^2-1. Example with P=19: N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 mod 19 log(N) - 0 1 13 2 16 14 6 3 8 17 12 15 5 7 11 4 10 9 mod 18 D(N) 120 30 345 358 74 26 344 258 327 108 265 162 3 132 326 44 236 232 345 mod 360 E(N) 0 0 0 352 56 224 56 192 288 312 160 168 72 48 344 296 344 208 0 mod 360 D satisfies five functional equations, all mod 360: D(x) + D(1-x) = D(0) + D(1) + K log(x) log(1-x) 2 [ D(x) + D(1/x) ] = - 2 D(1) + K log(-x)^2 x/=0 2 [ D(x) + D(-x) ] = D(x^2) D(xy) = D(x) + D(y) - D((x-xy)/(1-xy)) - D((y-xy)/(1-xy)) + D(0) + K log((1-x)/(1-xy)) log((1-y)/(1-xy)) xy/=1 2 [ D(1-x) + D(1-y) + D(1-z) ] = D(1-xy) + D(1-xz) + D(1-yz) with z = (2-x-y)/(1-xy) xy/=1 K = 20. Logs are base 2. The arithmetic for arguments of log and D is done mod 19. The value for log(0) doesn't matter: it's always multiplied by log(1) = 0. Any multiple of D also works, with K adjusted appropriately. E() is another solution for the functional equations, with K = -40. 3E = 192D (mod 360). Any linear combination dD+eE works, with K = 20d-40e. There are 1080 solutions: 360 multiples of D, plus 0,1,2 times E. 2D+E gives a "Modular Rogers Dilogarithm" without log terms (K=0). The Modular Dilogarithm satisfies the same functional equations that the regular dilogarithm does, with a few adjustments. Log terms are interpreted as discrete logs. Since discrete logs are mod P-1, the log terms must be multiplied by P+1 to fit into functional equations mod P^2-1. The base of the logs is unspecified, so the log terms may need an additional scaling factor. We replace pi^2/6 with D(1), and allow the possibility that D(0) is nonzero. D(infinity) is left undefined. All the functional equations of dilogs are simple sums of dilog terms, so any multiple of dilog will also satisfy the equations if other terms are scaled to match. Some properties of the solution space: D(x^2) is divisible by 2, so quadratic residues have even dilogs. For P=19, D(x) is odd exactly when both x and 1-x are non-residues. Dilogs of cubic residues are divisible by 3, etc. 4. Computing Modular Dilogarithms Individual values of Modular Dilogarithms don't have meaning; a particular value is not right or wrong. We must compute the entire function -- the value at each residue mod P -- to have something to check. Our approach is to assign an independent unknown variable to represent each function value. We substitute numbers into the functional equations, and learn relationships between the function values. For example, suppose P=7. We would use 7 variables, D0,D1,...,D6. The functional equation 2 [ D(x) + D(-x) ] = D(x^2) would be specialized with x=0...6. X=2 would give the relationship 2 D2 + 2 D5 = D4. Since all the functional equations are linear in the dilog terms, we use matrices to keep track of our work. We create a non-square matrix, with P columns and many rows. Column J corresponds to the variable D(J). The matrix entries are integers, representing coefficients of D(J). The rows are initialized from substitutions into the functional equations. Each row represents one relationship between the D values, saying "These D values, with these coefficients, sum to 0." Most of the coefficients in the row are 0, since there are only a few terms in the functional equations. If the functional equation has fractions, we clear them, to avoid non-integer entries in the matrix. When substitution into a functional equation gives an infinity in some argument, we discard the instance, and don't make a matrix row. When a functional equation has numerical or log terms, we use an extra column of the matrix to hold the values. Log terms are evaluated as discrete logs (using a fixed primitive root mod P), with values defined mod P-1. Our matrix solution method avoids combining entries in different columns. Most of our work uses the co-dilogarithm, which has a nice 6-term functional equation with no log terms or constants. This allows agnosticism on the base of the logarithms. An example of the matrix for P=7, using codilogs. Column J is cD(J) = D(1-J). 1 0 2 0 0 0 0 0 3 0 0 0 0 0 0 0 0 2 -1 0 2 0 0 0 0 2 2 -1 0 0 4 2 -1 0 -2 0 0 1 -1 0 1 2 0 0 -1 4 2 -2 0 0 0 -1 -2 4 0 2 0 0 0 0 -3 6 0 The first row is cD(0)+2cD(2) = 0. This corresponds to x=0,y=0,z=2 in the 6-term functional equation: 2[cD(0)+cD(0)+cD(2)] = cD(0)+cD(0)+cD(0) For larger P, the number of rows is about P^2/6. ( Most of the rows turn out to be redundant and could be dropped or never generated. Probably any set of somewhat more than P rows is adequate.) The matrix entries are regarded as integers, rather than modular residues. This postpones the choice of modulus. The matrix is "solved" by elementary row operations, adding or subtracting multiples of one row to or from another row. The algorithm diagonalizes the matrix as best it can, although there are some remaining non-diagonal elements. Redundant rows are simplified to 0, and dropped. We avoid division of a row in solving the matrix, to avoid losing potential modular information. After the row-reduction, the example matrix reduces to 1 0 0 0 0 0 2 0 3 0 0 0 0 0 0 0 1 0 0 0 11 0 0 0 1 0 -1 9 0 0 0 0 1 -2 -8 0 0 0 0 0 6 -9 0 0 0 0 0 0 24 Some all-0 rows have been dropped. The bottom two rows correspond to the equations 6 cD(5) - 9 cD(6) = 0 and 24 cD(6) = 0. We want integer solutions, so the modulus for the dilogarithms must be a multiple of 48. The other rows are all compatible with 48. Using the bottom row, we assign cD(6) = 2t. The next row, 6 cD(5) - 9 cD(6) = 0, gives cD(5) = 3t+8u. The other cD values can be computed from the matrix rows. cD(1) requires one new parameter; cD(1) = 16v. Dilog values are then computed from D(x) = cD(1-x). The co-dilog functional equation has weight 3, so each matrix row also has weight 3. The weights of rows in the solution matrix are multiples of 3. The other dilogarithm functional equations may impose additional conditions on the variables. We have solved coDilog matrices for primes 5...23. Attempts to use several single variable functional equations instead of the two-variable co-dilog equations have not worked out. Computational Complexity Computing a dilog table for P=1009 would be a major effort with present methods; in contrast, the discrete log table can be computed in a millisecond. Our current matrix approach requires O(P^4) arithmetic operations to solve the dilog matrix. This would drop to O(P^3) if we only used O(P) rows. A successful basis approach, with a basis size of perhaps sqrt(P) values, would bring the complexity down to O(P^1.5). Checking that a proposed dilog table satisfies a two-variable functional equation is O(P^2), unless we develop new theorems that allow checking only a subset of the combinations. These are all much larger than the corresponding effort for discrete logs, for which naive algorithms are O(P), and good algorithms begin at O(sqrtP) and drop to O(P^epsilon). Possibilities for Extension to Larger P Ladders The matrix method is limited to modest P values, but we have some ideas for larger P. There are dozens of "polylogarithm ladders" known, which give relationships between Li values of various algebraic numbers. The relationships involve both dilogarithms and higher polylogs. A simple example is Li2(phi^-6) = 4 Li2(phi^-3) + 3 Li2(phi^-2) - 6 Li2(phi^-1) + 7 pi^2/30 with phi=1.618..., the golden ratio. If P is a prime ending in 1 or 9, then 5 is a square (mod P), and there is a residue corresponding to phi, a root of the equation phi^2 = phi+1. The example ladder above may translate to a "free" modular dilog relation. A large part of [L91] is devoted to ladder relationships. These ladders could map to residues mod P, and determine relationships among modular dilogs. The most extensive example known [BB] uses a root W of the Lehmer polynomial, W^10+W^9-W^7-W^6-W^5-W^4-W^3+W+1, and goes up to Li17, involves a smattering of powers up to W^630, and coefficients with hundreds of digits. Symbolic Values Another possible approach is related to the matrix approach, with "opportunism". The idea is to assume a few symbolic values for particular dilogs, and use the functional equations to determine related dilogs. When all possible dilogs have been derived, another symbolic value is assumed. Eventually, every dilog is assigned a value based on the assumed symbolic values. Then the functional equations can be enumerated systematically, and the symbolic values checked. Occasionally a new relationship among symbolic values will be learned, and a symbolic value is eliminated from the system. Example: Mod 101, starting with symbolic values for D5 and D8. We can use the following "rules of inference". If we know D(x) we can express D(y) ... x -> 1/x and 1-x and the rest of the 6-ring x and -x -> x^2 x and x^2 -> -x We begin with D(5)=D5 and D(8)=D8. We also assume D(0)=D0 and D(1)=D1 are known, and we assume a multiplier K and base 2 for the discrete logs which appear. 2 is a primitive root mod 101. (We could also use one of the dilog variants which doesn't need log terms in its functional equations.) Each residue is in a ring of 6 values. We proceed according to the following plan: 5 -> -20, -4, 25, -24, 21 5, 25 -> -5 -5 -> 20, 6, 17, -16, -19 8 -> 38, -7, -29, 30, -37 8, -37 -> -8 -8 -> -38, 9, 39, 45, -44 9, -20 -> -9 etc. Using the functional equation for D(5)+D(1/5), we find D(-20) = D(1/5) = (-2 D1 + K (log(-5))^2)/2 - D5 = - D1 - D5 - (K 74^2)/2 + 5100u = - D1 - D5 - 2738 K + 5100 u The 5100u term arises from dividing an equation mod 10200 by 2. We continue by calculating expressions for D(-4) and so on, until we have every residue mod 101. Whether this approach actually will work is speculative. 5. Extensions: Other Moduli, Other Fields, Other Functions Prime Powers We've done experiments to see how far the Modular Dilogarithm idea can be extended. A co-dilog matrix was created and solved for Mod 25, as an example of a prime power. The dilogs seem to be defined mod 600. This is analogous to the path from mod 5 to mod 25 for discrete logs, where the solution range (mod 4) is multiplied by 5 to get (mod 20). The P=5 dilog range (mod 24) is multiplied by 25 to get (mod 600). Composite Moduli We haven't tried experiments with composite moduli divisible by different primes. The results might be simply the cross product of the separate prime power solutions, or there might be new phenomena. Finite Fields Another experiment was with GF[5^2], the finite field of order 25. Here the dilogs appear to be mod 624, which is 5^4-1. There's also a relationship between the dilog of a field element and the dilog of its conjugate. Curiously, the intermediate partially-reduced matrices included integers of more than 100K bits. The matrix took ~50K row-reduction steps to process, much more than the mod 25 case or the mod 19 case. The final matrix only contained 3 digit numbers, with no sign that the intermediates were huge. Modular Trilogarithms We've made some limited progress with Modular Trilogarithms. The single variable functional equations don't give enough relationships. A 22-term trivariate functional equation due to Goncharov [L91, p. 375] always produced zero solutions. (Our conversion to modular form might be wrong.) We had some success with a two-variable 10-term equation, eqn 6.93 in [L81, p. 174]. Lewin derives this from an 1809 result of Spence. Let u=s+t-st. T(u) = 2T(s)+2T(t)+2T(s/u)+2T(t/u)+2T(-st/u)+T(-s/t)+T(-t/s) -T(s^2/u)-T(t^2/u)-2T(1) +(pi^2/6+log(s/t)^2/2)log(u^2/st)-(log(u/s)^3+log(u/t)^3)/3 The T(1) and pi and log terms aren't counted in the name "10-term". We multiplied the non-trilog terms by 6 to clear fractions, and used pi^2 => -(p-1)^2/4. This approach yielded matrices with solutions mod 7(P^3-1) for P=5...17. 6. Miscellaneous Musings Toward a Formula for Modular Dilogs Starting with a functional equation from [L81, p. 9] D(ab) = D(a) + D(b) + D((ab-a)/(1-a)) + D((ab-b)/(1-b)) + K * 1/2 (log((1-a)/(1-b)))^2 Fix a/=0,1. Sum over b/=1 (mod P). Let S = D(0)+D(1)+...+D(P-1). S-D(a) = (P-1)D(a) + (S-D(1)) + (S-D(0)) + (S-D(1-a)) + K * 1/2 sum(0^2...(p-2)^2) -P D(a) = 2S -D(0) -D(1) -D(1-a) + K/12 (P-2)(P-1)(2P-3) Assume D(a)+D(1-a) = D(0)+D(1)-K*log(a)*log(1-a) -(P+1)Da = 2S - 2(D(0)+D(1)) + K*log(a)*log(1-a) + K/12 (P-2)(P-1)(2P-3) If we assume that log terms are multiplied by P+1, then this determines D(a) up to approximately mod P-1. Why the Modulus for Modular Dilogarithms is P^2-1 Consider the squaring formula, 2(D(x)+D(-x)) = D(x^2). If we are working over a finite field GF[2^N], then x = -x, so 4 D(x) = D(x^2). N squarings gets us back to x: x^(2^N) = x, so 4^N D(x) = D(x^(2^N)) = D(x). Whence (4^N-1) D(x) = 0. So we expect dilogs in GF[2^N] to be mod 4^N-1. Similarly, over a general finite field GF[P^E], we use the P-tuplication formula P (D(x) + D(wx) + D(w^2 x) + D(w^3 x) + ... + D(w^(P-1) x) ) = D(x^P) with w^P = 1. But in a field over (mod P), the only Pth root of 1 is 1, so w = 1. Thus P^2 D(x) = D(x^P). Taking Pth powers E times gives P^(2E) D(x) = D(x^(P^E)) = D(x), since x^(P^E) = x in a finite field. Thus we expect (P^(2E)-1) D(x) = 0 for all x in the field, and the dilogs "exist" mod P^(2E)-1. The argument extends to trilogarithms: P^2 (T(x) + T(wx) + ... + T(w^(P-1) x) ) = T(x^P), with w^P=1, so P^3 T(x) = T(x^P), and then P^(3E) T(x) = T(x^(P^E)) = T(x), and trilogs "exist" mod P^(3E)-1. The argument also works in the other direction, to "explain" why discrete logs are mod P^E-1. This also explains the conjugation mapping, P^2 D(x) = D(x^P). Taking Pth powers of an element cycles through the conjugates; in the simple case E=2, x^P = x~. This explains the structure in the GF[5^2] example; and why the elements in the ground field, which are their own conjugates, satisfy x^P = x and therefore P^2 D(x) = D(x), so they are multiples of (P^4-1)/(P^2-1) = P^2 + 1. This isn't rigorous, but it might be the beginnings of a proof. 7. Prospects Dilogarithms and polylogarithms are an active area of research. A Net search turned up several different threads, although our modular idea seems to be new. The most important unanswered question is: Why Do Modular Dilogarithms Exist? All simpler modular operations and functions, up through discrete logs, can be derived from analogies with the integer and real number versions of the functions, and can ultimately be traced back to counting operations. For example, the familiar "Laws of Exponents" are derived by counting the number of times various factors are multiplied together. The Dilogarithm concept has no such grounding: the definition depends on limit operations -- integrals and infinite series -- which have no modular counterpart. That there are modular solutions of the functional equations can only be regarded as magic at this point. There are many other questions: Give a proof that Modular Dilogarithms exist for all primes P, and perhaps for prime powers and finite fields. Give a formula to compute them. Describe the structure of the solution space. Is there a useful inverse function, a Modular Diexponential? Are there special primes for which computing dilogs is easy? How far can the concept of Modular Functions be extended? References [BB] David Bailey and David Broadhurst, A Seventeenth-Order Polylogarithm Ladder, Oct 12, 1999. http://www.nersc.gov/~dhbailey/dhbpapers/ladder.pdf [L58] Leonard Lewin, Dilogarithms and Associated Functions, 1958, Macdonald. [L81] Leonard Lewin, Polylogarithms and Associated Functions, 1981, Elsevier North Holland. Second edition of [L58]. Contains a small amount of new material, and an updated bibliography. [L91] Leonard Lewin ed., Structural Properties of Polylogarithms, 1991, v. 37 of AMS Surveys and Monographs. [Z] Don Zagier, Special Values and Functional Equations of Polylogarithms, Appendix A in [L91], p. 377-400.