Dedekind Sums, Carlitz Identity, Reciprocity

Let $a,b\ge2$ be coprime integers. Begin with the line of rational slope $\displaystyle y=\frac ba x$ , drawn from $(0,0)$ to $(a,b)$ .

This small geometric object already contains several familiar reciprocity laws. Eisenstein’s lattice proof of quadratic reciprocity studies the lattice points on one side of this line and extracts only a parity from the count.

Dedekind reciprocity comes from keeping much more information: one records the entire staircase of lattice points just below the line and studies how that staircase deviates from the straight segment. The geometry is the same in both cases. What changes is the resolution at which we observe it.

The condition $(a,b)=1$ is what makes the picture clean. If the line passed through an interior lattice point, then for some $1\le r\le a-1$ we would have $br/a\in\mathbb Z$ . This would imply $a\mid br$ , hence $a\mid r$ because $a$ and $b$ are coprime, which is impossible. Thus the segment from $(0,0)$ to $(a,b)$ meets no lattice point in the interior of the rectangle. There are therefore no boundary ambiguities: every interior lattice point lies strictly above or strictly below the line.

For each $r=1,\dots,a-1$ , put $\displaystyle h_r:=\left\lfloor\frac{br}{a}\right\rfloor$ . The number $h_r$ is the height of the lower staircase in the $r$ -th vertical column. More concretely, the lattice points $(r,s)$ with $1\le s\le h_r$ are exactly the positive-height lattice points in that column which lie below the line. Hence $\displaystyle \sum_{r=1}^{a-1}h_r$ counts all interior lattice points below the diagonal segment. The most elementary symmetry in the picture comes from replacing $r$ by $a-r$ . Since $br/a$ is never an integer for $1\le r\le a-1$ , we have $\displaystyle h_{a-r}=\left\lfloor b-\frac{br}{a}\right\rfloor=b-1-h_r$ .

Pairing the columns gives the basic rational-triangle count

$\displaystyle \sum_{r=1}^{a-1}\left\lfloor\frac{br}{a}\right\rfloor=\frac{(a-1)(b-1)}2.$

This identity says that the interior lattice points of the rectangle divide equally between the two open triangles cut out by the rational line. Eisenstein’s argument uses a carefully chosen half-rectangle and then retains only the parity of a related count. Dedekind sums will instead remember where every step of the lower staircase occurs and how far it sits below the line.

The floor sum knows only the total number of points below the line. It forgets the shape of the staircase. To retain that shape, introduce formal variables $u$ and $v$ , and define the Carlitz polynomial

$\displaystyle C_{a,b}(u,v):=\sum_{r=1}^{a-1}u^{r-1}v^{h_r}=\sum_{r=1}^{a-1}u^{r-1}v^{\lfloor br/a\rfloor}.$

The monomial $u^{r-1}v^{h_r}$ labels the lattice point $(r-1,h_r)$ . Its $u$ -exponent records horizontal position and its $v$ -exponent records vertical position. It is useful to think of $C_{a,b}$ not as a generating function for every lattice point below the line, but as a generating function for the horizontal edges of the lower staircase. Indeed, multiplying one monomial by $u-1$ gives $\displaystyle (u-1)u^{r-1}v^{h_r}=u^rv^{h_r}-u^{r-1}v^{h_r}$ . These two terms correspond to the right and left endpoints of the horizontal edge at height $h_r$ .

The staircase also has vertical edges. Define $\displaystyle k_s:=\left\lfloor\frac{as}{b}\right\rfloor$ for $1\le s\le b-1$ . The vertical edge at level $s$ goes from $(k_s,s-1)$ to $(k_s,s)$ , so its contribution is $\displaystyle u^{k_s}(v^s-v^{s-1})$ . Summing these vertical edges produces $\displaystyle (v-1)C_{b,a}(v,u)$ , where the variables are reversed because transposing the picture exchanges horizontal and vertical coordinates.

The horizontal and vertical edges fit together into one monotone lattice path from $(0,0)$ to $(a-1,b-1)$ . The reason is that $h_r=s$ precisely when $\displaystyle s\le\frac{br}{a}<s+1$ , or equivalently $\displaystyle \frac{as}{b}\le r<\frac{a(s+1)}b$ . Thus the horizontal edges at height $s$ occur consecutively between the appropriate vertical edges. No gaps occur, and no edge is repeated. When all oriented edges are added, every interior vertex appears once with positive sign and once with negative sign. The intermediate vertices cancel exactly. Only the first and last vertices survive, giving the Dedekind–Carlitz reciprocity identity

$\displaystyle (u-1)C_{a,b}(u,v)+(v-1)C_{b,a}(v,u)=u^{a-1}v^{b-1}-1.$

This is already a reciprocity law. The ordinary statement that two rational triangles complement one another inside a rectangle has become a weighted identity. Instead of assigning the weight $1$ to each lattice point, we have assigned each step a monomial that remembers its exact position. The cancellation remains the same, but it now happens edge by edge and monomial by monomial.

For example, take $a=5$ and $b=3$ . Then the staircase heights are $\left(\left\lfloor\frac35\right\rfloor,\left\lfloor\frac65\right\rfloor,\left\lfloor\frac95\right\rfloor,\left\lfloor\frac{12}5\right\rfloor\right)=(0,1,1,2)$ , so $\displaystyle C_{5,3}(u,v)=1+uv+u^2v+u^3v^2$ . On the transposed side one has $\displaystyle C_{3,5}(v,u)=u+u^3v$ . The identity becomes $\displaystyle (u-1)(1+uv+u^2v+u^3v^2)+(v-1)(u+u^3v)=u^4v^2-1$ . Geometrically, this is the telescoping path $\displaystyle (0,0)\to(1,0)\to(1,1)\to(2,1)\to(3,1)\to(3,2)\to(4,2)$ : every middle vertex cancels, leaving only the initial and terminal ones.

The Carlitz identity contains the original floor-sum relation as a very low-order consequence. Differentiate once with respect to $u$ and once with respect to $v$ , then set $u=v=1$ . For a horizontal-edge monomial, one obtains

$\displaystyle \left.\frac{\partial^2}{\partial u\partial v}\left[(u-1)u^{r-1}v^{h_r}\right]\right|_{u=v=1}=h_r$ .

Similarly, the vertical contribution gives $k_s$ . Thus the differentiated Carlitz identity becomes

$\displaystyle \sum_{r=1}^{a-1}\left\lfloor\frac{br}{a}\right\rfloor+\sum_{s=1}^{b-1}\left\lfloor\frac{as}{b}\right\rfloor=(a-1)(b-1).$

This is simply the statement that the two open triangles fill the interior of the rectangle. The first derivative therefore recovers an unweighted count. Higher derivatives recover more refined data: sums of horizontal coordinates, sums of heights, mixed coordinate sums, and eventually the centered mixed statistic that defines the Dedekind sum. In this sense, the floor-sum identity is the lowest-order shadow of a richer finite generating-function identity.

There is also a useful cone interpretation. For a lattice set $S\subseteq\mathbb Z^2$ , write $\sigma_S(u,v):=\sum_{(m,n)\in S}u^mv^n$ . The first quadrant has generating function

$\displaystyle \sigma_{\mathbb Z_{\ge0}^2}(u,v)=\frac1{(1-u)(1-v)}$ .

Split the quadrant along the ray through $(a,b)$ . The upper cone is generated by $(0,1)$ and $(a,b)$ , while the lower half-open cone is generated by $(1,0)$ and $(a,b)$ . Their fundamental parallelograms contain, respectively, the lattice points $(0,0),\ \left(r,\left\lceil\frac{br}{a}\right\rceil\right)$ for $1\le r\le a-1$ , and $(1,0),\ \left(\left\lfloor\frac{as}{b}\right\rfloor+1,s\right)$ for $1\le s\le b-1$ . Since coprimality gives $\left\lceil\frac{br}{a}\right\rceil=\left\lfloor\frac{br}{a}\right\rfloor+1$ , the two cone series are

$\displaystyle \sigma_{\text{up}}(u,v)=\frac{v+uvC_{a,b}(u,v)}{(1-v)(1-u^av^b)},\qquad \sigma_{\text{low}}(u,v)=\frac{u+uvC_{b,a}(v,u)}{(1-u)(1-u^av^b)}.$

The cone series of the ray joining $(0,0)$ and $(a, b)$ is $\frac{1}{1-u^av^b}$ . The sum of all these three cone series is the generating function of the first quadrant. Clearing denominators gives the Carlitz identity again. Thus the finite staircase relation is also the numerator identity produced by decomposing a rational cone into two simpler cones. This viewpoint is useful because the same pattern persists in higher-dimensional lattice-point geometry.

To pass from an unweighted lattice count to Dedekind reciprocity, we must stop measuring only the heights $h_r$ and instead measure the error between the line and the staircase. Write $\displaystyle {x}:=x-\lfloor x\rfloor$ for the fractional part, and define the sawtooth function by

$\displaystyle ((x)):=\begin{cases}\{x\}-\frac12,&x\notin\mathbb Z,\\ 0,&x\in\mathbb Z.\end{cases}$

For coprime $a,b$ , the Dedekind sum is

$\displaystyle s(b,a):=\sum_{r=1}^{a-1}\left(\left(\frac ra\right)\right)\left(\left(\frac{br}{a}\right)\right).$

Neither $r/a$ nor $br/a$ is an integer in this range, so the sawtooth factors are simply centered fractional parts. Put $x_r:=\frac ra-\frac12$ and $y_r:=\Big\{\frac{br}{a}\Big \}-\frac12$ . Since $\Big\{\frac{br}{a} \Big \}=\frac{br}{a}-h_r$ , we can write

$\displaystyle s(b,a)=\sum_{r=1}^{a-1}\Big(\frac ra-\frac12\Big)\Big (\frac{br}{a}-\lfloor\frac{br}{a}\rfloor-\frac12 \Big )=\sum_{r=1}^{a-1} x_ry_r.$

This formula explains the geometric content of the Dedekind sum. The quantity $x_r$ is the centered horizontal location of the $r$ -th step. The quantity $y_r$ is the centered vertical discrepancy between the line and the staircase at that step. Their product measures whether a step lying to one side of the midpoint tends to lie above or below its typical vertical error. Thus $s(b,a)$ is a covariance-like mixed second moment of position and deviation. It is not merely a second moment of the raw staircase heights. The centering by $1/2$ removes the average linear behavior and isolates the oscillatory arithmetic part of the staircase.

To make this statistic emerge from the Carlitz polynomial, introduce the centered exponential transform

$\displaystyle \mathcal F_{a,b}(X,Y):=\sum_{r=1}^{a-1}e^{Xx_r+Yy_r}.$

This is the generating function of the centered data. It is related to $C_{a,b}$ by a simple shear of coordinates. Set $U:=e^{X/a+bY/a}$ and $V:=e^{-Y}$ . Then the monomial $U^{r-1}V^{h_r}$ has exponent $(r-1)\left(\frac Xa+\frac{bY}{a}\right)-Yh_r$ . Multiplication by the fixed factor $\displaystyle e^{(1/a-1/2)X+(b/a-1/2)Y}$ changes this exactly into $Xx_r+Yy_r$ . Therefore

$\displaystyle \mathcal F_{a,b}(X,Y)=e^{(1/a-1/2)X+(b/a-1/2)Y}C_{a,b}\left(e^{X/a+bY/a},e^{-Y}\right).$

The meaning of the substitution is important. The original $v$ -variable measured raw vertical height. The new $Y$ -variable measures vertical error relative to the line. A horizontal movement of one unit carries a compensating $b/a$ vertical contribution, so the quantity that remains is $br/a-h_r$ , namely the fractional part of $br/a$ . The coordinate system has been sheared to align with the rational slope.

Multiplication by $b$ permutes the nonzero residue classes modulo $a$ . Consequently, the values $\displaystyle \Big \{\frac{br}{a}\Big\}$ for $1\le r\le a-1$ are merely a rearrangement of $\frac1a,\frac2a,\dots,\frac{a-1}{a}$ . Hence $\displaystyle \sum_{r=1}^{a-1}x_r=0$ and $\displaystyle \sum_{r=1}^{a-1}y_r=0$ . The two square sums agree, and their common value is

$\displaystyle A_a:=\sum_{r=1}^{a-1}\Big(\frac ra-\frac12\Big)^2=\frac{(a-1)(a-2)}{12a}.$

The vanishing of the linear terms means that the first nontrivial information in the Taylor expansion of $\mathcal F_{a,b}$ occurs at quadratic order. Expanding the exponential term by term gives

$\displaystyle \mathcal F_{a,b}(X,Y)=(a-1)+\frac{A_a}{2}(X^2+Y^2)+s(b,a)XY+O_3(X,Y),$

where $O_3(X,Y)$ denotes terms of total degree at least $3$ . The coefficient of $XY$ is exactly $\sum_r x_ry_r=s(b,a)$ . Thus Dedekind’s sum is literally encoded in the quadratic Taylor expansion of the centered staircase transform.

The Carlitz identity is exact, so after the change of variables it remains exact. Let $Z:=-\frac{X+bY}{a}$ . The choice of $Z$ is forced by the transposed staircase: it makes the variables in $C_{b,a}(v,u)$ become the variables defining $\mathcal F_{b,a}(X,Z)$ . Substituting the centered transforms into the Carlitz identity gives

$\displaystyle \begin{aligned} &= e^{\frac{X+Y}{2}}-e^{(1/a-1/2)X+(b/a-1/2 )Y} \\ &\Big (e^{X/a+bY/a}-1\Big)\mathcal F_{a,b}(X,Y)\ +\Big(e^{-Y}-1\Big)e^{X/(2a)+(1/2+b/(2a))Y}\mathcal F_{b,a}\Big(X,-\frac{X+bY}{a}\Big) . \end{aligned}$

This formula may look complicated, but its meaning is simple. It is still the same path identity: horizontal edges plus vertical edges telescope to the two endpoints. The only change is that the coordinates have been sheared and centered so that the quadratic terms measure Dedekind sums rather than raw staircase heights. Write $S:=s(b,a)$ and $T:=s(a,b)$ . The quadratic expansions are

$\displaystyle \mathcal F_{a,b}(X,Y)=(a-1)+\frac{A_a}{2}(X^2+Y^2)+SXY+O_3(X,Y),$

$\displaystyle \mathcal F_{b,a}(X,Z)=(b-1)+\frac{A_b}{2}(X^2+Z^2)+TXZ+O_3(X,Z).$

To obtain reciprocity, compare the coefficient of $X^2Y$ in the exact identity. This is the first coefficient at which both $S$ and $T$ occur. In the first term, write $\displaystyle \alpha:=\frac Xa+\frac{bY}{a}$ . The relevant contributions come from $\displaystyle \frac Xa\cdot SXY$ , from $\displaystyle \frac{bY}{a}\cdot\frac{A_aX^2}{2}$ , and from the cubic term $\displaystyle \frac{\alpha^3}{6}\cdot(a-1)$ . Their total is $\displaystyle \frac Sa+\frac{bA_a}{2a}+\frac{b(a-1)}{2a^3}$ .

For the second term, the degree-one part of $\displaystyle e^{-Y}-1$ is $-Y$ . Since $\displaystyle Z=-\frac{X+bY}{a}$ , the coefficient of $X^2$ in the quadratic part $\frac{A_b}{2}(X^2+Z^2)+TXZ$ equals $\frac{A_b}{2}\left(1+\frac1{a^2}\right)-\frac Ta$ . Multiplying by $-Y$ gives the corresponding contribution. There is also a contribution from the constant term $b-1$ in $\mathcal F_{b,a}$ : the coefficient of $X^2Y$ in $(e^{-Y}-1)e^{X/(2a)+(1/2+b/(2a))Y}$ is $-\frac1{8a^2}$ . The right side contributes $\frac1{16}-\frac12\left(\frac1a-\frac12\right)^2\left(\frac ba-\frac12\right)$ . Thus coefficient comparison gives

$\displaystyle \begin{aligned} &\frac{S+T}{a} +\frac{bA_a}{2a}+\frac{b(a-1)}{2a^3} -\frac{A_b}{2}\Big(1+\frac1{a^2}\Big)-\frac{b-1}{8a^2} \\ &=\frac1{16}-\frac12\Big(\frac1a-\frac12\Big)^2\Big(\frac ba-\frac12\Big). \end{aligned}$

Now substitute $\displaystyle A_a=\frac{(a-1)(a-2)}{12a}$ and $\displaystyle A_b=\frac{(b-1)(b-2)}{12b}$ . The remaining calculation is a simplification of rational functions in $a$ and $b$ . After collecting terms, one obtains

$\displaystyle s(b,a)+s(a,b)=\frac{a^2-3ab+b^2+1}{12ab}.$

Equivalently, in the standard symmetric form,

$\displaystyle s(b,a)+s(a,b)=-\frac14+\frac1{12}\left(\frac ba+\frac ab+\frac1{ab}\right).$

This is Dedekind-sum reciprocity. The formula has emerged from the same finite staircase that gave the elementary floor-sum identity. The difference is that we no longer look merely at the number of lattice points below the line; we retain the centered mixed second-order information contained in the staircase.

Eisenstein’s proof of quadratic reciprocity and the present argument should therefore be viewed as two readings of the same rational lattice picture. Eisenstein counts suitable points in a half-rectangle and retains a parity-sensitive quantity; Gauss’s lemma then turns that parity into a quadratic-residue sign. The Dedekind-sum argument keeps the full lower staircase. The Carlitz polynomial records its horizontal and vertical edges one by one, and the centered transform measures both the horizontal position of each step and the fractional error between the step and the rational line. More precisely, Eisenstein’s argument records a parity-sensitive lattice count, whereas Dedekind reciprocity records the centered covariance between position and slope error.

This is why lattice paths, rational cones, generating functions, and reciprocity laws belong together. A rational line cuts a rectangle into complementary lattice regions. The common boundary is a finite staircase. The path identity gives a polynomial reciprocity law. Low derivatives recover ordinary lattice counts, while centered quadratic terms recover Dedekind sums. In higher-dimensional cone decompositions, the same mechanism produces higher Dedekind sums, Todd-polynomial corrections, and Ehrhart-type reciprocity formulas.

Share this:

Related

Leave a comment Cancel reply